资源描述：
《并行遗传算法的新进展》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2002年2月系统工程理论与实践第2期文章编号:1000-6788(2002)02-0015-09并行遗传算法的新进展郭彤城,慕春棣(清华大学自动化系,北京100084)摘要:并行遗传算法将并行计算机的高速并行性和遗传算法固有的并行性相结合,极大地提升了遗传算法的求解速度和质量.在主从式、细粒度和粗粒度这三类遗传算法并行化模型中,粗粒度模型以其较小的通讯开销和对种群多样化,获得了最广泛的应用.本文概括了基于模式定理和有限状态马尔可夫链的遗传算法理论,总结了前人在粗粒度模型下开展的理论分析和实践应用,并指出并行遗传算法的研究将向异步化,理论化和模型化的方向发展,而有限状态马尔可
2、夫链是构建并行遗传算法可执行模型的有力工具.关键词:遗传算法;并行计算;粗粒度;有限状态马尔可夫模型中图分类号:TP18文献标识码:AaTheParallelDriftsofGeneticAlgorithmsGUOTong-cheng,MUChun-di(DepartmentofAutomation,TsinghuaUniversity,Beijing100084,China)Abstract:TheparallelGAs(PGAs)combinethehigh-speedparallel-abilityofsu-percomputerswiththeinherentpara
3、llelityofGAs,andimprovegreatlytheefficiencyandaccuracyofGAs.Amongthemaster-slave,fine-grainedandcoarsegrainedparallelavenues,thecoarse-grainedmodelismostwidelyusedforitslittlecommunicationoverheadanditsdiversifyingofthepopulation.Inthispaper,theschematheoryandthemodelbasedonthelimitMarkovch
4、ainaregeneralized,thepreviousanalysisandimplementationonthecoarsegrainedmodelarereviewed.ItisshownthatresearchesofPGAswillfocusonasynchronization,theorizationandmodelization.Furthermore,thetheoryoflimitMarkovchainprovidespowerfultoolstoconstructexecutablemod-elsofPGAs.Keywords:geneticalgori
5、thms;parallelcomputation;coarsegrain;limitMarkovchain1引言组合优化和函数优化需要在复杂庞大的搜索空间中寻找最优解或次最优解(满意解),是存在于各学科中的普遍难题.遗传算法(GeneticAlgorithms,GAs)从一组初始可行解出发,在不需要除目标函数值外[1]的其它信息的条件下实现对可行域的全局高效搜索,并以概率1收敛到全局最优解.这种良好的特性使遗传算法成为组合优化和函数优化的有利工具,并成为计算智能(computationalintelligence)领域的研究热点.随着科学技术的不断发展,问题的规模不断扩大,面
6、对复杂程度越来越高的搜索空间遗传算法在优化效率(时间)和求解质量上都显得“力不从心”.并行遗传算法将并行计算机的高速并行性和遗传算法天然的并行性相结合,极大地促进了遗传算法的研究与应用.并行处理的引入不但加速了遗传算法的搜索过a收稿日期:2000-06-16资助项目:863应用基础研究基金(863-511-943-014)16系统工程理论与实践2002年2月程,而且由于种群规模的扩大和各子种群的隔离,使种群的多样性得以丰富和保持,减少了未成熟收敛的可能性,提高了求解质量.2遗传算法的运行机理对遗传算法运行机理的解释有两类:一是传统的模式理论;二是1990年以后发展起来的有限状
7、态马尔可夫链模型.2.1模式理论模式理论由Holland创建[2],主要包括模式定理,隐并行性原理和积木块假说三部分[3,4].模式是可行域中某些特定位取固定值的所有编码的集合.模式理论认为遗传算法实质上是模式的运算,编码的字母表越短,算法处理一代群体时隐含处理的模式就越多.当算法采用二进制编码时,效率最高,处理规模为N3[5]的一代群体时,可同时处理O(N)个模式.遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性.模式理论还指出,目标函数通常满足积木块假说,即阶数高,长度长,平均适应度
