高慶吉 王瑞雪 談 政

(中國(guó)民航大學(xué)電子信息與自動(dòng)化學(xué)院 天津 300300)

0 引 言

通常在多目標(biāo)優(yōu)化問(wèn)題當(dāng)中，要求在幾個(gè)相互關(guān)聯(lián)的約束條件下，實(shí)現(xiàn)此類問(wèn)題的全局優(yōu)化，多目標(biāo)優(yōu)化問(wèn)題解集不是唯一的，要想使得優(yōu)化問(wèn)題中的每個(gè)目標(biāo)函數(shù)值達(dá)到最佳效果，要求針對(duì)這些目標(biāo)函數(shù)進(jìn)行進(jìn)一步的優(yōu)化處理。

粒子群優(yōu)化算法(Particle swarm optimization，PSO)的原型是虛擬大量的生物群體活動(dòng)，例如進(jìn)行尋找食物行為等，提出的一種群體智能優(yōu)化方法[1]。具有簡(jiǎn)易迅速的優(yōu)化特點(diǎn)[2]，已經(jīng)很好地在求解單目標(biāo)最優(yōu)問(wèn)題當(dāng)中實(shí)現(xiàn)[3]。近幾年P(guān)SO優(yōu)化算法再次引起國(guó)內(nèi)外學(xué)者關(guān)注并成功被應(yīng)用到多目標(biāo)的優(yōu)化問(wèn)題中[4]，同時(shí)也成為了處理多目標(biāo)優(yōu)化問(wèn)題的優(yōu)選算法之一，取得良好的應(yīng)用效果。文獻(xiàn)[5]討論了一種特殊的以分解和差分進(jìn)化為基礎(chǔ)的MOPSO優(yōu)化算法，引用方向角概念，保證了粒子分布的均勻性，同時(shí)用隱式精英保持策略與差分進(jìn)化修正方法挑選出整體最優(yōu)粒子，防止粒子陷入局部最優(yōu)Pareto前沿。文獻(xiàn)[6]討論了以QPSO和擁擠距離排序?yàn)榛A(chǔ)的MOPSO優(yōu)化方法，利用粒子重置方法確保了群體的多樣性。

目前大多數(shù)PSO算法的研究主要集中在種群多樣性和目標(biāo)收斂性方面[7]，標(biāo)準(zhǔn)PSO易陷入局部最優(yōu)解，收斂性較差[8,9]。為了改善PSO在尋找最優(yōu)解集時(shí)的多樣性，提出了一種利用高斯變異位置更新方法避免早熟現(xiàn)象，為了提高算法的收斂性，提出了一種采用自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略，將收斂性較差的粒子剔除。實(shí)驗(yàn)表明該算法具有快速的收斂性，同時(shí)在解的多樣性和分布性上也表現(xiàn)出很好的性能。在解決復(fù)雜多目標(biāo)難題時(shí)，該改進(jìn)方法的性能指標(biāo)得到較大改善。

1 MOPSO算法模型

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

多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)模型[10]如下：

(1)

式中：x=(x1,x2,x3,…,xn)T，x∈A為函數(shù)的搜索域，t是函數(shù)的時(shí)間變量，T和s是此數(shù)學(xué)模型的等式與不等式的約束條件，n是決策變量的維數(shù)，f是隨時(shí)間變化的D維目標(biāo)函數(shù)。

在多目標(biāo)優(yōu)化問(wèn)題求解過(guò)程中，最好的求解結(jié)果是使得到最優(yōu)解最大程度地接近或收斂于真正Pareto前沿，并且此解集的分布盡量可能平均。

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

一開(kāi)始最原始的粒子群算法的速度項(xiàng)并沒(méi)有系數(shù)，后經(jīng)Shi等[11]科研人員的改進(jìn)，引進(jìn)了系數(shù)權(quán)重，構(gòu)成了現(xiàn)在常用的PSO算法更新公式。設(shè)種群里的每一個(gè)粒子i(i∈N),N是群體大小，粒子活動(dòng)的空間是D維的，t時(shí)刻到t+1時(shí)刻的速度更新和位置更新為[12]：

vi(t+1,d)=ωvi(t,d)+c1rand(gbest(t,d)-xi(t,d))+
c2rand(pbest(t,d)-xi(t,d))

(2)

xi(t+1,d)=xi(t,d)+vi(t+1,d),d=1,2,…,D

(3)

式中：ω是關(guān)系系數(shù)，代表著上一時(shí)刻的速度大小對(duì)下一時(shí)刻速度大小的影響大??；c1、c2是能力系數(shù)，分別表示全局學(xué)習(xí)能力的大小和局部學(xué)習(xí)能力大小，c1越大表示粒子全局學(xué)習(xí)能力越強(qiáng)，越趨向于全局最優(yōu)位置，c2越小代表粒子局部搜察能力越弱；gbest代表整個(gè)粒子群中所有的粒子所經(jīng)歷過(guò)的最優(yōu)坐標(biāo)；pbest是粒子個(gè)體i曾經(jīng)經(jīng)歷的最優(yōu)位置；rand為(0, 1)上產(chǎn)生的隨機(jī)數(shù)；d為粒子i的d維變量。

標(biāo)準(zhǔn)PSO簡(jiǎn)單而且在單目標(biāo)求解中獲得了很好的應(yīng)用[13,14],但在更新個(gè)體最優(yōu)值和全局最優(yōu)值的過(guò)程中，粒子通常會(huì)表現(xiàn)出早熟的跡象[15,16]，種群粒子提前終止進(jìn)化，陷入局部最優(yōu)。

2 改進(jìn)多目標(biāo)粒子群算法

2.1 基于高斯變異的位置更新

標(biāo)準(zhǔn)PSO優(yōu)化算法在更新個(gè)體最優(yōu)值和全局最優(yōu)值的過(guò)程中，粒子通常會(huì)表現(xiàn)出早熟的現(xiàn)象，整個(gè)粒子群中的粒子提早終止變異，陷入部分極值。研究發(fā)現(xiàn)，在粒子位置更新過(guò)程中，適當(dāng)?shù)靥砑右恍_動(dòng)，很容易使某些解值跳出局部最優(yōu)。所以，將高斯變異的思想帶入PSO算法的尋找最優(yōu)解過(guò)程當(dāng)中，從而改善粒子在求解過(guò)程當(dāng)中的多樣性。采用實(shí)時(shí)變異，即在位置的更新上加入動(dòng)態(tài)變異，使迭代次數(shù)也參與變異，可以使變異呈隨時(shí)間變化而變化的動(dòng)態(tài)形式。由于在位置更新的過(guò)程中，初始時(shí)刻的解接近最優(yōu)解的較少，大部分的解距離最優(yōu)解較遠(yuǎn)，而隨著時(shí)間的推移，有越來(lái)越多解接近最優(yōu)解，變異解個(gè)數(shù)應(yīng)隨時(shí)間的流逝而呈遞減狀態(tài)，因此定義每一代粒子參加變異的個(gè)數(shù)隨迭代次數(shù)的遞增而呈單調(diào)衰減，保證了一些較優(yōu)的解不變異。根據(jù)高斯概率函數(shù)的分布情況重構(gòu)了基于高斯變異的函數(shù)Gi(t)，具體的構(gòu)造表達(dá)式如下：

(4)

式中：xbest是目前總體的最優(yōu)解，δ是高斯分布標(biāo)準(zhǔn)差，當(dāng)?shù)螖?shù)達(dá)到一定值后，大部分的粒子將向xbest的位置移動(dòng)，導(dǎo)致所有的解值過(guò)早的停止尋優(yōu)，此刻利用Gi(t)函數(shù)來(lái)增加擾動(dòng),使粒子逃脫xbest的束縛，減小了粒子進(jìn)入部分最優(yōu)的概率。應(yīng)用高斯變異擾動(dòng)迭代更新，其公式如下：

(5)

2.2 基于自適應(yīng)參考點(diǎn)外部檔案維護(hù)

在本小節(jié)中外部檔案的主要作用是來(lái)存儲(chǔ)粒子在迭代過(guò)程中求得的較好的非支配解。每次將所得到的非支配解存儲(chǔ)到外部檔案中，將外部檔案中解的個(gè)數(shù)與最大值比較，當(dāng)數(shù)量超過(guò)最大數(shù)量時(shí)，就必須從中選擇一些解將其剔除，同時(shí)保持解集多樣性和收斂性。為了改善這兩種性能指標(biāo)，提出了一種基于自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略。首先選出密度函數(shù)最大的標(biāo)準(zhǔn)線，其次將標(biāo)準(zhǔn)線所在的解集中收斂程度最小的粒子剔除，然后將外部檔案的大小與容量最大值進(jìn)行比較，判斷是否需要從外部檔案中剔除多余的解值。具體步驟如下：

Step1計(jì)算粒子密度函數(shù)。算出每代粒子x的密度函數(shù)集合M。

Step2計(jì)算粒子的收斂程度S。

Step3取密度函數(shù)最大的集合Mmax，從中任意選擇出當(dāng)中的一條作為標(biāo)準(zhǔn)線j。

Step4將標(biāo)準(zhǔn)線j所在的解集M中收斂程度S最小的粒子剔除。

Step5將外部檔案的大小與容量最大值進(jìn)行比較，如果超過(guò)，就執(zhí)行Step 1；否則，將該解存入外部存儲(chǔ)器。

2.3 算法流程

以上述操作作為基本原則，改進(jìn)粒子群算法的具體步驟如下：

Step1初始化，首先設(shè)置參數(shù)的最初數(shù)，例如粒子群的大小、外部檔案的大小、最大迭代次數(shù)。然后初始化粒子群的搜索范圍、將外部檔案設(shè)置為零。

Step2更新局部最優(yōu)粒子、全局最優(yōu)粒子和粒子位置。

Step3高斯變異位置更新。

Step4外部檔案更新。

Step5迭代次數(shù)加1，判斷是否達(dá)到迭代次數(shù)，若達(dá)到迭代次數(shù)，結(jié)束更新。否則繼續(xù)執(zhí)行Step2。

算法的流程圖如圖1所示。

圖1 該進(jìn)粒子群算法的工作流程

3 仿真實(shí)驗(yàn)及結(jié)果分析

判斷一個(gè)多目標(biāo)優(yōu)化算法是否優(yōu)于其他方法時(shí)，其中最重要的判斷方法就是該方法是否能夠?qū)ふ业秸嬲腜areto前沿，并且在該條件下，將得到的解集的收斂性和多樣性與沒(méi)有改進(jìn)時(shí)的性能進(jìn)行對(duì)比，最終得出算法的評(píng)價(jià)結(jié)果。為驗(yàn)證本文改進(jìn)的基于高斯變異和自適應(yīng)參考點(diǎn)的多目標(biāo)粒子群優(yōu)化算法的性能，選取ZDT1、ZDT2[17,18]測(cè)試函數(shù)來(lái)驗(yàn)證。選以上函數(shù)作為驗(yàn)證函數(shù)是因?yàn)閆DT1函數(shù)為凸函數(shù)，ZDT2函數(shù)為凹函數(shù)，其中f1和f2分別是兩個(gè)目標(biāo)函數(shù)。利用不同的多目標(biāo)函數(shù)來(lái)驗(yàn)證高斯變異和自適應(yīng)參考點(diǎn)的多目標(biāo)粒子群優(yōu)化算法的收斂性和多樣性。

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

非靜態(tài)的多目標(biāo)優(yōu)化算法的目的就是在非靜態(tài)的條件中，使最多的解集能夠快速的收斂于該函數(shù)的Parto前沿P*(t)，并且需要保持解集合S(t)的多樣性。本文采用反向代距離[19](Inverse gener-ation distance, IGD)和超體積比 (Hypervolume ratio,HVR)指標(biāo)來(lái)評(píng)價(jià)所提算法的收斂新和多樣性。其中,IGD的定義如下：

(6)

IGD(t)函數(shù)能夠判斷該方法的收斂性。在理想狀態(tài)下IGD(t)值為0，表示S(t)達(dá)到了最好的收斂效果。超體積比[20]HVR是以超體積 (Hypervolume, HV)為基準(zhǔn)演變過(guò)來(lái)的，其數(shù)值的大小直接能夠反映出算法尋找解的多樣性能力，計(jì)算公式如下所示：

(7)

(8)

根據(jù)HVR(t)值的大小能夠得出該算法多樣性是否豐富的結(jié)果，當(dāng)S(t)和P*(t)的值大小相等時(shí)，HVR(t)的值最大，且為1。由此可以得出HVR(t)的數(shù)值越大，就表示該算法在多樣性這方面的性能越好。

3.2 算法參數(shù)設(shè)置及實(shí)驗(yàn)結(jié)果分析

為了證明本文方法具有一定的改善效果，本算法的所有參數(shù)設(shè)置如下：其中慣性系數(shù)ωmax=0.9、ωmin=0.4，學(xué)習(xí)系數(shù)C1=C2=1.5。ZDT函數(shù)所有算法均取種群數(shù)量為200，外部存檔數(shù)量為200。為了體現(xiàn)出公正性，表1是對(duì)不同算法的參數(shù)設(shè)置。

表1 優(yōu)化算法的參數(shù)設(shè)置

MDPSO算法和改進(jìn)MOPSO。

算法在ZDT1、ZDT2函數(shù)上的對(duì)比如圖2、圖3所示，其性能指標(biāo)如表2所示。

(a) MOPSO (b) 改進(jìn)MOPSO圖2 算法在ZDT1函數(shù)上的對(duì)比

(a) MOPSO (b) 改進(jìn)MOPSO圖3 算法在ZDT2函數(shù)上的對(duì)比

表2 MOPSO與改進(jìn)MOPSO在ZDT函數(shù)上性能指標(biāo)

由表2可知，改進(jìn)MOPSO在加入高斯變異和自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略后，在測(cè)試函數(shù)ZDT1和ZDT2上的IGD和HVR性能指標(biāo)都有了明顯的提高。

MOPSO算法與改進(jìn)MOPSO算法在ZDT1、ZDT2函數(shù)上的IGD趨勢(shì)如圖4、圖5所示。

圖4 ZDT1的IGD趨勢(shì)

圖5 ZDT2的IGD趨勢(shì)

由圖4和圖5可知，改進(jìn)MOPSO在加入高斯變異和自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略后，在相同的迭代次數(shù)后Pareto解的收斂性明顯高于MOPSO。

MOPSO算法與改進(jìn)MOPSO算法在ZDT1、ZDT2函數(shù)上的HVR趨勢(shì)如圖6、圖7所示。

圖6 ZDT1的HVR趨勢(shì)

圖7 ZDT2的HVR趨勢(shì)

由圖6和圖7可知，改進(jìn)MOPSO在加入高斯變異和自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略后，在相同的迭代次數(shù)時(shí)Pareto解的多樣性明顯高于MOPSO。

綜上所述，改進(jìn)MOPSO在加入高斯變異和自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略后，最優(yōu)解集向標(biāo)準(zhǔn)的Pareto解集收斂的速度加快了，同時(shí)粒子能夠跳出局部最優(yōu)極值的能力增強(qiáng)了，尋優(yōu)的精度也變高了。

4 結(jié) 語(yǔ)

針對(duì)動(dòng)態(tài)多目標(biāo)優(yōu)化問(wèn)題，本文提出了一種基于高斯變異和自適應(yīng)參考點(diǎn)的多目標(biāo)粒子群優(yōu)化算法。該算法利用高斯變異的位置更新方法避免早熟現(xiàn)象，提高了PSO在尋優(yōu)過(guò)程中搜索解的多樣性，采用自適應(yīng)參考點(diǎn)的外部檔案維護(hù)策略提高算法的收斂性。仿真實(shí)驗(yàn)結(jié)果表明：改進(jìn)MOPSO算法在多目標(biāo)優(yōu)化中具有良好的效果，同時(shí)，該算法結(jié)構(gòu)簡(jiǎn)單，具有良好的可移植性，可為后續(xù)多目標(biāo)優(yōu)化算法的研究提供參考。