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

基于遗传算法的染色体编码的分析第19卷第1期2010年1月重庆电子工程职业学院Vo1。19NO。1lan.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。如同染色体的基因.每一位二进制数据单元就是可以进行操作的最小单元。便于对交叉与变异这两种基本的遗传现象的模拟正是将生命遗传，进化的规律运用到程序设计中，所以程序运行符合自然规律.可以得到理想的结果遗传算法在当时提出主要解决科学计算方面的问题.即值类型的问题.采用二进制的形式可以很好的解决