【正文】 Pm = MaxGens = 500 PopSize = 200Pc = 。 Pm = MaxGens = 500 PopSize = 200Pc = 。在今后對算法做進(jìn)一步研究時,還可將與實(shí)際求解問題相關(guān)的啟發(fā)式規(guī)則或啟發(fā)式算法引入非劣解局部搜索過程,以達(dá)到有效利用現(xiàn)有各學(xué)科專業(yè)知識指導(dǎo)局部搜索的目的,則GA 的全局搜索優(yōu)勢與啟發(fā)式快速鄰域搜索的優(yōu)勢相結(jié)合,算法尋求多目標(biāo)優(yōu)化問題非劣解的效率和結(jié)果有望得到進(jìn)一步提高。而后又總結(jié)了MOEA的研究現(xiàn)狀，就是以進(jìn)化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進(jìn)化策略局部搜索的優(yōu)勢，獲得高性能的多目標(biāo)優(yōu)化算法，成為多目標(biāo)進(jìn)化算法研究的潛在發(fā)展方向第二章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和最優(yōu)性原理。但是，同樣由于上面提及的算法間集成性差的原因，當(dāng)研究人員提出一種新算法，需要評價一下該算法的性能，或比較已有算法間的性能差別時，只能算法逐一執(zhí)行，然后將各算法的結(jié)果進(jìn)行人工分析、手動計(jì)算。上述分析可以看出，在復(fù)雜優(yōu)化空間多目標(biāo)函數(shù)算例優(yōu)化中，NSGAII獲得了明顯好于MOGLS算法的非劣解集，初步顯示了它的良好優(yōu)化性能。為了進(jìn)一步通過直觀比較法確定兩種算法的優(yōu)化性能，本文采用Zitzler在文獻(xiàn)[29]中提出的方法對算法性能進(jìn)行直觀評價。為了對NSGAII和MOGLS兩種多目標(biāo)遺傳算法性能進(jìn)行考察，選擇ZDTKUR ：（1）KUR：變量個數(shù)是3，（2）ZDT4:變量個數(shù)是10， 對于函數(shù)優(yōu)化算例，本文采用實(shí)數(shù)編碼方式，即基因編碼中的每個位置表示優(yōu)化變量中的一個變量。在采用驗(yàn)證算法比較時，C指標(biāo)使用最為普遍[26]。（4）交叉和變異：從父代解中選擇的對，分別應(yīng)用交叉過程，從每個父代解的對中產(chǎn)生新解，然后對新解使用變異操作。局部搜索的步驟：（1）：指定一個初始解；（2）：檢驗(yàn)初始解的相鄰解；（3）：如果比好，那么用代替；（4）：如果得所有相鄰解都已經(jīng)被檢驗(yàn)了，結(jié)束這個過程，否則返回（1）；在（4）中可以看出，對一個初始解通過局部搜索檢驗(yàn)的解的總數(shù)要遠(yuǎn)大于相鄰解的總數(shù)[25]。在此算法中局部搜索應(yīng)用每個由父代種群向子代種群進(jìn)化的過程中，新種群的適應(yīng)度通過被用于選擇父代種群的權(quán)值而定義，這樣，對每個解的局部搜索的方向就由應(yīng)用于它的父代解選擇的權(quán)值定義了。多目標(biāo)遺傳局部搜索算法試圖尋找多目標(biāo)最有問題所有的非支配解，如果在一個多目標(biāo)問題中一個解不被其他解支配，它叫做非劣解，一個多目標(biāo)問題有許多非劣解。當(dāng)排序產(chǎn)生的非支配集的個體數(shù)目足夠填充時，就不必再繼續(xù)對剩下的部分排序了。NSGAⅡ算法的主流程：首先隨即初始化一個父代種群，并將所有個體按非支配關(guān)系排序，且指定一個適應(yīng)度值。擁擠度的概念：擁擠度是指在種群中的給定點(diǎn)的周圍個體的密度，計(jì)算上要考慮個體周圍包含本身但不包含其他個體的最小正方形，如下圖，個體的聚集距離是。NSGAⅡ針對以上的缺陷通過以下三個方面進(jìn)行了改進(jìn)：(1)提出了快速非支配排序法，在選擇運(yùn)算之前，根據(jù)個體的非劣解水平對種群分級。最后簡單介紹了算法的性能評價體系，為幾種算法比較的方案提供依據(jù)，得出基于實(shí)驗(yàn)的方法是可行的，本文將在第三章利用這一思想來試驗(yàn)NSGAⅡ和MOGLS兩種算法的優(yōu)劣。因此從理論上來證明算法的優(yōu)劣并不常用，也較難實(shí)現(xiàn)正確的評估。 (31)對于收斂性的評價指標(biāo)而言，可以通過指標(biāo)值反映出算法間優(yōu)化效果的差異，但只局限于最優(yōu)解集中更優(yōu)解的數(shù)量，對于其空間上的特性不做相關(guān)考慮。而從現(xiàn)階段的研究來看，人們更關(guān)注的是，算法結(jié)果是否為高質(zhì)量的結(jié)果，而對于另外兩個因素相對要求并不高，而且對于算法的效率來說，涉及到的是經(jīng)典的算法復(fù)雜度理論，已經(jīng)有很完善的泛化體系對其進(jìn)行評價了，無需在多目標(biāo)進(jìn)化算法領(lǐng)域?qū)ζ湓龠M(jìn)行專門的研究。一代一代循環(huán)往復(fù)，使種群中最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個體的適應(yīng)度滿足優(yōu)化準(zhǔn)則或最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不再提高，則迭代過程收斂，算法結(jié)束。也可以設(shè)定期望的適應(yīng)度函數(shù)值，只有當(dāng)種群中存在個體能達(dá)到期望值時，算法才可以結(jié)束。更新的算法研究表明，如果同時采用這兩種精英策略，可以進(jìn)一步提高算法的搜索性能與收斂效果?，F(xiàn)有算法中精英策略的實(shí)現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過確定性的選擇方法在混合群體中選擇后代，而不是采用變化之后的配對池來替換舊群體，增大了精英個體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。該策略主要考慮給定點(diǎn)至第個最近鄰居的距離，以便估計(jì)出其在鄰域內(nèi)的密度。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進(jìn)化算法多樣性的途徑。多目標(biāo)問題與單目標(biāo)問題不同，它的優(yōu)劣性與支配關(guān)系并非定義目標(biāo)向量之間的那種整體有序關(guān)系，只是給出部分有序關(guān)系，因而種群的級別排序不具有唯一性。(3)基于非劣解等級優(yōu)先概念的適應(yīng)值分配策略由Goldberg最先提出，后人大多在此基礎(chǔ)上進(jìn)行改進(jìn)，如將群體劃分為幾個有序的子群體。(2)為了避免未成熟收斂和獲得均勻分布且范圍最廣的非劣解，如何保持群體的多樣性。設(shè)有解集,若中的個體不被任何其它個體支配, 則是 中的非支配個體。本文采用廣泛使用的Pareto 最優(yōu)性[12]定義。本文將以NSGAII算法和MOGLS（MultiObjective Genetic Lcal Search）算法為例，通過算例和指定的函數(shù)指標(biāo)來分析比較它們各自性能的優(yōu)缺點(diǎn)。多目標(biāo)遺傳算法的研究一直是這類算法研究的主流方向：盡管遺傳算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他進(jìn)化策略或啟發(fā)式局部搜索算法好的局部搜索性能，因此，以進(jìn)化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進(jìn)化策略局部搜索的優(yōu)勢，獲得高性能的多目標(biāo)優(yōu)化算法，成為多目標(biāo)進(jìn)化算法研究的潛在發(fā)展方向。第四類算法是采用其他搜索算法策略改進(jìn)的MOEA。第二類算法是基于Goldberg提出的適應(yīng)值分級和共享策略的多目標(biāo)遺傳算法。有些方法每次運(yùn)行只產(chǎn)生一個解,求多個解時需要運(yùn)行多次,效率較低。而對算法性能進(jìn)行比較和評價就成為一個重要的核心問題，引起了諸多學(xué)者的研究興趣。與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別在于,多目標(biāo)優(yōu)化問題的解不是唯一的,而是存在一個最優(yōu)解集合,集合中元素稱為Pareto 最優(yōu)或非劣最優(yōu)(nondominance) 。有時目標(biāo)之間是相輔相成、互相促進(jìn)的，但更多的時候，目標(biāo)之間是相互矛盾、此消彼長的。本文分析總結(jié)了兩種目前流行的所目標(biāo)進(jìn)化算法的基本原理，并通過算例來比較它們的性能。本文主要工作內(nèi)容如下：1. 簡要回顧了多目標(biāo)進(jìn)化算法的發(fā)展歷史，按照算法原理與進(jìn)化模式將算法分類。因此在絕大多數(shù)情況下，若想達(dá)到總目標(biāo)的最優(yōu)，就需要對各個目標(biāo)進(jìn)行綜合考慮、折中處理，所得到的解是一組基于Pareto最優(yōu)性概念的非劣解集[1]，所以如何進(jìn)行綜合與折中就成為解決問題的關(guān)鍵。求解它們需要用不同于單目標(biāo)優(yōu)化的數(shù)學(xué)工具,甚至最優(yōu)的含義也發(fā)生了變化。優(yōu)化問題一直是倍受人們關(guān)注的問題，自1950 年以來,運(yùn)籌學(xué)研究人員已經(jīng)建立了許多方法解決MOP。進(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ùn)算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。這類算法在適應(yīng)值設(shè)計(jì)中鼓勵非劣解等級優(yōu)先個體和同一等級內(nèi)較為稀疏個體以較大概率出現(xiàn)在后代群體中。這類算法由于采用的進(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ā)展才開始活躍起來。 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類[11]：前決策（先驗(yàn)式）、后決策（后驗(yàn)式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時間先后劃分的。NSGAII算法首先隨機(jī)產(chǎn)生一個初始種群，對種群通過采用輪盤賭的方式選擇、交叉和變異操作獲得新的種群，將種群中的個體構(gòu)造其Pareto 邊界集，并根據(jù)個體間的聚集距離，建立偏序關(guān)系，最終從偏序關(guān)系中選擇原始種群規(guī)模大小的個體，組成新的種群，完成了一次進(jìn)化操作。定義1 ( 個體的Pareto 支配關(guān)系) 。 由 中的所有非支配個體構(gòu)成的子集稱為 的非支配集。在已有研究中，多目標(biāo)遺傳算法的適應(yīng)值設(shè)計(jì)(Fitness Assignment)主要有基于加權(quán)策略、基于目標(biāo)設(shè)計(jì)策略和基于非劣解等級優(yōu)先策略三種設(shè)計(jì)策略[14]：(1)基于加權(quán)策略的適應(yīng)值設(shè)計(jì)，即基于聚合策略的方法，是通過加權(quán)策略將多個目標(biāo)轉(zhuǎn)化為單個目標(biāo)后進(jìn)行優(yōu)化。這類算法的適應(yīng)值設(shè)計(jì)主要有等級優(yōu)先、深度優(yōu)先和基于優(yōu)先數(shù)三種：等級優(yōu)先策略算法在計(jì)算適應(yīng)值時主要考慮個體在群體中“優(yōu)于”其他個體的數(shù)目或考慮優(yōu)于該個體的其他個體數(shù)目之和，以此確定給個體的適應(yīng)度值；而深度優(yōu)先策略算法在分配個體適應(yīng)值時主要以個體所在的非劣解等級及等級內(nèi)的疏密程度有關(guān)；基于優(yōu)先數(shù)的適應(yīng)值分配算法在計(jì)算個體適應(yīng)值時，考慮了個體所優(yōu)先于或劣于群體中其他個體的數(shù)目。假設(shè)第代種群中的個體，在第代種群個體排序中的位置為，基于個體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個體進(jìn)行級別排序。進(jìn)化算法由于其進(jìn)化算子固有的隨機(jī)誤差，因而基于有限群體實(shí)施進(jìn)化時會出現(xiàn)收斂至某一個解。(3)分區(qū)統(tǒng)計(jì)數(shù)目策略：分區(qū)統(tǒng)計(jì)數(shù)目策略是將目標(biāo)空間劃分成一定比例的區(qū)域，通過統(tǒng)計(jì)個體所在區(qū)域中鄰域解數(shù)目來確定個體被保留的概率鄰域解數(shù)目越大，被保留概率越小。另一種實(shí)現(xiàn)方式是采用獨(dú)立于進(jìn)化群體的伴隨群體，即使用帶有所謂的檔案（Archive）的方式，保留與更新算法進(jìn)化過程中搜索到的非劣解集來維護(hù)當(dāng)代群體中的滿意群體，使其能夠復(fù)制到下一代，伴隨群體僅作為一個外部存儲集，獨(dú)立于進(jìn)化過程的優(yōu)化操作[17]。Holland教授提出的遺傳算法，現(xiàn)在一般稱為簡單遺傳算法或基本遺傳算法[18]，其基本流程如下圖：圖21遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問題空間的參數(shù)，因此在算法開始進(jìn)行之前，首先要選擇合適的編碼方式對待優(yōu)化的參數(shù)進(jìn)行編碼。通常情況下，這兩種方法同時作為優(yōu)化準(zhǔn)則使用。遺傳算法的選擇和交叉算子賦予了它強(qiáng)有力的搜索能力，變異算子則使算法能搜索到問題解空間的每一個點(diǎn)，以確保算法能達(dá)到全局最優(yōu)。所以現(xiàn)階段的性能評價方法主要集中于對算法的效果的衡量。2. 解集分布性評價在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過于集中，則周圍的很多解事實(shí)上并沒有太大的意義，也不利于產(chǎn)生新個體，從而影響了種群的進(jìn)化效果。2. 實(shí)驗(yàn)比較分析實(shí)驗(yàn)比較分析是指通過對優(yōu)化算例的結(jié)果和結(jié)果的各種指標(biāo)進(jìn)行比較，驗(yàn)證新算法與已存在的算法之間的性能差別。第三章 優(yōu)化算例及分析 NSGAⅡ和MOGLS算法（NSGAⅡ）在NSGA 中, 同一個小生境內(nèi)的個體適應(yīng)度共享, 從而降低該小生境內(nèi)個體的競爭力, 防止種群在收斂過程中陷入局部最優(yōu), 實(shí)現(xiàn)種群多樣性。首先將當(dāng)前的所有的非劣解個體劃為同一等級，令其等級為；然后將這些個體從種群中移出，在剩余個體中尋找出新的非劣解，再令其等級為；重復(fù)上述過程，直至種群中所有個體都被設(shè)定相應(yīng)的等級。為了計(jì)算每個個體的聚集距離，需要對群體按每個子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對個子目標(biāo)分別進(jìn)行排序的時間復(fù)雜度為。然后采用選擇、交叉、變異算子產(chǎn)生下一代種群，大小也為，完成第一代進(jìn)化。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。雜交算法的目的不是確定一個單一的最終解，而是試圖尋找這個多目標(biāo)問題所有符合約束條件的最優(yōu)解。這種方法下，每個解都有自己的搜索方向。精英保留策略：本算法保留了兩組解：當(dāng)前解和試驗(yàn)的非劣解。（5）精英保留策略：從試驗(yàn)非劣解集中隨機(jī)選擇解，接著將這個選中的解加入到在(4)中解中，它的功能是為了創(chuàng)建解的一個種群。指標(biāo)由Zitzler提出，其定義為：設(shè)是兩種算法優(yōu)化所得的非劣解集，指標(biāo)是一種值域定義在上、用來刻畫之間偏序能性的指標(biāo)：。分別選用線性交叉和非均勻變異方式生成新個體。符號集約定為：設(shè)有種算法（本文有兩種）參與性能評價，對于某個優(yōu)化算例，采用每種算法獨(dú)立運(yùn)行次（本文為30次），每次獨(dú)立運(yùn)行后，獲得非劣解集， ，合并各算法獨(dú)立運(yùn)行所得的非劣解集，剔除其中劣解后得到算法優(yōu)化的最終非劣解集，則Zitzler評價方法的實(shí)現(xiàn)過程可描述為：(1)令， ；。本章首先詳細(xì)介紹了NSGAII和MOGLS的原理及流程，特別是兩種方法存在差異的適應(yīng)度評價和精英保留策略。這無疑消耗了大量的時間和精力。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，包括適應(yīng)值設(shè)計(jì)、維持群體多樣性和精英保留策略。參 考 文 獻(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