【正文】 了，結(jié)束這個過程，否則返回（ 1）； 在（ 4）中可以看出，對一個初始解通過局部搜索檢驗的解的總數(shù)要遠大于相鄰解的總數(shù) [25]。 精英保留策略： 本算法保留了兩組解：當(dāng)前解和試驗的非劣解。局部搜索后，當(dāng)前種群已被進化的種群替換，接著試驗的非劣解被新的當(dāng)前種群所更新，即如果當(dāng)前種群的一個解不受 其他解和試驗的非劣解集支配，那么將此解添加進這個試驗集合，在試驗集合中被這個解支配的其他解就被剔除。在試驗集合中，一小部分解被任意地選擇作為局部搜索的最初解，這是因為如果一個非劣解沒有父代解，隨機權(quán)值分配給那個非劣解去執(zhí)行局部搜索，隨機選擇的非劣解可能被認為是精英解，因為它們被添入沒有進過遺傳操作的當(dāng)前種群。 MOGLS 的步驟： （ 1）初始化，隨機產(chǎn)生一個初始種群：popN是這個種群解的個數(shù)。 （ 2）評價適應(yīng)值：對當(dāng)前種群中每個解在 n 個目標(biāo)方向計算適應(yīng)度值，更新臨時非劣解集。 （ 3）選擇：重復(fù)以下過程去選擇父代解的 ? ?pop sliteNN?： 通過 (27) 在適應(yīng)度函數(shù) (*1)中計算隨機的權(quán)值， 1? 、 2? ， ， n? 。通過（ 28）確定的選擇概率，從當(dāng)前種群中選擇一組父代解。 （ 4）交叉 和變異：從父代解中選擇的 ? ?pop sliteNN?對，分別應(yīng)用交叉過程，從每個父代解的對中產(chǎn)生新解，然后對新解使用變異操作。 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 19 （ 5）精英保留策略：從試驗非劣解集中隨機選擇 eliteN 解，接著將這個選中的 eliteN 解加入到在 (4)中 ? ?pop sliteNN?解中，它的功能是為了創(chuàng)建popN解的一個種群。 （ 6）局部搜索：在當(dāng) 前種群對所有popN解 應(yīng)用改進的局部搜索過程，對每個解的局部搜索方向已經(jīng)由父代解被選擇的適應(yīng)度函數(shù)中的權(quán)值確定。當(dāng)前種群被局部搜索改進的 eliteN 解置換。 （ 7）終止測試：如果一個提前確定的停止條件被滿足，結(jié)束算法，否則，返回第二步。 如果多目標(biāo)優(yōu)化問題有凹的 Praeto 前端，使用帶有連續(xù)權(quán)值的計算權(quán)值之和的方法將不能得到整個 Praeto 前端。但 MOGLS 能處理帶有凹的 Praeto 前端的多目標(biāo)進化問題。 具體流程見下圖 ： 進化開始種群初始化非劣解整理選擇交叉變異進化代數(shù) gen大于最大代數(shù)終止計算適應(yīng)度產(chǎn)生混合種群 Rt對 Rt 中的解賦權(quán)值 ，并利用權(quán)值分級計算適應(yīng)度通過精英選擇策略剔除劣解局部搜索非劣解整理保留保留Gen + 1NoY e s 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 20 性能評價指標(biāo) 現(xiàn)有研究中，對新的多目標(biāo)遺傳算法進行性能評價時，普遍采用兩種方法：一種是構(gòu)造一系列可以獨立評價算法性能的指標(biāo)用于考察算法搜索到的非劣解集的優(yōu)劣；另一種是選取一種迄今為止性能優(yōu)越的驗證算法與新算法在相同進化條件下對測試算例進行優(yōu)化，比較搜索到的非劣解集。在采用驗證算法比較時，C 指標(biāo)使用最為普遍 [26]。 C 指標(biāo)由 Zitzler 提出，其定義為：設(shè) ,AB X? 是兩種算法優(yōu)化所得的非劣解集，C 指標(biāo)是一種值域定義在 (0,1) 上、用來刻畫 (,)AB 之間偏序能性的指標(biāo)：? ? ? ?| | : |,: ||b B a A a bC A B B??? 。若 ( , ) 1C A B ? ，則說明對于 B 集中的任一個非劣解個體，A 集中總存在 ―優(yōu)于 ‖(dominace)它的解個 體； ( , ) 0C AB ? ，說明對于 B 集中任一個解個體， A 集中都不存在 ―優(yōu)于 ‖它的解個體。 算例分析 算例描述 為了對新提出的多目標(biāo)進化算法性能進行評價，或?qū)Χ喾N不同的多目標(biāo)進化算法進行性能比較，研究者們常常需要借助不同性狀的標(biāo)準測試函數(shù)對算法性能進行考察。已有的測試函數(shù)的設(shè)計原則主要有： （ 1）優(yōu)化問題為非凸情形下的優(yōu)化性能測試； （ 2）優(yōu)化問題目標(biāo)空間不 連續(xù)情形下的優(yōu)化性能測試； （ 3）多變量優(yōu)化問題的優(yōu)化性能測試。 針對這些測試原則中的一種或幾種原則的組合，借鑒單目標(biāo)遺傳算法測試函數(shù)的設(shè)計方法， Deb、 Fonseca、 Fleming、 Veldhuizen和 Zitzler等人通過長期研究，分別提出了多個具有不同優(yōu)化性狀的測試函數(shù)。尤其是 Zitzler、 Deb、 Thiele提出的系列測試函數(shù)，是目前為止評價新的多目標(biāo)優(yōu)化算法性能時采用最廣泛的測試函數(shù)族 [27]，因此，對新算法的評價及其改進具有重要的指導(dǎo)意義。本文性能測試函數(shù)使用 KUR和 ZDT4來分別測試 MOGLS和 NSGAⅡ 。 為了對 NSGAII和 MOGLS兩種多目標(biāo)遺傳算法性能進行考察，選擇 ZDTKUR 兩個測試函數(shù)作為算例進行優(yōu)化 .分別介紹這兩種測試函數(shù)： （ 1） KUR：變量個數(shù)是 3， [ 5, 5]ix ? ? ? ， 1, ,3i? ? ? ? ?2 22111 [ 1 0 e x p 0 .2 ]iiif x x x ??? ? ? ?? ? ? ? ?3 0 .8 32 1 5 s iniiif x x x? ??????? （ 2） ZDT4:變量個數(shù)是 10， 1 [0,1]x? [ 5, 5]ix??? 2, ,10i? ? ?11f x x? ? ? ? ? ? ?? ?2 30 2, , 1 10 1 10 c os 4n iiig x x n x x??? ? ? ? ?? ? ? ? ? ? ?12 2 3 0 2 , , 3 0( , , ) 1 fxf x g x x g x x???????? ?????? 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 21 進化編碼及進化操作 對于函數(shù)優(yōu)化算例，本文采用實數(shù)編碼方式，即基因編碼中的每個位置表示優(yōu)化變量中的一個變量。 分別選用線性交叉和非均勻變異方式生成新個體。 設(shè) 1x 與 2x 為當(dāng)前群體隨機抽出的兩個進行交叉的父代個體， 1x 、 2x 為線性交叉后生成的兩個新個體，則線性交叉算子實現(xiàn)方式如公式所示： ? ?? ?1 1 22 1 211x x xx x x????? ? ?? ? ? 其中， ? 為 ? ?0,1 之間的隨機數(shù)。 設(shè)隨機選中進行變異的個體為 ix ，則非均勻變異算子采用如下公式生成新個體 ix ： ? ? ? ?? ? ? ? 0 . 50 . 5i i i ii i i i ix b x f G if rxx x a f G if r? ? ? ??? ?? ? ??? 其中 ia 、 ib 分別為變量的下界和上界， ? ?fG 可由 下式 計算得出： ? ? 2 m a x1 bGf G r G?????????????? 其中 1r 、 2r 為之間均勻分布的隨機數(shù)， G 為當(dāng)前遞進層的進化代數(shù)，為每層遞進設(shè)定的最大進化代數(shù)， b 為一形式參數(shù)，此處取 2。 進化參數(shù)設(shè)置 采用 NSGAⅡ 和 MOGLS 對 KUR 算例進行優(yōu)化時，兩種算法均設(shè)置相同的進化參數(shù)，以便保證各算法的進化條件相同或相似 ，從而可以根據(jù)算法求解到的非劣解集的優(yōu)劣評價算法的相對性能 [28]。 因為現(xiàn)代啟發(fā)式算法存在不確 定性，因此在每組參數(shù)組合下計算 30 次做統(tǒng)計分析。 經(jīng)實驗確定，三種算法優(yōu)化測試函數(shù)的進化參數(shù)設(shè)定為： 群體規(guī)模： 100/200 進化代數(shù)： 500/1000 交叉概率： 變異概率： MOGLS 每代個體的非劣解局部搜索步長： 5 所以本實驗要獲得 8 組解。 結(jié)果分析 首先，計算兩種算法優(yōu)化算例得到的 C 指標(biāo)（見附錄 A），從附錄 A 中可以反映出， C（ NSGAII,MOGLS） 接近于 1， C（ MOGLS ， NSGAII）接近于零，即 NSGAII 算法優(yōu)于 MOGLS 算法。 為了進一 步通過直觀比較法確定兩種算法的優(yōu)化性能 ，本文采用 Zitzler 在文獻 [29]中提出的方法對算法性能進行直觀評價。 符號集約定為：設(shè)有 K 種算法（本文有兩種）參與性能評價，對于某個優(yōu)華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 22 化算例，采用每種算法獨立運行 l 次（本文為 30 次），每次獨立運行后，獲得非劣解集 jiP ， 1,2, ,il? 1, 2, ,jK? ，合并各算法獨立運行所得的非劣解集，剔除其中劣解后得到算法優(yōu)化的最終非劣解集 jP ， 1, 2, ,jK? 則 Zitzler 評價方法的實現(xiàn)過程可描述為： (1)令 jP ?? ， jiP ?? ， 1,2, ,il? ； 1, 2, ,jK? 。 1i? ， 1j? ； (2)運行算法 j ，令 j j jiP P P?? ； (3)若 ,i l j K?? 時算法停止運行； (4)若 il? ，則 1, 1j j i? ? ? ，轉(zhuǎn)到 (2)，否則 1ii?? ，轉(zhuǎn)到 (2)； 所有算法運行完畢后，剔除各算法非劣解集 jP 中的劣解，然后比較各算法所得最終非劣解集 (分布圖 )的等級優(yōu)先程度及非劣解分布的均勻程度，最終確定算法優(yōu)化性能的優(yōu)劣 [30]。 采用 MOGLS 和 NSGAⅡ 算法和優(yōu)化函數(shù)測試算例 KUR 時，為保證算法結(jié)果比較的公正性，將兩種算法的進化參數(shù)設(shè)置為相同的進化條件（進化群體規(guī)模、進化代數(shù)以及交叉和變異概率，等）。 采用三種算法分別對各算例獨立優(yōu)化 30 次，將所得非劣解合并，在完成 30次獨立優(yōu)化后，剔除各算法非劣解并集中的相同個 體及劣解，得到各算法優(yōu)化的最終非劣解集，如下圖所示。 f 1 ( x )f2(x) 2 1 2 0 1 9 1 8 1 7 1 6 1 5 1 4 1 3 1 4 1 2 1 0 8 6 4 202N S G A I IM O G L S 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 23 f 1 ( x )f2(x) 2 1 2 0 1 9 1 8 1 7 1 6 1 5 1 4 1 3 1 4 1 2 1 0 8 6 4 202N S G A I IM O G L S 在這個函數(shù)優(yōu)化算例中， KUR 屬于優(yōu)化變量相對較少、優(yōu)化目標(biāo)較為復(fù)雜 的函數(shù)測試算例 （ 非凸、不連續(xù)問題 ） ，因此在許多算法研究的性能評價中，都采用這個算例驗證新算法的有效性； ZDT4 算例屬于多變量函數(shù)優(yōu)化算例 （ 優(yōu)化變量 10） 。因此，本文在比較函數(shù)優(yōu)化算例結(jié)果時，首先對 兩種 種算法優(yōu)化和所得的結(jié)果進行比較，進而初步確定 這兩 種算法對于少變量復(fù)雜空間優(yōu)化問題的求解性能，然后參照 兩種 種算法求解 ZDT4 算例所得的非劣解集 (見附錄 B)，通過類似方法評價出算法 對多變量函數(shù)優(yōu)化問題的求解能力。 MOGLS 算法所得的非劣解集明顯劣于 NSGAII 算法：其非劣解數(shù)目非常稀少；非劣解所在的等級明顯比其他兩種算法的非劣解等級差，因此， NSGAII對 KUR 函數(shù)的優(yōu)化性能優(yōu)于 MOGLS。上述分析可以看出，在復(fù)雜優(yōu)化空間多目標(biāo)函數(shù)算例優(yōu)化中， NSGAII 獲得了明顯好于 MOGLS 算法的非劣解集，初步顯示了它的良好優(yōu)化性能。 本章小結(jié) 本章 首先詳細介紹了 NSGAII 和 MOGLS 的原理及流程， 特別是兩種方法存在差異的適應(yīng)度評價和精英保留策略。而后 沿用了經(jīng)典的進化結(jié) 構(gòu)，基于這種策略， 引用 C 指標(biāo) 對比了 NSGAII 和 MOGLS 算法的性能。采用這兩種算法對典型的多目標(biāo)函數(shù)優(yōu)化 KUR 算例進行了優(yōu)化求解，將兩種算法的所得結(jié)果進行比較分析，研究結(jié)果表明， NSGAII 有比 MOGLS 更優(yōu)的非劣解等級及非劣解集分布，因此驗證了這兩種算法對多目標(biāo)函數(shù)優(yōu)化問題的求解性能的強弱關(guān)系。 雖然實驗比較分析的方法已經(jīng)在本學(xué)科內(nèi)廣泛的被使用，且有它的一些優(yōu)點，但是它本身也存在著一些問題： 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 24 1. 算法間的差異較大，可比性較差 因為它們都是根據(jù)不同的特定問題而提出的，算法結(jié)構(gòu)、參數(shù)等都不盡相同，所以當(dāng)問 題改變的時候，一般需要修改算法才能適應(yīng)新問題，這使得算法間較難進行集成比較。但是，想要進行性能的評測，就需要算法在相同環(huán)境下統(tǒng)一運行，以保證結(jié)果的公正性和準確性，保證結(jié)果更具有說服力，如果不能進行集成，就很難達到這樣的評測條 \件。另外，對于結(jié)果的比較，也應(yīng)該有統(tǒng)一的、通用的優(yōu)劣標(biāo)準或指標(biāo)體系。 2. 人工操作 用實驗來評價算法的性能，目前基本是靠算法結(jié)果的人工審查，以及各種性能指標(biāo)值的比較。但是，同樣由于上面提及的算法間集成性差的原因，當(dāng)研究人員提出一種新算法，需要評價一下該算法的性能，或比較已有算法間的性能差別時，只能算法逐一執(zhí)行，然后將各算法的結(jié)果進行人工分析、手動計算。這無疑消耗了大量的時間和精力。另外，評估一個算法的優(yōu)劣，往往需要反復(fù)大量的評測才能得出相對準確的性能結(jié)論。所以基于以上兩個原因，人工方式就顯得效率極其低下，不能使研究人員專注于算法自身的改進上。 3. 靜態(tài)的環(huán)境