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