本科畢業(yè)設(shè)計多目標(biāo)進(jìn)化算法及應(yīng)用預(yù)計

1、華北電力大學(xué)畢業(yè)設(shè)計摘 要 在最近二十年，作為一類新興的優(yōu)化技術(shù)，多目標(biāo)進(jìn)化算法吸引了極大關(guān)注，許多學(xué)者提出了不同的算法，多目標(biāo)進(jìn)化算法已經(jīng)成為處理多目標(biāo)工程設(shè)計和科學(xué)研究問題的重要方法。許多moea的方面被廣泛地調(diào)研，然而一些問題仍然沒有被很好地受到關(guān)注。例如，隨著這類算法的快速發(fā)展，對算法之間性能進(jìn)行比較變得越來越重要。本文分析總結(jié)了兩種目前流行的所目標(biāo)進(jìn)化算法的基本原理，并通過算例來比較它們的性能。本文主要工作內(nèi)容如下：1. 簡要回顧了多目標(biāo)進(jìn)化算法的發(fā)展歷史，按照算法原理與進(jìn)化模式將算法分類。2. 簡述多目標(biāo)問題及進(jìn)化算法的相關(guān)技術(shù)，詳細(xì)分析了nsga-ii算法和mogls算法。3.

2、分別利用nsga-ii算法和mogls算法對算例進(jìn)行求解，并用c指標(biāo)對兩種算法的結(jié)果進(jìn)行評價，得出它們各自的優(yōu)缺點。多目標(biāo)問題仍向算法設(shè)計，呈現(xiàn)和執(zhí)行提出挑戰(zhàn)。不斷變化的多目標(biāo)問題很少被考慮到它的時變特性，對此有效的多目標(biāo)進(jìn)化算法很罕見，多目標(biāo)進(jìn)化算法的結(jié)合量計算和有區(qū)別的進(jìn)化還始終停留在初級階段。多目標(biāo)進(jìn)化算法的應(yīng)用應(yīng)該在未來不斷地延續(xù)，moea的理論分析比它本身更復(fù)雜而且應(yīng)該通過主要從事計算機(jī)和數(shù)學(xué)研究人員的努力工作來解決。關(guān)鍵詞：多目標(biāo)優(yōu)化，進(jìn)化算法，適應(yīng)度計算，精英保留，局部搜索 abstractin the past two decades, as a new subject， mu

3、lti-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 extensive

4、ly 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

5、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 mo

6、gls 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 desi

7、gn, 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 t

8、he 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 sea

9、rch 目 錄摘 要 .abstract.第1章 緒 論11.1究背景及意義11.2多目標(biāo)進(jìn)化算法的研究現(xiàn)狀21.3本文研究內(nèi)容4第2章 多目標(biāo)進(jìn)化算法62.1 多目標(biāo)優(yōu)化基本概念62.1.1多目標(biāo)優(yōu)化問題描述62.2多目標(biāo)遺傳算法設(shè)計的關(guān)鍵技術(shù)72.2.1適應(yīng)值設(shè)計72.2.2維持群體多樣性72.2.3精英保留策略92.3 nsga-和mogls算法12!異常的公式結(jié)尾2.3.2mogls142.4本章小結(jié)11附 錄26致 謝33第3章 優(yōu)化算例及分析303.1多目標(biāo)遺傳算法的性能評價20 3.3.1性能評價指標(biāo)20 3.3.2測試函數(shù)及其設(shè)計253.2二級標(biāo)題 353.3二級標(biāo)題 403.

10、3.1三級標(biāo)題40 3.3.2三級標(biāo)題45第 4 章 總結(jié)304.1二級標(biāo)題 304.2二級標(biāo)題 354.3二級標(biāo)題 404.3.1三級標(biāo)題40 4.3.2三級標(biāo)題45參考文獻(xiàn)50附 錄 51致 謝 52第1章 緒 論許多科學(xué)研究和工程實踐中遇到的優(yōu)化問題，通常需要綜合考慮多方面因素，這就要求在解決問題時同時對多個目標(biāo)進(jìn)行優(yōu)化，這樣的問題被稱為多目標(biāo)優(yōu)化問題(multi-objective optimization problem, mop)，它們有許多沖突的目標(biāo)。有時目標(biāo)之間是相輔相成、互相促進(jìn)的，但更多的時候，目標(biāo)之間是相互矛盾、此消彼長的。因此在絕大多數(shù)情況下，若想達(dá)到總目標(biāo)的最優(yōu)，就需

11、要對各個目標(biāo)進(jìn)行綜合考慮、折中處理，所得到的解是一組基于pareto最優(yōu)性概念的非劣解集1，所以如何進(jìn)行綜合與折中就成為解決問題的關(guān)鍵。1.1研究背景及意義生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得品種不斷的到改良，這種生命現(xiàn)象叫做進(jìn)化。進(jìn)化算法(evolutionary algorithm, ea)是一種通過模擬生物進(jìn)化規(guī)律來進(jìn)行選擇與變化的隨機(jī)搜索算法，起源于20 世紀(jì)50 年代末，現(xiàn)有的代表性進(jìn)化方法有遺傳算法(genetic algorithm, ga)、進(jìn)化規(guī)劃(evolutionary programming, ep)和進(jìn)化策略(evolutionstrategy, es)

12、等幾種方法2。進(jìn)化算法非常適用于于求解高度復(fù)雜的非線性問題，并且由于這類算法具有通用性，因而被廣泛地應(yīng)用于單個目標(biāo)的復(fù)雜系統(tǒng)優(yōu)化問題。然而，人們在求解現(xiàn)實世界許多優(yōu)化問題時，通常不追求單一目標(biāo)的最優(yōu)性，這就要求在解決問題時同時對多個目標(biāo)進(jìn)行優(yōu)化和權(quán)衡，有時目標(biāo)之間是相輔相成、互相促進(jìn)的，但更多的時候，目標(biāo)之間是相互矛盾、此消彼長的，這樣的問題被稱為多目標(biāo)優(yōu)化問題(multi-objective optimization problem, mop)，大多數(shù)工程和科學(xué)問題是多目標(biāo)最優(yōu)問題。多目標(biāo)優(yōu)化問題的各目標(biāo)之間通過決策變量相互制約,對其中一個目標(biāo)優(yōu)化必須以其它目標(biāo)作為代價,而且各目標(biāo)的單位又往

13、往不一致,因此很難客觀地評價多目標(biāo)問題解的優(yōu)劣性。例如,在設(shè)計一座橋梁時,我們一方面希望建設(shè)橋梁的費用最小,另一方面希望橋梁具有最大的安全性。與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別在于,多目標(biāo)優(yōu)化問題的解不是唯一的,而是存在一個最優(yōu)解集合,集合中元素稱為pareto 最優(yōu)或非劣最優(yōu)(non-dominance) 。求解它們需要用不同于單目標(biāo)優(yōu)化的數(shù)學(xué)工具,甚至最優(yōu)的含義也發(fā)生了變化。由于它們有許多沖突的目標(biāo)，因此若想達(dá)到總目標(biāo)的最優(yōu)，就需要對各個目標(biāo)進(jìn)行綜合考慮、折中處理，所以如何進(jìn)行綜合與折中就成為解決問題的關(guān)鍵。多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorith

14、m, moea)就是一類可以有效解決這種問題的優(yōu)化技術(shù)3。它的主要思想是將進(jìn)化算法的概念引入到多目標(biāo)優(yōu)化領(lǐng)域，對多目標(biāo)優(yōu)化問題同樣采用進(jìn)化操作方式，但算法由單目標(biāo)優(yōu)化問題求取一個最優(yōu)解，轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問題中求取一個最優(yōu)解集，該解集稱為pareto最優(yōu)解集。最優(yōu)解集中的每個解，理論上都是“最優(yōu)解”，而在實際應(yīng)用中，可以根據(jù)決策需要選擇其中一個解作為最終決策方案，實現(xiàn)最優(yōu)化的目的。多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，理論與算法并不完善，尚處于發(fā)展階段。然而，它對工程項目具有重要的實踐意義，因此在過去的十多年間涌現(xiàn)出許多新的改進(jìn)算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標(biāo)進(jìn)化算法。而對算法性能進(jìn)行

15、比較和評價就成為一個重要的核心問題，引起了諸多學(xué)者的研究興趣。1.2多目標(biāo)進(jìn)化算法的研究現(xiàn)狀優(yōu)化問題一直是倍受人們關(guān)注的問題，自1950 年以來,運籌學(xué)研究人員已經(jīng)建立了許多方法解決mop。在專業(yè)文獻(xiàn)中,有許多數(shù)學(xué)規(guī)劃技巧解決mop ,如多目標(biāo)加權(quán)法、分層序列法、約束法、目標(biāo)規(guī)劃法等。遺傳算法自出現(xiàn)以來在許多領(lǐng)域得到了廣泛的應(yīng)用，在解決簡單的單目標(biāo)優(yōu)化問題方面取得了很好的成果，但面對復(fù)雜的多目標(biāo)優(yōu)化問題，傳統(tǒng)的遺傳算法就顯得力不從心。例如在現(xiàn)代能源系統(tǒng)生產(chǎn)過程參數(shù)的優(yōu)化4設(shè)計中經(jīng)常會遇到多目標(biāo)函數(shù)的優(yōu)化問題，使用經(jīng)典的多目標(biāo)優(yōu)化方法通常把多個目標(biāo)函數(shù)整合成單目標(biāo)，將問題轉(zhuǎn)變?yōu)閱文繕?biāo)優(yōu)化問題，然

16、后采用單目標(biāo)的優(yōu)化技術(shù)求解。但這些方法存在：只能得到一個解；多個目標(biāo)函數(shù)之間量綱不同難以統(tǒng)一；加權(quán)值的分配帶有較強的主觀性；加權(quán)的目標(biāo)函數(shù)之間通過決策變量相互制約，最終優(yōu)化目標(biāo)僅為各目標(biāo)之和，各目標(biāo)的優(yōu)化進(jìn)度不可操作等缺點。這是因為傳統(tǒng)數(shù)學(xué)規(guī)劃方法存在一些缺陷,例如有些方法對pareto 前沿比較敏感,當(dāng)pareto 前沿是凹的或者不連續(xù)時,這些方法失效;有些方法要求目標(biāo)函數(shù)和約束條件可微;有些方法每次運行只產(chǎn)生一個解,求多個解時需要運行多次,效率較低。進(jìn)化多目標(biāo)優(yōu)化始于1967年，此后眾多的研究人員通過對遺傳算法進(jìn)行改造，相繼提出了多種用于解決多目標(biāo)優(yōu)化問題的遺傳算法，如基于向量評估的遺傳算

17、法(vega) 5，小組決勝遺傳算法(npga) 6，非支配排序遺傳算法(nsga)及其改進(jìn)算法nsga-ii7等. 其中nsga的改進(jìn)算法nsga-ii是帶有精英策略的非支配排序遺傳算法，改進(jìn)了先前算法的不足之處，提高了算法的運算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。自scharfer提出vega起，多目標(biāo)進(jìn)化算法的發(fā)展經(jīng)歷了由基于單目標(biāo)子群體優(yōu)化的算法到基于pareto最優(yōu)性指導(dǎo)的分級策略與適應(yīng)值共享策略算法的發(fā)展歷程。按照算法原理與進(jìn)化模式劃分，現(xiàn)有多目標(biāo)進(jìn)化算法可分如下四大類：第一類算法是早期基于單目標(biāo)群體優(yōu)化的moga。這類算法通過加權(quán)或劃分子群體進(jìn)化等方法將mop轉(zhuǎn)化為不同的

18、sop，然后借助現(xiàn)有單目標(biāo)遺傳算法對轉(zhuǎn)化后的sop進(jìn)行求解，最后對進(jìn)化獲得的解進(jìn)行分析，篩選出非劣解集。由于這類算法的設(shè)計思想是基于單目標(biāo)遺傳算法的進(jìn)化策略，因此它的優(yōu)點是算法容易實現(xiàn)；其不足是，基于單目標(biāo)子群體優(yōu)化的算法很難搜索到嚴(yán)格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點。代表算法有vega、wbga、dm等。ishibuchi、murata等人1996年提出的mogls是在隨機(jī)權(quán)策略的wbga中引入局部搜索的改進(jìn)算法，其本質(zhì)屬于這類算法8。第二類算法是基于goldberg提出的適應(yīng)值分級和共享策略的多目標(biāo)遺傳算法。這類算法在適應(yīng)值設(shè)計中鼓勵非劣解等級優(yōu)先個體和同一等級內(nèi)較為稀

19、疏個體以較大概率出現(xiàn)在后代群體中。由于這類算法是基于pareto概念的moga，因此，它的優(yōu)點是可以通過單次優(yōu)化獲得一組靠近真實非劣解前沿的非劣解集；但由于算法未考慮進(jìn)化過程中精英個體的保留，因此解的收斂速度及收斂性能不夠穩(wěn)健。代表算法有moga、nsga和npga等。第三類算法是由第二類算法發(fā)展起來的精英保留策略moga。這類算法通過在進(jìn)化過程中引入外部伴隨群體對群體中的精英個體加以保留，同時采用更加成熟的適應(yīng)值設(shè)計策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。這類算法的不足之處是，算法進(jìn)化模式單一、局部搜索性能欠佳，之所以存在這些不足，主要是因為這類算法大多由第二類算法

20、改進(jìn)得到，因此進(jìn)化模式不可能完全擺脫先前的算法框架，并且遺傳算法的進(jìn)化原理決定了它不可能具有性能較高的局部搜索能力。代表算法有npga-ii、nsga-ii、paes和spea等9。第四類算法是采用其他搜索算法策略改進(jìn)的moea。這類算法由于采用的進(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ā)展才開始活躍起來。這類算法由于群體規(guī)模適中，因此算法復(fù)雜性相對較低，而且由于算法局部搜索性能優(yōu)越，因

21、此常常可以與現(xiàn)有的moga結(jié)合，形成新的精英算法。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)、又能維持群體多樣性，因此，在算法設(shè)計時往往設(shè)置了許多控制參數(shù)對算法性能進(jìn)行調(diào)整，這又導(dǎo)致在求解問題時常常需要借助大量試驗計算分析確定進(jìn)化參數(shù)，因此算法性能不夠穩(wěn)健。代表算法有mose、mopso等10。除了上述四類算法外，一些學(xué)者在演化策略中引入偏好分級或適應(yīng)值分享機(jī)制獲取滿意解。但由于這些方法不能通過幾次運行獲得穩(wěn)定的非劣解集，且算法復(fù)雜性較高，因此這類研究不是多目標(biāo)進(jìn)化算法研究的主流方向。而考慮偏好關(guān)系對遺傳進(jìn)化的影響，大多是用模糊集方法進(jìn)行偏好信息的處理，而進(jìn)一步利用偏好對

22、進(jìn)化進(jìn)行指導(dǎo)或通過進(jìn)化引導(dǎo)偏好的交互式多目標(biāo)進(jìn)化算法還僅僅處于概念研究階段，距算法實現(xiàn)尚有較大差距。多目標(biāo)遺傳算法的研究一直是這類算法研究的主流方向：盡管遺傳算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他進(jìn)化策略或啟發(fā)式局部搜索算法好的局部搜索性能，因此，以進(jìn)化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進(jìn)化策略局部搜索的優(yōu)勢，獲得高性能的多目標(biāo)優(yōu)化算法，成為多目標(biāo)進(jìn)化算法研究的潛在發(fā)展方向。1.3本文研究內(nèi)容 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類11：前決策（先驗式）、后決策（后驗式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時間先后劃分的。其

23、中，后決策是最常用的技術(shù)，即算法終止時提供給用戶一組最優(yōu)解。目前絕大多數(shù)多目標(biāo)進(jìn)化算法是排序選擇法和后決策技術(shù)類型的。spea/spea2 (zitzler & thiele 2001)和nsga/nsga-ii (srinivas & deb 2002)兩類算法目前的應(yīng)用更廣泛，也更具有代表性。由于本文需要對多目標(biāo)進(jìn)化算法的結(jié)構(gòu)進(jìn)行深入的分析，所以需要在此選擇一個代表性的算法，通過該算法的簡介，來描述一下多目標(biāo)進(jìn)化算法的一些基本概念和工作原理。本文將以nsga-ii算法和mogls（multi-objective genetic lcal search）算法為例，通過算例和指定的函數(shù)指標(biāo)來分

24、析比較它們各自性能的優(yōu)缺點。nsga-ii算法首先隨機(jī)產(chǎn)生一個初始種群，對種群通過采用輪盤賭的方式選擇、交叉和變異操作獲得新的種群，將種群中的個體構(gòu)造其pareto 邊界集，并根據(jù)個體間的聚集距離，建立偏序關(guān)系，最終從偏序關(guān)系中選擇原始種群規(guī)模大小的個體，組成新的種群，完成了一次進(jìn)化操作。由此可見，對于多目標(biāo)進(jìn)化算法而言，構(gòu)造pareto 邊界集和計算個體間的聚集距離是新的概念，也是絕大多數(shù)多目標(biāo)進(jìn)化算法共有的流程，這為之后提取算法公共流程方式的討論提供了基本的依據(jù)。mogls是ishibuchi和murata兩位學(xué)者提出的。最初的mogls是在遺傳進(jìn)化過程中，每代遺傳操作生成新個體后，對現(xiàn)有

25、群體中的所有個體進(jìn)行局部搜索；后來ishibuchi等人對局部搜索的步長選取、鄰域搜索效率做了進(jìn)一步研究后，將局部搜索過程僅應(yīng)用于當(dāng)前群體中的優(yōu)秀，顯著提高了算法效率，改進(jìn)后的算法可獲得與spea、nsga-ii相當(dāng)?shù)膬?yōu)化性能。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)的方法往往不能保證所得非劣解集分布的均勻性。第2章 多目標(biāo)進(jìn)化算法2.1 多目標(biāo)優(yōu)化基本概念2.1.1多目標(biāo)優(yōu)化

26、問題描述 多目標(biāo)問題( mop) 的一般描述為: 給定決策向量 , 它滿足下列約束: ( 2-1) ( 2-2)設(shè)有r 個優(yōu)化目標(biāo), 且這r 個優(yōu)化目標(biāo)是相互沖突的, 優(yōu)化目標(biāo)可表示為: 尋求, 使在滿足約束( 2-1) 和( 2-2) 的同時達(dá)到最小。2.1.2最優(yōu)性對于多目標(biāo)優(yōu)化問題, 由于其待優(yōu)化的各個子目標(biāo)一般是相互沖突的, 因此需要定義解個體間的優(yōu)劣關(guān)系, 以便對候選解進(jìn)行評價與取舍。本文采用廣泛使用的pareto 最優(yōu)性12定義。定義1 ( 個體的pareto 支配關(guān)系) 。設(shè)和是進(jìn)化群體中的任意兩個不同的個體,稱支配(dominate) ,則必須滿足下列二個條件:( 1) 對所有

27、的子目標(biāo), 不比 差, 即 ( k=1, 2, r) ; （2） 至少存在一個子目標(biāo),使比好。即, 使其中r 為子目標(biāo)的數(shù)量。此時稱 為非支配的( non- dominated), 為被支配的( dominated) 。表示為, 其中“”是支配關(guān)系。定義2( pareto 非支配集)。設(shè)有解集,若中的個體不被任何其它個體支配, 則是 中的非支配個體; 由 中的所有非支配個體構(gòu)成的子集稱為 的非支配集。即: 最優(yōu)性的含義為：是pareto最優(yōu)解，表示在整個解空間中，不存在這樣的解：某一個目標(biāo)比小的同時，保持其余個目標(biāo)值不大于x的目標(biāo)值。因此，滿足這種最優(yōu)性的“最優(yōu)解”往往不是單個解，而是一組滿足

28、上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱作非劣解集（pareto solutions set）或非受控解集(nondominated solutions set)；非劣解對應(yīng)的目標(biāo)值在目標(biāo)空間中稱為非劣點；最優(yōu)解集在優(yōu)化目標(biāo)空間構(gòu)成的分布稱作非劣解前沿。在決策和優(yōu)化問題中，最優(yōu)性取決于如何比較和排序候選解，及決策者的偏好結(jié)構(gòu)。從決策者的立場來看，一般認(rèn)為每對候選解具有以下比較關(guān)系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。由此才可以對每對解之間的優(yōu)劣比較進(jìn)行細(xì)致的區(qū)分13。2.2多目標(biāo)遺傳算法設(shè)計的關(guān)鍵技術(shù)2.2.1適應(yīng)值設(shè)計mop問題包含多個待優(yōu)化的子目標(biāo)，

29、通常eas用于多目標(biāo)優(yōu)化時必須考慮兩個關(guān)鍵問題：(1)為了保證朝pareto最優(yōu)集的方向搜索，如何實施適應(yīng)度賦值和選擇。(2)為了避免未成熟收斂和獲得均勻分布且范圍最廣的非劣解，如何保持群體的多樣性。在已有研究中，多目標(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)化。這種適應(yīng)值設(shè)計的遺傳算法通常需要在算法進(jìn)化過程中系統(tǒng)地對函數(shù)中的參數(shù)的權(quán)重值進(jìn)行調(diào)整，以便得到一組非劣解集。在進(jìn)化的每一代中參數(shù)呈現(xiàn)有規(guī)律

30、的變化，但在該代操作過程中保持不變，常見的進(jìn)化加權(quán)法，個體的評估使用確定的加權(quán)組合，所有個體都有一個適應(yīng)度值，保證了搜索方向朝最優(yōu)解邁進(jìn)。(2)基于目標(biāo)設(shè)計策略的算法，即基于準(zhǔn)則的策略，每當(dāng)個體選中后進(jìn)行復(fù)制時根據(jù)不同的目標(biāo)來決定是否被復(fù)制至配對池。此方法通過在不同進(jìn)化代之間更換優(yōu)化目標(biāo)每次優(yōu)化一個目標(biāo)，使算法群體每次運行得到一個非劣解，從而通過多次運行找到優(yōu)化問題的非劣解集。目前，常用的方法是在選擇階段根據(jù)概率來確定各子目標(biāo)的排序，該概率值由用戶確定或隨機(jī)產(chǎn)生。這種策略存在的問題是進(jìn)化結(jié)果容易偏向某些極端邊界解，并且對pareto最優(yōu)前端的非凸部敏感。(3)基于非劣解等級優(yōu)先概念的適應(yīng)值分配

31、策略由goldberg最先提出，后人大多在此基礎(chǔ)上進(jìn)行改進(jìn)，如將群體劃分為幾個有序的子群體。這類算法的適應(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ù)目。一般來說直接統(tǒng)計優(yōu)勝個體數(shù)目的操作方式簡單，在原理上一目了然。單目標(biāo)優(yōu)化中的目標(biāo)函數(shù)常與適應(yīng)度函數(shù)相同，但mop問題中的適應(yīng)度賦值和選

32、擇必須考慮幾個子目標(biāo)，moeas必須根據(jù)個體間的pareto優(yōu)勝關(guān)系和其他信息為個體確定適應(yīng)度值，這種適應(yīng)度值和每個目標(biāo)函數(shù)的具體大小沒有直接關(guān)系。另外，與單目標(biāo)優(yōu)化不同的是，在個體保持不變的條件下，同一個體在這一代和下一代的適應(yīng)值可能不相等。pareto優(yōu)勝關(guān)系是決定個體適應(yīng)度函數(shù)值的重要依據(jù)，很多moeas根據(jù)個體間的這種關(guān)系，將個體的適應(yīng)度函數(shù)值分成兩個層次，即劣解和非劣解，后者的適應(yīng)度值總是優(yōu)于前者。當(dāng)個體間沒有pareto優(yōu)勝關(guān)系時，其他形式的個體信息被用于確定適應(yīng)度函數(shù)值，其中個體密度值是利用最多的信息，并采用不同的方法估計個體密度值。基于pareto優(yōu)勝關(guān)系的選擇方法已經(jīng)被廣大研

33、究者采納，現(xiàn)已有多種基于pareto的適應(yīng)度賦值方案，其中基于種群個體級別排序的適應(yīng)度賦值方法是較常見的一種方法。多目標(biāo)問題與單目標(biāo)問題不同，它的優(yōu)劣性與支配關(guān)系并非定義目標(biāo)向量之間的那種整體有序關(guān)系，只是給出部分有序關(guān)系，因而種群的級別排序不具有唯一性。假設(shè)第代種群中的個體，在第代種群個體排序中的位置為，基于個體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個體進(jìn)行級別排序。(2)利用線性或非線性的插值方法在最低序號與最高序號之間進(jìn)行插值。(3)具有相同序號的個體進(jìn)行適應(yīng)度共享算子操作，即通過除以相同序號的個體數(shù)目得到新的適應(yīng)度值，另外，也可以給不同序號的個體分配固定不變的適應(yīng)度

34、值。2.2.2維持群體多樣性因為eas是并行地處理一組解，通過雜交和變異來搜索空間以尋找可能的最優(yōu)區(qū)域，通過選擇來搜索具有較高適應(yīng)度的個體。傳統(tǒng)的進(jìn)化算法在pareto最優(yōu)集上執(zhí)行多目標(biāo)搜尋，希望找出盡可能均勻分布的解集，因而個體的多樣性減少的很快，經(jīng)常收斂至單個解而丟失多個其他非劣解。在進(jìn)化過程中某些具有較高適應(yīng)度個體的大量復(fù)制造成高選擇壓力，使得個別具有更高適應(yīng)度的個體得不到遺傳的機(jī)會，甚至導(dǎo)致整個群體出現(xiàn)同解的現(xiàn)象15。如果單純從群體多樣性出發(fā)，群體規(guī)模應(yīng)該越大越好，但群體規(guī)模太大會帶來若干弊?。阂皇菑挠嬎阈蕘砜?，群體越大，導(dǎo)致其適應(yīng)度評估次數(shù)增加，引起計算量的增加，從而影響算法效能；

35、二是群體中個體生存下來的選擇概率大多采用和適應(yīng)度成比例的方法，當(dāng)群體中個體非常多時，少量適應(yīng)度很高的個體會被選擇而生存下來，大多數(shù)個體被淘汰，嚴(yán)重影響交叉操作。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進(jìn)化算法多樣性的途徑。進(jìn)化算法由于其進(jìn)化算子固有的隨機(jī)誤差，因而基于有限群體實施進(jìn)化時會出現(xiàn)收斂至某一個解。因為多目標(biāo)優(yōu)化的目的是得到一組在整個pareto曲面上盡可能均勻分布的一組解，因此必須在進(jìn)化過程中采取措施避免進(jìn)化結(jié)果收斂至單個解。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點，大多數(shù)moeas在當(dāng)代群體中維持多樣性是在選擇過程中結(jié)合了密度信息，即個體在其

36、鄰域范圍內(nèi)所占的密度越高被選擇復(fù)制的機(jī)會越小?，F(xiàn)有多目標(biāo)遺傳算法可根據(jù)統(tǒng)計概率密度估計的方法加以分類為如下三種策略來維持群體多樣性：(1)基于核函數(shù)的評價策略：基于核函數(shù)的評價策略主要通過計算以個體為“核”、群體中其他個體距離“核”的核函數(shù)之和，通過優(yōu)先保留核函數(shù)值較大的個體即較稀疏的解個體達(dá)到維持群體多樣性的目的。具體應(yīng)用時首先根據(jù)內(nèi)核函數(shù)來定義一個點的鄰域范圍，內(nèi)核函數(shù)采用至另一點的距離作為參數(shù)。每一個個體計算至其他個體的距離，通過內(nèi)核函數(shù)的映射后求和計算出值，該累加值代表了個體的密度估計。(2)基于鄰域解數(shù)目的評價策略：基于鄰域解數(shù)目的評價策略是以評價解為核心、包含一定數(shù)量鄰域解的鄰域半

37、徑為指標(biāo)，優(yōu)先保留鄰域半徑較大的個體即較稀疏的解個體。該策略主要考慮給定點至第個最近鄰居的距離，以便估計出其在鄰域內(nèi)的密度。(3)分區(qū)統(tǒng)計數(shù)目策略：分區(qū)統(tǒng)計數(shù)目策略是將目標(biāo)空間劃分成一定比例的區(qū)域，通過統(tǒng)計個體所在區(qū)域中鄰域解數(shù)目來確定個體被保留的概率鄰域解數(shù)目越大，被保留概率越小。該方法采用一個網(wǎng)格來定義空間上的鄰居關(guān)系，個體的密度只要通過簡單地統(tǒng)計同一網(wǎng)格內(nèi)的個體數(shù)目即可，這種網(wǎng)絡(luò)可以是固定的，也可以根據(jù)當(dāng)前群體進(jìn)行自適應(yīng)調(diào)整。多目標(biāo)進(jìn)化算法與單目標(biāo)進(jìn)化算法類似，為了提高群體多樣性，在算法過程中盡量采用小生境（niche）共享技術(shù)，使得在一個群體內(nèi)可以形成在多目標(biāo)問題上分布均勻的非劣最優(yōu)解

38、集。具有相同pareto級別序號的解個體在實施共享適應(yīng)度值后，還必須按解的目標(biāo)向量之間的空間距離進(jìn)行小生境規(guī)模調(diào)整。當(dāng)兩個解的目標(biāo)向量之間的空間距離小于某一預(yù)定值時，相應(yīng)解的小生境規(guī)模就必須進(jìn)行調(diào)整。此外，還有同時基于決策向量空間與目標(biāo)向量空間的混合共享技術(shù)，共享問題的關(guān)鍵是如何確定共享參數(shù)，的選擇將會影響算法的性能，而適應(yīng)度共享效果則共同取決于和種群大小16。2.2.3精英保留策略遺傳算法是基于隨機(jī)進(jìn)化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標(biāo)遺傳算法大都引入了精英保留策略。現(xiàn)有算法中精英策略的實現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過確定性的選擇方法在混合群體中選擇后代，

39、而不是采用變化之后的配對池來替換舊群體，增大了精英個體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。另一種實現(xiàn)方式是采用獨立于進(jìn)化群體的伴隨群體，即使用帶有所謂的檔案（archive）的方式，保留與更新算法進(jìn)化過程中搜索到的非劣解集來維護(hù)當(dāng)代群體中的滿意群體，使其能夠復(fù)制到下一代，伴隨群體僅作為一個外部存儲集，獨立于進(jìn)化過程的優(yōu)化操作17。由于內(nèi)存資源的限制，以上兩種最優(yōu)個體保留策略必須確定哪些個體作為最優(yōu)個體加以保留。通常采用優(yōu)勝準(zhǔn)則來確定最優(yōu)個體。如果使用伴隨群體的方式，則伴隨群體中包括當(dāng)前的近似pareto集，即伴隨群體中受控的個體被移去。但是使用優(yōu)勝關(guān)系比較的方法有時也存在問題，如對某些

40、連續(xù)型問題所對應(yīng)的pareto集可能包含無窮多個解，因此需要補充其他的信息知識來減小所存儲的個體數(shù)目。這些信息包括密度信息，個體進(jìn)入伴隨群體所需時間。moeas的最優(yōu)個體大多利用優(yōu)勝關(guān)系和密度兩者的組合來進(jìn)行挑選，最優(yōu)個體保存在每代的伴隨群體中。更新的算法研究表明，如果同時采用這兩種精英策略，可以進(jìn)一步提高算法的搜索性能與收斂效果。2.3遺傳算法的一般流程holland教授提出的遺傳算法，現(xiàn)在一般稱為簡單遺傳算法或基本遺傳算法18，其基本流程如下圖：圖2-1遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問題空間的參數(shù)，因此在算法開始進(jìn)行之前，首先要選擇合適的編碼方式對待優(yōu)化的參數(shù)進(jìn)行

41、編碼。通常采用二進(jìn)制編碼，將參數(shù)轉(zhuǎn)換成為和組成的數(shù)字串。 (2) 產(chǎn)生初始種群：隨機(jī)地產(chǎn)生一個由個個體組成的種群，該種群代表一些可能解的集合。遺傳算法的任務(wù)是種群出發(fā)，模擬生物進(jìn)化的過程進(jìn)行優(yōu)勝劣汰，最后得出滿足優(yōu)化要求的種群和個體。 (3) 設(shè)計適應(yīng)度函數(shù)：把問題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度函數(shù)計算種群中的每個個體的適應(yīng)度，為種群進(jìn)化的選擇提供依據(jù)。 (4) 優(yōu)化準(zhǔn)則：也可稱作終止條件，是用來判斷算法是否可以終止的標(biāo)準(zhǔn)。可以設(shè)定進(jìn)化的最大代數(shù)，當(dāng)進(jìn)化到最大代數(shù)時，算法終止運行。也可以設(shè)定期望的適應(yīng)度函數(shù)值，只有當(dāng)種群中存在個體能達(dá)到期望值時，算法才可以結(jié)束。通常情況下，這兩

42、種方法同時作為優(yōu)化準(zhǔn)則使用。(5) 選擇(復(fù)制)操作:按一定概率從群體中選擇個體，作為雙親用于繁殖后代，產(chǎn)生新的個體。在此操作中，適應(yīng)于生存環(huán)境的優(yōu)良個體將有更多的機(jī)會繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。(6) 交叉操作:隨機(jī)地選擇用于繁殖的每一對個體的同一基因位，將其染色體在此基因位斷開并相互交換。(7) 變異操作:以一定的概率從群體中選擇若干個個體。對于選中的個體，隨機(jī)選擇某一位進(jìn)行取反操作。對產(chǎn)生的新一代群體重新進(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)度不再提高，則迭代過

43、程收斂，算法結(jié)束。遺傳算法的選擇和交叉算子賦予了它強有力的搜索能力，變異算子則使算法能搜索到問題解空間的每一個點，以確保算法能達(dá)到全局最優(yōu)。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種類。對一個需要進(jìn)行優(yōu)化計算的實際應(yīng)用問題，一般可以按照上述步驟來構(gòu)造求解該問題的遺傳算法。由上述步驟可以看出，構(gòu)造遺傳算法時需要考慮的兩個主要問題是可行解的編碼方法和遺傳算子的設(shè)計，這也是設(shè)計遺傳算法的兩個關(guān)鍵步驟。2.4算法性能評價2.4.1多目標(biāo)進(jìn)化算法性能評價的研究現(xiàn)狀多目標(biāo)遺傳算法的性能評價與傳統(tǒng)優(yōu)化算法及單目標(biāo)遺傳算法的性能評價有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過梯度下降速

44、度進(jìn)行評價，并且可以通過嚴(yán)格的數(shù)學(xué)證明分析其收斂性能；單目標(biāo)遺傳算法可以采用基于模式定理或基于馬爾可夫隨機(jī)過程理論的證明分析其收斂性，盡管這類證明研究還很初步。然而在對多目標(biāo)進(jìn)化算法的性能進(jìn)行評價時，一般需要考慮到三個較為重要的因素19：算法的效率、算法的效果，以及算法的魯棒性。算法的效率是指算法自身的時間復(fù)雜度和空間復(fù)雜度，也即算法運算時間的長短和資源消耗的多少；算法的效果是指算法求得的解集的質(zhì)量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應(yīng)用范圍和穩(wěn)定性，也即是否對多種問題都有很好的求解能力、是否求解問題時總是相對穩(wěn)定的。而從現(xiàn)階段的研究來看，人們更關(guān)注的是，算法結(jié)果是否

45、為高質(zhì)量的結(jié)果，而對于另外兩個因素相對要求并不高，而且對于算法的效率來說，涉及到的是經(jīng)典的算法復(fù)雜度理論，已經(jīng)有很完善的泛化體系對其進(jìn)行評價了，無需在多目標(biāo)進(jìn)化算法領(lǐng)域?qū)ζ湓龠M(jìn)行專門的研究。所以現(xiàn)階段的性能評價方法主要集中于對算法的效果的衡量。2.4.2多目標(biāo)進(jìn)化算法的性能評價方法多目標(biāo)進(jìn)化算法的性能評價方法有很多，大體上可以分為兩類20，一類是評價算法的收斂性效果的，一類是評價解集的分布性效果的。下面分別對二者加以介紹。1. 算法收斂性評價所謂的收斂性，實際上是指算法的真實結(jié)果集與理論上的最優(yōu)結(jié)果集之間的趨近度，即理論上的pareto邊界和真正得到的pareto邊界之間的差距。收斂性的評價方

46、法有很多種，如錯誤率、解集間覆蓋率、世代距離、最大出錯率等等。以解集間覆蓋率為例，該覆蓋率又稱為s指標(biāo)(zitzler, 2000) 21，用來計算一個解集中被另一個解集中的個體支配的個體所占的比率。如式(3-1)所示。(3-1)對于收斂性的評價指標(biāo)而言，可以通過指標(biāo)值反映出算法間優(yōu)化效果的差異，但只局限于最優(yōu)解集中更優(yōu)解的數(shù)量，對于其空間上的特性不做相關(guān)考慮。2. 解集分布性評價在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過于集中，則周圍的很多解事實上并沒有太大的意義，也不利于產(chǎn)生新個體，從而影響了種群的進(jìn)

47、化效果。分布性的評價方法也有很多，如空間評價方法、基于個體信息的評價方法、網(wǎng)格分布度評價方法等等。以空間評價方法為例，該方法又被稱為delta指標(biāo)(schott, 1995) 22，用來計算解的分布信息的，如式(3-2)所示。 (3-2) 其中，對于分布性的評價指標(biāo)而言，只關(guān)注結(jié)果集的分布特性，用以檢測算法是否被阻在一個很小的范圍之內(nèi)進(jìn)行搜索，而導(dǎo)致無法實現(xiàn)全局的最優(yōu)搜索的現(xiàn)象。由于收斂性評價與分布性評價的應(yīng)用方向不同，因而在比較算法的時候，多會綜合兩種評價后，對算法的性能得出適當(dāng)?shù)慕Y(jié)論。2.4.3現(xiàn)有性能評價體系的特點分析現(xiàn)有的性能評價體系可以分為兩種形式22：1. 理論證明理論證明即是對算

48、法的復(fù)雜度、收斂性等進(jìn)行求解和比較，即通過理論的分析得出正確的結(jié)論。但是由于多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，多目標(biāo)進(jìn)化計算的理論基礎(chǔ)尚未成熟，算法收斂性的理論證明對有限時間內(nèi)的收斂性分析較少，而時間無窮大的收斂性并沒有工程實際的應(yīng)用價值。因此從理論上來證明算法的優(yōu)劣并不常用，也較難實現(xiàn)正確的評估。2. 實驗比較分析實驗比較分析是指通過對優(yōu)化算例的結(jié)果和結(jié)果的各種指標(biāo)進(jìn)行比較，驗證新算法與已存在的算法之間的性能差別。這種基于解決實際算例進(jìn)行評價的方法具有一定的局限性，很難得出某種算法一定比另外一種更優(yōu)的結(jié)論，其結(jié)論的說服力也不夠。但是，由于這種方法可以簡單直觀的反映出算法的一些特性，所以在分析算

49、法性能領(lǐng)域的應(yīng)用十分廣泛。因此，現(xiàn)有的性能評價體系從使用范圍上講，是基于實驗比較分析來實現(xiàn)的。2.5本章小結(jié) 本章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和原理。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，現(xiàn)代多目標(biāo)進(jìn)化算法正是在這些方面存在差異，也是判斷算法之間性能優(yōu)劣的出發(fā)點。第三部分給出了多目標(biāo)進(jìn)化算法的一般流程，這是所有算法的原型，不同算法都是在此基礎(chǔ)上做出改動，了解此框架是學(xué)習(xí)其他算法的基礎(chǔ)。最后簡單介紹了算法的性能評價體系，為幾種算法比較的方案提供依據(jù)，得出基于實驗的方法是可行的，本文將在第三章利用這一思想來試驗nsga-和mogls兩種算法的優(yōu)劣。第三章 優(yōu)化算例及分析3.1 nsga-和

50、mogls算法3.1.1帶精英策略的非支配排序的遺傳算法（nsga-）在nsga 中, 同一個小生境內(nèi)的個體適應(yīng)度共享, 從而降低該小生境內(nèi)個體的競爭力, 防止種群在收斂過程中陷入局部最優(yōu), 實現(xiàn)種群多樣性。首先, 對種群內(nèi)個體按非劣性排序, 為獲得的pareto 最優(yōu)解賦予相同的適應(yīng)度; 其次, 根據(jù)goldberg和deb等23提出的共享方法, 按式(2-3) 和式( 2-4) 計算出每一個pareto 最優(yōu)解的小生境數(shù), 將該個體原適應(yīng)度除以小生境數(shù),就得到它的共享適應(yīng)度。這樣, 處于同一個pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應(yīng)度也不同。 (2-3)其中,

51、 表示個體 與個體 的距離, 是同一小生境中個體間的最大允許距離, 表示距離為時的共享函數(shù)值。其中, ( 2-4) 表示個體i 的小生境數(shù)。雖然非支配排序遺傳算法（nsga）在許多問題上得到了應(yīng)用，但仍存在一些問題，如計算復(fù)雜度較高，需要指定共享半徑，易丟失已經(jīng)得到的滿意解。nsga-針對以上的缺陷通過以下三個方面進(jìn)行了改進(jìn)：(1)提出了快速非支配排序法，在選擇運算之前，根據(jù)個體的非劣解水平對種群分級。首先將當(dāng)前的所有的非劣解個體劃為同一等級，令其等級為；然后將這些個體從種群中移出，在剩余個體中尋找出新的非劣解，再令其等級為；重復(fù)上述過程，直至種群中所有個體都被設(shè)定相應(yīng)的等級。具體方法與nsg

52、a的快速非支配排序方法不同，nsga-對于每個個體都設(shè)有以下兩個參數(shù)和，為在種群中支配個體的解個體的數(shù)量，為被個體所支配的解個體的集合。首先，找到種群中所有的個體，將它們存入當(dāng)前集合，然后對于當(dāng)前集合的每個個體，考察它所支配的個體集,將集合中的每個個體的減去1，即支配個體的解個體數(shù)減1，如果則將個體存入另一個集。最后，將作為第一級非支配個體集合，并賦予該集合內(nèi)個體一個相同的非支配序，然后繼續(xù)對作上述分級操作并賦予相應(yīng)的非支配序，直到所有個體都被分級。如此操作降低了算法的計算復(fù)雜度。由原來的降到，其中，為目標(biāo)函數(shù)個數(shù)，為種群大小。(2)提出了擁擠度和擁擠度比較算子，代替了需要指定共享半徑的適應(yīng)度

53、共享策略，并在快速排序后的同級比較中作為勝出標(biāo)準(zhǔn)，使準(zhǔn)pareto域中的個體能擴(kuò)展到整個域，并均勻分布，保持了種群的多樣性。擁擠度的概念：擁擠度是指在種群中的給定點的周圍個體的密度，計算上要考慮個體周圍包含本身但不包含其他個體的最小正方形，如下圖，個體的聚集距離是。為了計算每個個體的聚集距離，需要對群體按每個子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對個子目標(biāo)分別進(jìn)行排序的時間復(fù)雜度為。從圖中可以看出值較小時，該個體周圍就比較擁擠，那么這幾個個體的適應(yīng)度就要降低，使得分布比較分散的解能保留下的幾率加大。擁擠度比較算子：為了維持種群的多樣性，需要一個比較擁擠度的算子以確保算法

54、能夠收斂到一個均勻分布的pareto面上。由于經(jīng)過了排序和擁擠度計算，群體中每個個體都得到了兩個屬性：非支配序和擁擠度，則定義偏序關(guān)系（）：當(dāng)滿足條件，或滿足且時，定義。即如果兩個個體的非支配排序不同，取排序號較小的個體；如果兩個個體在同一級，取周圍較不擁擠的個體。(3)引入精英策略，擴(kuò)大采樣空間。將父代種群與其產(chǎn)生的子代種群組合，共同競爭產(chǎn)生下一代種群，有利于保持父代中的優(yōu)良個體進(jìn)入下一代，并通過對種群中所有個體的分層存放，使得最佳個體不會丟失，迅速提高種群水平。nsga-算法的主流程：首先隨即初始化一個父代種群，并將所有個體按非支配關(guān)系排序，且指定一個適應(yīng)度值。然后采用選擇、交叉、變異算子

55、產(chǎn)生下一代種群，大小也為，完成第一代進(jìn)化。在產(chǎn)生新種群后，將與其父代種群合并組成，此時種群大小為。然后進(jìn)行非支配排序，產(chǎn)生一系列非支配集并計算擁擠度，通常選擇前個個體組成，滿足且。在上圖中，由于子代和父代個體都包含在中，則經(jīng)過非支配排序以后的非支配集中包含的個體是中最好的，所以先將放入新的父代種群中。如果的大小小于，則繼續(xù)向中填充，直到添加到時種群大小超出，對中的個體進(jìn)行擁擠度排序，取前個個體。使個體數(shù)量達(dá)到。然后通過遺傳算子產(chǎn)生新的子代種群。當(dāng)排序產(chǎn)生的非支配集的個體數(shù)目足夠填充時，就不必再繼續(xù)對剩下的部分排序了。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。算法流程圖：圖3-

56、1 nsga-的算法流程3.1.2mogls在mogls中，局部搜索過程應(yīng)用于通過遺傳操作所獲得每一個解。這種算法應(yīng)用在適應(yīng)度評價功能上應(yīng)用一種計算權(quán)值和的方式，即當(dāng)一對父代種群被選擇通過交叉變異去獲得新解時使用這個功能。局部搜索過程應(yīng)用于新解而最大限度地發(fā)揮它的適應(yīng)度的效率24。這個算法的一大典型特性是無論何時選擇一組父代種群都要指定權(quán)值效率。每個解通過不同的權(quán)值矢量執(zhí)行。另一個特點是在局部搜索的過程中不需要計算當(dāng)前種群的所有鄰域解，只有少部分鄰域解被檢驗避免在這個算法中消耗過多的所有可行解的計算時間。多目標(biāo)遺傳局部搜索算法試圖尋找多目標(biāo)最有問題所有的非支配解，如果在一個多目標(biāo)問題中一個解不被其他解支配，它叫做非劣解，一個多目標(biāo)問題有許多非劣解。雜交算法的目的不是確定一個單一的最終解，而是試圖尋找這個多目標(biāo)問題所有符合約束條件的最優(yōu)解。當(dāng)我們應(yīng)用ga算法解決多目標(biāo)問題時，需要評價每個解的適應(yīng)度，我們通過計算個目標(biāo)權(quán)值和的方式定義一個解的適