当前位置： IC37首页 > 技术资料 > 嵌入式系统 > 一种基于逆序算子的优化组合遗传算法
一种基于逆序算子的优化组合遗传算法
类别：嵌入式系统
来源：电子技术应用 作者：马书南 帅训波 曹凤雪
摘要：针对遗传算法(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。
实验结果表明，没有进行逆序算子运算的结果容易发散，一旦临近最优值点，很难再逼近。进行逆序运算的结果不容易发散，局部搜索性强，但一旦临近极小值，就很难跳出，全局搜索能力有所降低。综合评价局部搜索能力和全局搜索能力，每隔30代进行一次逆序算予运算的效果较好。
2 优化组合遗传算法
2．1 算法构造
利用逆序算子增强局部搜索性能的特点，并且最大限度地减少对全局搜索的影响，把全局搜索算子和局部搜索算子优化组合，构造一种基于逆序算子的优化组合遗传算法。全局搜索算子为高变异和低杂交率的均匀杂交法，局部搜索算子为逆序算子与低变异率和高杂交率单点交叉法。该算法把搜索过程分为全局搜索和局部搜索两个阶段，操作过程为：首先在繁殖代数的前四分之三代启动全局搜索算子，为全局搜索阶段；后四分之一代数启动基于逆序算子的局部搜索算子，为局部搜索过程；对于最终最优解采用每代迭代法来确定最终全局最优解。实验结果表明该优化组合遗传算法具有良好的全局搜索性能和局部搜索性能。
该组合优化遗传算法的编码采用位、串结构型编码，有二进制编码、实数编码、浮点数编码、格雷编码等。常用的选择算子如转盘式选择、锦标赛选择等，转盘式选择法不能使传统遗传算法收敛至全局最优解，锦标赛选择策略能避免超级个体的影响，但对局部搜索不利，关于本文的选择算子的遗传算法的收敛性将在后面做出证明。本算法中采用排序选择的方法作为选择算子。在求解过程中，根据个体的适应度大小，然后把一定的概率分配给个体，作为个体的选择概率。
在全局搜索和局部搜索阶段，分别考虑杂交和变异方式的优化选择的同时，要和其参数相适应。在全局搜索阶段，采用对全局搜索有效的均匀杂交方式，均匀杂交方式破坏模式的概率大，在搜索过程中能以较大的概率搜索到点式杂交无法搜索到的模式，但此杂交方式对局部搜索不利，因此其杂交概率一般不要过高，在0．30~0．60之间为好。为了兼顾局部搜索概率，变异率设置稍大一些，在0．03~0．1之间。在局部搜索阶段，每隔30代启动逆序算子运算。采用破坏模式概率小的点式杂交，其杂交率一般不宜过低，在0．6~0．85之间，为了兼顾全局搜索概率，变异率设置应偏小，在0．005~O．02之间。
2．2 优化组台遗传算法实现过程
具体分析上述构造基于GR的优化组合遗传算法各个环节，其过程描述如下：
(1)根据约束条件，生成二进制编码的初始化种群，初始全局最优解为P；
(2)计算种群各个染色体的适应度；
(3)根据排序选择算法对群体进行排序选择，如果本代的最优解优于P，则P被本代最优解替代；
(4)如果属于全局搜索阶段，按全局搜索阶段的交叉和变异算子生成满足条件的新种群；
(5)如果属于局部搜索阶段，按局部搜索阶段的交叉和变异算子生成满足条件的新种群，并且每隔30代启动一次逆序局部搜索算子；
(6)判断是否满足优化组合遗传算法的结束条件，如果满足结束条件，输出最终解P，否则转向(2)；
(7)输出结果。
2．3 算法收敛性分析
定理如果变异概率Pm∈(0，1)，交叉概率Pc ∈(0，1)，同时采用排序选择算法和局部搜索策略，遗传算法最终收敛到全局最优解。
证明：令Fk是时刻k，状态为λi时群体中的最大适应度，F*是遗传算法所求问题的全局最优解的适应度。若S0是含有最优个体X*群体的集合，那么X*的适应度F0=F*。因此，如果状态λi进入S0，λk(k=i+1，……)将以概率1处于S0中，即S0为闭集。由于采用排序选择算法，并按给定的概率表来进行选择，在选择之后，排在最前面的个体被选择，也就是最佳的个体被选择后保留。
由于陈国良等已证明了对于变异概率Pm∈(0，1)，交叉概率Pc∈(O，1)。并采用选择后保留当前最优值的遗传算法能收敛到全局最优解。
应用马尔克夫链理论可证明局部搜索策略可在某一时刻j，进入搜索状态Sj，并且Sj是含有最优个体X*的小群体(状态)的集合Sj∈S08，X*的适应度F0=F*，那么Sj收敛到全局最优解。
由此可证基于逆序算子的本文优化组合遗传算法具有良好的全局收敛性。
2．4 试验结果对比及分析
为了验证本文的优化组合遗传算法具有良好的局部搜索性能和更好寻优能力，对Shubert函数测试和传统遗传算法进行试验比较。二者均采用二进制串编码，排序选择算法选择策略，种群规模m=80。传统遗传算法的均匀杂交率为O．60，变异率为0．1。组合优化遗传算法全局搜索阶段均匀杂交率Pc=0．45，变异率Pm=O．05，局部搜索阶段每30代进行逆序算子运算，点式杂交率Pc′=0.7，变异率Pm′=0．0l，对比试验分别繁殖800代、1200代、1600代、2000代随机测试200次，结果平均值为随机取实验10次的平均，如表2和表3。
由表2和表3比较可见，基于逆序算子的优化结合算法与传统的遗传算法相比较，具有较好的寻优能力。由于逆序算子在局部搜索阶段的作用，搜索结果分布相对集中，搜索到的优化值的效率较高，有良好的全局搜索性能和局部搜索性能。
本文从引入逆序算子的角度，改善了遗传算法本身的局部搜索性能。把逆序算子作用于优化组合算法的局部搜索阶段，实验结果表明该优化组合遗传算法具有较强的局部搜索性能和更好的寻优能力。逆序算子增强了遗传算法本身的局部搜索性能，同时也破坏了种群的多样性，在一定程度上影响了全局搜索能力。如何提出一种新型的遗传算子，从遗传算法本身解决好全局搜索和局部搜索之间的矛盾，这将是一个有意义的研究方向，也是今后研究的重点之一。
