一种提高遗传算法全局收敛性的方法-

1、收稿日期:2002-11-22基金项目:教育部高等学校骨干教师资助计划;辽宁省自然科学基金资助项目(002013作者简介:何大阔(1975-,男,辽宁沈阳人,东北大学博士后研究人员;王福利(1957-,男,辽宁辽阳人,东北大学教授,博士生导师第24卷第6期2003年6月东北大学学报(自然科学版Journal of Northeastern U niversity(Natural ScienceVol 24,No.6Jun.2003文章编号:1005-3026(200306-0511-04一种提高遗传算法全局收敛性的方法何大阔,王福利(东北大学信息科学与工程学院,辽宁沈阳 110004摘 要:通

2、过对遗传算法过早收敛原因的分析,认为遗传算法出现过早收敛主要与问题解的分布状况、种群个体的分布情况及遗传算子的应用有关,提高算法全局收敛性能的核心就是如何使算法科学地处理种群多样性及识别个体对全局收敛性能的作用 提出几类与遗传算法全局收敛性能关系较大的个体,并结合小生境进化共享函数思想,形成一种旨在提高遗传算法全局收敛性、求解全局最优解的遗传算法,仿真结果验证了这种算法良好的全局收敛性能 关 键 词:遗传算法;收敛性;多样性;遗传算子;全局最优;共享函数中图分类号:T P 13 文献标识码:A遗传算法以其鲁棒性、并行性及高效性等优点得到了广泛的应用13但作为一种优化算法,遗传算法也存在一些不足

3、46,收敛于局部极值即过早收敛就是遗传算法存在的一个有待解决的问题 开发一种提高遗传算法全局收敛性能的全局收敛算法具有重要的理论与现实意义 本文基于对算法全局收敛性能影响较大的几类个体结合小生境进化思想提出一种提高遗传算法收敛性能的有效算法1 遗传算法过早收敛的原因遗传算法出现过早收敛的原因很多,首先它与问题解的分布有关 一般说来,寻优算法都是向解的改善方向进行搜索,而这一搜索方向是否为全局收敛的方向即达到最优解的方向却无法确定 于是,当问题解的分布较为复杂、特异时,就极易使优化算法陷入局部极值 所以,对于不同的问题,应对优化算法进行相应的调整以适应这类问题的求解,降低局部收敛的可能性 通常,

4、解的分布状况出现下列情况就极易使算法产生早敛:在最优解附近区域解的分布较为陡峭,个体的适应值跨度较大,靠近最优解的个体的适应值可能很差,这样即使种群中出现了最优区域中的个体,这些个体也可能会因适应值较差而遭淘汰使算法失去进一步在该区域搜索的机会,从而错过最优解;解为多峰分布且最优峰与次优峰距离较近,同时最优解与次优解相差不大,这时极易使算法由于对最优峰没能搜索到底而陷入次优解不能自拔;解为多峰分布且峰与峰之间距离较远,这时算法不能确保各算子能将搜索空间扩展达最优区域,也无法保证这一区域个体的生存机会,于是也就无法保证算法搜索到最优解 遗传算法其自身的不完善及缺陷也是造成早敛现象的原因 目前,G

5、A 的全局收敛理论大都是基于初始种群及进化代数无限大为前提,而这实际上是不可能的,实际指导意义不大 另外,即使能够证明算法可以在有限代内全局收敛概率为1,但有限的定义是多大却无法知道,这事实上也无实用的价值 到目前为止,只能对GA 的全局收敛性能进行改进或改善,而无法确保其全局收敛另外,遗传算法初始种群的产生方法与初始种群的规模对初始种群的个体分布状况有着相当的影响,而初始种群的个体分布状况又直接影响算法的全局收敛性能 由于传统GA 的初始种群是随机选取的,初始种群的覆盖空间具有很大的不确定性,如果初始种群空间不包含全局最优解,而遗传算子又不能在有限的进化代数内将覆盖空间扩延到全局最优解所在的

6、区域,那么过早收敛就不可避免 所以,确保初始种群的多样性与个体分布的相对合理性就是改善GA 全局收敛性首先要解决的问题 由初始种群开始进行寻优搜索,在进化的过程中种群的个体分布变化的状况也决定了算法的全局收敛性能 初始种群中没有的最优解的信息可以通过群体的进化来得到,从而达到最优解 但如果种群在有限的代数内不能将种群引导到最优解所在区域(即种群个体的分布无法覆盖最优解区域并有机会搜索该区域,就会造成算法早敛 GA寻优过程中种群分布的变化几乎与GA所有的组成部分有关 各算子的计算形式、操作方式及操作概率,算法整体的寻优结构等都决定了种群中个体分布的变化 其中,人们已广泛认识的由于超级个体的出现而

7、导致的局部极值问题就是与算法的选择、交叉、变异都有关的 实际上,无论是初始种群的分布状况、还是进化中种群分布的变化状况,其核心都是希望种群无论是初始还是进化过程中都尽可能保持多样性并在尽可能少的代数内将寻优搜索引导到最优解区域7 目前,人们大多是通过对选择与变异的改进以保持种群在进化的过程中始终保持多样性,从而在一定程度上克服过早收敛 但由于算子本身的随机性,仅靠算子是不能确保算法搜索到最优解区域的 比如,变异算子使算法具有爬山能力从而改善算法的全局收敛性能,但其随机性无法确保寻优过程在有限且尽可能少的进化代数内搜索到全局最优解所在区域 同时,保持多样性的确可以对算法的全局收敛性能进行改善,但

8、这样做究竟对全局收敛性有多大贡献无从考量,片面地强调多样性有时不仅不能防止早敛的发生,还会对算法的稳定性、种群的整体收敛性造成很大影响 种群多样性的保持策略必须具有一定的指导性,使算法在寻优过程中的多样性是一种以一定的原则将群体引导到有利于全局收敛的多样性 另外,本文认为单纯保持多样性是不够的,因为在寻优过程中群体中不乏最优解区域中的个体出现,不过这些个体往往由于适应值较低而很快被淘汰,问题是如何保护好这些个体使算法有机会搜索该区域 所以,如何评价个体尤其是那些适应值不大甚至较差的个体的寻优作用并加以保护,对于改善GA的全局收敛性能也是很重要的 遗传模拟退火法中的概率接受劣解就是在种群多样的同

9、时增加较差解的生存机会,进而达到全局收敛的目的2 算法的提出与实现应该说要克服过早收敛必须处理好两大问题:第一,如何保持种群多样性;第二,如何鉴别个体对全局收敛性能的作用并加以保护与引导 保持种群多样性的方法很多,如初始种群平均分布与其补码个体相结合、引入个体间距离的概念以避免近亲繁殖等,在此不进行详述 这里主要讨论一下如何鉴别个体对全局收敛性能的作用并加以保护与引导的问题 由于传统GA是采用定向选优模式,不接受差解 所以,要对某些个体实施保护就要对传统GA选择的指导思想及操作策略进行改进 但完全依靠随机性的概率接受劣解是无法保证GA的全局收敛性的 算法本身必须指导算子哪些个体是应该保护的,而

10、哪些个体应该淘汰,也就是如何评价个体对全局收敛性能的作用以决定是否接受该个体 事实上,给出准确的定义是很困难的,只能在算法寻优过程中,定义哪些个体应提起一定的注意力或重视程度 也就是哪些个体可能对全局收敛是有益的甚至是重要的,然后对这类个体加以保护避免其很快遭到淘汰而造成早敛,提高全局收敛的可能性本文认为值得注意的个体有以下几类:第一类为适应值较好但距离当前最好解较远的个体,因为这类个体可能暗示种群搜索到了远离群体集中区域的峰值区域;第二类为距离当前最好解较近个体而适应值较差的个体,这类个体可能意味着最好解较近可能还有峰值的存在应给适当的注意;第三类为经算子的寻优计算产生的子代适应值较父代个体

11、适应值有很大改进的父代个体,尤其是适应值较差的这类个体,因为无论这类个体自身的适应度如何,其被改进的速度很快可能是因为该个体所在的区域解的分布较为陡峭,这类区域正是早敛易发的区域,重视这类个体首先可以使算法有机会在第一时间搜索可能快速搜索的区域(即陡峭区域,同时,对这类个体进行一定的保护使其在群体中有机会延长生存的时间给算法更多的机会仔细搜索该区域,因此,保护这类个体有利于达到全局最优解同时有利于局部区域的搜索 这类个体也是提高全局收敛性的重要环节 本文采用算子并行计算结构,即各算子分别对父代进行操作,然后将产生的新个体以一定比例直接进入子代,通过各算子产生的新个体进入子代的比例来调节各算子对

12、GA性能的影响8 在最优保持计算时,应用小生境进化中共享函数思想(这里定义海明距离为共享函数,算法优先选择适应值超过种群平均值且与当前最好值的海明距离高于种群平均值的个体;对于与当前最好值的海明距离低于种群平均值的个体,采取抛弃处理不让其进入子代;采用J=f old-f newf ol d作为个体的自我改进系数,其中,f old为变异的父代个体适应值;f ne w为子代个体适应值 子代个体优于父代个体即f new f o l d,对于J值达到一定阈值的512东北大学学报(自然科学版 第24卷个体进行最优保护9 混合改进遗传算法的计算过程如下:(1确定寻优参数、产生初始种群;(2对群体实施遗传操

13、作,产生遗传子代新群体:计算群体中个体的适应值,将适应值超过种群平均值且与当前最好值的海明距离高于种群平均值的个体作为最优保持子代个体;采用线性均匀交叉算子进行交叉计算,产生交叉子代个体;采用变步长Gaussian 变异算子进行变异计算,某代变异步长为:当k 4时, (k = 1-f *(k -1-f *(k -3f *(k -1,为常数;当k 4时, 取为常数(其中f *(k 为第k 代时的最好值计算群体个体与当前最好解的海明距离并由远到近进行排序,将海明距离序号和适应值序号之和最大的n 1个个体作为第一类启发个体;将海明距离序号和适应值序号之和最小的n 2个个体作为第二类启发个体;群体中参

14、与变异操作的父代个体J 值最高的n 3个个体作为第三类启发个体;(3检验收敛条件,若满足收敛条件则结束遗传进化过程并输出结果;否则,返回(23 仿真研究本文采用文献10中提供的测试函数进行仿真研究,并与文献10的仿真结果进行比较,来验证本文提出的遗传算法的寻优性能 初始种群为50;最优保持、交叉、变异及第一、二、三类启发个体的数量分别为10,15,18,2,2,3 max F 1=0 002+25j =11j +2i=1(x i -a i j 2,-65 536 x i 65 536函数F 1具有多个局部极大点,一般其函数值大于1即可认为收敛,其中:a 1j =-32,-16,0,16,32,

15、-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32;a 2j =-32,-32,-32,-32,-32,-16,-16,-16,-16,-16,0,0,0,0,0,16,16,16,16,16,32,32,32,32,32对测试函数采用本文提出的遗传算法计算100次,考察求得全局最优解的概率、收敛的平均代数、所得解与全局最优解的平均误差 同时,将结果与文献10中提供的仿真结果进行比较,结果见表1表1 3种方法仿真结果比较表Table 1 Com paring of sim ul ati on results bythr

16、ee algorithm s 算法收敛概率/%平均收敛代数平均误差/10-4SA GA 32177 1.47GAA 72105 1.45本文98940.57如仿真结果所示,本文算法在对存在众多局部最优值的复杂函数进行寻优时,能够以较高的概率较好地收敛于全局最优解,并且求解较为精确4 结 语在分析遗传算法收敛性能的基础上,定义几类与收敛性能密切相关的个体,并在算法中对这类个体进行处理,使算法的种群分布更为合理,进而提高算法全局收敛性能 本文提出的改进遗传算法具有良好的全局收敛性能,并且在精确性及收敛速度方面都有了一定提高 参考文献:1Ozdamar L.A genetic algori thm

17、approach to a general category project scheduling problem J.IEEE Tr ans Syst M an Cyber ,1999,29(1:44-59.2Juidette H,Youlal H.Fuzzy dynamic path planning using genetic algorithms J.Electronics L etters ,2000,36(4:374-376.3S hitomatu.Fuzzy satisficing method for electri c pow er plant coal put chase

18、using genetic algorithms J .Eur opean Jour nal of Operational R esearch ,2000,126(1:218-230.4Li M aojun,Fan Shaosheng,Tong T iaosheng.T he application of partheno -genetic algori thm in pattern clus tering problem J .Engine er ing Ap plications of Artif icial Intelligence ,1999,12(2:175-184.5Correa

19、R C,Ferrei ra A,Rebreyend P.Schedul ing mul tiprocess or tas ks w i th genetic algorithmsJ.IEEE Trans on Parallel and Distributed Systems ,1999,10(8:825-837.6Fumiaki T ,Toshi n i ro N,Sigeruo.Banknote recogniti on by m eans of optimized masks,neural netw ork,and gen etic algorithms J .Engineering Ap

20、p lications of Ar tif icial Intelligence ,1999,12(2:175-184.7何大阔,李延强,王福利 并行启发式进化遗传算法J 信息与控制,2001,30(7:681-683(He D K,Li Y Q,Wang F L.Paralleled heuristic gen etic algorithmJ.I nf ormation and Con trol ,2001,30(7:681-683.8何大阔,李延强,王福利 基于单纯形算子的混合遗传算法J 信息与控制,2001,30(3:276-278(He D K,Li Y Q,Wang F L.Hybr

21、id genetic algori thm based on the operator of pattern search J .Inf or mation and513第6期 何大阔等:一种提高遗传算法全局收敛性的方法Control,2001,30(3:276-278.9何大阔,王福利 基于可进化性的快速遗传算法J 东北大学学报(自然科学版,2002,23(7:628-631(He D K,Wang F L.Fast genetic algorithm based onevolvabi li tyJ.Jour nal of Nor theastern Univer sity(Natur al

22、 Science,2002,23(7:628-631.10李绍军,王惠,姚平经 求解全局最优化的遗传(GAAlopex算法的研究J 信息与控制,2000,29(4:304-308(Li S J,W ang H,Yao P J.Study of genetic-algorithms forseeking the global optimizationJ.I nf or mation andControl,2000,29(4:304-308.Improving the Global Convergence of the Genetic AlgorithmH E D a-kuo,WA N G Fu-

23、li(School of Infor matio n Science&Eng ineering,Nor theastern U niv ersity,Shenyang110004,China.Cor respondent:HE Da-kuo,E-mail:hedakuoAbstract:Based o n the analysis of the r eason of the early converg ence o f the genetic algor ithm,it w as shown t hat t he early conver gence of the genetic algor

24、ithm is mainly concerned w ith the distribution of t he solutions to the problem,the distr ibution of t he indiv iduals of t he population and the application of the genetic operators.T he key to impro ve the per for mance of the global conver gence of the genetic algorithms was believed to apply th

25、e algo rithms to deal wit h the diversity of population scientifically and recognize the contribution of t he individuals to the global conv er gence.Sever al kinds of the indiv iduals,which have much to do w ith t he per for mance of the global converg ence,have been proposed and combined with the niche evolutio n shar ing function.A genetic alg orithm is sug ge