基于NSGA-II的偏好分解的多目标优化算法研究

谢倩文， 何利力

( 浙江理工大学 信息学院， 杭州 310018)

0 引 言

涉及两个或者多个要优化的冲突目标的问题称为多目标优化问题(Multi-objective Optimization Problem，MOP)。由于各个目标之间相互排斥，无法取得在各个目标上的最优解。如何取得最优解或者逐渐靠近最优解的近似解，成为研究多目标进化算法(MOEA)的重点。目前的研究主要从两个方面着手，一种是通过加权的方式，将多目标优化问题转化成单目标优化问题；另外一种就是基于Pareto支配关系得到非支配解。Deb K提出使用带有精英策略的、非支配的排序算法NSGA-II，能够在真正的Pareto前沿附近找到最优的解I[1]，但NSGA-II算法对于高维多目标优化问题，Pareto非支配解会越来越多，维度越大，拥挤距离在高维空间的计算也会更加复杂。张青富、李辉提出的MOEA/D对于低维简单PF的多目标优化问题效果很好，根据分解方法能生成一组均匀分布的解，可扩展性高、收敛快、计算复杂度低[2]。但当有复杂的Pareto前沿时，MOEA/D的均匀分布就会被破坏。而偏好优化算法通过建立偏好的初始条件，在进化迭代的过程中不断朝着偏好方向去搜索，减小搜索范围，找到离偏好信息最接近的解。为了求解基于偏好关系的多目标问题，Molina在参考点附近估计有效设置，提出了适用于MO进化算法和MO元启发算法的g-Dominance[3]；王丽萍等通过将偏好信息和分解的多目标算法相结合，消除参考点的不同区域对算法收敛性的影响[4]。针对高维的多目标问题，Deb, K提出了基于参考点的非支配排序方法的进化多目标优化算法NSGA-III[5]；……