【正文】 基于實(shí)驗(yàn)的方法是可行的，本文將在第三章利用這一思想來(lái)試驗(yàn)NSGAⅡ和MOGLS兩種算法的優(yōu)劣。首先, 對(duì)種群內(nèi)個(gè)體按非劣性排序, 為獲得的Pareto 最優(yōu)解賦予相同的適應(yīng)度。這樣, 處于同一個(gè)Pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應(yīng)度也不同。其中, ( 24) 表示個(gè)體i 的小生境數(shù)。NSGAⅡ針對(duì)以上的缺陷通過(guò)以下三個(gè)方面進(jìn)行了改進(jìn)：(1)提出了快速非支配排序法，在選擇運(yùn)算之前，根據(jù)個(gè)體的非劣解水平對(duì)種群分級(jí)。具體方法與NSGA的快速非支配排序方法不同，NSGAⅡ?qū)τ诿總€(gè)個(gè)體都設(shè)有以下兩個(gè)參數(shù)和，為在種群中支配個(gè)體的解個(gè)體的數(shù)量，為被個(gè)體所支配的解個(gè)體的集合。最后，將作為第一級(jí)非支配個(gè)體集合，并賦予該集合內(nèi)個(gè)體一個(gè)相同的非支配序，然后繼續(xù)對(duì)作上述分級(jí)操作并賦予相應(yīng)的非支配序，直到所有個(gè)體都被分級(jí)。由原來(lái)的降到，其中，為目標(biāo)函數(shù)個(gè)數(shù)，為種群大小。擁擠度的概念：擁擠度是指在種群中的給定點(diǎn)的周?chē)鷤€(gè)體的密度，計(jì)算上要考慮個(gè)體周?chē)旧淼话渌麄€(gè)體的最小正方形，如下圖，個(gè)體的聚集距離是。從圖中可以看出值較小時(shí)，該個(gè)體周?chē)捅容^擁擠，那么這幾個(gè)個(gè)體的適應(yīng)度就要降低，使得分布比較分散的解能保留下的幾率加大。由于經(jīng)過(guò)了排序和擁擠度計(jì)算，群體中每個(gè)個(gè)體都得到了兩個(gè)屬性：非支配序和擁擠度，則定義偏序關(guān)系（）：當(dāng)滿足條件，或滿足且時(shí)，定義。(3)引入精英策略，擴(kuò)大采樣空間。NSGAⅡ算法的主流程：首先隨即初始化一個(gè)父代種群，并將所有個(gè)體按非支配關(guān)系排序，且指定一個(gè)適應(yīng)度值。在產(chǎn)生新種群后，將與其父代種群合并組成，此時(shí)種群大小為。在上圖中，由于子代和父代個(gè)體都包含在中，則經(jīng)過(guò)非支配排序以后的非支配集中包含的個(gè)體是中最好的，所以先將放入新的父代種群中。使個(gè)體數(shù)量達(dá)到。當(dāng)排序產(chǎn)生的非支配集的個(gè)體數(shù)目足夠填充時(shí)，就不必再繼續(xù)對(duì)剩下的部分排序了。算法流程圖：圖31 NSGAⅡ的算法流程在MOGLS中，局部搜索過(guò)程應(yīng)用于通過(guò)遺傳操作所獲得每一個(gè)解。局部搜索過(guò)程應(yīng)用于新解而最大限度地發(fā)揮它的適應(yīng)度的效率[24]。每個(gè)解通過(guò)不同的權(quán)值矢量執(zhí)行。多目標(biāo)遺傳局部搜索算法試圖尋找多目標(biāo)最有問(wèn)題所有的非支配解，如果在一個(gè)多目標(biāo)問(wèn)題中一個(gè)解不被其他解支配，它叫做非劣解，一個(gè)多目標(biāo)問(wèn)題有許多非劣解。當(dāng)我們應(yīng)用GA算法解決多目標(biāo)問(wèn)題時(shí)，需要評(píng)價(jià)每個(gè)解的適應(yīng)度，我們通過(guò)計(jì)算個(gè)目標(biāo)權(quán)值和的方式定義一個(gè)解的適應(yīng)度函數(shù)： (25)是這個(gè)目標(biāo)的權(quán)值，它們符合以下條件：（1）。連續(xù)權(quán)值策略和一個(gè)目標(biāo)的選擇方式都不能為尋找所有的多目標(biāo)問(wèn)題的非劣解高效的服務(wù)，這是因?yàn)楦鞣N搜索方向需要尋找多種非劣解。這個(gè)權(quán)值被定義為 (27) 其中，是隨機(jī)值。在此算法中局部搜索應(yīng)用每個(gè)由父代種群向子代種群進(jìn)化的過(guò)程中，新種群的適應(yīng)度通過(guò)被用于選擇父代種群的權(quán)值而定義，這樣，對(duì)每個(gè)解的局部搜索的方向就由應(yīng)用于它的父代解選擇的權(quán)值定義了。另一個(gè)值得注意的是，如何決定介于局部搜索和進(jìn)化操作的可行計(jì)算時(shí)間。本算法不會(huì)花相當(dāng)長(zhǎng)的時(shí)間，還有代數(shù)通過(guò)遺傳操作更新能夠反復(fù)聲明很多次。從用于通過(guò)交叉操作的后代群體的當(dāng)前群體中選擇一組父代解，、已經(jīng)通過(guò)上面的式子確定，在當(dāng)前種群中每個(gè)解的適應(yīng)度已經(jīng)作為個(gè)目標(biāo)權(quán)值之和而得到。局部搜索的步驟：（1）：指定一個(gè)初始解；（2）：檢驗(yàn)初始解的相鄰解；（3）：如果比好，那么用代替；（4）：如果得所有相鄰解都已經(jīng)被檢驗(yàn)了，結(jié)束這個(gè)過(guò)程，否則返回（1）；在（4）中可以看出，對(duì)一個(gè)初始解通過(guò)局部搜索檢驗(yàn)的解的總數(shù)要遠(yuǎn)大于相鄰解的總數(shù)[25]。局部搜索后，當(dāng)前種群已被進(jìn)化的種群替換，接著試驗(yàn)的非劣解被新的當(dāng)前種群所更新，即如果當(dāng)前種群的一個(gè)解不受其他解和試驗(yàn)的非劣解集支配，那么將此解添加進(jìn)這個(gè)試驗(yàn)集合，在試驗(yàn)集合中被這個(gè)解支配的其他解就被剔除。MOGLS的步驟：（1）初始化，隨機(jī)產(chǎn)生一個(gè)初始種群：是這個(gè)種群解的個(gè)數(shù)。（3）選擇：重復(fù)以下過(guò)程去選擇父代解的： 通過(guò)(27) 在適應(yīng)度函數(shù)(*1)中計(jì)算隨機(jī)的權(quán)值，、。（4）交叉和變異：從父代解中選擇的對(duì)，分別應(yīng)用交叉過(guò)程，從每個(gè)父代解的對(duì)中產(chǎn)生新解，然后對(duì)新解使用變異操作。（6）局部搜索：在當(dāng)前種群對(duì)所有解應(yīng)用改進(jìn)的局部搜索過(guò)程，對(duì)每個(gè)解的局部搜索方向已經(jīng)由父代解被選擇的適應(yīng)度函數(shù)中的權(quán)值確定。（7）終止測(cè)試：如果一個(gè)提前確定的停止條件被滿足，結(jié)束算法，否則，返回第二步。但MOGLS能處理帶有凹的Praeto前端的多目標(biāo)進(jìn)化問(wèn)題。在采用驗(yàn)證算法比較時(shí)，C指標(biāo)使用最為普遍[26]。若，則說(shuō)明對(duì)于集中的任一個(gè)非劣解個(gè)體，集中總存在“優(yōu)于”(dominace)它的解個(gè)體；，說(shuō)明對(duì)于集中任一個(gè)解個(gè)體，集中都不存在“優(yōu)于”它的解個(gè)體。已有的測(cè)試函數(shù)的設(shè)計(jì)原則主要有：（1）優(yōu)化問(wèn)題為非凸情形下的優(yōu)化性能測(cè)試；（2）優(yōu)化問(wèn)題目標(biāo)空間不連續(xù)情形下的優(yōu)化性能測(cè)試；（3）多變量?jī)?yōu)化問(wèn)題的優(yōu)化性能測(cè)試。尤其是Zitzler、Deb、Thiele提出的系列測(cè)試函數(shù)，是目前為止評(píng)價(jià)新的多目標(biāo)優(yōu)化算法性能時(shí)采用最廣泛的測(cè)試函數(shù)族[27]，因此，對(duì)新算法的評(píng)價(jià)及其改進(jìn)具有重要的指導(dǎo)意義。為了對(duì)NSGAII和MOGLS兩種多目標(biāo)遺傳算法性能進(jìn)行考察，選擇ZDTKUR ：（1）KUR：變量個(gè)數(shù)是3，（2）ZDT4:變量個(gè)數(shù)是10， 對(duì)于函數(shù)優(yōu)化算例，本文采用實(shí)數(shù)編碼方式，即基因編碼中的每個(gè)位置表示優(yōu)化變量中的一個(gè)變量。設(shè)與為當(dāng)前群體隨機(jī)抽出的兩個(gè)進(jìn)行交叉的父代個(gè)體，、為線性交叉后生成的兩個(gè)新個(gè)體，則線性交叉算子實(shí)現(xiàn)方式如公式所示： 其中，為之間的隨機(jī)數(shù)。 采用NSGAⅡ和MOGLS對(duì)KUR算例進(jìn)行優(yōu)化時(shí)，兩種算法均設(shè)置相同的進(jìn)化參數(shù)，以便保證各算法的進(jìn)化條件相同或相似，從而可以根據(jù)算法求解到的非劣解集的優(yōu)劣評(píng)價(jià)算法的相對(duì)性能[28]。經(jīng)實(shí)驗(yàn)確定，三種算法優(yōu)化測(cè)試函數(shù)的進(jìn)化參數(shù)設(shè)定為：群體規(guī)模：100/200進(jìn)化代數(shù)：500/1000交叉概率：變異概率：MOGLS每代個(gè)體的非劣解局部搜索步長(zhǎng)：5所以本實(shí)驗(yàn)要獲得8組解。為了進(jìn)一步通過(guò)直觀比較法確定兩種算法的優(yōu)化性能，本文采用Zitzler在文獻(xiàn)[29]中提出的方法對(duì)算法性能進(jìn)行直觀評(píng)價(jià)。；(2)運(yùn)行算法，令；(3)若時(shí)算法停止運(yùn)行；(4)若，則，轉(zhuǎn)到(2)，否則，轉(zhuǎn)到(2)； 所有算法運(yùn)行完畢后，剔除各算法非劣解集中的劣解，然后比較各算法所得最終非劣解集(分布圖)的等級(jí)優(yōu)先程度及非劣解分布的均勻程度，最終確定算法優(yōu)化性能的優(yōu)劣[30]。采用三種算法分別對(duì)各算例獨(dú)立優(yōu)化30次，將所得非劣解合并，在完成30次獨(dú)立優(yōu)化后，剔除各算法非劣解并集中的相同個(gè)體及劣解，得到各算法優(yōu)化的最終非劣解集，如下圖所示。因此，本文在比較函數(shù)優(yōu)化算例結(jié)果時(shí)，首先對(duì)兩種種算法優(yōu)化和所得的結(jié)果進(jìn)行比較，進(jìn)而初步確定這兩種算法對(duì)于少變量復(fù)雜空間優(yōu)化問(wèn)題的求解性能，然后參照兩種種算法求解ZDT4算例所得的非劣解集(見(jiàn)附錄B)，通過(guò)類(lèi)似方法評(píng)價(jià)出算法對(duì)多變量函數(shù)優(yōu)化問(wèn)題的求解能力。上述分析可以看出，在復(fù)雜優(yōu)化空間多目標(biāo)函數(shù)算例優(yōu)化中，NSGAII獲得了明顯好于MOGLS算法的非劣解集，初步顯示了它的良好優(yōu)化性能。而后沿用了經(jīng)典的進(jìn)化結(jié)構(gòu)，基于這種策略，引用C指標(biāo)對(duì)比了NSGAII和MOGLS算法的性能。雖然實(shí)驗(yàn)比較分析的方法已經(jīng)在本學(xué)科內(nèi)廣泛的被使用，且有它的一些優(yōu)點(diǎn)，但是它本身也存在著一些問(wèn)題：1. 算法間的差異較大，可比性較差因?yàn)樗鼈兌际歉鶕?jù)不同的特定問(wèn)題而提出的，算法結(jié)構(gòu)、參數(shù)等都不盡相同，所以當(dāng)問(wèn)題改變的時(shí)候，一般需要修改算法才能適應(yīng)新問(wèn)題，這使得算法間較難進(jìn)行集成比較。另外，對(duì)于結(jié)果的比較，也應(yīng)該有統(tǒng)一的、通用的優(yōu)劣標(biāo)準(zhǔn)或指標(biāo)體系。但是，同樣由于上面提及的算法間集成性差的原因，當(dāng)研究人員提出一種新算法，需要評(píng)價(jià)一下該算法的性能，或比較已有算法間的性能差別時(shí)，只能算法逐一執(zhí)行，然后將各算法的結(jié)果進(jìn)行人工分析、手動(dòng)計(jì)算。另外，評(píng)估一個(gè)算法的優(yōu)劣，往往需要反復(fù)大量的評(píng)測(cè)才能得出相對(duì)準(zhǔn)確的性能結(jié)論。3. 靜態(tài)的環(huán)境與參數(shù)目前的各種性能測(cè)試都只能針對(duì)靜態(tài)環(huán)境，即固定的參數(shù)。而以現(xiàn)有的條件來(lái)看，這是很難辦到的，研究人員只能在給定初始參數(shù)后，運(yùn)行算法，等待結(jié)果的輸出，而中間的執(zhí)行過(guò)程透明，也不可控，這使得通過(guò)測(cè)試來(lái)進(jìn)行算法改進(jìn)的效率較為低下。而后又總結(jié)了MOEA的研究現(xiàn)狀，就是以進(jìn)化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進(jìn)化策略局部搜索的優(yōu)勢(shì)，獲得高性能的多目標(biāo)優(yōu)化算法，成為多目標(biāo)進(jìn)化算法研究的潛在發(fā)展方向第二章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和最優(yōu)性原理。 而后給出了多目標(biāo)進(jìn)化算法的一般流程，不同算法都是在此基礎(chǔ)上做出改動(dòng)而得到的。第三章本章首先詳細(xì)介紹了NSGAII和MOGLS的原理及流程，特別是兩種方法存在差異的適應(yīng)度評(píng)價(jià)和精英保留策略。采用這兩種算法對(duì)典型的多目標(biāo)函數(shù)優(yōu)化KUR算例進(jìn)行了優(yōu)化求解，將兩種算法的所得結(jié)果進(jìn)行比較分析，研究結(jié)果表明，NSGAII有比 MOGLS更優(yōu)的非劣解等級(jí)及非劣解集分布，因此驗(yàn)證了這兩種算法對(duì)多目標(biāo)函數(shù)優(yōu)化問(wèn)題的求解性能的強(qiáng)弱關(guān)系。在今后對(duì)算法做進(jìn)一步研究時(shí),還可將與實(shí)際求解問(wèn)題相關(guān)的啟發(fā)式規(guī)則或啟發(fā)式算法引入非劣解局部搜索過(guò)程,以達(dá)到有效利用現(xiàn)有各學(xué)科專(zhuān)業(yè)知識(shí)指導(dǎo)局部搜索的目的,則GA 的全局搜索優(yōu)勢(shì)與啟發(fā)式快速鄰域搜索的優(yōu)勢(shì)相結(jié)合,算法尋求多目標(biāo)優(yōu)化問(wèn)題非劣解的效率和結(jié)果有望得到進(jìn)一步提高。 Sons, Chichester, UK, 2001.[12]林銼云，[M].長(zhǎng)春：吉林教育出版社,1992[13] 崔遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京: 國(guó)防工業(yè)出版社，2006.[14]李莉. 基于遺傳算法的多目標(biāo)進(jìn)化算法綜述[A]. 中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C], 2007: 363365.[15] 李晶. 一種基于局部收斂估計(jì)的多目標(biāo)進(jìn)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(23): 4952.[16] 崔遜學(xué). 一種基于偏好的多目標(biāo)調(diào)和遺傳算法[J]. 軟件學(xué)報(bào)，2005, 6(5): 761767.[17] 王向慧. 基于Pareto最優(yōu)概念的多目標(biāo)進(jìn)化算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用. 2008, 44(27): 5861.[18]王小平，曹立明，遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M]，西安；西安交通大學(xué)出版社，2002[19] K. Deb, A. Pratap, , et al. A fast and elitist multiobjective genetic algorithm: NSGAII [J]. IEEE Transactions on Evolutionary Computation, 6(2):182197, April 2002.[20] 崔遜學(xué), 林闖. 多目標(biāo)進(jìn)化算法的研究與發(fā)展[J]. 模式識(shí)別與人工智能, 2003,16(3): 306314,.[21]. Tan, . Lee, . Khor. Evolutionary Algorithms for MultiObjective Optimization: Performance Assessments and Comparisons [J]. Proceedings of the 2001 Congress on Evolutionary Computation, (2): 979986, 2001.[22] . Coello. Handling preferences in evolutionary multiobjective optimization: a survey [J]. Proceedings of the 2000 Congress on Evolutionary Computation, (1): 3037, 2000.[23] Goldberg D E, Richardson algorithms with sharing for multimodal function optimization[C]//Proc of the 2nd Int’l Conf on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum, 1987: 41 49. [24] genetic algorithm and its applications to flowshop scheduling[J].Computers ,1996,30(4):957968. [25] MultiObject genetic local search algorithm and its application to flowshop Transactions on Systems,1998,28(3):392403.[26]Nemhauser .,Wolsey ..Integer and Combinatorial Optimization[M].Canada:John Wileyamp。 Pm = MaxGens = 500 PopSize = 100Pc = 。 Pm = MaxGens = 1000 PopSize = 100Pc = 。 Pm = MaxGens = 500 PopSize = 200Pc = 。 Pm = MaxGens = 1000 PopSize = 200Pc = 。 Pm = MaxGens = 500 PopSize = 100Pc = 。 Pm = MaxGens = 1000 PopSize = 100Pc = 。 Pm = MaxGens = 500 PopSize = 200Pc = 。 Pm = MaxGens = 1000 PopSize = 200Pc