基于pareo最優(yōu)的多目標演化算法

基于pareo最優(yōu)的多目標演化算法

1.多目標優(yōu)化問題的概念進化算法作為一種漸進搜索算法，在多目標優(yōu)化領(lǐng)域得到了成功應(yīng)用，并發(fā)展成為一個相對較熱的研究方向。最優(yōu)化問題是工程實踐和科學(xué)研究中主要的問題形式之一,其中,僅有一個目標函數(shù)的最優(yōu)化問題稱為單目標優(yōu)化問題,目標函數(shù)超過一個并且需要同時處理的最優(yōu)化問題稱為多目標優(yōu)化問題(multiobjectiveoptimizationproblems,簡稱MOPs)。對于多目標優(yōu)化問題,一個解對于某個目標來說可能是較好的,而對于其他目標來講可能是較差的,因此,存在一個折衷解的集合,稱為Pareto最優(yōu)解集(Paretooptimalset)或非支配解集(nondominatedset)。起初,多目標優(yōu)化問題往往通過加權(quán)等方式轉(zhuǎn)化為單目標問題,然后用數(shù)學(xué)規(guī)劃的方法來求解,每次只能得到一種權(quán)值情況下的最優(yōu)解。同時,由于多目標優(yōu)化問題的目標函數(shù)和約束函數(shù)可能是非線性、不可微或不連續(xù)的,傳統(tǒng)的數(shù)學(xué)規(guī)劃方法往往效率較低,且它們對于權(quán)重值或目標給定的次序較敏感。進化算法通過在代與代之間維持由潛在解組成的種群來實現(xiàn)全局搜索,這種從種群到種群的方法對于搜索多目標優(yōu)化問題的Pareto最優(yōu)解集是很有用的。2.約束定義多目標優(yōu)化問題又稱為多標準優(yōu)化問題。不失一般性,一個具有n個決策變量,m個目標變量的多目標優(yōu)化問題可表述為其中,x=(x1…xn)∈X?Rn為n維的決策矢量,X為n維的決策空間,y=(y1…ym)∈Y奐Rm為m維目標矢量,Y為m微的目標空間。目標函數(shù)F(x)定義了m個由決策空間向目標空間的映射函數(shù)gi(x)≤0(i=1,2,…,q)定義了q個不等式約束;hj(x)=0,(j=1,2,…,p)定義了p個等式約束。在此基礎(chǔ)上,給出以下幾個重要的定義。定義1(可行解)對于某個x∈X,如果滿足(1)中的約束條件gi(x)≤0,(i=1,2,…,q)和hj(x)=0,(j=1,2,…,p),則稱x為可行解。定義2(可行解集合)由X中的所有的可行解組成的集合稱為可行解集合,記為Xf且Xf?X。定義3(Pareto占優(yōu))假設(shè)XA,XB∈Xf是式(1)所示多目標優(yōu)化問題的兩個可行解,則稱與XB相比,XA是Pareto占優(yōu)的,當(dāng)且僅當(dāng)?i=1,2,…,m,fi(xA)≤fi(xB)∧?j=1,2,…m,fj(xA)<fj(xB)記作xA>xB,也稱為XA支配XB。定義4(Pareto最優(yōu)解)一個解x*∈Xf被稱為Pareto最優(yōu)解(或非支配解),當(dāng)且僅當(dāng)滿足如下條件:定義5(Pareto最優(yōu)解集)Pareto最優(yōu)解集是所有Pareto最優(yōu)解的集合,定義如下:定義6(Pareto前沿面)Pareto最優(yōu)解集P*中的所有Pareto最優(yōu)解對應(yīng)的目標矢量組成的曲面稱為Pareto前沿面PF*:3.主要算法是實現(xiàn)多目標優(yōu)化的多目標優(yōu)化3.1適應(yīng)度共享機制的建立第一代進化多目標優(yōu)化算法以Goldberg的建議為萌芽。1989年,Goldberg建議用非支配排序和小生境技術(shù)來解決多目標優(yōu)化問題。非支配排序的過程為:對當(dāng)前種群中的非支配個體分配等級1,并將其從競爭中移去;然后從當(dāng)前種群中選出非支配個體,并對其分配等級2,該過程持續(xù)到種群中所有個體都分配到次序后結(jié)束。小生境技術(shù)用來保持種群多樣性,防止早熟。Goldberg雖然沒有把他的思想具體實施到進化多目標優(yōu)化中,但是其思想對以后的學(xué)者來說,具有啟發(fā)意義。隨后,一些學(xué)者基于這種思想提出了MOGA,NSGA和NPGA。Fonseca和Fleming在1993年提出了MOGA。該方法對每個個體劃分等級,所有非支配個體的等級定義為1,其他個體的等級為支配它的個體數(shù)目加1。具有相同等級的個體用適應(yīng)度共享機制進行選擇。其適應(yīng)度分配方式按如下方式執(zhí)行:首先,種群按照等級排序,然后,對所有個體分配適應(yīng)度,方法是用Goldberg提出的線性或非線性插值的方法來分配,具有相同等級個體的適應(yīng)度值是一樣的。通過適應(yīng)度共享機制采用隨機采樣進行選擇。MOGA過于依賴共享函數(shù)的選擇,而且可能產(chǎn)生較大的選擇壓力,從而導(dǎo)致未成熟收斂。NSGA也是基于Goldberg的非支配排序的思想設(shè)計的。非支配解首先被確定,然后被分配一個很大的虛擬適應(yīng)度值。為了保持種群的多樣性,這些非支配解用它們的虛擬適應(yīng)度值進行共享。這些非支配個體暫時不予考慮。從余下的種群中確定第二批非支配個體,然后它們被分配一個比先前非支配個體共享后最小適應(yīng)度值還要小的虛擬適應(yīng)度值。這些非支配個體也暫時不予考慮,從余下的種群中確定第三批非支配個體。該過程一直持續(xù)到整個種群都被劃分為若干等級為止。NSGA采用比例選擇來復(fù)制出新一代。NSGA的計算復(fù)雜度為O(mN3),其中,m是目標個數(shù),Ⅳ是種群大小。其計算復(fù)雜度較高,而且需要預(yù)先確定共享參數(shù)。NPGA設(shè)計了基于Pareto支配關(guān)系的錦標賽選擇機制。具體思想如下:隨機地從進化種群中選擇兩個個體,再隨機地從進化群體中選取一個比較集,如果只有其中一個個體不受比較集的支配,則這個個體將被選中進入下一代:當(dāng)它們?nèi)恐浠蛉勘恢溆谠摫容^集時,采用小生境技術(shù)實現(xiàn)共享來選取其中之一進入下一代。算法選取共享適應(yīng)值大的個體進入下一代。該算法中,J、生境半徑的選取和調(diào)整比較困難,還要選擇一個合適的比較集的規(guī)模。第一代進化多目標優(yōu)化算法以基于非支配排序的選擇和基于共享函數(shù)的多樣性保持為其主要特點。在第一代進化多目標優(yōu)化的發(fā)展期間,一些亟需解決的問題也凸顯出來。首先,能否找到替代小生境(共享函數(shù))的方法來保持種群的多樣性。適應(yīng)度共享是由Goldberg和Richardson針對多峰函數(shù)優(yōu)化提出來的,通常需要關(guān)于有限峰數(shù)量的先驗知識和解空間小生境均勻分布的假設(shè)。對于多目標優(yōu)化問題,同樣需要確定共享半徑的先驗信息,其計算復(fù)雜度為種群大小的平方。3.2spea2環(huán)境選擇從20世紀末期開始,進化多目標優(yōu)化領(lǐng)域的研究趨勢發(fā)生了巨大的變化,l999年,Zitzler等人提出了SPEA。該方法使精英保留機制在進化多目標優(yōu)化領(lǐng)域流行起來。第二代進化多目標優(yōu)化算法的誕生就是以精英保留策略的引入為標志。在進化多目標優(yōu)化領(lǐng)域,精英保留策略指的是采用一個外部種群(相對于原來個體種群而言)來保留非支配個體。SPEA是Zitzler和Thiele在1999年提出來的算法。在該算法中,個體的適應(yīng)度又稱為Pareto強度,非支配集中個體的適應(yīng)度定義為其所支配的個體總數(shù)在群體中所占的比重,其他個體的適應(yīng)度定義為支配它的個體總數(shù)加1,約定適應(yīng)度低的個體對應(yīng)著較高的選擇概率。除了進化種群以外,還設(shè)置了一個保存當(dāng)前非支配個體的外部種群,當(dāng)外部種群的個體數(shù)目超過約定值時,則用聚類技術(shù)來刪減個體。采用錦標賽選擇從進化群體和外部種群中選擇個體進入交配池,進行交叉、變異操作。該算法的計算復(fù)雜度高達種群大小的立方。SEPA2是Zitzler和Thiele在2001年提出的對SPEA的改進版本。他們在適應(yīng)度分配策略、個體分布性的評估方法以及非支配解集的更新三個方面進行了改進。在SPEA2中,個體的適應(yīng)度函數(shù)為f)=R(f)+D(f),其中,R(i)同時考慮到個體i在外部種群和進化種群中的個體支配信息09(0是由個體i到它的第k個鄰近個體的距離決定的擁擠度度量。在構(gòu)造新群體時,首先進行環(huán)境選擇,然后進行交配選擇。在進行環(huán)境選擇時,首先選擇適應(yīng)度小于1的個體進入外部種群,當(dāng)這些個體數(shù)目小于外部種群的大小時,選擇進化種群中適應(yīng)度較低的個體;當(dāng)這些個體數(shù)目大于外部種群的大小時,則運用環(huán)境選擇進行刪減。在交配選擇中,運用錦標賽機制選擇個體進入交配池。SPEA2引入了基于近鄰規(guī)則的環(huán)境選擇,簡化了SPEA中基于聚類的外部種群更新方法。雖然其計算復(fù)雜度仍為種群規(guī)模的立方,但是,基于近鄰規(guī)則的環(huán)境選擇得出的解分布的均勻性是很多其他方法無法超越的。PAES采用(1+1)進化策略對當(dāng)前一個解進行變異操作,然后對變異后的個體進行評價,比較它與變異前個體的支配關(guān)系,采用精英保留策略保留其中較好的。該算法的經(jīng)典之處在于引進了空間超格的機制來保持種群的多樣性,每一個個體分配進一個格子。該算法的時問復(fù)雜度為O(Nx),其中,Ⅳ為進化種群的大小,為外部種群的大小。該算法的空間超格的策略被以后許多進化多目標算法所采。隨后,Come等人基于這種空間超格的思想提出了PESA。PESA設(shè)置了一個內(nèi)部種群和一個外部種群,進化時將內(nèi)部種群的非支配個體并入到外部種群中,當(dāng)一個新個體進入外部種群時,同時要在外部種群中淘汰一個個體,具體的方法是在外部種群中尋找擁擠系數(shù)最大的個體并將其刪除,如果同時存在多個個體具有相同的擁擠系數(shù),則隨機地刪除一個。一個個體的擁擠系數(shù)是指該個體所對應(yīng)的超格中所聚集個體的數(shù)目。Come等人在2001年對PESA作了進一步改進。稱為PESA-II,提出了基于區(qū)域選擇的概念,與基于個體選擇的PESA相比,PESA。II用網(wǎng)格選擇代替?zhèn)€體選擇,在一定程度上提高了算法的效率。NSGA—II是2002年Deb等人對其算法NSGA的改進,它是迄今為止最優(yōu)秀的進化多目標優(yōu)化算法之一,NSGA-II具有以下優(yōu)點:(1)新的基于分級的快速非支配解排序方法將計算復(fù)雜度由O(mN3)降到O(mN2),其中,m表示目標函數(shù)的數(shù)目、N表示種群中個體的數(shù)目。(2)為了標定快速非支配排序后同級中不同元素的適應(yīng)度值,同時使當(dāng)前Pareto前沿面中的個體能夠擴展到整個Pareto前沿面,并盡可能地均勻遍布。該算法提出了擁擠距離的概念,采用擁擠距離比較算子代替NSGA中的適值度共享方法,擁擠距離的時間復(fù)雜度為O(m(2N)log(2N))。(3)引入了精英保留機制,經(jīng)選擇后參加繁殖的個體所產(chǎn)生的后代與其父代個體共同競爭來產(chǎn)生下一代種群,因此有利于保持優(yōu)良的個體,提高種群的整體進化水平。NSGA-Ⅱ,SPEA2和PESA-Ⅱ是第二代進化多目標優(yōu)化的主要經(jīng)典算法,該時期的算法以精英保留策略為主要特征,并且大多數(shù)算法不再以適應(yīng)度共享的小生境技術(shù)作為保持種群多樣性的手段,一些更好的策略被提出來,比如基于聚類的方法、基于擁擠距離的方法、基于空間超格的方法等。4.付款時4.1工程領(lǐng)域各領(lǐng)域的應(yīng)用現(xiàn)實生活中,大量的MOEA研究成果,已被應(yīng)用到許多領(lǐng)域。根據(jù)現(xiàn)有的參考文獻,可分為:工程、工業(yè)和科學(xué)三大領(lǐng)域。工程領(lǐng)域的重要應(yīng)用有:電子工程、水力工程、結(jié)構(gòu)工程、航空工程、機器人和控制等;工業(yè)領(lǐng)域中的應(yīng)用有:設(shè)計與制造、調(diào)度與管理;科學(xué)領(lǐng)域的應(yīng)用包括化學(xué)、物理、藥學(xué)、計算機科學(xué)等眾多學(xué)科研究與實踐環(huán)節(jié)。4.2如何確定最優(yōu)的規(guī)模和算法停止準則每個時代的算法都是受當(dāng)時所處的研究水平限制的:第一代進化多目標優(yōu)化算法面臨的問題是如何將進化算法與多目標優(yōu)化問題有機地結(jié)合,第二代則開始考慮算法的效率問題,而當(dāng)前一段時間研究者們在進一步提高算法效率的同時,面臨著如何處理高維多目標優(yōu)化的難題。進化多目標優(yōu)化算法也存在一些有待解決的難題,主要體現(xiàn)在以下兩個方面:首先,如果進化多目標優(yōu)化算法采用小規(guī)模種群,則對于一些復(fù)雜的多目標優(yōu)化問題,將很難收斂到理想Pareto前沿面,而且很難獲得均勻分布的Pareto最優(yōu)解。因此,如何根據(jù)問題的復(fù)雜度自適應(yīng)地調(diào)整種群的規(guī)模是需要進一步研究的問題。根據(jù)非支配解在當(dāng)前種群中所占的比率來自適應(yīng)地調(diào)整種群規(guī)?；蛟S是解決該問題的一個可行方向。此外,如何設(shè)計有效的算法停止準則也是進化多目標優(yōu)化的一個基礎(chǔ)理論難題之一。迄今為止,還很難明確地判斷算法進化到某一代已經(jīng)達到了最優(yōu)或者說可以停止。在單目標優(yōu)化過程中,當(dāng)種群中個體的適應(yīng)度值在一定代數(shù)內(nèi)沒有提高時,可以認定算法可以停止,這種停止策略是不能簡單地應(yīng)用于多目標優(yōu)化的,因為多目標優(yōu)化要得到的不是一個解,而是P