论文部分内容阅读
解决现实世界中的许多问题会遇到两种类型的难度:Ⅰ)多个相互冲突的目标,Ⅱ)高维复杂的搜索空间。就第一点而言,与单目标优化不同的是,多个相互竞争目标的优化结果是得到一组可行解,一般被称作Pareto最优解集。由于缺少喜好信息,在折中解中找不到一个解比另一个解更好。就第二点而言,若使用精确的方法解决多目标优化问题,搜索空间太大而且很复杂。因此,需要设计高效的优化策略来解决这两个问题。非劣分类算法Ⅱ(NSGA Ⅱ)是近几年发展起来的一种多目标遗传算法。它采用了非劣分类算法以及精英策略。它具有很多优点:(1)将时间复杂度降低到(GMN~2),其中G是代数,M是目标个数,N是种群规模;(2)采用精英策略,使得先前各代中搜索到的精英解得以保留;(3)不需要确定共享参数,因此算法对于用户来说是透明的。 本文对遗传算法进行了介绍,讨论了多目标演化算法的相关重要策略,并介绍了SPEA2算法和NSGAⅡ算法。在对NSGAⅡ实验发现,大概在20代以后,种群中的所有解都是精英,随后各代的操作都将在精英解中进行,非精英解无法参与其中,当前种群也就不能再接纳一些新的解参与下一代的操作,降低了解的多样性。搜索过程将中止并过早的收敛到局部的Pareto解。为了确保搜索向全局Pareto优解收敛,一种确保解的多样性的改进精英策略的多目标遗传算法(IENSGAⅡ)被提出,在改进的多目标优化算法中,精英策略保存从上一代至今最优的非劣解,使得精英解的作用代数得以延续。同时提出一种分布函数,通过调节参数,以及改进精英策略的应用代数gener在遗传操作中控制精英解的选取范围,使得一部分非精英解按照等级的不同公平参与到遗传操作中,增加了解的多样性。 将IENSGAⅡ算法和NSGAⅡ算法在六个多目标测试问题(ZDT1,ZDT2,ZDT3,ZDT4,ZDT6,KUR)上作了比较,并引入Deb所提出的两个性能度量值r和△进行测试。通过性能度量值及最终优化后的Pareto优解的组成图示均可看出在所有的六个测试问题上改进的多目标演化算法无论在解的多样性还是解的收敛性方面都有较大改观,在多样性及收敛性之间达到了一个较好的平衡,避免了解过早收敛到局部Pareto解集。性能明显优于NSGAⅡ算法。