进化算法——多目标优化
所有的實際優(yōu)化問題都是多目標(biāo)的，如果不是顯式的至少也是隱式的。接下來討論多目標(biāo)優(yōu)化問題（MOP）如何修改進(jìn)化算法。實際的優(yōu)化問題包含多個目標(biāo)，那些目標(biāo)常常互相沖突。例如：
- 在購買汽車時，我們可能想要車最舒適并且花錢最少。最舒適的汽車太貴，最便宜的汽車又不太舒服。
- 在設(shè)計一座橋時，我們可能想讓它的費用最低強(qiáng)度最大。用泡沫塑料建造的橋可能費用最低，但他非常脆弱。用鈦合金建造的橋可能強(qiáng)度最大但它非常昂貴，在費用和強(qiáng)度之間如何才是最好的折中？
MOP又被稱為多準(zhǔn)則優(yōu)化、多性能優(yōu)化，以及向量優(yōu)化。假定獨立變量x為n維向量，并假定MOP是最小化問題。MOP可以寫成如下的形式：
MOP的目標(biāo)是同時最小化k個函數(shù)。
MOP常常包含約束，我們不處理帶約束的MOP。我們可以將約束融入多目標(biāo)進(jìn)化算（MOEAs），其方式與將約束融入單目標(biāo)進(jìn)化算法相同。
目錄
帕累托最優(yōu)性
?支配
多目標(biāo)優(yōu)化的目標(biāo)
1.超體積
2.相對覆蓋度
基于非帕累托的進(jìn)化算法
1.集結(jié)方法
?凹帕累托前沿的目標(biāo)達(dá)成
2.向量評價遺傳算法
3.字典排序
?4.?-約束方法
?5.基于性別的方法
基于帕累托進(jìn)化算法
1.多目標(biāo)進(jìn)化優(yōu)化器
a.簡單多目標(biāo)進(jìn)化優(yōu)化器（simple evolutionary multi-objective optimizer，SEMO）
b.多樣性多目標(biāo)進(jìn)化優(yōu)化器（divercity evolutionary multi-objective optimizer，DEMO）?
2.基于?的多目標(biāo)進(jìn)化算法
3.非支配排序遺傳算法NSGA
NSGAⅡ
4.多目標(biāo)遺傳算法?
5.小生境帕累托遺傳算法NPGA
6.優(yōu)勢帕累托進(jìn)化算法SPEA
SPEA2
7.帕累托歸檔進(jìn)化策略PAES
基于生物地理學(xué)的多目標(biāo)優(yōu)化
1.向量評價BBO
2.非支配排序BBO
3.小生境帕累托BBO
4.優(yōu)勢帕累托BBO
?
帕累托最優(yōu)性
我們首先列出在多目標(biāo)優(yōu)化中經(jīng)常用到的一些定義。
1.支配。稱點支配x如果下面的兩個條件成立：（1）對所有i∈[1,k]，并且（2）對至少一個j∈[1,k]，＜，即對所有目標(biāo)函數(shù)值，至少與x一樣好，并且至少有一個目標(biāo)函數(shù)值比x好，用記號
表示支配x，符號表示的函數(shù)值小于或等于x的函數(shù)值。
2.弱支配。?稱點弱支配x如果對所有i∈[1,k]，，即對所有目標(biāo)函數(shù)值，至少與x一樣好，如果支配x，它也弱支配x。?如果對所有i∈[1,k]，=， 則與x互相弱支配。用記號
表示?弱支配x。
3.非支配。?稱點是非支配的，如果不存在能支配它的x。非劣、允許的，以及有效的，都是非支配的同義詞。
4.帕累托最優(yōu)點。 帕累托最優(yōu)點，也被稱為帕累托點，是不受搜索空間中任意一點x支配的點。即，
5.帕累托最優(yōu)集。也被稱為帕累托集并記為，是所有非支配的的集合。
6.帕累托前沿。也被稱為非支配集合，并記為，是相應(yīng)于帕累托集的所有函數(shù)向量f(x)的集合。
注意，是非支配的并不意味著支配所有與不等的x。對所有i∈[1,k]，可能會有?=?，在這種情況下x和互相都是非支配的，其中一個不會支配另一個。還可能出現(xiàn)的情況是，以有兩個目標(biāo)的問題為例，其中并且。在這種情況下x和都是非支配的，其中一個不會支配另一個。
支配
帕累托集這個概念的局限在于它的非此即彼，非黑即白的性質(zhì)。例如，考慮下面三個費用函數(shù)值的集合：
x支配y和z，但是帕累托支配的概念并不考慮支配水平之間的差別，也不會識別在目標(biāo)函數(shù)空間中相互靠的很近的兩個候選解。在（11）式中，x支配y，但是因為x和y很相似，相互之間幾乎都是非支配的。實際上，差不多也可以說y支配z。由此引出了支配的概念。
我們用記號
表示?支配x，注意，如果=0，則支配等價于弱支配。
注意，對于＞0，支配是比弱支配更弱的支配，也就是說，如果?弱支配x，則對＞0，?也支配x。反之，如果對某個＞0，?支配x，則?可能弱支配x，可能不能弱支配x：
多目標(biāo)優(yōu)化的目標(biāo)
MOEA可能的一些目標(biāo)如下：
目標(biāo)1和2是要找出真實帕累托集的“最好的”近似，目標(biāo)3是要找出解的多樣化集合，以便讓決策者有足夠的資源做出明智的決定。與其他目標(biāo)不同，目標(biāo)4是要找出與決策者的理想解盡可能接近的解。
目標(biāo)1和2假定我們一開始就知道真實帕累托集。如果知道真實的帕累托集，并且MOEA給出一個近似的帕累托集，可以計算它們之間的平均距離M(，)
?其中||·||是用戶指定的距離測度。
可以用幾種不同的方式度量目標(biāo)3。首先，可以度量每一個個體與近似帕累托集中離他最近的鄰居的平均距離；其次，可以度量在近似帕累托集中兩個末端的個體之間的距離；最后，可以計算在帕累托集中與每個元素距離大于某個閾值的個數(shù)的平均
其中，是用戶指定的距離。一般來說，隨著中元素的個數(shù)的增加而增大，也隨著中元素多樣性的增加而增大。
目標(biāo)4被稱為目標(biāo)向量優(yōu)化，目標(biāo)達(dá)到，或目標(biāo)規(guī)劃。我們通常使用歐氏距離度量目標(biāo)函數(shù)向量f和理想點之間的距離，歐氏距離也被稱為二范數(shù)距離。f和之間的距離定義如下：
?也可以使用其他距離，如加權(quán)二范數(shù)，一范數(shù)，或無窮范數(shù)。
1.超體積
?常用的度量帕累托前沿質(zhì)量的另一個指標(biāo)是它的超體積。假設(shè)MOEA在近似帕累托前沿中找到M個點={}，j∈[1,M]，其中是一個k維函數(shù)。超體積為
對于最小化問題，超體積越小表明帕累托前沿的近似也越好。
?假設(shè)有兩個MOEA，它們都被用來近似一個有兩個目標(biāo)的最小化問題的帕累托前沿。下圖所示為它們的近似帕累托前沿。圖a的近似點為
其超體積為1×5+2×3+5×1=16。圖b的近似點為
其超體積為1×4+3×3+4×1=17.圖a中的比圖b中的稍好。?
?不能盲目的將超體積作為衡量帕累托前沿質(zhì)量的指標(biāo)。（18）式說明一個空的近似帕累托前沿（M=0）得到S可能的最小值。因此，更精確的度量可能是正規(guī)化之后的超體積=/M。但這個量也可能不是近似帕累托前沿的好指標(biāo)。考慮某個近似帕累托前沿，其正規(guī)化后的超體積。現(xiàn)在假設(shè)添加一個新的點到中得到。于是有可能讓＞。盡管和的唯一不同是，比多了一個點。顯然比好，但?＞?與我們的直覺不符。?
因此我們得修改超體積這個測度，不是關(guān)于目標(biāo)函數(shù)空間的原點來計算超體積，而是關(guān)于帕累托前沿之外的參考點來計算。假設(shè)要比較Q個帕累托前沿近似，q∈[1,Q]，首先計算參考點向量r=[]，其中
?然后關(guān)于參考點計算超體積
其中，M(q)是在第q個近似帕累托前沿中點的個數(shù)，是在第q個近似帕累托集中第j個點。參考點超體積S’較大表示最小化問題的帕累托前沿較好。我們可以采用正規(guī)化后的參考點超體積
如果要將帕累托點的個數(shù)也納入指標(biāo)中，也可以采用總的參考點超體積。
2.相對覆蓋度
比較近似帕累托前沿的另一種方式是計算在一個近似中的個體被另一個近似中至少一個個體弱支配的平均個數(shù)。假設(shè)兩個近似記為?和?。定義?相對于?中個體被?中至少一個個體弱支配的平均個數(shù)：
?
注意，。如果=0，則對沒一個個體a2∈??，在??中沒有個體弱支配a2。如果=1，則對每一個個體a2∈??，在?中至少有一個個體弱支配a2。
基于非帕累托的進(jìn)化算法
接下來討論幾種MOEA，它們并不顯示的使用帕累托支配個概念。
1.集結(jié)方法
集結(jié)方法將MOP的目標(biāo)函數(shù)向量組合成一個目標(biāo)函數(shù)。例如，將（1）式中k個目標(biāo)的MOP轉(zhuǎn)換為問題
是權(quán)重參數(shù)的集合，其元素都為正且總和為1。（25）式被稱為加權(quán)和方法，但也可以采用其他的集結(jié)方法。例如，把目標(biāo)組合成一個乘積：
如果采用該方法，就應(yīng)該確保對所有的x，目標(biāo)0。無論用什么方法集結(jié)，其重點在于將MOP轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。
如果帕累托前沿是凹的，集結(jié)方法就無法得到完整的帕累托前沿，我們用下面的例子來說明。
?考慮問題
其中x∈[0,4]，這是一個一維兩個目標(biāo)的MOP，我們可以將兩個目標(biāo)集結(jié)成一個標(biāo)量目標(biāo)
其中w∈[0,1]。下圖為兩個問題的解。我們知道帕累托前沿是凹的，集結(jié)方法正確地給出了帕累托前沿凸起的部分，但凹進(jìn)的部分不正確。
?凹帕累托前沿的目標(biāo)達(dá)成
有時候，通過七屆下面的問題來近似目標(biāo)達(dá)到：
?其中，是第i個目標(biāo)的理想解，是權(quán)重參數(shù)的集合，表示每個目標(biāo)的相對重要性，每一個都是正數(shù)。（33）式允許比用戶的理想解還好的解存在。如果最優(yōu)的α＞0，則不能達(dá)到理想點，但（33）式的解是盡可能靠近理想點的向量解。如果最優(yōu)的α＜0，對于每一個目標(biāo)，就可以找到比理想解更好的解。
2.向量評價遺傳算法
向量評價遺傳算法VEGA是最早的MOEA。VEGA每次使用一個目標(biāo)函數(shù)在種群中選擇。它給出子種群的集合，每個目標(biāo)函數(shù)一個集合。然后從子種群中選擇個體得到下一代的父代，并利用標(biāo)準(zhǔn)進(jìn)化算法的重組方法讓父代組合得到子代。算法1為VEGA的概述。
算法1通常隨機(jī)生成初始化種群。在每一代計算所有N個個體的全部k個費用函數(shù)值。然后用所需的選擇方案選擇M個個體，即子種群。我們根據(jù)概率來選擇每個目標(biāo)函數(shù)的子種群。再生成每個目標(biāo)函數(shù)的子種群之后，將它們組合起來得到父代1種群P。然后將P中的個體重組生成子代集合C。可以采用任何一個進(jìn)化算法進(jìn)行重組。
在單目標(biāo)進(jìn)化算法中實施精英能極大地改善算法性能。在算法1中實施精英的幾種方式。例如，在每一代找到針對每一個目標(biāo)函數(shù)的最好個體，并確保它們能留到下一代；或者可以在每一個直到非支配個體，確保其中至少能有幾個保留到下一代。
3.字典排序
與VEGA類似，它允許用戶對目標(biāo)按優(yōu)先級排序。基于優(yōu)先級的目標(biāo)對個體做比較執(zhí)行錦標(biāo)賽選擇。錦標(biāo)賽選擇也可以基于隨機(jī)的目標(biāo)。
?算法2概述了字典排序方法。在最初的字典排序方法中，最外層的循環(huán)按目標(biāo)函數(shù)的優(yōu)先級對i∈[1,k]執(zhí)行。在它的隨即便種中，則會一直執(zhí)行直到滿足用戶定義的終止準(zhǔn)則，并且在每一代指標(biāo)i會隨機(jī)的變化。
?4.-約束方法
-約束方法每次最小化一個目標(biāo)函數(shù)，同時將其他目標(biāo)函數(shù)限制在給定的閾值內(nèi)。首先，對于i∈[1,k]，通過單目標(biāo)優(yōu)化算法最小化找到目標(biāo)函數(shù)的最小值。于是得到目標(biāo)函數(shù)約束的下界：
然后最小化第一個目標(biāo)同時限制其他目標(biāo)小于某個閾值：
?由（35）式得到的最后的種群作為下一個進(jìn)化算法的初始種群，最小化下一個目標(biāo)：
?對所有k個目標(biāo)重復(fù)這個過程，然后減小值并重復(fù)順序最小化的過程。算法3概述約束MOEA。在實施-約束方法時，MOEA最具挑戰(zhàn)的是算法3如何精確決定“設(shè)為大于的某個數(shù)”以及如何“減小，i∈[1,k]”。
?5.基于性別的方法
?基于性別的方法根據(jù)對目標(biāo)函數(shù)的評價為每一個個體的分配性別。基于性別的方法還利用被稱為檔案的第二種群。檔案也是非支配個體的一個集合，與精英類似，他能避免丟失最好的個體。
在k個目標(biāo)MOP基于性別的方法中，有k個不同的性別，每一個相應(yīng)于不同的目標(biāo)。我們對每個個體生成數(shù)目相同的初始化種群，然后基于從每個性別i選擇一個個體。再用選出的個體重組得到子代個體，按照子代表現(xiàn)得最好的目標(biāo)為子代個體分配性別。在每一代的最后，通常將種群與檔案比較并將非支配個體存入檔案同時去掉檔案中的被支配個體。算法4概述了多目標(biāo)優(yōu)化基于性別的方法。
基于帕累托進(jìn)化算法
下面幾節(jié)討論直接使用帕累托支配的方法。
1.多目標(biāo)進(jìn)化優(yōu)化器
a.簡單多目標(biāo)進(jìn)化優(yōu)化器（simple evolutionary multi-objective optimizer，SEMO）
最初是為二進(jìn)制優(yōu)化提出的算法。在SEMO中，一開始我們隨機(jī)生成個體中群。一開始的種群規(guī)模為1，隨著算法找到越來越多的非支配解，種群也在長大。在每一代，我們從種群中隨機(jī)選出一個個體，讓它變異生成子代。如果這個子代不被種群支配，就將它加入種群中，并去掉種群中被支配的個體。算法5說明SEMO。
b.多樣性多目標(biāo)進(jìn)化優(yōu)化器（divercity evolutionary multi-objective optimizer，DEMO）?
SEMO有一個問題是它的種群會不受限制的生長。我們可以在測試時候?qū)納入種群P時采用支配而不是支配來處理這個問題。由此得到多樣性多目標(biāo)進(jìn)化優(yōu)化器DEMO。DEMO采用的算法和算法5相同，但它使用支配作為是否將y納入P的準(zhǔn)則。這個準(zhǔn)則就是僅當(dāng)y不被P中的其他個體支配是就將y納入當(dāng)前種群。因為支配是比帕累托支配更弱的一種支配。在DEMO中將y納入種群的準(zhǔn)則比在SEMO中更嚴(yán)格。DEMO本質(zhì)上是將目標(biāo)空間分成超箱，并且讓種群在每個超箱中包含的個體最多只有一個。DEMO通常使用加性支配。
對兩個目標(biāo)的優(yōu)化問題，如下圖說明DEMO的概念。我們不會將子代納入種群，因為它被同一個超箱中的個體支配，但會將納入種群因為它不會被當(dāng)前種群中的任何一個成員支配。注意，下圖說的并不是百分百正確，因為DEMO的超箱是相對當(dāng)前種群定義的。
2.基于的多目標(biāo)進(jìn)化算法
-MODE包含一個種群和一個檔案。在每一代，我們從種群中選擇一個個體并在檔案中選擇一個個體，用某種重組方法得到一個子代。
如果子代支配種群中的一個個體，就用子代替換被支配的個體。如果子代支配不止一個個體，則替換隨機(jī)選出的一個個體。
然后將子代與檔案比較。這種比較會出現(xiàn)四種情況：
（1）如果子代被歸檔中的一個個體支配，就不把子代放進(jìn)檔案中。
（2）如果子代支配某個歸檔個體，則將子代添加到檔案，并去掉檔案中的被支配個體。
如果這兩個條件不成立，就計算子代x的-箱B(x)：對于j∈[1,k]
其中，k是目標(biāo)函數(shù)的個數(shù)，是第j個目標(biāo)所需的分辨率。由此得到子代與檔案比較的第三種情況：（3）如果子代x與一個歸檔個體同一個?-箱中，如果子代更接近目標(biāo)函數(shù)的原點，就讓子代替換a：
（4）如果上面的三種情況都沒有出現(xiàn)，就將子代添加到檔案中，檔案規(guī)模加1。
下圖說明了這4種可能性。這里描述的邏輯保證檔案的每個-箱中最多只有一個個體。盡管檔案從一代到另一代會長大，這個邏輯會限制它的增長。
圖（a）說明子代被一個或者多個歸檔支配；在這種情況下，子代不會被納入檔案。圖（b）說明子代支配一個或者多個歸檔個體；在這種情況下，子代被納入檔案，替換被子代支配的個體；圖（c）說明子代和歸檔個體互相非支配，且子代與歸檔個體在同一個?-箱中；在這種情況下，如果子代更接近目標(biāo)函數(shù)空間的原點，子代就替換同一個?-箱中歸檔個體。最后，圖（d）說明子代和檔案互相都是非支配的，并且子代沒有與任何一個歸檔個體在同一個?-箱中；在這種情況下，子代被添加到檔案，檔案規(guī)模加1.
算法6概述?-MOEA。
3.非支配排序遺傳算法NSGA
非支配排序遺傳算法（nondominated sorting genetic algrorithm，NSGA），它基于每一個個體的支配水平為其分配費用。首先將所有的個體復(fù)制給一個臨時種群T。然后找出T中的所有非支配個體；用集合B表示這些非支配個體并未它們分配最低的費用。接下來從T中去掉B并在縮減后的集合T中找出所有非支配個體，為這些個體分配次低的費用。重復(fù)這個過程，就得到基于個體非支配水平的每一個個體的費用。算法7概述NSGA。
NSGAⅡ
?NSGAⅡ是對NSGA的改進(jìn)。?NSGAⅡ在計算個體x費用時不僅考慮支配它的個體而且還考慮它支配的個體。對每一個個體，沿著目標(biāo)函數(shù)的維度找出離它最近的個體，并用它們之間的距離計算擁擠距離。?NSGAⅡ不適用檔案，但使用(μ+λ)進(jìn)化策略實施精英。
?NSGA將每一個個體x的擁擠距離設(shè)置為沿每個目標(biāo)函數(shù)的維度距離它最近的鄰居的平均距離。加入，在?NSGA中有N個個體，進(jìn)一步假設(shè)x的目標(biāo)函數(shù)向量為
對于每個目標(biāo)的維度，找出種群中離得最近的較大值和離得最近的較小值，如下：
然后計算x的擁擠距離：
在目標(biāo)函數(shù)空間中較擁擠的地方擁擠距離往往較小。位于目標(biāo)函數(shù)空間極值處的個體的距離會無窮大：
最大立方體的邊界不會超出x的最近鄰居在每個維度上目標(biāo)函數(shù)空間的坐標(biāo)，擁擠距離應(yīng)該相應(yīng)于最大立方體的邊長的一半。下圖顯示二維目標(biāo)函數(shù)空間中的一個超立方，它是一個矩形。下圖中x在方向上的最近鄰居是A和C，在方向上的最近鄰居是A和B。
最大超立方體（在二維空間中是一個矩形）的周長的1一半為x的擁擠距離，最大立方體的邊界不會超出x的最近鄰居在目標(biāo)函數(shù)空間中的坐標(biāo)。?
既然種群中的每個個體都由一個擁擠距離，我們就把它作為次級排序的參數(shù)得到每一個個體的排名。與NSGA算法一樣，我們基于非支配水平對每一個個體排序，同時還包含基于擁擠距離的一個細(xì)粒度的排名水平。也就是說，如果，或者如果=且d(x)>d(y)，則x的排名比y的好。NSGA算法采用選擇重組父代，而NSGAⅡ則用上述的排名來選擇重組父代。
4.多目標(biāo)遺傳算法?
它基于支配水平分配費用。MOGA從相反的方向解決費用分配。MOGA基于有多少個個體支配x來為他分配費用。我們對所有非支配個體分配相同的費用。對每個被支配個體x，則根據(jù)有多少個個體支配它以及有多少個個體在它附近來分配費用。與NSGAⅡ使用擁擠距離類似，這樣做會促進(jìn)種群的多樣性。
在MOGA中，x的排名比y好（即），如果種群P中支配它的個體較少（即d(x)＜d(y)），或者支配它們的個體數(shù)相同且在目標(biāo)函數(shù)空間靠近x的個體比靠近y的個體少（即s(x)＜s(y)）。這個排名的方法可以表示為
?其中，是用戶定義的參數(shù)，||·||是某個距離測度，可以自動的實現(xiàn)共享，這樣就不需要其他用戶定義共享參數(shù)。算法8概述MOGA。
5.小生境帕累托遺傳算法NPGA
小生境帕累托遺傳算法（NPGA）與NSGA和MOGA類似，它基于支配水平分配費用。NPGA試圖減少NSGA和MOGA的計算量。我們從種群中隨機(jī)選出兩個個體和，然后隨機(jī)選出種群的一個子集S，這個子集通常約占種群的10%。如果其中有一個個體或被S中的某個個體支配，另一不被支配，則記非支配個體為r（r為或中的一個），它贏得錦標(biāo)賽被選出來進(jìn)行重組。如果和這兩個個體都被S中至少一個個體支配，或都不被S中的任何一個個體支配，則用適應(yīng)度分享來決定錦標(biāo)賽的贏家；也就是說，處于目標(biāo)函數(shù)空間中不擁擠區(qū)域中的個體贏得錦標(biāo)賽。這個選擇過程可以描述如下：
?是支配個個體數(shù)，是的擁擠距離，r是我們最后選出來重組的個體（?或?）。
搜索空間或目標(biāo)函數(shù)空間中越擁擠的區(qū)域個體的擁擠距離越小。在NPGA中使用擁擠距離會鼓勵多樣性；它特別適合多模態(tài)問題，或者用戶有意在函數(shù)空間或搜索空間中相距很遠(yuǎn)的區(qū)域找到好的潛在解的那些問題。算法9概述NPGA。
6.優(yōu)勢帕累托進(jìn)化算法SPEA
優(yōu)勢帕累托進(jìn)化算法（strength Pareto evolutionary algorithm，SPEA）是第一個顯式地利用精英的MOEA。精英通常是單目標(biāo)和多目標(biāo)進(jìn)化算法的一個常識性的選擇。如果基于用戶的偏好的方法用與MOEA，并且讓偏好隨時間地變化而變化，精英可能會導(dǎo)致性能退化。
SPEA會把在學(xué)習(xí)過程中找到的所有非支配個體留在檔案中。每當(dāng)找到非支配個體就把它復(fù)制到檔案中。對每個歸檔個體α，基于種群中被α支配的個體數(shù)為其分配優(yōu)勢值S(α)：
其中，P是候選解的集合，N為P的大小，A是檔案的集合。注意，?S(α)∈[0,1）。對P中的每一個個體x，我們找出支配它的的所有歸檔個體的集合α(x)。然后令x的原始費用為α(x)中優(yōu)勢個體的總和，記為R(x)：
在上面的等式加上1能保證R(x)≥1，它反過來保證，對所有x∈P和所有α∈A，R(x)＞S(α)。注意，如果x的原始費用很低，則x是一個高性能個體。
下圖說明優(yōu)勢和原始費用的計算，其中檔案規(guī)模為|A|=3種群規(guī)模|P|=6。下圖顯示帕累托前沿的優(yōu)勢值為它們所支配的個體數(shù)正規(guī)化后的值。此圖也顯示每個被支配的點的原始費用為支配它的帕累托前沿點的優(yōu)勢的總和再加上1。注意，個體越遠(yuǎn)離帕累托前沿（即當(dāng)個體被更多的帕累托前沿支配），原始費用就越大。
帕累托前沿個體用x表示，旁邊顯示的是它們的優(yōu)勢值，非帕累托前沿用實心圓表示，旁邊顯示的是它們的原始費用。例如9/7的點被優(yōu)勢值為2/7的點支配，因此原始費用為2/7+1=9/7。
?在每一代將{P，A}中的非支配個體都加入到檔案A中，但這會讓檔案無限增長。SPEA用聚類來處理這個潛在的問題。如果檔案中有|A|個個體，我們一開始定義一個個體為一個聚類。然后把兩個離得最近的聚類合并為一個聚類，A的聚類個數(shù)減1.重復(fù)這個過程直到檔案中含有個聚類，它是我們想要的檔案規(guī)模。最后，在每一個聚類中留下一個點，通常是離聚類中心點最近的那個點。
SPEA2
SPEA2對SPEA做了醫(yī)學(xué)改進(jìn)。首先，我們不僅為檔案個體分配優(yōu)勢值S(α)，也為種群中的個體分配優(yōu)勢值：
?與（45）式比較，可知上式?jīng)]有對優(yōu)勢值做歸一化處理。
其次，在計算P中每個個體的原始費用時也稍微有點不同，我們將種群和檔案中支配個體的總優(yōu)勢和起來：
?與（46）式比較，上式在計算原始費用時沒有加1。
再次，基于鄰近個體數(shù)修改每個x∈P的原始費用；也就是說，對于目標(biāo)函數(shù)空間中鄰居較多的個體在費用上給予懲罰。對于y≠x的所有x∈P和所有y∈{P,A}，找出f(x)和f(y)之間的距離來懲罰。通常采用歐氏距離。對于每一個x∈P，將它與每一個y∈{P,A}之間的距離按升序排列，得到x的（|P|+|A|）個元素的有序距離列表。然后選擇距離列表中的第j個元素，它是x和距它第j個最近鄰居之間的距離，記為。定義x的密度為
?這列分母需要選擇常數(shù)γ以保證D(x)<1。
最后，將原始費用加到密度上得到修改后x點的費用：
?由（48）式可知，所有非支配個體的原始費用為0，并且對于所有x，D(x)<1，因此所欲非支配個體的費用C(x)<1。
在SPEA中檔案規(guī)模沒有下界，但在SPEA2中檔案規(guī)模保持為一個常值。如果在SPEA2過程中任一點檔案規(guī)模過小，就將種群中費用最低的個體，即使它們是被支配的，納入檔案直到檔案規(guī)模達(dá)到最想要的值。如果檔案規(guī)模過大，就在目標(biāo)函數(shù)空間中通過找出距每個x∈A最近的鄰居：
?由此得到|A|個的值，這里|A|為檔案的規(guī)模。下面我們用D表示具有最小的個體的集合：
D中至少會有兩個個體，因為兩個個體x和y之間的距離與y與x之間的距離相同。在D中的所有個體中，找出距不屬于D的任一歸檔個體最近的個體，記為：
?從檔案中去掉，這樣檔案規(guī)模減1。如果|A|過大，重復(fù)上述過程，在每次迭代中去掉一個個體，直到達(dá)到想要的檔案規(guī)模。
算法10概述了SPEA和SPEA2個基本思想。
7.帕累托歸檔進(jìn)化策略PAES
帕累托歸檔進(jìn)化策略PAES，其動機(jī)來自（1+1）進(jìn)化策略。在每一代，單個個體利用變異生成單個子代。在每一代一個父代生成一個子代，如果子代不被檔案中的個體支配就將它納入檔案。如果檔案規(guī)模超過某個閾值，就通過剔除擁擠距離最小的個體（即在搜索空間或目標(biāo)函數(shù)看空間中最擁擠的個體）修剪檔案。算法11概述一般的PAES。s(α)是α的擁擠距離，對于目標(biāo)函數(shù)空間或搜索域的擁擠區(qū)域中的個體數(shù)。
基于生物地理學(xué)的多目標(biāo)優(yōu)化
1.向量評價BBO
因為BBO以遷移為基礎(chǔ)，多目標(biāo)BBO的遷入以每一個個體的第個目標(biāo)函數(shù)值為基礎(chǔ)，這里是在第i個遷移實驗的隨機(jī)目標(biāo)函數(shù)的指標(biāo)，然后，讓遷出以每一個個體的第個目標(biāo)函數(shù)值為基礎(chǔ)，這里也是一個隨機(jī)目標(biāo)函數(shù)指標(biāo)。由此得到向量評價BBO（VEBBO）算法12。
2.非支配排序BBO
將BBO與NSGA結(jié)合，算法7是NSGA。為了針對BBO修改算法7，只需要將重組語句改為一個BBO的遷移操作。由此得到非支配排序BBO算法（NSBBO），算法13。
3.小生境帕累托BBO
與NSBBO算法類似，為了針對BBO修改算法9，只需要把重組語句改為BBO的遷移操作。因為NPGA已經(jīng)基于非支配選擇了R中的個體，我們可以簡單的對R中的每一個個體以相等的遷移概率選擇遷移操作。由此得到小生境帕累托BBO（NPBBO）算法14。
4.優(yōu)勢帕累托BBO
BBO與SPEA或SPEA2結(jié)合的方法，算法10是SPEA和SPEA2，為了針對BBO修改算法10，需要改變選擇父代和重組方法的語句。用SPEA或者SPEA2的費用來計算遷移率，然后利用這些遷移率實施BBO。從種群P和檔案A中選出父代，這就是優(yōu)勢帕累托BBO(SPBBP)算法15。
?
總結(jié)
以上是生活随笔為你收集整理的进化算法——多目标优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Coffice协同办公管理系统(C#)(
- 下一篇： Excel 2010 VBA 入门 12