【正文】 參 考 文 獻(xiàn)[1] 鄭金華. 多目標(biāo)進(jìn)化算法及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2007.[2] J. H. Holland, Adaptation in Natural and Artificial Systems[M]. Ann Arbor, MI: Univ. of Michigan Press, 1975.[3]T. Murata and H. Ishibuchi, MOGA: Multiobjective genetic algorithms[A]. in IEEE Int. Conf. Evolutionary Computat[C]., 1995,pp. 289–294[4] 杜平安, 郭志龍, 梁山虎, 等. 基于遺傳算法與動態(tài)規(guī)劃法的工藝過程優(yōu)化[J]. 電子科技大學(xué)學(xué)報, 2007, 3(20):146149.[5] . Schaffer. Multiple objective optimization with vector evaluated genetic algorithms[A]. in the Proceeding of the First International Conference on Genetic Algorithms[C]. New Jersey, Britain: IEE, 1985.[6] CHEOL G L, DONG H C, HYUM K J, et al. Niching genetic Algorithm with restricted petition selection for multimodal function optimization[J]. IEEE Transactions on Maqnetics, 1999, 35(3): 17221725.[7] K. Deb, A. Pratap, S. Agrawal, T. Meyrivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGAII [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182 197.[8] 唐云嵐. Pareto 最優(yōu)概念的多目標(biāo)進(jìn)化算法綜述[J]. 計算機(jī)科學(xué), 2008, 35(10): 3510.[9]鄭向偉. 多目標(biāo)進(jìn)化算法研究進(jìn)展[J]. 計算機(jī)科學(xué), 2007, 34(7): 187192.[10]孟紅云. 多目標(biāo)進(jìn)化算法及應(yīng)用研究. 博士學(xué)位論文[D]. 西安: 西安電子科技大學(xué), 2007.[11]K. Deb. MultiObjective Optimization using Evolutionary Algorithms [M]. John Wiley amp。而后沿用了經(jīng)典的進(jìn)化結(jié)構(gòu)，基于這種策略，引用C指標(biāo)對比了NSGAII和MOGLS算法的性能。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，包括適應(yīng)值設(shè)計、維持群體多樣性和精英保留策略。但是，在算法的測試與改進(jìn)的過程中，研究人員往往希望能夠跟蹤算法的中間數(shù)據(jù)，或是在執(zhí)行的過程中能夠動態(tài)的改變某些參數(shù)，從而方便的對算法進(jìn)行調(diào)整。這無疑消耗了大量的時間和精力。但是，想要進(jìn)行性能的評測，就需要算法在相同環(huán)境下統(tǒng)一運行，以保證結(jié)果的公正性和準(zhǔn)確性，保證結(jié)果更具有說服力，如果不能進(jìn)行集成，就很難達(dá)到這樣的評測條\件。本章首先詳細(xì)介紹了NSGAII和MOGLS的原理及流程，特別是兩種方法存在差異的適應(yīng)度評價和精英保留策略。在這個函數(shù)優(yōu)化算例中，KUR屬于優(yōu)化變量相對較少、優(yōu)化目標(biāo)較為復(fù)雜的函數(shù)測試算例（非凸、不連續(xù)問題），因此在許多算法研究的性能評價中，都采用這個算例驗證新算法的有效性；ZDT4算例屬于多變量函數(shù)優(yōu)化算例（優(yōu)化變量10）。符號集約定為：設(shè)有種算法（本文有兩種）參與性能評價，對于某個優(yōu)化算例，采用每種算法獨立運行次（本文為30次），每次獨立運行后，獲得非劣解集， ，合并各算法獨立運行所得的非劣解集，剔除其中劣解后得到算法優(yōu)化的最終非劣解集，則Zitzler評價方法的實現(xiàn)過程可描述為：(1)令， ；。因為現(xiàn)代啟發(fā)式算法存在不確定性，因此在每組參數(shù)組合下計算30次做統(tǒng)計分析。分別選用線性交叉和非均勻變異方式生成新個體。針對這些測試原則中的一種或幾種原則的組合，借鑒單目標(biāo)遺傳算法測試函數(shù)的設(shè)計方法，Deb、Fonseca、Fleming、Veldhuizen和Zitzler等人通過長期研究，分別提出了多個具有不同優(yōu)化性狀的測試函數(shù)。指標(biāo)由Zitzler提出，其定義為：設(shè)是兩種算法優(yōu)化所得的非劣解集，指標(biāo)是一種值域定義在上、用來刻畫之間偏序能性的指標(biāo)：。如果多目標(biāo)優(yōu)化問題有凹的Praeto前端，使用帶有連續(xù)權(quán)值的計算權(quán)值之和的方法將不能得到整個Praeto前端。（5）精英保留策略：從試驗非劣解集中隨機(jī)選擇解，接著將這個選中的解加入到在(4)中解中，它的功能是為了創(chuàng)建解的一個種群。（2）評價適應(yīng)值：對當(dāng)前種群中每個解在個目標(biāo)方向計算適應(yīng)度值，更新臨時非劣解集。精英保留策略：本算法保留了兩組解：當(dāng)前解和試驗的非劣解。總之，我們能通過局部搜索調(diào)整計算時間。這種方法下，每個解都有自己的搜索方向。為了實現(xiàn)各個方向搜索，而提出這種算法。雜交算法的目的不是確定一個單一的最終解，而是試圖尋找這個多目標(biāo)問題所有符合約束條件的最優(yōu)解。這個算法的一大典型特性是無論何時選擇一組父代種群都要指定權(quán)值效率。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。如果的大小小于，則繼續(xù)向中填充，直到添加到時種群大小超出，對中的個體進(jìn)行擁擠度排序，取前個個體。然后采用選擇、交叉、變異算子產(chǎn)生下一代種群，大小也為，完成第一代進(jìn)化。即如果兩個個體的非支配排序不同，取排序號較小的個體；如果兩個個體在同一級，取周圍較不擁擠的個體。為了計算每個個體的聚集距離，需要對群體按每個子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對個子目標(biāo)分別進(jìn)行排序的時間復(fù)雜度為。如此操作降低了算法的計算復(fù)雜度。首先將當(dāng)前的所有的非劣解個體劃為同一等級，令其等級為；然后將這些個體從種群中移出，在剩余個體中尋找出新的非劣解，再令其等級為；重復(fù)上述過程，直至種群中所有個體都被設(shè)定相應(yīng)的等級。 (23)其中, 表示個體 與個體 的距離, 是同一小生境中個體間的最大允許距離, 表示距離為時的共享函數(shù)值。第三章 優(yōu)化算例及分析 NSGAⅡ和MOGLS算法（NSGAⅡ）在NSGA 中, 同一個小生境內(nèi)的個體適應(yīng)度共享, 從而降低該小生境內(nèi)個體的競爭力, 防止種群在收斂過程中陷入局部最優(yōu), 實現(xiàn)種群多樣性。 本章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和原理。2. 實驗比較分析實驗比較分析是指通過對優(yōu)化算例的結(jié)果和結(jié)果的各種指標(biāo)進(jìn)行比較，驗證新算法與已存在的算法之間的性能差別。由于收斂性評價與分布性評價的應(yīng)用方向不同，因而在比較算法的時候，多會綜合兩種評價后，對算法的性能得出適當(dāng)?shù)慕Y(jié)論。2. 解集分布性評價在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過于集中，則周圍的很多解事實上并沒有太大的意義，也不利于產(chǎn)生新個體，從而影響了種群的進(jìn)化效果。收斂性的評價方法有很多種，如錯誤率、解集間覆蓋率、世代距離、最大出錯率等等。所以現(xiàn)階段的性能評價方法主要集中于對算法的效果的衡量。多目標(biāo)遺傳算法的性能評價與傳統(tǒng)優(yōu)化算法及單目標(biāo)遺傳算法的性能評價有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過梯度下降速度進(jìn)行評價，并且可以通過嚴(yán)格的數(shù)學(xué)證明分析其收斂性能；單目標(biāo)遺傳算法可以采用基于模式定理或基于馬爾可夫隨機(jī)過程理論的證明分析其收斂性，盡管這類證明研究還很初步。遺傳算法的選擇和交叉算子賦予了它強(qiáng)有力的搜索能力，變異算子則使算法能搜索到問題解空間的每一個點，以確保算法能達(dá)到全局最優(yōu)。(7) 變異操作:以一定的概率從群體中選擇若干個個體。通常情況下，這兩種方法同時作為優(yōu)化準(zhǔn)則使用。 (3) 設(shè)計適應(yīng)度函數(shù)：把問題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度函數(shù)計算種群中的每個個體的適應(yīng)度，為種群進(jìn)化的選擇提供依據(jù)。Holland教授提出的遺傳算法，現(xiàn)在一般稱為簡單遺傳算法或基本遺傳算法[18]，其基本流程如下圖：圖21遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問題空間的參數(shù)，因此在算法開始進(jìn)行之前，首先要選擇合適的編碼方式對待優(yōu)化的參數(shù)進(jìn)行編碼。但是使用優(yōu)勝關(guān)系比較的方法有時也存在問題，如對某些連續(xù)型問題所對應(yīng)的Pareto集可能包含無窮多個解，因此需要補充其他的信息知識來減小所存儲的個體數(shù)目。另一種實現(xiàn)方式是采用獨立于進(jìn)化群體的伴隨群體，即使用帶有所謂的檔案（Archive）的方式，保留與更新算法進(jìn)化過程中搜索到的非劣解集來維護(hù)當(dāng)代群體中的滿意群體，使其能夠復(fù)制到下一代，伴隨群體僅作為一個外部存儲集，獨立于進(jìn)化過程的優(yōu)化操作[17]。當(dāng)兩個解的目標(biāo)向量之間的空間距離小于某一預(yù)定值時，相應(yīng)解的小生境規(guī)模就必須進(jìn)行調(diào)整。(3)分區(qū)統(tǒng)計數(shù)目策略：分區(qū)統(tǒng)計數(shù)目策略是將目標(biāo)空間劃分成一定比例的區(qū)域，通過統(tǒng)計個體所在區(qū)域中鄰域解數(shù)目來確定個體被保留的概率鄰域解數(shù)目越大，被保留概率越小。具體應(yīng)用時首先根據(jù)內(nèi)核函數(shù)來定義一個點的鄰域范圍，內(nèi)核函數(shù)采用至另一點的距離作為參數(shù)。進(jìn)化算法由于其進(jìn)化算子固有的隨機(jī)誤差，因而基于有限群體實施進(jìn)化時會出現(xiàn)收斂至某一個解。傳統(tǒng)的進(jìn)化算法在Pareto最優(yōu)集上執(zhí)行多目標(biāo)搜尋，希望找出盡可能均勻分布的解集，因而個體的多樣性減少的很快，經(jīng)常收斂至單個解而丟失多個其他非劣解。假設(shè)第代種群中的個體，在第代種群個體排序中的位置為，基于個體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個體進(jìn)行級別排序。Pareto優(yōu)勝關(guān)系是決定個體適應(yīng)度函數(shù)值的重要依據(jù)，很多MOEAs根據(jù)個體間的這種關(guān)系，將個體的適應(yīng)度函數(shù)值分成兩個層次，即劣解和非劣解，后者的適應(yīng)度值總是優(yōu)于前者。這類算法的適應(yīng)值設(shè)計主要有等級優(yōu)先、深度優(yōu)先和基于優(yōu)先數(shù)三種：等級優(yōu)先策略算法在計算適應(yīng)值時主要考慮個體在群體中“優(yōu)于”其他個體的數(shù)目或考慮優(yōu)于該個體的其他個體數(shù)目之和，以此確定給個體的適應(yīng)度值；而深度優(yōu)先策略算法在分配個體適應(yīng)值時主要以個體所在的非劣解等級及等級內(nèi)的疏密程度有關(guān)；基于優(yōu)先數(shù)的適應(yīng)值分配算法在計算個體適應(yīng)值時，考慮了個體所優(yōu)先于或劣于群體中其他個體的數(shù)目。此方法通過在不同進(jìn)化代之間更換優(yōu)化目標(biāo)每次優(yōu)化一個目標(biāo)，使算法群體每次運行得到一個非劣解，從而通過多次運行找到優(yōu)化問題的非劣解集。在已有研究中，多目標(biāo)遺傳算法的適應(yīng)值設(shè)計(Fitness Assignment)主要有基于加權(quán)策略、基于目標(biāo)設(shè)計策略和基于非劣解等級優(yōu)先策略三種設(shè)計策略[14]：(1)基于加權(quán)策略的適應(yīng)值設(shè)計，即基于聚合策略的方法，是通過加權(quán)策略將多個目標(biāo)轉(zhuǎn)化為單個目標(biāo)后進(jìn)行優(yōu)化。從決策者的立場來看，一般認(rèn)為每對候選解具有以下比較關(guān)系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。 由 中的所有非支配個體構(gòu)成的子集稱為 的非支配集。此時稱 為非支配的( non dominated), 為被支配的( dominated) 。定義1 ( 個體的Pareto 支配關(guān)系) 。MOGLS的優(yōu)點是通過隨機(jī)權(quán)將MOP轉(zhuǎn)化為SOP，算法容易實現(xiàn)，并且恰當(dāng)控制MOGLS中鄰域搜索個體的選取及步長可以在減少計算復(fù)雜度的同時獲得良好的計算結(jié)果；算法的不足之處是，算法的構(gòu)造是基于MOP轉(zhuǎn)化為SOP的思想，因此在不明確多個目標(biāo)偏好情況下，采用隨機(jī)權(quán)的方法往往不能保證所得非劣解集分布的均勻性。NSGAII算法首先隨機(jī)產(chǎn)生一個初始種群，對種群通過采用輪盤賭的方式選擇、交叉和變異操作獲得新的種群，將種群中的個體構(gòu)造其Pareto 邊界集，并根據(jù)個體間的聚集距離，建立偏序關(guān)系，最終從偏序關(guān)系中選擇原始種群規(guī)模大小的個體，組成新的種群，完成了一次進(jìn)化操作。 Thiele 2001)和NSGA/NSGAII (Srinivas amp。 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類[11]：前決策（先驗式）、后決策（后驗式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時間先后劃分的。除了上述四類算法外，一些學(xué)者在演化策略中引入偏好分級或適應(yīng)值分享機(jī)制獲取滿意解。這類算法由于采用的進(jìn)化策略是基于模擬退火搜索、禁忌搜索、粒子群優(yōu)化、小生境策略等不以傳統(tǒng)遺傳算法進(jìn)化結(jié)構(gòu)為主導(dǎo)的優(yōu)化策略，因此在早期的多目標(biāo)進(jìn)化算法研究中并未受到廣泛重視，只是在近年隨著多目標(biāo)遺傳算法局部搜索性能欠佳的不足逐漸呈現(xiàn)，以及其他進(jìn)化策略單目標(biāo)進(jìn)化算法的迅速發(fā)展才開始活躍起來。這類算法通過在進(jìn)化過程中引入外部伴隨群體對群體中的精英個體加以保留，同時采用更加成熟的適應(yīng)值設(shè)計策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。這類算法在適應(yīng)值設(shè)計中鼓勵非劣解等級優(yōu)先個體和同一等級內(nèi)較為稀疏個體以較大概率出現(xiàn)在后代群體中。由于這類算法的設(shè)計思想是基于單目標(biāo)遺傳算法的進(jìn)化策略，因此它的優(yōu)點是算法容易實現(xiàn)；其不足是，基于單目標(biāo)子群體優(yōu)化的算法很難搜索到嚴(yán)格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點。進(jìn)化多目標(biāo)優(yōu)化始于1967年，此后眾多的研究人員通過對遺傳算法進(jìn)行改造，相繼提出了多種用于解決多目標(biāo)優(yōu)化問題的遺傳算法，如基于向量評估的遺傳算法(VEGA) [5]，小組決勝遺傳算法(NPGA) [6]，非支配排序遺傳算法(NSGA)及其改進(jìn)算法NSGAII[7]等. 其中NSGA的改進(jìn)算法NSGAII是帶有精英策略的非支配排序遺傳算法，改進(jìn)了先前算法的不足之處，提高了算法的運算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。但這些方法存在：只能得到一個解；多個目標(biāo)函數(shù)之間量綱不同難以統(tǒng)一