【正文】 華北電力大學(xué)畢業(yè)設(shè)計(jì)摘 要 在最近二十年，作為一類新興的優(yōu)化技術(shù)，多目標(biāo)進(jìn)化算法吸引了極大關(guān)注，許多學(xué)者提出了不同的算法，多目標(biāo)進(jìn)化算法已經(jīng)成為處理多目標(biāo)工程設(shè)計(jì)和科學(xué)研究問題的重要方法。許多MOEA的方面被廣泛地調(diào)研，然而一些問題仍然沒有被很好地受到關(guān)注。例如，隨著這類算法的快速發(fā)展，對(duì)算法之間性能進(jìn)行比較變得越來(lái)越重要。本文分析總結(jié)了兩種目前流行的所目標(biāo)進(jìn)化算法的基本原理，并通過算例來(lái)比較它們的性能。本文主要工作內(nèi)容如下：1. 簡(jiǎn)要回顧了多目標(biāo)進(jìn)化算法的發(fā)展歷史，按照算法原理與進(jìn)化模式將算法分類。2. 簡(jiǎn)述多目標(biāo)問題及進(jìn)化算法的相關(guān)技術(shù)，詳細(xì)分析了NSGAII算法和MOGLS算法。3. 分別利用NSGAII算法和MOGLS算法對(duì)算例進(jìn)行求解，并用C指標(biāo)對(duì)兩種算法的結(jié)果進(jìn)行評(píng)價(jià)，得出它們各自的優(yōu)缺點(diǎn)。多目標(biāo)問題仍向算法設(shè)計(jì)，呈現(xiàn)和執(zhí)行提出挑戰(zhàn)。不斷變化的多目標(biāo)問題很少被考慮到它的時(shí)變特性，對(duì)此有效的多目標(biāo)進(jì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)該通過主要從事計(jì)算機(jī)和數(shù)學(xué)研究人員的努力工作來(lái)解決。關(guān)鍵詞：多目標(biāo)優(yōu)化，進(jìn)化算法，適應(yīng)度計(jì)算，精英保留，局部搜索 2ABSTRACTIn the past two decades, as a new subject， MultiObjective Evolutionary Algorithm (MOEA) has attracted much attention, the numerous algorithms have been proposed and MOEA has bee the important approach to deal with multiobjective 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 pare the performance between the algorithms have bee 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: brief review of the history and current studies of MOEA was brought mon algorithms have been distributed into several sorts. 2 MOP and the relational technique of MOEA was introduced NSGAII and MOGLS were expounded in detail.3 NSGAII and MOGLS were used for solving the same MultiObjective 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 timevarying nature. The effective pMOEA is very sparse and the MOEA bining quantum puting 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 plicated than MOEA itself and should be considered through the hard works of researchers majoring in puters and mathematics et al.KEY WORDS: multiobjective optimization,evolutionary algorithm,fitness calculating,elitism duplication,local search 目 錄摘 要 ……………………………………………………………..…………ⅠABSTRACT………………………………………………….…………………Ⅱ第1章 緒 論 1 1 2 4第2章 多目標(biāo)進(jìn)化算法 6 多目標(biāo)優(yōu)化基本概念 6 6 7 7 7 9 NSGAⅡ和MOGLS算法 12!異常的公式結(jié)尾 14 11附 錄 26致 謝 33第3章 優(yōu)化算例及分析………………………………………………30……………………………………20 ………………………………………………20 …………………………………………25 ……………………………………………………35 ……………………………………………………40………………………………………………40 ………………………………………………45第 4 章 總結(jié)……………………………………………………………30 …………………………………………………… 30 ……………………………………………………35 ……………………………………………………40………………………………………………40 ………………………………………………45參考文獻(xiàn)……………………………………………………………………50附 錄 ……………………………………………………………………51致 謝 ……………………………………………………………………52華北電力大學(xué)本科畢業(yè)設(shè)計(jì)（論文）第1章 緒 論許多科學(xué)研究和工程實(shí)踐中遇到的優(yōu)化問題，通常需要綜合考慮多方面因素，這就要求在解決問題時(shí)同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化，這樣的問題被稱為多目標(biāo)優(yōu)化問題(MultiObjective 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)行綜合與折中就成為解決問題的關(guān)鍵。生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得品種不斷的到改良，這種生命現(xiàn)象叫做進(jìn)化。進(jìn)化算法(Evolutionary Algorithm, EA)是一種通過模擬生物進(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ù)雜的非線性問題，并且由于這類算法具有通用性，因而被廣泛地應(yīng)用于單個(gè)目標(biāo)的復(fù)雜系統(tǒng)優(yōu)化問題。然而，人們?cè)谇蠼猬F(xiàn)實(shí)世界許多優(yōu)化問題時(shí)，通常不追求單一目標(biāo)的最優(yōu)性，這就要求在解決問題時(shí)同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化和權(quán)衡，有時(shí)目標(biāo)之間是相輔相成、互相促進(jìn)的，但更多的時(shí)候，目標(biāo)之間是相互矛盾、此消彼長(zhǎng)的，這樣的問題被稱為多目標(biāo)優(yōu)化問題(MultiObjective Optimization Problem, MOP)，大多數(shù)工程和科學(xué)問題是多目標(biāo)最優(yōu)問題。多目標(biāo)優(yōu)化問題的各目標(biāo)之間通過決策變量相互制約,對(duì)其中一個(gè)目標(biāo)優(yōu)化必須以其它目標(biāo)作為代價(jià),而且各目標(biāo)的單位又往往不一致,因此很難客觀地評(píng)價(jià)多目標(biāo)問題解的優(yōu)劣性。例如,在設(shè)計(jì)一座橋梁時(shí),我們一方面希望建設(shè)橋梁的費(fèi)用最小,另一方面希望橋梁具有最大的安全性。與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別在于,多目標(biāo)優(yōu)化問題的解不是唯一的,而是存在一個(gè)最優(yōu)解集合,集合中元素稱為Pareto 最優(yōu)或非劣最優(yōu)(nondominance) 。求解它們需要用不同于單目標(biāo)優(yōu)化的數(shù)學(xué)工具,甚至最優(yōu)的含義也發(fā)生了變化。由于它們有許多沖突的目標(biāo)，因此若想達(dá)到總目標(biāo)的最優(yōu)，就需要對(duì)各個(gè)目標(biāo)進(jìn)行綜合考慮、折中處理，所以如何進(jìn)行綜合與折中就成為解決問題的關(guān)鍵。多目標(biāo)進(jìn)化算法(MultiObjective Evolutionary Algorithm, MOEA)就是一類可以有效解決這種問題的優(yōu)化技術(shù)[3]。它的主要思想是將進(jìn)化算法的概念引入到多目標(biāo)優(yōu)化領(lǐng)域，對(duì)多目標(biāo)優(yōu)化問題同樣采用進(jìn)化操作方式，但算法由單目標(biāo)優(yōu)化問題求取一個(gè)最優(yōu)解，轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問題中求取一個(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)化算法是一門新興的學(xué)科，理論與算法并不完善，尚處于發(fā)展階段。然而，它對(duì)工程項(xiàng)目具有重要的實(shí)踐意義，因此在過去的十多年間涌現(xiàn)出許多新的改進(jìn)算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標(biāo)進(jìn)化算法。而對(duì)算法性能進(jìn)行比較和評(píng)價(jià)就成為一個(gè)重要的核心問題，引起了諸多學(xué)者的研究興趣。優(yōu)化問題一直是倍受人們關(guān)注的問題，自1950 年以來(lái),運(yùn)籌學(xué)研究人員已經(jīng)建立了許多方法解決MOP。在專業(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)化問題方面取得了很好的成果，但面對(duì)復(fù)雜的多目標(biāo)優(yōu)化問題，傳統(tǒng)的遺傳算法就顯得力不從心。例如在現(xiàn)代能源系統(tǒng)生產(chǎn)過程參數(shù)的優(yōu)化[4]設(shè)計(jì)中經(jīng)常會(huì)遇到多目標(biāo)函數(shù)的優(yōu)化問題，使用經(jīng)典的多目標(biāo)優(yōu)化方法通常把多個(gè)目標(biāo)函數(shù)整合成單目標(biāo)，將問題轉(zhuǎn)變?yōu)閱文繕?biāo)優(yōu)化問題，然后采用單目標(biāo)的優(yōu)化技術(shù)求解。但這些方法存在：只能得到一個(gè)解；多個(gè)目標(biāo)函數(shù)之間量綱不同難以統(tǒng)一；加權(quán)值的分配帶有較強(qiáng)的主觀性；加權(quán)的目標(biāo)函數(shù)之間通過決策變量相互制約，最終優(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年，此后眾多的研究人員通過對(duì)遺傳算法進(jìn)行改造，相繼提出了多種用于解決多目標(biāo)優(yōu)化問題的遺傳算法，如基于向量評(píng)估的遺傳算法(VEGA) [5]，小組決勝遺傳算法(NPGA) [6]，非支配排序遺傳算法(NSGA)及其改進(jìn)算法NSGAII[7]等. 其中NSGA的改進(jìn)算法NSGAII是帶有精英策略的非支配排序遺傳算法，改進(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)化算法可分如下四大類：第一類算法是早期基于單目標(biāo)群體優(yōu)化的MOGA。這類算法通過加權(quán)或劃分子群體進(jìn)化等方法將MOP轉(zhuǎn)化為不同的SOP，然后借助現(xiàn)有單目標(biāo)遺傳算法對(duì)轉(zhuǎn)化后的SOP進(jìn)行求解，最后對(duì)進(jìn)化獲得的解進(jìn)行分析，篩選出非劣解集。由于這類算法的設(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ì)屬于這類算法[8]。第二類算法是基于Goldberg提出的適應(yīng)值分級(jí)和共享策略的多目標(biāo)遺傳算法。這類算法在適應(yīng)值設(shè)計(jì)中鼓勵(lì)非劣解等級(jí)優(yōu)先個(gè)體和同一等級(jí)內(nèi)較為稀疏個(gè)體以較大概率出現(xiàn)在后代群體中。由于這類算法是基于Pareto概念的MOGA，因此，它的優(yōu)點(diǎn)是可以通過單次優(yōu)化獲得一組靠近真實(shí)非劣解前沿的非劣解集；但由于算法未考慮進(jìn)化過程中精英個(gè)體的保留，因此解的收斂速度及收斂性能不夠穩(wěn)健。代表算法有MOGA、NSGA和NPGA等。第三類算法是由第二類算法發(fā)展起來(lái)的精英保留策略MOGA。這類算法通過在進(jìn)化過程中引入外部伴隨群體對(duì)群體中的精英個(gè)體加以保留，同時(shí)采用更加成熟的適應(yīng)值設(shè)計(jì)策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。這類算法的不足之處是，