基于免疫的并行单亲遗传算法研究

《基于免疫的并行单亲遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8期行小帅等：基于免疫的并行单亲遗传算法研究·105·基于免疫的并行单亲遗传算法研究行小帅，霍冰鹏（山西师范大学物理与信息工程学院，山西临汾041004）摘　要：在分析了单亲遗传算法的优越性与存在不足的基础上，借鉴生物免疫概念与理论并结合并行计算的思想，提出了一种新的遗传算法——基于免疫的并行单亲遗传算法。理论分析和仿真结果表明,该算法不仅能够有效地保持群体多样性，而且减轻了遗传算法后期的波动现象，同时收敛速度有明显的提高。关键词：并行；单亲遗传算法；免疫算法；非均匀变异算子；免疫算子中图分类号：TP18，PT13文

2、献标识码：B文章编号：1000-436X(2007)08-0099-06ResearchonparallelparthenogeneticalgorithmbasedontheimmuneprogrammingXINGXiao-shuai,HUOBing-peng(CollegeofPhysicsandInformationEngineering,ShanxiTeacher’sUniversity,Linfen041004,China)Abstract:Anovelalgorithmparallelparthenoge

3、neticalgorithmbasedontheimmuneprogramming(IPPPGA)wasproposed,thealgorithmanalogiestotheconceptandtheoryofimmunityinbioticscienceandunifiestheparallelcomputationthought,afteranalyzingtheadvantagesanddisadvantagesoftheparthenogeneticalgorithm.Thetheoryanalysisande

4、xperimentalresultsshowthatthealgorithmnotonlyeffectivelykeepspopulationdiversity,butalsoalleviatestheundulatephenomenoninevolutionarylatterstages,meanwhileincreasestheconvergentspeedandcomputationalefficiencygreatly.Keywords:parallel;parthenogeneticalgorithm;imm

5、uneprogramming;nonuniformmutationoperator;immuneoperator第8期行小帅等：基于免疫的并行单亲遗传算法研究·105·1引言收稿日期：2006-12-12；修回日期：2007-05-20基金项目：山西省青年科技研究基金资助项目（20031008）FoundationItem:TheShanxiYoungScienceandTechnologyResearchFundSchemeofChina(20031008)单亲遗传算法[1,2](PGA,parthenogeneti

6、calgorithm)是一种对样本空间的样本分别进行基因换位、基因移位、基因倒位、变位等单亲遗传操作，实现解空间全局搜索的算法。与传统的遗传算法相比，PGA可以更好地保持样本地稳定性，特别适合于求解组合优化以及多峰函数的优化问题[3,4]。从理论上分析，在PGA的循环迭代过程中保留了上一代最佳个体的前提下，PGA是全局收敛的[5]。通常PGA操作算子如换位、移位等为了保证遗传算子的全局搜索能力，都是基于一定的概率操作。但是在定向搜索时，这样操作往往效率较低[6]。文献[7]提出的单亲遗传算法是基于实数编码，它使用选择算

7、子和变异算子，从而保证了个体间隔离，彼此互不交换信息，能够有效地保持群体的多样性，在一定程度上减少了早熟现象，收敛速度也较快，但是在进化过程中利用系统信息不够，进化后期易出现波动现象，因此不能保证其以最大概率收敛到全局最优解。免疫进化算法（IEA,immuneevolutionaryalgorithm）[8]第8期行小帅等：基于免疫的并行单亲遗传算法研究·105·是一种有效的全局寻优算法，它借鉴生命科学中的免疫概念和理论，在保留原算法优良特性的前提下，力图有目地、有选择地利用待求问题中一些特征或知识来抑制其优化过程中出

8、现的退化现象。免疫进化算法的核心是在合理抽取疫苗的基础上，通过接种疫苗和免疫选择2个步骤完成的。前者是为了提高个体的适应度，后者是为了防止群体的退化。因此免疫算法能够提高个体的适应度和防止群体的退化现象，从而提高了收敛速度并且减轻了原有进化算法后期的波动现象。本文将免疫算法和单亲遗传算法的优点相结合，并集成了并行计算[9,10]中