一种新的混合演化多目标优化算法

杜冠军 佟国香

摘  要： 在KKT（Karush-Kuhn-Tucker）条件下，m维的连续多目标优化问题的Pareto解集在决策空间是一个（m-1）维的流形（manifold）。随着算法的迭代，当前种群将分布在流形的周围。为充分利用这一规则特性（regularity property）以解决具有复杂PS（Pareto set）的多目标优化问题，本文提出一种基于差分算子和分布估计算子的混合子代生成算法。首先，引入一个参数来指示当前种群的收敛程度，即当前种群解个体所构成的数据的协方差矩阵的前（m-1）个特征值的和与所有特征值的和的比，比值越大，收敛程度越高;进而，根据不同比值，自适应调节差分算子和分布估计算子生成新解的数量。将该算法在tec09系列测试函数上进行仿真实验，并与RM-MEDA、NSGA-II-DE两个算法进行对比，实验结果表明，RM-MEDA/DE算法优于与之比较的其他算法。

关键词： 流形;差分算子;分布估计算子;多目标优化

中图分类号： TP301    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.02.002

【Abstract】： From the Karush-Kuhn-Tucher condition， it can be induced that， in the decision space， the Pareto set of a m-D continuous multi-objective optimization problem is a piecewise continuous （m-1）-D manifold. To take full advantage of this regularity property to solve multi-objective optimization problem with a complex Pareto Set （PS）， this paper proposes a new algorithm， named RM-MEDA/DE， which hybridizes differential evolution （DE） and estimation of distribution （EDA）. Firstly， a new parameter is employed， which is the ratio of the sum of the first （m-1） largest eigenvalue of the populations covariance matrix to the sum of the whole eigenvalue， to illustrate the degree of convergence of the population. The bigger the ratio is the higher the convergence will be. The number of new solution generated by two methods is adjusted by the parameter. The proposed algorithm is validated on nine tec09 problems. Systematic experiments have shown that RM-MEDA/DE outperforms two other state-of-the-art algorithms， namely， RM-MEDA and NSGA-II-DE.

【Key words】： Manifold; Differential evolution; Estimation of distribution algorithm; Multi-objective optimization

0  引言

在生活实践以及科学研究中常常要同时优化多个相互冲突的问题，此类问题被称之为多目标优化问题MOPs（Multi-objective Optimization Problems）[1]。进化算法（evolutionary algorithm，简称EAs）[2]作为一类基于群体智能的启发式搜索算法具有不受目标函数数学性质的影响、以及一次运行可以得到多个解等特点使其成为求解多目标优化问题的研究热点。

在进化多目标优化算法领域中，多算子混合策略一直受到广泛的关注。在每一代用不同的算子生成不同的个体将不同种类信息融合在种群中。如JADE[3]、CoDE[4]、SaDE[5]。

文献[6-7]将差分算法（differential evolution，简称DE）[8]和分布估计算法（estimation of distribution algorithm，简称EDA）[9]两种算子混合使用将个体分布信息与种群分布信息融合以增强种群的收敛性和多样性。文献[10]利用局部主成分分析[11]方法对种群进行聚类，并对每个聚类构造高斯概率模型以采样新解，其在收敛性和多样性方面都取得了良好的表现。受此启发，本文提出一种新的混合算法，即将DE和RM-MEDA兩种不同生成算子应用在进化多目标优化问题中，记作RM-MEDA/DE。在每一代中使用DE和高斯概率模型两种算子来生成新解;通过计算当前种群的协方差矩阵的前（m-1）个特征值的和与所有特征值的和的比值来指示种群收敛程度，并根据此比值自适应的调节不同算子生成解的数量。在算法的开始阶段，收敛程度不高，特征值的比值较小，此时大部分的新解由DE算子生成;在算法的后期，特征值的比值较大，此时由RM- MEDA来生成更多过的新解。在维持多样性的同时加快了收敛速度。

4  結束语

为了充分利用连续多目标优化问题的规则特性，本文提出了基于差分和分布估计算子的混合算法。用当前种群所构成空间的特征值比例来指示种群收敛程度。并根据种群收敛程度来自适应调节差分和分布估计算子生成新解的数量。实验结果表明本文所提出的混合算法能更快更有效地逼近真实的Pareto前沿。

需要指出的是混合算法在Pareto支配排序算法框架下的逼近能力仍然是有限的，对于过于复杂的问题，该模型只能部分逼近其PS。在接下来的工作中我们将连续多目标优化算法的规则特性和混合算子应用在基于分解的算法框架下。

参考文献

[1] Coello C A C. A comprehensive survey of evolutionary- based multiobjective optimization techniques[J]. Knowledge and Information systems， 1999， 1（3）： 269-308.

[2] Schaffer J D. Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of the First International Conference on Genetic Algorithms and Their Applications， 1985. Lawrence Erlbaum Associates. Inc.， Publishers， 1985.93-100.

[3] Zhang J， Sanderson A C. JADE： adaptive differential evolution with optional external archive[J]. IEEE Transactions on evolutionary computation， 2009， 13（5）： 945-958.

[4] Wang Y， Cai Z， Zhang Q. Differential evolution with composite trial vector generation strategies and control parameters[J]. IEEE Transactions on Evolutionary Computation， 2011， 15（1）： 55-66.

Qin A K， Suganthan P N. Self-adaptive differential evolution algorithm for numerical optimization[C]//Evolutionary Computation， 2005. The 2005 IEEE Congress on. IEEE， 2005， 2： 1785-1791.

Fang H， Zhou A， Zhang H. Information fusion in offspring generation： A case study in DE and EDA[J]. Swarm and Evolutionary Computation， 2018.

Sun J， Zhang Q， Tsang E P K. DE/EDA： A new evolutionary algorithm for global optimization[J]. Information Sciences， 2005， 169（3-4）： 249-262.

Storn R， Price K. Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of global optimization， 1997， 11（4）： 341- 359.

Mühlenbein H， Paass G. From recombination of genes to the estimation of distributions I. Binary parameters[C]// International conference on parallel problem solving from nature. Springer， Berlin， Heidelberg， 1996： 178-187.

Zhang Q， Zhou A， Jin Y. RM-MEDA： A regularity model- based multiobjective estimation of distribution algorithm[J]. IEEE Transactions on Evolutionary Computation， 2008， 12（1）： 41-63.

Kambhatla N， Leen T K. Dimension reduction by local principal component analysis[J]. Neural computation， 1997， 9（7）： 1493-1516.

Hillermeier C. Nonlinear multiobjective optimization： a generalized homotopy approach[M]. Springer Science & Business Media， 2001.

Li H， Zhang Q. Multiobjective optimization problems with complicated Pareto sets， MOEA/D and NSGA-II[J]. IEEE Transactions on evolutionary computation， 2009， 13（2）： 284- 302.