基于遗传算法的多目标优化算法研究

被引:0
作者
王鲁
机构
[1] 武汉理工大学
关键词
遗传算法; 密度估计; Pareto优解; 多目标优化; 精英策略;
D O I
暂无
年度学位
2006
学位类型
硕士
导师
摘要
解决现实世界中的许多问题会遇到两种类型的难度:Ⅰ)多个相互冲突的目标,Ⅱ)高维复杂的搜索空间。就第一点而言,与单目标优化不同的是,多个相互竞争目标的优化结果是得到一组可行解,一般被称作Pareto最优解集。由于缺少喜好信息,在折中解中找不到一个解比另一个解更好。就第二点而言,若使用精确的方法解决多目标优化问题,搜索空间太大而且很复杂。因此,需要设计高效的优化策略来解决这两个问题。非劣分类算法Ⅱ(NSGA Ⅱ)是近几年发展起来的一种多目标遗传算法。它采用了非劣分类算法以及精英策略。它具有很多优点:(1)将时间复杂度降低到(GMN2),其中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Ⅱ算法。
引用
收藏
页数:63
共 10 条
[1]
多目标优化的演化算法 [J].
谢涛 ;
陈火旺 ;
康立山 .
计算机学报, 2003, (08) :997-1003
[2]
基于粒子群算法的多目标函数优化问题研究 [D]. 
刘麟 .
武汉理工大学,
2005
[3]
多目标演化算法及在优化问题中的应用 [D]. 
李锋 .
武汉理工大学,
2004
[4]
遗传算法在多目标优化中的应用 [D]. 
涂雪珠 .
福州大学,
2004
[5]
基于遗传算法的多目标优化与决策方法研究 [D]. 
郑丽君 .
国防科学技术大学,
2003
[6]
基于进化计算的多目标优化与决策方法研究 [D]. 
汪晗 .
中国人民解放军国防科学技术大学,
2002
[7]
GENETIC SEARCH STRATEGIES IN MULTICRITERION OPTIMAL-DESIGN [J].
HAJELA, P ;
LIN, CY .
STRUCTURAL OPTIMIZATION, 1992, 4 (02) :99-107
[8]
遗传算法.[M].王小平;曹立明著;.西安交通大学出版社.2002,
[9]
遗传算法原理及应用.[M].周明;孙树栋编著;.国防工业出版社.1999,
[10]
遗传算法及其应用.[M].陈国良等编著;.人民邮电出版社.1996,