自適應(yīng)信息反饋模型改進(jìn)的MOEA/D算法

王啟翔 許峰

摘 要：為了提高M(jìn)OEA/D算法求解大規(guī)模高維多目標(biāo)優(yōu)化問題的能力，本文提出一種基于自適應(yīng)信息反饋機(jī)制改進(jìn)的MOEA/D算法，其基本思想是根據(jù)信息反饋原理，將當(dāng)前代第k個(gè)個(gè)體與用MOEA/D算法求得的第i個(gè)個(gè)體加權(quán)平均后作為下一代第i個(gè)個(gè)體。k的選取有指定和隨機(jī)兩種方式，可以根據(jù)目標(biāo)函數(shù)的梯度自適應(yīng)地選擇。采用標(biāo)準(zhǔn)的測試函數(shù)來評(píng)測改進(jìn)后的算法的性能。結(jié)果表明，改進(jìn)后的MOEA/D算法在收斂性方面有明顯的提高。

關(guān)鍵詞：大規(guī)模高維多目標(biāo)優(yōu)化;MOEA/D;信息反饋;自適應(yīng);目標(biāo)函數(shù)梯度

中圖分類號(hào)：TP391 ?文獻(xiàn)標(biāo)識(shí)碼：A ?文章編號(hào)：1673-260X（2021）04-0025-04

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

基于分解的MOEAs根據(jù)分解的形式可分為基于聚合函數(shù)的MOEAs和基于參考向量分解的MOEAs[2]?；诜纸獾亩嗄繕?biāo)進(jìn)化算法中具代表性的算法是MOEA/D。Zhang提出了基于多目標(biāo)分解的MOEA/D[3];為了改善計(jì)算資源的分配，Zhang提出了改進(jìn)的MOEA/D，稱為MOEA/D-DRA[4];在MOEA/D-DRA的基礎(chǔ)上，Zhou和Zhang提出了MOEA/D-GRA[5];Ryoji[6]分析了MOEA/D的控制參數(shù);Dong[7]提出了自適應(yīng)權(quán)重MOEA/D。Zhang和Wang[8]提出了一種基于信息反饋的改進(jìn)MOEA/D。

Zhang和Wang將信息反饋模型中參數(shù)k的兩種選擇方式對(duì)應(yīng)為兩種不同的算法，分別研究了這兩種算法對(duì)MOEA/D的改進(jìn)[8]?？紤]到參數(shù)k的兩種選擇方式的優(yōu)缺點(diǎn)，本文提出了一種針對(duì)參數(shù)k選擇方式的不同來進(jìn)行自適應(yīng)地確定參數(shù)k選擇方式的算法，具體做法就是利用目標(biāo)函數(shù)的梯度，來構(gòu)建自適應(yīng)性選擇，從而確定參數(shù)k的選擇方式。對(duì)改進(jìn)后算法的性能，一般用標(biāo)準(zhǔn)化測試函數(shù)對(duì)其進(jìn)行評(píng)測，并將改進(jìn)后算法得出的結(jié)果和MOEA/D算法產(chǎn)生的結(jié)果相比較。

1 MOEA/D算法

在MOEA/D算法中，權(quán)重向量的生成方式是多種多樣的，可以根據(jù)自己的需求預(yù)先設(shè)置權(quán)重向量，再利用權(quán)重向量將復(fù)雜的多目標(biāo)優(yōu)化問題轉(zhuǎn)換成一個(gè)一個(gè)的單目標(biāo)問題，每個(gè)子問題進(jìn)化所需要的參考信息是由相鄰的子問題來提供，子問題與其相鄰的子問題依據(jù)參考信息相互協(xié)同進(jìn)化。MOEA/D主要用于求解MaOP。該算法采用Tchebycheff分解法，MOEA/D的基本步驟如下。

步驟1 初始化：

（1）設(shè)EP=？椎。

（3）根據(jù)權(quán)重向量生成初始種群x1，x2，…，xN。令FVi=F（xi）。

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

步驟2 更新：

（1）從B（i）中隨機(jī)選取兩個(gè)序號(hào)k，l，運(yùn)用遺傳算子由xk和xl產(chǎn)生一個(gè)新的解y。

（2）對(duì)y運(yùn)用基于測試問題的修復(fù)和改進(jìn)啟發(fā)產(chǎn)生y′。

（3）若zj

（4）若gte（y′|u，zu*）≤gte（xu|u，zu*），u∈B（i），若xu=y′，F(xiàn)Vu=F（y′）。

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

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

其中，N是子問題的個(gè)數(shù);？姿1，？姿2，…，？姿N是權(quán)向量;T是每個(gè)權(quán)重向量的鄰域中含有權(quán)重向量的個(gè)數(shù);EP是最優(yōu)解的集合，？椎是空集。

2 信息反饋MOEA/D算法

數(shù)值實(shí)驗(yàn)表明，MOEA/D算法在求解大規(guī)模高維多目標(biāo)優(yōu)化問題時(shí)，會(huì)面臨比較復(fù)雜的Pareto最優(yōu)解，會(huì)導(dǎo)致算法收斂速率慢，并且在同等評(píng)價(jià)次數(shù)情況下，求解質(zhì)量不高[8]。

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

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

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

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

當(dāng)從第t代選取個(gè)體的數(shù)目為1時(shí)，此時(shí)信息反饋模型可以按如下的方式定義[8]：

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

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

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

3 自適應(yīng)信息反饋模型改進(jìn)的MOEA/D算法

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

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

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

在進(jìn)化的前期和中期，？滓值是控制算法過早收斂重要因素。因?yàn)楫?dāng)公式（3）計(jì)算出的？籽a(bǔ)b值小于預(yù)先設(shè)定的臨界值？滓（？滓的取值是10-2）時(shí)，算法可能會(huì)陷入局部最優(yōu)的狀況。這時(shí)讓信息反饋機(jī)制中的參數(shù)k按照隨機(jī)的方式進(jìn)行選取，這樣能使算法跳出局部最優(yōu)狀況。如果算法沒有陷入局部最優(yōu)狀況，那么信息反饋機(jī)制參數(shù)k的選取就用固定的方式。在進(jìn)化后期，為了避免算法的收斂性遭到破壞，要根據(jù)算法收斂的情況，適當(dāng)?shù)胤艞夒S機(jī)性的選擇方式，直接采用固定的方式進(jìn)行選擇。另外，要在程序中將總進(jìn)化代數(shù)的后20%為設(shè)置為進(jìn)化后期。

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

步驟1 初始化種群。

步驟2 種群更新。

（1）將父代種群Pt，經(jīng)過MOEA/D算法得到個(gè)體uit+1。

（2）根據(jù)目標(biāo)函數(shù)梯度自適應(yīng)來確定信息反饋方法，即自適應(yīng)地確定k的選取方式，再根據(jù)公式（1）和（2）生成子種群Qt。

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

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

步驟3 達(dá)到設(shè)定值時(shí)，停止此循環(huán)并輸出結(jié)果EP。否則循環(huán)回到步驟2。

4 數(shù)值實(shí)驗(yàn)與算法性能評(píng)測

為了評(píng)測本文提出的基于自適應(yīng)信息反饋機(jī)制的MOEA/D算法的性能，用此算法對(duì)兩個(gè)標(biāo)準(zhǔn)測試函數(shù)DTLZ1和DTLZ2進(jìn)行數(shù)值實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與經(jīng)典的MOEA/D算法的優(yōu)化結(jié)果進(jìn)行了比較。

4.1 DTLZ1測試函數(shù)

M=3時(shí)兩者的PF如圖4所示。

為了更準(zhǔn)確、定量地衡量本文算法的性能，下面給出基于自適應(yīng)信息反饋機(jī)制的MOEA/D算法和常規(guī)MOEA/D算法的世代距離（GD）和分散性（SP）兩個(gè)指標(biāo)的對(duì)比數(shù)據(jù)。其中，GD指標(biāo)反映的是算法的收斂性，而SP指標(biāo)則描述了解的分布性。由于計(jì)算結(jié)果有隨機(jī)性，表1、表2中數(shù)據(jù)為GD指標(biāo)數(shù)據(jù)和SP指標(biāo)數(shù)據(jù)計(jì)算結(jié)果的平均值。

5 結(jié)論

圖3-6直觀顯示，基于自適應(yīng)信息反饋機(jī)制的MOEA/D算法的解明顯優(yōu)于常規(guī)MOEA/D算法的解。表1和表2中的指標(biāo)進(jìn)一步表明，MOEA/D-AIF算法與常規(guī)MOEA/D算法相比，SP指標(biāo)相差不大，但GD指標(biāo)明顯占優(yōu)。

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

參考文獻(xiàn)：

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

〔2〕袁源.基于分解的多目標(biāo)進(jìn)化算法及其應(yīng)用[D].清華大學(xué)，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.