【正文】 華北電力大學畢業(yè)設計摘 要 在最近二十年，作為一類新興的優(yōu)化技術，多目標進化算法吸引了極大關注，許多學者提出了不同的算法，多目標進化算法已經(jīng)成為處理多目標工程設計和科學研究問題的重要方法。許多MOEA的方面被廣泛地調(diào)研，然而一些問題仍然沒有被很好地受到關注。例如，隨著這類算法的快速發(fā)展，對算法之間性能進行比較變得越來越重要。本文分析總結了兩種目前流行的所目標進化算法的基本原理，并通過算例來比較它們的性能。本文主要工作內(nèi)容如下：1. 簡要回顧了多目標進化算法的發(fā)展歷史，按照算法原理與進化模式將算法分類。2. 簡述多目標問題及進化算法的相關技術，詳細分析了NSGAII算法和MOGLS算法。3. 分別利用NSGAII算法和MOGLS算法對算例進行求解，并用C指標對兩種算法的結果進行評價，得出它們各自的優(yōu)缺點。多目標問題仍向算法設計，呈現(xiàn)和執(zhí)行提出挑戰(zhàn)。不斷變化的多目標問題很少被考慮到它的時變特性，對此有效的多目標進化算法很罕見，多目標進化算法的結合量計算和有區(qū)別的進化還始終停留在初級階段。多目標進化算法的應用應該在未來不斷地延續(xù)，MOEA的理論分析比它本身更復雜而且應該通過主要從事計算機和數(shù)學研究人員的努力工作來解決。關鍵詞：多目標優(yōu)化，進化算法，適應度計算，精英保留，局部搜索 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章 多目標進化算法 6 多目標優(yōu)化基本概念 6 6 7 7 7 9 NSGAⅡ和MOGLS算法 12!異常的公式結尾 14 11附 錄 26致 謝 33第3章 優(yōu)化算例及分析………………………………………………30……………………………………20 ………………………………………………20 …………………………………………25 ……………………………………………………35 ……………………………………………………40………………………………………………40 ………………………………………………45第 4 章 總結……………………………………………………………30 …………………………………………………… 30 ……………………………………………………35 ……………………………………………………40………………………………………………40 ………………………………………………45參考文獻……………………………………………………………………50附 錄 ……………………………………………………………………51致 謝 ……………………………………………………………………52華北電力大學本科畢業(yè)設計（論文）第1章 緒 論許多科學研究和工程實踐中遇到的優(yōu)化問題，通常需要綜合考慮多方面因素，這就要求在解決問題時同時對多個目標進行優(yōu)化，這樣的問題被稱為多目標優(yōu)化問題(MultiObjective Optimization Problem, MOP)，它們有許多沖突的目標。有時目標之間是相輔相成、互相促進的，但更多的時候，目標之間是相互矛盾、此消彼長的。因此在絕大多數(shù)情況下，若想達到總目標的最優(yōu)，就需要對各個目標進行綜合考慮、折中處理，所得到的解是一組基于Pareto最優(yōu)性概念的非劣解集[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)化問題(MultiObjective Optimization Problem, MOP)，大多數(shù)工程和科學問題是多目標最優(yōu)問題。多目標優(yōu)化問題的各目標之間通過決策變量相互制約,對其中一個目標優(yōu)化必須以其它目標作為代價,而且各目標的單位又往往不一致,因此很難客觀地評價多目標問題解的優(yōu)劣性。例如,在設計一座橋梁時,我們一方面希望建設橋梁的費用最小,另一方面希望橋梁具有最大的安全性。與單目標優(yōu)化問題的本質(zhì)區(qū)別在于,多目標優(yōu)化問題的解不是唯一的,而是存在一個最優(yōu)解集合,集合中元素稱為Pareto 最優(yōu)或非劣最優(yōu)(nondominance) 。求解它們需要用不同于單目標優(yōu)化的數(shù)學工具,甚至最優(yōu)的含義也發(fā)生了變化。由于它們有許多沖突的目標，因此若想達到總目標的最優(yōu)，就需要對各個目標進行綜合考慮、折中處理，所以如何進行綜合與折中就成為解決問題的關鍵。多目標進化算法(MultiObjective Evolutionary Algorithm, MOEA)就是一類可以有效解決這種問題的優(yōu)化技術[3]。它的主要思想是將進化算法的概念引入到多目標優(yōu)化領域，對多目標優(yōu)化問題同樣采用進化操作方式，但算法由單目標優(yōu)化問題求取一個最優(yōu)解，轉(zhuǎn)變?yōu)槎嗄繕藘?yōu)化問題中求取一個最優(yōu)解集，該解集稱為Pareto最優(yōu)解集。最優(yōu)解集中的每個解，理論上都是“最優(yōu)解”，而在實際應用中，可以根據(jù)決策需要選擇其中一個解作為最終決策方案，實現(xiàn)最優(yōu)化的目的。多目標進化算法是一門新興的學科，理論與算法并不完善，尚處于發(fā)展階段。然而，它對工程項目具有重要的實踐意義，因此在過去的十多年間涌現(xiàn)出許多新的改進算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標進化算法。而對算法性能進行比較和評價就成為一個重要的核心問題，引起了諸多學者的研究興趣。優(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ù)整合成單目標，將問題轉(zhuǎn)變?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)及其改進算法NSGAII[7]等. 其中NSGA的改進算法NSGAII是帶有精英策略的非支配排序遺傳算法，改進了先前算法的不足之處，提高了算法的運算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。自Scharfer提出VEGA起，多目標進化算法的發(fā)展經(jīng)歷了由基于單目標子群體優(yōu)化的算法到基于Pareto最優(yōu)性指導的分級策略與適應值共享策略算法的發(fā)展歷程。按照算法原理與進化模式劃分，現(xiàn)有多目標進化算法可分如下四大類：第一類算法是早期基于單目標群體優(yōu)化的MOGA。這類算法通過加權或劃分子群體進化等方法將MOP轉(zhuǎn)化為不同的SOP，然后借助現(xiàn)有單目標遺傳算法對轉(zhuǎn)化后的SOP進行求解，最后對進化獲得的解進行分析，篩選出非劣解集。由于這類算法的設計思想是基于單目標遺傳算法的進化策略，因此它的優(yōu)點是算法容易實現(xiàn)；其不足是，基于單目標子群體優(yōu)化的算法很難搜索到嚴格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點。代表算法有VEGA、WBGA、DM等。Ishibuchi、Murata等人1996年提出的MOGLS是在隨機權策略的WBGA中引入局部搜索的改進算法，其本質(zhì)屬于這類算法[8]。第二類算法是基于Goldberg提出的適應值分級和共享策略的多目標遺傳算法。這類算法在適應值設計中鼓勵非劣解等級優(yōu)先個體和同一等級內(nèi)較為稀疏個體以較大概率出現(xiàn)在后代群體中。由于這類算法是基于Pareto概念的MOGA，因此，它的優(yōu)點是可以通過單次優(yōu)化獲得一組靠近真實非劣解前沿的非劣解集；但由于算法未考慮進化過程中精英個體的保留，因此解的收斂速度及收斂性能不夠穩(wěn)健。代表算法有MOGA、NSGA和NPGA等。第三類算法是由第二類算法發(fā)展起來的精英保留策略MOGA。這類算法通過在進化過程中引入外部伴隨群體對群體中的精英個體加以保留，同時采用更加成熟的適應值設計策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。這類算法的不足之處是，