基于種群分區的多策略自適應多目標粒子群算法

張偉 黃衛民

在多數實際問題和工程應用中,決策者需要同時使多個目標在決策空間內盡可能得到最佳優化,即多目標優化問題(Multi-objective optimization problems,MOPs)[1].在MOPs 中,使算法快速有效地收斂在Pareto 最優解集中并使得到的非支配解在Pareto 前沿中保持均勻分布是衡量多目標優化算法性能的重要指標之一,即算法的收斂性和多樣性.過度強調算法的收斂性會導致粒子聚集,陷入局部最優;過度增強算法多樣性會導致算法收斂速度慢,影響最終非支配解集的收斂性[2].因此,平衡算法的收斂性和多樣性是研究MOPs 的重要課題之一[3?5].

粒子群優化算法因為易于實現和計算效率高等特點,在單目標優化問題上得到廣泛應用.當粒子群優化應用于多目標優化問題時,即多目標粒子群優化(Multi-objective particle swarm optimization,MOPSO).由于MOPs 中沒有真正意義上的最優解,所以MOPSO 算法的全局最優粒子gbest和個體最優粒子pbst需要采取特定的策略進行選取,并且由于MOPSO 算法較快的收斂速度,在算法學習過程中,易使所得到的非支配解集迅速喪失多樣性[6].

為解決上述問題,學者們相繼提出了一些改進的MOPSO 算法.Coello等[7]提出一種基于自適應網格的多目標粒子群優化算法,采用自適應網格技術對外部存檔進行維護,指導粒子更新,并對粒子以及粒子的飛行區域實施變異.雖然算法相比于傳統多目標進化算法在MOPs 問題上表現出一定優勢,但在解決多局部前沿的復雜MOPs 問題時存在困難,且非支配解多樣性較差.Raquel等[8]提出一種基于擁擠距離的MOPSO (An effective use of crowding distance in MOPSO,cdMOPSO)算法,采用目標空間的擁擠距離評估非支配解的密集程度,并據此來選取全局最優粒子和保持外部存檔中解的分布性,但算法仍存在收斂性不足的問題.為解決這個問題,Yen等[9]提出一種動態多子群的多目標粒子群優化算法,算法將種群分為多個子群,通過動態調整子群大小從種群角度平衡算法的探索能力和開發能力,實驗結果表明算法性能得到改善.

與上述通過支配關系確定搜索機制的MOPSO 算法不同,Peng等[10]基于分解的多目標進化算法 (Multi-objective evolutionary algorithm based on decomposition,MOEA/D) 的分解框架,將MOPs 分解為多個單目標優化問題,用粒子群優化的搜索方法替代遺傳算子,從而提出一種MOPSO算法,雖然其維護了一個外部存檔存儲各單目標優化問題的全局最優粒子,但并未對粒子群優化的搜索機制進行優化,算法綜合性能不足.Martinez等[11]提出一種多目標粒子群優化器,算法提出了一種重新初始化策略來保持群的多樣性,當粒子存在超過一定代數時將會重新初始化,以此來提高種群多樣性和避免陷入局部極值,但由于用分解替換了占優關系,算法在求解一些復雜MOPs 時,不能覆蓋整個Pareto前沿.為解決這個問題,Dai等[12]提出一種基于分解的多目標粒子群優化算法,根據一系列預先定義的方向向量將整個目標空間分解為一系列子空間,并讓每個子空間都有至少一個解來維護解集的多樣性,進一步提升MOPSO 算法解決MOPs的能力.

學者們還提出了其他改進方法提升MOPSO算法的性能.Hu等[13]提出一種基于平行單元坐標系的自適應多目標粒子群優化(Adaptive MOPSO based on parallel cell coordinate,pccsAMOPSO)算法,將目標空間的Pareto 前沿變換為平行單元坐標形式的二維網格,采用種群的熵作為反饋信息,設計具有自適應調節探索和開發過程的進化策略,使算法的收斂性和多樣性都得到了提升.Kumar等[14]提出一種自學習的多目標粒子群優化算法,在粒子速度和位置更新上采用4種運算方式,不同方式對應不同的學習來源,獨立提高每個粒子搜索的有效性.但目前多數改進的MOPSO 算法僅依靠一種搜索策略更新粒子的位置和速度,沒有考慮不同性能粒子的搜索情況,在求解復雜多目標問題時,算法收斂性和多樣性不足.

為解決上述問題,進一步提升MOPSO 算法的性能,本文提出一種基于種群分區的多策略自適應多目標粒子群優化(Multi-strategy adaptive multiobjective particle swarm optimization based on swarm partition,spmsAMOPSO)算法.對MOPSO 算法的改進在于: 1)提出一種基于種群分區的多策略全局最優粒子選取方法,并基于種群分區思想,提出一種多策略的變異方法,提升粒子探索和開發能力;2)為提升個體最優粒子選取的可靠性,提出一種帶有記憶區間的個體最優粒子選取方法;3)根據算法環境,自適應調整粒子探索和開發過程,并采用雙性能測度的融合指標維護外部存檔,平衡算法的收斂性和多樣性.實驗結果表明,相比一些其他多目標優化算法,本文算法在收斂性和多樣性上具有一定優勢.

1 多目標優化問題和粒子群優化算法

1.1 多目標優化問題

多目標優化問題的數學模型可描述為:

則稱x′為Pareto 最優解.

3) Pareto 最優解集: 對給定的MOPs,Pareto最優解集定義為:

4) Pareto 前沿: 由P?的定義,Pareto 前沿(Pareto front,PF)可定義為:

1.2 標準粒子群算法

粒子群算法是由Kennedy等[15]提出的一種基于種群搜索的進化計算技術.種群中粒子i的速度vi和位置xi的更新方法分別為:

2 基于種群分區的多策略自適應多目標粒子群優化算法

MOPSO 算法因其特殊的搜索機制和快速的收斂速度,需要對算法的參數調整、全局最優粒子選取、個體最優粒子選取、外部存檔維護以及粒子變異操作等部分制定策略以引導粒子搜索[7].本文在全局最優粒子選取和變異操作部分,提出一種基于種群分區的多策略改進方法,并提出一種帶有記憶區間的個體最優粒子選取方法,結合自適應參數調整以及使用融合指標的外部存檔維護策略,進一步提升MOPSO 算法性能.本文spmsAMOPSO 算法的整體結構如圖1 所示,通過算法的參數調整、最優粒子選取、變異以及外部存檔維護等部分之間的協同,共同指導粒子尋優過程,提升算法綜合性能.

圖1 spmsAMOPSO 算法整體框圖Fig.1 Frame of spmsAMOPSO algorithm

2.1 自適應調整慣性權重和學習因子

對于MOPSO 算法,由于算法迭代過程中,其環境是實時變化的,為提升粒子探索和開發能力,本文根據算法環境變化調整慣性權重wp以及學習因子c1和c2,達到算法參數精細化調控的目的.

當算法搜索到的非支配解需要加入外部存檔時,計算其對外部存檔中解的支配程度,得到粒子的收斂性貢獻[16]:

式中,xn,i為算法尋優所得到的第i個非劣解;xr為外部存檔中存儲的非支配解;rep為算法外部存檔;ρ(xn,i,xr)為xn,i對xr的支配程度,計算方法如下:

式中,M為目標個數;fj,max和fj,min分別為外部存檔中非支配解在第j個目標上的最大值和最小值.若t時刻算法搜索到np個非支配解,則算法的環境檢測參數Ap定義為:

粒子對外部檔案的收斂性貢獻反映算法當前的收斂狀態,當Ap較大時,種群處于探索階段,應保持其全局搜索能力,隨著Ap逐漸減小,種群逐漸達到收斂,應加強局部搜索,當Ap趨于0 時,表明種群達到收斂穩定狀態.

由文獻[17]可知,較小的慣性權重wp和學習因子c1以及較大的學習因子c2有利于算法收斂,較大的wp和c1以及較小的c2有利于增強算法多樣性.為避免參數調整影響算法搜索連貫性,本文采用增量式參數調節方法:

2.2 基于種群分區的多策略全局最優粒子選取

全局最優粒子 (gbest) 選取是影響MOPSO 算法收斂性和多樣性的重要問題.本文采用不同的評價指標分別選取促進算法收斂的全局最優粒子(cgbest)和增強算法多樣性全局最優粒子 (d-gbest),并根據粒子性能將種群劃分為多個區域,對不同區域粒子制定不同的gbest選取策略.

2.2.1 c-gbest和d-gbest 的選取方法

為保證算法的收斂性,在算法尋優過程中選取外部存檔中收斂程度最好的粒子做為算法的cgbest.

本文采用粒子的平均排名和全局損害作為粒子的收斂性評價指標.

粒子平均排名(Average ranking,AR)的計算方法為:

式中,rm(xi) 為粒子i在第m個目標變量上的排名;M為目標個數.

粒子全局損害(Global detriment,GD)的計算方法如下:

式中,fm(xi) 為粒子i在第m個目標上的適應度值;GD(xi) 表示粒子i比其他粒子在目標上的劣勢.

由于通過AR 指標選取最優粒子時容易使粒子聚集在Pareto 前沿的邊緣,而GD 指標容易排除Pareto 前沿中的端點粒子[6].將上述兩個指標結合,改善評價方式缺陷:

式中,η1和η2為區間[0,1]之間的常數,用于確定指標AR和GD 的權重,其取值分別為:η1=0.4、η2=0.6,具體討論分析見第3.2.1 節.Fusion ranking (FR)指標有利于目標解的序列和個體之間的相對信息結合,從而更全面地評估解空間內個體的收斂程度.由式(12)～(14)計算外部存檔中各粒子的融合排序FR 指標,選取FR 指標最小的粒子作為算法的c-gbest.

為保證非支配解集的多樣性,在算法尋優過程中應引導粒子向外部存檔中非支配解較為稀疏的區域飛行,本文采用粒子的擁擠距離作為算法多樣性全局最優粒子(d-gbest)的選取標準.

粒子i與粒子j之間的歐氏距離為:

為避免個別極端粒子影響粒子密度估計,本文采用局部距離作為粒子的密度評價指標,取粒子i距離最近的S個粒子之間距離的平均值作為粒子i的擁擠距離,即:

局部擁擠距離(Locality crowding distance,LD)為反映粒子分布情況的指標,粒子的LD 指標越大,表明粒子分布越稀疏.根據式(15)～(17)計算外部存檔中各粒子的LD 指標,選取LD 指標最大的粒子作為算法的d-gbest.

2.2.2 種群分區及各區域粒子的 gbest 選取方法

為增強粒子探索和開發能力,并根據算法環境自適應調整種群探索和開發過程,擴大粒子搜索區域的同時保持算法收斂性和多樣性的平衡.本文通過粒子收斂程度將種群中粒子劃分為3 個區域,根據不同區域粒子的特征,提出一種多策略的gbest選取方法.

根據種群中各粒子的FR 指標大小,得到每個粒子基于指標FR 的種群內排名:

根據每個粒子的群內排名FRs,確定各粒子的所屬區域:

式中,α和β均為正常數,通過確定α和β的值,將種群劃分為3 個區域,分區參數選取分別為:α=0.2N,β=0.8N,N為種群粒子個數,分區參數的取值對算法影響分析見第3.2.2 節.圖2 給出了種群各區域粒子的劃分情況.

圖2 種群中各粒子所屬區域Fig.2 Location of each particles in the population

根據各區域內粒子的不同特征,制定一種多策略的gbest選取方案:

1)對于I 區粒子,其在種群中具有較好的收斂性,為保持算法搜索到非支配解的多樣性,使I 區粒子選取d-gbest作為全局最優粒子指導其飛行.

2)對于II 區粒子,為平衡算法的收斂性和多樣性,使種群能夠探索更多區域,使II 區粒子根據算法環境進行全局最優粒子的選取,由第2.1 節中的粒子收斂貢獻度對算法當前環境進行估計,根據算法環境確定粒子選取c-gbest或d-gbest作為gbest的概率:

由式(20)使II 區粒子能夠根據算法當前環境進行自適應探索和開發.當Ap較大時,為保證算法收斂性,使粒子有較大概率選取c-gbest作為gbest指導其飛行;當Ap逐漸減小時,為增強算法的多樣性,應使粒子有較大概率選取d-gbest作為gbest.

3)對于III 區粒子,由于其在種群中性能較差,對種群中的其他粒子的飛行沒有太大貢獻,為提升粒子的開發能力,保證算法收斂性,使III 區粒子選取c-gbest作為全局最佳粒子指導其飛行.

通過上述多策略的gbest選取方法,使算法能夠根據不同區域的粒子性能和算法環境,選取c-gbest或d-gbest作為全局最優粒子,有效提升算法的收斂性和多樣性,增強粒子探索和開發能力.

2.3 基于種群分區的多策略高斯變異

由于MOPSO 算法具有快速的收斂過程,算法易發生早熟收斂,過早結束搜索過程,陷入局部最優.為解決這個問題,在粒子位置更新時,對部分粒子加入擾動,使算法跳出局部最優,擴大粒子搜索區域[19].基于種群分區,針對不同區域粒子的性能,提出一種多策略的變異方法:

1)若粒子i位于I 區,表明粒子i距離真實Pareto前沿較近,為避免種群產生退化,保留種群中的精英個體,粒子i不進行變異操作;

2) 若粒子i位于II 區,則其具有較好的性能,可以通過較少的迭代次數飛行至真實Pareto 前沿附近;若δ

3)若粒子i位于III 區,則粒子性能較差,距離真實Pareto 前沿較遠,優先考慮增強粒子的收斂性;若δ <(1?pm),將粒子i向c-gbest方向進行變異:

式中,δ為區間[0,1]之間的隨機數;d為區間[1,D] 之間的隨機整數,D為問題的決策空間維數;xmax,d和xmin,d分別為d維決策空間上的最大值和最小值;pm為粒子變異因子,取值為pm=0.25+(t/2T);σ為高斯函數方差,根據算法迭代次數更新:σ=exp(?(t/T)); 方差σ控制變異范圍,隨迭代次數增加,使粒子的變異范圍越來越小,保證算法迭代后期粒子的開發能力.

上述變異方法具有以下2 個優點: 1)算法能夠根據粒子位置進行不同程度的變異,使算法跳出局部最優的同時避免對粒子搜索產生太大干擾,保持算法搜索連貫性.2)根據不同區域粒子的性能差異,制定不同的變異策略,擴大粒子的搜索區域,增強粒子的探索和開發能力.

2.4 帶有記憶區間的個體最優粒子選取方法

合理選擇個體最優粒子(pbest)有助于提高種群對局部空間的開發能力.多數MOPSO 算法均采用一個外部庫來存儲粒子的pbest,當粒子位置xi受pbesti支配時,pbesti保持,當xi支配pbesti時,將pbesti更新為粒子當前位置xi,兩者無支配關系時,采用隨機方法進行選取.這種方法雖然計算簡單,但當xi與pbesti無支配關系時,選取的pbest不能有效指導粒子的飛行方向,易導致算法停滯[20].

基于上述問題,本文提出一種帶有記憶區間的pbest選取方法,在算法迭代過程中,每個粒子具有一個外部存儲庫,存儲粒子最近幾次迭代所經過的位置,形成記憶區間:

根據第2.2.1 節中粒子的融合排序方法,計算記憶區間中各位置的FR 指標,選取FR 指標最小的位置作為粒子i下一次迭代時的pbest:

當記憶區間飽和時,需要制定策略對記憶區間進行維護,圖3 以2 個粒子為例,給出了粒子的記憶區間更新過程.

圖3 粒子記憶區間更新過程Fig.3 Update process of particle memory interval

由圖3 可以看出,粒子記憶區間更新存在兩種情況:1)若存儲位置達到記憶區間最大值,則將記憶中最早一次迭代時的位置遺忘,即.2)若為最優的粒子位置,則按時間順序向后,將相鄰的一個位置遺忘.即:

2.5 基于雙性能測度融合指標的外部存檔維護

算法在迭代過程中將非支配解存入外部存檔中,隨著算法迭代次數增加,非支配解個數隨之增加,當達到外部存檔的最大容量時,需要對外部存檔進行維護.多數MOPSO 算法在進行外部存檔維護時,采用粒子的分布性能指標作為判斷粒子性能的標準,將密度最大的粒子進行刪除.這種方法雖然能夠保持外部檔案中非支配解的多樣性,但可能會刪除外部存檔中收斂性較好的非支配解,導致種群產生退化,影響粒子開發能力[21].因此,在進行外部存檔維護時不應將粒子密度作為外部存檔維護的唯一性能指標,還應考慮到粒子的收斂性.

根據粒子的收斂性指標FR和粒子的分布性指標LD,采用融合的評價指標判斷外部存檔中粒子的綜合性能:

由式(12)和式(14)可知,粒子FR 指標越小,粒子收斂性越好,LD 指標越大,粒子分布性越好.由式(26) 可以看出,粒子的綜合排序(Comprehensive ranking,CR)指標不僅能夠反映粒子的收斂程度而且包含了粒子的分布情況,粒子的CR 指標越小,表明粒子的綜合性能越好.因此,當算法搜索到的非支配解個數超過外部存檔的最大容量時,將外部存檔中CR 指標較大的粒子刪除.

3 實驗分析

3.1 性能評價指標

為有效評價算法的收斂性和多樣性,本文采用反世代距離(Inverted generational distance,IGD)、間隔指標(Spacing,SP)、出錯比率(Error ratio,ER)和計算時間,分別對算法性能進行評價.

1) IGD: IGD 是度量真實Pareto 前沿與算法獲得的近似Pareto 前沿之間的距離指標[13].IGD 值越小,表明算法獲得的近似Pareto 前沿的收斂性和多樣性越好,越接近真實Pareto 前沿,其計算方法為:

式中,PF為多目標算法所求得的Pareto 前沿;PF?為真實Pareto 前沿的一組采樣點;n為Pareto 前沿中非支配解個數.

2) SP: 用于度量每個解到其他解最小距離的標準差,是衡量一個范圍內鄰近解差異的重要指標[22].SP 值越小,表明解集分布越均勻,其計算方法為:

式中,di為第i個非支配解與其他解之間最小的歐氏距離;為所有di的平均值.

3) ER: 用來說明最優解的百分比[7].ER 越小,所得非支配解在真實Pareto 前沿中占比越高,其計算方法為:

式中,ei取值方法為: 若第i個非支配解在真實Pareto前沿中,則ei=0,否則ei=1.

4)計算時間t: 計算時間是多目標優化算法的重要性能評價指標之一[23],相同實驗平臺下算法的計算時間能夠表征各算法的計算復雜度.

3.2 參數取值和分析

本節通過本文算法在不同參數取值方案下對ZDT3和DTLZ2 測試函數的實驗,說明參數的取值方法.實驗基本參數設置:種群粒子數量為100,外部存檔最大容量為200,粒子記憶區間長度為u=5,粒子擁擠距離中S=4,變異策略中高斯函數的方差初始值σ0=0.8.

3.2.1 融合收斂性指標 FR 的權重 η1和η2

由式(14)所描述的融合收斂性指標FR的權重η1和η2的取值對粒子的收斂性評價產生影響,進而影響算法性能,合適的η1和η2取值能夠有效對粒子進行分區,提升算法開發能力.本節通過多種參數取值下的實驗,說明η1和η2的取值原因.選取7種參數取值方案:

分別對兩目標問題ZDT3和三目標問題DTLZ2進行實驗,測試ZDT3 問題時,每20 次迭代進行一次IGD 指標評價,測試DTLZ2問題時,每30 次迭代進行一次IGD 指標評價,實驗結果如圖4 所示.

圖4 η1和η2 的不同取值方案下IGD 指標變化Fig.4 IGD metric changes of differentη1 and η2 value schemes

由圖4 可以看出,在7種參數取值方案中,算法在Case 3～Case 5 的取值方案下,性能較好,即η1和η2的取值大小接近時,算法能夠獲得良好的性能.這是由于粒子平均排名AR和粒子全局損害GD 的計算方法造成的.粒子收斂性融合指標FR由AR和GD 的加權和構成,種群中粒子個數為100 時,粒子的AR 指標略大于GD 指標,當η1的取值遠大于η2時,GD指標在粒子收斂性評價中幾乎被忽略,即FR ≈AR.粒子的收斂性評價將由AR 主導,導致粒子收斂性評價不全面,算法性能下降,反之亦然.為保證本文算法性能,本文中η1和η2的取值分別為0.4和0.6.

3.2.2 分區參數 α 和β

第2.2.2 節通過分區參數α和β將種群劃分為3 個區域,I 區和III 區最優粒子的選取可以保證算法基本的收斂性和多樣性,II 區粒子能夠根據算法當前環境進行自適應最優粒子的選取,提升粒子的探索和開發能力.因此,α和β的取值將影響算法的收斂速度和綜合性能.圖5 給出本文算法解決ZDT3和DTLZ2 問題時,3種α和β取值方案下IGD 指標下降趨勢,取值方案分別為: Case 1:α=0.1N,β=0.9N;Case 2:α=0.2N,β=0.8N;Case 3:α=0.3N,β=0.7N.式中N為粒子總個數.

由圖5 可以看出,當α和β的取值使II 區粒子數量較多時,算法收斂速度較慢,當II 區粒子數量較少時算法收斂速度較快.由ZDT3 測試問題的Case 3 可以看出,當II 區粒子數量較少時,算法的IGD 指標下降陡峭,并且算法迭代過程中IGD 指標下降無明顯波動,表明算法在搜索過程中由于II區粒子數量不足,導致粒子的探索能力不足;由DTLZ2 測試問題可以看出,隨著II 區粒子的增多,算法獲得的最終IGD 指標逐漸減小,算法的綜合性能逐漸提升.

圖5 不同分區參數取值方案下IGD 指標變化Fig.5 IGD metric changes of different partition parameter value schemes

為避免算法收斂速度過快,保證種群中粒子的探索和開發能力,應使II 區粒子保持較高數量.通過大量實驗驗證,α和β的取值使I 區、II 區和III區粒子數分別約為粒子總數的1/5、3/5和1/5,能夠使算法保持合適的收斂速度并獲得良好的綜合性能.

3.3 實驗結果及比較分析

為驗證本文算法的有效性,分別對兩目標問題(ZDT 系列函數)和三目標問題(DTLZ 系列函數)進行實驗測試,并設置8種多目標算法進行對比實驗,對比算法包括: 基于聚類的多目標粒子群優化算法(MOPSO based on clustering,clusterMOPSO)[23]、cdMOPSO[8]、pccsAMOPSO[13]、非支配排序遺傳算法(Nondominated sorting genetic algorithm II,NSGA-II)[24]、增強Pareto 進化算法(Strength Pareto evolutionary algorithm,SPEA2)[25]、MOEA/D[26]、基于競爭機制的多目標粒子群優化算法(Competitive mechanism based MOPSO,CMOPSO)[27]和嵌入基于分解歸檔方法的SPEA2 算法(Decomposition-based archiving approach embedded in SPEA2,SPEA2+DAA)[28]算法.各算法對測試問題的最大評價次數均為1 000 次,實驗結果均為各算法在同一測試問題上獨立運行30 次的統計結果.算法運行環境均為Inter Core i5-5257U 2.70 GHz CPU,8 GB 內存,Windows10 操作系統,Matlab 2016b.各對比算法參數設置均與原文獻保持一致.

表1～6 分別給出了包括本文spmsAMOPSO 算法在內的多種多目標優化算法在12 個測試問題上的IGD、SP 以及ER 性能指標的平均值和標準差.表7 給出了幾種算法計算所需的時間,其中粗體數據為各評價指標下所得的最優結果.

表7 不同算法對多目標測試問題的運行時間 (s)Table 7 Computational time of different algorithms for multi-objective test problems (s)

由表1～2 可以看出,本文算法在12 個測試問題的結果中,獲得10 次IGD 指標的最優平均值和6 次標準差最優值.雖然在DTLZ4 測試問題中本文算法的IGD 指標略遜于pccsAMOPSO 算法(其結果為最優值,本文算法結果為次優值),但優于其中5種多目標算法.這是由于本文算法在進行最優粒子選取時采用分區策略,將部分性能相似的粒子劃分為一個區域,對一個區域的粒子實現一種搜索引導策略,而pccsAMOPSO 算法在進行全局最優粒子選取時,對種群中粒子逐個進行選取,而本文算法根據粒子當前性能進行分區所獲得的分區較為模糊,在對復雜多目標問題進行優化時,綜合性能表現稍顯不足.但本文算法通過種群分區策略,提出一種新的變異方法,并結合帶有記憶區間的個體最優粒子選取和融合指標的外部存檔維護等方法,使本文算法最終仍具有良好的性能.在DTLZ5測試問題中本文算法性能相較于CMOPSO 算法和cdMOPSO 算法具有一些劣勢(綜合性能上CMOPSO 算法最優,cdMOPSO 算法次優),但優于其余6種多目標優化算法.對其余測試問題中,本文算法均取得IGD 指標的最優值,各算法在12個測試問題中的IGD 最優值個數表明,本文算法在綜合性能上優于其他8種多目標優化算法.

表1 本文算法與其他多目標粒子群算法的IGD 評價指標對比Table 1 Results of IGD metric of the proposed algorithm and MOPSOs

表2 本文算法與其他多目標進化算法的IGD 評價指標對比Table 2 Results of IGD metric of the proposed algorithm and multi-objective genetic algorithms

由表3和表4 可以得到,本文算法在12 個測試問題的結果中,獲得11 次SP 指標的最優平均值和7 次標準差最優值.在DTLZ5 測試問題中,本文算法的SP 指標略遜于cdMOPSO和NSGA-II 算法(cdMOPSO和NSGA-II 算法分別獲得最優值和次優值),但優于pccsAMOPSO、clusterMOPSO、MOEA/D和SPEA2 等4種多目標優化算法,在其余測試問題中,本文算法的SP 指標均取得最優值.實驗結果表明,相比于其余多目標優化算法,本文算法獲得的Pareto 前沿中非支配解分布均勻,算法具有良好的多樣性.

表3 本文算法與其他多目標粒子群算法的SP 評價指標對比Table 3 Results of SP metric of the proposed algorithm and MOPSOs

表4 本文算法與其他多目標進化算法的SP 評價指標對比Table 4 Results of SP metric of the proposed algorithm and multi-objective genetic algorithms

SP 指標的實驗結果表明,本文算法獲得的非支配解集具有良好的多樣性,這是由于本文算法通過對算法環境的檢查自適應地調整了算法慣性權重和學習因子,并采用種群分區策略,對種群中收斂性較好的粒子制定特殊的搜索引導策略和變異方法,提升粒子的探索效率,有效增強算法多樣性.

由表5～6 可以看出,在12 個測試問題的結果中,本文算法共獲得8 次ER 評價指標的最優值,在求解ZDT4、DTLZ1和DTLZ4 測試問題時取得次優值(MOEA/D、clusterMOPSO和SPEA2 算法分別取得最優值).在DTLZ6 測試問題中,本文算法的ER 指標略遜于clusterMOPSO和NSGAII 算法,這是由于本文算法在最優粒子選取,變異以及外部存檔維護等方面均采用不同的策略對算法的收斂性和多樣性進行平衡,即犧牲了粒子的部分局部開發能力換取粒子的全局開發能力,使算法取得相較于其他算法更好的多樣性,因此在部分復雜多目標優化問題中收斂性略顯不足.但相比于cdMOPSO 等其余4種多目標優化算法,本文算法在收斂性上仍然具有一定優勢.綜合各算法的ER 評價指標實驗結果,本文spmsAMOPSO 算法獲得的非支配解集能夠較好地逼近真實Pareto 前沿,相比于其他幾種多目標優化算法,具有良好的收斂性.

表5 本文算法與其他多目標粒子群算法的ER 評價指標對比Table 5 Results of ER metric of the proposed algorithm and MOPSOs

表6 本文算法與其他多目標進化算法的ER 評價指標對比Table 6 Results of ER metric of the proposed algorithm and multi-objective genetic algorithms

ER 指標的實驗結果表明,本文算法相較于其他幾種多目標優化算法具有更好的收斂性,這是由于本文算法通過在最優粒子選取和變異中加入種群分區,對種群中性能較差的粒子實行特殊的尋優策略,增強劣勢粒子的利用率,有效提升算法收斂性;在個體最優粒子選取中,加入粒子的記憶機制,提升個體最優粒子選取的可靠性,增強個體最優粒子對粒子收斂過程的指導作用.

由表7 可以看出,本文算法在求解多數測試問題時具均有較好的實時性,僅在ZDT1和DTLZ2問題時劣于cdMOPSO 算法,在DTLZ4 問題時略遜于pccsAMOPSO.雖然本文算法采用了分區機制和粒子記憶區間,增加了算法的計算復雜度,但有效的種群劃分使粒子的全局最優粒子選取以及變異更有效率,并且個體最優粒子的可靠選取使粒子能夠更快收斂至Pareto 前沿附近,使算法運行時間相較其他同類型優化算法更短.

為詳細說明各算法所得非支配解集的收斂性和多樣性,圖6～8 分別給出了6種算法在求解ZDT3、DTLZ2和DTLZ7 測試問題時的非支配解集和真實Pareto 前沿.由實驗結果可以看出,在三種測試問題中,cdMOPSO、pccsAMOPSO、NSGA-II、SPEA2和MOEA/D 等多目標優化算法均不同程度的出現了收斂性和多樣性不足的問題.同樣是在DTLZ2 測試問題中,cdMOPSO、NSGA-II和SPEA2 算法均表現出收斂性不足的缺點,雖然pccs-AMOPSO和MOEA/D 算法具有較好的收斂性,但算法多樣性較差,而本文spmsAMOPSO 算法得到的Pareto 前沿中,非支配解不僅較好地收斂在真實Pareto 前沿附近,而且具有良好的分布性,算法在收斂性和多樣性上均有較好表現.

圖6 不同多目標優化算法對ZDT3 函數的Pareto 前沿Fig.6 Pareto front of ZDT3 function of different multi-objective optimization algorithms

圖8 不同多目標優化算法對DTLZ7 函數的Pareto 前沿Fig.8 Pareto front of DTLZ7 function of different multi-objective optimization algorithms

為直觀展示各算法多次實驗數據的分布情況,圖9 分別給出了7種多目標優化算法在測試ZDT3、DTLZ2和DTLZ7 問題時IGD、SP 以及ER 指標的箱形圖,其中橫軸坐標1～7 分別代表spmsAMOPSO、clusterMOPSO、cdMOPSO、pccsAMOPSO、NSGA-II、SPEA2和MOEA/D 算法.由圖9可以看出,本文算法在求解ZDT3、DTLZ2和DTLZ7測試問題時,IGD、SP 以及ER 指標相較于其他6種多目標優化算法均具有較大優勢,并且本文算法的多次測試結果數據無明顯偏態,出現的異常數據較少,各項性能指標的中值和最大偏差均優于其他多目標優化算法.實驗結果表明,本文算法不僅具有良好的綜合性能,并且測試結果穩定.

圖9 7種多目標優化算法在測試ZDT3、DTLZ2和DTLZ7 問題時IGD、SP 以及ER 指標的箱形圖Fig.9 Box plots of IGD,SP and ER metric on ZDT3,DTLZ2 and DTLZ7 problems of multi-objective optimization algorithms

綜合實驗結果表明,本文算法得到的非支配解集能夠有效地收斂在真實Pareto 前沿,并具有良好的分布性.這是由于本文算法通過對種群進行分區,制定多策略的搜索引導方案,有效平衡了算法的收斂性和多樣性,提升了粒子的探索和開發能力及尋優效率,并且使算法具有較好綜合性能的同時降低了算法的計算復雜度.

4 結束語

本文提出了一種基于種群分區的多策略自適應多目標粒子群優化算法.算法通過基于種群分區的多策略改進,確定算法的全局最優粒子選取和變異方法,將粒子性能與算法尋優過程結合,提升種群中各個粒子的搜索效率;提出帶有記憶區間的個體最優粒子選取方法,提升個體最優粒子選取的可靠性,避免因個體最優粒子不能有效指導粒子的飛行,使算法停滯,陷入局部最優;采用雙性能測度指標的外部存檔維護策略,能夠有效保持外部存檔中非支配解良好的分布性,避免進行外部存檔維護時,刪除收斂性較好的粒子,導致種群產生退化,影響粒子開發能力.為驗證算法有效性,采用ZDT和DTLZ系列測試函數進行仿真實驗,并與其他幾種多目標優化算法進行對比,通過各算法對同一測試問題的IGD、SP、ER 以及計算時間等評價指標的實驗結果,分別說明本文算法的收斂性,多樣性和實時性.綜合實驗結果表明,本文算法具有較顯著的收斂性和多樣性優勢,且具有良好的實時性.