基于社會學習粒子群的大規模多目標優化算法

劉能現

（福州大學研究生院， 福州 350116）

0 引 言

多目標優化問題（Multi－Ojective Optimization Problems，MOPs）廣泛存在于工程實踐和科學研究中。 如：社區檢測［1］、云工作流調度［2］和車輛路徑問題［3］等。 多目標優化問題通常含有2 個及以上的目標，且這些目標之間相互沖突。 過去的幾十年，關于多目標優化問題的研究取得了很大發展，研究人員提出了大量的多目標進化算法（Multi－Objective Evolutionary Algorithms， MOEAs），這些算法大致可以分為Pareto 支配多目標算法（如NSGA－II），基于分解的多目標算法（如MOEA／D），基于指標的多目標算法（如IBEA），及其它不屬于前3 類的算法（如MOEA／DD）等等。 近年來，大多數關于多目標進化算法的研究主要集中在高維多目標優化問題上，而對于決策變量較多的多目標優化問題關注較少。 然而，現實世界中很多多目標優化問題可能有數百甚至數千個決策變量，這類問題被稱為大規模多目標優化問題（Large－Scale MOP， LSMOP）［4］。

通常，大規模MOP 比決策變量少的MOP 更難解決，其主要原因是MOP 的搜索空間與決策變量的數量呈指數關系，即維度災難問題，使得大多數現有多目標進化算法無法有效地探索搜索空間，并可能會過早地收斂到局部最優值或收斂到太大的區域［5］。 盡管大規模單目標優化問題多年來一直是熱門研究課題，但大規模多目標優化的研究仍處于早期階段。 一般來說，現有的求解大規模多目標問題的進化算法可以大致分為3 類［6］：

（1）基于決策變量分組算法

該類算法在求解大規模優化問題時使用分治策略，將決策變量隨機或啟發式地分成幾組，然后交替優化每組決策變量。 該策略已廣泛用于解決大規模的單目標優化問題，但大規模的多目標優化問題包含多個相互沖突的目標，決策變量之間的相互關系更加復雜，在決策變量分組與優化時，應考慮總體的收斂性和多樣性。 現有MOEA 中的決策變量分組技術主要包括隨機分組、差分分組和變量分析。 如：CCGDE3［7］算法使用隨機分組策略，將決策變量隨機劃分為大小相同的分組。 雖然該算法在一些優化問題上取得了較滿意的優化結果，但由于沒有考慮變量之間的相互關系，在處理具有復雜變量關系的大規模多目標優化問題時效果較差。 Ma 等人［8］提出了一種基于決策變量分析的大規模多目標優化算法MOEA／DVA。 該算法根據收斂性和多樣性把決策變量分成位置相關變量、距離相關變量和混合變量，在解決某些大規模多目標優化問題時具有較好的效果，但需要大量的適應度評估進行變量分析。Zhang 等人［9］進一步擴展了MOEA／DVA 算法，提出了LMEA 算法。 該算法根據角度，把決策變量分為收斂性相關決策變量和多樣性相關決策變量。

（2）基于決策空間縮減算法

該類算法用降維的思想，將父代的決策向量維數縮短并用于生成后代，然后將縮短的后代向量恢復到原始決策空間進行函數評估。 因此，該類算法只需要找到一個短向量的最優值，而不是在高維決策空間中搜索。 目前降維的技術主要包括問題轉換、問題重構、隨機嵌入、主成分分析等。 如：Zille等人［10］提出了一種加權優化框架（WOF），該框架對原優化問題通過變量分組和加權實施轉換。 其主要思想是采用分組策略將決策變量劃分成幾組， 每組變量關聯一個權重， 即在同一組內的變量具有相同的權重， 從而將大規模決策變量的優化轉化為對維度較低權重向量的優化， 實現對原搜索空間的降維，但該方法在重構解時較依賴于分組策略。 He 等人［11］提出采用問題重構優化框架LSMOF，其核心思想是通過問題重構直接跟蹤Pareto 最優解。 基于LSMOF 的思想，Qin 等人［12］提出了一種大規模多目標優化方法LMOEA－DS，該方法在搜索方向上直接生成解。

（3）基于新搜索策略算法

該類算法通過設計新穎搜索策略直接在原搜索空間生成后代，來求解大規模多目標優化問題。 這類算法只需設計相對簡單的操作就能在不同的大規模多目標優化問題取得較好的性能。 新的搜索策略主要包括新的生成后代的操作算子、概率模型等。 如：Tian 等人［4］提出一種基于競爭學習粒子群的大規模多目標優化算法LMOCSO。 在該算法中，作者提出一種考慮速度和加速度的新策略。 其中，失敗粒子向獲勝粒子學習，使失敗粒子能更有效地向更好的位置移動。 Cheng 等人［13］提出了一種基于概率模型的大規模多目標優化算法IM－MOEA，該算法通過構建基于高斯過程的逆模型，將解從目標空間映射到決策空間，并使用逆模型對目標空間進行采樣來生成后代。

盡管現有的大規模多目標優化算法都有良好的性能，但每一類算法也有其自身的不足。 如基于決策變量分組的方法，在求解復雜景觀的多目標優化問題會遇到困難。 具體來說，基于決策變量分組的MOEA，可能會將兩個相互關聯的變量分到不同的組，因此在分別優化這兩個變量時，算法很可能陷入局部最優。 對于基于決策變量分析的MOEA，雖然能夠檢測變量間的相互關系，但該操作需要大量的函數評估。 基于決策空間縮減的算法，可以快速找到大規模多目標優化問題的一些局部最優解，但即使消耗更多的函數評估，其也可能無法找到全局最優解，這是因為轉換后的問題很可能會丟失原始大規模多目標優化問題的全局最優解［6］。 基于新搜索策略的算法一般需要較多函數評估次數才能獲得問題解［12］，但新搜索策略一般獨立于選擇策略，其可以比較容易地嵌入到許多MOEA 中，以提高其在處理大規模多目標優化問題上的性能。

受基于競爭機制粒子群的大規模多目標優化算法的啟發，本文基于社會學習的粒子群算法，提出了一種處理大規模多目標優化問題的算法LMOSLPSO。 通過實驗對比發現，該算法比其它幾個大規模多目標進化算法有更好的性能表現。

1 相關概念

1.1 多目標優化問題

不失一般性，求最小值問題的多目標優化問題可描述如下：

其中，x＝（x1，x2，…，xD） 表示決策空間的D維向量；m為目標個數；fi（x）；i＝1，2，…，m是m維目標空間中的目標函數；gp和hq分別表示k個不等式約束和l個等式約束。

給定兩個可行解xa和xb，xa支配xb，當且僅當對于?i，fi（xa） ≤fi（xb） 和?j，fj（xa）＜fj（xb），i，j∈｛1，2，…，m｝ 。 如果沒有其他解支配x?， 那么x?稱為帕累托最優解。 所有的帕累托最優解構成帕累托最優解集（Pareto optimal Set，PS），其目標值構成帕累托前沿（Pareto Front，PF）。

帶2 個最小化目標的優化問題如圖1 所示。 其中，x3支配x1和x2，x1和x2之間互不支配，藍色曲線上的點為帕累托最優解，藍色曲線為帕累托前沿。

圖1 帶2 個最小化目標的優化問題Fig. 1 Optimization problems with two minimization objectives

1.2 基于社會學習的粒子群算法

為求解單目標優化問題， Kennedy 等于1995 年提出粒子群優化算法（PSO），該算法在求解決策變量規模較小的問題時有較好的效果。 但是，隨著問題規模的增大，PSO 算法在搜索過程中較難平衡算法收斂性以及種群多樣性，而且粒子在算法搜索的后期容易早熟收斂，陷入局部極值。 為此，Cheng 等人［14］在2015 年提出了一種改進的粒子群算法來求解大規模單目標優化問題，并將其稱為基于社會學習的粒子群算法（SLPSO）。

在SLPSO 算法中，首先按適應值大小對種群中的粒子進行排序，然后種群中除最優粒子外的其它粒子以一定的概率向其它較好的粒子及種群的平均位置學習。 具體學習方式由公式（2）、（3）定義。

其中：

式中：v、x和g分別表示粒子的速度、位置和進化代數，r1，j、r2，j和r3，j均為區間［0，1］ 內的隨機數，為社會影響因子，用來調節算法的多樣性和收斂性，其中β＝0.01，M＝100，k表示粒子i在j維上學習粒子（示范粒子），k選擇過程如圖2 所示，為當前種群在第j維上的平均值，ps為種群大小。

圖2 種群排序和選擇示范粒子kFig. 2 Population sorting and selection of demonstration particle k

2 基于社會學習粒子群的大規模多目標算法

2.1 算法框架

圖3 LMOSLPSO 算法的框架圖Fig. 3 The framework of LMOSLPSO algorithm

算法1LMOSLPSO 框架

初始化：種群大小ps，問題維數D，最大函數評估次數FESmax，函數評估次數FES，隨機初始化種群P；

while（FES ＜FESmax） do

P′←基于社會學習的粒子群進化（P）；

P←環境選擇（P，P′）；

end

輸出P中的所有非支配個體

二是全面性原則。量化評審指標設置要盡可能全面完整、相互銜接，指標之間在內涵與外延上不能彼此交叉，互相重復。因此，在確定量化指標和評分標準時，要堅持從學歷資歷、能力水平、業績成果等各方面對專業技術人員進行全方位評價。并要根據不同專業性質、崗位特點和技術復雜難易程度等，研究制定有針對性的、各有側重的評價指標體系，科學合理確定各級指標分值和權重。量化評價體系既要綜合評價參評人員各方面的能力，又要便于申報者之間進行比較，科學區別，保證優秀人才優先晉升。

2.2 基于社會學習的粒子群進化

基于社會學習的粒子群進化主要包括粒子的適應值計算、種群P 的排序及學習概率設置、粒子的速度和位置更新，以及所有粒子的多項式變異操作等。 基于社會學習的粒子群進化操作的偽代碼如算法2 所示。算法2基于社會學習的粒子群進化（P）輸入當前種群P；

利用公式（6）計算種群P中每個粒子的適應值；

對種群P按適應值從大到小（好到差）進行排序；

按公式（7）計算種群P中每個粒子學習概率；

for 除最優粒子外的每個粒子xiinPdo

if（lpi ＞rand） then ／ ／學習率大于隨機數

｛k，l｝ ←從［1，i］ 中隨機選擇兩個粒子；

使用公式（8）更新粒子速度vi；

使用公式（3）更新粒子位置xi；

end if

end for

對所有粒子執行變異操作并放入后代種群P′

輸出后代種群P′首先，進行粒子的適應值計算，與單目標優化問題不同，因多目標優化問題含有多個目標且各個目標之間相互沖突，無法采用單個目標值直接進行粒子優劣的比較，為此需要一個能夠評價粒子優劣的方法。 本文采用轉換的密度估計策略（Shift－based Density Estimation，SDE）［16］來求解每個粒子的適應值。 SDE 策略能夠從多樣性和收斂性兩個方面進行粒子的質量評價，并已被多個MOEAs 所采用［4］。因此，在LMOSLPSO 算法中，本文也采用了基于SDE 的策略來評估種群中每個個體的收斂性和多樣性。 具體來說，用最小的基于SDE 的距離公式（6）［16］來定義粒子x的適應值。

按社會學習粒子群的思想，對種群P中的粒子按適應值從大到小進行排序，并按公式（7）計算每個粒子的學習率lpi，即為粒子排序值i除以種群數ps，表示越差的粒子越有機會向好的粒子學習。

接著對每個粒子按學習概率進行速度更新和位置更新。 具體來說，隨機產生0 到1 之間隨機數rand，當學習率大于隨機數rand時，從種群中隨機選擇比粒子i具有更好適應值的兩個粒子k、l，并按公式（8）更新粒子速度和按公式（3）更新粒子位置。本文的速度更新公式（8）與公式（2）不同，由于在多目標優化中，使用相同的種群平均位置引導種群會使種群失去多樣性，因此本文利用了兩個適應值較好的粒子來引導種群進化。

最后，為進一步提高LMOSLPSO 算法性能，避免算法陷入局部極值，對種群中的每個粒子執行多項式變異操作［17］。 在基于社會學習的粒子群進化結束后返回到算法1，執行多目標環境選擇操作。

3 實驗結果與分析

3.1 對比算法及測試函數

為驗證LMOSLPSO 算法的效果，將其算法與多個經典的多目標算法進行對比。 其中包括：LMEA［9］、IM－MOEA［13］、MMOPSO［18］和LMOCSO［4］。

實驗采用大規模多目標測試集［19］作為測試問題，即LSMOP1－LSMOP9。 LSMOP 測試集是在大規模單目標問題基礎上設計的，該測試集的問題具有較好的可擴展性和普遍性。 在這9 個LSMOP 問題中，在Pareto 集上存在線性變量連接（如LSMOP1－LSMOP4） 和非線性變量連接（如 LSMOP5 －LSMOP）， 以及線性Pareto 前沿（如LSMOP1 －LSMOP4）、凹Pareto 前沿（如LSMOP5－LSMOP8），和非連續Pareto 前沿（如LSMOP9）。

3.2 評價指標

為了比較不同算法的性能， 本文采用反轉世代距離（Inverted Generational Distance，IGD） 作為性能指標，來評價不同算法的實驗結果。 假設目標空間中最優Pareto 前沿面上均勻分布的點集合為P?，算法所求得的非支配解集為P，則IGD的計算公式定義為

其中，dist（x，y） 表示點x到點y之間的歐氏距離。 因此，反轉世代距離IGD是從最優前沿面P?中的每個點到支配解集P的平均最小距離，其測量的是支配解集P的收斂性和均勻性。IGD值越小，說明對應算法的綜合性能越好。 同時，采用顯著性水平為0.05 的威爾科克森符號秩檢驗對不同對比算法進行比較。

3.3 實驗設置

本文實驗采用Tian 等人［20］提出的PlatEMO 平臺，所有算法采用Matlab 語言編程。 實驗所用的電腦配置：中央處理器采用Inter（R）Core（TM）i5－4590 CPU＠3.30 GHZ，內存8.00 GB，操作系統Windows 7。

相關算法的參數參考文獻［4］設置，所有對比算法種群大小設置相同；對于2 個目標的問題種群大小設置為300，3 個目標的問題種群大小設置為496。 對于LSMOP1 ～LSMOP9 問題，每個變量組的子分量數量nk設置為5，目標數M設置為2 和3，決策變量維數D的大小從100 到500 不等。 最大函數評估次數作為所有對比算法的終止條件，設置為15 000×D。

3.4 實驗結果

不同算法在2 維多目標問題LSMOP1－ LSMOP9函數上IGD值的平均值和標準差詳見表1，最好的IGD值用藍色粗體字體標出。 從表1 中可見，本文提出的LMOSLPSO 算法對比其他4 種方法獲得了更好的優化結果。 所提出的LMOSLPSO 算法在27 個測試問題中獲得了17 個最優平均IGD值。 對比算法LMEA、IMMOEA、MMOPSO 和LMOCSO 分別在0、5、1和4 個測試問題上獲得了最優平均IGD值。 具體來說，與LMEA 相比，本文提出的LMOSLPSO 算法在27個測試問題中的22（5）個測試問題上表現更好（相似）。 與IMMOEA 相比，LMOSLPSO 算法在27 個測試問題中的17（4）個測試問題上表現更好（相似）。與MMOPSO 相比，LMOSLPSO 算法在27 個測試問題中的21（1）個測試問題上表現更好（相似）。 與LMOCSO 相比，LMOSLPSO 算法在27 個測試問題中的19 （3） 個測試問題上表現更好（相似）。LMOSLPSO 算法具有更好的性能主要是因為其使用了基于社會學習的粒子群進化操作。

表1 不同算法在2 維LSMOP1－LSMOP9 上得到IGD 的平均值和標準差比較Tab. 1 Comparison of the mean and standard deviation of IGD obtained by different algorithms on 2－dimensional lsmop1－lsmop9

表2 給出了所有對比多目標算法在3 維多目標問題LSMOP1～LSMOP9 函數上的IGD值的平均值和標準差，最好的IGD值用藍色字體標出。 從表2中我們同樣可以清楚地看出， 本文提出的LMOSLPSO 算法比4 種對比方法獲得了更好的優化結果。 所提出的LMOSLPSO 算法在27 個測試問題中的13 個上獲得了最優平均IGD值，對比算法LMEA、IMMOEA、MMOPSO 和LMOCSO 分別在0、4、1 和9 個測試問題上獲得了最優平均IGD值。 具體來說，與LMEA 相比，本文提出的LMOSLPSO 算法在27 個測試問題中的25（1）個測試問題上表現更好（相似）。 與IMMOEA 相比，LMOSLPSO 算法在27 個測試問題中的21（3）個測試問題上表現更好（相似）。 與MMOPSO 相比， LMOSLPSO 算法在27個測試問題中的22（5）個測試問題上表現更好（相似）。 與LMOCSO 相比， LMOSLPSO 算法在27 個測試問題中的11（10）個測試問題上表現更好（相似）。 在3 維多目標問題中，對比算法LMEA、IMMOEA 和MMOPSO 的對比性能有所下降，對比算法LMOCSO 的對比性能有所提高，但LMOCSO 的性能還是比本文提出的LMOSLPSO 算法的性能差。

表2 不同算法在3 維LSMOP1～LSMOP9 上得到的IGD 平均值和標準差比較Tab. 2 Comparison of IGD mean and standard deviation obtained by different algorithms on 3－d lsmop1～lsmop9

圖4 和圖5 分別給出了所有對比多目標算法在2 維和3 維大規模多目標優化問題LSMOP4 上獲得的非支配解。 由圖中可以看出，對比算法LMEA、IMMOEA 和MMOPSO 獲得的非支配解均勻性和收斂性較差。 從圖4 可以看出，在2 維多目標優化問題LSMOP4 上，對比算法LMOCSO 和提出算法LMOSLPSO 均勻性和多樣性都較好；從圖5 可以看出，在3 維多目標優化問題LSMOP4 上，本文算法LMOSLPSO 在均勻性上比算法LMOCSO 更佳。

圖4 不同算法在雙目標LSMOP4 函數上獲得的非支配解Fig. 4 The non－dominated solution obtained by different algorithms on the bi－objective LSMOP4 function

綜上所述，從表1、表2 以及圖4、圖5 可以得出，本文提出的LMOSLPSO 算法比其它算法在求解大規模多目標優化問題上有較好的性能表現。

4 結束語

本文基于社會學習粒子群算法思想，提出了一種用于求解大規模多目標優化問題的多目標粒子群算法（LMOSLPSO）。 該算法利用轉換的密度估計策略求解每個粒子的適應值，然后基于適應值排序設計了一種有效的粒子速度更新方法。 該方法能有效引導種群進化，使所提出的LMOSLPSO 算法獲得了綜合性能較優的優化結果。 實驗結果表明，LMOSLPSO 算法比對其他算法有較好的性能表現，該算法是處理大規模優化問題的有效算法。