【正文】 = 。 而后給出了多目標(biāo)進(jìn)化算法的一般流程，不同算法都是在此基礎(chǔ)上做出改動(dòng)而得到的。而后沿用了經(jīng)典的進(jìn)化結(jié)構(gòu)，基于這種策略，引用C指標(biāo)對(duì)比了NSGAII和MOGLS算法的性能。設(shè)與為當(dāng)前群體隨機(jī)抽出的兩個(gè)進(jìn)行交叉的父代個(gè)體，、為線性交叉后生成的兩個(gè)新個(gè)體，則線性交叉算子實(shí)現(xiàn)方式如公式所示： 其中，為之間的隨機(jī)數(shù)。（6）局部搜索：在當(dāng)前種群對(duì)所有解應(yīng)用改進(jìn)的局部搜索過程，對(duì)每個(gè)解的局部搜索方向已經(jīng)由父代解被選擇的適應(yīng)度函數(shù)中的權(quán)值確定。另一個(gè)值得注意的是，如何決定介于局部搜索和進(jìn)化操作的可行計(jì)算時(shí)間。算法流程圖：圖31 NSGAⅡ的算法流程在MOGLS中，局部搜索過程應(yīng)用于通過遺傳操作所獲得每一個(gè)解。從圖中可以看出值較小時(shí)，該個(gè)體周圍就比較擁擠，那么這幾個(gè)個(gè)體的適應(yīng)度就要降低，使得分布比較分散的解能保留下的幾率加大。首先, 對(duì)種群內(nèi)個(gè)體按非劣性排序, 為獲得的Pareto 最優(yōu)解賦予相同的適應(yīng)度。分布性的評(píng)價(jià)方法也有很多，如空間評(píng)價(jià)方法、基于個(gè)體信息的評(píng)價(jià)方法、網(wǎng)格分布度評(píng)價(jià)方法等等。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種類。通常采用二進(jìn)制編碼，將參數(shù)轉(zhuǎn)換成為和組成的數(shù)字串。該方法采用一個(gè)網(wǎng)格來定義空間上的鄰居關(guān)系，個(gè)體的密度只要通過簡(jiǎn)單地統(tǒng)計(jì)同一網(wǎng)格內(nèi)的個(gè)體數(shù)目即可，這種網(wǎng)絡(luò)可以是固定的，也可以根據(jù)當(dāng)前群體進(jìn)行自適應(yīng)調(diào)整。(2)利用線性或非線性的插值方法在最低序號(hào)與最高序號(hào)之間進(jìn)行插值。這種適應(yīng)值設(shè)計(jì)的遺傳算法通常需要在算法進(jìn)化過程中系統(tǒng)地對(duì)函數(shù)中的參數(shù)的權(quán)重值進(jìn)行調(diào)整，以便得到一組非劣解集。設(shè)和是進(jìn)化群體中的任意兩個(gè)不同的個(gè)體,稱支配(dominate) ,則必須滿足下列二個(gè)條件:( 1) 對(duì)所有的子目標(biāo), 不比 差, 即 ( k=1, 2,?, r) 。其中，后決策是最常用的技術(shù)，即算法終止時(shí)提供給用戶一組最優(yōu)解。由于這類算法是基于Pareto概念的MOGA，因此，它的優(yōu)點(diǎn)是可以通過單次優(yōu)化獲得一組靠近真實(shí)非劣解前沿的非劣解集；但由于算法未考慮進(jìn)化過程中精英個(gè)體的保留，因此解的收斂速度及收斂性能不夠穩(wěn)健。在專業(yè)文獻(xiàn)中,有許多數(shù)學(xué)規(guī)劃技巧解決MOP ,如多目標(biāo)加權(quán)法、分層序列法、約束法、目標(biāo)規(guī)劃法等。生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得品種不斷的到改良，這種生命現(xiàn)象叫做進(jìn)化。例如，隨著這類算法的快速發(fā)展，對(duì)算法之間性能進(jìn)行比較變得越來越重要。例如,在設(shè)計(jì)一座橋梁時(shí),我們一方面希望建設(shè)橋梁的費(fèi)用最小,另一方面希望橋梁具有最大的安全性。有些方法要求目標(biāo)函數(shù)和約束條件可微。代表算法有NPGAII、NSGAII、PAES和SPEA等[9]。由于本文需要對(duì)多目標(biāo)進(jìn)化算法的結(jié)構(gòu)進(jìn)行深入的分析，所以需要在此選擇一個(gè)代表性的算法，通過該算法的簡(jiǎn)介，來描述一下多目標(biāo)進(jìn)化算法的一些基本概念和工作原理。定義2( Pareto 非支配集)。這種策略存在的問題是進(jìn)化結(jié)果容易偏向某些極端邊界解，并且對(duì)Pareto最優(yōu)前端的非凸部敏感。如果單純從群體多樣性出發(fā)，群體規(guī)模應(yīng)該越大越好，但群體規(guī)模太大會(huì)帶來若干弊?。阂皇菑挠?jì)算效率來看，群體越大，導(dǎo)致其適應(yīng)度評(píng)估次數(shù)增加，引起計(jì)算量的增加，從而影響算法效能；二是群體中個(gè)體生存下來的選擇概率大多采用和適應(yīng)度成比例的方法，當(dāng)群體中個(gè)體非常多時(shí)，少量適應(yīng)度很高的個(gè)體會(huì)被選擇而生存下來，大多數(shù)個(gè)體被淘汰，嚴(yán)重影響交叉操作。遺傳算法是基于隨機(jī)進(jìn)化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標(biāo)遺傳算法大都引入了精英保留策略?？梢栽O(shè)定進(jìn)化的最大代數(shù)，當(dāng)進(jìn)化到最大代數(shù)時(shí)，算法終止運(yùn)行。算法的效率是指算法自身的時(shí)間復(fù)雜度和空間復(fù)雜度，也即算法運(yùn)算時(shí)間的長(zhǎng)短和資源消耗的多少；算法的效果是指算法求得的解集的質(zhì)量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應(yīng)用范圍和穩(wěn)定性，也即是否對(duì)多種問題都有很好的求解能力、是否求解問題時(shí)總是相對(duì)穩(wěn)定的。但是由于多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，多目標(biāo)進(jìn)化計(jì)算的理論基礎(chǔ)尚未成熟，算法收斂性的理論證明對(duì)有限時(shí)間內(nèi)的收斂性分析較少，而時(shí)間無窮大的收斂性并沒有工程實(shí)際的應(yīng)用價(jià)值。雖然非支配排序遺傳算法（NSGA）在許多問題上得到了應(yīng)用，但仍存在一些問題，如計(jì)算復(fù)雜度較高，需要指定共享半徑，易丟失已經(jīng)得到的滿意解。將父代種群與其產(chǎn)生的子代種群組合，共同競(jìng)爭(zhēng)產(chǎn)生下一代種群，有利于保持父代中的優(yōu)良個(gè)體進(jìn)入下一代，并通過對(duì)種群中所有個(gè)體的分層存放，使得最佳個(gè)體不會(huì)丟失，迅速提高種群水平。另一個(gè)特點(diǎn)是在局部搜索的過程中不需要計(jì)算當(dāng)前種群的所有鄰域解，只有少部分鄰域解被檢驗(yàn)避免在這個(gè)算法中消耗過多的所有可行解的計(jì)算時(shí)間。解選擇概率已經(jīng)通過使用線性縮放的輪盤賭方法得到： (28) 是當(dāng)前群體最壞解的適應(yīng)度。具體流程見下圖：現(xiàn)有研究中，對(duì)新的多目標(biāo)遺傳算法進(jìn)行性能評(píng)價(jià)時(shí)，普遍采用兩種方法：一種是構(gòu)造一系列可以獨(dú)立評(píng)價(jià)算法性能的指標(biāo)用于考察算法搜索到的非劣解集的優(yōu)劣；另一種是選取一種迄今為止性能優(yōu)越的驗(yàn)證算法與新算法在相同進(jìn)化條件下對(duì)測(cè)試算例進(jìn)行優(yōu)化，比較搜索到的非劣解集。 首先，計(jì)算兩種算法優(yōu)化算例得到的C指標(biāo)（見附錄A），從附錄A中可以反映出，C（NSGAII,MOGLS）接近于1，C（MOGLS ，NSGAII）接近于零，即NSGAII算法優(yōu)于MOGLS算法。2. 人工操作用實(shí)驗(yàn)來評(píng)價(jià)算法的性能，目前基本是靠算法結(jié)果的人工審查，以及各種性能指標(biāo)值的比較。本文在現(xiàn)有兩種多目標(biāo)進(jìn)化算法的基礎(chǔ)上，通過算例分析了它們的模式和性能，比較了它們精英保留策略的復(fù)制方式通過與兩種現(xiàn)有多目標(biāo)遺傳算法NSGA 和MOGLS 對(duì)KUR多目標(biāo)連續(xù)函數(shù)算例的優(yōu)化,初步驗(yàn)證了算法的有效性，今后可以對(duì)其他兩到三種算法進(jìn)行性能比較；此外通過設(shè)置不同的遞進(jìn)參數(shù)與每層進(jìn)化代數(shù)對(duì)兩個(gè)算例進(jìn)行優(yōu)化的結(jié)果分析,進(jìn)一步深入分析了遞進(jìn)層數(shù)與遺傳進(jìn)化代數(shù)設(shè)置的比例對(duì)算法性能的影響。 Pm = C(N,M)C(M,N)C(N,M)C(M,N)C(N,M)C(M,N)C(N,M)C(M,N)123456789101112131415161718192021222324252627282930最大最小平均方差采用NSGAII和MOGLS優(yōu)化ZDT4結(jié)果(續(xù))MaxGens = 500 PopSize = 200Pc = 。 Pm = MaxGens = 1000 PopSize = 200Pc = 。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，包括適應(yīng)值設(shè)計(jì)、維持群體多樣性和精英保留策略。本章首先詳細(xì)介紹了NSGAII和MOGLS的原理及流程，特別是兩種方法存在差異的適應(yīng)度評(píng)價(jià)和精英保留策略。分別選用線性交叉和非均勻變異方式生成新個(gè)體。（5）精英保留策略：從試驗(yàn)非劣解集中隨機(jī)選擇解，接著將這個(gè)選中的解加入到在(4)中解中，它的功能是為了創(chuàng)建解的一個(gè)種群。這種方法下，每個(gè)解都有自己的搜索方向。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。為了計(jì)算每個(gè)個(gè)體的聚集距離，需要對(duì)群體按每個(gè)子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對(duì)個(gè)子目標(biāo)分別進(jìn)行排序的時(shí)間復(fù)雜度為。第三章 優(yōu)化算例及分析 NSGAⅡ和MOGLS算法（NSGAⅡ）在NSGA 中, 同一個(gè)小生境內(nèi)的個(gè)體適應(yīng)度共享, 從而降低該小生境內(nèi)個(gè)體的競(jìng)爭(zhēng)力, 防止種群在收斂過程中陷入局部最優(yōu), 實(shí)現(xiàn)種群多樣性。2. 解集分布性評(píng)價(jià)在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過于集中，則周圍的很多解事實(shí)上并沒有太大的意義，也不利于產(chǎn)生新個(gè)體，從而影響了種群的進(jìn)化效果。遺傳算法的選擇和交叉算子賦予了它強(qiáng)有力的搜索能力，變異算子則使算法能搜索到問題解空間的每一個(gè)點(diǎn)，以確保算法能達(dá)到全局最優(yōu)。Holland教授提出的遺傳算法，現(xiàn)在一般稱為簡(jiǎn)單遺傳算法或基本遺傳算法[18]，其基本流程如下圖：圖21遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問題空間的參數(shù)，因此在算法開始進(jìn)行之前，首先要選擇合適的編碼方式對(duì)待優(yōu)化的參數(shù)進(jìn)行編碼。(3)分區(qū)統(tǒng)計(jì)數(shù)目策略：分區(qū)統(tǒng)計(jì)數(shù)目策略是將目標(biāo)空間劃分成一定比例的區(qū)域，通過統(tǒng)計(jì)個(gè)體所在區(qū)域中鄰域解數(shù)目來確定個(gè)體被保留的概率鄰域解數(shù)目越大，被保留概率越小。假設(shè)第代種群中的個(gè)體，在第代種群個(gè)體排序中的位置為，基于個(gè)體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個(gè)體進(jìn)行級(jí)別排序。在已有研究中，多目標(biāo)遺傳算法的適應(yīng)值設(shè)計(jì)(Fitness Assignment)主要有基于加權(quán)策略、基于目標(biāo)設(shè)計(jì)策略和基于非劣解等級(jí)優(yōu)先策略三種設(shè)計(jì)策略[14]：(1)基于加權(quán)策略的適應(yīng)值設(shè)計(jì)，即基于聚合策略的方法，是通過加權(quán)策略將多個(gè)目標(biāo)轉(zhuǎn)化為單個(gè)目標(biāo)后進(jìn)行優(yōu)化。定義1 ( 個(gè)體的Pareto 支配關(guān)系) 。 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類[11]：前決策（先驗(yàn)式）、后決策（后驗(yàn)式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時(shí)間先后劃分的。這類算法在適應(yīng)值設(shè)計(jì)中鼓勵(lì)非劣解等級(jí)優(yōu)先個(gè)體和同一等級(jí)內(nèi)較為稀疏個(gè)體以較大概率出現(xiàn)在后代群體中。優(yōu)化問題一直是倍受人們關(guān)注的問題，自1950 年以來,運(yùn)籌學(xué)研究人員已經(jīng)建立了許多方法解決MOP。因此在絕大多數(shù)情況下，若想達(dá)到總目標(biāo)的最優(yōu)，就需要對(duì)各個(gè)目標(biāo)進(jìn)行綜合考慮、折中處理，所得到的解是一組基于Pareto最優(yōu)性概念的非劣解集[1]，所以如何進(jìn)行綜合與折中就成為解決問題的關(guān)鍵。本文分析總結(jié)了兩種目前流行的所目標(biāo)進(jìn)化算法的基本原理，并通過算例來比較它們的性能。與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別在于,多目標(biāo)優(yōu)化問題的解不是唯一的,而是存在一個(gè)最優(yōu)解集合,集合中元素稱為Pareto 最優(yōu)或非劣最優(yōu)(nondominance) 。有些方法每次運(yùn)行只產(chǎn)生一個(gè)解,求多個(gè)解時(shí)需要運(yùn)行多次,效率較低。第四類算法是采用其他搜索算法策略改進(jìn)的MOEA。本文將以NSGAII算法和MOGLS（MultiObjective Genetic Lcal Search）算法為例，通過算例和指定的函數(shù)指標(biāo)來分析比較它們各自性能的優(yōu)缺點(diǎn)。設(shè)有解集,若中的個(gè)體不被任何其它個(gè)體支配, 則是 中的非支配個(gè)體。(3)基于非劣解等級(jí)優(yōu)先概念的適應(yīng)值分配策略由Goldberg最先提出，后人大多在此基礎(chǔ)上進(jìn)行改進(jìn)，如將群體劃分為幾個(gè)有序的子群體。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進(jìn)化算法多樣性的途徑?，F(xiàn)有算法中精英策略的實(shí)現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過確定性的選擇方法在混合群體中選擇后代，而不是采用變化之后的配對(duì)池來替換舊群體，增大了精英個(gè)體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。也可以設(shè)定期望的適應(yīng)度函數(shù)值，只有當(dāng)種群中存在個(gè)體能達(dá)到期望值時(shí)，算法才可以結(jié)束。而從現(xiàn)階段的研究來看，人們更關(guān)注的是，算法結(jié)果是否為高質(zhì)量的結(jié)果，而對(duì)于另外兩個(gè)因素相對(duì)要求并不高，而且對(duì)于算法的效率來說，涉及到的是經(jīng)典的算法復(fù)雜度理論，已經(jīng)有很完善的泛化體系對(duì)其進(jìn)行評(píng)價(jià)了，無需在多目標(biāo)進(jìn)化算法領(lǐng)域?qū)ζ湓龠M(jìn)行專門的研究。因此從理論上來證明算法的優(yōu)劣并不常用，也較難實(shí)現(xiàn)正確的評(píng)估。NSGAⅡ針對(duì)以上的缺陷通過以下三個(gè)方面進(jìn)行了改進(jìn)：(1)提出了快速非支配排序法，在選擇運(yùn)算之前，根據(jù)個(gè)體的非劣解水平對(duì)種群分級(jí)。NSGAⅡ算法的主流程：首先隨即初始化一個(gè)父代種群，并將所有個(gè)體按非支配關(guān)系排序，且指定一個(gè)適應(yīng)度值。多目標(biāo)遺傳局部搜索算法試圖尋找多目標(biāo)最有問題所有的非支配解，如果在一個(gè)多目標(biāo)問題中一個(gè)解不被其他解支配，它叫做非劣解，一個(gè)多目標(biāo)問題有許多非劣解。局部搜索的步驟：（1）：指定一個(gè)初始解；（2）：檢驗(yàn)初始解的相鄰解；（3）：如果比好，那么用代替；（4）：如果得所有相鄰解都已經(jīng)被檢驗(yàn)了，結(jié)束這個(gè)過程，否則返回（1）；在（4）中可以看出，對(duì)一個(gè)初始解通過局部搜索檢驗(yàn)的解的總數(shù)要遠(yuǎn)大于相鄰解的總數(shù)[25]。在采用驗(yàn)證算法比較時(shí)，C指標(biāo)使用最為普遍[26]。為了進(jìn)一步通過直觀比較法確定兩種算法的優(yōu)化性能，本文采用Zitzler在文獻(xiàn)[29]中提出的方法對(duì)算法性能進(jìn)行直觀評(píng)價(jià)。但是，同樣由于上面提及的算法間集成性差的原因，當(dāng)研究人員提出一種新算法，需要評(píng)價(jià)一下該算法的性能，或比較已有算法間的性能差別時(shí)，只能算法逐一執(zhí)行，然后將各算法的結(jié)果進(jìn)行人工分析、