外文翻譯---一種基于樹結(jié)構(gòu)的快速多目標(biāo)遺傳算法

1、<p><b>　　附錄4</b></p><p>　　一種基于樹結(jié)構(gòu)的快速多目標(biāo)遺傳算法</p><p><b>　　介紹：</b></p><p>　　一般來講，解決多目標(biāo)的科學(xué)和工程問題，是一個(gè)非常困難的任務(wù)。在這些多目標(biāo)優(yōu)化問題(MOPS)中，這些目標(biāo)往往在一個(gè)高維的問題空間發(fā)生沖突，而且多目標(biāo)優(yōu)化也需要

2、更多的計(jì)算資源。一些經(jīng)典的優(yōu)化方法表明將多目標(biāo)優(yōu)化轉(zhuǎn)化成為單目標(biāo)優(yōu)化問題，其中許多運(yùn)行被要求找到多個(gè)解決方案。這使得一種算法返回一組候選解，這比只返回一個(gè)基于目標(biāo)的權(quán)重解的算法更好。由于這個(gè)原因，在過去20年中，人們?cè)絹碓礁信d趣把進(jìn)化算法(EAs)應(yīng)用到多目標(biāo)優(yōu)化中。</p><p>　　許多多目標(biāo)進(jìn)化算法(MOEAs)已經(jīng)被提出，這些多目標(biāo)進(jìn)化算法使用Pareto占優(yōu)的概念來引導(dǎo)搜索，并返回一組非支配解作為結(jié)果

3、。與在單目標(biāo)優(yōu)化中找到最優(yōu)解作為最終的解不同，在多目標(biāo)優(yōu)化中有二個(gè)目標(biāo)：（1）收斂到Pareto最優(yōu)解集（2）在Pareto最優(yōu)解集中保持解的多樣性。為了解決在多目標(biāo)優(yōu)化中這兩個(gè)有時(shí)候會(huì)沖突的任務(wù)，許多策略和方法被提出。這些方法的一個(gè)共同的問題是，它們往往是錯(cuò)綜復(fù)雜的。對(duì)于這兩項(xiàng)任務(wù)，為了得到更優(yōu)秀的解，一些復(fù)雜的策略通常被使用，并且許多參數(shù)需要依據(jù)經(jīng)驗(yàn)和已經(jīng)得到的問題信息進(jìn)行調(diào)整。另外，許多多目標(biāo)進(jìn)化算法有高達(dá)的計(jì)算復(fù)雜度或者需要更多

4、的處理時(shí)間（G是代數(shù)，M是目標(biāo)函數(shù)的數(shù)量，N是種群大小。這些符號(hào)在下文也保持相同的含義）。</p><p>　　在這篇文章中，我們提出了一種基于樹結(jié)構(gòu)的快速多目標(biāo)遺傳算法。(這個(gè)數(shù)據(jù)結(jié)構(gòu)是一個(gè)二進(jìn)制樹，它保存了在多目標(biāo)優(yōu)化中解的三值支配關(guān)系 （例如，正在支配、被支配和非支配），因此，我們命名它為支配樹(DT)。由于一些獨(dú)特的性能，使支配樹能夠含蓄地包含種群個(gè)體的密度信息，并且很明顯地減少了種群個(gè)體之間的比較。計(jì)算

5、復(fù)雜度實(shí)驗(yàn)也表明，支配樹是一種處理種群有效的工具?；谥錁涞倪M(jìn)化算法(DTEA)統(tǒng)一了在支配樹中的收斂性和多樣性策略，即多目標(biāo)進(jìn)化算法中的兩個(gè)目標(biāo)，并且由于只有幾個(gè)參數(shù)，這種算法很容易操作。另外，基于支配樹的進(jìn)化算法(DTEA)使用了一種特別設(shè)計(jì)的基于支配樹(DT)的消除策略。這種策略不僅維護(hù)自然種群的多樣性，但也意識(shí)到精英主義沒有額外的消耗。六個(gè)基準(zhǔn)測(cè)試函數(shù)和三個(gè)著名的MOEAs（如NSGA-II，SPEA2，和Jensen的改進(jìn)版

6、本的NSGA-II）被用來檢驗(yàn)DTEA算法的效率和效果。程序運(yùn)行時(shí)間實(shí)驗(yàn)表明，DTEA算法總是遠(yuǎn)遠(yuǎn)快于基準(zhǔn)算法，尤其是在人口規(guī)模很大的時(shí)候。另一方面，通過檢測(cè)三個(gè)評(píng)價(jià)解質(zhì)量的標(biāo)準(zhǔn)，我們發(fā)現(xiàn)，整體上對(duì)于收斂到真正Pareto最優(yōu)前沿和維護(hù)種群多樣性來講，DT</p><p><b>　　概述MOEAs</b></p><p>　　本節(jié)簡要調(diào)查當(dāng)代MOEA研究。第一部分將

7、給出在本文中使用的一些概念。第二部分將簡要分析當(dāng)前最先進(jìn)的多目標(biāo)進(jìn)化算法。</p><p>　　2.1在多目標(biāo)優(yōu)化中的定義</p><p>　　許多研究人員都給出了類似的定義。我們?cè)谶@介紹兩個(gè)重要概念的定義。為了不是一般性，我們?cè)诒疚闹兄豢紤]最小化問題，它很容易將一個(gè)最大化問題轉(zhuǎn)換成一個(gè)最小化問題。</p><p>　　定義1：一般的多目標(biāo)優(yōu)化：一般來說，最小化一組

8、多目標(biāo)優(yōu)化函數(shù)，約束函數(shù)（是決策變量空間）一個(gè)多目標(biāo)優(yōu)化的解可以使m維的目標(biāo)向量的一部分達(dá)到最小，其中是空間的n維決策變量向量。</p><p>　　定義2：Pareto占優(yōu)：一個(gè)向量是占優(yōu)向量（記作），當(dāng)且僅當(dāng)部分小于，即 ，并且 。</p><p>　　當(dāng)前，大多數(shù)多目標(biāo)優(yōu)化的研究都是基于Pareto占優(yōu)。（在一些文獻(xiàn)中，Pareto占優(yōu)也被定義為嚴(yán)格的，這里我們并不討論他們的區(qū)別。）

9、一個(gè)決策變量向量被稱作Pareto最優(yōu)解，當(dāng)且僅當(dāng)不存在，使得。所有Pareto最優(yōu)決策向量被稱為Pareto最優(yōu)解集。相應(yīng)的目標(biāo)向量解集被稱作非支配集，或者Pateto前沿。根據(jù)Pareto占優(yōu)的定義，我們可以發(fā)現(xiàn)在MOPs和SOPs的解之間的關(guān)系中一個(gè)截然不同的差異。SOPs的解在目標(biāo)空間中是標(biāo)量數(shù)字，并且它們的關(guān)系有兩種可能性：小于和大于（包含等于，為了簡單起見，經(jīng)常稱之為大于）。然而，MOPs的解是向量，并且它們之間的關(guān)系有三種

10、可能：，和非支配。這些差異要求MOEAs要有更復(fù)雜的適應(yīng)度評(píng)價(jià)規(guī)則。</p><p>　　2.2先進(jìn)的MOEAs</p><p>　　一個(gè)良好的MOEA必須滿足以下兩個(gè)點(diǎn)：</p><p>　?。?）得到的非支配集要收斂到真正的Pareto最優(yōu)前沿；</p><p>　?。?）一個(gè)均勻分布的解決方案是可取的。</p><p

11、>　　這兩個(gè)目標(biāo)往往是大多數(shù)MOEAs的性能指標(biāo)。許多方法被設(shè)計(jì)用來滿足這兩個(gè)目標(biāo)。為了解決第一個(gè)方面，一個(gè)基于Pareto的適應(yīng)度評(píng)價(jià)方法通常被設(shè)計(jì)為指導(dǎo)朝向真正Pareto前沿進(jìn)行搜索。其基本思想是根據(jù)它們的支配關(guān)系對(duì)解進(jìn)行排序。Goldberg第一次提出了一個(gè)普遍的方法，解集按照不同的支配序分成不同的前沿。Fonseca和Fleming提出了一種方法，在這種方法中，一個(gè)解集的支配序被解的數(shù)量和當(dāng)前支配它的種群賦值。另一個(gè)排序

12、在SPEA2中被提出，在這種方法中，每一個(gè)個(gè)體都被分配一個(gè)強(qiáng)度值。對(duì)于第二方面中，一些成功的多目標(biāo)進(jìn)化算法提供的密度估計(jì)方法以保存種群的多樣性。Pareto小生境和適應(yīng)度共享技術(shù)在許多多目標(biāo)進(jìn)化算法中得到廣泛地使用，例如，在NSGA，NPGA和MOGA中。在SPEA2中，第k個(gè)最近鄰密度估算方法被應(yīng)用于獲得每一個(gè)個(gè)體的密度指數(shù)，NSGA-II的定義了一個(gè)新的密度估計(jì)度量，它不需要任何用戶定義的參數(shù)。另一種流行的策略是使用超網(wǎng)格把目標(biāo)空間

13、劃分成單元格。此外，一個(gè)新的ε-eliminating多樣性的方法也被提出。最近，一些新的進(jìn)化范例成功應(yīng)用于多目標(biāo)優(yōu)化，例如，粒子群</p><p>　　另一方面，許多多目標(biāo)進(jìn)化算法耗時(shí)。由于與單目標(biāo)優(yōu)化相比，多目標(biāo)有優(yōu)化通常是一個(gè)難計(jì)算的問題（比如三值關(guān)系），所以，由于大多數(shù)發(fā)表的多目標(biāo)進(jìn)化算法有高計(jì)算的需求。還有一種解釋是MOEA的研究往往忽略了問題的計(jì)算復(fù)雜性，幸運(yùn)的是，許多研究人員已經(jīng)開始注意到這個(gè)問題。

14、Deb等人提出了一種快速非支配排序算法來減少計(jì)算復(fù)雜度，在NSGA-II算法中，非支配排序的計(jì)算復(fù)雜度從降到。Jensen系統(tǒng)地分析許多當(dāng)代多目標(biāo)進(jìn)化算法的計(jì)算復(fù)雜度，并提出了一些有效的非支配排序算法。此外，為了減小難度，一些數(shù)據(jù)結(jié)構(gòu)也被引入。四叉樹被檢驗(yàn)作為把精英個(gè)體存儲(chǔ)到非支配解中，</p><p>　　這個(gè)不可約的支配圖(IDG)被提出以用來管理種群。為了促進(jìn)帶精英策略的非支配排序，引入被支配和非支配的樹結(jié)

15、構(gòu)。這些新算法和數(shù)據(jù)結(jié)構(gòu)在某些程度上加快了適應(yīng)度評(píng)價(jià)的處理。然而，它仍然需要進(jìn)一步調(diào)查這個(gè)重要問題并且設(shè)計(jì)簡單而又有效的適應(yīng)度評(píng)價(jià)方法。</p><p>　　基于支配樹的進(jìn)化算法</p><p><b>　　3.1支配樹</b></p><p>　　3.1.1支配樹的結(jié)構(gòu)</p><p>　　正如我們所知道的，適用度評(píng)價(jià)

16、是多目標(biāo)進(jìn)化算法的重要組成部分，它高度影響算法的性能；并且它在處理時(shí)間上非常耗時(shí)。大多數(shù)基于Pareto的適應(yīng)度評(píng)價(jià)要求每個(gè)解應(yīng)該與其他大量的解進(jìn)行比較，這使得大多數(shù)的MOEAs計(jì)算復(fù)雜度限制在。請(qǐng)注意因子意味著隨著種群數(shù)量的增長，使得計(jì)算復(fù)雜度增加非?？?。然而，在許多情況下，MOEAs使用種群規(guī)模非常大的，特別是當(dāng)相互沖突的目標(biāo)非常多的時(shí)候。因此，這種困難需要解決。</p><p>　　通過分析一些常用的適應(yīng)度

17、評(píng)價(jià)處理過程，我們可以發(fā)現(xiàn)在這些過程中有很多不必要的比較。個(gè)體之間的占優(yōu)關(guān)系可以在一個(gè)圖中看出，每個(gè)節(jié)點(diǎn)代表一個(gè)個(gè)體并且每條邊代表相鄰節(jié)點(diǎn)之間的關(guān)系。例如，圖1顯示了五個(gè)節(jié)點(diǎn)之間的占優(yōu)關(guān)系。我們我們直觀地觀察可能有一些冗余的關(guān)系在圖1(b)。減少這些冗余的關(guān)系可能是一個(gè)有效的策略來減少適應(yīng)度評(píng)價(jià)的計(jì)算復(fù)雜度。</p><p>　　因?yàn)镻areto占優(yōu)關(guān)系是可傳遞的，一些關(guān)系可以基于現(xiàn)有的關(guān)系來推導(dǎo)。以圖1為例，如

18、果我們知道N4 Pareto占優(yōu)N3，N3 Pareto占優(yōu)N2，，那么不用通過比較我們也可以得出N4 Pareto占優(yōu)N2。因此，N4與N2之間的比較可以避免。我們也注意到了另一個(gè)現(xiàn)象，我們只需要獲得種群中每一代的Pareto最優(yōu)解集，即使那些占優(yōu)的解仍然對(duì)于進(jìn)化過程有用。這樣的原因是決策者經(jīng)?；谧顑?yōu)解做出決定，而不在其他解上花費(fèi)更多的功夫。也正是由于這個(gè)原因，許多解之間的關(guān)系(例如，解之間的占優(yōu)關(guān)系)是不必要的知道，因此這些關(guān)系可

19、以去除。在圖1（b）這個(gè)示例中，很明顯N1和N4構(gòu)成Pareto最優(yōu)解集。我們可以觀察N4占優(yōu)N3，N1占優(yōu)N2。因此，我們并不對(duì)N2和N3之間的關(guān)系感興趣并且這可能不值得花費(fèi)時(shí)間來比較或推斷它們。通過以上分析，我們能找到兩個(gè)原則來減少不必要的計(jì)算時(shí)間： （1）避免冗余比較（例如依靠推理來推斷這些關(guān)系）；（2）只保留必要的關(guān)系（即，忽略那些不是非常重要的關(guān)系）</p><p>　　正如我們提到的，不同于SOPs的

20、解之間的關(guān)系，MOPs的解有三值關(guān)系。它可以歸納成一個(gè)叫做的函數(shù)。</p><p><b>　　定義3：的函數(shù)</b></p><p>　　這個(gè)函數(shù)是一個(gè)三值函數(shù)。當(dāng)?shù)哪繕?biāo)向量占優(yōu)的目標(biāo)向量，；當(dāng)?shù)哪繕?biāo)向量占優(yōu)的目標(biāo)向量；當(dāng)、互不占優(yōu)時(shí)，。我們知道，對(duì)于排列標(biāo)量數(shù)的二值關(guān)系來說，二進(jìn)制排列樹（BST）是一個(gè)非常有效的工具。在二進(jìn)制排列樹中，一個(gè)節(jié)點(diǎn)的左子樹所連接的節(jié)點(diǎn)

21、其值小于它本身，一個(gè)節(jié)點(diǎn)的右子樹所連接的節(jié)點(diǎn)其值大于它本身。我們考慮多目標(biāo)優(yōu)化的三值的關(guān)系也可以被存儲(chǔ)在一個(gè)擴(kuò)展的二叉樹</p><p><b>　　中。</b></p><p>　　接下來是作者早期在Ref工作時(shí)提出來的關(guān)于結(jié)構(gòu)樹的思想，為此目的，我們?cè)O(shè)計(jì)了一個(gè)特殊的二叉樹。圖2中的一個(gè)例子表明圖1中節(jié)點(diǎn)之間的關(guān)系。在圖中，Pareto最優(yōu)解集是{N1、N4}，主要

22、的關(guān)系被保留，許多不重要的關(guān)系（例如，被支配節(jié)點(diǎn)之間的關(guān)系）被忽略。作為一個(gè)新型的二叉樹，我們稱之為支配樹。</p><p>　　定義4：支配樹(DT)。一個(gè)支配樹是一種二叉樹，定義如下。</p><p>　　1)一個(gè)支配樹一個(gè)外部節(jié)點(diǎn)或者一個(gè)內(nèi)部節(jié)點(diǎn)，其連接到被稱為左子樹節(jié)點(diǎn)和右子樹節(jié)點(diǎn)的一對(duì)支配樹上。</p><p>　　2)每個(gè)節(jié)點(diǎn)在支配樹有中四個(gè)域：id

23、、計(jì)數(shù)器、左連接和右連接。其中，個(gè)體節(jié)點(diǎn)代表id域表示所代表的哪個(gè)個(gè)體節(jié)點(diǎn)，計(jì)數(shù)器域表示左子樹的大?。òㄋ约海?，左連接域連接到其左子樹，該節(jié)點(diǎn)占優(yōu)它的左子樹的根節(jié)點(diǎn)，右連接域連接到它的右子樹，該節(jié)點(diǎn)不占優(yōu)它的右子樹的根節(jié)點(diǎn)。</p><p>　　DT的定義與BST的定義相似，DT和BST也擁有近似的性能。例如，在DT和BST中，一個(gè)節(jié)點(diǎn)的子代是它左子樹的根節(jié)點(diǎn)；相應(yīng)地，這個(gè)節(jié)點(diǎn)是父代節(jié)點(diǎn)。DT也還有一些不同的

24、特點(diǎn)。一個(gè)新術(shù)語“同級(jí)鏈”在DT中被使用。DT的同級(jí)鏈被定義為由它的根節(jié)點(diǎn)和它的右連接節(jié)點(diǎn)構(gòu)成的鏈條。因?yàn)槊總€(gè)DT只有一個(gè)根節(jié)點(diǎn)，DT根節(jié)點(diǎn)的同級(jí)鏈有時(shí)在下面章節(jié)的部分被簡單地叫做DT的同級(jí)鏈。通過跟蹤右連接域，可以獲得同級(jí)鏈。以圖2為例，N1和N4構(gòu)成DT的同級(jí)鏈，其根節(jié)點(diǎn)是N4。此外，N3和N5也構(gòu)成DT的同級(jí)鏈，其根節(jié)點(diǎn)是N3。值得注意的是，雖然具有相同的名字，在DT中一個(gè)節(jié)點(diǎn)的左子樹和右子樹與在傳統(tǒng)的BST中一個(gè)節(jié)點(diǎn)的左子樹和右