高維多目標進化算法總結(jié)

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

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

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

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

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

6、算子，加入到交叉算子的池子里，或是參數(shù)控制云交叉算子替換其中的能達到類似效果的幾種算子，便于統(tǒng)一。（二）基于模糊支配的高維多目標進化算法1. 算法簡介基于模糊支配的高維多目標進化算法 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、.是對模糊支配關(guān)系的一種改進，2005年M. Farina首次提出的模糊支配，其隸屬函數(shù)是一條正態(tài)分布函數(shù)，如圖2所示，而此文的隸屬函數(shù)是一條半正態(tài)分布函數(shù)，表達的概念更加清晰。圖2 正態(tài)隸屬函數(shù)對于最小化問題，歸一化后的解A（a1,a2,.,aM），B（b1,b2,.,bM）如果目標向量的某一維上的差量（ai-bi）達到-1，則ai好于bi的程度為1，即pareto支配關(guān)系下ai支配bi；如果差量（ai-bi）是1，則pareto支配關(guān)系下bi支配ai。A模糊支配B程度為每一維差量映射下的隸屬度之積，與種群中其他解進行比較，所得隸屬度相加即為A解在整個中群眾的性能好壞程度，相當于NSGA-I

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、EA模式。參考文獻 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 孔維健, 丁進良, 柴天佑. 高維多目標進化算法研究綜述. 控制與決策. 2010 (03): 321-3263 鞏敦衛(wèi), 季新芳, 孫曉燕. 基于集合的高維多目標優(yōu)化問題的進化算法. 電子學報. 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 陳小紅, 李霞, 王娜. 高維多目標優(yōu)化中基于稀疏特征選擇的目標降維方法. 電子學報. 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、春雨. 基于模糊支配的高維多目標進化算法mfea. 電子學報. 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 鄭金華, 申瑞珉, 李密青, 鄒娟. 一種基于信息分離的高維多目標進化算法. 軟件學報. 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