基于遗传算法的染色体编码的分析.doc

基于遗传算法的染色体编码的分析
第19卷第1期
2010年1月
重庆电子工程职业学院Vo1。19NO。1
lan.2010oumalofChon￡咽in￡CoUe~eofElectronicEnl～ine
基于遗传算法的染色体编码的分析
吴焱岷
(重庆大学计算机学院，重庆400044；重庆电子工程职业学院，重庆401331）
摘要:遗传算法为解决复杂问题，特别是NP类问题提供了一种全新的思路，其编码方式也将在一定程
度上决定算法效率的高低和程序设计的复杂程度.需要针对想要解决问题类型的不同而采取不同的编码方式.
关键词：遗传算法；编码;值类型；事务类型
中图分类号：TP39文献标识码:A文章编号：1674-5787（2010)01一【）【】86一O2
遗传算法的概念最早是由BagleyJ.D在1967年提出
的.而开始遗传算法的理论和方法的系统性研究在1975
年开始.这一开创性工作是由Michigan大学的J。H.
Holland所实行。遗传算法简称GA(GeneticAlgorithm），在
本质上是一种不依赖具体问题的直接搜索方法。其基本
思想是基于Darwin进化论和Mendel的遗传学说
Darwin进化论最重要的是适者生存原理它认为每
一
物种在发展中越来越适应环境.物种每个个体的基本
特征由后代所继承。但后代又会产生一些异于父代的新
变化.
Mendel遗传学说最重要的是基因遗传原理它认为
遗传以密码方式存在细胞中。并以基因形式包含在染色
体内每个基因有特殊的位置并控制某种特殊性质，所
以。每个基因产生的个体对环境具有某种适应性.基因突
变和基因杂交可产生更适应于环境的后代。经过存优去
劣的自然淘汰。适应性高的基因结构得以保存下来。
遗传算法最大的特点莫过于可以绕过复杂的数学推
导而采用最直接的方式在有限空间中搜索结果。例如求
函数f(x）=x＊sin(10”n’x)+2在（一1，2)区间上的极大值,按照
常规思路.需要对函数求导，找出函数的变化趋势和拐
点。才能确定最大值的位置.对于相对简单的函数。采用
这些数学的方法还没有太高的难度.但是对于复杂的函
数。则需要较为深厚的数学功底.同时也增加了程序设计
的复杂程度
对于GA.采用一套全新的思路,首先任意给定一组
随机值x。由此开始进行演化.这些值就是代表一系列原
始生命。这些生命是否可以延续，取决于他们的适应程
度将这些随机值带入函数中进行运算，对得到的一系列
函数值进行排序.求最大值，可以认为值较大的函数值对
应的x接近我们所需要的结论,这些结果可以保留;反
之。对于另外一些函数值较小的x。则表明应该被淘汰.
第二步就是按照Mendel的基因理论。对这些将被淘
汰的X进行演化.演化分两步进行:
（1)交叉。两个x值交换数据,类似生物界的交配,染
色体进行重新重组。交换基因以期得到新的品种，新品种
可能更加适应环境而得到生存的机会.也可能向相反的
方向发展。从而失去生存的机会。因此通过某种方式得到
新的X的值可以导致函数值增大。也可能导致减小，他们
都将参加新一轮的竞争
（2）变异。单一的X值进行自身的调整，这类似于生
物界的染色体发生基因突变。突变后的基因也可能导致
物种更加适应或更加不适应环境。因此通过突变方式后
要重新评估函数值以决定新的X值的去留.同样新的X
值也必将参加新一轮的竞争
通过一系列操作.我们始终保留函数值较大的一系
列X.如同生物竞争中只有最强的个体才能生存下来一
样。最终我们可以得到最佳答案
按照上面的思路。我们任意产生100个随机数。经过
100代的进化。得到如下结论：
在第27代最早出现最佳运算结论：
f（1.8505594374083l1=3。85027363583461
共使用4。828125秒。起始时间：21:54：08.31，结束时
间：21：54：12。859
经过反复测试。结果可以稳定x=1.85附近。这和理论
值也是非常近似的那么GA是如何保证这种收敛性的
呢7原因就在于它的编码方式可以很好地与基因理论相
融合.
显然。由于X的编码方式千差万别，因此J.H.Holland
本人也提及采用二进制才是最佳方式.这样做的好处有
两点：
收稿日期:2009一l2一l8
作者简介:吴焱岷(1974一),男，湖北武汉人,重庆大学计算机学院计算机科学技术专业2004级在职研究生，重庆电子工程职业
学院计算机应用系党总支副书记,主要从事软件设计,网站建设方面的研究.
87重庆电子工程职业学院第19卷
1。数据在计算机内部就是采用二进制方式。这样的
编码方式与计算机内部的数据表示相吻合。便于计算机
的处理
2。如同染色体的基因.每一位二进制数据单元就是
可以进行操作的最小单元。便于对交叉与变异这两种基
本的遗传现象的模拟
正是将生命遗