多目標進化算法簡介

姓名:劉一婷酱固;學號: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?

其中,x =(x_{1} 诫龙,x_{2} ,...,x_{n} )\in \Omega ,Ω是決策空間析显,F:\Omega \rightarrow R^m 由m個目標函數(shù)組成,R^m 稱為目標空間签赃」纫欤可達到的目標集合被定義為F(x)|x\in \Omega 。很多時候锦聊,由于目標彼此矛盾歹嘹,Ω中的任何一點都不能同時最大化所有目標,所以我們必須平衡這些目標孔庭。目標之間的最佳折衷解可以根據(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的值受選擇的參照點影響大行贪。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市模闲,隨后出現(xiàn)的幾起案子建瘫,更是在濱河造成了極大的恐慌,老刑警劉巖尸折,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件啰脚,死亡現(xiàn)場離奇詭異,居然都是意外死亡实夹,警方通過查閱死者的電腦和手機橄浓,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來亮航,“玉大人荸实,你說我怎么就攤上這事〗闪埽” “怎么了准给?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長重抖。 經(jīng)常有香客問我露氮,道長,這世上最難降的妖魔是什么钟沛? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任畔规,我火速辦了婚禮,結(jié)果婚禮上恨统,老公的妹妹穿的比我還像新娘叁扫。我一直安慰自己,他們只是感情好延欠,可當我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布陌兑。 她就那樣靜靜地躺著沈跨,像睡著了一般由捎。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上饿凛,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天狞玛,我揣著相機與錄音软驰,去河邊找鬼。 笑死心肪,一個胖子當著我的面吹牛锭亏,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播硬鞍,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼慧瘤,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了固该?” 一聲冷哼從身側(cè)響起锅减,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎伐坏,沒想到半個月后怔匣,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡桦沉,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年每瞒,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片纯露。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡剿骨,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出埠褪,到底是詐尸還是另有隱情懦砂,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布组橄,位于F島的核電站荞膘,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏玉工。R本人自食惡果不足惜羽资,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望遵班。 院中可真熱鬧屠升,春花似錦、人聲如沸狭郑。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽翰萨。三九已至脏答,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背殖告。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工阿蝶, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人黄绩。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓羡洁,卻偏偏與公主長得像,于是被迫代替她去往敵國和親爽丹。 傳聞我的和親對象是個殘疾皇子筑煮,可洞房花燭夜當晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內(nèi)容