高維多目標(biāo)進(jìn)化算法總結(jié)

1、精選優(yōu)質(zhì)文檔傾情為你奉上精選優(yōu)質(zhì)文檔傾情為你奉上專心專注專業(yè)專心專注專業(yè)精選優(yōu)質(zhì)文檔傾情為你奉上專心專注專業(yè)高維多目標(biāo)進(jìn)化算法二、文獻(xiàn)選讀內(nèi)容分析及思考（一）Borg算法Borg算法是基于-MOEA算法（Deb，2003）的一種全新改進(jìn)算法 ADDIN EN.CITE Hadka20132513225125117Hadka, DavidReed, PatrickBorg: An auto-adaptive many-objective evolutionary computing frameworkEvolutionary computationEvolutionary Computation

2、231-25921220131063-6560，下面將從創(chuàng)新點(diǎn)、原理、算法流程和啟發(fā)思考四方面進(jìn)行闡述。1. 創(chuàng)新點(diǎn)1）在支配關(guān)系的基礎(chǔ)上提出盒支配的概念，具有能同時(shí)保證算法收斂性與多樣性的特點(diǎn)。2）提出了歸檔進(jìn)程，能提高算法計(jì)算效率和防止早熟。3）種群大小的自適應(yīng)調(diào)整。4）交叉算子的自適應(yīng)選擇。由于處理實(shí)際問(wèn)題時(shí)，是不知道目標(biāo)函數(shù)具有什么特性，前沿面如何，在具有多個(gè)交叉算子的池子里，根據(jù)進(jìn)程反饋，選擇不同的交叉算子，使產(chǎn)生的后代具有更好的特性針對(duì)要研究的問(wèn)題。2. Borg算法原理1）盒支配：通過(guò)對(duì)目標(biāo)空間向量的每一維除以一個(gè)較小的，然后取整后進(jìn)行pareto支配比較。這樣的支配關(guān)系達(dá)到的效

3、果是把目標(biāo)空間劃分成以為邊長(zhǎng)的網(wǎng)格（2目標(biāo)時(shí)），當(dāng)點(diǎn)處于不同的網(wǎng)格時(shí)，按pareto支配關(guān)系比較；當(dāng)處于同一網(wǎng)格時(shí)，比較哪個(gè)點(diǎn)距離中心點(diǎn)（網(wǎng)格最左下角）最近。這樣一來(lái)，網(wǎng)格內(nèi)都只有一個(gè)點(diǎn)。2）歸檔進(jìn)程如圖1所示，黑點(diǎn)表示已經(jīng)歸檔的，想要添加到檔案集的新解用表示，陰影表示歸檔解支配的區(qū)域。當(dāng)新解的性能提升量超過(guò)閾值才屬于歸檔進(jìn)程。比如解1、解2加入歸檔集屬于歸檔進(jìn)程，解3加入歸檔集就不屬于歸檔進(jìn)程。圖1 支配網(wǎng)格在這個(gè)過(guò)程中設(shè)置了一個(gè)參數(shù)c，表示每一代中加入歸檔集解得個(gè)數(shù)，每隔一定迭代次數(shù)檢測(cè)c有沒(méi)有增加，如果沒(méi)有增加表明算法停滯，重啟機(jī)制啟動(dòng)。3）重啟自適應(yīng)種群大?。褐貑⒑蟮姆N群大小是根據(jù)歸檔

4、集的大小設(shè)置。表示種群大小與歸檔集大小的比值，這個(gè)值也用于第二步中，如果值沒(méi)超過(guò)1.25，重啟機(jī)制也啟動(dòng)。啟動(dòng)后，人為設(shè)定為固定值，種群被清空，填充歸檔集的所有個(gè)體，不足的個(gè)體是隨機(jī)選取歸檔集中個(gè)體變異所得。與之相匹配的錦標(biāo)賽比較集大小是歸檔集大小乘以固定比值。4）交叉算子的自適應(yīng)選擇摒棄以往采用單一的交叉算子，采用包含各類交叉算子的池子，比如有K種交叉算子，選擇概率最開(kāi)始是相等的，設(shè)n表示各類交叉算子產(chǎn)生的后代屬于歸檔進(jìn)程所得個(gè)數(shù)，個(gè)數(shù)越多，選取相應(yīng)交叉算子的概率就越大，逐漸趨于選擇解決未知現(xiàn)實(shí)問(wèn)題的交叉算子。3. Borg算法總體流程通過(guò)交叉算子的自適應(yīng)選擇選擇一種交叉算子，假設(shè)所選交叉算

5、子需要K個(gè)父代，1個(gè)父代在歸檔集中按均勻分布選擇，K-1個(gè)父代從種群中按錦標(biāo)賽選擇（大小按上述第3步中計(jì)算），交叉產(chǎn)生一個(gè)后代，如果這個(gè)后代pareto支配種群中一個(gè)或多個(gè)個(gè)體，則隨機(jī)的取代一個(gè)；如果被種群中的任一個(gè)體支配，則不能加入種群；如果互不支配，也是隨機(jī)的取代種群中的一個(gè)。而加入歸檔集，是按照上述第2步實(shí)施的。如此循環(huán)一定代數(shù)之后，看達(dá)沒(méi)達(dá)到第3步重啟的條件，達(dá)到則重啟過(guò)程開(kāi)始，直至滿足終止條件。4. 思考1）盒支配時(shí)，同一網(wǎng)格內(nèi)的點(diǎn)只是比較離中心點(diǎn)距離最近的，這就有一個(gè)不足，最近的不一定是非支配解，離的遠(yuǎn)的點(diǎn)有可能還支配它，我覺(jué)得還需要比較一下哪個(gè)解優(yōu)的目標(biāo)維數(shù)多。2）設(shè)計(jì)一種云交叉

6、算子，加入到交叉算子的池子里，或是參數(shù)控制云交叉算子替換其中的能達(dá)到類似效果的幾種算子，便于統(tǒng)一。（二）基于模糊支配的高維多目標(biāo)進(jìn)化算法1. 算法簡(jiǎn)介基于模糊支配的高維多目標(biāo)進(jìn)化算法 ADDIN EN.CITE He20142433324324317Z. HeG. G. YenJ. ZhangFuzzy-Based Pareto Optimality for Many-Objective Evolutionary AlgorithmsIEEE Transactions on Evolutionary ComputationIEEE Transactions on Evolutionary Co

7、mputation269-285182Pareto optimisationevolutionary computationfuzzy set theoryPareto optimality principleevolutionary algorithmsfuzzy based Pareto optimalityfuzzy logicmultiobjective optimization problemsNSGA-IIPareto optimalitySPEA2multiobjective evolutionary algorithm20141089-778X10.1109/TEVC.2013

8、.是對(duì)模糊支配關(guān)系的一種改進(jìn)，2005年M. Farina首次提出的模糊支配，其隸屬函數(shù)是一條正態(tài)分布函數(shù)，如圖2所示，而此文的隸屬函數(shù)是一條半正態(tài)分布函數(shù)，表達(dá)的概念更加清晰。圖2 正態(tài)隸屬函數(shù)對(duì)于最小化問(wèn)題，歸一化后的解A（a1,a2,.,aM），B（b1,b2,.,bM）如果目標(biāo)向量的某一維上的差量（ai-bi）達(dá)到-1，則ai好于bi的程度為1，即pareto支配關(guān)系下ai支配bi；如果差量（ai-bi）是1，則pareto支配關(guān)系下bi支配ai。A模糊支配B程度為每一維差量映射下的隸屬度之積，與種群中其他解進(jìn)行比較，所得隸屬度相加即為A解在整個(gè)中群眾的性能好壞程度，相當(dāng)于NSGA-I

9、I中的非支配排序，只是這里的等級(jí)程度更加細(xì)分，然后還得設(shè)置一個(gè)閾值，即模糊支配隸屬度達(dá)到多少才能是最優(yōu)解，也就是NSGA-II中的非支配排序等級(jí)為1的解。設(shè)定這個(gè)值是關(guān)鍵，此文獻(xiàn)也對(duì)這個(gè)值得選取進(jìn)行了實(shí)驗(yàn)說(shuō)明，針對(duì)不同的問(wèn)題選取不同的值，但是還沒(méi)能達(dá)到根據(jù)問(wèn)題特性自適應(yīng)調(diào)整。2. 思考1）既然隸屬度函數(shù)不是一成不變的，想用云模型確定隸屬度，借鑒張國(guó)英高維云模型及其在多屬性評(píng)價(jià)中的應(yīng)用構(gòu)造一M維云模型，它的作用是輸入M維差量映射為一維的模糊支配隸屬度u，無(wú)需像上文中求出每一維隸屬度再相乘。2）由于閾值不好確定，可不可以根據(jù)歸檔集的大小取前N個(gè)，找到使個(gè)體數(shù)量大于等于N的u值為。（三）基于網(wǎng)格支配

10、的高維多目標(biāo)進(jìn)化算法GrEA ADDIN EN.CITE Yang20132303423023017Yang, ShengxiangLi, MiqingLiu, XiaohuiZheng, JinhuaA grid-based evolutionary algorithm for many-objective optimizationEvolutionary Computation, IEEE Transactions onEvolutionary Computation, IEEE Transactions on721-73617520131089-778X10.1109/TEVC.2012

11、.也是針對(duì)-MOEA算法進(jìn)行改進(jìn)的，作者認(rèn)為-MOEA算法中的網(wǎng)格劃分是基于個(gè)體的，如果個(gè)體分配不均勻，也就不能得到分布性好的最優(yōu)前沿，而且網(wǎng)格的大小也不能隨著目標(biāo)空間的特性而自適應(yīng)調(diào)整。1. 支配關(guān)系創(chuàng)新grid-dominance，這種支配關(guān)系是基于空間區(qū)域劃分網(wǎng)格，就是在當(dāng)代種群中找出每一個(gè)目標(biāo)函數(shù)上的最大值與最小值（下圖上行），然后根據(jù)這兩個(gè)值計(jì)算出這個(gè)目標(biāo)函數(shù)的網(wǎng)格上下界值（下圖下行）。人為設(shè)定每一個(gè)目標(biāo)函數(shù)需劃分的段數(shù)div,是一個(gè)固定的值，這樣就使得收斂性與多樣性的要求隨著算法進(jìn)程自適應(yīng)調(diào)整，比如說(shuō)剛開(kāi)始時(shí)目標(biāo)空間的個(gè)體分布比較廣，就需要大的網(wǎng)格來(lái)選擇個(gè)體，隨著算法深入，個(gè)體更加

12、集中于Pareto前沿區(qū)域，就需要小的網(wǎng)格區(qū)分個(gè)體，更加強(qiáng)調(diào)個(gè)體的多樣性，因此這樣動(dòng)態(tài)的網(wǎng)格劃分更能體現(xiàn)算法的進(jìn)程。另外，-支配強(qiáng)調(diào)個(gè)體生死，只有非支配才能加入歸檔集；而grid dominance不同，它更強(qiáng)調(diào)個(gè)體的先后，非支配個(gè)體只是先于支配個(gè)體進(jìn)入歸檔集，支配個(gè)體還是有機(jī)會(huì)加入歸檔集，這在一定程度上保留了邊界點(diǎn)，而-MOEA算法會(huì)丟失邊界點(diǎn)。圖3 網(wǎng)格分段示意圖2. 適應(yīng)度值指派創(chuàng)新本文提出了適應(yīng)度值指派的三個(gè)指標(biāo)grid ranking (GR)、grid crowding distance (GCD)和grid coordinate point distance(GCPD)，GR和G

13、CPD是收斂性評(píng)價(jià)指標(biāo)，GCD是多樣性評(píng)價(jià)指標(biāo)，網(wǎng)格指標(biāo)如圖4所示。GR表示個(gè)體所處網(wǎng)格各維目標(biāo)函數(shù)坐標(biāo)之和，相當(dāng)于將目標(biāo)向量各維相加，只不過(guò)這里是將函數(shù)值映射為所處網(wǎng)格坐標(biāo)值之和。比如下圖A點(diǎn)的網(wǎng)格坐標(biāo)為（0,4），則GR=0+4=4。GCD是網(wǎng)格擁擠距離，以往的網(wǎng)格擁擠距離都是在一個(gè)網(wǎng)格之內(nèi)的，這樣就不能反映分布性了，此處的GCD還考慮臨近網(wǎng)格的個(gè)體，用網(wǎng)格坐標(biāo)的差量之和評(píng)估，之和越小的GCD值就越大，多樣性就越差。如下圖C的鄰居是B、D，F(xiàn)的鄰居是E、G。GCPD表示的是同一網(wǎng)格內(nèi)與中心點(diǎn)的距離，這一點(diǎn)與-MOEA中相同。比較的先后準(zhǔn)則是GR，GR相同比較GCD，GR、GCD都相同則比較

14、GCPD。圖4 網(wǎng)格指標(biāo)示意圖3. 歸檔策略的改進(jìn)以往的歸檔策略都是基于適應(yīng)度值的支配關(guān)系選擇刪除，這樣會(huì)導(dǎo)致解集多樣性的缺失，因?yàn)橄噜彽狞c(diǎn)具有相似的適應(yīng)度值，會(huì)使他們同時(shí)被選擇或刪除，比如上圖的E、F、G，這樣多樣性會(huì)得不到保證。本文作者對(duì)歸檔策略進(jìn)行了改進(jìn)，就是當(dāng)一個(gè)個(gè)體加入歸檔集時(shí)，在歸檔集中和它相關(guān)的個(gè)體GR值會(huì)受到懲罰，相關(guān)的個(gè)體包括：1. 處于同一網(wǎng)格坐標(biāo) 2. 被網(wǎng)格支配的 3. 鄰域個(gè)體，懲罰力度依次減小。（四）基于坐標(biāo)轉(zhuǎn)換的高維多目標(biāo)進(jìn)化算法針對(duì)原始的密度評(píng)估算子在高維多目標(biāo)中會(huì)出現(xiàn)不能很好的兼顧收斂性與多樣性，解集往往會(huì)有很好的多樣性而收斂性差的缺點(diǎn)，論文設(shè)計(jì)了一種包含收斂

15、性的密度評(píng)估算子shift-based density estimation (SDE) ADDIN EN.CITE Li20142293522922917Li, MiqingYang, ShengxiangLiu, XiaohuiShift-Based Density Estimation for Pareto-Based Algorithms in Many-Objective OptimizationIEEE Transactions on Evolutionary ComputationIEEE Transactions on Evolutionary Computation348-3

16、65183201410.1109/TEVC.2013.。比如圖5中的A點(diǎn)，按照基于pareto支配的多目標(biāo)優(yōu)化算法來(lái)看，是非支配解切多樣性好于B、C、D，但很明顯得看出A點(diǎn)收斂性不及BCD。SDE是將各維目標(biāo)函數(shù)上小于A點(diǎn)對(duì)應(yīng)維的值轉(zhuǎn)化為A點(diǎn)那一維的函數(shù)值，如下圖所示。轉(zhuǎn)換之后A點(diǎn)的密度值較大，而BCD密度值較小，符合所考慮的情況圖5 坐標(biāo)轉(zhuǎn)換示意圖從圖6的四圖中可以看出，只有收斂性和多樣性都好的個(gè)體，其SDE值小，即其值不僅體現(xiàn)密度信息，而且將收斂性信息也包含在內(nèi)。SDE是一種通用的密度評(píng)估算子，可以將其植入NSGA-II，SPEA2和PESA-II中。圖6 擁擠密度示意圖（五）基于角點(diǎn)排序

17、的高維多目標(biāo)進(jìn)化算法本文是在非支配排序上的改進(jìn)。在高維多目標(biāo)優(yōu)化問(wèn)題中，隨著目標(biāo)維數(shù)的增加，非支配解之間的比較次數(shù)是非常大的，因此論文提出了角點(diǎn)支配。所謂的角點(diǎn)指的是在M維目標(biāo)空間中只考慮其中k個(gè)目標(biāo)，在本文中只考慮一個(gè)目標(biāo)函數(shù)上的，因?yàn)樵谝粋€(gè)目標(biāo)函數(shù)上最好的點(diǎn)肯定是非支配解。二維、三維角點(diǎn)分別如下圖所示。圖7 二維、三維角點(diǎn)示意圖找到角點(diǎn)后，所有被角點(diǎn)支配的點(diǎn)就不用比較了，大大減少評(píng)價(jià)次數(shù)。而且本文還指出非支配解排序的比較次數(shù)應(yīng)該是精確到每一維的目標(biāo)函數(shù)的比較上，因?yàn)槊績(jī)蓚€(gè)解之間目標(biāo)函數(shù)的比較次數(shù)從2到M，也就是說(shuō)不同的兩個(gè)解之間比較所花費(fèi)的計(jì)算量是不同的，只計(jì)算一個(gè)解與其他解的比較次數(shù)是不

18、對(duì)的。角點(diǎn)支配排序大致過(guò)程如圖8所示。圖8 角點(diǎn)非支配排序圖8是2維目標(biāo)函數(shù)的情況，首先得找出每一維目標(biāo)函數(shù)上最好的點(diǎn)，如上圖A中的白點(diǎn)，標(biāo)記他們所支配的點(diǎn)如上圖陰影區(qū)域，這些點(diǎn)在當(dāng)前等級(jí)中就不考慮排序了，在剩下的點(diǎn)中再尋找兩個(gè)角點(diǎn)，直到將所有的點(diǎn)都標(biāo)記，如圖B，B中白點(diǎn)表示等級(jí)1，等級(jí)2、3依次進(jìn)行。（六）NSGA-III算法系列文獻(xiàn)1. MO-NSGA-II為了適合解決高維多目標(biāo)問(wèn)題，Kalyanmoy Deb針對(duì)NSGA-II的缺點(diǎn)，提出了MO-NSGA-II（many-objective NSGA-II），這是NSGA-III的雛形。MO-NSGA-II的基本框架和NSGA-II差不多

19、，不同之處在于精英選擇機(jī)制上，因?yàn)樵械倪x擇機(jī)制對(duì)快速增加的非支配解已經(jīng)沒(méi)有選擇壓力。MO-NSGA-II是一種基于參考點(diǎn)的多目標(biāo)算法，放置分布性好的參考點(diǎn)，使得到的非支配解靠近這些參考點(diǎn)，就能得到分布性好的最優(yōu)前端。讓我們回顧一下NSGA-II，有一個(gè)大小為N的當(dāng)前種群Pt，由他產(chǎn)生的子代種群Qt，大小也為N，然后對(duì)Pt、Qt的合集Rt進(jìn)行快速非支配排序F1、F2.Fi,將這些點(diǎn)按等級(jí)加入下一代種群Pt+1，通過(guò)對(duì)Fl中個(gè)體計(jì)算擁擠距離按降序排列，依次加入Pt+1，直到種群大小為N。參考點(diǎn)的設(shè)置就是從這里開(kāi)始，取代原有的擁擠距離。均勻分布的參考點(diǎn)可以通過(guò)一些特定的系統(tǒng)產(chǎn)生。1）超平面的建立。

20、設(shè)F1、F2.Fi的合集為St，在這個(gè)集合中找到每一個(gè)目標(biāo)函數(shù)值最小的點(diǎn)組成理想點(diǎn)，將目標(biāo)函數(shù)值轉(zhuǎn)化為相對(duì)的，然后種群中的點(diǎn)通過(guò)一個(gè)聚集函數(shù)求最小值（它是相對(duì)于在某一維坐標(biāo)軸上的參考點(diǎn)的）把它當(dāng)成這一維的端點(diǎn)，通過(guò)這M個(gè)端點(diǎn)構(gòu)造超平面，根據(jù)這個(gè)超平面重新計(jì)算參考點(diǎn)，這個(gè)超平面在每一代中都不同，所以它是可以根據(jù)種群特性自適應(yīng)調(diào)整。2）選取低擁擠度的解。為了確定解集擁擠度，需要把所有的點(diǎn)投影到超平面上（如圖9左圖），找到與之距離最近的參考點(diǎn)，這樣每個(gè)參考點(diǎn)就會(huì)有一定數(shù)量的解與之相關(guān)聯(lián)（如圖9右圖）。選擇參考點(diǎn)周圍個(gè)體最少的參考點(diǎn)，選出Fi解集中在這個(gè)參考點(diǎn)下ASF最小的點(diǎn)加入Pt+1。再選出個(gè)體數(shù)

21、次最少的參考點(diǎn)，選出Fi解集中在這個(gè)參考點(diǎn)下ASF最小的點(diǎn)加入Pt+1，直到加滿Pt+1。圖9 關(guān)聯(lián)操作3）錦標(biāo)賽選擇。當(dāng)Pt+1形成，用錦標(biāo)賽方法產(chǎn)生后代Qt+1，具體操作是從Pt+1任意挑選兩個(gè)解，比較策略是如果一個(gè)解的非支配等級(jí)小于另一個(gè)解，選擇前一個(gè)解；如果同處一個(gè)非支配等級(jí)但是所屬參考點(diǎn)的擁擠度不同，選擁擠度小的點(diǎn)；如果非支配等級(jí)和所屬參考點(diǎn)的擁擠度都相同，則選ASF值小的。然后采用模擬二進(jìn)制交叉算子，產(chǎn)生后代Qt+1，然后在合并進(jìn)行第一步，依次循環(huán)。2. NSGA-III本文作者針對(duì)上文提出的MO-NSGA-II作了適當(dāng)改進(jìn)，提出了NSGA-III。1）超平面的建立。與上文不同的是

22、，本文將超平面進(jìn)行了歸一化處理，找到基于坐標(biāo)軸上的參考點(diǎn)的每一維端點(diǎn)后，還必須將組成的超平面延伸相交于fi，坐標(biāo)系，截距為ai，如圖10所示。圖10 端點(diǎn)歸一化示意圖2）個(gè)體與參考點(diǎn)的關(guān)聯(lián)操作。上文中是將個(gè)體投影到超平面上，而此文是個(gè)體與參考線方向的垂直距離（參考線方向是參考點(diǎn)與理想點(diǎn)的連線方向），如圖11所示。圖11 關(guān)聯(lián)操作3）小生境保留操作。此處本文與上文有個(gè)很大不同，本文只計(jì)算排除Fi的St，的小生境數(shù)，選出圍繞參考線個(gè)體為0的參考線，如果有多條則任選一條，即，這樣Fi個(gè)體就有兩種情況。第一，F(xiàn)i中有一到多個(gè)個(gè)體與參考點(diǎn) 相關(guān)聯(lián)，這樣就選一個(gè)與參考點(diǎn)垂直距離最短的個(gè)體加入下一代種群Pt

23、+1，加1。第二，如果，F(xiàn)i中沒(méi)有個(gè)體與參考點(diǎn)相關(guān)聯(lián)，則這個(gè)參考點(diǎn)在當(dāng)前代就不用考慮了。如果，則從Fi中與參考點(diǎn) 相關(guān)聯(lián)的個(gè)體集合中任選一個(gè)，加1。重新調(diào)整小生境數(shù)，直到加滿Pt+1。3. C-NSGA-III上文提出的NSGA-III是處理無(wú)約束的問(wèn)題，本文為處理約束條件，對(duì)NSGA-III進(jìn)行了改進(jìn)。1）精英選擇操作上的改進(jìn)，用約束支配取代pareto支配，和NSGA-II為處理約束條件的約束支配原則是一樣。此時(shí)的種群一般既有可行解，還有不可行解，如果可行解的個(gè)數(shù)，那么還需要從具有最小約束違反度的不可行解中選取個(gè)體加滿Pt+1；如果，則按照無(wú)約束的NSGA-III精英選擇操作進(jìn)行，接著也要

24、用Pt+1中可行解更新理想點(diǎn)和端點(diǎn)。2）子代種群生成。錦標(biāo)賽選取規(guī)則是任選兩個(gè)解，如果一個(gè)可行解，一個(gè)不可行解，選可行解；如果都是不可行解，選約束違反度小的；如果都是可行解，任選一個(gè)；這樣選擇出一個(gè)父代，再進(jìn)行一次，選出另一個(gè)父代，模擬二進(jìn)制交叉，然后變異。但是通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)上述算法有個(gè)不足，由于約束條件的存在，可行區(qū)域可能只是整個(gè)區(qū)域的一小部分，然而參考點(diǎn)是均勻的分布在目標(biāo)向量空間，導(dǎo)致不是每個(gè)參考方向都能與最有前沿面相交，也就是說(shuō)有一部分參考點(diǎn)是沒(méi)用的，而用到的參考點(diǎn)會(huì)與多個(gè)個(gè)體相關(guān)聯(lián)，又不能達(dá)到好的分布性，如圖12所示。圖12 參考點(diǎn)自適應(yīng)調(diào)整這就涉及到一個(gè)問(wèn)題：如何使所有的參考點(diǎn)能均勻分

25、布在可行區(qū)域上，理想的方法是能分配所有的參考點(diǎn)均勻地分布在最優(yōu)前沿面，但是對(duì)于不同的問(wèn)題最優(yōu)前沿面是未知的。于是本文作者提出了自適應(yīng)的NSGA-III，叫做A-NSGA-III，讓它能夠自適應(yīng)鑒別出無(wú)用的參考點(diǎn)然后分配他們，希望能找到新的最優(yōu)解。于是在原有的NSGA-III生成大小為N的Pt+1后，有兩個(gè)新的操作1.增加新的參考點(diǎn) 2.消除無(wú)用的參考點(diǎn)。1）增加新的參考點(diǎn)。由于參考點(diǎn)個(gè)數(shù)等于種群規(guī)模，理想情況是一個(gè)參考點(diǎn)一個(gè)個(gè)體，當(dāng)參考點(diǎn)j方向的小生境數(shù)，則必存在參考點(diǎn)k方向的小生境數(shù)，。我們針對(duì)參考點(diǎn)j，在其周圍增加M個(gè)參考點(diǎn)的單純形（單純形法是一類在小范圍內(nèi)具有更精細(xì)搜索效果的優(yōu)化算法，能

26、提高點(diǎn)的多樣性），如下圖所示三維空間中具有三個(gè)頂點(diǎn)的單純形擴(kuò)展。圖13 單純形擴(kuò)展法但是擴(kuò)張的點(diǎn)有兩種情況是不接受的：1.不在第一象限 2.在參考點(diǎn)集中已經(jīng)存在2）消除無(wú)用的參考點(diǎn)。擴(kuò)張完后的參考點(diǎn)可能存在一些無(wú)用的，則消除那些的擴(kuò)展點(diǎn)，而原始的參考點(diǎn)是要保留的，有可能下一代就有用了。4. A2-NSGA-III論文針對(duì)A-NSGA-III的四點(diǎn)缺點(diǎn)進(jìn)行了改進(jìn)，提出了A2-NSGA-III，四點(diǎn)缺點(diǎn)如下：1）當(dāng)問(wèn)題的最優(yōu)前沿面很小時(shí)，A-NSGA-III擴(kuò)張操作不能提供足夠的參考點(diǎn)使種群分布均勻。2）擴(kuò)張操作不適合角點(diǎn)，因?yàn)橐越屈c(diǎn)為中心擴(kuò)張生成的點(diǎn)不在第一象限或出界。3）由于擴(kuò)張操作是從第一代

27、開(kāi)始，種群較分散，離最優(yōu)前沿面較遠(yuǎn)，很可能沒(méi)有足夠的時(shí)間使種群在各個(gè)區(qū)域均勻分布而由于額外的擴(kuò)張點(diǎn)陷入局部最優(yōu)。4）只有當(dāng)所有參考點(diǎn)小生境數(shù)為0或1時(shí)才開(kāi)始消除操作，對(duì)于高維多目標(biāo)，由于種群變大，這個(gè)條件很難達(dá)到。改進(jìn)措施：選取參考點(diǎn)為單純形的一個(gè)頂點(diǎn)，而不是中心，且邊長(zhǎng)減半，而且這樣可以有三種外形，如圖14所示。圖14 改進(jìn)單純形擴(kuò)展法當(dāng)添加一個(gè)外形后，還有小生境數(shù)大于1的，采用另一個(gè)外形，直到所有M個(gè)外形都采用，如果還有，則單純形的邊長(zhǎng)再取半，直到小生境數(shù)為0。在一個(gè)外形加入之前，需要進(jìn)行檢查：1.如果外形的點(diǎn)超出邊界是不被接受，比如上圖Q點(diǎn)，外形1、3是不被接受的。2.如果外形的點(diǎn)在參考

28、點(diǎn)中存在，也是不被接受。這樣的擴(kuò)張操作引入了更多的單純形，能緩解第一個(gè)缺點(diǎn)；以參考點(diǎn)為頂點(diǎn)半邊長(zhǎng)的單純形適用于定點(diǎn)，比如Q點(diǎn)，緩解了第二個(gè)缺點(diǎn)；只有當(dāng)原始的參考點(diǎn)小生境數(shù)在過(guò)去的10代穩(wěn)定在一個(gè)定值，則擴(kuò)張的點(diǎn)才被接受，這樣能克服第三個(gè)缺點(diǎn)；只要參考點(diǎn)總數(shù)達(dá)到原始參看點(diǎn)個(gè)數(shù)的10倍，消除操作就開(kāi)始，這樣能克服第四個(gè)缺點(diǎn)。（七）MOEA/D-M2MMOEA/D-M2M是將高維多目標(biāo)問(wèn)題分解為多個(gè)簡(jiǎn)單的多目標(biāo)優(yōu)化子問(wèn)題，通過(guò)協(xié)同方式解決這些子問(wèn)題，每個(gè)子問(wèn)題對(duì)應(yīng)一個(gè)子種群，通過(guò)這種方式種群多樣性得到維護(hù)。它是針對(duì)MOEA/D的存在的兩個(gè)缺點(diǎn)進(jìn)行的改進(jìn)。MOEA/D有兩個(gè)缺點(diǎn)：1）一個(gè)新個(gè)體不該完全

29、根據(jù)聚合函數(shù)值取代舊個(gè)體，因?yàn)樵谟行┣闆r下，這樣完全取代會(huì)導(dǎo)致種群多樣性的丟失。2）對(duì)于不同的問(wèn)題，MOEA/D總是需要設(shè)置合適的聚合方法和權(quán)重向量，而這個(gè)在解決問(wèn)題之前是很困難的。均勻生成K個(gè)單位方向向量，將目標(biāo)空間劃分為K個(gè)子區(qū)間，通過(guò)計(jì)算N個(gè)種群個(gè)體所在方向與K個(gè)單方方向的夾角，將n個(gè)個(gè)體劃分到k個(gè)區(qū)域里。這樣基于方向向量分解目標(biāo)空間有兩個(gè)好處：1）每個(gè)子區(qū)域的局部最優(yōu)前沿面可以組成整個(gè)最優(yōu)前沿面。2）即使整個(gè)區(qū)域的最優(yōu)前沿面是非線性幾何形狀（不規(guī)則），經(jīng)過(guò)分解，各個(gè)子區(qū)域只是整個(gè)區(qū)域的一小部分，所以最優(yōu)前沿面在子區(qū)域內(nèi)可以很接近線性形狀。而求解線性形狀的最優(yōu)前沿面比非線性幾何形狀簡(jiǎn)單得

30、多。（八）-DEA算法1. 算法簡(jiǎn)介近期進(jìn)化算法上有人基于NSGA3提出一種基于新型支配關(guān)系支配的高維多目標(biāo)優(yōu)化算法-DEA，它通過(guò)引入分解算法MOEA/D中的PBI聚合函數(shù)來(lái)提高NSGA3的收斂性。出發(fā)點(diǎn)是整合NSGA-III 和MOEA/D，達(dá)到優(yōu)勢(shì)互補(bǔ)。通過(guò)分析，文章作者得出：1）NSGA-III 強(qiáng)調(diào)的是個(gè)體中靠近參考線的Pareto非支配解，然而目標(biāo)維數(shù)增大時(shí)，會(huì)導(dǎo)致非支配解個(gè)數(shù)也急劇增多，基于pareto支配關(guān)系的NSGA-III 將缺乏足夠的選擇壓力去促使種群向最優(yōu)PF面進(jìn)化，事實(shí)上NSGA-III 過(guò)多的側(cè)重于多樣性而導(dǎo)致收斂性不足。2）MOEA/D通過(guò)基于聚合函數(shù)的選擇操作能

31、很好地逼近最優(yōu)PF面，在高維情況下收斂性也很好，而多樣性試圖通過(guò)設(shè)置均勻分布的權(quán)重向量來(lái)維護(hù)，低維可以到達(dá)目的，但是在高維情況下就不適用了，因?yàn)樵诟呔S空間中，一個(gè)具有很好聚合函數(shù)值的解有可能離相應(yīng)的權(quán)重向量很遠(yuǎn)，那么多樣性就會(huì)缺失。綜上所訴，NSGA-III收斂性不足，MOEA/D多樣性缺失，因此作者通過(guò)引入MOEA/D的聚合函數(shù)來(lái)提高NSGA-III的收斂性，而繼承NSGA-III優(yōu)良的多樣性。2. 算法步驟1）合并父代種群和子代種群，組成，對(duì)進(jìn)行非支配排序，其中表示第i層pareto前沿，滿足,2）以N個(gè)權(quán)重向量為聚類中心，將中的個(gè)體聚類到各個(gè)權(quán)重向量附近（各個(gè)權(quán)重向量附近個(gè)體數(shù)是不一樣的

32、），然后通過(guò)支配關(guān)系對(duì)每一個(gè)類內(nèi)個(gè)體劃分等級(jí)。這里所說(shuō)的支配也就是MOEA/D中的PBI聚合函數(shù)，如圖15所示。圖15 PBI聚合函數(shù)示意圖其中，d1越小，代表x解的收斂性越好；d2越小說(shuō)明越靠近權(quán)重向量，多樣性越好。綜合這兩者表示一個(gè)解的優(yōu)劣，可以令，如果，我們就說(shuō)x支配y，其中是懲罰系數(shù)，實(shí)驗(yàn)仿真取5（對(duì)5作解釋）說(shuō)明一下，這里通過(guò)支配關(guān)系對(duì)每一個(gè)類內(nèi)個(gè)體劃分等級(jí)，其實(shí)每一個(gè)等級(jí)上只有一個(gè)解，因?yàn)槭且粋€(gè)可以比較大小的數(shù)值。3）以此取每一個(gè)類里的第一等級(jí)，第二等級(jí)，以此類推，直到選擇最后一個(gè)等級(jí)，他加入的話大于N，不加入就少于N，然后隨機(jī)的在這一等級(jí)里選取個(gè)體滿足數(shù)量N。3. 思考1）對(duì)-D

33、EA的改進(jìn)，在第三步中，是隨機(jī)的在最后一等級(jí)里選擇，而我的想法是定向的選擇類內(nèi)個(gè)體數(shù)少的那一類的最后等級(jí)個(gè)體，能夠進(jìn)一步提高多樣性。2）NSGA-III在多樣性維護(hù)階段只是依靠d2來(lái)選擇個(gè)體，會(huì)導(dǎo)致收斂性不足，而-DEA在考慮多樣性d2的同時(shí)稍微考慮一點(diǎn)收斂性d1，根據(jù)這一點(diǎn)我對(duì)自己的多個(gè)子種群進(jìn)化算法做了進(jìn)一步改進(jìn)，將子種群中由以前只依靠d2選擇個(gè)體變?yōu)閐1+5d2。3）NSGA-III和-DEA都是先進(jìn)行非支配排序后聚類，不同的是NSGA-III通過(guò)評(píng)估每一個(gè)類里的小生境數(shù)選擇小生境數(shù)少的類內(nèi)個(gè)體，而-DEA是通過(guò)支配循環(huán)選擇每一類個(gè)體，因此我可以將我的子種群的NSGA-III模式改為-D

34、EA模式。參考文獻(xiàn) ADDIN EN.REFLIST 1 R.C. Purshouse, P.J. Fleming. On the Evolutionary Optimization of Many Conflicting Objectives. Evolutionary Computation, IEEE Transactions on. 2007, 11 (6): 770-7842 孔維健, 丁進(jìn)良, 柴天佑. 高維多目標(biāo)進(jìn)化算法研究綜述. 控制與決策. 2010 (03): 321-3263 鞏敦衛(wèi), 季新芳, 孫曉燕. 基于集合的高維多目標(biāo)優(yōu)化問(wèn)題的進(jìn)化算法. 電子學(xué)報(bào). 2014 (

35、01): 77-834 E. Hughes. Radar Waveform Optimisation as a Many-Objective Application Benchmark. In: Evolutionary Multi-Criterion Optimization-S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, T. Murata, eds.: Springer Berlin Heidelberg, 2007: 700-7145 A. Slflow, N. Drechsler, R. Drechsler. Robust Multi-Obj

36、ective Optimization in High Dimensional Spaces. In: Evolutionary multi-criterion optimization: Springer, 2007: 715-7266 R. Lygoe, M. Cary, P. Fleming. A Real-World Application of a Many-Objective Optimisation Complexity Reduction Process. In: Evolutionary Multi-Criterion Optimization-R. Purshouse, P

37、. Fleming, C. Fonseca, S. Greco, J. Shaw, eds.: Springer Berlin Heidelberg, 2013: 641-6557 K. Deb, A. Pratap, S. Agarwal, T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: Nsga-Ii. Evolutionary Computation, IEEE Transactions on. 2002, 6 (2): 182-1978 E. Zitzler, M. Laumanns, L. Thie

38、le. Spea2: Improving the Strength Pareto Evolutionary Algorithm. TIK, Swiss Federal Institute of Technology (ETH. 20019 D.W. Corne, N.R. Jerram, J.D. Knowles, M.J. Oates, J. Martin. Pesa-Ii: Region-Based Selection in Evolutionary Multiobjective Optimization. In: Proceedings of the Genetic and Evolut

39、ionary Computation Conference (GECCO2001, 2001: 283-29010 陳小紅, 李霞, 王娜. 高維多目標(biāo)優(yōu)化中基于稀疏特征選擇的目標(biāo)降維方法. 電子學(xué)報(bào). 2015 (07): 1300-130711 H. Ishibuchi, N. Tsukamoto, Y. Nojima. Evolutionary Many-Objective Optimization: A Short Review. In: Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computat

40、ional Intelligence). IEEE Congress on, 2008: 2419-242612 K. Deb, M. Mohan, S. Mishra. Evaluating the -Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions. Evolutionary Computation. 2005, 13 (4): 501-52513 H. Sato, H. Aguirre, K. Tanaka. Control

41、ling Dominance Area of Solutions and Its Impact on the Performance of Moeas. In: Evolutionary Multi-Criterion Optimization-S. Obayashi, K. Deb, C. Poloni, T. Hiroyasu, T. Murata, eds.: Springer Berlin Heidelberg, 2007: 5-2014 Y. Shengxiang, L. Miqing, L. Xiaohui, Z. Jinhua. A Grid-Based Evolutionary

42、 Algorithm for Many-Objective Optimization. Evolutionary Computation, IEEE Transactions on. 2013, 17 (5): 721-73615 Z. He, G.G. Yen, J. Zhang. Fuzzy-Based Pareto Optimality for Many-Objective Evolutionary Algorithms. Evolutionary Computation, IEEE Transactions on. 2014, 18 (2): 269-28516 畢曉君, 張永建, 陳

43、春雨. 基于模糊支配的高維多目標(biāo)進(jìn)化算法mfea. 電子學(xué)報(bào). 2014 (08): 1653-165917 A. Jaimes, L. Quintero, C.C. Coello. Ranking Methods in Many-Objective Evolutionary Algorithms. In: Nature-Inspired Algorithms for Optimisation-R. Chiong, ed.: Springer Berlin Heidelberg, 2009: 413-43418 Z. Xiufen, C. Yu, L. Minzhong, K. Lishan.

44、 A New Evolutionary Algorithm for Solving Many-Objective Optimization Problems. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on. 2008, 38 (5): 1402-141219 E. Carreno Jara. Multi-Objective Optimization by Using Evolutionary Algorithms: The -Optimality Criteria. Evolutionary C

45、omputation, IEEE Transactions on. 2014, 18 (2): 167-17920 J. Cheng, G.G. Yen, G. Zhang. A Many-Objective Evolutionary Algorithm with Enhanced Mating and Environmental Selections. IEEE Transactions on Evolutionary Computation. 2015, 19 (4): 592-60521 J. Horn, N. Nafpliotis, D.E. Goldberg. A Niched Pa

46、reto Genetic Algorithm for Multiobjective Optimization. In: Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on: Ieee, 1994: 82-8722 鄭金華, 申瑞珉, 李密青, 鄒娟. 一種基于信息分離的高維多目標(biāo)進(jìn)化算法. 軟件學(xué)報(bào). 2015 (05): 1013-103623 S.F. Adra, P.J. Fleming

47、. Diversity Management in Evolutionary Many-Objective Optimization. Evolutionary Computation, IEEE Transactions on. 2011, 15 (2): 183-19524 K. Deb, H. Jain. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with

48、Box Constraints. Evolutionary Computation, IEEE Transactions on. 2014, 18 (4): 577-60125 L. Miqing, Y. Shengxiang, L. Xiaohui. Shift-Based Density Estimation for Pareto-Based Algorithms in Many-Objective Optimization. Evolutionary Computation, IEEE Transactions on. 2014, 18 (3): 348-36526 X. Zhang, Y. Tian, Y. Jin. A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization. Evolutionary Computation, IEEE Transactions on. 2015, 19 (6): 761-77627 H. Li