【文章內(nèi)容簡(jiǎn)介】 策略必須確定哪些個(gè)體作為最優(yōu)個(gè)體加以保留。通常采用優(yōu)勝準(zhǔn)則來(lái)確定最優(yōu)個(gè)體。如果使用伴隨群體的方式，則伴隨群體中包括當(dāng)前的近似Pareto集，即伴隨群體中受控的個(gè)體被移去。但是使用優(yōu)勝關(guān)系比較的方法有時(shí)也存在問(wèn)題，如對(duì)某些連續(xù)型問(wèn)題所對(duì)應(yīng)的Pareto集可能包含無(wú)窮多個(gè)解，因此需要補(bǔ)充其他的信息知識(shí)來(lái)減小所存儲(chǔ)的個(gè)體數(shù)目。這些信息包括密度信息，個(gè)體進(jìn)入伴隨群體所需時(shí)間。MOEAs的最優(yōu)個(gè)體大多利用優(yōu)勝關(guān)系和密度兩者的組合來(lái)進(jìn)行挑選，最優(yōu)個(gè)體保存在每代的伴隨群體中。更新的算法研究表明，如果同時(shí)采用這兩種精英策略，可以進(jìn)一步提高算法的搜索性能與收斂效果。Holland教授提出的遺傳算法，現(xiàn)在一般稱為簡(jiǎn)單遺傳算法或基本遺傳算法[18]，其基本流程如下圖：圖21遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問(wèn)題空間的參數(shù)，因此在算法開(kāi)始進(jìn)行之前，首先要選擇合適的編碼方式對(duì)待優(yōu)化的參數(shù)進(jìn)行編碼。通常采用二進(jìn)制編碼，將參數(shù)轉(zhuǎn)換成為和組成的數(shù)字串。 (2) 產(chǎn)生初始種群：隨機(jī)地產(chǎn)生一個(gè)由個(gè)個(gè)體組成的種群，該種群代表一些可能解的集合。遺傳算法的任務(wù)是種群出發(fā)，模擬生物進(jìn)化的過(guò)程進(jìn)行優(yōu)勝劣汰，最后得出滿足優(yōu)化要求的種群和個(gè)體。 (3) 設(shè)計(jì)適應(yīng)度函數(shù)：把問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度函數(shù)計(jì)算種群中的每個(gè)個(gè)體的適應(yīng)度，為種群進(jìn)化的選擇提供依據(jù)。 (4) 優(yōu)化準(zhǔn)則：也可稱作終止條件，是用來(lái)判斷算法是否可以終止的標(biāo)準(zhǔn)?？梢栽O(shè)定進(jìn)化的最大代數(shù)，當(dāng)進(jìn)化到最大代數(shù)時(shí)，算法終止運(yùn)行。也可以設(shè)定期望的適應(yīng)度函數(shù)值，只有當(dāng)種群中存在個(gè)體能達(dá)到期望值時(shí)，算法才可以結(jié)束。通常情況下，這兩種方法同時(shí)作為優(yōu)化準(zhǔn)則使用。(5) 選擇(復(fù)制)操作:按一定概率從群體中選擇個(gè)體，作為雙親用于繁殖后代，產(chǎn)生新的個(gè)體。在此操作中，適應(yīng)于生存環(huán)境的優(yōu)良個(gè)體將有更多的機(jī)會(huì)繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。(6) 交叉操作:隨機(jī)地選擇用于繁殖的每一對(duì)個(gè)體的同一基因位，將其染色體在此基因位斷開(kāi)并相互交換。(7) 變異操作:以一定的概率從群體中選擇若干個(gè)個(gè)體。對(duì)于選中的個(gè)體，隨機(jī)選擇某一位進(jìn)行取反操作。對(duì)產(chǎn)生的新一代群體重新進(jìn)行評(píng)價(jià)、選擇、雜交和變異。一代一代循環(huán)往復(fù)，使種群中最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個(gè)體的適應(yīng)度滿足優(yōu)化準(zhǔn)則或最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不再提高，則迭代過(guò)程收斂，算法結(jié)束。遺傳算法的選擇和交叉算子賦予了它強(qiáng)有力的搜索能力，變異算子則使算法能搜索到問(wèn)題解空間的每一個(gè)點(diǎn)，以確保算法能達(dá)到全局最優(yōu)。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的領(lǐng)域和種類。對(duì)一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問(wèn)題，一般可以按照上述步驟來(lái)構(gòu)造求解該問(wèn)題的遺傳算法。由上述步驟可以看出，構(gòu)造遺傳算法時(shí)需要考慮的兩個(gè)主要問(wèn)題是可行解的編碼方法和遺傳算子的設(shè)計(jì)，這也是設(shè)計(jì)遺傳算法的兩個(gè)關(guān)鍵步驟。多目標(biāo)遺傳算法的性能評(píng)價(jià)與傳統(tǒng)優(yōu)化算法及單目標(biāo)遺傳算法的性能評(píng)價(jià)有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過(guò)梯度下降速度進(jìn)行評(píng)價(jià)，并且可以通過(guò)嚴(yán)格的數(shù)學(xué)證明分析其收斂性能；單目標(biāo)遺傳算法可以采用基于模式定理或基于馬爾可夫隨機(jī)過(guò)程理論的證明分析其收斂性，盡管這類證明研究還很初步。然而在對(duì)多目標(biāo)進(jìn)化算法的性能進(jìn)行評(píng)價(jià)時(shí)，一般需要考慮到三個(gè)較為重要的因素[19]：算法的效率、算法的效果，以及算法的魯棒性。算法的效率是指算法自身的時(shí)間復(fù)雜度和空間復(fù)雜度，也即算法運(yùn)算時(shí)間的長(zhǎng)短和資源消耗的多少；算法的效果是指算法求得的解集的質(zhì)量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應(yīng)用范圍和穩(wěn)定性，也即是否對(duì)多種問(wèn)題都有很好的求解能力、是否求解問(wèn)題時(shí)總是相對(duì)穩(wěn)定的。而從現(xiàn)階段的研究來(lái)看，人們更關(guān)注的是，算法結(jié)果是否為高質(zhì)量的結(jié)果，而對(duì)于另外兩個(gè)因素相對(duì)要求并不高，而且對(duì)于算法的效率來(lái)說(shuō)，涉及到的是經(jīng)典的算法復(fù)雜度理論，已經(jīng)有很完善的泛化體系對(duì)其進(jìn)行評(píng)價(jià)了，無(wú)需在多目標(biāo)進(jìn)化算法領(lǐng)域?qū)ζ湓龠M(jìn)行專門的研究。所以現(xiàn)階段的性能評(píng)價(jià)方法主要集中于對(duì)算法的效果的衡量。多目標(biāo)進(jìn)化算法的性能評(píng)價(jià)方法有很多，大體上可以分為兩類[20]，一類是評(píng)價(jià)算法的收斂性效果的，一類是評(píng)價(jià)解集的分布性效果的。下面分別對(duì)二者加以介紹。1. 算法收斂性評(píng)價(jià)所謂的收斂性，實(shí)際上是指算法的真實(shí)結(jié)果集與理論上的最優(yōu)結(jié)果集之間的趨近度，即理論上的Pareto邊界和真正得到的Pareto邊界之間的差距。收斂性的評(píng)價(jià)方法有很多種，如錯(cuò)誤率、解集間覆蓋率、世代距離、最大出錯(cuò)率等等。以解集間覆蓋率為例，該覆蓋率又稱為S指標(biāo)(Zitzler, 2000) [21]，用來(lái)計(jì)算一個(gè)解集中被另一個(gè)解集中的個(gè)體支配的個(gè)體所占的比率。如式(31)所示。 (31)對(duì)于收斂性的評(píng)價(jià)指標(biāo)而言，可以通過(guò)指標(biāo)值反映出算法間優(yōu)化效果的差異，但只局限于最優(yōu)解集中更優(yōu)解的數(shù)量，對(duì)于其空間上的特性不做相關(guān)考慮。2. 解集分布性評(píng)價(jià)在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過(guò)于集中，則周圍的很多解事實(shí)上并沒(méi)有太大的意義，也不利于產(chǎn)生新個(gè)體，從而影響了種群的進(jìn)化效果。分布性的評(píng)價(jià)方法也有很多，如空間評(píng)價(jià)方法、基于個(gè)體信息的評(píng)價(jià)方法、網(wǎng)格分布度評(píng)價(jià)方法等等。以空間評(píng)價(jià)方法為例，該方法又被稱為Delta指標(biāo)(Schott, 1995) [22]，用來(lái)計(jì)算解的分布信息的，如式(32)所示。 (32) 其中，對(duì)于分布性的評(píng)價(jià)指標(biāo)而言，只關(guān)注結(jié)果集的分布特性，用以檢測(cè)算法是否被阻在一個(gè)很小的范圍之內(nèi)進(jìn)行搜索，而導(dǎo)致無(wú)法實(shí)現(xiàn)全局的最優(yōu)搜索的現(xiàn)象。由于收斂性評(píng)價(jià)與分布性評(píng)價(jià)的應(yīng)用方向不同，因而在比較算法的時(shí)候，多會(huì)綜合兩種評(píng)價(jià)后，對(duì)算法的性能得出適當(dāng)?shù)慕Y(jié)論?，F(xiàn)有的性能評(píng)價(jià)體系可以分為兩種形式[22]：1. 理論證明理論證明即是對(duì)算法的復(fù)雜度、收斂性等進(jìn)行求解和比較，即通過(guò)理論的分析得出正確的結(jié)論。但是由于多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，多目標(biāo)進(jìn)化計(jì)算的理論基礎(chǔ)尚未成熟，算法收斂性的理論證明對(duì)有限時(shí)間內(nèi)的收斂性分析較少，而時(shí)間無(wú)窮大的收斂性并沒(méi)有工程實(shí)際的應(yīng)用價(jià)值。因此從理論上來(lái)證明算法的優(yōu)劣并不常用，也較難實(shí)現(xiàn)正確的評(píng)估。2. 實(shí)驗(yàn)比較分析實(shí)驗(yàn)比較分析是指通過(guò)對(duì)優(yōu)化算例的結(jié)果和結(jié)果的各種指標(biāo)進(jìn)行比較，驗(yàn)證新算法與已存在的算法之間的性能差別。這種基于解決實(shí)際算例進(jìn)行評(píng)價(jià)的方法具有一定的局限性，很難得出某種算法一定比另外一種更優(yōu)的結(jié)論，其結(jié)論的說(shuō)服力也不夠。但是，由于這種方法可以簡(jiǎn)單直觀的反映出算法的一些特性，所以在分析算法性能領(lǐng)域的應(yīng)用十分廣泛。因此，現(xiàn)有的性能評(píng)價(jià)體系從使用范圍上講，是基于實(shí)驗(yàn)比較分析來(lái)實(shí)現(xiàn)的。 本章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和原理。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，現(xiàn)代多目標(biāo)進(jìn)化算法正是在這些方面存在差異，也是判斷算法之間性能優(yōu)劣的出發(fā)點(diǎn)。第三部分給出了多目標(biāo)進(jìn)化算法的一般流程，這是所有算法的原型，不同算法都是在此基礎(chǔ)上做出改動(dòng)，了解此框架是學(xué)習(xí)其他算法的基礎(chǔ)。最后簡(jiǎn)單介紹了算法的性能評(píng)價(jià)體系，為幾種算法比較的方案提供依據(jù)，得出基于實(shí)驗(yàn)的方法是可行的，本文將在第三章利用這一思想來(lái)試驗(yàn)NSGAⅡ和MOGLS兩種算法的優(yōu)劣。第三章 優(yōu)化算例及分析 NSGAⅡ和MOGLS算法（NSGAⅡ）在NSGA 中, 同一個(gè)小生境內(nèi)的個(gè)體適應(yīng)度共享, 從而降低該小生境內(nèi)個(gè)體的競(jìng)爭(zhēng)力, 防止種群在收斂過(guò)程中陷入局部最優(yōu), 實(shí)現(xiàn)種群多樣性。首先, 對(duì)種群內(nèi)個(gè)體按非劣性排序, 為獲得的Pareto 最優(yōu)解賦予相同的適應(yīng)度。 其次, 根據(jù)Goldberg和Deb等[23]提出的共享方法, 按式(23) 和式( 24) 計(jì)算出每一個(gè)Pareto 最優(yōu)解的小生境數(shù), 將該個(gè)體原適應(yīng)度除以小生境數(shù),就得到它的共享適應(yīng)度。這樣, 處于同一個(gè)Pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應(yīng)度也不同。 (23)其中, 表示個(gè)體 與個(gè)體 的距離, 是同一小生境中個(gè)體間的最大允許距離, 表示距離為時(shí)的共享函數(shù)值。其中, ( 24) 表示個(gè)體i 的小生境數(shù)。雖然非支配排序遺傳算法（NSGA）在許多問(wèn)題上得到了應(yīng)用，但仍存在一些問(wèn)題，如計(jì)算復(fù)雜度較高，需要指定共享半徑，易丟失已經(jīng)得到的滿意解。NSGAⅡ針對(duì)以上的缺陷通過(guò)以下三個(gè)方面進(jìn)行了改進(jìn)：(1)提出了快速非支配排序法，在選擇運(yùn)算之前，根據(jù)個(gè)體的非劣解水平對(duì)種群分級(jí)。首先將當(dāng)前的所有的非劣解個(gè)體劃為同一等級(jí)，令其等級(jí)為；然后將這些個(gè)體從種群中移出，在剩余個(gè)體中尋找出新的非劣解，再令其等級(jí)為；重復(fù)上述過(guò)程，直至種群中所有個(gè)體都被設(shè)定相應(yīng)的等級(jí)。具體方法與NSGA的快速非支配排序方法不同，NSGAⅡ?qū)τ诿總€(gè)個(gè)體都設(shè)有以下兩個(gè)參數(shù)和，為在種群中支配個(gè)體的解個(gè)體的數(shù)量，為被個(gè)體所支配的解個(gè)體的集合。首先，找到種群中所有的個(gè)體，將它們存入當(dāng)前集合，然后對(duì)于當(dāng)前集合的每個(gè)個(gè)體，考察它所支配的個(gè)體集,將集合中的每個(gè)個(gè)體的減去1，即支配個(gè)體的解個(gè)體數(shù)減1，如果則將個(gè)體存入另一個(gè)集。最后，將作為第一級(jí)非支配個(gè)體集合，并賦予該集合內(nèi)個(gè)體一個(gè)相同的非支配序，然后繼續(xù)對(duì)作上述分級(jí)操作并賦予相應(yīng)的非支配序，直到所有個(gè)體都被分級(jí)。如此操作降低了算法的計(jì)算復(fù)雜度。由原來(lái)的降到，其中，為目標(biāo)函數(shù)個(gè)數(shù)，為種群大小。(2)提出了擁擠度和擁擠度比較算子，代替了需要指定共享半徑的適應(yīng)度共享策略，并在快速排序后的同級(jí)比較中作為勝出標(biāo)準(zhǔn)，使準(zhǔn)Pareto域中的個(gè)體能擴(kuò)展到整個(gè)域，并均勻分布，保持了種群的多樣性。擁擠度的概念：擁擠度是指在種群中的給定點(diǎn)的周圍個(gè)體的密度，計(jì)算上要考慮個(gè)體周圍包含本身但不包含其他個(gè)體的最小正方形，如下圖，個(gè)體的聚集距離是。為了計(jì)算每個(gè)個(gè)體的聚集距離，需要對(duì)群體按每個(gè)子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對(duì)個(gè)子目標(biāo)分別進(jìn)行排序的時(shí)間復(fù)雜度為。從圖中可以看出值較小時(shí)，該個(gè)體周圍就比較擁擠，那么這幾個(gè)個(gè)體的適應(yīng)度就要降低，使得分布比較分散的解能保留下的幾率加大。擁擠度比較算子：為了維持種群的多樣性，需要一個(gè)比較擁擠度的算子以確保算法能夠收斂到一個(gè)均勻分布的Pareto面上。由于經(jīng)過(guò)了排序和擁擠度計(jì)算，群體中每個(gè)個(gè)體都得到了兩個(gè)屬性：非支配序和擁擠度，則定義偏序關(guān)系（）：當(dāng)滿足條件，或滿足且時(shí)，定義。即如果兩個(gè)個(gè)體的非支配排序不同，取排序號(hào)較小的個(gè)體；如果兩個(gè)個(gè)體在同一級(jí)，取周圍較不擁擠的個(gè)體。(3)引入精英策略，擴(kuò)大采樣空間。將父代種群與其產(chǎn)生的子代種群組合，共同競(jìng)爭(zhēng)產(chǎn)生下一代種群，有利于保持父代中的優(yōu)良個(gè)體進(jìn)入下一代，并通過(guò)對(duì)種群中所有個(gè)體的分層存放，使得最佳個(gè)體不會(huì)丟失，迅速提高種群水平。NSGAⅡ算法的主流程：首先隨即初始化一個(gè)父代種群，并將所有個(gè)體按非支配關(guān)系排序，且指定一個(gè)適應(yīng)度值。然后采用選擇、交叉、變異算子產(chǎn)生下一代種群，大小也為，完成第一代進(jìn)化。在產(chǎn)生新種群后，將與其父代種群合并組成，此時(shí)種群大小為。然后進(jìn)行非支配排序，產(chǎn)生一系列非支配集并計(jì)算擁擠度，通常選擇前個(gè)個(gè)體組成，滿足且。在上圖中，由于子代和父代個(gè)體都包含在中，則經(jīng)過(guò)非支配排序以后的非支配集中包含的個(gè)體是中最好的，所以先將放入新的父代種群中。如果的大小小于，則繼續(xù)向中填充，直到添加到時(shí)種群大小超出，對(duì)中的個(gè)體進(jìn)行擁擠度排序，取前個(gè)個(gè)體。使個(gè)體數(shù)量達(dá)到。然后通過(guò)遺傳算子產(chǎn)生新的子代種群。當(dāng)排序產(chǎn)生的非支配集的個(gè)體數(shù)目足夠填充時(shí)，就不必再繼續(xù)對(duì)剩下的部分排序了。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。算法流程圖：圖31 NSGAⅡ的算法流程在MOGLS中，局部搜索過(guò)程應(yīng)用于通過(guò)遺傳操作所獲得每一個(gè)解。這種算法應(yīng)用在適應(yīng)度評(píng)價(jià)功能上應(yīng)用一種計(jì)算權(quán)值和的方式，即當(dāng)一對(duì)父代種群被選擇通過(guò)交叉變異去獲得新解時(shí)使用這個(gè)功能。局部搜索過(guò)程應(yīng)用于新解而最大限度地發(fā)揮它的適應(yīng)度的效率[24]。這個(gè)算法的一大典型特性是無(wú)論何時(shí)選擇一組父代種群都要指定權(quán)值效率。每個(gè)解通過(guò)不同的權(quán)值矢量執(zhí)行。另一個(gè)特點(diǎn)是在局部搜索的過(guò)程中不需要計(jì)算當(dāng)前種群的所有鄰域解，只有少部分鄰域解被檢驗(yàn)避免在這個(gè)算法中消耗過(guò)多的所有可行解的計(jì)算時(shí)間。多目標(biāo)遺傳局部搜索算法試圖尋找多目標(biāo)最有問(wèn)題所有的非支配解，如果在一個(gè)多目標(biāo)問(wèn)題中一個(gè)解不被其他解支配，它叫做非劣解，一個(gè)多目標(biāo)問(wèn)題有許多非劣解。雜交算法的目的不是確定一個(gè)單一的最終解，而是試圖尋找這個(gè)多目標(biāo)問(wèn)題所有符合約束條件的最優(yōu)解。當(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）。 （2） (26)如果我們使用連續(xù)的權(quán)值，通過(guò)GA局部搜索的方向是已經(jīng)固定的。連續(xù)權(quán)值策略和一個(gè)目標(biāo)的選擇方式都不能為尋找所有的多目標(biāo)問(wèn)題的非劣解高效的服務(wù)，這是因?yàn)楦鞣N搜索方向需要尋找多種非劣解。為了實(shí)現(xiàn)各個(gè)方向搜索，而提出這種算法。這個(gè)權(quán)值被定義為 (27) 其中，是隨機(jī)值。無(wú)論何時(shí)選擇一組父代種群我們都這樣定義權(quán)值。在此算法中局部搜索應(yīng)用每個(gè)由父代種群向子代種群進(jìn)化的過(guò)程中，新種群的適應(yīng)度通過(guò)被用于選擇父代種群的權(quán)值而定義，這樣，對(duì)每個(gè)解的局部搜索的方向就由應(yīng)用于它的父代解選擇的權(quán)值定義了。這種方法下，每個(gè)解都有自己的搜索方向。另一個(gè)值得注意的是，如何決定介于局部搜索和進(jìn)化操作的可行計(jì)算時(shí)間。按照慣例的局部搜索，只有等在檢驗(yàn)所有相鄰解后沒(méi)找到比當(dāng)前解更好的解時(shí)，搜索才結(jié)束。本算法不會(huì)花相當(dāng)長(zhǎng)的時(shí)間，還有代數(shù)通過(guò)遺傳操作更新能夠反復(fù)聲明很多次?？傊?，我們能通過(guò)局部搜索調(diào)整計(jì)算時(shí)間。從用于通過(guò)交叉操作的后代群體的當(dāng)前群體中選擇一組父代解，、，已經(jīng)通過(guò)上面的式