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