基于R2指標(biāo)的擬態(tài)物理學(xué)約束多目標(biāo)優(yōu)化算法

孫 寶,郭 娜,李占龍,張麗靜

(1.太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院， 太原 030024； 2.太原科技大學(xué) 機(jī)械工程學(xué)院， 太原 030024)

1 引言

在實(shí)際問題中，絕大多數(shù)優(yōu)化問題由多個子目標(biāo)所組成，并且這些子目標(biāo)之間相互矛盾，相互沖突，一個子目標(biāo)性能的改善可能會引起其余子目標(biāo)性能的降低，這種在優(yōu)化過程中要求多個子目標(biāo)同時在指定區(qū)域內(nèi)達(dá)到最優(yōu)值的問題即為多目標(biāo)優(yōu)化問題。針對多目標(biāo)優(yōu)化問題及其研究，越來越多的群體智能進(jìn)化算法在自然行為的啟發(fā)下得到發(fā)展，如多目標(biāo)粒子群優(yōu)化算法(MOPSO)、非支配排序遺傳算法(NSGAII)、多目標(biāo)分布估計(jì)算法(MOEDA)等。

APO算法是一種新的基于群體智能的隨機(jī)優(yōu)化算法。通過牛頓第二定律的啟發(fā)，建立個體之間的虛擬力規(guī)則，更新個體的速度和位置，使個體移動到最優(yōu)目標(biāo)，并圍繞全局最優(yōu)收斂。APO算法已成功應(yīng)用于無約束多目標(biāo)優(yōu)化問題。Wang Y等針對APO算法自身的性能，從多目標(biāo)優(yōu)化問題出發(fā)，以虛擬力的角度分析多目標(biāo)算法中個體-優(yōu)劣，提出一種基于虛擬力排序的約束多目標(biāo)擬態(tài)物理學(xué)優(yōu)化算法。Sun B等在MOAPO算法的基礎(chǔ)上結(jié)合約束違反度的判斷準(zhǔn)則，提出一種基于序值和擁擠度的擬態(tài)物理學(xué)多目標(biāo)算法(improved constrained rank multi-objective artificial physics optimization,ICRMOAPO)，但在解的篩選過程中將新的個體與archive解集中的個體進(jìn)行比較，容易將優(yōu)質(zhì)解丟失，使其無法得到一組均勻且廣泛的最優(yōu)解。

近年來，對于多目標(biāo)優(yōu)化算法的選解機(jī)制，國內(nèi)外學(xué)者做了大量的研究。Sedighizadeh D等提出了一種連續(xù)空間粒子群優(yōu)化算法，通過在速度更新方程中引入新的項(xiàng)，使得在搜索空間中更好地進(jìn)行搜索。Cai D等將目標(biāo)空間分解為多個子空間，并在每個子空間上保留最優(yōu)解以保持解集的分布性。Kohler M等將多樣性插入到群體中，擴(kuò)大搜索空間的覆蓋率，提高了算法的效率和收斂速度。Garcia I C等提出了一種基于超體積指標(biāo)的多目標(biāo)粒子群算法，利用外部存檔來存儲進(jìn)化過程中發(fā)現(xiàn)的全局非支配解，為求解多目標(biāo)問題提出了一種新的思考方向。Li F團(tuán)隊(duì)針對HV指標(biāo)難以有效權(quán)衡計(jì)算時間復(fù)雜度和計(jì)算精度之間的矛盾進(jìn)行研究，發(fā)現(xiàn)R2指標(biāo)可以替代HV指標(biāo)求解多目標(biāo)問題，將R2指標(biāo)和PBI分解策略結(jié)合求解多目標(biāo)優(yōu)化問題,提出了R2-MOPSO算法。

針對ICRMOAPO算法的不足，為了得到收斂于Pareto前沿且均勻分布的解，利用R2指標(biāo)綜合評價解集的特質(zhì)，提出一種基于R2指標(biāo)的擬態(tài)物理學(xué)約束多目標(biāo)優(yōu)化算法(R2-ICRMOAPO)。算法將非支配排序和R2指標(biāo)結(jié)合，并根據(jù)R2指標(biāo)的貢獻(xiàn)值對外部存儲集進(jìn)行更新和維護(hù)，保留分布均勻的精英解。

2 約束多目標(biāo)優(yōu)化問題

一般地,約束多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型可以被描述為：

min()=[(),(),…,()]

s.t.()=((),()…,())<0

()=((),()…,())=0

(1)

式中，=[,,…,]∈為決策變量，決策空間∈，

滿足邊界約束條件：≤≤,1≤≤，,分別為的上界和下界；()為目標(biāo)函數(shù)；()<0為不等式約束條件，()=0為等式約束條件，約束條件決定可行域的范圍。

1pareto支配

Pareto支配，記為<，其中為支配解，為非支配解，當(dāng)且僅當(dāng)?∈{1,2,…,},()≤()，?∈{1,2,…,},s.t.()<()。

2Pareto最優(yōu)解集

對于一個約束多目標(biāo)優(yōu)化問題，它的可行決策空間中所有最優(yōu)解的集合稱為Pareto最優(yōu)解集，令其為。

(2)

3Pareto前沿

Pareto最優(yōu)解集中每個解對應(yīng)的目標(biāo)值向量組成的集合稱為Pareto前沿。

約束多目標(biāo)優(yōu)化問題就是要得到一組解集，使之逼近Pareto前沿。在目標(biāo)空間中則表示為，非支配解集覆蓋的目標(biāo)空間區(qū)域盡可能大，且與真實(shí)前沿的距離盡可能小。

3 擬態(tài)物理學(xué)算法

擬態(tài)物理學(xué)是由美國懷俄名州立大學(xué)的Spear等人以自然物理力量為動力所提出來的，受啟發(fā)于物理力學(xué)定律，故稱之為“擬態(tài)”，最初被應(yīng)用于機(jī)器人群體的分布式控制研究。

文獻(xiàn)[5]中利用擬態(tài)物理學(xué)的思想處理全局優(yōu)化問題，提出一種新的優(yōu)化算法APO。該方法本質(zhì)上是通過對牛頓第二定律的模擬，將問題可行域中采樣的個體粒子看作是物理中的質(zhì)點(diǎn)，在粒子之間虛構(gòu)一種相互作用力，給出該作用力的計(jì)算規(guī)則，結(jié)合個體的速度和位移更新粒子的運(yùn)動，實(shí)現(xiàn)對整個種群的控制。

在APO算法中，種群規(guī)模為，個體在維上的速度表示為,，個體在維上位置表示為,。第個個體的質(zhì)量為(=1,2,…,)，且個體的質(zhì)量隨著適應(yīng)值的改變而改變，適應(yīng)值小的個體質(zhì)量大，適應(yīng)值大的個體質(zhì)量反而小。此外個體質(zhì)量還受到種群中適應(yīng)度值最優(yōu)和最差個體的影響，進(jìn)而影響個體所受的力。所以，計(jì)算個體質(zhì)量函數(shù)定義為：

(3)

式中：、分別表示最優(yōu)、最差適應(yīng)值的位置。

由每個個體質(zhì)量，仿照萬有引力公式，計(jì)算出各個個體所受作用力的大小，故個體在第維上所受的第個(≠)個體的虛擬力為,：

(4)

個體在第維上所受作用力合力的計(jì)算公式為：

(5)

式中，為引力因子。

個體的速度和位置更新公式為：

,(+1)=,()+,, ?≠

(6)

,(+1)=,()+,(+1), ?≠

(7)

式中：∈(0,1)為慣性權(quán)重；為分布在區(qū)間[0，1]上的一個隨機(jī)數(shù)；∈[,]；∈[,]。

4 R2-ICRMOAPO算法

隨著約束多目標(biāo)問題的廣泛應(yīng)用，相應(yīng)的約束多目標(biāo)優(yōu)化算法也層出不窮。非支配解的選取是解決約束多目標(biāo)問題的重要技術(shù)之一，直接影響算法的性能。ICRMOAPO 算法通過比較新的非支配個體和archive集中的個體來獲得新的外部存儲集，在一定程度上對問題進(jìn)行了求解，但由于沒有嚴(yán)格地對解集進(jìn)行篩選，可能會使一些優(yōu)質(zhì)個體缺失。R2指標(biāo)可以很好地解決這一問題，利用個體的R2指標(biāo)貢獻(xiàn)值，對個體進(jìn)行篩選，可以得到一組性能較好的解集。

4.1 R2指標(biāo)

R2指標(biāo)是基于效用函數(shù)，區(qū)分候選解的優(yōu)劣，從而選擇效用較大的候選解，最初被用于評價2組個體的相對質(zhì)量。利用具有特定參考點(diǎn)的標(biāo)準(zhǔn)加權(quán)切比雪夫函數(shù)，可以用該指標(biāo)相對于參考點(diǎn)來評估單個個體集合的質(zhì)量。因R2指標(biāo)可以綜合評價種群的收斂性和多樣性,并可以通過快速計(jì)算獲得均勻分布的解集,已被應(yīng)用于求解多目標(biāo)優(yōu)化問題。

在此利用加權(quán)切比雪夫函數(shù)作為R2指標(biāo)的效用函數(shù)，通過一組個體(集合)和參考點(diǎn)對個體的質(zhì)量進(jìn)行評價：

(8)

式中：為一組均勻的權(quán)重向量，每個權(quán)重向量=(，，…，)∈，均勻的分布在目標(biāo)空間中，1||代表每個權(quán)重向量被選擇的概率。

如果效用函數(shù)集中每個函數(shù)由于不同的權(quán)重向量而確定,則個體的R2指標(biāo)的貢獻(xiàn)值被定義為：

CR2(,,,)=R2(,,)-R2({},,)

(9)

通過R2指標(biāo)的貢獻(xiàn)值可以對種群中的個體進(jìn)行全排序,R2指標(biāo)的貢獻(xiàn)值越大說明解集的分布性能越好，解的質(zhì)量越高，將其保留到下一代種群的概率就越大。

4.2 R2-ICRMOAPO算法基本思想

外部存儲集非支配個體的選取對算法的收斂性和分布性具有直接的影響，在算法的迭代進(jìn)化過程中，非支配解的數(shù)量也在同步增加，并且可能會超過預(yù)先設(shè)定的解集規(guī)模，因此外部存儲集的更新和維護(hù)對于解集的質(zhì)量起著非常重要的作用。本研究在ICRMOAPO算法的基礎(chǔ)上，將非支配排序和R2指標(biāo)結(jié)合，首先利用Pareto支配關(guān)系得到一組非支配解集，計(jì)算出非支配解集中個體的R2指標(biāo)貢獻(xiàn)值，然后將R2指標(biāo)貢獻(xiàn)值作為外部存儲集的更新機(jī)制，通過刪減R2指標(biāo)貢獻(xiàn)值較小的個體，實(shí)現(xiàn)對整個種群的控制，從而選擇出效用更好的候選解。針對上述思想構(gòu)造出一種R2-ICRMOAPO算法，為求解約束多目標(biāo)優(yōu)化問題提供一種新的思路。算法的關(guān)鍵要素如下：

1) 個體序值

設(shè)在第代生成的種群()由個個體所組成，()表示種群()中支配個體的所有個體數(shù)量，則個體在第代的序值定義為：

()=1+()

(10)

依據(jù)個體序值的定義，為種群中所有的支配個體，分配相對應(yīng)的序值。但若在某一代中出現(xiàn)具有相同序值的個體，則需要從其他角度對此問題進(jìn)行解決。

2) 鄰域半徑

針對序值相同的個體，下面引入鄰域半徑的定義。

定義個體的鄰域?yàn)樵搨€體半徑內(nèi)所包含的區(qū)域。為了避免算法中鄰域半徑過小，故將鄰域半徑定義為：

(11)

式中，max||為初始化時第維上個體間的最大歐式距離。

3) 鄰域擁擠度

鄰域擁擠度是指在個體間支配與被支配的作用下所計(jì)算出某個個體在對應(yīng)鄰域半徑區(qū)域內(nèi)所包含個體數(shù)量的大小。

當(dāng)出現(xiàn)序值大小相同，鄰域擁擠度也相同的個體時，將鄰域半徑重新調(diào)整。若調(diào)整后，具有相同序值的個體在相應(yīng)鄰域半徑內(nèi)還包含相同的個體數(shù)量，將這些個體隨機(jī)進(jìn)行排列，分配編號即可。

4) 質(zhì)量函數(shù)

為了考慮個體間的支配關(guān)系和個體所處鄰域半徑內(nèi)的擁擠程度，并充分體現(xiàn)多目標(biāo)優(yōu)化問題本身的特點(diǎn)，將質(zhì)量函數(shù)定義為：

(12)

5) 引力因子

引力因子是影響算法性能的重要因素之一，在一定程度上會決定種群做收斂運(yùn)動的個體數(shù)量。在標(biāo)準(zhǔn)APO算法中，將引力因子規(guī)定為10。R2-ICRMOAPO算法為了使引力因子隨種群的進(jìn)化而產(chǎn)生動態(tài)的變化，將其進(jìn)行改進(jìn)，令為：

(13)

式中：和為引力因子的初始值和終值，由經(jīng)驗(yàn)可知，算法中=70，迭代到最后，的終取值為=1；為迭代次數(shù)；為最大迭代次數(shù)。

6) 慣性權(quán)重

慣性權(quán)重的選取影響算法的性能和效率，迭代初期較大的慣性權(quán)重使算法保持較強(qiáng)的全局搜索能力，迭代后期較小的慣性權(quán)重有利于算法進(jìn)行更精確的局部搜索。

在R2-ICRMOAPO算法中采用線性遞減的慣性權(quán)重，使慣性權(quán)重隨著迭代的進(jìn)行而動態(tài)減小：

(14)

式中：為初始值，算法中取09；為終值，算法中取04。

7) 不可行度

不可行度可以作為一種準(zhǔn)則來判斷更新個體是否落入可行域中。

R2-ICRMOAPO算法中定義不可行度為：

(15)

式中:、分別為多目標(biāo)優(yōu)化問題的不等式約束和等式約束。當(dāng)為可行解時，不可行度為0。

4.3 R2-ICRMOAPO算法流程

R2-ICRMOAPO算法流程如圖1所示。

圖1 R2-ICRMOAPO算法流程框圖Fig.1 R2-ICRMOAPO algorithm flowchart

R2-ICRMOAPO算法的主要步驟如下：

Step 1：初始化種群：種群規(guī)模，外部存儲集規(guī)模archivesize，權(quán)重向量，最大迭代次數(shù)，隨機(jī)產(chǎn)生所有個體的初始速度和位置，初始化參考點(diǎn)。

Step 2：計(jì)算所有個體在每個目標(biāo)下的適應(yīng)度值，確定非支配個體，存儲于archive集。對非支配個體的序值定義為1，其余個體的序值定義為+1。

Step 3：對archive集中的非支配個體計(jì)算R2指標(biāo)貢獻(xiàn)值，按降序原則進(jìn)行排序。

Step 4：根據(jù)個體序值的定義，對種群中所有個體按照升序原則進(jìn)行排序。

Step 5：利用歐式距離計(jì)算鄰域半徑，若出現(xiàn)序值相等的個體，重新確定個體鄰域擁擠度，按升序原則對全部個體重新進(jìn)行排序。

Step 6：出現(xiàn)鄰域半徑內(nèi)包含相同個體數(shù)量的同序值個體時，將該個體標(biāo)記為()=1。

Step 7：()=1時，對鄰域半徑進(jìn)行調(diào)整并重新排序，對于調(diào)整后序值大小和擁擠度相等的個體，進(jìn)行隨機(jī)排序。對所有個體賦予1～的自然數(shù)，作為每個個體序號，記作()。

Step 8：計(jì)算每個個體的質(zhì)量，個體在第維上所受的第個(≠)個體的虛擬力,，在第維上所受作用力的合力,。

Step 9：根據(jù)式(6)、式(7)更新個體的速度和位置。

Step 10：利用不可行度的判斷準(zhǔn)則來確定所更新的個體是否落在可行域內(nèi)，將未落入可行域內(nèi)的個體用最優(yōu)迭代更新的方法重新更新其位置。

Step 11：確定新的非支配個體，更新archive集，當(dāng)archive集中都是非支配個體時，對所有個體計(jì)算CR2值，按照降序原則進(jìn)行排序，若個體數(shù)量超過archive集規(guī)模時，將archive集中R2指標(biāo)貢獻(xiàn)值較小的個體刪除，直到個體數(shù)量滿足設(shè)定的規(guī)模，獲得新的archive集。

Step 12：若達(dá)到最大迭代次數(shù)則退出，否則返回步驟5。

5 實(shí)驗(yàn)結(jié)果與分析

為了評估R2-ICRMOAPO算法在解決約束多目標(biāo)問題時的性能，通過R2-ICRMOAPO算法和其他四種優(yōu)化算法：基于序值與擁擠度的擬態(tài)物理學(xué)多目標(biāo)算法(improved constrained rank multi-objective artificial physics optimization，ICRMOAPO)、帶精英策略的非支配排序的遺傳算法 (non-dominated sorting genetic algorithm，NSGAII)、基于R2指標(biāo)的多目標(biāo)粒子群算法(multi-objective particle swarm optimization on R2 indicator,R2MOPSO)、ε多目標(biāo)進(jìn)化算法(epsilon multi-objective evolutionary algorithm,ε-MOEA)在標(biāo)準(zhǔn)約束多目標(biāo)測試函數(shù)上進(jìn)行實(shí)驗(yàn)對比，并將超體積(Hypervolume,HV)和反轉(zhuǎn)世代距離(inverted generational distance，IGD)作為算法的性能評價指標(biāo)，從收斂性和分布性對算法進(jìn)行綜合評價，全面說明算法的有效性。

本文選定的測試函數(shù)如表1所示。

表1 約束多目標(biāo)標(biāo)準(zhǔn)測試函數(shù)Table 1 Constrained multi-objective standard test functions

實(shí)驗(yàn)中，設(shè)定種群規(guī)模和外部存儲集規(guī)模均為100，進(jìn)化代數(shù)為50。圖2～圖4表示算法R2-ICRMOAPO、ICRMOAPO、R2MOPSO、NSGAII、和ε-MOEA對測試函數(shù)生成的Pareto前沿和真實(shí)Pareto前沿曲線。

圖2 Binh(2)的Pareto前沿曲線Fig.2 The Pareto Frontier of Binh (2)

圖3 SRN的Pareto前沿曲線Fig.3 The Pareto Frontier of SRN

圖4 DEB的Pareto前沿曲線Fig.4 The Pareto Frontier of DEB

圖5～圖7顯示了R2-ICRMOAPO算法所求得Pareto 解集中更新個體的位置。

圖5 Binh(2)的Pareto解集中更新個體位置曲線Fig.5 The updated position of Binh(2)

圖6 SRN的Pareto解集中更新個體位置曲線Fig.6 The updated position of SRN

圖7 DEB的Pareto解集中更新個體位置曲線Fig.7 The updated position of DEB

大多數(shù)研究使用逼近實(shí)際解決方案的程度和設(shè)置解決方案的分布情況來測量多目標(biāo)優(yōu)化算法的性能。本文采用HV和IGD算法性能指標(biāo)對5種算法進(jìn)行對比。

HV指標(biāo)是一種能夠同時衡量算法的收斂性和分布性的綜合性能指標(biāo)，表示非支配解集覆蓋的目標(biāo)空間區(qū)域大小。HV函數(shù)的定義為：

(16)

式中：為Lebesgue測度,用來測量體積；||為非支配解的數(shù)目；為參照點(diǎn)與解集中第個解所構(gòu)成的超體積。算法求得的HV值越大則意味著解集收斂性和分布性越好。

IGD指標(biāo)是一種綜合評價解集質(zhì)量的指標(biāo)，衡量的是真實(shí)前沿的個體到所求得的近似解集之間最小距離的平均值。IGD的函數(shù)定義為：

(17)

對測試函數(shù)進(jìn)行了100次獨(dú)立實(shí)驗(yàn)后，表2～表3分別展示了5種算法關(guān)于HV和IGD性能指標(biāo)的平均值、最優(yōu)值和方差。此外，還采用統(tǒng)計(jì)學(xué)Wilcoxon秩和檢驗(yàn)來表明結(jié)果的顯著性水平，顯著性差異水平為0.05，如果值大于0.05，則表示2種算法之間沒有明顯差異。

表2 測試函數(shù)的HV指標(biāo)值Table 2 HV performance indicators on test functions

表3 測試函數(shù)的IGD指標(biāo)值Table 3 IGD performance indicators on test functions

從表2和表3可以看出，R2-ICRMOAPO算法的HV值高于ICRMOAPO算法，且IGD值低于ICRMOAPO算法。數(shù)據(jù)表明，利用R2指標(biāo)貢獻(xiàn)值對個體進(jìn)行篩選，提高了算法的收斂性和分布性。

從圖2～圖4和表2～表3可知，R2-ICRMOAPO算法在測試函數(shù)Binh(2)和SRN上對Pareto前沿產(chǎn)生了更好的近似，得到的解大部分夠收斂于真實(shí)的Pareto前沿上，在DEB函數(shù)上略差于NSGAII算法。以上數(shù)據(jù)和圖表表明，R2-ICRMOAPO算法在大多數(shù)測試問題上優(yōu)于對比算法，說明R2-ICRMOAPO算法在解決約束多目標(biāo)問題方面具有很大的潛力，可進(jìn)一步推廣應(yīng)用于實(shí)際問題中。

6 結(jié)論

在APO算法的基礎(chǔ)上，針對約束多目標(biāo)優(yōu)化算法，構(gòu)造基于R2指標(biāo)的多目標(biāo)約束優(yōu)化算法，將非支配排序和R2指標(biāo)結(jié)合，利用R2指標(biāo)貢獻(xiàn)值區(qū)分候選解的優(yōu)劣，更新最優(yōu)個體，維護(hù)外部存儲集；將其與4種算法在HV和IGD指標(biāo)下進(jìn)行對比實(shí)驗(yàn)。主要得到以下結(jié)論：

1) 算法利用個體間的支配關(guān)系，考慮個體的擁擠度，對搜索空間中個體適應(yīng)值合理排序，增強(qiáng)了Pareto 解集的多樣性。

2) 設(shè)計(jì)R2指標(biāo)貢獻(xiàn)值選擇個體，對外部存儲集進(jìn)行維護(hù)和更新，增強(qiáng)了種群的分布，在處理約束多目標(biāo)問題中取得較好的效果。

3) 該算法在求解約束多目標(biāo)的問題中收斂性和分布性均得到提高，但對于提高收斂速度還需進(jìn)行研究。