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

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

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

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

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

5、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 severalsorts. 2 MOP and the relational technique of MOEA was introduced concisely.Then NSGA-II and MOGLS wer

6、e 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, vis

7、ualization 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

8、 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目錄摘

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

10、二級(jí)標(biāo)題 354.3二級(jí)標(biāo)題 40三級(jí)標(biāo)題40三級(jí)標(biāo)題45參考文獻(xiàn)50附 錄 51致 謝 52第1章緒論許多科學(xué)研究和工程實(shí)踐中遇到的優(yōu)化問(wèn)題，通常需要綜合考慮多方面因素，這就要求在解決問(wèn)題時(shí)同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化，這樣的問(wèn)題被稱為多目標(biāo)優(yōu)化問(wèn)題(Multi-Objective Optimization Problem, MOP)，它們有許多沖突的目標(biāo)。有時(shí)目標(biāo)之間是相輔相成、互相促進(jìn)的，但更多的時(shí)候，目標(biāo)之間是相互矛盾、此消彼長(zhǎng)的。因此在絕大多數(shù)情況下，若想達(dá)到總目標(biāo)的最優(yōu)，就需要對(duì)各個(gè)目標(biāo)進(jìn)行綜合考慮、折中處理，所得到的解是一組基于Pareto最優(yōu)性概念的非劣解集1，所以如何進(jìn)行綜合與折中

11、就成為解決問(wèn)題的關(guān)鍵。1.1研究背景及意義生物在其延續(xù)生存的過(guò)程中，逐漸適應(yīng)其生存環(huán)境，使得品種不斷的到改良，這種生命現(xiàn)象叫做進(jìn)化。進(jìn)化算法(Evolutionary Algorithm, EA)是一種通過(guò)模擬生物進(jìn)化規(guī)律來(lái)進(jìn)行選擇與變化的隨機(jī)搜索算法，起源于20 世紀(jì)50 年代末，現(xiàn)有的代表性進(jìn)化方法有遺傳算法(Genetic Algorithm, GA)、進(jìn)化規(guī)劃(Evolutionary Programming, EP)和進(jìn)化策略(EvolutionStrategy, ES)等幾種方法2。進(jìn)化算法非常適用于于求解高度復(fù)雜的非線性問(wèn)題，并且由于這類(lèi)算法具有通用性，因而被廣泛地應(yīng)用于單個(gè)目標(biāo)

12、的復(fù)雜系統(tǒng)優(yōu)化問(wèn)題。然而，人們?cè)谇蠼猬F(xiàn)實(shí)世界許多優(yōu)化問(wèn)題時(shí)，通常不追求單一目標(biāo)的最優(yōu)性，這就要求在解決問(wèn)題時(shí)同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化和權(quán)衡，有時(shí)目標(biāo)之間是相輔相成、互相促進(jìn)的，但更多的時(shí)候，目標(biāo)之間是相互矛盾、此消彼長(zhǎng)的，這樣的問(wèn)題被稱為多目標(biāo)優(yōu)化問(wèn)題(Multi-Objective Optimization Problem, MOP)，大多數(shù)工程和科學(xué)問(wèn)題是多目標(biāo)最優(yōu)問(wèn)題。多目標(biāo)優(yōu)化問(wèn)題的各目標(biāo)之間通過(guò)決策變量相互制約,對(duì)其中一個(gè)目標(biāo)優(yōu)化必須以其它目標(biāo)作為代價(jià),而且各目標(biāo)的單位又往往不一致,因此很難客觀地評(píng)價(jià)多目標(biāo)問(wèn)題解的優(yōu)劣性。例如,在設(shè)計(jì)一座橋梁時(shí),我們一方面希望建設(shè)橋梁的費(fèi)用最小,另一方

13、面希望橋梁具有最大的安全性。與單目標(biāo)優(yōu)化問(wèn)題的本質(zhì)區(qū)別在于,多目標(biāo)優(yōu)化問(wèn)題的解不是唯一的,而是存在一個(gè)最優(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)，就需要對(duì)各個(gè)目標(biāo)進(jìn)行綜合考慮、折中處理，所以如何進(jìn)行綜合與折中就成為解決問(wèn)題的關(guān)鍵。多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithm, MOEA)就是一類(lèi)可以有效解決這種問(wèn)題的優(yōu)化技術(shù)3。它的主要思想是將進(jìn)化算法的概念引入到多目標(biāo)優(yōu)化領(lǐng)域，對(duì)多

14、目標(biāo)優(yōu)化問(wèn)題同樣采用進(jìn)化操作方式，但算法由單目標(biāo)優(yōu)化問(wèn)題求取一個(gè)最優(yōu)解，轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問(wèn)題中求取一個(gè)最優(yōu)解集，該解集稱為Pareto最優(yōu)解集。最優(yōu)解集中的每個(gè)解，理論上都是“最優(yōu)解”，而在實(shí)際應(yīng)用中，可以根據(jù)決策需要選擇其中一個(gè)解作為最終決策方案，實(shí)現(xiàn)最優(yōu)化的目的。多目標(biāo)進(jìn)化算法是一門(mén)新興的學(xué)科，理論與算法并不完善，尚處于發(fā)展階段。然而，它對(duì)工程項(xiàng)目具有重要的實(shí)踐意義，因此在過(guò)去的十多年間涌現(xiàn)出許多新的改進(jìn)算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標(biāo)進(jìn)化算法。而對(duì)算法性能進(jìn)行比較和評(píng)價(jià)就成為一個(gè)重要的核心問(wèn)題，引起了諸多學(xué)者的研究興趣。1.2多目標(biāo)進(jìn)化算法的研究現(xiàn)狀優(yōu)化問(wèn)題一直是倍受人們

15、關(guān)注的問(wèn)題，自1950 年以來(lái),運(yùn)籌學(xué)研究人員已經(jīng)建立了許多方法解決MOP。在專(zhuān)業(yè)文獻(xiàn)中,有許多數(shù)學(xué)規(guī)劃技巧解決MOP ,如多目標(biāo)加權(quán)法、分層序列法、約束法、目標(biāo)規(guī)劃法等。遺傳算法自出現(xiàn)以來(lái)在許多領(lǐng)域得到了廣泛的應(yīng)用，在解決簡(jiǎn)單的單目標(biāo)優(yōu)化問(wèn)題方面取得了很好的成果，但面對(duì)復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題，傳統(tǒng)的遺傳算法就顯得力不從心。例如在現(xiàn)代能源系統(tǒng)生產(chǎn)過(guò)程參數(shù)的優(yōu)化4設(shè)計(jì)中經(jīng)常會(huì)遇到多目標(biāo)函數(shù)的優(yōu)化問(wèn)題，使用經(jīng)典的多目標(biāo)優(yōu)化方法通常把多個(gè)目標(biāo)函數(shù)整合成單目標(biāo)，將問(wèn)題轉(zhuǎn)變?yōu)閱文繕?biāo)優(yōu)化問(wèn)題，然后采用單目標(biāo)的優(yōu)化技術(shù)求解。但這些方法存在：只能得到一個(gè)解；多個(gè)目標(biāo)函數(shù)之間量綱不同難以統(tǒng)一；加權(quán)值的分配帶有較強(qiáng)

16、的主觀性；加權(quán)的目標(biāo)函數(shù)之間通過(guò)決策變量相互制約，最終優(yōu)化目標(biāo)僅為各目標(biāo)之和，各目標(biāo)的優(yōu)化進(jìn)度不可操作等缺點(diǎn)。這是因?yàn)閭鹘y(tǒng)數(shù)學(xué)規(guī)劃方法存在一些缺陷,例如有些方法對(duì)Pareto 前沿比較敏感,當(dāng)Pareto 前沿是凹的或者不連續(xù)時(shí),這些方法失效;有些方法要求目標(biāo)函數(shù)和約束條件可微;有些方法每次運(yùn)行只產(chǎn)生一個(gè)解,求多個(gè)解時(shí)需要運(yùn)行多次,效率較低。進(jìn)化多目標(biāo)優(yōu)化始于1967年，此后眾多的研究人員通過(guò)對(duì)遺傳算法進(jìn)行改造，相繼提出了多種用于解決多目標(biāo)優(yōu)化問(wèn)題的遺傳算法，如基于向量評(píng)估的遺傳算法(VEGA) 5，小組決勝遺傳算法(NPGA) 6，非支配排序遺傳算法(NSGA)及其改進(jìn)算法NSGA-II7等

17、. 其中NSGA的改進(jìn)算法NSGA-II是帶有精英策略的非支配排序遺傳算法，改進(jìn)了先前算法的不足之處，提高了算法的運(yùn)算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。自Scharfer提出VEGA起，多目標(biāo)進(jìn)化算法的發(fā)展經(jīng)歷了由基于單目標(biāo)子群體優(yōu)化的算法到基于Pareto最優(yōu)性指導(dǎo)的分級(jí)策略與適應(yīng)值共享策略算法的發(fā)展歷程。按照算法原理與進(jìn)化模式劃分，現(xiàn)有多目標(biāo)進(jìn)化算法可分如下四大類(lèi)：第一類(lèi)算法是早期基于單目標(biāo)群體優(yōu)化的MOGA。這類(lèi)算法通過(guò)加權(quán)或劃分子群體進(jìn)化等方法將MOP轉(zhuǎn)化為不同的SOP，然后借助現(xiàn)有單目標(biāo)遺傳算法對(duì)轉(zhuǎn)化后的SOP進(jìn)行求解，最后對(duì)進(jìn)化獲得的解進(jìn)行分析，篩選出非劣解集。由于這類(lèi)算

18、法的設(shè)計(jì)思想是基于單目標(biāo)遺傳算法的進(jìn)化策略，因此它的優(yōu)點(diǎn)是算法容易實(shí)現(xiàn)；其不足是，基于單目標(biāo)子群體優(yōu)化的算法很難搜索到嚴(yán)格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點(diǎn)。代表算法有VEGA、WBGA、DM等。Ishibuchi、Murata等人1996年提出的MOGLS是在隨機(jī)權(quán)策略的WBGA中引入局部搜索的改進(jìn)算法，其本質(zhì)屬于這類(lèi)算法8。第二類(lèi)算法是基于Goldberg提出的適應(yīng)值分級(jí)和共享策略的多目標(biāo)遺傳算法。這類(lèi)算法在適應(yīng)值設(shè)計(jì)中鼓勵(lì)非劣解等級(jí)優(yōu)先個(gè)體和同一等級(jí)內(nèi)較為稀疏個(gè)體以較大概率出現(xiàn)在后代群體中。由于這類(lèi)算法是基于Pareto概念的MOGA，因此，它的優(yōu)點(diǎn)是可以通過(guò)單次優(yōu)化獲

19、得一組靠近真實(shí)非劣解前沿的非劣解集；但由于算法未考慮進(jìn)化過(guò)程中精英個(gè)體的保留，因此解的收斂速度及收斂性能不夠穩(wěn)健。代表算法有MOGA、NSGA和NPGA等。第三類(lèi)算法是由第二類(lèi)算法發(fā)展起來(lái)的精英保留策略MOGA。這類(lèi)算法通過(guò)在進(jìn)化過(guò)程中引入外部伴隨群體對(duì)群體中的精英個(gè)體加以保留，同時(shí)采用更加成熟的適應(yīng)值設(shè)計(jì)策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。這類(lèi)算法的不足之處是，算法進(jìn)化模式單一、局部搜索性能欠佳，之所以存在這些不足，主要是因?yàn)檫@類(lèi)算法大多由第二類(lèi)算法改進(jìn)得到，因此進(jìn)化模式不可能完全擺脫先前的算法框架，并且遺傳算法的進(jìn)化原理決定了它不可能具有性能較高的局部搜索能力

20、。代表算法有NPGA-II、NSGA-II、PAES和SPEA等9。第四類(lèi)算法是采用其他搜索算法策略改進(jìn)的MOEA。這類(lèi)算法由于采用的進(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ā)展才開(kāi)始活躍起來(lái)。這類(lèi)算法由于群體規(guī)模適中，因此算法復(fù)雜性相對(duì)較低，而且由于算法局部搜索性能優(yōu)越，因此常?？梢耘c現(xiàn)有的MOGA結(jié)合，形成新的精英算法。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)

21、、又能維持群體多樣性，因此，在算法設(shè)計(jì)時(shí)往往設(shè)置了許多控制參數(shù)對(duì)算法性能進(jìn)行調(diào)整，這又導(dǎo)致在求解問(wèn)題時(shí)常常需要借助大量試驗(yàn)計(jì)算分析確定進(jìn)化參數(shù)，因此算法性能不夠穩(wěn)健。代表算法有MOSE、MOPSO等10。除了上述四類(lèi)算法外，一些學(xué)者在演化策略中引入偏好分級(jí)或適應(yīng)值分享機(jī)制獲取滿意解。但由于這些方法不能通過(guò)幾次運(yùn)行獲得穩(wěn)定的非劣解集，且算法復(fù)雜性較高，因此這類(lèi)研究不是多目標(biāo)進(jìn)化算法研究的主流方向。而考慮偏好關(guān)系對(duì)遺傳進(jìn)化的影響，大多是用模糊集方法進(jìn)行偏好信息的處理，而進(jìn)一步利用偏好對(duì)進(jìn)化進(jìn)行指導(dǎo)或通過(guò)進(jìn)化引導(dǎo)偏好的交互式多目標(biāo)進(jìn)化算法還僅僅處于概念研究階段，距算法實(shí)現(xiàn)尚有較大差距。多目標(biāo)遺傳算法

22、的研究一直是這類(lèi)算法研究的主流方向：盡管遺傳算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他進(jìn)化策略或啟發(fā)式局部搜索算法好的局部搜索性能，因此，以進(jìn)化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進(jìn)化策略局部搜索的優(yōu)勢(shì)，獲得高性能的多目標(biāo)優(yōu)化算法，成為多目標(biāo)進(jìn)化算法研究的潛在發(fā)展方向。1.3本文研究?jī)?nèi)容 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類(lèi)11：前決策（先驗(yàn)式）、后決策（后驗(yàn)式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時(shí)間先后劃分的。其中，后決策是最常用的技術(shù)，即算法終止時(shí)提供給用戶一組最優(yōu)解。目前絕大多數(shù)多目標(biāo)進(jìn)化算法是排序選擇法和后決策技術(shù)類(lèi)型

23、的。SPEA/SPEA2 (Zitzler & Thiele 2001)和NSGA/NSGA-II (Srinivas & Deb 2002)兩類(lèi)算法目前的應(yīng)用更廣泛，也更具有代表性。由于本文需要對(duì)多目標(biāo)進(jìn)化算法的結(jié)構(gòu)進(jìn)行深入的分析，所以需要在此選擇一個(gè)代表性的算法，通過(guò)該算法的簡(jiǎn)介，來(lái)描述一下多目標(biāo)進(jìn)化算法的一些基本概念和工作原理。本文將以NSGA-II算法和MOGLS（Multi-Objective Genetic Lcal Search）算法為例，通過(guò)算例和指定的函數(shù)指標(biāo)來(lái)分析比較它們各自性能的優(yōu)缺點(diǎn)。NSGA-II算法首先隨機(jī)產(chǎn)生一個(gè)初始種群，對(duì)種群通過(guò)采用輪盤(pán)賭的方式

24、選擇、交叉和變異操作獲得新的種群，將種群中的個(gè)體構(gòu)造其Pareto 邊界集，并根據(jù)個(gè)體間的聚集距離，建立偏序關(guān)系，最終從偏序關(guān)系中選擇原始種群規(guī)模大小的個(gè)體，組成新的種群，完成了一次進(jìn)化操作。由此可見(jiàn)，對(duì)于多目標(biāo)進(jìn)化算法而言，構(gòu)造Pareto 邊界集和計(jì)算個(gè)體間的聚集距離是新的概念，也是絕大多數(shù)多目標(biāo)進(jìn)化算法共有的流程，這為之后提取算法公共流程方式的討論提供了基本的依據(jù)。MOGLS是Ishibuchi和Murata兩位學(xué)者提出的。最初的MOGLS是在遺傳進(jìn)化過(guò)程中，每代遺傳操作生成新個(gè)體后，對(duì)現(xiàn)有群體中的所有個(gè)體進(jìn)行局部搜索；后來(lái)Ishibuchi等人對(duì)局部搜索的步長(zhǎng)選取、鄰域搜索效率做了進(jìn)一

25、步研究后，將局部搜索過(guò)程僅應(yīng)用于當(dāng)前群體中的優(yōu)秀，顯著提高了算法效率，改進(jìn)后的算法可獲得與SPEA、NSGA-II相當(dāng)?shù)膬?yōu)化性能。MOGLS的優(yōu)點(diǎn)是通過(guò)隨機(jī)權(quán)將MOP轉(zhuǎn)化為SOP，算法容易實(shí)現(xiàn)，并且恰當(dāng)控制MOGLS中鄰域搜索個(gè)體的選取及步長(zhǎng)可以在減少計(jì)算復(fù)雜度的同時(shí)獲得良好的計(jì)算結(jié)果；算法的不足之處是，算法的構(gòu)造是基于MOP轉(zhuǎn)化為SOP的思想，因此在不明確多個(gè)目標(biāo)偏好情況下，采用隨機(jī)權(quán)的方法往往不能保證所得非劣解集分布的均勻性。第2章多目標(biāo)進(jìn)化算法2.1 多目標(biāo)優(yōu)化基本概念多目標(biāo)優(yōu)化問(wèn)題描述多目標(biāo)問(wèn)題( MOP) 的一般描述為: 給定決策向量 , 它滿足下列約束: ( 2-1) ( 2-2)

26、設(shè)有r 個(gè)優(yōu)化目標(biāo), 且這r 個(gè)優(yōu)化目標(biāo)是相互沖突的, 優(yōu)化目標(biāo)可表示為:尋求, 使在滿足約束( 2-1) 和( 2-2) 的同時(shí)達(dá)到最小。最優(yōu)性對(duì)于多目標(biāo)優(yōu)化問(wèn)題, 由于其待優(yōu)化的各個(gè)子目標(biāo)一般是相互沖突的, 因此需要定義解個(gè)體間的優(yōu)劣關(guān)系, 以便對(duì)候選解進(jìn)行評(píng)價(jià)與取舍。本文采用廣泛使用的Pareto 最優(yōu)性12定義。定義1 ( 個(gè)體的Pareto 支配關(guān)系) 。設(shè)和是進(jìn)化群體中的任意兩個(gè)不同的個(gè)體,稱支配(dominate),則必須滿足下列二個(gè)條件:( 1) 對(duì)所有的子目標(biāo),不比 差, 即 ( k=1, 2, r) ; （2） 至少存在一個(gè)子目標(biāo),使比好。即, 使其中r 為子目標(biāo)的數(shù)量。此

27、時(shí)稱 為非支配的( non- dominated), 為被支配的( dominated) 。表示為, 其中“”是支配關(guān)系。定義2( Pareto 非支配集)。設(shè)有解集,若中的個(gè)體不被任何其它個(gè)體支配, 則是 中的非支配個(gè)體; 由 中的所有非支配個(gè)體構(gòu)成的子集稱為 的非支配集。即: 最優(yōu)性的含義為：是Pareto最優(yōu)解，表示在整個(gè)解空間中，不存在這樣的解：某一個(gè)目標(biāo)比小的同時(shí)，保持其余個(gè)目標(biāo)值不大于x的目標(biāo)值。因此，滿足這種最優(yōu)性的“最優(yōu)解”往往不是單個(gè)解，而是一組滿足上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱作非劣解集（Pareto Solutions Set）或非受控解集(nondomi

28、nated solutions set)；非劣解對(duì)應(yīng)的目標(biāo)值在目標(biāo)空間中稱為非劣點(diǎn)；最優(yōu)解集在優(yōu)化目標(biāo)空間構(gòu)成的分布稱作非劣解前沿。在決策和優(yōu)化問(wèn)題中，最優(yōu)性取決于如何比較和排序候選解，及決策者的偏好結(jié)構(gòu)。從決策者的立場(chǎng)來(lái)看，一般認(rèn)為每對(duì)候選解具有以下比較關(guān)系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。由此才可以對(duì)每對(duì)解之間的優(yōu)劣比較進(jìn)行細(xì)致的區(qū)分13。2.2多目標(biāo)遺傳算法設(shè)計(jì)的關(guān)鍵技術(shù)適應(yīng)值設(shè)計(jì)MOP問(wèn)題包含多個(gè)待優(yōu)化的子目標(biāo)，通常EAs用于多目標(biāo)優(yōu)化時(shí)必須考慮兩個(gè)關(guān)鍵問(wèn)題：(1)為了保證朝Pareto最優(yōu)集的方向搜索，如何實(shí)施適應(yīng)度賦值和選擇。(2)為了避免未成

29、熟收斂和獲得均勻分布且范圍最廣的非劣解，如何保持群體的多樣性。在已有研究中，多目標(biāo)遺傳算法的適應(yīng)值設(shè)計(jì)(Fitness Assignment)主要有基于加權(quán)策略、基于目標(biāo)設(shè)計(jì)策略和基于非劣解等級(jí)優(yōu)先策略三種設(shè)計(jì)策略14：(1)基于加權(quán)策略的適應(yīng)值設(shè)計(jì)，即基于聚合策略的方法，是通過(guò)加權(quán)策略將多個(gè)目標(biāo)轉(zhuǎn)化為單個(gè)目標(biāo)后進(jìn)行優(yōu)化。這種適應(yīng)值設(shè)計(jì)的遺傳算法通常需要在算法進(jìn)化過(guò)程中系統(tǒng)地對(duì)函數(shù)中的參數(shù)的權(quán)重值進(jìn)行調(diào)整，以便得到一組非劣解集。在進(jìn)化的每一代中參數(shù)呈現(xiàn)有規(guī)律的變化，但在該代操作過(guò)程中保持不變，常見(jiàn)的進(jìn)化加權(quán)法，個(gè)體的評(píng)估使用確定的加權(quán)組合，所有個(gè)體都有一個(gè)適應(yīng)度值，保證了搜索方向朝最優(yōu)解邁進(jìn)。

30、(2)基于目標(biāo)設(shè)計(jì)策略的算法，即基于準(zhǔn)則的策略，每當(dāng)個(gè)體選中后進(jìn)行復(fù)制時(shí)根據(jù)不同的目標(biāo)來(lái)決定是否被復(fù)制至配對(duì)池。此方法通過(guò)在不同進(jìn)化代之間更換優(yōu)化目標(biāo)每次優(yōu)化一個(gè)目標(biāo)，使算法群體每次運(yùn)行得到一個(gè)非劣解，從而通過(guò)多次運(yùn)行找到優(yōu)化問(wèn)題的非劣解集。目前，常用的方法是在選擇階段根據(jù)概率來(lái)確定各子目標(biāo)的排序，該概率值由用戶確定或隨機(jī)產(chǎn)生。這種策略存在的問(wèn)題是進(jìn)化結(jié)果容易偏向某些極端邊界解，并且對(duì)Pareto最優(yōu)前端的非凸部敏感。(3)基于非劣解等級(jí)優(yōu)先概念的適應(yīng)值分配策略由Goldberg最先提出，后人大多在此基礎(chǔ)上進(jìn)行改進(jìn)，如將群體劃分為幾個(gè)有序的子群體。這類(lèi)算法的適應(yīng)值設(shè)計(jì)主要有等級(jí)優(yōu)先、深度優(yōu)先和

31、基于優(yōu)先數(shù)三種：等級(jí)優(yōu)先策略算法在計(jì)算適應(yīng)值時(shí)主要考慮個(gè)體在群體中“優(yōu)于”其他個(gè)體的數(shù)目或考慮優(yōu)于該個(gè)體的其他個(gè)體數(shù)目之和，以此確定給個(gè)體的適應(yīng)度值；而深度優(yōu)先策略算法在分配個(gè)體適應(yīng)值時(shí)主要以個(gè)體所在的非劣解等級(jí)及等級(jí)內(nèi)的疏密程度有關(guān)；基于優(yōu)先數(shù)的適應(yīng)值分配算法在計(jì)算個(gè)體適應(yīng)值時(shí)，考慮了個(gè)體所優(yōu)先于或劣于群體中其他個(gè)體的數(shù)目。一般來(lái)說(shuō)直接統(tǒng)計(jì)優(yōu)勝個(gè)體數(shù)目的操作方式簡(jiǎn)單，在原理上一目了然。單目標(biāo)優(yōu)化中的目標(biāo)函數(shù)常與適應(yīng)度函數(shù)相同，但MOP問(wèn)題中的適應(yīng)度賦值和選擇必須考慮幾個(gè)子目標(biāo)，MOEAs必須根據(jù)個(gè)體間的Pareto優(yōu)勝關(guān)系和其他信息為個(gè)體確定適應(yīng)度值，這種適應(yīng)度值和每個(gè)目標(biāo)函數(shù)的具體大小沒(méi)有

32、直接關(guān)系。另外，與單目標(biāo)優(yōu)化不同的是，在個(gè)體保持不變的條件下，同一個(gè)體在這一代和下一代的適應(yīng)值可能不相等。Pareto優(yōu)勝關(guān)系是決定個(gè)體適應(yīng)度函數(shù)值的重要依據(jù)，很多MOEAs根據(jù)個(gè)體間的這種關(guān)系，將個(gè)體的適應(yīng)度函數(shù)值分成兩個(gè)層次，即劣解和非劣解，后者的適應(yīng)度值總是優(yōu)于前者。當(dāng)個(gè)體間沒(méi)有Pareto優(yōu)勝關(guān)系時(shí)，其他形式的個(gè)體信息被用于確定適應(yīng)度函數(shù)值，其中個(gè)體密度值是利用最多的信息，并采用不同的方法估計(jì)個(gè)體密度值。基于Pareto優(yōu)勝關(guān)系的選擇方法已經(jīng)被廣大研究者采納，現(xiàn)已有多種基于Pareto的適應(yīng)度賦值方案，其中基于種群個(gè)體級(jí)別排序的適應(yīng)度賦值方法是較常見(jiàn)的一種方法。多目標(biāo)問(wèn)題與單目標(biāo)問(wèn)題不

33、同，它的優(yōu)劣性與支配關(guān)系并非定義目標(biāo)向量之間的那種整體有序關(guān)系，只是給出部分有序關(guān)系，因而種群的級(jí)別排序不具有唯一性。假設(shè)第代種群中的個(gè)體，在第代種群個(gè)體排序中的位置為，基于個(gè)體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個(gè)體進(jìn)行級(jí)別排序。(2)利用線性或非線性的插值方法在最低序號(hào)與最高序號(hào)之間進(jìn)行插值。(3)具有相同序號(hào)的個(gè)體進(jìn)行適應(yīng)度共享算子操作，即通過(guò)除以相同序號(hào)的個(gè)體數(shù)目得到新的適應(yīng)度值，另外，也可以給不同序號(hào)的個(gè)體分配固定不變的適應(yīng)度值。維持群體多樣性因?yàn)镋As是并行地處理一組解，通過(guò)雜交和變異來(lái)搜索空間以尋找可能的最優(yōu)區(qū)域，通過(guò)選擇來(lái)搜索具有較高適應(yīng)度的個(gè)體。傳統(tǒng)的進(jìn)

34、化算法在Pareto最優(yōu)集上執(zhí)行多目標(biāo)搜尋，希望找出盡可能均勻分布的解集，因而個(gè)體的多樣性減少的很快，經(jīng)常收斂至單個(gè)解而丟失多個(gè)其他非劣解。在進(jìn)化過(guò)程中某些具有較高適應(yīng)度個(gè)體的大量復(fù)制造成高選擇壓力，使得個(gè)別具有更高適應(yīng)度的個(gè)體得不到遺傳的機(jī)會(huì)，甚至導(dǎo)致整個(gè)群體出現(xiàn)同解的現(xiàn)象15。如果單純從群體多樣性出發(fā)，群體規(guī)模應(yīng)該越大越好，但群體規(guī)模太大會(huì)帶來(lái)若干弊?。阂皇菑挠?jì)算效率來(lái)看，群體越大，導(dǎo)致其適應(yīng)度評(píng)估次數(shù)增加，引起計(jì)算量的增加，從而影響算法效能；二是群體中個(gè)體生存下來(lái)的選擇概率大多采用和適應(yīng)度成比例的方法，當(dāng)群體中個(gè)體非常多時(shí)，少量適應(yīng)度很高的個(gè)體會(huì)被選擇而生存下來(lái)，大多數(shù)個(gè)體被淘汰，嚴(yán)重影

35、響交叉操作。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進(jìn)化算法多樣性的途徑。進(jìn)化算法由于其進(jìn)化算子固有的隨機(jī)誤差，因而基于有限群體實(shí)施進(jìn)化時(shí)會(huì)出現(xiàn)收斂至某一個(gè)解。因?yàn)槎嗄繕?biāo)優(yōu)化的目的是得到一組在整個(gè)Pareto曲面上盡可能均勻分布的一組解，因此必須在進(jìn)化過(guò)程中采取措施避免進(jìn)化結(jié)果收斂至單個(gè)解。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點(diǎn)，大多數(shù)MOEAs在當(dāng)代群體中維持多樣性是在選擇過(guò)程中結(jié)合了密度信息，即個(gè)體在其鄰域范圍內(nèi)所占的密度越高被選擇復(fù)制的機(jī)會(huì)越小?，F(xiàn)有多目標(biāo)遺傳算法可根據(jù)統(tǒng)計(jì)概率密度估計(jì)的方法加以分類(lèi)為如下三種策略來(lái)維持群體多樣性：(1)基于核函數(shù)

36、的評(píng)價(jià)策略：基于核函數(shù)的評(píng)價(jià)策略主要通過(guò)計(jì)算以個(gè)體為“核”、群體中其他個(gè)體距離“核”的核函數(shù)之和，通過(guò)優(yōu)先保留核函數(shù)值較大的個(gè)體即較稀疏的解個(gè)體達(dá)到維持群體多樣性的目的。具體應(yīng)用時(shí)首先根據(jù)內(nèi)核函數(shù)來(lái)定義一個(gè)點(diǎn)的鄰域范圍，內(nèi)核函數(shù)采用至另一點(diǎn)的距離作為參數(shù)。每一個(gè)個(gè)體計(jì)算至其他個(gè)體的距離，通過(guò)內(nèi)核函數(shù)的映射后求和計(jì)算出值，該累加值代表了個(gè)體的密度估計(jì)。(2)基于鄰域解數(shù)目的評(píng)價(jià)策略：基于鄰域解數(shù)目的評(píng)價(jià)策略是以評(píng)價(jià)解為核心、包含一定數(shù)量鄰域解的鄰域半徑為指標(biāo)，優(yōu)先保留鄰域半徑較大的個(gè)體即較稀疏的解個(gè)體。該策略主要考慮給定點(diǎn)至第個(gè)最近鄰居的距離，以便估計(jì)出其在鄰域內(nèi)的密度。(3)分區(qū)統(tǒng)計(jì)數(shù)目策略：

37、分區(qū)統(tǒng)計(jì)數(shù)目策略是將目標(biāo)空間劃分成一定比例的區(qū)域，通過(guò)統(tǒng)計(jì)個(gè)體所在區(qū)域中鄰域解數(shù)目來(lái)確定個(gè)體被保留的概率鄰域解數(shù)目越大，被保留概率越小。該方法采用一個(gè)網(wǎng)格來(lái)定義空間上的鄰居關(guān)系，個(gè)體的密度只要通過(guò)簡(jiǎn)單地統(tǒng)計(jì)同一網(wǎng)格內(nèi)的個(gè)體數(shù)目即可，這種網(wǎng)絡(luò)可以是固定的，也可以根據(jù)當(dāng)前群體進(jìn)行自適應(yīng)調(diào)整。多目標(biāo)進(jìn)化算法與單目標(biāo)進(jìn)化算法類(lèi)似，為了提高群體多樣性，在算法過(guò)程中盡量采用小生境（Niche）共享技術(shù)，使得在一個(gè)群體內(nèi)可以形成在多目標(biāo)問(wèn)題上分布均勻的非劣最優(yōu)解集。具有相同Pareto級(jí)別序號(hào)的解個(gè)體在實(shí)施共享適應(yīng)度值后，還必須按解的目標(biāo)向量之間的空間距離進(jìn)行小生境規(guī)模調(diào)整。當(dāng)兩個(gè)解的目標(biāo)向量之間的空間距離

38、小于某一預(yù)定值時(shí)，相應(yīng)解的小生境規(guī)模就必須進(jìn)行調(diào)整。此外，還有同時(shí)基于決策向量空間與目標(biāo)向量空間的混合共享技術(shù)，共享問(wèn)題的關(guān)鍵是如何確定共享參數(shù)，的選擇將會(huì)影響算法的性能，而適應(yīng)度共享效果則共同取決于和種群大小16。精英保留策略遺傳算法是基于隨機(jī)進(jìn)化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標(biāo)遺傳算法大都引入了精英保留策略。現(xiàn)有算法中精英策略的實(shí)現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過(guò)確定性的選擇方法在混合群體中選擇后代，而不是采用變化之后的配對(duì)池來(lái)替換舊群體，增大了精英個(gè)體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。另一種實(shí)現(xiàn)方式是采用獨(dú)立于進(jìn)化群體的伴隨群體，即使用帶有所謂

39、的檔案（Archive）的方式，保留與更新算法進(jìn)化過(guò)程中搜索到的非劣解集來(lái)維護(hù)當(dāng)代群體中的滿意群體，使其能夠復(fù)制到下一代，伴隨群體僅作為一個(gè)外部存儲(chǔ)集，獨(dú)立于進(jìn)化過(guò)程的優(yōu)化操作17。由于內(nèi)存資源的限制，以上兩種最優(yōu)個(gè)體保留策略必須確定哪些個(gè)體作為最優(yōu)個(gè)體加以保留。通常采用優(yōu)勝準(zhǔn)則來(lái)確定最優(yōu)個(gè)體。如果使用伴隨群體的方式，則伴隨群體中包括當(dāng)前的近似Pareto集，即伴隨群體中受控的個(gè)體被移去。但是使用優(yōu)勝關(guān)系比較的方法有時(shí)也存在問(wèn)題，如對(duì)某些連續(xù)型問(wèn)題所對(duì)應(yīng)的Pareto集可能包含無(wú)窮多個(gè)解，因此需要補(bǔ)充其他的信息知識(shí)來(lái)減小所存儲(chǔ)的個(gè)體數(shù)目。這些信息包括密度信息，個(gè)體進(jìn)入伴隨群體所需時(shí)間。MOEA

40、s的最優(yōu)個(gè)體大多利用優(yōu)勝關(guān)系和密度兩者的組合來(lái)進(jìn)行挑選，最優(yōu)個(gè)體保存在每代的伴隨群體中。更新的算法研究表明，如果同時(shí)采用這兩種精英策略，可以進(jìn)一步提高算法的搜索性能與收斂效果。2.3遺傳算法的一般流程Holland教授提出的遺傳算法，現(xiàn)在一般稱為簡(jiǎn)單遺傳算法或基本遺傳算法18，其基本流程如下圖：圖2-1遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問(wèn)題空間的參數(shù)，因此在算法開(kāi)始進(jìn)行之前，首先要選擇合適的編碼方式對(duì)待優(yōu)化的參數(shù)進(jìn)行編碼。通常采用二進(jìn)制編碼，將參數(shù)轉(zhuǎn)換成為和組成的數(shù)字串。 (2)產(chǎn)生初始種群：隨機(jī)地產(chǎn)生一個(gè)由個(gè)個(gè)體組成的種群，該種群代表一些可能解的集合。遺傳算法的任務(wù)是種

41、群出發(fā)，模擬生物進(jìn)化的過(guò)程進(jìn)行優(yōu)勝劣汰，最后得出滿足優(yōu)化要求的種群和個(gè)體。 (3)設(shè)計(jì)適應(yīng)度函數(shù)：把問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度函數(shù)計(jì)算種群中的每個(gè)個(gè)體的適應(yīng)度，為種群進(jìn)化的選擇提供依據(jù)。 (4)優(yōu)化準(zhǔn)則：也可稱作終止條件，是用來(lái)判斷算法是否可以終止的標(biāo)準(zhǔn)?？梢栽O(shè)定進(jìn)化的最大代數(shù)，當(dāng)進(jìn)化到最大代數(shù)時(shí)，算法終止運(yùn)行。也可以設(shè)定期望的適應(yīng)度函數(shù)值，只有當(dāng)種群中存在個(gè)體能達(dá)到期望值時(shí)，算法才可以結(jié)束。通常情況下，這兩種方法同時(shí)作為優(yōu)化準(zhǔn)則使用。(5)選擇(復(fù)制)操作:按一定概率從群體中選擇個(gè)體，作為雙親用于繁殖后代，產(chǎn)生新的個(gè)體。在此操作中，適應(yīng)于生存環(huán)境的優(yōu)良個(gè)體將有更多的機(jī)

42、會(huì)繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。(6)交叉操作:隨機(jī)地選擇用于繁殖的每一對(duì)個(gè)體的同一基因位，將其染色體在此基因位斷開(kāi)并相互交換。(7)變異操作:以一定的概率從群體中選擇若干個(gè)個(gè)體。對(duì)于選中的個(gè)體，隨機(jī)選擇某一位進(jìn)行取反操作。對(duì)產(chǎn)生的新一代群體重新進(jìn)行評(píng)價(jià)、選擇、雜交和變異。一代一代循環(huán)往復(fù)，使種群中最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個(gè)體的適應(yīng)度滿足優(yōu)化準(zhǔn)則或最優(yōu)個(gè)體的適應(yīng)度和平均適應(yīng)度不再提高，則迭代過(guò)程收斂，算法結(jié)束。遺傳算法的選擇和交叉算子賦予了它強(qiáng)有力的搜索能力，變異算子則使算法能搜索到問(wèn)題解空間的每一個(gè)點(diǎn)，以確保算法能達(dá)到全局最優(yōu)。遺傳算法提供了一種求解復(fù)雜系統(tǒng)

43、優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的領(lǐng)域和種類(lèi)。對(duì)一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問(wèn)題，一般可以按照上述步驟來(lái)構(gòu)造求解該問(wèn)題的遺傳算法。由上述步驟可以看出，構(gòu)造遺傳算法時(shí)需要考慮的兩個(gè)主要問(wèn)題是可行解的編碼方法和遺傳算子的設(shè)計(jì)，這也是設(shè)計(jì)遺傳算法的兩個(gè)關(guān)鍵步驟。2.4算法性能評(píng)價(jià)多目標(biāo)進(jìn)化算法性能評(píng)價(jià)的研究現(xiàn)狀多目標(biāo)遺傳算法的性能評(píng)價(jià)與傳統(tǒng)優(yōu)化算法及單目標(biāo)遺傳算法的性能評(píng)價(jià)有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過(guò)梯度下降速度進(jìn)行評(píng)價(jià)，并且可以通過(guò)嚴(yán)格的數(shù)學(xué)證明分析其收斂性能；單目標(biāo)遺傳算法可以采用基于模式定理或基于馬爾可夫隨機(jī)過(guò)程理論的證明分析其收斂性，盡管這類(lèi)證明研究還很初步。然而在對(duì)多目標(biāo)進(jìn)化算

44、法的性能進(jìn)行評(píng)價(jià)時(shí)，一般需要考慮到三個(gè)較為重要的因素19：算法的效率、算法的效果，以及算法的魯棒性。算法的效率是指算法自身的時(shí)間復(fù)雜度和空間復(fù)雜度，也即算法運(yùn)算時(shí)間的長(zhǎng)短和資源消耗的多少；算法的效果是指算法求得的解集的質(zhì)量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應(yīng)用范圍和穩(wěn)定性，也即是否對(duì)多種問(wèn)題都有很好的求解能力、是否求解問(wèn)題時(shí)總是相對(duì)穩(wěn)定的。而從現(xiàn)階段的研究來(lái)看，人們更關(guān)注的是，算法結(jié)果是否為高質(zhì)量的結(jié)果，而對(duì)于另外兩個(gè)因素相對(duì)要求并不高，而且對(duì)于算法的效率來(lái)說(shuō)，涉及到的是經(jīng)典的算法復(fù)雜度理論，已經(jīng)有很完善的泛化體系對(duì)其進(jìn)行評(píng)價(jià)了，無(wú)需在多目標(biāo)進(jìn)化算法領(lǐng)域?qū)ζ湓龠M(jìn)行專(zhuān)

45、門(mén)的研究。所以現(xiàn)階段的性能評(píng)價(jià)方法主要集中于對(duì)算法的效果的衡量。多目標(biāo)進(jìn)化算法的性能評(píng)價(jià)方法多目標(biāo)進(jìn)化算法的性能評(píng)價(jià)方法有很多，大體上可以分為兩類(lèi)20，一類(lèi)是評(píng)價(jià)算法的收斂性效果的，一類(lèi)是評(píng)價(jià)解集的分布性效果的。下面分別對(duì)二者加以介紹。1. 算法收斂性評(píng)價(jià)所謂的收斂性，實(shí)際上是指算法的真實(shí)結(jié)果集與理論上的最優(yōu)結(jié)果集之間的趨近度，即理論上的Pareto邊界和真正得到的Pareto邊界之間的差距。收斂性的評(píng)價(jià)方法有很多種，如錯(cuò)誤率、解集間覆蓋率、世代距離、最大出錯(cuò)率等等。以解集間覆蓋率為例，該覆蓋率又稱為S指標(biāo)(Zitzler, 2000)21，用來(lái)計(jì)算一個(gè)解集中被另一個(gè)解集中的個(gè)體支配的個(gè)體所占

46、的比率。如式(3-1)所示。(3-1)對(duì)于收斂性的評(píng)價(jià)指標(biāo)而言，可以通過(guò)指標(biāo)值反映出算法間優(yōu)化效果的差異，但只局限于最優(yōu)解集中更優(yōu)解的數(shù)量，對(duì)于其空間上的特性不做相關(guān)考慮。2. 解集分布性評(píng)價(jià)在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過(guò)于集中，則周?chē)暮芏嘟馐聦?shí)上并沒(méi)有太大的意義，也不利于產(chǎn)生新個(gè)體，從而影響了種群的進(jìn)化效果。分布性的評(píng)價(jià)方法也有很多，如空間評(píng)價(jià)方法、基于個(gè)體信息的評(píng)價(jià)方法、網(wǎng)格分布度評(píng)價(jià)方法等等。以空間評(píng)價(jià)方法為例，該方法又被稱為Delta指標(biāo)(Schott, 1995)22，用來(lái)計(jì)算解的

47、分布信息的，如式(3-2)所示。 (3-2) 其中，對(duì)于分布性的評(píng)價(jià)指標(biāo)而言，只關(guān)注結(jié)果集的分布特性，用以檢測(cè)算法是否被阻在一個(gè)很小的范圍之內(nèi)進(jìn)行搜索，而導(dǎo)致無(wú)法實(shí)現(xiàn)全局的最優(yōu)搜索的現(xiàn)象。由于收斂性評(píng)價(jià)與分布性評(píng)價(jià)的應(yīng)用方向不同，因而在比較算法的時(shí)候，多會(huì)綜合兩種評(píng)價(jià)后，對(duì)算法的性能得出適當(dāng)?shù)慕Y(jié)論。現(xiàn)有性能評(píng)價(jià)體系的特點(diǎn)分析現(xiàn)有的性能評(píng)價(jià)體系可以分為兩種形式22：1. 理論證明理論證明即是對(duì)算法的復(fù)雜度、收斂性等進(jìn)行求解和比較，即通過(guò)理論的分析得出正確的結(jié)論。但是由于多目標(biāo)進(jìn)化算法是一門(mén)新興的學(xué)科，多目標(biāo)進(jìn)化計(jì)算的理論基礎(chǔ)尚未成熟，算法收斂性的理論證明對(duì)有限時(shí)間內(nèi)的收斂性分析較少，而時(shí)間無(wú)窮大

48、的收斂性并沒(méi)有工程實(shí)際的應(yīng)用價(jià)值。因此從理論上來(lái)證明算法的優(yōu)劣并不常用，也較難實(shí)現(xiàn)正確的評(píng)估。2. 實(shí)驗(yàn)比較分析實(shí)驗(yàn)比較分析是指通過(guò)對(duì)優(yōu)化算例的結(jié)果和結(jié)果的各種指標(biāo)進(jìn)行比較，驗(yàn)證新算法與已存在的算法之間的性能差別。這種基于解決實(shí)際算例進(jìn)行評(píng)價(jià)的方法具有一定的局限性，很難得出某種算法一定比另外一種更優(yōu)的結(jié)論，其結(jié)論的說(shuō)服力也不夠。但是，由于這種方法可以簡(jiǎn)單直觀的反映出算法的一些特性，所以在分析算法性能領(lǐng)域的應(yīng)用十分廣泛。因此，現(xiàn)有的性能評(píng)價(jià)體系從使用范圍上講，是基于實(shí)驗(yàn)比較分析來(lái)實(shí)現(xiàn)的。2.5本章小結(jié)本章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和原理。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，現(xiàn)代多目標(biāo)

49、進(jìn)化算法正是在這些方面存在差異，也是判斷算法之間性能優(yōu)劣的出發(fā)點(diǎn)。第三部分給出了多目標(biāo)進(jìn)化算法的一般流程，這是所有算法的原型，不同算法都是在此基礎(chǔ)上做出改動(dòng)，了解此框架是學(xué)習(xí)其他算法的基礎(chǔ)。最后簡(jiǎn)單介紹了算法的性能評(píng)價(jià)體系，為幾種算法比較的方案提供依據(jù)，得出基于實(shí)驗(yàn)的方法是可行的，本文將在第三章利用這一思想來(lái)試驗(yàn)NSGA-和MOGLS兩種算法的優(yōu)劣。第三章優(yōu)化算例及分析3.1 NSGA-和MOGLS算法3.1.1帶精英策略的非支配排序的遺傳算法（NSGA-）在NSGA 中, 同一個(gè)小生境內(nèi)的個(gè)體適應(yīng)度共享, 從而降低該小生境內(nèi)個(gè)體的競(jìng)爭(zhēng)力, 防止種群在收斂過(guò)程中陷入局部最優(yōu), 實(shí)現(xiàn)種群多樣性。

50、首先, 對(duì)種群內(nèi)個(gè)體按非劣性排序, 為獲得的Pareto 最優(yōu)解賦予相同的適應(yīng)度; 其次, 根據(jù)Goldberg和Deb等23提出的共享方法, 按式(2-3) 和式( 2-4) 計(jì)算出每一個(gè)Pareto 最優(yōu)解的小生境數(shù), 將該個(gè)體原適應(yīng)度除以小生境數(shù),就得到它的共享適應(yīng)度。這樣, 處于同一個(gè)Pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應(yīng)度也不同。 (2-3)其中, 表示個(gè)體 與個(gè)體 的距離, 是同一小生境中個(gè)體間的最大允許距離, 表示距離為時(shí)的共享函數(shù)值。其中, ( 2-4) 表示個(gè)體i 的小生境數(shù)。雖然非支配排序遺傳算法（NSGA）在許多問(wèn)題上得到了應(yīng)用，但仍存在一

51、些問(wèn)題，如計(jì)算復(fù)雜度較高，需要指定共享半徑，易丟失已經(jīng)得到的滿意解。NSGA-針對(duì)以上的缺陷通過(guò)以下三個(gè)方面進(jìn)行了改進(jìn)：(1)提出了快速非支配排序法，在選擇運(yùn)算之前，根據(jù)個(gè)體的非劣解水平對(duì)種群分級(jí)。首先將當(dāng)前的所有的非劣解個(gè)體劃為同一等級(jí)，令其等級(jí)為；然后將這些個(gè)體從種群中移出，在剩余個(gè)體中尋找出新的非劣解，再令其等級(jí)為；重復(fù)上述過(guò)程，直至種群中所有個(gè)體都被設(shè)定相應(yīng)的等級(jí)。具體方法與NSGA的快速非支配排序方法不同，NSGA-對(duì)于每個(gè)個(gè)體都設(shè)有以下兩個(gè)參數(shù)和，為在種群中支配個(gè)體的解個(gè)體的數(shù)量，為被個(gè)體所支配的解個(gè)體的集合。首先，找到種群中所有的個(gè)體，將它們存入當(dāng)前集合，然后對(duì)于當(dāng)前集合的每個(gè)個(gè)

52、體，考察它所支配的個(gè)體集,將集合中的每個(gè)個(gè)體的減去1，即支配個(gè)體的解個(gè)體數(shù)減1，如果則將個(gè)體存入另一個(gè)集。最后，將作為第一級(jí)非支配個(gè)體集合，并賦予該集合內(nèi)個(gè)體一個(gè)相同的非支配序，然后繼續(xù)對(duì)作上述分級(jí)操作并賦予相應(yīng)的非支配序，直到所有個(gè)體都被分級(jí)。如此操作降低了算法的計(jì)算復(fù)雜度。由原來(lái)的降到，其中，為目標(biāo)函數(shù)個(gè)數(shù)，為種群大小。(2)提出了擁擠度和擁擠度比較算子，代替了需要指定共享半徑的適應(yīng)度共享策略，并在快速排序后的同級(jí)比較中作為勝出標(biāo)準(zhǔn)，使準(zhǔn)Pareto域中的個(gè)體能擴(kuò)展到整個(gè)域，并均勻分布，保持了種群的多樣性。擁擠度的概念：擁擠度是指在種群中的給定點(diǎn)的周?chē)鷤€(gè)體的密度，計(jì)算上要考慮個(gè)體周?chē)?/p>

53、身但不包含其他個(gè)體的最小正方形，如下圖，個(gè)體的聚集距離是。為了計(jì)算每個(gè)個(gè)體的聚集距離，需要對(duì)群體按每個(gè)子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對(duì)個(gè)子目標(biāo)分別進(jìn)行排序的時(shí)間復(fù)雜度為。從圖中可以看出值較小時(shí)，該個(gè)體周?chē)捅容^擁擠，那么這幾個(gè)個(gè)體的適應(yīng)度就要降低，使得分布比較分散的解能保留下的幾率加大。擁擠度比較算子：為了維持種群的多樣性，需要一個(gè)比較擁擠度的算子以確保算法能夠收斂到一個(gè)均勻分布的Pareto面上。由于經(jīng)過(guò)了排序和擁擠度計(jì)算，群體中每個(gè)個(gè)體都得到了兩個(gè)屬性：非支配序和擁擠度，則定義偏序關(guān)系（）：當(dāng)滿足條件，或滿足且時(shí)，定義。即如果兩個(gè)個(gè)體的非支配排序不同，取排序

54、號(hào)較小的個(gè)體；如果兩個(gè)個(gè)體在同一級(jí)，取周?chē)^不擁擠的個(gè)體。(3)引入精英策略，擴(kuò)大采樣空間。將父代種群與其產(chǎn)生的子代種群組合，共同競(jìng)爭(zhēng)產(chǎn)生下一代種群，有利于保持父代中的優(yōu)良個(gè)體進(jìn)入下一代，并通過(guò)對(duì)種群中所有個(gè)體的分層存放，使得最佳個(gè)體不會(huì)丟失，迅速提高種群水平。NSGA-算法的主流程：首先隨即初始化一個(gè)父代種群，并將所有個(gè)體按非支配關(guān)系排序，且指定一個(gè)適應(yīng)度值。然后采用選擇、交叉、變異算子產(chǎn)生下一代種群，大小也為，完成第一代進(jìn)化。在產(chǎn)生新種群后，將與其父代種群合并組成，此時(shí)種群大小為。然后進(jìn)行非支配排序，產(chǎn)生一系列非支配集并計(jì)算擁擠度，通常選擇前個(gè)個(gè)體組成，滿足且。在上圖中，由于子代和父代個(gè)體

55、都包含在中，則經(jīng)過(guò)非支配排序以后的非支配集中包含的個(gè)體是中最好的，所以先將放入新的父代種群中。如果的大小小于，則繼續(xù)向中填充，直到添加到時(shí)種群大小超出，對(duì)中的個(gè)體進(jìn)行擁擠度排序，取前個(gè)個(gè)體。使個(gè)體數(shù)量達(dá)到。然后通過(guò)遺傳算子產(chǎn)生新的子代種群。當(dāng)排序產(chǎn)生的非支配集的個(gè)體數(shù)目足夠填充時(shí)，就不必再繼續(xù)對(duì)剩下的部分排序了。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。算法流程圖：圖3-1 NSGA-的算法流程3.1.2MOGLS在MOGLS中，局部搜索過(guò)程應(yīng)用于通過(guò)遺傳操作所獲得每一個(gè)解。這種算法應(yīng)用在適應(yīng)度評(píng)價(jià)功能上應(yīng)用一種計(jì)算權(quán)值和的方式，即當(dāng)一對(duì)父代種群被選擇通過(guò)交叉變異去獲得新解時(shí)

56、使用這個(gè)功能。局部搜索過(guò)程應(yīng)用于新解而最大限度地發(fā)揮它的適應(yīng)度的效率24。這個(gè)算法的一大典型特性是無(wú)論何時(shí)選擇一組父代種群都要指定權(quán)值效率。每個(gè)解通過(guò)不同的權(quán)值矢量執(zhí)行。另一個(gè)特點(diǎn)是在局部搜索的過(guò)程中不需要計(jì)算當(dāng)前種群的所有鄰域解，只有少部分鄰域解被檢驗(yàn)避免在這個(gè)算法中消耗過(guò)多的所有可行解的計(jì)算時(shí)間。多目標(biāo)遺傳局部搜索算法試圖尋找多目標(biāo)最有問(wèn)題所有的非支配解，如果在一個(gè)多目標(biāo)問(wèn)題中一個(gè)解不被其他解支配，它叫做非劣解，一個(gè)多目標(biāo)問(wèn)題有許多非劣解。雜交算法的目的不是確定一個(gè)單一的最終解，而是試圖尋找這個(gè)多目標(biāo)問(wèn)題所有符合約束條件的最優(yōu)解。當(dāng)我們應(yīng)用GA算法解決多目標(biāo)問(wèn)題時(shí)，需要評(píng)價(jià)每個(gè)解的適應(yīng)度，我們通過(guò)計(jì)算個(gè)目標(biāo)權(quán)值和的方式定義一個(gè)解的適應(yīng)度函數(shù)： (2-5)是這個(gè)目標(biāo)的權(quán)值，它們符合以下條件：（1）。 （2） (2-6)如果我們使用連續(xù)的權(quán)值，通過(guò)GA局部搜索的方向是已經(jīng)固定的。連續(xù)權(quán)值策略和一個(gè)目標(biāo)的選擇方式都不能為尋找所有的多目標(biāo)問(wèn)題的非劣解高效的服務(wù)，這是因?yàn)楦鞣N搜索方向需要尋找多種非劣解。為了實(shí)現(xiàn)各個(gè)方向搜索，而提出這種算法。這個(gè)權(quán)值被定義為 (2-7) 其中，是隨機(jī)值。無(wú)論何時(shí)選擇