基于R2指標的擬態物理學約束多目標優化算法

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

(1.太原科技大學 應用科學學院， 太原 030024； 2.太原科技大學 機械工程學院， 太原 030024)

1 引言

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

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

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

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

2 約束多目標優化問題

一般地,約束多目標優化問題的數學模型可以被描述為：

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

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

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

(1)

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

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

1pareto支配

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

2Pareto最優解集

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

(2)

3Pareto前沿

Pareto最優解集中每個解對應的目標值向量組成的集合稱為Pareto前沿。

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

3 擬態物理學算法

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

文獻[5]中利用擬態物理學的思想處理全局優化問題，提出一種新的優化算法APO。該方法本質上是通過對牛頓第二定律的模擬，將問題可行域中采樣的個體粒子看作是物理中的質點，在粒子之間虛構一種相互作用力，給出該作用力的計算規則，結合個體的速度和位移更新粒子的運動，實現對整個種群的控制。

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

(3)

式中：、分別表示最優、最差適應值的位置。

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

(4)

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

(5)

式中，為引力因子。

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

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

(6)

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

(7)

式中：∈(0,1)為慣性權重；為分布在區間[0，1]上的一個隨機數；∈[,]；∈[,]。

4 R2-ICRMOAPO算法

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

4.1 R2指標

R2指標是基于效用函數，區分候選解的優劣，從而選擇效用較大的候選解，最初被用于評價2組個體的相對質量。利用具有特定參考點的標準加權切比雪夫函數，可以用該指標相對于參考點來評估單個個體集合的質量。因R2指標可以綜合評價種群的收斂性和多樣性,并可以通過快速計算獲得均勻分布的解集,已被應用于求解多目標優化問題。

在此利用加權切比雪夫函數作為R2指標的效用函數，通過一組個體(集合)和參考點對個體的質量進行評價：

(8)

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

如果效用函數集中每個函數由于不同的權重向量而確定,則個體的R2指標的貢獻值被定義為：

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

(9)

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

4.2 R2-ICRMOAPO算法基本思想

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

1) 個體序值

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

()=1+()

(10)

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

2) 鄰域半徑

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

定義個體的鄰域為該個體半徑內所包含的區域。為了避免算法中鄰域半徑過小，故將鄰域半徑定義為：

(11)

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

3) 鄰域擁擠度

鄰域擁擠度是指在個體間支配與被支配的作用下所計算出某個個體在對應鄰域半徑區域內所包含個體數量的大小。

當出現序值大小相同，鄰域擁擠度也相同的個體時，將鄰域半徑重新調整。若調整后，具有相同序值的個體在相應鄰域半徑內還包含相同的個體數量，將這些個體隨機進行排列，分配編號即可。

4) 質量函數

為了考慮個體間的支配關系和個體所處鄰域半徑內的擁擠程度，并充分體現多目標優化問題本身的特點，將質量函數定義為：

(12)

5) 引力因子

引力因子是影響算法性能的重要因素之一，在一定程度上會決定種群做收斂運動的個體數量。在標準APO算法中，將引力因子規定為10。R2-ICRMOAPO算法為了使引力因子隨種群的進化而產生動態的變化，將其進行改進，令為：

(13)

式中：和為引力因子的初始值和終值，由經驗可知，算法中=70，迭代到最后，的終取值為=1；為迭代次數；為最大迭代次數。

6) 慣性權重

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

在R2-ICRMOAPO算法中采用線性遞減的慣性權重，使慣性權重隨著迭代的進行而動態減小：

(14)

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

7) 不可行度

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

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

(15)

式中:、分別為多目標優化問題的不等式約束和等式約束。當為可行解時，不可行度為0。

4.3 R2-ICRMOAPO算法流程

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

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

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

Step 1：初始化種群：種群規模，外部存儲集規模archivesize，權重向量，最大迭代次數，隨機產生所有個體的初始速度和位置，初始化參考點。

Step 2：計算所有個體在每個目標下的適應度值，確定非支配個體，存儲于archive集。對非支配個體的序值定義為1，其余個體的序值定義為+1。

Step 3：對archive集中的非支配個體計算R2指標貢獻值，按降序原則進行排序。

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

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

Step 6：出現鄰域半徑內包含相同個體數量的同序值個體時，將該個體標記為()=1。

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

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

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

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

Step 11：確定新的非支配個體，更新archive集，當archive集中都是非支配個體時，對所有個體計算CR2值，按照降序原則進行排序，若個體數量超過archive集規模時，將archive集中R2指標貢獻值較小的個體刪除，直到個體數量滿足設定的規模，獲得新的archive集。

Step 12：若達到最大迭代次數則退出，否則返回步驟5。

5 實驗結果與分析

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

本文選定的測試函數如表1所示。

表1 約束多目標標準測試函數Table 1 Constrained multi-objective standard test functions

實驗中，設定種群規模和外部存儲集規模均為100，進化代數為50。圖2～圖4表示算法R2-ICRMOAPO、ICRMOAPO、R2MOPSO、NSGAII、和ε-MOEA對測試函數生成的Pareto前沿和真實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

大多數研究使用逼近實際解決方案的程度和設置解決方案的分布情況來測量多目標優化算法的性能。本文采用HV和IGD算法性能指標對5種算法進行對比。

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

(16)

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

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

(17)

對測試函數進行了100次獨立實驗后，表2～表3分別展示了5種算法關于HV和IGD性能指標的平均值、最優值和方差。此外，還采用統計學Wilcoxon秩和檢驗來表明結果的顯著性水平，顯著性差異水平為0.05，如果值大于0.05，則表示2種算法之間沒有明顯差異。

表2 測試函數的HV指標值Table 2 HV performance indicators on test functions

表3 測試函數的IGD指標值Table 3 IGD performance indicators on test functions

從表2和表3可以看出，R2-ICRMOAPO算法的HV值高于ICRMOAPO算法，且IGD值低于ICRMOAPO算法。數據表明，利用R2指標貢獻值對個體進行篩選，提高了算法的收斂性和分布性。

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

6 結論

在APO算法的基礎上，針對約束多目標優化算法，構造基于R2指標的多目標約束優化算法，將非支配排序和R2指標結合，利用R2指標貢獻值區分候選解的優劣，更新最優個體，維護外部存儲集；將其與4種算法在HV和IGD指標下進行對比實驗。主要得到以下結論：

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

2) 設計R2指標貢獻值選擇個體，對外部存儲集進行維護和更新，增強了種群的分布，在處理約束多目標問題中取得較好的效果。

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