基于種群分區(qū)的多策略自適應(yīng)多目標(biāo)粒子群算法

張偉 黃衛(wèi)民

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

粒子群優(yōu)化算法因?yàn)橐子趯?shí)現(xiàn)和計(jì)算效率高等特點(diǎn),在單目標(biāo)優(yōu)化問題上得到廣泛應(yīng)用.當(dāng)粒子群優(yōu)化應(yīng)用于多目標(biāo)優(yōu)化問題時(shí),即多目標(biāo)粒子群優(yōu)化(Multi-objective particle swarm optimization,MOPSO).由于MOPs 中沒有真正意義上的最優(yōu)解,所以MOPSO 算法的全局最優(yōu)粒子gbest和個(gè)體最優(yōu)粒子pbst需要采取特定的策略進(jìn)行選取,并且由于MOPSO 算法較快的收斂速度,在算法學(xué)習(xí)過(guò)程中,易使所得到的非支配解集迅速喪失多樣性[6].

為解決上述問題,學(xué)者們相繼提出了一些改進(jìn)的MOPSO 算法.Coello等[7]提出一種基于自適應(yīng)網(wǎng)格的多目標(biāo)粒子群優(yōu)化算法,采用自適應(yīng)網(wǎng)格技術(shù)對(duì)外部存檔進(jìn)行維護(hù),指導(dǎo)粒子更新,并對(duì)粒子以及粒子的飛行區(qū)域?qū)嵤┳儺?雖然算法相比于傳統(tǒng)多目標(biāo)進(jìn)化算法在MOPs 問題上表現(xiàn)出一定優(yōu)勢(shì),但在解決多局部前沿的復(fù)雜MOPs 問題時(shí)存在困難,且非支配解多樣性較差.Raquel等[8]提出一種基于擁擠距離的MOPSO (An effective use of crowding distance in MOPSO,cdMOPSO)算法,采用目標(biāo)空間的擁擠距離評(píng)估非支配解的密集程度,并據(jù)此來(lái)選取全局最優(yōu)粒子和保持外部存檔中解的分布性,但算法仍存在收斂性不足的問題.為解決這個(gè)問題,Yen等[9]提出一種動(dòng)態(tài)多子群的多目標(biāo)粒子群優(yōu)化算法,算法將種群分為多個(gè)子群,通過(guò)動(dòng)態(tài)調(diào)整子群大小從種群角度平衡算法的探索能力和開發(fā)能力,實(shí)驗(yàn)結(jié)果表明算法性能得到改善.

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

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

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

1 多目標(biāo)優(yōu)化問題和粒子群優(yōu)化算法

1.1 多目標(biāo)優(yōu)化問題

多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型可描述為:

則稱x′為Pareto 最優(yōu)解.

3) Pareto 最優(yōu)解集: 對(duì)給定的MOPs,Pareto最優(yōu)解集定義為:

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

1.2 標(biāo)準(zhǔn)粒子群算法

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

2 基于種群分區(qū)的多策略自適應(yīng)多目標(biāo)粒子群優(yōu)化算法

MOPSO 算法因其特殊的搜索機(jī)制和快速的收斂速度,需要對(duì)算法的參數(shù)調(diào)整、全局最優(yōu)粒子選取、個(gè)體最優(yōu)粒子選取、外部存檔維護(hù)以及粒子變異操作等部分制定策略以引導(dǎo)粒子搜索[7].本文在全局最優(yōu)粒子選取和變異操作部分,提出一種基于種群分區(qū)的多策略改進(jìn)方法,并提出一種帶有記憶區(qū)間的個(gè)體最優(yōu)粒子選取方法,結(jié)合自適應(yīng)參數(shù)調(diào)整以及使用融合指標(biāo)的外部存檔維護(hù)策略,進(jìn)一步提升MOPSO 算法性能.本文spmsAMOPSO 算法的整體結(jié)構(gòu)如圖1 所示,通過(guò)算法的參數(shù)調(diào)整、最優(yōu)粒子選取、變異以及外部存檔維護(hù)等部分之間的協(xié)同,共同指導(dǎo)粒子尋優(yōu)過(guò)程,提升算法綜合性能.

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

2.1 自適應(yīng)調(diào)整慣性權(quán)重和學(xué)習(xí)因子

對(duì)于MOPSO 算法,由于算法迭代過(guò)程中,其環(huán)境是實(shí)時(shí)變化的,為提升粒子探索和開發(fā)能力,本文根據(jù)算法環(huán)境變化調(diào)整慣性權(quán)重wp以及學(xué)習(xí)因子c1和c2,達(dá)到算法參數(shù)精細(xì)化調(diào)控的目的.

當(dāng)算法搜索到的非支配解需要加入外部存檔時(shí),計(jì)算其對(duì)外部存檔中解的支配程度,得到粒子的收斂性貢獻(xiàn)[16]:

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

式中,M為目標(biāo)個(gè)數(shù);fj,max和fj,min分別為外部存檔中非支配解在第j個(gè)目標(biāo)上的最大值和最小值.若t時(shí)刻算法搜索到np個(gè)非支配解,則算法的環(huán)境檢測(cè)參數(shù)Ap定義為:

粒子對(duì)外部檔案的收斂性貢獻(xiàn)反映算法當(dāng)前的收斂狀態(tài),當(dāng)Ap較大時(shí),種群處于探索階段,應(yīng)保持其全局搜索能力,隨著Ap逐漸減小,種群逐漸達(dá)到收斂,應(yīng)加強(qiáng)局部搜索,當(dāng)Ap趨于0 時(shí),表明種群達(dá)到收斂穩(wěn)定狀態(tài).

由文獻(xiàn)[17]可知,較小的慣性權(quán)重wp和學(xué)習(xí)因子c1以及較大的學(xué)習(xí)因子c2有利于算法收斂,較大的wp和c1以及較小的c2有利于增強(qiáng)算法多樣性.為避免參數(shù)調(diào)整影響算法搜索連貫性,本文采用增量式參數(shù)調(diào)節(jié)方法:

2.2 基于種群分區(qū)的多策略全局最優(yōu)粒子選取

全局最優(yōu)粒子 (gbest) 選取是影響MOPSO 算法收斂性和多樣性的重要問題.本文采用不同的評(píng)價(jià)指標(biāo)分別選取促進(jìn)算法收斂的全局最優(yōu)粒子(cgbest)和增強(qiáng)算法多樣性全局最優(yōu)粒子 (d-gbest),并根據(jù)粒子性能將種群劃分為多個(gè)區(qū)域,對(duì)不同區(qū)域粒子制定不同的gbest選取策略.

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

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

本文采用粒子的平均排名和全局損害作為粒子的收斂性評(píng)價(jià)指標(biāo).

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

式中,rm(xi) 為粒子i在第m個(gè)目標(biāo)變量上的排名;M為目標(biāo)個(gè)數(shù).

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

式中,fm(xi) 為粒子i在第m個(gè)目標(biāo)上的適應(yīng)度值;GD(xi) 表示粒子i比其他粒子在目標(biāo)上的劣勢(shì).

由于通過(guò)AR 指標(biāo)選取最優(yōu)粒子時(shí)容易使粒子聚集在Pareto 前沿的邊緣,而GD 指標(biāo)容易排除Pareto 前沿中的端點(diǎn)粒子[6].將上述兩個(gè)指標(biāo)結(jié)合,改善評(píng)價(jià)方式缺陷:

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

為保證非支配解集的多樣性,在算法尋優(yōu)過(guò)程中應(yīng)引導(dǎo)粒子向外部存檔中非支配解較為稀疏的區(qū)域飛行,本文采用粒子的擁擠距離作為算法多樣性全局最優(yōu)粒子(d-gbest)的選取標(biāo)準(zhǔn).

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

為避免個(gè)別極端粒子影響粒子密度估計(jì),本文采用局部距離作為粒子的密度評(píng)價(jià)指標(biāo),取粒子i距離最近的S個(gè)粒子之間距離的平均值作為粒子i的擁擠距離,即:

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

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

為增強(qiáng)粒子探索和開發(fā)能力,并根據(jù)算法環(huán)境自適應(yīng)調(diào)整種群探索和開發(fā)過(guò)程,擴(kuò)大粒子搜索區(qū)域的同時(shí)保持算法收斂性和多樣性的平衡.本文通過(guò)粒子收斂程度將種群中粒子劃分為3 個(gè)區(qū)域,根據(jù)不同區(qū)域粒子的特征,提出一種多策略的gbest選取方法.

根據(jù)種群中各粒子的FR 指標(biāo)大小,得到每個(gè)粒子基于指標(biāo)FR 的種群內(nèi)排名:

根據(jù)每個(gè)粒子的群內(nèi)排名FRs,確定各粒子的所屬區(qū)域:

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

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

根據(jù)各區(qū)域內(nèi)粒子的不同特征,制定一種多策略的gbest選取方案:

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

2)對(duì)于II 區(qū)粒子,為平衡算法的收斂性和多樣性,使種群能夠探索更多區(qū)域,使II 區(qū)粒子根據(jù)算法環(huán)境進(jìn)行全局最優(yōu)粒子的選取,由第2.1 節(jié)中的粒子收斂貢獻(xiàn)度對(duì)算法當(dāng)前環(huán)境進(jìn)行估計(jì),根據(jù)算法環(huán)境確定粒子選取c-gbest或d-gbest作為gbest的概率:

由式(20)使II 區(qū)粒子能夠根據(jù)算法當(dāng)前環(huán)境進(jìn)行自適應(yīng)探索和開發(fā).當(dāng)Ap較大時(shí),為保證算法收斂性,使粒子有較大概率選取c-gbest作為gbest指導(dǎo)其飛行;當(dāng)Ap逐漸減小時(shí),為增強(qiáng)算法的多樣性,應(yīng)使粒子有較大概率選取d-gbest作為gbest.

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

通過(guò)上述多策略的gbest選取方法,使算法能夠根據(jù)不同區(qū)域的粒子性能和算法環(huán)境,選取c-gbest或d-gbest作為全局最優(yōu)粒子,有效提升算法的收斂性和多樣性,增強(qiáng)粒子探索和開發(fā)能力.

2.3 基于種群分區(qū)的多策略高斯變異

由于MOPSO 算法具有快速的收斂過(guò)程,算法易發(fā)生早熟收斂,過(guò)早結(jié)束搜索過(guò)程,陷入局部最優(yōu).為解決這個(gè)問題,在粒子位置更新時(shí),對(duì)部分粒子加入擾動(dòng),使算法跳出局部最優(yōu),擴(kuò)大粒子搜索區(qū)域[19].基于種群分區(qū),針對(duì)不同區(qū)域粒子的性能,提出一種多策略的變異方法:

1)若粒子i位于I 區(qū),表明粒子i距離真實(shí)Pareto前沿較近,為避免種群產(chǎn)生退化,保留種群中的精英個(gè)體,粒子i不進(jìn)行變異操作;

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

3)若粒子i位于III 區(qū),則粒子性能較差,距離真實(shí)Pareto 前沿較遠(yuǎn),優(yōu)先考慮增強(qiáng)粒子的收斂性;若δ <(1?pm),將粒子i向c-gbest方向進(jìn)行變異:

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

上述變異方法具有以下2 個(gè)優(yōu)點(diǎn): 1)算法能夠根據(jù)粒子位置進(jìn)行不同程度的變異,使算法跳出局部最優(yōu)的同時(shí)避免對(duì)粒子搜索產(chǎn)生太大干擾,保持算法搜索連貫性.2)根據(jù)不同區(qū)域粒子的性能差異,制定不同的變異策略,擴(kuò)大粒子的搜索區(qū)域,增強(qiáng)粒子的探索和開發(fā)能力.

2.4 帶有記憶區(qū)間的個(gè)體最優(yōu)粒子選取方法

合理選擇個(gè)體最優(yōu)粒子(pbest)有助于提高種群對(duì)局部空間的開發(fā)能力.多數(shù)MOPSO 算法均采用一個(gè)外部庫(kù)來(lái)存儲(chǔ)粒子的pbest,當(dāng)粒子位置xi受pbesti支配時(shí),pbesti保持,當(dāng)xi支配pbesti時(shí),將pbesti更新為粒子當(dāng)前位置xi,兩者無(wú)支配關(guān)系時(shí),采用隨機(jī)方法進(jìn)行選取.這種方法雖然計(jì)算簡(jiǎn)單,但當(dāng)xi與pbesti無(wú)支配關(guān)系時(shí),選取的pbest不能有效指導(dǎo)粒子的飛行方向,易導(dǎo)致算法停滯[20].

基于上述問題,本文提出一種帶有記憶區(qū)間的pbest選取方法,在算法迭代過(guò)程中,每個(gè)粒子具有一個(gè)外部存儲(chǔ)庫(kù),存儲(chǔ)粒子最近幾次迭代所經(jīng)過(guò)的位置,形成記憶區(qū)間:

根據(jù)第2.2.1 節(jié)中粒子的融合排序方法,計(jì)算記憶區(qū)間中各位置的FR 指標(biāo),選取FR 指標(biāo)最小的位置作為粒子i下一次迭代時(shí)的pbest:

當(dāng)記憶區(qū)間飽和時(shí),需要制定策略對(duì)記憶區(qū)間進(jìn)行維護(hù),圖3 以2 個(gè)粒子為例,給出了粒子的記憶區(qū)間更新過(guò)程.

圖3 粒子記憶區(qū)間更新過(guò)程Fig.3 Update process of particle memory interval

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

2.5 基于雙性能測(cè)度融合指標(biāo)的外部存檔維護(hù)

算法在迭代過(guò)程中將非支配解存入外部存檔中,隨著算法迭代次數(shù)增加,非支配解個(gè)數(shù)隨之增加,當(dāng)達(dá)到外部存檔的最大容量時(shí),需要對(duì)外部存檔進(jìn)行維護(hù).多數(shù)MOPSO 算法在進(jìn)行外部存檔維護(hù)時(shí),采用粒子的分布性能指標(biāo)作為判斷粒子性能的標(biāo)準(zhǔn),將密度最大的粒子進(jìn)行刪除.這種方法雖然能夠保持外部檔案中非支配解的多樣性,但可能會(huì)刪除外部存檔中收斂性較好的非支配解,導(dǎo)致種群產(chǎn)生退化,影響粒子開發(fā)能力[21].因此,在進(jìn)行外部存檔維護(hù)時(shí)不應(yīng)將粒子密度作為外部存檔維護(hù)的唯一性能指標(biāo),還應(yīng)考慮到粒子的收斂性.

根據(jù)粒子的收斂性指標(biāo)FR和粒子的分布性指標(biāo)LD,采用融合的評(píng)價(jià)指標(biāo)判斷外部存檔中粒子的綜合性能:

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

3 實(shí)驗(yàn)分析

3.1 性能評(píng)價(jià)指標(biāo)

為有效評(píng)價(jià)算法的收斂性和多樣性,本文采用反世代距離(Inverted generational distance,IGD)、間隔指標(biāo)(Spacing,SP)、出錯(cuò)比率(Error ratio,ER)和計(jì)算時(shí)間,分別對(duì)算法性能進(jìn)行評(píng)價(jià).

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

式中,PF為多目標(biāo)算法所求得的Pareto 前沿;PF?為真實(shí)Pareto 前沿的一組采樣點(diǎn);n為Pareto 前沿中非支配解個(gè)數(shù).

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

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

3) ER: 用來(lái)說(shuō)明最優(yōu)解的百分比[7].ER 越小,所得非支配解在真實(shí)Pareto 前沿中占比越高,其計(jì)算方法為:

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

4)計(jì)算時(shí)間t: 計(jì)算時(shí)間是多目標(biāo)優(yōu)化算法的重要性能評(píng)價(jià)指標(biāo)之一[23],相同實(shí)驗(yàn)平臺(tái)下算法的計(jì)算時(shí)間能夠表征各算法的計(jì)算復(fù)雜度.

3.2 參數(shù)取值和分析

本節(jié)通過(guò)本文算法在不同參數(shù)取值方案下對(duì)ZDT3和DTLZ2 測(cè)試函數(shù)的實(shí)驗(yàn),說(shuō)明參數(shù)的取值方法.實(shí)驗(yàn)基本參數(shù)設(shè)置:種群粒子數(shù)量為100,外部存檔最大容量為200,粒子記憶區(qū)間長(zhǎng)度為u=5,粒子擁擠距離中S=4,變異策略中高斯函數(shù)的方差初始值σ0=0.8.

3.2.1 融合收斂性指標(biāo) FR 的權(quán)重 η1和η2

由式(14)所描述的融合收斂性指標(biāo)FR的權(quán)重η1和η2的取值對(duì)粒子的收斂性評(píng)價(jià)產(chǎn)生影響,進(jìn)而影響算法性能,合適的η1和η2取值能夠有效對(duì)粒子進(jìn)行分區(qū),提升算法開發(fā)能力.本節(jié)通過(guò)多種參數(shù)取值下的實(shí)驗(yàn),說(shuō)明η1和η2的取值原因.選取7種參數(shù)取值方案:

分別對(duì)兩目標(biāo)問題ZDT3和三目標(biāo)問題DTLZ2進(jìn)行實(shí)驗(yàn),測(cè)試ZDT3 問題時(shí),每20 次迭代進(jìn)行一次IGD 指標(biāo)評(píng)價(jià),測(cè)試DTLZ2問題時(shí),每30 次迭代進(jìn)行一次IGD 指標(biāo)評(píng)價(jià),實(shí)驗(yàn)結(jié)果如圖4 所示.

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

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

3.2.2 分區(qū)參數(shù) α 和β

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

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

圖5 不同分區(qū)參數(shù)取值方案下IGD 指標(biāo)變化Fig.5 IGD metric changes of different partition parameter value schemes

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

3.3 實(shí)驗(yàn)結(jié)果及比較分析

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

表1～6 分別給出了包括本文spmsAMOPSO 算法在內(nèi)的多種多目標(biāo)優(yōu)化算法在12 個(gè)測(cè)試問題上的IGD、SP 以及ER 性能指標(biāo)的平均值和標(biāo)準(zhǔn)差.表7 給出了幾種算法計(jì)算所需的時(shí)間,其中粗體數(shù)據(jù)為各評(píng)價(jià)指標(biāo)下所得的最優(yōu)結(jié)果.

表7 不同算法對(duì)多目標(biāo)測(cè)試問題的運(yùn)行時(shí)間 (s)Table 7 Computational time of different algorithms for multi-objective test problems (s)

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

表1 本文算法與其他多目標(biāo)粒子群算法的IGD 評(píng)價(jià)指標(biāo)對(duì)比Table 1 Results of IGD metric of the proposed algorithm and MOPSOs

表2 本文算法與其他多目標(biāo)進(jìn)化算法的IGD 評(píng)價(jià)指標(biāo)對(duì)比Table 2 Results of IGD metric of the proposed algorithm and multi-objective genetic algorithms

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

表3 本文算法與其他多目標(biāo)粒子群算法的SP 評(píng)價(jià)指標(biāo)對(duì)比Table 3 Results of SP metric of the proposed algorithm and MOPSOs

表4 本文算法與其他多目標(biāo)進(jìn)化算法的SP 評(píng)價(jià)指標(biāo)對(duì)比Table 4 Results of SP metric of the proposed algorithm and multi-objective genetic algorithms

SP 指標(biāo)的實(shí)驗(yàn)結(jié)果表明,本文算法獲得的非支配解集具有良好的多樣性,這是由于本文算法通過(guò)對(duì)算法環(huán)境的檢查自適應(yīng)地調(diào)整了算法慣性權(quán)重和學(xué)習(xí)因子,并采用種群分區(qū)策略,對(duì)種群中收斂性較好的粒子制定特殊的搜索引導(dǎo)策略和變異方法,提升粒子的探索效率,有效增強(qiáng)算法多樣性.

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

表5 本文算法與其他多目標(biāo)粒子群算法的ER 評(píng)價(jià)指標(biāo)對(duì)比Table 5 Results of ER metric of the proposed algorithm and MOPSOs

表6 本文算法與其他多目標(biāo)進(jìn)化算法的ER 評(píng)價(jià)指標(biāo)對(duì)比Table 6 Results of ER metric of the proposed algorithm and multi-objective genetic algorithms

ER 指標(biāo)的實(shí)驗(yàn)結(jié)果表明,本文算法相較于其他幾種多目標(biāo)優(yōu)化算法具有更好的收斂性,這是由于本文算法通過(guò)在最優(yōu)粒子選取和變異中加入種群分區(qū),對(duì)種群中性能較差的粒子實(shí)行特殊的尋優(yōu)策略,增強(qiáng)劣勢(shì)粒子的利用率,有效提升算法收斂性;在個(gè)體最優(yōu)粒子選取中,加入粒子的記憶機(jī)制,提升個(gè)體最優(yōu)粒子選取的可靠性,增強(qiáng)個(gè)體最優(yōu)粒子對(duì)粒子收斂過(guò)程的指導(dǎo)作用.

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

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

圖6 不同多目標(biāo)優(yōu)化算法對(duì)ZDT3 函數(shù)的Pareto 前沿Fig.6 Pareto front of ZDT3 function of different multi-objective optimization algorithms

圖8 不同多目標(biāo)優(yōu)化算法對(duì)DTLZ7 函數(shù)的Pareto 前沿Fig.8 Pareto front of DTLZ7 function of different multi-objective optimization algorithms

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

圖9 7種多目標(biāo)優(yōu)化算法在測(cè)試ZDT3、DTLZ2和DTLZ7 問題時(shí)IGD、SP 以及ER 指標(biāo)的箱形圖Fig.9 Box plots of IGD,SP and ER metric on ZDT3,DTLZ2 and DTLZ7 problems of multi-objective optimization algorithms

綜合實(shí)驗(yàn)結(jié)果表明,本文算法得到的非支配解集能夠有效地收斂在真實(shí)Pareto 前沿,并具有良好的分布性.這是由于本文算法通過(guò)對(duì)種群進(jìn)行分區(qū),制定多策略的搜索引導(dǎo)方案,有效平衡了算法的收斂性和多樣性,提升了粒子的探索和開發(fā)能力及尋優(yōu)效率,并且使算法具有較好綜合性能的同時(shí)降低了算法的計(jì)算復(fù)雜度.

4 結(jié)束語(yǔ)

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