09第九章 多目標(biāo)優(yōu)化算法

第九章多目標(biāo)優(yōu)化算法習(xí)題與答案1.填空題多目標(biāo)優(yōu)化問題由于存在 目標(biāo),使得同時優(yōu)化的對象增多。由于目標(biāo)之間往往相互沖突，某一目標(biāo)性能的提高會引起其他目標(biāo)性能的 ，因此只能通過 的方法使所有目標(biāo)盡可能達(dá)到最優(yōu)。多目標(biāo)優(yōu)化問題需要求解一個由不同程度折中的 組成的解集，并且需要保證解集的 和 ，這就導(dǎo)致多目標(biāo)優(yōu)化問題的求解難度遠(yuǎn)遠(yuǎn)大于單目標(biāo)優(yōu)化問題。解釋：本題考查多目標(biāo)優(yōu)化算法的基礎(chǔ)知識。具體內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：多個，降低，權(quán)衡折中最優(yōu)解，收斂性，均勻性如何理解多目標(biāo)優(yōu)化問題？解釋：本題考查多目標(biāo)優(yōu)化問題的形式和實質(zhì)。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：多目標(biāo)優(yōu)化問題由于存在多個目標(biāo)，優(yōu)化對象增多，且目標(biāo)之間往往是相互沖突的，某一目標(biāo)性能的提高會引起其他目標(biāo)性能的降低，因此只能通過權(quán)衡折中的方法使所有目標(biāo)盡可能達(dá)到最優(yōu)。不同于單目標(biāo)優(yōu)化只需求得一個最優(yōu)解，多目標(biāo)優(yōu)化需要求解一個由不同程度折中的最優(yōu)解組成的解集，且需同時保證解集的收斂性和均勻性。例如，購買汽車時考慮到汽車性能和價格兩個方面，往往當(dāng)性能較好時性能優(yōu)良且價格昂貴，而性能較差時價格低廉，人們總是想得到價格便宜同時性能又好的汽車，但這兩方面往往不能同時兼優(yōu)，只能在某一方面有所偏重，這就形成了一個以汽車性能(比如百米加速時間)和價格為兩個沖突目標(biāo)的多目標(biāo)優(yōu)化問題。試舉例說明Pareto支配關(guān)系具有傳遞性。解釋：本題考查Pareto支配關(guān)系的性質(zhì)。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：TOC\o"1-5"\h\z假設(shè)兩目標(biāo)最小優(yōu)化的三個個體，C=(2,2),C=(3,3),C=(4,4)，貝ljCC,1 2 3 1 2CC，又因為C C，所以Pareto支配關(guān)系具有傳遞性。 》2 3 13A A考慮一個具有兩個目標(biāo)最小化問題,20個個體的進(jìn)化群體,進(jìn)行Pareto非支配排序分層。20個個體定義如下：C1=(9,1),C2=(7,2),C3=1 2 3(5,4), C4 =(4,5), C5 =(3,6), C6 =(2,7),C7=(1,9), C8=(10,1), C9 = (8,5), C1Q =, C11 =(5,7), C12 =(4,8),「=(3,9),「=(10,5), Q=(9,6),%=, C17 =(7,9), C18 =(10,6),C19=(9,7),°。=(8,9)解釋：本題考查基于Pareto支配的排序方法。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：由于{c}C {c,C,C}C {c,C,C,C}C {c,C,C,C}CTOC\o"1-5"\h\z由于1 8 2 3 4 9 2 3 4 5 10 3 4 5 6 11{c,C,C}C? {c,C,C}C {C,C,C,C,C,C}CA4 5 6 12 5 6 7 13 1 2 3 4 8 9 14A {c,C,C,C,C,C,C,CA {c,C,C,C,C,C,C,C}C2 3 4 5 6 9 10 11 162 3 4 5 9 10 15

{c{c,C,C,C,C,C,C,C,C,C}C345671011121317；{C,C,C,C,C,C,C,C,C,C}C；123458910141518；{C,C,C,C,C,C,C,C,C,C,C}C12345691011151619{C,C,C,C,C,C,C,C,C,C,C,C,C}C234567910111213161720根據(jù)以上支配關(guān)系，這20個個體具有下列4個層次:P={c,C,C,C,C,C,C}11234567P={c,C,C,C,C,C}28910111213P={c,C,C,C}14151617P={c,C,C}181920簡述NSGA-n算法的基本流程。解釋：本題考查NSGAII算法思想。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：首先，隨機(jī)產(chǎn)生規(guī)模為N的初始種群P，產(chǎn)生子代種群Q，并將兩個種群tt聯(lián)合在一起形成大小為2N的種群R；其次，將父代種群與子代種群合并，進(jìn)行t快速非支配排序并且分層，同時對每個非支配層中的個體進(jìn)行擁擠度計算，根據(jù)非支配關(guān)系以及個體的擁擠度選取合適的個體組成新的父代種群P，最后，通t+1過遺傳算法的基本操作產(chǎn)生新的子代種群Q，將P與Q合并形成新的種群t+1 t+1 t+1R，重復(fù)以上操作，直到滿足程序結(jié)束的條件。t簡述NSGA-II與NSGA-m的不同之處。解釋：本題考查NSGAIII算法思想。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件答案：NSGAIII的基本框架與NSGAII算法類似，不同之處在于多樣性維護(hù)策略，其采用基于參考點的小生境保留策略：首先，在關(guān)聯(lián)操作將每個個體關(guān)聯(lián)到對應(yīng)的參考點上之后，定義第j個參考點的小生境數(shù)為Pj,它表示s’/F中與第j個參考點相關(guān)聯(lián)的個體數(shù)；然后，選取具有最小 Pj的參考點組成參考點集Jmin兒：argminjPjI如果Jmj>1，則從中隨機(jī)選擇一個參考點jJffiln。如果關(guān)鍵層￡中沒有個體與參考點j相關(guān)聯(lián)，則此參考點在當(dāng)前代不再考慮，同時更新Jmln并重新選擇j。否則，參考點j將被考慮：當(dāng)Pj—0時，關(guān)聯(lián)參考點j并隸屬于關(guān)鍵層的個體中，選取其中到第j個參考線垂直距離最近的個體添加到種群〈+1，同時P-增加1；當(dāng)P->0，從關(guān)聯(lián)參考點了并隸屬于關(guān)鍵層的個體中隨機(jī)選取一個個體添加到種群4+1，同時Pj增加1。分析MOEA/D算法三種分解方式的優(yōu)缺點。解釋：本題考查MOEA/D算法思想。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：MOEA/D算法利用預(yù)先設(shè)定的多組權(quán)重向量將多目標(biāo)優(yōu)化問題分解成多個單目標(biāo)子問題，并利用不同的分解策略對子問題進(jìn)行求解。常用的三種分解方式：加權(quán)和法，切比雪夫法，懲罰邊界交集法。加權(quán)和法簡單，收斂速度快，但由于實質(zhì)是不同目標(biāo)函數(shù)構(gòu)成凸組合，所以不適用于求解真實PF為非凸的多目標(biāo)優(yōu)化問題；切比雪夫法適用于不同形狀的前沿，但對于對于連續(xù)問題的聚合曲線不平滑，且在目標(biāo)數(shù)增多時，并不能保證分布性；懲罰邊界交集法適用于不同形狀的前沿和目標(biāo)數(shù)多的情況，但存在一參數(shù)難以事先確定，不易調(diào)節(jié)。試說明NSGA-m算法和MOEA/D算法的區(qū)別和聯(lián)系，及各自的優(yōu)缺點。解釋：本題考查NSGAIII算法和MOEA/D算法思想對比分析。內(nèi)容請參考課堂視頻“第9章多目標(biāo)優(yōu)化算法”及其課件。答案：NSGAIII算法和MOEA/D算法均采用了均勻分布的參考點，但作