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

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

1 引言

在實(shí)際問題中，絕大多數(shù)優(yōu)化問題由多個(gè)子目標(biāo)所組成，并且這些子目標(biāo)之間相互矛盾，相互沖突，一個(gè)子目標(biāo)性能的改善可能會引起其余子目標(biāo)性能的降低，這種在優(yōu)化過程中要求多個(gè)子目標(biāo)同時(shí)在指定區(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ā)，建立個(gè)體之間的虛擬力規(guī)則，更新個(gè)體的速度和位置，使個(gè)體移動到最優(yōu)目標(biāo)，并圍繞全局最優(yōu)收斂。APO算法已成功應(yīng)用于無約束多目標(biāo)優(yōu)化問題。Wang Y等針對APO算法自身的性能，從多目標(biāo)優(yōu)化問題出發(fā)，以虛擬力的角度分析多目標(biāo)算法中個(gè)體-優(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)，但在解的篩選過程中將新的個(gè)體與archive解集中的個(gè)體進(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)空間分解為多個(gè)子空間，并在每個(gè)子空間上保留最優(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ì)算時(shí)間復(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)綜合評價(jià)解集的特質(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)解集

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

(2)

3Pareto前沿

Pareto最優(yōu)解集中每個(gè)解對應(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ì)上是通過對牛頓第二定律的模擬，將問題可行域中采樣的個(gè)體粒子看作是物理中的質(zhì)點(diǎn)，在粒子之間虛構(gòu)一種相互作用力，給出該作用力的計(jì)算規(guī)則，結(jié)合個(gè)體的速度和位移更新粒子的運(yùn)動，實(shí)現(xiàn)對整個(gè)種群的控制。

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

(3)

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

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

(4)

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

(5)

式中，為引力因子。

個(gè)體的速度和位置更新公式為：

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

(6)

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

(7)

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

4 R2-ICRMOAPO算法

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

4.1 R2指標(biāo)

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

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

(8)

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

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

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

(9)

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

4.2 R2-ICRMOAPO算法基本思想

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

1) 個(gè)體序值

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

()=1+()

(10)

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

2) 鄰域半徑

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

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

(11)

式中，max||為初始化時(shí)第維上個(gè)體間的最大歐式距離。

3) 鄰域擁擠度

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

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

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

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

(12)

5) 引力因子

引力因子是影響算法性能的重要因素之一，在一定程度上會決定種群做收斂運(yùn)動的個(gè)體數(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)則來判斷更新個(gè)體是否落入可行域中。

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

(15)

式中:、分別為多目標(biāo)優(yōu)化問題的不等式約束和等式約束。當(dāng)為可行解時(shí)，不可行度為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)生所有個(gè)體的初始速度和位置，初始化參考點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

為了評估R2-ICRMOAPO算法在解決約束多目標(biāo)問題時(shí)的性能，通過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)作為算法的性能評價(jià)指標(biāo)，從收斂性和分布性對算法進(jìn)行綜合評價(jià)，全面說明算法的有效性。

本文選定的測試函數(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 解集中更新個(gè)體的位置。

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

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

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

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

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

(16)

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

IGD指標(biāo)是一種綜合評價(jià)解集質(zhì)量的指標(biāo)，衡量的是真實(shí)前沿的個(gè)體到所求得的近似解集之間最小距離的平均值。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)值對個(gè)體進(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)個(gè)體，維護(hù)外部存儲集；將其與4種算法在HV和IGD指標(biāo)下進(jìn)行對比實(shí)驗(yàn)。主要得到以下結(jié)論：

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

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

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