自適應信息反饋模型改進的MOEA/D算法

王啟翔 許峰

摘 要：為了提高MOEA/D算法求解大規模高維多目標優化問題的能力，本文提出一種基于自適應信息反饋機制改進的MOEA/D算法，其基本思想是根據信息反饋原理，將當前代第k個個體與用MOEA/D算法求得的第i個個體加權平均后作為下一代第i個個體。k的選取有指定和隨機兩種方式，可以根據目標函數的梯度自適應地選擇。采用標準的測試函數來評測改進后的算法的性能。結果表明，改進后的MOEA/D算法在收斂性方面有明顯的提高。

關鍵詞：大規模高維多目標優化;MOEA/D;信息反饋;自適應;目標函數梯度

中圖分類號：TP391 ?文獻標識碼：A ?文章編號：1673-260X（2021）04-0025-04

當多目標優化問題中的目標函數的個數有二至三個時，此類優化問題被稱為多目標優化問題（Multi-objective Optimization Problems，MOP）;當優化問題中的目標函數的個數達到4個以上時，此類優化問題則被稱為高維多目標優化問題[1]（Many-objective Optimization Problems，MaOP）。多目標進化算法（Multi-objective Evolutionary Algorithm，MOEA）是求解MOP非常經典的優化算法，但是在用于求解MaOP時，算法的性能就會有一定程度地下降，不足之處主要表現在隨著目標函數個數的增加，進而導致算法的收斂性不足，Pareto最優前沿不能完美地逼近真實的Pareto前沿，并且解的分布性和均勻性也欠佳。

基于分解的MOEAs根據分解的形式可分為基于聚合函數的MOEAs和基于參考向量分解的MOEAs[2]。基于分解的多目標進化算法中具代表性的算法是MOEA/D。Zhang提出了基于多目標分解的MOEA/D[3];為了改善計算資源的分配，Zhang提出了改進的MOEA/D，稱為MOEA/D-DRA[4];在MOEA/D-DRA的基礎上，Zhou和Zhang提出了MOEA/D-GRA[5];Ryoji[6]分析了MOEA/D的控制參數;Dong[7]提出了自適應權重MOEA/D。Zhang和Wang[8]提出了一種基于信息反饋的改進MOEA/D。

Zhang和Wang將信息反饋模型中參數k的兩種選擇方式對應為兩種不同的算法，分別研究了這兩種算法對MOEA/D的改進[8]。考慮到參數k的兩種選擇方式的優缺點，本文提出了一種針對參數k選擇方式的不同來進行自適應地確定參數k選擇方式的算法，具體做法就是利用目標函數的梯度，來構建自適應性選擇，從而確定參數k的選擇方式。對改進后算法的性能，一般用標準化測試函數對其進行評測，并將改進后算法得出的結果和MOEA/D算法產生的結果相比較。

1 MOEA/D算法

在MOEA/D算法中，權重向量的生成方式是多種多樣的，可以根據自己的需求預先設置權重向量，再利用權重向量將復雜的多目標優化問題轉換成一個一個的單目標問題，每個子問題進化所需要的參考信息是由相鄰的子問題來提供，子問題與其相鄰的子問題依據參考信息相互協同進化。MOEA/D主要用于求解MaOP。該算法采用Tchebycheff分解法，MOEA/D的基本步驟如下。

步驟1 初始化：

（1）設EP=？椎。

（3）根據權重向量生成初始種群x1，x2，…，xN。令FVi=F（xi）。

（4）采用基于問題的特定方法初始化z=（z1*，z2*，…，zm*）。

步驟2 更新：

（1）從B（i）中隨機選取兩個序號k，l，運用遺傳算子由xk和xl產生一個新的解y。

（2）對y運用基于測試問題的修復和改進啟發產生y′。

（3）若zj

（4）若gte（y′|u，zu*）≤gte（xu|u，zu*），u∈B（i），若xu=y′，FVu=F（y′）。

（5）剔除EP中受y′支配所有的向量，并且在EP中向量都不支配y′時，令EP=EP∪{f（y）}。

步驟3 終止條件：如果滿足終止條件，則停止并輸出EP，否則轉步驟2。

其中，N是子問題的個數;？姿1，？姿2，…，？姿N是權向量;T是每個權重向量的鄰域中含有權重向量的個數;EP是最優解的集合，？椎是空集。

2 信息反饋MOEA/D算法

數值實驗表明，MOEA/D算法在求解大規模高維多目標優化問題時，會面臨比較復雜的Pareto最優解，會導致算法收斂速率慢，并且在同等評價次數情況下，求解質量不高[8]。

Wang[9]提出信息反饋機制策略，并將其引入啟發類算法中，從而提高算法的收斂性。Zhang[8]年研究如何將信息反饋機制引入到MOEA/D算法中，來改善算法在求解大規模高維多目標優化問題時性能不佳等狀況。

信息反饋機制的原理類似于求解線性方程組數值解法中的超松弛法，本質是第t代個體經過MOEA/D算法后，產生的個體是不能作為第t+1代的個體，只能是作為一個中間個體。將此中間個體與第t代中的若干個體，按一定的規律進行加權平均后得到新的個體，才能作為第t+1代的個體。在信息反饋機制中，由于中間個體可以和第t代若干個體進行組合，那么到底從第t代中選取多少個個體以及怎樣選取個體，這會產生多種信息反饋模型。

為了避免增加算法的復雜性，從第t代中選取個體的數目一般不要超過3個，并且從第t代選取個體有兩種選取方式，即固定方式和隨機方式，因此產生6種信息反饋模型。

雖然信息反饋模型有不同的形式，但是它們的結構基本上是相似的，而本文只研究從第t代選取個體的數目為1時的情形。

當從第t代選取個體的數目為1時，此時信息反饋模型可以按如下的方式定義[8]：

其中，xkt是第t代種群中的第k個個體，uit+1是用MOEA/D算法求出的中間個體，xit+1是第t+1代種群中的第i個個體，f表示個體對應的適應度。

很明顯，xit+1就是由xkt和uit+1加權平均生成的，并且權重？茲1和？茲2與適應度相關。有兩種方法可以對k進行確定：第一種是固定方式，即令k=i;第二種是隨機方式，即k=rand（1，2，…，N）。固定方法即為數值計算中的松弛法，可以起到對算法進行加速的作用。

在MOEA/D中，利用信息反饋模型來對種群進行更新，即可得到信息反饋MOEA/D算法。

3 自適應信息反饋模型改進的MOEA/D算法

Zhang和Wang提出了6種信息反饋模型[8]，并且利用這些模型對MOEA/D算法進行改進，得到6種改進后的MOEA/D算法，而MOEA/D1算法（固定方式選取第t代中一個個體）相較剩下5種算法而言，屬于模型改進后效果最好的算法，讓其產生的結果與其他相關算法產生的結果做了比較。

下面對種群的更新方式加以分析，信息反饋模型中的參數k的兩種選取方式各有優劣。固定方式是最符合常理，也是最自然的方式。采用此方式的算法，其收斂速度是比較快的，但是會面臨一些問題。比如當uit+1與xkt接近時，算法會陷入局部最優，非常容易導致算法早熟。此時，要想使算法跳出局部最優，只有靠隨機方式。因此在改進MOEA/D算法時，最佳方案是將固定和隨機這兩種方式根據具體情況進行自適應地結合，這樣既能夠保證算法收斂速度加快，又能盡量避免算法陷入局部最優。

基于上述的討論，本文提出了自適應信息反饋模型，將其應用在MOEA/D算法中。而構造自適應信息反饋模型的關鍵就在參數k的選取方式上，讓參數k根據算法自身收斂的狀況，來自行確定參數 的選取方式，即自適應性選擇。自適應的構造如下：

在進化的前期和中期，？滓值是控制算法過早收斂重要因素。因為當公式（3）計算出的？籽ab值小于預先設定的臨界值？滓（？滓的取值是10-2）時，算法可能會陷入局部最優的狀況。這時讓信息反饋機制中的參數k按照隨機的方式進行選取，這樣能使算法跳出局部最優狀況。如果算法沒有陷入局部最優狀況，那么信息反饋機制參數k的選取就用固定的方式。在進化后期，為了避免算法的收斂性遭到破壞，要根據算法收斂的情況，適當地放棄隨機性的選擇方式，直接采用固定的方式進行選擇。另外，要在程序中將總進化代數的后20%為設置為進化后期。

將自適應信息反饋模型應用到MOEA/D算法中，得到自適應信息反饋MOEA/D算法（MOEA/D based on adaptive information feedback， MOEA/D-AIF），簡記為MOEA/D-AIF。此間具體步驟如下：

步驟1 初始化種群。

步驟2 種群更新。

（1）將父代種群Pt，經過MOEA/D算法得到個體uit+1。

（2）根據目標函數梯度自適應來確定信息反饋方法，即自適應地確定k的選取方式，再根據公式（1）和（2）生成子種群Qt。

（3）將Pt和Qt合并，記為Dt。

（4）對Dt再利用MOEA/D算法，生成下一代父代種群Pt+1。

步驟3 達到設定值時，停止此循環并輸出結果EP。否則循環回到步驟2。

4 數值實驗與算法性能評測

為了評測本文提出的基于自適應信息反饋機制的MOEA/D算法的性能，用此算法對兩個標準測試函數DTLZ1和DTLZ2進行數值實驗，并將實驗結果與經典的MOEA/D算法的優化結果進行了比較。

4.1 DTLZ1測試函數

M=3時兩者的PF如圖4所示。

為了更準確、定量地衡量本文算法的性能，下面給出基于自適應信息反饋機制的MOEA/D算法和常規MOEA/D算法的世代距離（GD）和分散性（SP）兩個指標的對比數據。其中，GD指標反映的是算法的收斂性，而SP指標則描述了解的分布性。由于計算結果有隨機性，表1、表2中數據為GD指標數據和SP指標數據計算結果的平均值。

5 結論

圖3-6直觀顯示，基于自適應信息反饋機制的MOEA/D算法的解明顯優于常規MOEA/D算法的解。表1和表2中的指標進一步表明，MOEA/D-AIF算法與常規MOEA/D算法相比，SP指標相差不大，但GD指標明顯占優。

綜上，可以得出明確的結論：基于自適應信息反饋機制的MOEA/D算法較常規MOEA/D算法在收斂性方面有明顯提高，分布性和均勻性也有一定程度的改進。

參考文獻：

〔1〕孔維健.高維多目標進化算法研究綜述[J].控制與決策，2010，25（03）：321-326.

〔2〕袁源.基于分解的多目標進化算法及其應用[D].清華大學，2015.

〔3〕Zhang Q. F Li H. MOEA/D： A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on. Evolutionary Computation.， 2007，11（06）：712-731.

〔4〕Zhang Q， Liu W， Li H. The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances [A]. Evolutionary Computation， 2009[C]. 2009， 203-208.

〔5〕Zhou A， Zhang Q. Are All the Subproblems Equally Important？ Resource Allocation in Decomposition-Based Multiobjective Evolutionary Algorithms [J]. IEEE Transactions on Evolutionary Computation， 2016， 20（01）： 52-64.

〔6〕Ryoji Tanabe， Hisao Ishibuchi. An analysis of control parameters of MOEA/D under two different optimization scenarios [J]. Applied Soft Computing， 2018， 70： 22-40.

〔7〕Zhiming Dong， Xianpeng Wang， Lixin Tang. MOEA/D with a self-adaptive weight vector adjustment strategy based on chain segmentation [J]. Information Sciences， 2020， 521： 209- 230.

〔8〕Yin Zhang， Gai-Ge Wang， Keqin Li. Enhancing MOEA/D with information feedback models for large-scale many-objective optimization [J]. Information Sciences， 2020， 522： 1-16.

〔9〕G. Wang， Y. Tan， Improving metaheuristic algorithms with information feedback models [J]. ?IEEE Trans. Cybern.， 2019， 49（2）： 542-555.