姓名:劉一婷酱固;學號:20021210599帝璧;學院:電子工程學院
轉(zhuǎn)自https://blog.csdn.net/sinat_33231573/article/details/80271522
【嵌牛導讀】
在實際問題中大都具有多個目標且需要同時滿足群井,即在同一問題模型中同時存在幾個非線性目標妆够,而這些目標函數(shù)需要同時進行優(yōu)化處理炭臭,并且這些目標又往往是互相沖突的晤郑,進化算法的特性往往能很好的解決此類問題敌呈。
【嵌牛鼻子】多目標,進化算法
【嵌牛提問】多目標優(yōu)化和多任務(wù)優(yōu)化的區(qū)別造寝?
【嵌牛正文】
1磕洪、多目標優(yōu)化的基本概念
多目標優(yōu)化問題(MOP)可以被表示為:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?subject to?
其中,,Ω是決策空間析显,
由m個目標函數(shù)組成,
稱為目標空間签赃」纫欤可達到的目標集合被定義為
。很多時候锦聊,由于目標彼此矛盾歹嘹,Ω中的任何一點都不能同時最大化所有目標,所以我們必須平衡這些目標孔庭。目標之間的最佳折衷解可以根據(jù)Pareto最優(yōu)性來定義尺上。
Pareto支配:
Pareto最優(yōu)解:
Pareto最優(yōu)解集:
Pareto前沿面:
2、多目標進化算法的基本流程
多目標進化算法的種類很多圆到,可以依據(jù)某一特征將它們分門別類怎抛。基于不同的選擇機制芽淡,我們可以對其進行分類:
(1)??基于Pareto的方法(Pareto-based Approaches)
(2)??基于群體的方法(Population-based Approaches)
(3)??聚集函數(shù)(AggregatingFunctions)
為了深入理解進化算法马绝,我們給出了基于Pareto的MOEA的基本流程,如圖2.1所示吐绵。首先初始化種群P迹淌,然后選擇某一個進化算法(如基于分解的多目標進化算法河绽,MOEA/D)對P執(zhí)行進化操作(如選擇、交叉唉窃、突變)耙饰,得到新的種群R。然后構(gòu)造P∪R的最優(yōu)解集Nset纹份,我們將最優(yōu)解集的大小設(shè)置為N苟跪,如果當前最優(yōu)解集Nset的大小與N的大小不一致,那么我們需要調(diào)整Nset的大小蔓涧,同時必須注意調(diào)整過后的Nset需要滿足分布性要求件已。之后判斷算法終止條件是否已經(jīng)被滿足,如果不滿足條件則將Nset中的個體復制到種群P中繼續(xù)下一輪的進化元暴,否則結(jié)束篷扩。我們一般用算法的迭代次數(shù)來控制它的執(zhí)行。
在MOEA中茉盏,算法收斂的必要條件同時也是一個極其重要的方面是保留上一代的最優(yōu)解集并將其加入新一代的進化過程鉴未。這樣進化下去,進化種群的最優(yōu)解集不斷向真正的Pareto前沿面收斂鸠姨,最終得到令人滿意的進化結(jié)果铜秆。
3、多目標優(yōu)化問題測試集
測試函數(shù)可以幫助我們更好地理解算法的優(yōu)點和缺點讶迁,因此測試函數(shù)的選擇對算法性能的理解與判斷尤為重要连茧。構(gòu)造的簡單性、對決策變量和目標數(shù)目的可擴展性以及對應(yīng)于算法的收斂性與多樣性均要設(shè)障等是選擇測試函數(shù)時的重要參考依據(jù)巍糯。DTLZ測試集與WFG測試集是兩個經(jīng)常使用的多目標優(yōu)化問題測試函數(shù)集啸驯。
Deb等人在2002年首次提出DTLZ測試函數(shù)集,并以共同研究者名字首字母命名(Deb鳞贷,Thiele坯汤,Laumanns虐唠,Zitzler)搀愧,根據(jù)不同難度的設(shè)置期望,2005年Deb等又在原有七個函數(shù)的基礎(chǔ)上加入了兩個測試函數(shù)疆偿,共同組成了DTLZ測試函數(shù)集咱筛。DTLZ測試函數(shù)集可以擴展至任意數(shù)量的目標(m>=2)并且可以有任意數(shù)目個變量(n>=m)。因為變量數(shù)與目標數(shù)易于控制杆故,所以DTLZ函數(shù)集被廣泛應(yīng)用于多目標優(yōu)化問題當中作為標準測試函數(shù)迅箩。
WFG測試函數(shù)集是Huband等人在2006年提出來的,一共包含9個測試問題处铛,這些問題的目標數(shù)目都可以擴展到任意數(shù)量饲趋。和DTLZ測試函數(shù)集比起來拐揭,DTLZ問題的變量都是可分離的,因此復雜程度不高奕塑,而WFG測試問題的復雜程度更高堂污、處理起來更具有挑戰(zhàn)性。WFG測試問題的屬性包括可分性或者不可分性龄砰、單峰或者多峰盟猖、PF形狀為凸或者非凸、無偏差參數(shù)或有偏差參數(shù)换棚。WFG測試函數(shù)集可以提供更有效的依據(jù)來評估優(yōu)化算法在各種不同問題上的表現(xiàn)性能式镐。
4、算法性能評價指標
通常在分析MOEA的性能時固蚤,我們希望算法在以下三個方面能夠具有較好的性能娘汞。
(1) 真實的Pareto前沿面PFtrue與算法求解的得出的PFknown與之間的距離應(yīng)該最小。
(2) 盡管搜索到的解點只是部分解夕玩,但最后求得的解點在Pareto最優(yōu)解集中該均勻分布价说,在Pareto前沿面上的點也盡量呈現(xiàn)均勻分布。
(3) 在整個前沿上應(yīng)該能夠找出大量的解點风秤,并且前沿上的各區(qū)域都應(yīng)該有解點來代表鳖目,除非PFtrue上缺少這一區(qū)域。
我們一般認為上述指標當中的第一條是最重要的缤弦,因為MOEA的目標是找到一組近似解與真實前端的距離最近领迈。
反向世代距離(Inverted GenerationalDistance):代表真實且均勻分布的Pareto最優(yōu)解集P* 到算法得到的最優(yōu)解集P 的平均距離,定義如下:
其中碍沐,種群P中個體到個體v之間的最小歐幾里德距離用d(v,P)來表示狸捅;在真實PF上均勻選取一定數(shù)目的個體并將其用P*表示;該算法求得的最優(yōu)解集用P表示累提。IGD為算法綜合性能評價指標尘喝,反映了算法的分布性和收斂性,它是越小越好的斋陪。IGD值很小朽褪,說明算法求得的最優(yōu)解集的分布性和收斂性都好。
超體積HV(Hypervolume):超體積指標度量的是通過多目標優(yōu)化算法獲得的非支配解集與參照點圍成的目標空間中的維區(qū)域的體積无虚。超體積的數(shù)學表示如下:
其中δ代表Lebesgue測度缔赠,用來測量體積。|S|表示非支配解集的數(shù)目友题,vi表示參照點z*與解集中第i個解構(gòu)成的超立方體嗤堰。HV是一個有效的一元質(zhì)量度量指標,在Pareto支配方面是嚴格單調(diào)的度宦,HV的值越大踢匣,表示對應(yīng)算法的性能越好告匠。此外,HV指標的計算不需要測試問題的理想PF离唬,這一點在實踐應(yīng)用中大大方便了HV的使用凫海。不過,HV指標存在兩點限制:1)超體積的計算成本高男娄;2)HV的值受選擇的參照點影響大行贪。