一種新的混合演化多目標(biāo)優(yōu)化算法

杜冠軍 佟國(guó)香

摘? 要： 在KKT（Karush-Kuhn-Tucker）條件下，m維的連續(xù)多目標(biāo)優(yōu)化問(wèn)題的Pareto解集在決策空間是一個(gè)（m-1）維的流形（manifold）。隨著算法的迭代，當(dāng)前種群將分布在流形的周圍。為充分利用這一規(guī)則特性（regularity property）以解決具有復(fù)雜PS（Pareto set）的多目標(biāo)優(yōu)化問(wèn)題，本文提出一種基于差分算子和分布估計(jì)算子的混合子代生成算法。首先，引入一個(gè)參數(shù)來(lái)指示當(dāng)前種群的收斂程度，即當(dāng)前種群解個(gè)體所構(gòu)成的數(shù)據(jù)的協(xié)方差矩陣的前（m-1）個(gè)特征值的和與所有特征值的和的比，比值越大，收斂程度越高;進(jìn)而，根據(jù)不同比值，自適應(yīng)調(diào)節(jié)差分算子和分布估計(jì)算子生成新解的數(shù)量。將該算法在tec09系列測(cè)試函數(shù)上進(jìn)行仿真實(shí)驗(yàn)，并與RM-MEDA、NSGA-II-DE兩個(gè)算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，RM-MEDA/DE算法優(yōu)于與之比較的其他算法。

關(guān)鍵詞： 流形;差分算子;分布估計(jì)算子;多目標(biāo)優(yōu)化

中圖分類號(hào)： TP301? ? 文獻(xiàn)標(biāo)識(shí)碼： 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? 引言

在生活實(shí)踐以及科學(xué)研究中常常要同時(shí)優(yōu)化多個(gè)相互沖突的問(wèn)題，此類問(wèn)題被稱之為多目標(biāo)優(yōu)化問(wèn)題MOPs（Multi-objective Optimization Problems）[1]。進(jìn)化算法（evolutionary algorithm，簡(jiǎn)稱EAs）[2]作為一類基于群體智能的啟發(fā)式搜索算法具有不受目標(biāo)函數(shù)數(shù)學(xué)性質(zhì)的影響、以及一次運(yùn)行可以得到多個(gè)解等特點(diǎn)使其成為求解多目標(biāo)優(yōu)化問(wèn)題的研究熱點(diǎn)。

在進(jìn)化多目標(biāo)優(yōu)化算法領(lǐng)域中，多算子混合策略一直受到廣泛的關(guān)注。在每一代用不同的算子生成不同的個(gè)體將不同種類信息融合在種群中。如JADE[3]、CoDE[4]、SaDE[5]。

文獻(xiàn)[6-7]將差分算法（differential evolution，簡(jiǎn)稱DE）[8]和分布估計(jì)算法（estimation of distribution algorithm，簡(jiǎn)稱EDA）[9]兩種算子混合使用將個(gè)體分布信息與種群分布信息融合以增強(qiáng)種群的收斂性和多樣性。文獻(xiàn)[10]利用局部主成分分析[11]方法對(duì)種群進(jìn)行聚類，并對(duì)每個(gè)聚類構(gòu)造高斯概率模型以采樣新解，其在收斂性和多樣性方面都取得了良好的表現(xiàn)。受此啟發(fā)，本文提出一種新的混合算法，即將DE和RM-MEDA兩種不同生成算子應(yīng)用在進(jìn)化多目標(biāo)優(yōu)化問(wèn)題中，記作RM-MEDA/DE。在每一代中使用DE和高斯概率模型兩種算子來(lái)生成新解;通過(guò)計(jì)算當(dāng)前種群的協(xié)方差矩陣的前（m-1）個(gè)特征值的和與所有特征值的和的比值來(lái)指示種群收斂程度，并根據(jù)此比值自適應(yīng)的調(diào)節(jié)不同算子生成解的數(shù)量。在算法的開(kāi)始階段，收斂程度不高，特征值的比值較小，此時(shí)大部分的新解由DE算子生成;在算法的后期，特征值的比值較大，此時(shí)由RM- MEDA來(lái)生成更多過(guò)的新解。在維持多樣性的同時(shí)加快了收斂速度。

4? 結(jié)束語(yǔ)

為了充分利用連續(xù)多目標(biāo)優(yōu)化問(wèn)題的規(guī)則特性，本文提出了基于差分和分布估計(jì)算子的混合算法。用當(dāng)前種群所構(gòu)成空間的特征值比例來(lái)指示種群收斂程度。并根據(jù)種群收斂程度來(lái)自適應(yīng)調(diào)節(jié)差分和分布估計(jì)算子生成新解的數(shù)量。實(shí)驗(yàn)結(jié)果表明本文所提出的混合算法能更快更有效地逼近真實(shí)的Pareto前沿。

需要指出的是混合算法在Pareto支配排序算法框架下的逼近能力仍然是有限的，對(duì)于過(guò)于復(fù)雜的問(wèn)題，該模型只能部分逼近其PS。在接下來(lái)的工作中我們將連續(xù)多目標(biāo)優(yōu)化算法的規(guī)則特性和混合算子應(yīng)用在基于分解的算法框架下。

參考文獻(xiàn)

[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.