一種新的混合演化多目標優化算法

杜冠軍 佟國香

摘? 要： 在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.