多个体参与交叉的Pareto多目标遗传算法

 

第1期2001年1月

电  子  学  报

ACTAELECTRONICASINICAVol.29 No.1

 

Jan. 2001

多个体参与交叉的Pareto多目标遗传算法

朱学军1,陈 彤2,薛 量1,李 峻1

(11上海交通大学机械工程学院,上海200030;21上海交通大学电子工程系,上海200030)

  摘 要: Pareto多目标遗传算法是利用Pareto最优的概念发展出的一种求解多目标优化问题的向量优化方法,

能够得到Pareto最优解集.由于采用常规的两个体参与交叉的遗传算法,使整个算法耗费在小生境()算子上的时间太多,导致算法的效率较低.本文发展出多个体参与交叉的Pareto多目标遗传算法,,使该算法的速度大大提高,同时证明了相应的模式定理,.最后用算例说明了采用多个体参与交叉的Pareto,.

关键词: 遗传算法;多点交叉;模式定理;中图分类号: O224,TP183:A037222112(2001)0120106204

ParetowithMultiple2ChromosomesCrossover

ZHUXue2jun1,CHENTong2,XUELiang1,LIJun1

(11SchoolofMechanicalEngineering,ShanghaiJiaotongUniversity,Shanghai200030,China;

21Dept.ofElectronicEngineering,ShanghaiJiaotongUniversity,Shanghai200030,China)

Abstract: ParetomultiobjectivegeneticalgorithmisonekindofvectoroptimizationmethodsderivedfromconceptofParetoop2timal,andthewholeParetooptimalsetcanbegotusingthismethod.BecauseconventionalParetoGArunswithtwochromosomescrossover,itconsumesmuchtimeonNichewhichmakestheefficencyofthisalgorithmsomewhatlow.Inthispaper,anewParetomul2tiobjectiveGAwithmultiple2chromosomescrossoverispresented,andtheindividualisexpressedwithreal2valuedrepresentationswhichmakesitmuchfasterthanconventionalalgorithms.Basedontheproofofcorrespondingschematheorem,varianceandentropyarepro2posedasmeasurementsofdiversityofpopulationingeneticalgorithms.TheinfluencethattheParetoMOGAwithmultiple2chromosomescrossoveractsuponvarianceandentropyisanalyzed.Atlast,oneexampleispresentedtocomparebetweenmethodinthispaperandtraditionalmethodssoastoprovethesuperiorityofthismethod.

Keywords: geneticalgorithm;multiple2chromosomescrossover;schematheorem;multiobjectiveoptimization

1 两个体交叉的Pareto多目标遗传算法的缺陷

  多目标优化设方法经历了一个从确定性搜索算法到随机

搜索算法,从本质上仍是单目标优化的目标组合方法到真正意义上的向量优化方法的过程.文献[2]发展出一种Pareto多目标遗传算法,利用遗传算法的随机搜索特性和隐含并行性[3],在简单遗传算法的基础上发展出了两个新的算子:Pareto解集过滤器和小生境算子;又在模糊集合理论的基础上提出了处理多目标优化设计问题中约束条件的模糊罚函数法;利用Pareto最优的概念[1]设计了处理多目标优化问题中群体的分级排序算法,并在此基础上建立了处理连续变量的Pareto多目标遗传算法,能够搜索到整个设计空间并求解出Pareto最优解集.后又提出了处理混合离散变量的离散变量圆整算子,使Paerto遗传算法能处理多种类型的变量[4].

众所周知,遗传算法的计算效率是其最大的缺陷,原因在于遗传算法采用随机搜索方式,

多个体参与交叉的Pareto多目标遗传算法

对每一代群体中个体数为m

个的较简单问题,其效率几乎是传统优化方法的1/m.在多目标遗传算法中,采用基于排挤的小生境技术来使群体保持每一代都比前一代更靠近Pareto最优解集的持续进化状态及群体中的个体保持均匀分布.由于Pareto多目标遗传算法采用了对群体中的每个个体都要进行交叉和变异的操作,使得在每一代中,交叉和变异的使用次数为m/2次.群体的规模越大,交叉和变异算子的计算量就越大,是Pareto多目标遗传算法中最耗时的部分之一.该算法虽然很有效,但从中可以发现遗传算法中两个体交叉的思想是受了模拟自然界生物有性繁殖进化的限制,事实上如果突破这一假定,采用多个体参与交叉的方式,可能会使Pareto多目标遗传算法的效率大大提高.

本文提出多个体参与交叉的Pareto多目标遗传算法,群体中的个体采用真实值表示,并通过证明相应的模式定理,分析其对解群多样性的影响,初步解释了其具有较高计算效率的原因,最后用算例证明了所提出算法的高效性.

收稿日期:1999208223;修回日期:2000208214

你可能喜欢

  • 遗传算法分析
  • 混合遗传算法
  • 量子遗传算法
  • 小生境遗传算法
  • 神经网络遗传算法
  • 锅炉遗传算法
  • 双种群遗传算法
  • 遗传算法论文

多个体参与交叉的Pareto多目标遗传算法相关文档

最新文档

返回顶部