基于速度約束和全局多樣性的MOPSO算法

趙 晶，曲相宇

(齊魯工業大學(山東省科學院)計算機科學與技術學院，山東 濟南 250353)

1 引言

在多目標優化問題中，這些目標往往互相矛盾，沒有一個單一的解決方案可以同時優化所有目標，因此其解集并不是唯一的[1-2]。如果想讓優化問題中的每個目標函數值達到最佳效果，需要對這些目標函數進行進一步的處理，目前有很多算法用于求解多目標優化問題，如基于參考點的非支配排序遺傳算法(A Fast and Elitist Multi-objective Genetic Algorithm，NSGA-Ⅱ)[3]，基于分解的多目標進化算法(A Multi-objective Evolutionary Algorithm Based on Decomposition，MOEA/D)[4]。在各種智能優化算法中，粒子群優化算法(Particle Swarm Optimization，PSO)是處理多目標優化問題的主流算法之一[5]。

在MOPSO算法中，如何提高算法所得的非支配解的收斂性和多樣性是算法亟待解決的主要難題，國內外專家對此作了很多研究[6]。粒子群優化算法的顯著特點是群中所有個體之間的協作，每個粒子都被群體中的全局最優(gBest)和自己的個體最優(pBest)所吸引從而改變自己的飛行方向，因此協作搜索策略使得粒子群算法具有更好的全局搜索能力[7-8]。另外，與其他進化計算算法相比，粒子群優化算法具有計算量小、收斂速度快的特點[9]。粒子群優化算法的相對簡單性和作為單目標優化算法的成功，促使研究者將粒子群算法的應用從單目標優化問題擴展到多目標優化問題。然而，除了檔案維護外，MOPSO仍有兩個問題有待進一步解決。

第一個是gBest和pBest的更新，多目標問題因為沒有絕對的最佳解決方案，而是一組非支配的解決方案。根據gBest和pBest的不同策略，可以從非支配集合中選擇不同的候選對象，gBest和pBest的不同選擇會導致粒子的飛行方向不同，這對粒子的收斂性以及MOPSO的多樣性有重要影響[10]。Knowles[11]等人通過增強多目標問題中非支配解的多樣性，提出了自適應超網格選擇全局最優解策略，但該方法會使得全局最優解朝著非代表性的支配前沿靠近，沒有兼顧到粒子的收斂性。Zhan[12]等人提出一種自適應粒子群優化算法，該算法預先定義粒子的4種進化狀態，從而對慣性因子、加速因子及其它參數達到自動控制的目的，有效平衡了解集的收斂性和多樣性。Zheng等人[13]通過綜合學習策略引入了一種新的MOPSO算法，該算法能夠保持群體的多樣性，并顯著提高進化粒子的性能。Lee 等人[15]提出了一種基于偏好排序的MOPSO算法，將用戶的偏好引入進化過程中，以確定非支配解的相對優缺點，以選擇合適的gBest和pBest。在每一次優化后，通過選擇全局評價值最高的方法來選擇最優的粒子作為gBest。結果表明，用戶的偏好在優化后的解中得到了很好的反映，而不損失整體解的質量和多樣性，但在粒子收斂性方面還有待加強。Liu等人[17]提出了一種基于平衡收斂性和多樣性的個體適應度計算策略(NMPSO)來定義解的新適應度，用于更好地尋找gBest和pBest，結果表明，NMPSO在某些多目標問題的表現不夠穩定。對于上述算法，如何選擇合適的具有適當收斂性和分布性的gBest和pBest仍然是一個挑戰[18-19]。

MOPSO的第二個問題是收斂性，為了實現MOPSO的快速收斂，人們提出了許多不同的策略。Nebro和Durillo等人提出了基于速度約束的多目標粒子群優化算法(Speed-constrained Multi-objective PSO，SMPSO)[16],該算法在傳統PSO基礎上引入收縮因子φ控制速度更新，提高了算法的收斂性，并跳出局部最優。但在算法多樣性方面表現欠佳。Li和Xiao[20]提出了一個動態MOPSO，在該模型中，群的數量在整個搜索過程中都是自適應調整的。動態MOPSO算法分配適當數量的群以支持收斂和分集準則。結果表明，在一些標準的基準問題上，所提出的動態MOPSO算法與所選算法相比具有一定的競爭力。韓等人[14]提出了一種基于種群多樣性信息的飛行參數調整機制來增強粒子收斂性，但在某些收斂時期易發生陷入局部最優的風險。在這些MOPSO算法中，為了獲得更好的性能，還開發了其它策略(如模糊聚類、協同協同進化等)[21，22]。然而，如何將MOPSO算法的收斂性和多樣性相結合的研究仍然不多[23]。

基于以上分析和回顧，本文提出一種基于速度約束和全局多樣性信息的多目標粒子群優化算法(SGDMOPSO)，SGDMOPSO算法主要從以下幾個方面進行了改進，原因如下：

1)速度更新方法中融入了速度收縮因子φ和新的由pBest到gBest的搜索方向，以提高整個粒子群的收斂速度，平衡粒子的全局搜索能力和局部開發能力。

2)采用基于精英庫多樣性信息的外部檔案維護策略，從非支配解的多樣性考慮，運用多個指標剔除劣勢解，能夠保持外部檔案中非劣解的多樣性。

3)從整個精英庫中的非支配解的多樣性考慮，非支配解的多樣性信息表征著算法在分布性方面的優劣，將此指標作為選取全局最優粒子的選擇機制，而全局最優解在本算法中影響著新的搜索方向，因此同時兼具了收斂性和多樣性，當精英庫中非支配解的多樣性好時，全局最優解的指標為收斂度最高的解；當精英庫中非支配解的多樣性不好時，全局最優解的指標為密集屬性最大的解。

通過上述改進，使得該算法在進化過程中具有更快的收斂速度和更高的處理MOPs的效率。

本文第二部分詳細介紹了SGDMOPSO算法：包括速度更新策略、外部存檔更新、算法流程；第三部分為仿真及結果分析；第四部分為總結。

2 SGDMOPSO算法

2.1 PSO算法及改進

1)PSO

粒子群優化算法(PSO)[24-25]是1995年由Kennedy和Eberhart提出的一種仿生啟發式算法，它模擬鳥群聚集的社會行為，算法結構簡單、參數少、收斂速度比較快。自從摩爾和查普曼在1999年首次將其擴展到多目標優化問題[26]以來，PSO算法已經成為解決多目標優化問題的一種非常流行的方法[14]。

PSO中的每個粒子有兩個屬性：位置x和速度v，它們由以下公式更新：

vi(t+1)=ω×v(t)+c1×r1×(pbesti-xi(t))

+c2×r2×(gbest-xi(t))

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

其中，xi為第t代粒子群中的第i個粒子，它的當前速度為vi(t)，當前位置為xi(t)，歷史最優位置為pbesti；整個粒子群的歷史最優位置為gbest；ω為慣性權重，用于調節粒子的飛行速度，如果ω大于1，會導致粒子的速度增加到無窮大，因此ω一般取小于1的隨機數；c1和c2分別表示向個體歷史最優和歷史全局最優的學習因子，r1和r2是兩個0到1之間的隨機數。

2)改進MOPSO速度控制

為了平衡PSO算法的全局搜索能力和局部開采能力，Zhan等人對慣性權重ω進行改進，使其在一定數值區間內作隨機調整[27]。Nebro和Durillo等人提出了基于速度約束的多目標粒子群優化算法(Speed-constrained Multi-objective PSO，SMPSO)，該算法在傳統PSO基礎上引入收縮因子φ控制速度更新，φ由學習因子c1和c2決定，其定義為[16]

(3)

Liu等人提出了一種平衡適應度值估計的多目標粒子群優化算法(A Balanceable Fitness Estimation for Many-objective PSO，NMPSO)，在速度更新過程中加入pbest到gbest的搜索方向[17]。為了避免加入新的搜尋方向對粒子尋優影響過大而削弱學習因子c1和c2的作用，更好地提升算法收斂速度和精度，本文在NMPSO的思想上，對PSO算法的速度更新策略做了進一步的改進，融入了由兩個學習因子c1和c2決定的速度收縮因子，使得粒子在新速度更新中既增加了方向的精細性，又保持了全局搜索能力和局部勘探能力。提出新的SMOPSO(Multi-objective Particle Swarm Optimization based on Speed-constraints,SMOPSO)算法，在該算法中，定義第i個粒子xi的速度更新公式為：

(4)

其中c1、c2、c3為學習因子；r1、r2、r3為0到1之間的隨機數。改進SMOPSO中xi的位置更新依然如PSO算子的式(2)一樣。通過在速度更新過程中增加由pbest到gbest的搜索方向，引導粒子群中的粒子向全局最優方向進化，加快粒子群的收斂速度。

在SMOPSO算法的速度控制策略中，進一步對粒子的速度中每一維元素越界做了壓縮控制

(5)

其中，Δj=0.5×(uj-dj),j=1,2，…,m,m為目標數，uj和dj分別為每個粒子速度第j元素的上下界限。

2.2 基于精英庫的外部檔案更新

外部檔案主要用于存儲粒子在迭代過程中求得的較好的非支配解，當非支配解的數量達到最大容量時，在MOPSO算法[28]中，本文提出基于精英庫的多樣性信息的外部存檔更新機制，將不同時期的外部存檔用多種規則靈活地進行更新，保留當前外部存檔時期最合適的非支配解，最大程度上維護解集的多樣性。基本思路如下：設At為第次迭代后產生的精英庫，At由第t次迭代產生的非支配解集Bt和前t-1次迭代保留下來的非支配解集Ct-1組成。如果在第t次迭代后算法產生的解被t-1代精英庫At-1中的解支配時，該解不是非支配解，不能進入精英庫At；如果精英庫At-1中的解被第t次迭代產生的解所支配時，精英庫中該支配解不再為非支配解，將其放入集合Dt-1中。

定義1(密集屬性)：一個非支配解的密集屬性為該非支配解與其相鄰的兩個非支配解的平均歐氏距離，即

(6)

其中，Disti是第i個非支配解密集屬性，dist1i、dist2i是與第i個非支配解相鄰非支配解的歐氏距離。非支配解的密集屬性越小，表示該非支配解附近越擁擠。

定義2(支配屬性)：一個解x∈Bt的支配屬性EA(x)是x在精英庫At中能夠支配的解y∈Dt-1的數目，即

EA(x)=|{y|y∈Dt-1∧x>y∧x∈Bt}|

(7)

其中Bt是第t次迭代產生的精英庫At中的非支配解集，Dt-1是第t次迭代產生的精英庫At中所支配的解的集合。當EA(x)為零時，該解支配屬性為零。

這里，非支配解集Bt中的解包含兩種：一種是可以支配Dt-1集合中的解(支配不為零)；另一種是不可以支配Dt-1集合中的解(支配屬性為零)。

定義3(收斂屬性)：一個解x∈Bt的收斂屬性是其與所有被其支配的解yi∈Dt-1的平均歐氏距離，即

(8)

其中，Dave(x)是解x的收斂屬性，yi是被解x支配的第i個解。非支配解集Ct-1中解的收斂屬性為零，無支配屬性的解其收斂屬性也為零。

精英庫At更新的具體流程如下：

Step1：若精英庫At容量未滿，則非支配解直接進入。

Step2：若精英庫At容量已滿，執行以下操作：從精英庫At中非支配解的多樣性考慮，計算精英庫At中每個非支配解的密集屬性，刪減解集Ct-1中密集屬性較小的解和非支配解集Bt中支配屬性為零的解。

Step3：如果刪減完密集屬性較小和支配屬性為零的解后仍然超出精英庫容量，考慮刪減Dt-1集合中支配屬性不為零的解。計算此時精英庫中非支配解的收斂屬性Dave，刪減Dave較小的解，若Dave相等，則執行Step4。

Step4：計算解集Bt中解的支配屬性，比較支配屬性大小，優先刪減支配屬性較小的解。

2.3 全局最優選擇機制

由于PSO算法優化過程中容易出現早熟現象，導致算法陷入局部最優，為了更好地跳出局部最優，收斂至全局最優，在保證收斂性的情況下根據多樣性信息選擇最優的全局最優解。

定義4(多樣性信息)：本文的多樣性信息一共分為兩種，一種為種群多樣性信息，一種為精英庫非支配解的多樣性信息。

種群多樣性信息：從整個粒子群考慮，種群多樣性能反映種群的粒子分布情況。種群多樣性不好，有可能導致算法優化過程中尋優速度慢、精度不夠。其表達式為

(9)

式中，SPp(t+1)是第t+1次迭代粒子群的種群多樣性信息，dpt(t+1)是在第t+1次迭代第i個粒子與其它粒子之間最小的曼哈頓距離，dpi(t+1)是所有的dpi(t+1)的平均值，n1是粒子的個數。

非支配解多樣性信息：從精英庫中非支配解的多樣性考慮，非支配解的多樣性代表了算法在分布性方面的性能，非支配解多樣性越好表示算法分布多樣性越好。其表達式為

(10)

根據式(10)計算的非支配解多樣性信息可以作為精英庫中非支配解集的多樣性度量指標，通過比較非支配解多樣性SPn(t+1)值與α值的大小關系(α為非支配解多樣性信息SPn(t+1)優劣性的分界值，在文中方法中定義α=0.05)，判斷當前整個精英庫中非支配解集的分布狀態。

全局最優解選擇機制為：

1)若SPn(t+1)≤α，說明整個精英庫非支配解的多樣性比較好，從算法角度考慮應提高算法收斂速度，此時全局最優解應選取收斂屬性最大的非支配解。

2)若SPn(t+1)>α，說明整個精英庫非支配解的多樣性比較差，從算法角度考慮應增加粒子分布的多樣性，此時全局最優解應選取密集屬性最大的非支配解。

2.4 SGDMOPSO算法流程

Step1：參數初始化：設置種群規模，最大迭代次數，個體粒子的速度、位置、慣性權重、學習因子，并將各粒子的初始位置設為其當前個體最優位置pbesti。

Step2：計算各粒子的適應度值，根據適應度值得到精英庫，根據式(6)(7)和(8)分別計算各個非支配解的密集屬性、支配屬性和收斂屬性。

Step3：計算當前整個精英庫非支配解多樣性SPn(t+1)，根據1.3節全局最優選擇策略確定全局最優解。

Step4：比較Step2中精英庫中各個非支配解的密集屬性、支配屬性和收斂屬性的值，按照精英庫更新策略，生成新的精英庫。

Step5：按照式(1)和(2)更新粒子的位置和速度。

Step6：判斷是否達到迭代次數，如達到迭代次數，則結束更新，否則轉到Step2。

3 實驗

3.1 MOP測試函數

1)性能標準

在多目標優化問題中，衡量一個算法應從收斂性和多樣性的角度來評價，因此本文采用以下兩個定量指標來說明算法效果。

①反向世代距離Inverted Generational Distance(IGD)：IGD通過計算所求得的近似Pareto最優解集前沿面的距離來綜合評價算法的收斂性與多樣性，IGD可定義為

(11)

其中，dist(x,P)為真實前沿P*中一個解x和所獲Pareto前沿之間的最小歐氏距離，|P*|表示真實的Pareto最優解集上的點的數量。IGD越小表明算法的收斂性和多樣性越好。

(12)

其中，Vol(·)表示勒貝格測度。其中P中所有的解都應能支配zr，如果不能支配，則將該解從P中刪除。HV越大表明算法的多樣性和收斂性越好。

2)標準測試函數

為了驗證SGDMOPSO算法的性能，本文采用標準測試函數ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ2和DTLZ7對4種算法進行測試。

為了對比不同算法的有效性能，將SGDMOPSO算法與SMPSO算法[16]、NSGA-Ⅱ算法[3]、NMOPSO算法[17]的測試數據相比較。在比較實驗中，算法執行時的參數設置為：各算法種群大小和精英庫外部存檔的最大容量均為100，最大迭代次數為2000。各算法的具體參數設置如表1所示，測試函數的參數設置如表2所示。

表1 算法參數設置

表2 測試函數參數設置

3.2 實驗結果與分析

表3和表4分別列出了4種算法在ZDT和DTLZ系列測試函數上的IGD和HV，Mean和Std分別表示同一算法在相同測試問題上獨立運行30次后的均值和方差，它們的最優數據用粗斜體表示，由此可反映出IGD和HV測試性能的綜合評價效果。圖1～6為4種算法得到的非劣支配解和真實的非劣支配解之間的相互關系。

從表3和表4可以看出，算法SGDMOPSO在給定的7個測試問題中分別獲得5個最優IGD值和4個HV值，可見SGDMOPSO算法在這7個測試問題的多樣性和收斂性表現優秀，在以上幾種測試問題上幾乎都優于其它3種算法。對于ZDT4測試問題，SGDMOPSO性能上要稍遜于NSGA-Ⅱ，在其它測試問題均優于NSGA-Ⅱ；對于DTLZ2和DTLZ7測試問題，SGDMOPSO性能上要稍遜于NMOPSO，在其它測試問題上都優于NMOPSO。從總體結果來看，本文算法在綜合性能優于其它的3種比較算法。

圖1 ZDT1的Pareto曲線

圖2 ZDT2的Pareto曲線

圖3 ZDT3的Pareto曲線

圖4 ZDT4的Pareto曲線

圖5 ZDT6的Pareto曲線

圖6 DTLZ2的Pareto曲線

表3 SGDMOPSO算法與其它算法的IGD指標

表4 SGDMOPSO算法與其它算法的HV指標

從圖1～6可以看出，SGDMOPSO在測試問題ZDT1、ZDT2、ZDT3、ZDT4、ZDT6和DTLZ2求得的非支配解的分布性和收斂性均較好。對于ZDT1、ZDT2和ZDT3測試問題，4種算法雖然都能夠較好地求得Pareto前沿，但SGDMOPSO算法得到的非支配解的分布性更加均勻。對于ZDT4測試問題，NMPSO算法所求得的Pareto前沿效果分布性較差,SGDMOPSO算法求得的Pareto前沿分布依然最均勻。對于ZDT6測試問題，SGDMOPSO算法獲得的Pareto前沿分布效果比其它3種算法好，不僅能夠較好地與真實Pareto前沿趨于吻合，且解的分布情況也比較均勻。對于三維測試問題DTLZ2，SGDMOPSO算法和NMPSO算法在DTLZ2的測試效果要好于其它兩種算法。換句話說，SGDMOPSO算法在大部分測試目標上都優于其它3種算法。

4 結語

為了更好地提高收斂速率和避免陷入局部最優，本文提出SGDMOPSO算法，通過改進速度更新公式和全局多樣性信息選取最優解來提升算法的性能，將粒子速度方向控制、全局最優選擇策略、精英庫外部檔案維護策略較好地統一在一起。實驗結果表明，提出的算法能夠獲得較好的Pareto最優前沿分布特性和較快的收斂速率。盡管SGDMOPSO算法已經能夠獲得較高地收斂精度和較好的多樣性，但是對于處理某些具體實際問題還存在一定局限性，下一步的研究考慮融入其它智能優化算法的思想，如微分進化算法、遺傳算法等，從而更好地從多樣性和收斂性兩方面來探究求解高維多目標優化問題的有效性和可行性。