【改进自适应遗传算法的性能分析】 遗传算法matlab程序
摘要：遗传算法存在未成熟收敛和收敛速度慢等不足之处，传统的自适应遗传算法虽能有效提高算法的收敛速度，却难以增强算法的鲁棒性。文中提出的改进的自适应遗传算法，提高了其搜索能力，具有更快的收敛速度和更可靠的稳定性，达到了预期的效果。关键词：遗传算法；自适应；收敛；改进；性能
中图分类号: TP18文献标识码：A文章编号：1009-3044(2012)21-5202-04
遗传算法(Genetic Algorithm，以下简称GA)[1]是一种模仿生物群体进化的随机优化算法，它是由美国密歇根大学J.H.Holland教授创立的。标准的遗传算法(Standard GA，以下简称SGA)往往存在一定的不足之处，比如容易出现早熟以及过慢的收敛速度等不良现象。鉴于此，Srinvas等提出了自适应遗传算法(Adaptive GA，以下简称AGA)[4]，在GA中应用自适应调整交叉率和变异率，结果证明，这种算法在GA的收敛速度方面能够较好的改进。不过，AGA在演化初期存在停滞现象，故将自适应调整交叉率和变异率的方法用于GA以提高算法收敛速度和鲁棒性仍十分具有挑战性[6]。文献[3]提出一种改进的自适应遗传算法，在一定程度上提高算法的计算速度和收敛速度。但因为它们计算所得到的变异概率Pm及交叉概率Pc具有不良的稳定性，同时该算法对整体协作能力存在不足。
为此，该文提出一种新的改进遗传算法，改进后的算法效果良好，在算法的收敛速度以及全局搜索性能等方面都具备良好的效果。
公式中：?max是指群体的最大适应度；?avg是指群体的适应度平均值；?’是指杂交双方适应度大者的适应度；?是指个体的适应度；0
针对M.Srinivas所提出的算法的缺点，文献[3]提出一种改进的自适应遗传算法。其通过判断适应度集中程度的情况，对整个群体的Pm以及Pc进行自适应地变化调整，同时将群体适应度的集中程度用三个变量来衡量，即：适应度平均值、群体的最大适应度、最小适应度。文献[3]提出的算法在一定程度上可以提高算法的计算速度和收敛速度。但因为它们计算所得到的变异概率Pm及交叉概率Pc具有不良的稳定性。尤其在遇到峰值密度较高的多峰值函数时，更容易出现得到概率较大的结果的现象。同时，该算法在一定程度上也是缺乏对算法的整体协作能力。
整体把控能力等方面都存在一定的不足之处。为此，本文在基于上述自适应遗传算法的基础上，提出一种新的自适应遗传算法，以改进其在上述所存在的不足。
2.1与进化代数有关的杂交概率的改进介绍
杂交算子的主要目的是用来产生新个体，同时也是为了让算法具备全局搜索的能力。因此，当我们以种群中的个体来观察时，如果杂交的概率偏大，群体中的优良模式就会被破坏；而如果杂交的概率偏小时，对于新个体的产生速度又会变得缓慢。在这里可以看出，与个体适应度有关的杂交概率的算法是具有一定的优势的。当我们以种群整体进化的整个过程来观察时，杂交概率应该会一个稳定但会慢慢变小，最终会向某一个稳定值靠近的过程。当我们以新个体的产生方面来看，在杂交操作上，群体中所有的个体应该具有相同的地位，也就是概率是一样的，这样就可以使得遗传算法在搜索空间拥有每个方向的匀称性。文献[3，4]的交叉概率算法都只注意了个体的作用，而忽视了整个种群的进化趋势情况和各个体的变异机会。
在本文中，为了改善目前算法所存在的不足，设计了一种与适应度没有关系，只同进化代数有关的概率公式：
本公式可以达到交叉概率随着进化过程而逐渐变化，同时能够对同一代的种群中的个体给予一样的交叉能力。这样也可以更好的实现全局搜索能力，同时，算法的计算速度也可以得到极大的提高。相对文献[4]，该文的算法对劣质个体的处理显得相对薄弱,但可以通过下面的方法来进行弥补此缺陷。
2.2自适应变异概率的改进介绍
维持种群多样性是变异算子的主要用处，其主要是用来抑制早熟现象的出现以及产生新个体。但杂交算子则不同，其主要是在全局搜索中起作用。因此，就变异概率来说，应该是在同一种群中每个个体都是随着个体本身的好坏而发生变化。同时，变异概率的取值也是十分关键的。如果变异概率的取值偏小，就很容易导致抑制早熟现象以及产生新个体的能力减弱。而如果变异概率取值偏大，又容易导致遗传算法搜索过程成为随机过程的现象产生，从而使种群中较好的模式被破坏的可能性增加。所以，自适应变化的变异操作的设计十分重要。
变异概率设计需要满足：（1）应该使变异概率慢慢减小，从而能够使得群体快速集中。（2）较小的变异概率给优秀的个体。（3）较大的变异概率给劣质的个体。针对上述条件，在本文中设计了如下的自适应变异概率公式：
在公式中，Pm(t)指的是第t代种群中个体Xi的变异概率；Pm,min指的是预先设置的最小的变异概率；Pm,max指的是预先设置的最大的变异概率。
以上式子的计算可以实现变异概率随进化过程自适应地变化。也能够针对所有待变异个体的适应值做相应的自适应变化。
上面所选取的函数在遗传算法性能测试方面都是很经典的函数，它们都有全局最小值，不过也存在有多个极值点的函数。在本实验中，先对函数?1、?3和?4进行求负处理，目的是方便对这些函数求最大值。
3.2仿真实验结果及分析
在对上面三种遗传算法进行仿真实验时，对所用到的参数作说明：收敛时间的单位是秒；群体的规模是64；最大进化代数是180。其他参数见表2
表2各算法中参数说明
针对传统遗传算法的早熟和收敛速度慢等缺点，文中提出一种改进的自适应遗传算法，实验数据表明，该算法具有良好的搜索能力，具有更快的收敛速度和更可靠的稳定性，达到了预期的效果。
[1] Holland J H.Adaptation in Natural Artificial Systems[M].MIT Press,1975.
[2] Masanori Suglsaka,Xinjian Fan.Adaptive Genetic Algorithm with a Cooperative Mode[C].Proceedings of IEEE International Symposium on Industrial Electronics,2001.
[3]王蕾,沈庭芝,招扬.一种改进的自适应遗传算法[J].系统工程与电子技术,2002:24（5）:75-78.
[4] Srinvas M,Patnaik L.M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Trans on Systems,Man and Cyber? netics,1994:24(4).
[5]欧阳森,王建华,耿英三,等.一种新的改进遗传算法[J].计算机工程与应用, 2003(11).
[6] F Herrera,M Lozano.Adaptive Genetic Operators Based on Coevolution with Fuzzy Behaviors[J].IEEE Trans on Evolutionary Computation, 2001(5):149-165.
[7]李茂军,童调生.用单亲遗传算法求解有序组合优化问题[J].系统工程与电子技术,1998(20):58-61.
[8]王小平,曹立明.遗传算法:理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[9]沙智明.基于改进自适应遗传算法的电力系统相量测量装置安装地点选择优化[J].电工技术学报,2004(8).