【正文】 何進(jìn)行綜合與折中就成為解決問題的關(guān)鍵。多目標(biāo)優(yōu)化問題的各目標(biāo)之間通過決策變量相互制約,對(duì)其中一個(gè)目標(biāo)優(yōu)化必須以其它目標(biāo)作為代價(jià),而且各目標(biāo)的單位又往往不一致,因此很難客觀地評(píng)價(jià)多目標(biāo)問題解的優(yōu)劣性。生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得品種不斷的到改良，這種生命現(xiàn)象叫做進(jìn)化。多目標(biāo)進(jìn)化算法的應(yīng)用應(yīng)該在未來不斷地延續(xù)，MOEA的理論分析比它本身更復(fù)雜而且應(yīng)該通過主要從事計(jì)算機(jī)和數(shù)學(xué)研究人員的努力工作來解決。2. 簡述多目標(biāo)問題及進(jìn)化算法的相關(guān)技術(shù)，詳細(xì)分析了NSGAII算法和MOGLS算法。許多MOEA的方面被廣泛地調(diào)研，然而一些問題仍然沒有被很好地受到關(guān)注。例如，隨著這類算法的快速發(fā)展，對(duì)算法之間性能進(jìn)行比較變得越來越重要。3. 分別利用NSGAII算法和MOGLS算法對(duì)算例進(jìn)行求解，并用C指標(biāo)對(duì)兩種算法的結(jié)果進(jìn)行評(píng)價(jià)，得出它們各自的優(yōu)缺點(diǎn)。關(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)。進(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)等幾種方法[2]。例如,在設(shè)計(jì)一座橋梁時(shí),我們一方面希望建設(shè)橋梁的費(fèi)用最小,另一方面希望橋梁具有最大的安全性。多目標(biāo)進(jìn)化算法(MultiObjective Evolutionary Algorithm, MOEA)就是一類可以有效解決這種問題的優(yōu)化技術(shù)[3]。然而，它對(duì)工程項(xiàng)目具有重要的實(shí)踐意義，因此在過去的十多年間涌現(xiàn)出許多新的改進(jìn)算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標(biāo)進(jìn)化算法。遺傳算法自出現(xiàn)以來在許多領(lǐng)域得到了廣泛的應(yīng)用，在解決簡單的單目標(biāo)優(yōu)化問題方面取得了很好的成果，但面對(duì)復(fù)雜的多目標(biāo)優(yōu)化問題，傳統(tǒng)的遺傳算法就顯得力不從心。有些方法要求目標(biāo)函數(shù)和約束條件可微。按照算法原理與進(jìn)化模式劃分，現(xiàn)有多目標(biāo)進(jìn)化算法可分如下四大類：第一類算法是早期基于單目標(biāo)群體優(yōu)化的MOGA。Ishibuchi、Murata等人1996年提出的MOGLS是在隨機(jī)權(quán)策略的WBGA中引入局部搜索的改進(jìn)算法，其本質(zhì)屬于這類算法[8]。代表算法有MOGA、NSGA和NPGA等。代表算法有NPGAII、NSGAII、PAES和SPEA等[9]。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)、又能維持群體多樣性，因此，在算法設(shè)計(jì)時(shí)往往設(shè)置了許多控制參數(shù)對(duì)算法性能進(jìn)行調(diào)整，這又導(dǎo)致在求解問題時(shí)常常需要借助大量試驗(yàn)計(jì)算分析確定進(jìn)化參數(shù)，因此算法性能不夠穩(wěn)健。而考慮偏好關(guān)系對(duì)遺傳進(jìn)化的影響，大多是用模糊集方法進(jìn)行偏好信息的處理，而進(jìn)一步利用偏好對(duì)進(jìn)化進(jìn)行指導(dǎo)或通過進(jìn)化引導(dǎo)偏好的交互式多目標(biāo)進(jìn)化算法還僅僅處于概念研究階段，距算法實(shí)現(xiàn)尚有較大差距。目前絕大多數(shù)多目標(biāo)進(jìn)化算法是排序選擇法和后決策技術(shù)類型的。由于本文需要對(duì)多目標(biāo)進(jìn)化算法的結(jié)構(gòu)進(jìn)行深入的分析，所以需要在此選擇一個(gè)代表性的算法，通過該算法的簡介，來描述一下多目標(biāo)進(jìn)化算法的一些基本概念和工作原理。MOGLS是Ishibuchi和Murata兩位學(xué)者提出的。對(duì)于多目標(biāo)優(yōu)化問題, 由于其待優(yōu)化的各個(gè)子目標(biāo)一般是相互沖突的, 因此需要定義解個(gè)體間的優(yōu)劣關(guān)系, 以便對(duì)候選解進(jìn)行評(píng)價(jià)與取舍。 （2） 至少存在一個(gè)子目標(biāo),使比好。定義2( Pareto 非支配集)。因此，滿足這種最優(yōu)性的“最優(yōu)解”往往不是單個(gè)解，而是一組滿足上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱作非劣解集（Pareto Solutions Set）或非受控解集(nondominated solutions set)；非劣解對(duì)應(yīng)的目標(biāo)值在目標(biāo)空間中稱為非劣點(diǎn)；最優(yōu)解集在優(yōu)化目標(biāo)空間構(gòu)成的分布稱作非劣解前沿。MOP問題包含多個(gè)待優(yōu)化的子目標(biāo)，通常EAs用于多目標(biāo)優(yōu)化時(shí)必須考慮兩個(gè)關(guān)鍵問題：(1)為了保證朝Pareto最優(yōu)集的方向搜索，如何實(shí)施適應(yīng)度賦值和選擇。在進(jìn)化的每一代中參數(shù)呈現(xiàn)有規(guī)律的變化，但在該代操作過程中保持不變，常見的進(jìn)化加權(quán)法，個(gè)體的評(píng)估使用確定的加權(quán)組合，所有個(gè)體都有一個(gè)適應(yīng)度值，保證了搜索方向朝最優(yōu)解邁進(jìn)。這種策略存在的問題是進(jìn)化結(jié)果容易偏向某些極端邊界解，并且對(duì)Pareto最優(yōu)前端的非凸部敏感。單目標(biāo)優(yōu)化中的目標(biāo)函數(shù)常與適應(yīng)度函數(shù)相同，但MOP問題中的適應(yīng)度賦值和選擇必須考慮幾個(gè)子目標(biāo)，MOEAs必須根據(jù)個(gè)體間的Pareto優(yōu)勝關(guān)系和其他信息為個(gè)體確定適應(yīng)度值，這種適應(yīng)度值和每個(gè)目標(biāo)函數(shù)的具體大小沒有直接關(guān)系?；赑areto優(yōu)勝關(guān)系的選擇方法已經(jīng)被廣大研究者采納，現(xiàn)已有多種基于Pareto的適應(yīng)度賦值方案，其中基于種群個(gè)體級(jí)別排序的適應(yīng)度賦值方法是較常見的一種方法。(3)具有相同序號(hào)的個(gè)體進(jìn)行適應(yīng)度共享算子操作，即通過除以相同序號(hào)的個(gè)體數(shù)目得到新的適應(yīng)度值，另外，也可以給不同序號(hào)的個(gè)體分配固定不變的適應(yīng)度值。如果單純從群體多樣性出發(fā)，群體規(guī)模應(yīng)該越大越好，但群體規(guī)模太大會(huì)帶來若干弊病：一是從計(jì)算效率來看，群體越大，導(dǎo)致其適應(yīng)度評(píng)估次數(shù)增加，引起計(jì)算量的增加，從而影響算法效能；二是群體中個(gè)體生存下來的選擇概率大多采用和適應(yīng)度成比例的方法，當(dāng)群體中個(gè)體非常多時(shí)，少量適應(yīng)度很高的個(gè)體會(huì)被選擇而生存下來，大多數(shù)個(gè)體被淘汰，嚴(yán)重影響交叉操作。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點(diǎn)，大多數(shù)MOEAs在當(dāng)代群體中維持多樣性是在選擇過程中結(jié)合了密度信息，即個(gè)體在其鄰域范圍內(nèi)所占的密度越高被選擇復(fù)制的機(jī)會(huì)越小。(2)基于鄰域解數(shù)目的評(píng)價(jià)策略：基于鄰域解數(shù)目的評(píng)價(jià)策略是以評(píng)價(jià)解為核心、包含一定數(shù)量鄰域解的鄰域半徑為指標(biāo)，優(yōu)先保留鄰域半徑較大的個(gè)體即較稀疏的解個(gè)體。多目標(biāo)進(jìn)化算法與單目標(biāo)進(jìn)化算法類似，為了提高群體多樣性，在算法過程中盡量采用小生境（Niche）共享技術(shù)，使得在一個(gè)群體內(nèi)可以形成在多目標(biāo)問題上分布均勻的非劣最優(yōu)解集。遺傳算法是基于隨機(jī)進(jìn)化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標(biāo)遺傳算法大都引入了精英保留策略。通常采用優(yōu)勝準(zhǔn)則來確定最優(yōu)個(gè)體。MOEAs的最優(yōu)個(gè)體大多利用優(yōu)勝關(guān)系和密度兩者的組合來進(jìn)行挑選，最優(yōu)個(gè)體保存在每代的伴隨群體中。 (2) 產(chǎn)生初始種群：隨機(jī)地產(chǎn)生一個(gè)由個(gè)個(gè)體組成的種群，該種群代表一些可能解的集合?？梢栽O(shè)定進(jìn)化的最大代數(shù)，當(dāng)進(jìn)化到最大代數(shù)時(shí)，算法終止運(yùn)行。在此操作中，適應(yīng)于生存環(huán)境的優(yōu)良個(gè)體將有更多的機(jī)會(huì)繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。對(duì)產(chǎn)生的新一代群體重新進(jìn)行評(píng)價(jià)、選擇、雜交和變異。對(duì)一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問題，一般可以按照上述步驟來構(gòu)造求解該問題的遺傳算法。算法的效率是指算法自身的時(shí)間復(fù)雜度和空間復(fù)雜度，也即算法運(yùn)算時(shí)間的長短和資源消耗的多少；算法的效果是指算法求得的解集的質(zhì)量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應(yīng)用范圍和穩(wěn)定性，也即是否對(duì)多種問題都有很好的求解能力、是否求解問題時(shí)總是相對(duì)穩(wěn)定的。下面分別對(duì)二者加以介紹。如式(31)所示。以空間評(píng)價(jià)方法為例，該方法又被稱為Delta指標(biāo)(Schott, 1995) [22]，用來計(jì)算解的分布信息的，如式(32)所示。但是由于多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，多目標(biāo)進(jìn)化計(jì)算的理論基礎(chǔ)尚未成熟，算法收斂性的理論證明對(duì)有限時(shí)間內(nèi)的收斂性分析較少，而時(shí)間無窮大的收斂性并沒有工程實(shí)際的應(yīng)用價(jià)值。但是，由于這種方法可以簡單直觀的反映出算法的一些特性，所以在分析算法性能領(lǐng)域的應(yīng)用十分廣泛。第三部分給出了多目標(biāo)進(jìn)化算法的一般流程，這是所有