阅读文章--机电之家
一种基于逆序算子的优化组合遗传算法
[ 来源：'d' | 类别：技术 | 时间：2009-5-14 11:07:50 ] [字体：]
针对遗传算法(GA)局部搜索能力差的问题，从提出基因逆序算子的新角度，构造了一种基于逆序算子的优化组合遗传算法，从理论上证明了该算法的收敛性。
遗传算法是一种具有全局搜索能力的进化算法，已经在许多领域得到成功应用，但它存在局部搜索能力较差的缺点。针对遗传算法的全局搜索和局部搜索之间的矛盾，Ge Hong等提出了GA与模拟退火算法结合的方案，Fogel D B给出了GA与进化规划(EP)融合算法。上述混合遗传算法均是利用遗传算法的全局性，从同时结合特定问题的局部搜索技术的角度，有效地弥补了GA的局部搜索不足的缺点，但是均未能很好地改善遗传算法本身的局部搜索性能。
本文模拟生物染色体中基因排列有序性，启发于转基因科学技术，从逆序算子的角度改善遗传算法的局部搜索能力，借鉴遗传算子的优化组合方案，构造了一种基于逆序算子的优化组合遗传算法，既基于传统的遗传算法，又有别于传统的遗传算法和混台算法。实验结果表明，该算法比传统的遗传算法具有较强的局部搜索性能和更好的寻优能力。
1 基因逆序算子
1．1 逆序算子的提出
遗传算法是基于进化思想的一种优化算法，很多的改进都来源于生物进化的启示，并且遵循进化规则。在遗传学中，染色体所携带的遗传基因决定个体发育的方向和全过程，个体发育过程就是特定基因有序地活化和表达的过程。染色体的每个基因都含有大量的信息，并且有显性基因和隐性基因之分。隐性基因是在特定的情况下表现其特性，改变生物体性能。在科技发达的今天，转基因技术给人类带来了无限美好的憧憬，在尝试改变癌变细胞的基因组排序方面不断取得新突破。此外。在现实世界中物质的排列结构对物质的性能影响较大，例如由于碳原子排列不同，从而形成性能截然不同的金刚石和石墨。
在位串编码遗传算法中，染色体的表示是一个有序位串基因组，含有的信息量比较少。模拟生物染色体中基因排列有序性和转基因技术应用，对于染色体的基因组存在一个基因反序排列的基因组，构成不同的染色体。由此提出了对染色体按基因组排列不同，分为显性基因组和隐性基因组。在位串编码中，染色体的顺序基因组称为显性基因组，该染色体的一种隐性基因组由基因组的反序列构成，由显性基因组到隐性基因组称为一次基因转换，逆序算子模仿了转基因技术，完成了基因转换，增强了染色体的适应度。
定义l：若染色体的反序列基因组有意义，设染色体X=x1x2……xn-1xn，则X′=xnxn-1……x2xl是X的逆序隐性基因组。
定义2：逆序算子(GR)是实现由X到X′转换的遗传算子，若X′的适应度优于X的适应度，则X被X′替代，反之，X′被淘汰。
1．2 局部搜索能力的提高
模式定理使遗传算法在位串基因的染色体对其性能分析有了基本定理描述手段。应用模式定理分析，经过逆序算子运算后的种群，每个染色体均保留了较高适应度的基因组，形成了规模不变的新种群，通常情况下，对于总体平均适应度和最优个体适应度，运算后的种群优于或者一定不亚于运算前的种群。
新种群的形成，符合遗传算法搜索方向，向搜索目标更加逼近和集中。逆序算子对当前种群表达的样本空间进行尽可能的搜索，快速找到染色体代表子空间的当前状态最优解，增加遗传算法的局部搜索能力，因此逆序算于是一种具有良好局部搜索性能的遗传算子。大量实验分析证明，在一定的程度上也破坏了种群的多样性，在实际操作中，不宜每代都进行逆序算子运算。
对Shubert函数测试逆序算子的局部搜索能力，此函数有760个局部极小点，其中(-1．42513，-0．80032)为全局最小点，最小值为-186．7309。此函数容易陷入局部极小值-186 34027。实验采用二进制串编码，锦标赛选择策略，均匀杂交概率PC=0．45，变异率Pm=O．01，种群规模m=80，遗传代数N=1500代。对无逆序算子运行(SGA)，每隔10代、30代、50代进行逆序算子运算，分别实验200次，结果平均值为随机取5次的平均，如表l。
浙ICP备05041018号
