【正文】 ；加權(quán)值的分配帶有較強的主觀性；加權(quán)的目標函數(shù)之間通過決策變量相互制約，最終優(yōu)化目標僅為各目標之和，各目標的優(yōu)化進度不可操作等缺點。優(yōu)化問題一直是倍受人們關(guān)注的問題，自1950 年以來,運籌學(xué)研究人員已經(jīng)建立了許多方法解決MOP。最優(yōu)解集中的每個解，理論上都是“最優(yōu)解”，而在實際應(yīng)用中，可以根據(jù)決策需要選擇其中一個解作為最終決策方案，實現(xiàn)最優(yōu)化的目的。求解它們需要用不同于單目標優(yōu)化的數(shù)學(xué)工具,甚至最優(yōu)的含義也發(fā)生了變化。然而，人們在求解現(xiàn)實世界許多優(yōu)化問題時，通常不追求單一目標的最優(yōu)性，這就要求在解決問題時同時對多個目標進行優(yōu)化和權(quán)衡，有時目標之間是相輔相成、互相促進的，但更多的時候，目標之間是相互矛盾、此消彼長的，這樣的問題被稱為多目標優(yōu)化問題(MultiObjective Optimization Problem, MOP)，大多數(shù)工程和科學(xué)問題是多目標最優(yōu)問題。因此在絕大多數(shù)情況下，若想達到總目標的最優(yōu)，就需要對各個目標進行綜合考慮、折中處理，所得到的解是一組基于Pareto最優(yōu)性概念的非劣解集[1]，所以如何進行綜合與折中就成為解決問題的關(guān)鍵。不斷變化的多目標問題很少被考慮到它的時變特性，對此有效的多目標進化算法很罕見，多目標進化算法的結(jié)合量計算和有區(qū)別的進化還始終停留在初級階段。本文主要工作內(nèi)容如下：1. 簡要回顧了多目標進化算法的發(fā)展歷史，按照算法原理與進化模式將算法分類。華北電力大學(xué)畢業(yè)設(shè)計摘 要 在最近二十年，作為一類新興的優(yōu)化技術(shù)，多目標進化算法吸引了極大關(guān)注，許多學(xué)者提出了不同的算法，多目標進化算法已經(jīng)成為處理多目標工程設(shè)計和科學(xué)研究問題的重要方法。本文分析總結(jié)了兩種目前流行的所目標進化算法的基本原理，并通過算例來比較它們的性能。多目標問題仍向算法設(shè)計，呈現(xiàn)和執(zhí)行提出挑戰(zhàn)。有時目標之間是相輔相成、互相促進的，但更多的時候，目標之間是相互矛盾、此消彼長的。進化算法非常適用于于求解高度復(fù)雜的非線性問題，并且由于這類算法具有通用性，因而被廣泛地應(yīng)用于單個目標的復(fù)雜系統(tǒng)優(yōu)化問題。與單目標優(yōu)化問題的本質(zhì)區(qū)別在于,多目標優(yōu)化問題的解不是唯一的,而是存在一個最優(yōu)解集合,集合中元素稱為Pareto 最優(yōu)或非劣最優(yōu)(nondominance) 。它的主要思想是將進化算法的概念引入到多目標優(yōu)化領(lǐng)域，對多目標優(yōu)化問題同樣采用進化操作方式，但算法由單目標優(yōu)化問題求取一個最優(yōu)解，轉(zhuǎn)變?yōu)槎嗄繕藘?yōu)化問題中求取一個最優(yōu)解集，該解集稱為Pareto最優(yōu)解集。而對算法性能進行比較和評價就成為一個重要的核心問題，引起了諸多學(xué)者的研究興趣。例如在現(xiàn)代能源系統(tǒng)生產(chǎn)過程參數(shù)的優(yōu)化[4]設(shè)計中經(jīng)常會遇到多目標函數(shù)的優(yōu)化問題，使用經(jīng)典的多目標優(yōu)化方法通常把多個目標函數(shù)整合成單目標，將問題轉(zhuǎn)變?yōu)閱文繕藘?yōu)化問題，然后采用單目標的優(yōu)化技術(shù)求解。有些方法每次運行只產(chǎn)生一個解,求多個解時需要運行多次,效率較低。這類算法通過加權(quán)或劃分子群體進化等方法將MOP轉(zhuǎn)化為不同的SOP，然后借助現(xiàn)有單目標遺傳算法對轉(zhuǎn)化后的SOP進行求解，最后對進化獲得的解進行分析，篩選出非劣解集。第二類算法是基于Goldberg提出的適應(yīng)值分級和共享策略的多目標遺傳算法。第三類算法是由第二類算法發(fā)展起來的精英保留策略MOGA。第四類算法是采用其他搜索算法策略改進的MOEA。代表算法有MOSE、MOPSO等[10]。多目標遺傳算法的研究一直是這類算法研究的主流方向：盡管遺傳算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他進化策略或啟發(fā)式局部搜索算法好的局部搜索性能，因此，以進化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進化策略局部搜索的優(yōu)勢，獲得高性能的多目標優(yōu)化算法，成為多目標進化算法研究的潛在發(fā)展方向。SPEA/SPEA2 (Zitzler amp。本文將以NSGAII算法和MOGLS（MultiObjective Genetic Lcal Search）算法為例，通過算例和指定的函數(shù)指標來分析比較它們各自性能的優(yōu)缺點。最初的MOGLS是在遺傳進化過程中，每代遺傳操作生成新個體后，對現(xiàn)有群體中的所有個體進行局部搜索；后來Ishibuchi等人對局部搜索的步長選取、鄰域搜索效率做了進一步研究后，將局部搜索過程僅應(yīng)用于當前群體中的優(yōu)秀，顯著提高了算法效率，改進后的算法可獲得與SPEA、NSGAII相當?shù)膬?yōu)化性能。本文采用廣泛使用的Pareto 最優(yōu)性[12]定義。即, 使其中r 為子目標的數(shù)量。設(shè)有解集,若中的個體不被任何其它個體支配, 則是 中的非支配個體。在決策和優(yōu)化問題中，最優(yōu)性取決于如何比較和排序候選解，及決策者的偏好結(jié)構(gòu)。(2)為了避免未成熟收斂和獲得均勻分布且范圍最廣的非劣解，如何保持群體的多樣性。(2)基于目標設(shè)計策略的算法，即基于準則的策略，每當個體選中后進行復(fù)制時根據(jù)不同的目標來決定是否被復(fù)制至配對池。(3)基于非劣解等級優(yōu)先概念的適應(yīng)值分配策略由Goldberg最先提出，后人大多在此基礎(chǔ)上進行改進，如將群體劃分為幾個有序的子群體。另外，與單目標優(yōu)化不同的是，在個體保持不變的條件下，同一個體在這一代和下一代的適應(yīng)值可能不相等。多目標問題與單目標問題不同，它的優(yōu)劣性與支配關(guān)系并非定義目標向量之間的那種整體有序關(guān)系，只是給出部分有序關(guān)系，因而種群的級別排序不具有唯一性。因為EAs是并行地處理一組解，通過雜交和變異來搜索空間以尋找可能的最優(yōu)區(qū)域，通過選擇來搜索具有較高適應(yīng)度的個體。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進化算法多樣性的途徑?，F(xiàn)有多目標遺傳算法可根據(jù)統(tǒng)計概率密度估計的方法加以分類為如下三種策略來維持群體多樣性：(1)基于核函數(shù)的評價策略：基于核函數(shù)的評價策略主要通過計算以個體為“核”、群體中其他個體距離“核”的核函數(shù)之和，通過優(yōu)先保留核函數(shù)值較大的個體即較稀疏的解個體達到維持群體多樣性的目的。該策略主要考慮給定點至第個最近鄰居的距離，以便估計出其在鄰域內(nèi)的密度。具有相同Pareto級別序號的解個體在實施共享適應(yīng)度值后，還必須按解的目標向量之間的空間距離進行小生境規(guī)模調(diào)整?，F(xiàn)有算法中精英策略的實現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過確定性的選擇方法在混合群體中選擇后代，而不是采用變化之后的配對池來替換舊群體，增大了精英個體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。如果使用伴隨群體的方式，則伴隨群體中包括當前的近似Pareto集，即伴隨群體中受控的個體被移去。更新的算法研究表明，如果同時采用這兩種精英策略，可以進一步提高算法的搜索性能與收斂效果。遺傳算法的任務(wù)是種群出發(fā)，模擬生物進化的過程進行優(yōu)勝劣汰，最后得出滿足優(yōu)化要求的種群和個體。也可以設(shè)定期望的適應(yīng)度函數(shù)值，只有當種群中存在個體能達到期望值時，算法才可以結(jié)束。(6) 交叉操作:隨機地選擇用于繁殖的每一對個體的同一基因位，將其染色體在此基因位斷開并相互交換。一代一代循環(huán)往復(fù)，使種群中最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不斷提高，直至最優(yōu)個體的適應(yīng)度滿足優(yōu)化準則或最優(yōu)個體的適應(yīng)度和平均適應(yīng)度不再提高，則迭代過程收斂，算法結(jié)束。由上述步驟可以看出，構(gòu)造遺傳算法時需要考慮的兩個主要問題是可行解的編碼方法和遺傳算子的設(shè)計，這也是設(shè)計遺傳算法的兩個關(guān)鍵步驟。而從現(xiàn)階段的研究來看，人們更關(guān)注的是，算法結(jié)果是否為高質(zhì)量的結(jié)果，而對于另外兩個因素相對要求并不高，而且對于算法的效率來說，涉及到的是經(jīng)典的算法復(fù)雜度理論，已經(jīng)有很完善的泛化體系對其進行評價了，無需在多目標進化算法領(lǐng)域?qū)ζ湓龠M行專門的研究。1. 算法收斂性評價所謂的收斂性，實際上是指算法的真實結(jié)果集與理論上的最優(yōu)結(jié)果集之間的趨近度，即理論上的Pareto邊界和真正得到的Pareto邊界之間的差距。 (31)對于收斂性的評價指標而言，可以通過指標值反映出算法間優(yōu)化效果的差異，但只局限于最優(yōu)解集中更優(yōu)解的數(shù)量，對于其空間上的特性不做相關(guān)考慮。 (32) 其中，對于分布性的評價指標而言，只關(guān)注結(jié)果集的分布特性，用以檢測算法是否被阻在一個很小的范圍之內(nèi)進行搜索，而導(dǎo)致無法實現(xiàn)全局的最優(yōu)搜索的現(xiàn)象。因此從理論上來證明算法的優(yōu)劣并不常用，也較難實現(xiàn)正確的評估。因此，現(xiàn)有的性能評價體系從使用范圍上講，是基于實驗比較分析來實現(xiàn)的。最后簡單介紹了算法的性能評價體系，為幾種算法比較的方案提供依據(jù)，得出基于實驗的方法是可行的，本文將在第三章利用這一思想來試驗NSGAⅡ和MOGLS兩種算法的優(yōu)劣。這樣, 處于同一個Pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應(yīng)度也不同。NSGAⅡ針對以上的缺陷通過以下三個方面進行了改進：(1)提出了快速非支配排序法，在選擇運算之前，根據(jù)個體的非劣解水平對種群分級。最后，將作為第一級非支配個體集合，并賦予該集合內(nèi)個體一個相同的非支配序，然后繼續(xù)對作上述分級操作并賦予相應(yīng)的非支配序，直到所有個體都被分級。擁擠度的概念：擁擠度是指在種群中的給定點的周圍個體的密度，計算上要考慮個體周圍包含本身但不包含其他個體的最小正方形，如下圖，個體的聚集距離是。由于經(jīng)過了排序和擁擠度計算，群體中每個個體都得到了兩個屬性：非支配序和擁擠度，則定義偏序關(guān)系（）：當滿足條件，或滿足且時，定義。NSGAⅡ算法的主流程：首先隨即初始化一個父代種群，并將所有個體按非支配關(guān)系排序，且指定一個適應(yīng)度值。在上圖中，由于子代和父代個體都包含在中，則經(jīng)過非支配排序以后的非支配集中包含的個體是中最好的，所以先將放入新的父代種群中。當排序產(chǎn)生的非支配集的個體數(shù)目足夠填充時，就不必再繼續(xù)對剩下的部分排序了。局部搜索過程應(yīng)用于新解而最大限度地發(fā)揮它的適應(yīng)度的效率[24]。多目標遺傳局部搜索算法試圖尋找多目標最有問題所有的非支配解，如果在一個多目標問題中一個解不被其他解支配，它叫做非劣解，一個多目標問題有許多非劣解。連續(xù)權(quán)值策略和一個目標的選擇方式都不能為尋找所有的多目標問題的非劣解高效的服務(wù)，這是因為各種搜索方向需要尋找多種非劣解。在此算法中局部搜索應(yīng)用每個由父代種群向子代種群進化的過程中，新種群的適應(yīng)度通過被用于選擇父代種群的權(quán)值而定義，這樣，對每個解的局部搜索的方向就由應(yīng)用于它的父代解選擇的權(quán)值定義了。本算法不會花相當長的時間，還有代數(shù)通過遺傳操作更新能夠反復(fù)聲明很多次。局部搜索的步驟：（1）：指定一個初始解；（2）：檢驗初始解的相鄰解；（3）：如果比好，那么用代替；（4）：如果得所有相鄰解都已經(jīng)被檢驗了，結(jié)束這個過程，否則返回（1）；在（4）中可以看出，對一個初始解通過局部搜索檢驗的解的總數(shù)要遠大于相鄰解的總數(shù)[25]。MOGLS的步驟：（1）初始化，隨機產(chǎn)生一個初始種群：是這個種群解的個數(shù)。（4）交叉和變異：從父代解中選擇的對，分別應(yīng)用交叉過程，從每個父代解的對中產(chǎn)生新解，然后對新解使用變異操作。（7）終止測試：如果一個提前確定的停止條件被滿足，結(jié)束算法，否則，返回第二步。在采用驗證算法比較時，C指標使用最為普遍[26]。已有的測試函數(shù)的設(shè)計原則主要有：（1）優(yōu)化問題為非凸情形下的優(yōu)化性能測試；（2）優(yōu)化問題目標空間不連續(xù)情形下的優(yōu)化性能測試；（3）多變量優(yōu)化問題的優(yōu)化性能測試。為了對NSGAII和MOGLS兩種多目標遺傳算法性能進行考察，選擇ZDTKUR ：（1）KUR：變量個數(shù)是3，（2）ZDT4:變量個數(shù)是10， 對于函數(shù)優(yōu)化算例，本文采用實數(shù)編碼方式，即基因編碼中的每個位置表示優(yōu)化變量中的一個變量。 采用NSGAⅡ和MOGLS對KUR算例進行優(yōu)化時，兩種算法均設(shè)置相同的進化參數(shù)，以便保證各算法的進化條件相同或相似，從而可以根據(jù)算法求解到的非劣解集的優(yōu)劣評價算法的相對性能[28]。為了進一步通過直觀比較法確定兩種算法的優(yōu)化性能，本文采用Zitzler在文獻[29]中提出的方法對算法性能進行直觀評價。采用三種算法分別對各算例獨立優(yōu)化30次，將所得非劣解合并，在完成30次獨立優(yōu)化后，剔除各算法非劣解并集中的相同個體及劣解，得到各算法優(yōu)化的最終非劣解集，如下圖所示。上述分析可以看出，在復(fù)雜優(yōu)化空間多目標函數(shù)算例優(yōu)化中，NSGAII獲得了明顯好于MOGLS算法的非劣解集，初步顯示了它的良好優(yōu)化性能。雖然實驗比較分析的方法已經(jīng)在本學(xué)科內(nèi)廣泛的被使用，且有它的一些優(yōu)點，但是它本身也存在著一些問題：1. 算法間的差異較大，可比性較差因為它們都是根據(jù)不同的特定問題而提出的，算法結(jié)構(gòu)、參數(shù)等都不盡相同，所以當問題改變的時候，一般需要修改算法才能適應(yīng)新問題，這使得算法間較難進行集成比較。但是，同樣由于上面提及的算法間集成性差的原因，當研究人員提出一種新算法，需要評價一下該算法的性能，或比較已有算法間的性能差別時，只能算法逐一執(zhí)行，然后將各算法的結(jié)果進行人工分析、手動計算。3. 靜態(tài)的環(huán)境與參數(shù)目前的各種性能測試都只能針對靜態(tài)環(huán)境，即固定的參數(shù)。而后又總結(jié)了MOEA的研究現(xiàn)狀，就是以進化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進化策略局部搜索的優(yōu)勢，獲得高性能的多目標優(yōu)化算法，成為多目標進化算法研究的潛在發(fā)展方向第二章首先介紹了多目標進化算法的基本概念和最優(yōu)性原理。第三章本章首先詳細介紹了NSGAII和MOGLS的原理及流程，特別是兩種方法存在差異的適應(yīng)度評價和精英保留策略。在今后對算法做進一步研究時,還可將與實際求解問題相關(guān)的啟發(fā)式規(guī)則或啟發(fā)式算法引入非劣解局部搜索過程,以達到有效利用現(xiàn)有各學(xué)科專業(yè)知識指導(dǎo)局部搜索的目的,則GA 的全局搜索優(yōu)勢與啟發(fā)式快速鄰域搜索的優(yōu)勢相結(jié)合,算法尋求多目標優(yōu)化問題非劣解的效率和結(jié)果有望得到進一步提高。 Pm = MaxGens = 500 PopSize = 100Pc = 。 Pm = MaxGens = 500 PopSize = 200Pc = 。 Pm = MaxGens = 500 PopSize = 100Pc = 。 Pm = MaxGens = 500 PopSize = 200Pc