本科畢業(yè)設計-多目標進化算法及應用預計.doc

華北電力大學畢業(yè)設計摘 要 在最近二十年，作為一類新興的優(yōu)化技術，多目標進化算法吸引了極大關注，許多學者提出了不同的算法，多目標進化算法已經(jīng)成為處理多目標工程設計和科學研究問題的重要方法。許多moea的方面被廣泛地調研，然而一些問題仍然沒有被很好地受到關注。例如，隨著這類算法的快速發(fā)展，對算法之間性能進行比較變得越來越重要。本文分析總結了兩種目前流行的所目標進化算法的基本原理，并通過算例來比較它們的性能。本文主要工作內容如下：1. 簡要回顧了多目標進化算法的發(fā)展歷史，按照算法原理與進化模式將算法分類。2. 簡述多目標問題及進化算法的相關技術，詳細分析了nsga-ii算法和mogls算法。3. 分別利用nsga-ii算法和mogls算法對算例進行求解，并用c指標對兩種算法的結果進行評價，得出它們各自的優(yōu)缺點。多目標問題仍向算法設計，呈現(xiàn)和執(zhí)行提出挑戰(zhàn)。不斷變化的多目標問題很少被考慮到它的時變特性，對此有效的多目標進化算法很罕見，多目標進化算法的結合量計算和有區(qū)別的進化還始終停留在初級階段。多目標進化算法的應用應該在未來不斷地延續(xù)，moea的理論分析比它本身更復雜而且應該通過主要從事計算機和數(shù)學研究人員的努力工作來解決。關鍵詞：多目標優(yōu)化，進化算法，適應度計算，精英保留，局部搜索 2abstractin the past two decades, as a new subject， multi-objective evolutionary algorithm (moea) has attracted much attention, the numerous algorithms have been proposed and moea has become the important approach to deal with multi-objective optimization problem （mop） of engineering design and science research. many aspects of moea have been extensively investigated, however, some problems are still not considered very well. for example,under the condition that many algorithms are brought up, the methods that compare the performance between the algorithms have become very prominent. the main principles of two popular algorithms were analyzed in this paper. the main work of this paper can be sumrised as the following:1.a brief review of the history and current studies of moea was brought out.all common algorithms have been distributed into several sorts. 2 mop and the relational technique of moea was introduced concisely.then nsga-ii and mogls were expounded in detail.3 nsga-ii and mogls were used for solving the same multi-objective scheduling problem separately and their sesults was evaluated by c norm, through this ,the advantage and defect of these two algorithms have been emerged.moop still poses the challenges for algorithm design, visualization and implementation. the dynamic mop is seldom considered for its time-varying nature. the effective pmoea is very sparse and the moea combining quantum computing and differential evolution is still in the infancy period. the applications of moea should be extended continuously in the near future. the theory analysis of moea is more complicated than moea itself and should be considered through the hard works of researchers majoring in computers and mathematics et al.key words: multi-objective optimization,evolutionary algorithm,fitness calculating,elitism duplication,local search 目 錄摘 要 .abstract.第1章 緒 論11.1究背景及意義11.2多目標進化算法的研究現(xiàn)狀21.3本文研究內容4第2章 多目標進化算法62.1 多目標優(yōu)化基本概念62.1.1多目標優(yōu)化問題描述62.2多目標遺傳算法設計的關鍵技術72.2.1適應值設計72.2.2維持群體多樣性72.2.3精英保留策略92.3 nsga-和mogls算法12!異常的公式結尾2.3.2mogls142.4本章小結11附 錄26致 謝33第3章 優(yōu)化算例及分析303.1多目標遺傳算法的性能評價20 3.3.1性能評價指標20 3.3.2測試函數(shù)及其設計253.2二級標題 353.3二級標題 403.3.1三級標題40 3.3.2三級標題45第 4 章 總結304.1二級標題 304.2二級標題 354.3二級標題 404.3.1三級標題40 4.3.2三級標題45參考文獻50附 錄 51致 謝 52華北電力大學本科畢業(yè)設計（論文）第1章 緒 論許多科學研究和工程實踐中遇到的優(yōu)化問題，通常需要綜合考慮多方面因素，這就要求在解決問題時同時對多個目標進行優(yōu)化，這樣的問題被稱為多目標優(yōu)化問題(multi-objective optimization problem, mop)，它們有許多沖突的目標。有時目標之間是相輔相成、互相促進的，但更多的時候，目標之間是相互矛盾、此消彼長的。因此在絕大多數(shù)情況下，若想達到總目標的最優(yōu)，就需要對各個目標進行綜合考慮、折中處理，所得到的解是一組基于pareto最優(yōu)性概念的非劣解集1，所以如何進行綜合與折中就成為解決問題的關鍵。1.1研究背景及意義生物在其延續(xù)生存的過程中，逐漸適應其生存環(huán)境，使得品種不斷的到改良，這種生命現(xiàn)象叫做進化。進化算法(evolutionary algorithm, ea)是一種通過模擬生物進化規(guī)律來進行選擇與變化的隨機搜索算法，起源于20 世紀50 年代末，現(xiàn)有的代表性進化方法有遺傳算法(genetic algorithm, ga)、進化規(guī)劃(evolutionary programming, ep)和進化策略(evolutionstrategy, es)等幾種方法2。進化算法非常適用于于求解高度復雜的非線性問題，并且由于這類算法具有通用性，因而被廣泛地應用于單個目標的復雜系統(tǒng)優(yōu)化問題。然而，人們在求解現(xiàn)實世界許多優(yōu)化問題時，通常不追求單一目標的最優(yōu)性，這就要求在解決問題時同時對多個目標進行優(yōu)化和權衡，有時目標之間是相輔相成、互相促進的，但更多的時候，目標之間是相互矛盾、此消彼長的，這樣的問題被稱為多目標優(yōu)化問題(multi-objective optimization problem, mop)，大多數(shù)工程和科學問題是多目標最優(yōu)問題。多目標優(yōu)化問題的各目標之間通過決策變量相互制約,對其中一個目標優(yōu)化必須以其它目標作為代價,而且各目標的單位又往往不一致,因此很難客觀地評價多目標問題解的優(yōu)劣性。例如,在設計一座橋梁時,我們一方面希望建設橋梁的費用最小,另一方面希望橋梁具有最大的安全性。與單目標優(yōu)化問題的本質區(qū)別在于,多目標優(yōu)化問題的解不是唯一的,而是存在一個最優(yōu)解集合,集合中元素稱為pareto 最優(yōu)或非劣最優(yōu)(non-dominance) 。求解它們需要用不同于單目標優(yōu)化的數(shù)學工具,甚至最優(yōu)的含義也發(fā)生了變化。由于它們有許多沖突的目標，因此若想達到總目標的最優(yōu)，就需要對各個目標進行綜合考慮、折中處理，所以如何進行綜合與折中就成為解決問題的關鍵。多目標進化算法(multi-objective evolutionary algorithm, moea)就是一類可以有效解決這種問題的優(yōu)化技術3。它的主要思想是將進化算法的概念引入到多目標優(yōu)化領域，對多目標優(yōu)化問題同樣采用進化操作方式，但算法由單目標優(yōu)化問題求取一個最優(yōu)解，轉變?yōu)槎嗄繕藘?yōu)化問題中求取一個最優(yōu)解集，該解集稱為pareto最優(yōu)解集。最優(yōu)解集中的每個解，理論上都是“最優(yōu)解”，而在實際應用中，可以根據(jù)決策需要選擇其中一個解作為最終決策方案，實現(xiàn)最優(yōu)化的目的。多目標進化算法是一門新興的學科，理論與算法并不完善，尚處于發(fā)展階段。然而，它對工程項目具有重要的實踐意義，因此在過去的十多年間涌現(xiàn)出許多新的改進算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標進化算法。而對算法性能進行比較和評價就成為一個重要的核心問題，引起了諸多學者的研究興趣。1.2多目標進化算法的研究現(xiàn)狀優(yōu)化問題一直是倍受人們關注的問題，自1950 年以來,運籌學研究人員已經(jīng)建立了許多方法解決mop。在專業(yè)文獻中,有許多數(shù)學規(guī)劃技巧解決mop ,如多目標加權法、分層序列法、約束法、目標規(guī)劃法等。遺傳算法自出現(xiàn)以來在許多領域得到了廣泛的應用，在解決簡單的單目標優(yōu)化問題方面取得了很好的成果，但面對復雜的多目標優(yōu)化問題，傳統(tǒng)的遺傳算法就顯得力不從心。例如在現(xiàn)代能源系統(tǒng)生產(chǎn)過程參數(shù)的優(yōu)化4設計中經(jīng)常會遇到多目標函數(shù)的優(yōu)化問題，使用經(jīng)典的多目標優(yōu)化方法通常把多個目標函數(shù)整合成單目標，將問題轉變?yōu)閱文繕藘?yōu)化問題，然后采用單目標的優(yōu)化技術求解。但這些方法存在：只能得到一個解；多個目標函數(shù)之間量綱不同難以統(tǒng)一；加權值的分配帶有較強的主觀性；加權的目標函數(shù)之間通過決策變量相互制約，最終優(yōu)化目標僅為各目標之和，各目標的優(yōu)化進度不可操作等缺點。這是因為傳統(tǒng)數(shù)學規(guī)劃方法存在一些缺陷,例如有些方法對pareto 前沿比較敏感,當pareto 前沿是凹的或者不連續(xù)時,這些方法失效;有些方法要求目標函數(shù)和約束條件可微;有些方法每次運行只產(chǎn)生一個解,求多個解時需要運行多次,效率較低。進化多目標優(yōu)化始于1967年，此后眾多的研究人員通過對遺傳算法進行改造，相繼提出了多種用于解決多目標優(yōu)化問題的遺傳算法，如基于向量評估的遺傳算法(vega) 5，小組決勝遺傳算法(npga) 6，非支配排序遺傳算法(nsga)及其改進算法nsga-ii7等. 其中nsga的改進算法nsga-ii是帶有精英策略的非支配排序遺傳算法，改進了先前算法的不足之處，提高了算法的運算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。自scharfer提出vega起，多目標進化算法的發(fā)展經(jīng)歷了由基于單目標子群體優(yōu)化的算法到基于pareto最優(yōu)性指導的分級策略與適應值共享策略算法的發(fā)展歷程。按照算法原理與進化模式劃分，現(xiàn)有多目標進化算法可分如下四大類：第一類算法是早期基于單目標群體優(yōu)化的moga。這類算法通過加權或劃分子群體進化等方法將mop轉化為不同的sop，然后借助現(xiàn)有單目標遺傳算法對轉化后的sop進行求解，最后對進化獲得的解進行分析，篩選出非劣解集。由于這類算法的設計思想是基于單目標遺傳算法的進化策略，因此它的優(yōu)點是算法容易實現(xiàn)；其不足是，基于單目標子群體優(yōu)化的算法很難搜索到嚴格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點。代表算法有vega、wbga、dm等。ishibuchi、murata等人1996年提出的mogls是在隨機權策略的wbga中引入局部搜索的改進算法，其本質屬于這類算法8。第二類算法是基于goldberg提出的適應值分級和共享策略的多目標遺傳算法。這類算法在適應值設計中鼓勵非劣解等級優(yōu)先個體和同一等級內較為稀疏個體以較大概率出現(xiàn)在后代群體中。由于這類算法是基于pareto概念的moga，因此，它的優(yōu)點是可以通過單次優(yōu)化獲得一組靠近真實非劣解前沿的非劣解集；但由于算法未考慮進化過程中精英個體的保留，因此解的收斂速度及收斂性能不夠穩(wěn)健。代表算法有moga、nsga和npga等。第三類算法是由第二類算法發(fā)展起來的精英保留策略moga。這類算法通過在進化過程中引入外部伴隨群體對群體中的精英個體加以保留，同時采用更加成熟的適應值設計策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。這類算法的不足之處是，算法進化模式單一、局部搜索性能欠佳，之所以存在這些不足，主要是因為這類算法大多由第二類算法改進得到，因此進化模式不可能完全擺脫先前的算法框架，并且遺傳算法的進化原理決定了它不可能具有性能較高的局部搜索能力。代表算法有npga-ii、nsga-ii、paes和spea等9。第四類算法是采用其他搜索算法策略改進的moea。這類算法由于采用的進化策略是基于模擬退火搜索、禁忌搜索、粒子群優(yōu)化、小生境策略等不以傳統(tǒng)遺傳算法進化結構為主導的優(yōu)化策略，因此在早期的多目標進化算法研究中并未受到廣泛重視，只是在近年隨著多目標遺傳算法局部搜索性能欠佳的不足逐漸呈現(xiàn)，以及其他進化策略單目標進化算法的迅速發(fā)展才開始活躍起來。這類算法由于群體規(guī)模適中，因此算法復雜性相對較低，而且由于算法局部搜索性能優(yōu)越，因此常?？梢耘c現(xiàn)有的moga結合，形成新的精英算法。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)、又能維持群體多樣性，因此，在算法設計時往往設置了許多控制參數(shù)對算法性能進行調整，這又導致在求解問題時常常需要借助大量試驗計算分析確定進化參數(shù)，因此算法性能不夠穩(wěn)健。代表算法有mose、mopso等10。除了上述四類算法外，一些學者在演化策略中引入偏好分級或適應值分享機制獲取滿意解。但由于這些方法不能通過幾次運行獲得穩(wěn)定的非劣解集，且算法復雜性較高，因此這類研究不是多目標進化算法研究的主流方向。而考慮偏好關系對遺傳進化的影響，大多是用模糊集方法進行偏好信息的處理，而進一步利用偏好對進化進行指導或通過進化引導偏好的交互式多目標進化算法還僅僅處于概念研究階段，距算法實現(xiàn)尚有較大差距。多目標遺傳算法的研究一直是這類算法研究的主流方向：盡管遺傳算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他進化策略或啟發(fā)式局部搜索算法好的局部搜索性能，因此，以進化算法為算法主體，結合遺傳算法全局搜索和一般啟發(fā)式進化策略局部搜索的優(yōu)勢，獲得高性能的多目標優(yōu)化算法，成為多目標進化算法研究的潛在發(fā)展方向。1.3本文研究內容 多目標進化算法如果按決策方式劃分，則可以分為三類11：前決策（先驗式）、后決策（后驗式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時間先后劃分的。其中，后決策是最常用的技術，即算法終止時提供給用戶一組最優(yōu)解。目前絕大多數(shù)多目標進化算法是排序選擇法和后決策技術類型的。spea/spea2 (zitzler & thiele 2001)和nsga/nsga-ii (srinivas & deb 2002)兩類算法目前的應用更廣泛，也更具有代表性。由于本文需要對多目標進化算法的結構進行深入的分析，所以需要在此選擇一個代表性的算法，通過該算法的簡介，來描述一下多目標進化算法的一些基本概念和工作原理。本文將以nsga-ii算法和mogls（multi-objective genetic lcal search）算法為例，通過算例和指定的函數(shù)指標來分析比較它們各自性能的優(yōu)缺點。nsga-ii算法首先隨機產(chǎn)生一個初始種群，對種群通過采用輪盤賭的方式選擇、交叉和變異操作獲得新的種群，將種群中的個體構造其pareto 邊界集，并根據(jù)個體間的聚集距離，建立偏序關系，最終從偏序關系中選擇原始種群規(guī)模大小的個體，組成新的種群，完成了一次進化操作。由此可見，對于多目標進化算法而言，構造pareto 邊界集和計算個體間的聚集距離是新的概念，也是絕大多數(shù)多目標進化算法共有的流程，這為之后提取算法公共流程方式的討論提供了基本的依據(jù)。mogls是ishibuchi和murata兩位學者提出的。最初的mogls是在遺傳進化過程中，每代遺傳操作生成新個體后，對現(xiàn)有群體中的所有個體進行局部搜索；后來ishibuchi等人對局部搜索的步長選取、鄰域搜索效率做了進一步研究后，將局部搜索過程僅應用于當前群體中的優(yōu)秀，顯著提高了算法效率，改進后的算法可獲得與spea、nsga-ii相當?shù)膬?yōu)化性能。mogls的優(yōu)點是通過隨機權將mop轉化為sop，算法容易實現(xiàn)，并且恰當控制mogls中鄰域搜索個體的選取及步長可以在減少計算復雜度的同時獲得良好的計算結果；算法的不足之處是，算法的構造是基于mop轉化為sop的思想，因此在不明確多個目標偏好情況下，采用隨機權的方法往往不能保證所得非劣解集分布的均勻性。第2章 多目標進化算法2.1 多目標優(yōu)化基本概念2.1.1多目標優(yōu)化問題描述 多目標問題( mop) 的一般描述為: 給定決策向量 , 它滿足下列約束: ( 2-1) ( 2-2)設有r 個優(yōu)化目標, 且這r 個優(yōu)化目標是相互沖突的, 優(yōu)化目標可表示為: 尋求, 使在滿足約束( 2-1) 和( 2-2) 的同時達到最小。2.1.2最優(yōu)性對于多目標優(yōu)化問題, 由于其待優(yōu)化的各個子目標一般是相互沖突的, 因此需要定義解個體間的優(yōu)劣關系, 以便對候選解進行評價與取舍。本文采用廣泛使用的pareto 最優(yōu)性12定義。定義1 ( 個體的pareto 支配關系) 。設和是進化群體中的任意兩個不同的個體,稱支配(dominate) ,則必須滿足下列二個條件:( 1) 對所有的子目標, 不比 差, 即 ( k=1, 2, r) ; （2） 至少存在一個子目標,使比好。即, 使其中r 為子目標的數(shù)量。此時稱 為非支配的( non- dominated), 為被支配的( dominated) 。表示為, 其中“”是支配關系。定義2( pareto 非支配集)。設有解集,若中的個體不被任何其它個體支配, 則是 中的非支配個體; 由 中的所有非支配個體構成的子集稱為 的非支配集。即: 最優(yōu)性的含義為：是pareto最優(yōu)解，表示在整個解空間中，不存在這樣的解：某一個目標比小的同時，保持其余個目標值不大于x的目標值。因此，滿足這種最優(yōu)性的“最優(yōu)解”往往不是單個解，而是一組滿足上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱作非劣解集（pareto solutions set）或非受控解集(nondominated solutions set)；非劣解對應的目標值在目標空間中稱為非劣點；最優(yōu)解集在優(yōu)化目標空間構成的分布稱作非劣解前沿。在決策和優(yōu)化問題中，最優(yōu)性取決于如何比較和排序候選解，及決策者的偏好結構。從決策者的立場來看，一般認為每對候選解具有以下比較關系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。由此才可以對每對解之間的優(yōu)劣比較進行細致的區(qū)分13。2.2多目標遺傳算法設計的關鍵技術2.2.1適應值設計mop問題包含多個待優(yōu)化的子目標，通常eas用于多目標優(yōu)化時必須考慮兩個關鍵問題：(1)為了保證朝pareto最優(yōu)集的方向搜索，如何實施適應度賦值和選擇。(2)為了避免未成熟收斂和獲得均勻分布且范圍最廣的非劣解，如何保持群體的多樣性。在已有研究中，多目標遺傳算法的適應值設計(fitness assignment)主要有基于加權策略、基于目標設計策略和基于非劣解等級優(yōu)先策略三種設計策略14：(1)基于加權策略的適應值設計，即基于聚合策略的方法，是通過加權策略將多個目標轉化為單個目標后進行優(yōu)化。這種適應值設計的遺傳算法通常需要在算法進化過程中系統(tǒng)地對函數(shù)中的參數(shù)的權重值進行調整，以便得到一組非劣解集。在進化的每一代中參數(shù)呈現(xiàn)有規(guī)律的變化，但在該代操作過程中保持不變，常見的進化加權法，個體的評估使用確定的加權組合，所有個體都有一個適應度值，保證了搜索方向朝最優(yōu)解邁進。(2)基于目標設計策略的算法，即基于準則的策略，每當個體選中后進行復制時根據(jù)不同的目標來決定是否被復制至配對池。此方法通過在不同進化代之間更換優(yōu)化目標每次優(yōu)化一個目標，使算法群體每次運行得到一個非劣解，從而通過多次運行找到優(yōu)化問題的非劣解集。目前，常用的方法是在選擇階段根據(jù)概率來確定各子目標的排序，該概率值由用戶確定或隨機產(chǎn)生。這種策略存在的問題是進化結果容易偏向某些極端邊界解，并且對pareto最優(yōu)前端的非凸部敏感。(3)基于非劣解等級優(yōu)先概念的適應值分配策略由goldberg最先提出，后人大多在此基礎上進行改進，如將群體劃分為幾個有序的子群體。這類算法的適應值設計主要有等級優(yōu)先、深度優(yōu)先和基于優(yōu)先數(shù)三種：等級優(yōu)先策略算法在計算適應值時主要考慮個體在群體中“優(yōu)于”其他個體的數(shù)目或考慮優(yōu)于該個體的其他個體數(shù)目之和，以此確定給個體的適應度值；而深度優(yōu)先策略算法在分配個體適應值時主要以個體所在的非劣解等級及等級內的疏密程度有關；基于優(yōu)先數(shù)的適應值分配算法在計算個體適應值時，考慮了個體所優(yōu)先于或劣于群體中其他個體的數(shù)目。一般來說直接統(tǒng)計優(yōu)勝個體數(shù)目的操作方式簡單，在原理上一目了然。單目標優(yōu)化中的目標函數(shù)常與適應度函數(shù)相同，但mop問題中的適應度賦值和選擇必須考慮幾個子目標，moeas必須根據(jù)個體間的pareto優(yōu)勝關系和其他信息為個體確定適應度值，這種適應度值和每個目標函數(shù)的具體大小沒有直接關系。另外，與單目標優(yōu)化不同的是，在個體保持不變的條件下，同一個體在這一代和下一代的適應值可能不相等。pareto優(yōu)勝關系是決定個體適應度函數(shù)值的重要依據(jù)，很多moeas根據(jù)個體間的這種關系，將個體的適應度函數(shù)值分成兩個層次，即劣解和非劣解，后者的適應度值總是優(yōu)于前者。當個體間沒有pareto優(yōu)勝關系時，其他形式的個體信息被用于確定適應度函數(shù)值，其中個體密度值是利用最多的信息，并采用不同的方法估計個體密度值?；趐areto優(yōu)勝關系的選擇方法已經(jīng)被廣大研究者采納，現(xiàn)已有多種基于pareto的適應度賦值方案，其中基于種群個體級別排序的適應度賦值方法是較常見的一種方法。多目標問題與單目標問題不同，它的優(yōu)劣性與支配關系并非定義目標向量之間的那種整體有序關系，只是給出部分有序關系，因而種群的級別排序不具有唯一性。假設第代種群中的個體，在第代種群個體排序中的位置為，基于個體排序的適應度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個體進行級別排序。(2)利用線性或非線性的插值方法在最低序號與最高序號之間進行插值。(3)具有相同序號的個體進行適應度共享算子操作，即通過除以相同序號的個體數(shù)目得到新的適應度值，另外，也可以給不同序號的個體分配固定不變的適應度值。2.2.2維持群體多樣性因為eas是并行地處理一組解，通過雜交和變異來搜索空間以尋找可能的最優(yōu)區(qū)域，通過選擇來搜索具有較高適應度的個體。傳統(tǒng)的進化算法在pareto最優(yōu)集上執(zhí)行多目標搜尋，希望找出盡可能均勻分布的解集，因而個體的多樣性減少的很快，經(jīng)常收斂至單個解而丟失多個其他非劣解。在進化過程中某些具有較高適應度個體的大量復制造成高選擇壓力，使得個別具有更高適應度的個體得不到遺傳的機會，甚至導致整個群體出現(xiàn)同解的現(xiàn)象15。如果單純從群體多樣性出發(fā)，群體規(guī)模應該越大越好，但群體規(guī)模太大會帶來若干弊病：一是從計算效率來看，群體越大，導致其適應度評估次數(shù)增加，引起計算量的增加，從而影響算法效能；二是群體中個體生存下來的選擇概率大多采用和適應度成比例的方法，當群體中個體非常多時，少量適應度很高的個體會被選擇而生存下來，大多數(shù)個體被淘汰，嚴重影響交叉操作。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進化算法多樣性的途徑。進化算法由于其進化算子固有的隨機誤差，因而基于有限群體實施進化時會出現(xiàn)收斂至某一個解。因為多目標優(yōu)化的目的是得到一組在整個pareto曲面上盡可能均勻分布的一組解，因此必須在進化過程中采取措施避免進化結果收斂至單個解。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點，大多數(shù)moeas在當代群體中維持多樣性是在選擇過程中結合了密度信息，即個體在其鄰域范圍內所占的密度越高被選擇復制的機會越小?，F(xiàn)有多目標遺傳算法可根據(jù)統(tǒng)計概率密度估計的方法加以分類為如下三種策略來維持群體多樣性：(1)基于核函數(shù)的評價策略：基于核函數(shù)的評價策略主要通過計算以個體為“核”、群體中其他個體距離“核”的核函數(shù)之和，通過優(yōu)先保留核函數(shù)值較大的個體即較稀疏的解個體達到維持群體多樣性的目的。具體應用時首先根據(jù)內核函數(shù)來定義一個點的鄰域范圍，內核函數(shù)采用至另一點的距離作為參數(shù)。每一個個體計算至其他個體的距離，通過內核函數(shù)的映射后求和計算出值，該累加值代表了個體的密度估計。(2)基于鄰域解數(shù)目的評價策略：基于鄰域解數(shù)目的評價策略是以評價解為核心、包含一定數(shù)量鄰域解的鄰域半徑為指標，優(yōu)先保留鄰域半徑較大的個體即較稀疏的解個體。該策略主要考慮給定點至第個最近鄰居的距離，以便估計出其在鄰域內的密度。(3)分區(qū)統(tǒng)計數(shù)目策略：分區(qū)統(tǒng)計數(shù)目策略是將目標空間劃分成一定比例的區(qū)域，通過統(tǒng)計個體所在區(qū)域中鄰域解數(shù)目來確定個體被保留的概率鄰域解數(shù)目越大，被保留概率越小。該方法采用一個網(wǎng)格來定義空間上的鄰居關系，個體的密度只要通過簡單地統(tǒng)計同一網(wǎng)格內的個體數(shù)目即可，這種網(wǎng)絡可以是固定的，也可以根據(jù)當前群體進行自適應調整。多目標進化算法與單目標進化算法類似，為了提高群體多樣性，在算法過程中盡量采用小生境（niche）共享技術，使得在一個群體內可以形成在多目標問題上分布均勻的非劣最優(yōu)解集。具有相同pareto級別序號的解個體在實施共享適應度值后，還必須按解的目標向量之間的空間距離進行小生境規(guī)模調整。當兩個解的目標向量之間的空間距離小于某一預定值時，相應解的小生境規(guī)模就必須進行調整。此外，還有同時基于決策向量空間與目標向量空間的混合共享技術，共享問題的關鍵是如何確定共享參數(shù)，的選擇將會影響算法的性能，而適應度共享效果則共同取決于和種群大小16。2.2.3精英保留策略遺傳算法是基于隨機進化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標遺傳算法大都引入了精英保留策略?，F(xiàn)有算法中精英策略的實現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過確定性的選擇方法在混合群體中選擇后代，而不是采用變化之后的配對池來替換舊群體，增大了精英個體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。另一種實現(xiàn)方式是采用獨立于進化群體的伴隨群體，即使用帶有所謂的檔案（archive）的方式，保留與更新算法進化過程中搜索到的非劣解集來維護當代群體中的滿意群體，使其能夠復制到下一代，伴隨群體僅作為一個外部存儲集，獨立于進化過程的優(yōu)化操作17。由于內存資源的限制，以上兩種最優(yōu)個體保留策略必須確定哪些個體作為最優(yōu)個體加以保留。通常采用優(yōu)勝準則來確定最優(yōu)個體。如果使用伴隨群體的方式，則伴隨群體中包括當前的近似pareto集，即伴隨群體中受控的個體被移去。但是使用優(yōu)勝關系比較的方法有時也存在問題，如對某些連續(xù)型問題所對應的pareto集可能包含無窮多個解，因此需要補充其他的信息知識來減小所存儲的個體數(shù)目。這些信息包括密度信息，個體進入伴隨群體所需時間。moeas的最優(yōu)個體大多利用優(yōu)勝關系和密度兩者的組合來進行挑選，最優(yōu)個體保存在每代的伴隨群體中。更新的算法研究表明，如果同時采用這兩種精英策略，可以進一步提高算法的搜索性能與收斂效果。2.3遺傳算法的一般流程holland教授提出的遺傳算法，現(xiàn)在一般稱為簡單遺傳算法或基本遺傳算法18，其基本流程如下圖：圖2-1遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問題空間的參數(shù)，因此在算法開始進行之前，首先要選擇合適的編碼方式對待優(yōu)化的參數(shù)進行編碼。通常采用二進制編碼，將參數(shù)轉換成為和組成的數(shù)字串。 (2) 產(chǎn)生初始種群：隨機地產(chǎn)生一個由個個體組成的種群，該種群代表一些可能解的集合。遺傳算法的任務是種群出發(fā)，模擬生物進化的過程進行優(yōu)勝劣汰，最后得出滿足優(yōu)化要求的種群和個體。 (3) 設計適應度函數(shù)：把問題的目標函數(shù)轉換成合適的適應度函數(shù)，并根據(jù)適應度函數(shù)計算種群中的每個個體的適應度，為種群進化的選擇提供依據(jù)。 (4) 優(yōu)化準則：也可稱作終止條件，是用來判斷算法是否可以終止的標準?？梢栽O定進化的最大代數(shù)，當進化到最大代數(shù)時，算法終止運行。也可以設定期望的適應度函數(shù)值，只有當種群中存在個體能達到期望值時，算法才可以結束。通常情況下，這兩種方法同時作為優(yōu)化準則使用。(5) 選擇(復制)操作:按一定概率從群體中選擇個體，作為雙親用于繁殖后代，產(chǎn)生新的個體。在此操作中，適應于生存環(huán)境的優(yōu)良個體將有更多的機會繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。(6) 交叉操作:隨機地選擇用于繁殖的每一對個體的同一基因位，將其染色體在此基因位斷開并相互交換。(7) 變異操作:以一定的概率從群體中選擇若干個個體。對于選中的個體，隨機選擇某一位進行取反操作。對產(chǎn)生的新一代群體重新進行評價、選擇、雜交和變異。一代一代循環(huán)往復，使種群中最優(yōu)個體的適應度和平均適應度不斷提高，直至最優(yōu)個體的適應度滿足優(yōu)化準則或最優(yōu)個體的適應度和平均適應度不再提高，則迭代過程收斂，算法結束。遺傳算法的選擇和交叉算子賦予了它強有力的搜索能力，變異算子則使算法能搜索到問題解空間的每一個點，以確保算法能達到全局最優(yōu)。遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領域和種類。對一個需要進行優(yōu)化計算的實際應用問題，一般可以按照上述步驟來構造求解該問題的遺傳算法。由上述步驟可以看出，構造遺傳算法時需要考慮的兩個主要問題是可行解的編碼方法和遺傳算子的設計，這也是設計遺傳算法的兩個關鍵步驟。2.4算法性能評價2.4.1多目標進化算法性能評價的研究現(xiàn)狀多目標遺傳算法的性能評價與傳統(tǒng)優(yōu)化算法及單目標遺傳算法的性能評價有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過梯度下降速度進行評價，并且可以通過嚴格的數(shù)學證明分析其收斂性能；單目標遺傳算法可以采用基于模式定理或基于馬爾可夫隨機過程理論的證明分析其收斂性，盡管這類證明研究還很初步。然而在對多目標進化算法的性能進行評價時，一般需要考慮到三個較為重要的因素19：算法的效率、算法的效果，以及算法的魯棒性。算法的效率是指算法自身的時間復雜度和空間復雜度，也即算法運算時間的長短和資源消耗的多少；算法的效果是指算法求得的解集的質量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應用范圍和穩(wěn)定性，也即是否對多種問題都有很好的求解能力、是否求解問題時總是相對穩(wěn)定的。而從現(xiàn)階段的研究來看，人們更關注的是，算法結果是否為高質量的結果，而對于另外兩個因素相對要求并不高，而且對于算法的效率來說，涉及到的是經(jīng)典的算法復雜度理論，已經(jīng)有很完善的泛化體系對其進行評價了，無需在多目標進化算法領域對其再進行專門的研究。所以現(xiàn)階段的性能評價方法主要集中于對算法的效果的衡量。2.4.2多目標進化算法的性能評價方法多目標進化算法的性能評價方法有很多，大體上可以分為兩類20，一類是評價算法的收斂性效果的，一類是評價解集的分布性效果的。下面分別對二者加以介紹。1. 算法收斂性評價所謂的收斂性，實際上是指算法的真實結果集與理論上的最優(yōu)結果集之間的趨近度，即理論上的pareto邊界和真正得到的pareto邊界之間的差距。收斂性的評價方法有很多種，如錯誤率、解集間覆蓋率、世代距離、最大出錯率等等。以解集間覆蓋率為例，該覆蓋率又稱為s指標(zitzler, 2000) 21，用來計算一個解集中被另一個解集中的個體支配的個體所占的比率。如式(3-1)所示。(3-1)對于收斂性的評價指標而言，可以通過指標值反映出算法間優(yōu)化效果的差異，但只局限于最優(yōu)解集中更優(yōu)解的數(shù)量，對于其空間上的特性不做相關考慮。2. 解集分布性評價在更多的算法應用領域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標空間中找到一組均勻的解集，以便做出不同的決策，如果解過于集中，則周圍的很多解事實上并沒有太大的意義，也不利于產(chǎn)生新個體，從而影響了種群的進化效果。分布性的評價方法也有很多，如空間評價方法、基于個體信息的評價方法、網(wǎng)格分布度評價方法等等。以空間評價方法為例，該方法又被稱為delta指標(schott, 1995) 22，用來計算解的分布信息的，如式(3-2)所示。 (3-2) 其中，對于分布性的評價指標而言，只關注結果集的分布特性，用以檢測算法是否被阻在一個很小的范圍之內進行搜索，而導致無法實現(xiàn)全局的最優(yōu)搜索的現(xiàn)象。由于收斂性評價與分布性評價的應用方向不同，因而在比較算法的時候，多會綜合兩種評價后，對算法的性能得出適當?shù)慕Y論。2.4.3現(xiàn)有性能評價體系的特點分析現(xiàn)有的性能評價體系可以分為兩種形式22：1. 理論證明理論證明即是對算法的復雜度、收斂性等進行求解和比較，即通過理論的分析得出正確的結論。但是由于多目標進化算法是一門新興的學科，多目標進化計算的理論基礎尚未成熟，算法收斂性的理論證明對有限時間內的收斂性分析較少，而時間無窮大的收斂性并沒有工程實際的應用價值。因此從理論上來證明算法的優(yōu)劣并不常用，也較難實現(xiàn)正確的評估。2. 實驗比較分析實驗比較分析是指通過對優(yōu)化算例的結果和結果的各種指標進行比較，驗證新算法與已存在的算法之間的性能差別。這種基于解決實際算例進行評價的方法具有一定的局限性，很難得出某種算法一定比另外一種更優(yōu)的結論，其結論的說服力也不夠。但是，由于這種方法可以簡單直觀的反映出算法的一些特性，所以在分析算法性能領域的應用十分廣泛。因此，現(xiàn)有的性能評價體系從使用范圍上講，是基于實驗比較分析來實現(xiàn)的。2.5本章小結 本章首先介紹了多目標進化算法的基本概念和原理。然后著重介紹了多目標進化算法的關鍵技術，現(xiàn)代多目標進化算法正是在這些方面存在差異，也是判斷算法之間性能優(yōu)劣的出發(fā)點。第三部分給出了多目標進化算法的一般流程，這是所有算法的原型，不同算法都是在此基礎上做出改動，了解此框架是學習其他算法的基礎。最后簡單介紹了算法的性能評價體系，為幾種算法比較的方案提供依據(jù)，得出基于實驗的方法是可行的，本文將在第三章利用這一思想來試驗nsga-和mogls兩種算法的優(yōu)劣。第三章 優(yōu)化算例及分析3.1 nsga-和mogls算法3.1.1帶精英策略的非支配排序的遺傳算法（nsga-）在nsga 中, 同一個小生境內的個體適應度共享, 從而降低該小生境內個體的競爭力, 防止種群在收斂過程中陷入局部最優(yōu), 實現(xiàn)種群多樣性。首先, 對種群內個體按非劣性排序, 為獲得的pareto 最優(yōu)解賦予相同的適應度; 其次, 根據(jù)goldberg和deb等23提出的共享方法, 按式(2-3) 和式( 2-4) 計算出每一個pareto 最優(yōu)解的小生境數(shù), 將該個體原適應度除以小生境數(shù),就得到它的共享適應度。這樣, 處于同一個pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應度也不同。 (2-3)其中, 表示個體 與個體 的距離, 是同一小生境中個體間的最大允許距離, 表示距離為時的共享函數(shù)值。其中, ( 2-4) 表示個體i 的小生境數(shù)。雖然非支配排序遺傳算法（nsga）在許多問題上得到了應用，但仍存在一些問題，如計算復雜度較高，需要指定共享半徑，易丟失已經(jīng)得到的滿意解。nsga-針對以上的缺陷通過以下三個方面進行了改進：(1)提出了快速非支配排序法，在選擇運算之前，根據(jù)個體的非劣解水平對種群分級。首先將當前的所有的非劣解個體劃為同一等級，令其等級為；然后將這些個體從種群中移出，在剩余個體中尋找出新的非劣解，再令其等級為；重復上述過程，直至種群中所有個體都被設定相應的等級。具體方法與nsga的快速非支配排序方法不同，nsga-對于每個個體都設有以下兩個參數(shù)和，為在種群中支配個體的解個體的數(shù)量，為被個體所支配的解個體的集合。首先，找到種群中所有的個體，將它們存入當前集合，然后對于當前集合的每個個體，考察它所支配的個體集,將集合中的每個個體的減去1，即支配個體的解個體數(shù)減1，如果則將個體存入另一個集。最后，將作為第一級非支配個體集合，并賦予該集合內個體一個相同的非支配序，然后繼續(xù)對作上述分級操作并賦予相應的非支配序，直到所有個體都被分級。如此操作降低了算法的計算復雜度。由原來的降到，其中，為目標函數(shù)個數(shù)，為種群大小。(2)提出了擁擠度和擁擠度比較算子，代替了需要指定共享半徑的適應度共享策略，并在快速排序后的同級比較中作為勝出標準，使準pareto域中的個體能擴展到整個域，并均勻分布，保持了種群的多樣性。擁擠度的概念：擁擠度是指在種群中的給定點的周圍個體的密度，計算上要考慮個體周圍包含本身但不包含其他個體的最小正方形，如下圖，個體的聚集距離是。為了計算每個個體的聚集距離，需要對群體按每個子目標函數(shù)值進行排序，在本算法中，若群體規(guī)模為，最極端情況下，對個子目標分別進行排序的時間復雜度為。從圖中可以看出值較小時，該個體周圍就比較擁擠，那么這幾個個體的適應度就要降低，使得分布比較分散的解能保留下的幾率加大。擁擠度比較算子：為了維持種群的多樣性，需要一個比較擁擠度的算子以確保算法能夠收斂到一個均勻分布的pareto面上。由于經(jīng)過了排序和擁擠度計算，群體中每個個體都得到了兩個屬性：非支配序和擁擠度，則定義偏序關系（）：當滿足條件，或滿足且時，定義。即如果兩個個體的非支配排序不同，取排序號較小的個體；如果兩個個體在同一級，取周圍較不擁擠的個體。(3)引入精英策略，擴大采樣空間。將父代種群與其產(chǎn)生的子代種群組合，共同競爭產(chǎn)生下一代種群，有利于保持父代中的優(yōu)良個體進入下一代，并通過對種群中所有個體的分層存放，使得最佳個體不會丟失，迅速提高種群水平。nsga-算法的主流程：首先隨即初始化一個父代種群，并將所有個體按非支配關系排序，且指定一個適應度值。然后采用選擇、交叉、變異算子產(chǎn)生下一代種群，大小也為，完成第一代進化。在產(chǎn)生新種群后，將與其父代種群合并組成，此時種群大小為。然后進行非支配排序，產(chǎn)生一系列非支配集并計算擁擠度，通常選擇前個個體組成，滿足且。在上圖中，由于子代和父代個體都包含在中，則經(jīng)過非支配排序以后的非支配集中包含的個體是中最好的，所以先將放入新的父代種群中。如果的大小小于，則繼續(xù)向中填充，直到添加到時種群大小超出，對中的個體進行擁擠度排序，取前個個體。使個體數(shù)量達到。然后通過遺傳算子產(chǎn)生新的子代種群。當排序產(chǎn)生的非支配集的個體數(shù)目足夠填充時，就不必再繼續(xù)對剩下的部分排序了。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。算法流程圖：圖3-1 nsga-的算法流程3.1.2mogls在mogls中，局部搜索過程應用于通過遺傳操作所獲得每一個解。這種算法應用在適應度評價功能上應用一種計算權值和的方式，即當一對父代種群被選擇通過交叉變異去獲得新解時使用這個功能。局部搜索過程應用于新解而最大限度地發(fā)揮它的適應度的效率24。這個算法的一大典型特性是無論何時選擇一組父代種群都要指定權值效率。每個解通過不同的權值矢量執(zhí)行。另一個特點是在局部搜索的過程中不需要計算當前種群的所有鄰域解，只有少部分鄰域解被檢驗避免在這個算法中消耗過多的所有可行解的計算時間。多目標遺傳局部搜索算法試圖尋找多目標最有問題所有的非支配解，如果在一個多目標問題中一個解不被其他解支配，它叫做非劣解，一個多目標問題有許多非劣解。雜交算法的目的不是確定一個單一的最終解，而是試圖尋找這個多目標問題所有符合約束條件的最優(yōu)解。當我們應用ga算法解決多目標問題時，需要評價每個解的適應