论文部分内容阅读
现实世界中有很多问题是多目标优化问题。在一个多目标优化问题中,至少存在一对相互冲突的目标。因此,多目标优化的结果不是单独的一个解,而是由许多无法比较出优劣的解所构成的解集。演化算法作为一类群体搜索方法,它可以同时获得多个近似最优解,因此很适合于求解多目标优化问题。然而,不少多目标优化问题所包含的目标数超过三个,它们被称为高维目标优化问题,具有较大的求解难度。在高维目标优化问题中,按照Pareto支配的概念,非支配解的比例随着目标数增加而急剧上升。传统的一些多目标演化算法无法有效地区分大量的非支配解,从而不易快速、精确地逼近最优解集。因此,对高维目标优化问题的演化算法进行研究很有必要。在高维目标优化问题中,目标之间的相互关系更加复杂,可能会有更多的目标之间存在冲突,也可能在有些目标之间不存在冲突,甚至有相互促进的关系。另外,作为多目标演化算法的两个关键要素,选择策略和变化算子在很大程度上影响算法的性能。因此,本文首先从分析目标之间的相关性入手,通过合并不冲突的目标减少目标数量从而区分出原目标集下的部分非支配解。然后,分别从多目标演化算法的选择策略和变化算子这两个角度出发,对高维目标优化问题的演化优化方法展开研究。本文的主要研究工作如下:1)综述了演化多目标优化的研究现状,阐述了多目标优化领域的一些基本概念,介绍了当前演化多目标优化领域的研究热点,指出现有高维目标演化优化方法存在的不足。2)阐述了多目标演化优化算法的三个关键成分在算法中所起的作用,提出了一种度量非支配解集分布性能的指标。新的指标受解集在目标空间上的平行坐标表示所启发,同时度量解集的分布均匀程度和分布广度。3)针对高维目标优化问题,提出了一种目标降维方法。当前高维目标优化问题的解决方法已有不少,其中目标降维方法已经成为一种有效的解决方法。但一些目标降维方法的复杂度比较高,而且不易于实现,因此将目标降维方法用于在线降维的研究成果并不多。针对这一问题,本文使用相关系数分析目标之间的关系,通过合并不冲突的目标达到降低目标数量、减少非支配解规模的目的。该方法在时间复杂度上相对一些其它的方法有所改善,因此适合于在线降维。文中不仅从理论上论证了该目标降维方法的可行性,而且通过实验验证了它的有效性。4)以上述目标降维方法为基础,提出一种高维目标演化优化框架。为了验证该框架的有效性,将快速非支配排序算法(NSGA-Ⅱ)、基于指标的演化算法(IBEA)分别融入该算法框架,在经典的高维目标测试问题上进行了实验研究。实验结果表明,目标降维方法能显著改善传统多目标演化算法的收敛性能。因此,提出的算法框架是解决高维目标优化问题的一种有效途径。5)提出多选择策略,将其融入上述高维目标演化优化框架用于处理高维目标优化问题。选择策略是多目标演化算法的关键要素之一。不同选择策略具有各自的优势和缺陷,而且单一选择策略调节选择压力的能力有限。因此,本文提出一种多选择策略。在多选择策略中,按概率使用Pareto非支配排名结合拥挤距离的选择方法和基于指标的选择方法,并且从降低支配抵触解的角度对这两种选择方法分别进行了改进以更好地适用于高维目标优化。实验结果表明,该方法可以利用Pareto非支配排名结合拥挤距离的选择方法与基于指标的选择方法所具有的优点,在解集的收敛性能和分布性能之间获得较好的平衡。6)设计了一个自适应K阶差分演化算法,将其融入上述高维目标演化优化框架用于求解高维目标优化问题。变化算子是多目标演化算法的关键要素之一。差分演化的杂交和变异集成在一起,是一种搜索能力很强的变化算子,适合于多目标演化优化。而差分演化中差分向量的产生方式以及杂交概率和缩放因子的取值,在很大程度上影响算法的收敛效果。因此,本文分别从上述两个方面出发对多目标差分演化算法展开研究。首先,从K阶差分方程的计算式得到启发,引入了K阶差分的概念对差分演化算法进行了拓展,提出多目标K阶差分演化算法。其次,将参数自适应策略融入多目标K阶差分演化算法,提出自适应多目标K阶差分演化算法。最后,将该算法融入提出的高维目标演化优化框架中,用于解决高维目标优化问题。针对多目标K阶差分演化算法的实验表明,使用2阶差分变异模式比使用1阶差分变异模式的演化算法收敛性能更好。针对自适应多目标K阶差分演化算法的实验表明,参数自适应策略能避免反复的参数尝试,而且能获得与最佳参数策略相近或更好的优化结果。在高维目标优化问题上的实验结果表明,自适应高维目标K阶差分演化算法与其它的一些高维目标演化算法相比,该算法具有较高的收敛性能和分布性能。