论文部分内容阅读
多目标优化问题是一门新兴学科,起源于许多实际复杂系统的设计、建模和规划问题。由于遗传算法自身的进化本质,使其非常适合处理多目标优化问题,对Pareto最优前端的形状和连续性也不敏感,比传统方法可求解的复杂问题的数量大得多。遗传算法的基本特点是多方向和全局搜索,操作对象是一组个体,这种从种群到种群的方法,使得遗传多目标优化算法运行一次就能找到多目标优化问题的几个Pareto最优解,而传统优化方法可能需要进行很多次的运算才能达到这样的效果,因此遗传多目标优化算法在寻找有良好的收敛性和分布性的Pareto最优解时十分有效,也是一种行之有效的求解多目标优化问题的方法。
1984年Schaffer提出的VEGA,该算法只是在简单遗传算法的基础上加上一个循环机制,针对每个目标函数来进行遗传操作,并产生最终结果。随后在Goldberg提出的Pareto排序思想上产生了MOGA(Fonseca和Fleming,1993),NPGA(Nafpliotis和Horn,1994)和NSGA(Srinivas和Deb,2000)等算法。MOGA算法依据个体的次序值来进行排序,并分配不同的适应值,相同的次序则有相同的适应值,较好地保存了较优个体。NPGA算法采用了二进制竞争选择机制,使得随机抽出的个体可以跟比较集进行比较来进行优胜劣汰。NSGA算法则是先将种群进行分类,依次分配的适应值。随后引入了精英保留机制(Elitism),产生了SPEA(Zitzler和Thiele,1999),SPEA2(Zitzleretal.2001),PESA(Corneetal.2000)和NSGA2(Debetal.2002)等算法。NSGA2算法就是在NSGA算法的基础上引入了一个外部种群,在实际操作中需确定其次序值,还需计算个体的拥挤距离。SPEA算法其个体的适应值由个体与外部种群间的支配关系决定,再采用二进制竞争选择机制来选择个体,具有较小适应值的个体更优。SPEA2算法改进了SPEA算法的适应值分配机制,引入了一个最小邻居密度估计机制来对搜索过程作更准确的引导,同时引入新的档案截断方法来保证了边缘解的保存。PESA算法最大的特点是采用hyper-box来保持种群的多样性,采用挤压因子来完成选择和EP种群更新机制,有利于保留Pareto最优前端中位于稀疏区域的个体,维持了较好的种群多样性。
本文主要从试验的角度出发,针对文中提到的8个不同的算法进行全面的综合比较。选取几个特定的应用比较广泛的测试函数,比较各个算法的收敛速率,种群的多样性等性能,再从中吸取各算法的长处,最终提出一个在性能方面有所改进的遗传多目标优化算法。