【正文】 端的非凸部敏感。此方法通過(guò)在不同進(jìn)化代之間更換優(yōu)化目標(biāo)每次優(yōu)化一個(gè)目標(biāo)，使算法群體每次運(yùn)行得到一個(gè)非劣解，從而通過(guò)多次運(yùn)行找到優(yōu)化問(wèn)題的非劣解集。在進(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)。在已有研究中，多目標(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)化。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)度賦值和選擇。從決策者的立場(chǎng)來(lái)看，一般認(rèn)為每對(duì)候選解具有以下比較關(guān)系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。因此，滿(mǎn)足這種最優(yōu)性的“最優(yōu)解”往往不是單個(gè)解，而是一組滿(mǎn)足上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱(chēng)作非劣解集（Pareto Solutions Set）或非受控解集(nondominated solutions set)；非劣解對(duì)應(yīng)的目標(biāo)值在目標(biāo)空間中稱(chēng)為非劣點(diǎn)；最優(yōu)解集在優(yōu)化目標(biāo)空間構(gòu)成的分布稱(chēng)作非劣解前沿。 由 中的所有非支配個(gè)體構(gòu)成的子集稱(chēng)為 的非支配集。定義2( Pareto 非支配集)。此時(shí)稱(chēng) 為非支配的( non dominated), 為被支配的( dominated) 。 （2） 至少存在一個(gè)子目標(biāo),使比好。定義1 ( 個(gè)體的Pareto 支配關(guān)系) 。對(duì)于多目標(biāo)優(yōu)化問(wèn)題, 由于其待優(yōu)化的各個(gè)子目標(biāo)一般是相互沖突的, 因此需要定義解個(gè)體間的優(yōu)劣關(guān)系, 以便對(duì)候選解進(jìn)行評(píng)價(jià)與取舍。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)的方法往往不能保證所得非劣解集分布的均勻性。MOGLS是Ishibuchi和Murata兩位學(xué)者提出的。NSGAII算法首先隨機(jī)產(chǎn)生一個(gè)初始種群，對(duì)種群通過(guò)采用輪盤(pán)賭的方式選擇、交叉和變異操作獲得新的種群，將種群中的個(gè)體構(gòu)造其Pareto 邊界集，并根據(jù)個(gè)體間的聚集距離，建立偏序關(guān)系，最終從偏序關(guān)系中選擇原始種群規(guī)模大小的個(gè)體，組成新的種群，完成了一次進(jìn)化操作。由于本文需要對(duì)多目標(biāo)進(jìn)化算法的結(jié)構(gòu)進(jìn)行深入的分析，所以需要在此選擇一個(gè)代表性的算法，通過(guò)該算法的簡(jiǎn)介，來(lái)描述一下多目標(biāo)進(jìn)化算法的一些基本概念和工作原理。 Thiele 2001)和NSGA/NSGAII (Srinivas amp。目前絕大多數(shù)多目標(biāo)進(jìn)化算法是排序選擇法和后決策技術(shù)類(lèi)型的。 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類(lèi)[11]：前決策（先驗(yàn)式）、后決策（后驗(yàn)式）和交互式?jīng)Q策，這是按照用戶(hù)的人工決策信息作用于算法的時(shí)間先后劃分的。而考慮偏好關(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)尚有較大差距。除了上述四類(lèi)算法外，一些學(xué)者在演化策略中引入偏好分級(jí)或適應(yīng)值分享機(jī)制獲取滿(mǎn)意解。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)、又能維持群體多樣性，因此，在算法設(shè)計(jì)時(shí)往往設(shè)置了許多控制參數(shù)對(duì)算法性能進(jìn)行調(diào)整，這又導(dǎo)致在求解問(wèn)題時(shí)常常需要借助大量試驗(yàn)計(jì)算分析確定進(jìn)化參數(shù)，因此算法性能不夠穩(wěn)健。這類(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)。代表算法有NPGAII、NSGAII、PAES和SPEA等[9]。這類(lèi)算法通過(guò)在進(jìn)化過(guò)程中引入外部伴隨群體對(duì)群體中的精英個(gè)體加以保留，同時(shí)采用更加成熟的適應(yīng)值設(shè)計(jì)策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。代表算法有MOGA、NSGA和NPGA等。這類(lèi)算法在適應(yīng)值設(shè)計(jì)中鼓勵(lì)非劣解等級(jí)優(yōu)先個(gè)體和同一等級(jí)內(nèi)較為稀疏個(gè)體以較大概率出現(xiàn)在后代群體中。Ishibuchi、Murata等人1996年提出的MOGLS是在隨機(jī)權(quán)策略的WBGA中引入局部搜索的改進(jìn)算法，其本質(zhì)屬于這類(lèi)算法[8]。由于這類(lèi)算法的設(shè)計(jì)思想是基于單目標(biāo)遺傳算法的進(jìn)化策略，因此它的優(yōu)點(diǎn)是算法容易實(shí)現(xiàn)；其不足是，基于單目標(biāo)子群體優(yōu)化的算法很難搜索到嚴(yán)格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點(diǎn)。按照算法原理與進(jìn)化模式劃分，現(xiàn)有多目標(biāo)進(jìn)化算法可分如下四大類(lèi)：第一類(lèi)算法是早期基于單目標(biāo)群體優(yōu)化的MOGA。進(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)算法NSGAII[7]等. 其中NSGA的改進(jìn)算法NSGAII是帶有精英策略的非支配排序遺傳算法，改進(jìn)了先前算法的不足之處，提高了算法的運(yùn)算速度和魯棒性，并保證了非劣最優(yōu)解的均勻分布。有些方法要求目標(biāo)函數(shù)和約束條件可微。但這些方法存在：只能得到一個(gè)解；多個(gè)目標(biāo)函數(shù)之間量綱不同難以統(tǒng)一；加權(quán)值的分配帶有較強(qiáng)的主觀(guān)性；加權(quán)的目標(biāo)函數(shù)之間通過(guò)決策變量相互制約，最終優(yōu)化目標(biāo)僅為各目標(biāo)之和，各目標(biāo)的優(yōu)化進(jìn)度不可操作等缺點(diǎn)。遺傳算法自出現(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)的遺傳算法就顯得力不從心。優(yōu)化問(wèn)題一直是倍受人們關(guān)注的問(wèn)題，自1950 年以來(lái),運(yùn)籌學(xué)研究人員已經(jīng)建立了許多方法解決MOP。然而，它對(duì)工程項(xiàng)目具有重要的實(shí)踐意義，因此在過(guò)去的十多年間涌現(xiàn)出許多新的改進(jìn)算法，人們不斷地尋找是否存在優(yōu)化效果更好的多目標(biāo)進(jìn)化算法。最優(yōu)解集中的每個(gè)解，理論上都是“最優(yōu)解”，而在實(shí)際應(yīng)用中，可以根據(jù)決策需要選擇其中一個(gè)解作為最終決策方案，實(shí)現(xiàn)最優(yōu)化的目的。多目標(biāo)進(jìn)化算法(MultiObjective Evolutionary Algorithm, MOEA)就是一類(lèi)可以有效解決這種問(wèn)題的優(yōu)化技術(shù)[3]。求解它們需要用不同于單目標(biāo)優(yōu)化的數(shù)學(xué)工具,甚至最優(yōu)的含義也發(fā)生了變化。例如,在設(shè)計(jì)一座橋梁時(shí),我們一方面希望建設(shè)橋梁的費(fèi)用最小,另一方面希望橋梁具有最大的安全性。然而，人們?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)題被稱(chēng)為多目標(biāo)優(yōu)化問(wèn)題(MultiObjective Optimization Problem, MOP)，大多數(shù)工程和科學(xué)問(wèn)題是多目標(biāo)最優(yōu)問(wè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]。因此在絕大多數(shù)情況下，若想達(dá)到總目標(biāo)的最優(yōu)，就需要對(duì)各個(gè)目標(biāo)進(jìn)行綜合考慮、折中處理，所得到的解是一組基于Pareto最優(yōu)性概念的非劣解集[1]，所以如何進(jìn)行綜合與折中就成為解決問(wèn)題的關(guā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)化問(wèn)題，通常需要綜合考慮