【正文】 252627282930最大最小平均方差附錄B 采用NSGAII和MOGLS優(yōu)化ZDT4結(jié)果MaxGens = 500 PopSize = 100Pc = 。 Pm = C(N,M)C(M,N)C(N,M)C(M,N)C(N,M)C(M,N)C(N,M)C(M,N)12345678910111213141516171819202122
。 Pm = MaxGens = 1000 PopSize = 100Pc = 。 Pm = MaxGens = 1000 PopSize = 100Pc = 。而后沿用了經(jīng)典的進化結(jié)構(gòu)，基于這種策略，引用C指標對比了NSGAII和MOGLS算法的性能。但是，在算法的測試與改進的過程中，研究人員往往希望能夠跟蹤算法的中間數(shù)據(jù)，或是在執(zhí)行的過程中能夠動態(tài)的改變某些參數(shù)，從而方便的對算法進行調(diào)整。但是，想要進行性能的評測，就需要算法在相同環(huán)境下統(tǒng)一運行，以保證結(jié)果的公正性和準確性，保證結(jié)果更具有說服力，如果不能進行集成，就很難達到這樣的評測條\件。在這個函數(shù)優(yōu)化算例中，KUR屬于優(yōu)化變量相對較少、優(yōu)化目標較為復(fù)雜的函數(shù)測試算例（非凸、不連續(xù)問題），因此在許多算法研究的性能評價中，都采用這個算例驗證新算法的有效性；ZDT4算例屬于多變量函數(shù)優(yōu)化算例（優(yōu)化變量10）。因為現(xiàn)代啟發(fā)式算法存在不確定性，因此在每組參數(shù)組合下計算30次做統(tǒng)計分析。針對這些測試原則中的一種或幾種原則的組合，借鑒單目標遺傳算法測試函數(shù)的設(shè)計方法，Deb、Fonseca、Fleming、Veldhuizen和Zitzler等人通過長期研究，分別提出了多個具有不同優(yōu)化性狀的測試函數(shù)。如果多目標優(yōu)化問題有凹的Praeto前端，使用帶有連續(xù)權(quán)值的計算權(quán)值之和的方法將不能得到整個Praeto前端。（2）評價適應(yīng)值：對當前種群中每個解在個目標方向計算適應(yīng)度值，更新臨時非劣解集?？傊?，我們能通過局部搜索調(diào)整計算時間。為了實現(xiàn)各個方向搜索，而提出這種算法。這個算法的一大典型特性是無論何時選擇一組父代種群都要指定權(quán)值效率。如果的大小小于，則繼續(xù)向中填充，直到添加到時種群大小超出，對中的個體進行擁擠度排序，取前個個體。即如果兩個個體的非支配排序不同，取排序號較小的個體；如果兩個個體在同一級，取周圍較不擁擠的個體。如此操作降低了算法的計算復(fù)雜度。 (23)其中, 表示個體 與個體 的距離, 是同一小生境中個體間的最大允許距離, 表示距離為時的共享函數(shù)值。 本章首先介紹了多目標進化算法的基本概念和原理。由于收斂性評價與分布性評價的應(yīng)用方向不同，因而在比較算法的時候，多會綜合兩種評價后，對算法的性能得出適當?shù)慕Y(jié)論。收斂性的評價方法有很多種，如錯誤率、解集間覆蓋率、世代距離、最大出錯率等等。多目標遺傳算法的性能評價與傳統(tǒng)優(yōu)化算法及單目標遺傳算法的性能評價有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過梯度下降速度進行評價，并且可以通過嚴格的數(shù)學(xué)證明分析其收斂性能；單目標遺傳算法可以采用基于模式定理或基于馬爾可夫隨機過程理論的證明分析其收斂性，盡管這類證明研究還很初步。(7) 變異操作:以一定的概率從群體中選擇若干個個體。 (3) 設(shè)計適應(yīng)度函數(shù)：把問題的目標函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度函數(shù)計算種群中的每個個體的適應(yīng)度，為種群進化的選擇提供依據(jù)。但是使用優(yōu)勝關(guān)系比較的方法有時也存在問題，如對某些連續(xù)型問題所對應(yīng)的Pareto集可能包含無窮多個解，因此需要補充其他的信息知識來減小所存儲的個體數(shù)目。當兩個解的目標向量之間的空間距離小于某一預(yù)定值時，相應(yīng)解的小生境規(guī)模就必須進行調(diào)整。具體應(yīng)用時首先根據(jù)內(nèi)核函數(shù)來定義一個點的鄰域范圍，內(nèi)核函數(shù)采用至另一點的距離作為參數(shù)。傳統(tǒng)的進化算法在Pareto最優(yōu)集上執(zhí)行多目標搜尋，希望找出盡可能均勻分布的解集，因而個體的多樣性減少的很快，經(jīng)常收斂至單個解而丟失多個其他非劣解。Pareto優(yōu)勝關(guān)系是決定個體適應(yīng)度函數(shù)值的重要依據(jù)，很多MOEAs根據(jù)個體間的這種關(guān)系，將個體的適應(yīng)度函數(shù)值分成兩個層次，即劣解和非劣解，后者的適應(yīng)度值總是優(yōu)于前者。此方法通過在不同進化代之間更換優(yōu)化目標每次優(yōu)化一個目標，使算法群體每次運行得到一個非劣解，從而通過多次運行找到優(yōu)化問題的非劣解集。從決策者的立場來看，一般認為每對候選解具有以下比較關(guān)系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。此時稱 為非支配的( non dominated), 為被支配的( dominated) 。MOGLS的優(yōu)點是通過隨機權(quán)將MOP轉(zhuǎn)化為SOP，算法容易實現(xiàn)，并且恰當控制MOGLS中鄰域搜索個體的選取及步長可以在減少計算復(fù)雜度的同時獲得良好的計算結(jié)果；算法的不足之處是，算法的構(gòu)造是基于MOP轉(zhuǎn)化為SOP的思想，因此在不明確多個目標偏好情況下，采用隨機權(quán)的方法往往不能保證所得非劣解集分布的均勻性。 Thiele 2001)和NSGA/NSGAII (Srinivas amp。除了上述四類算法外，一些學(xué)者在演化策略中引入偏好分級或適應(yīng)值分享機制獲取滿意解。這類算法通過在進化過程中引入外部伴隨群體對群體中的精英個體加以保留，同時采用更加成熟的適應(yīng)值設(shè)計策略，使算法不僅在收斂速度上有所提高，而且在優(yōu)化性能上也有所改善。由于這類算法的設(shè)計思想是基于單目標遺傳算法的進化策略，因此它的優(yōu)點是算法容易實現(xiàn)；其不足是，基于單目標子群體優(yōu)化的算法很難搜索到嚴格意義上的非劣解集，往往僅能得到非劣解集中的部分極值點。但這些方法存在：只能得到一個解；多個目標函數(shù)之間量綱不同難以統(tǒng)一；加權(quán)值的分配帶有較強的主觀性；加權(quán)的目標函數(shù)之間通過決策變量相互制約，最終優(yōu)化目標僅為各目標之和，各目標的優(yōu)化進度不可操作等缺點。最優(yōu)解集中的每個解，理論上都是“最優(yōu)解”，而在實際應(yīng)用中，可以根據(jù)決策需要選擇其中一個解作為最終決策方案，實現(xiàn)最優(yōu)化的目的。然而，人們在求解現(xiàn)實世界許多優(yōu)化問題時，通常不追求單一目標的最優(yōu)性，這就要求在解決問題時同時對多個目標進行優(yōu)化和權(quán)衡，有時目標之間是相輔相成、互相促進的，但更多的時候，目標之間是相互矛盾、此消彼長的，這樣的問題被稱為多目標優(yōu)化問題(MultiObjective Optimization Problem, MOP)，大多數(shù)工程和科學(xué)問題是多目標最優(yōu)問題。不斷變化的多目標問題很少被考慮到它的時變特性，對此有效的多目標進化算法很罕見，多目標進化算法的結(jié)合量計算和有區(qū)別的進化還始終停留在初級階段。華北電力大學(xué)畢業(yè)設(shè)計摘 要 在最近二十年，作為一類新興的優(yōu)化技術(shù)，多目標進化算法吸引了極大關(guān)注，許多學(xué)者提出了不同的算法，多目標進化算法已經(jīng)成為處理多目標工程設(shè)計和科學(xué)研究問題的重要方法。多目標問題仍向算法設(shè)計，呈現(xiàn)和執(zhí)行提出挑戰(zhàn)。進化算法非常適用于于求解高度復(fù)雜的非線性問題，并且由于這類算法具有通用性，因而被廣泛地應(yīng)用于單個目標的復(fù)雜系統(tǒng)優(yōu)化問題。它的主要思想是將進化算法的概念引入到多目標優(yōu)化領(lǐng)域，對多目標優(yōu)化問題同樣采用進化操作方式，但算法由單目標優(yōu)化問題求取一個最優(yōu)解，轉(zhuǎn)變?yōu)槎嗄繕藘?yōu)化問題中求取一個最優(yōu)解集，該解集稱為Pareto最優(yōu)解集。例如在現(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ù)求解。這類算法通過加權(quán)或劃分子群體進化等方法將MOP轉(zhuǎn)化為不同的SOP，然后借助現(xiàn)有單目標遺傳算法對轉(zhuǎn)化后的SOP進行求解，最后對進化獲得的解進行分析，篩選出非劣解集。第三類算法是由第二類算法發(fā)展起來的精英保留策略MOGA。代表算法有MOSE、MOPSO等[10]。SPEA/SPEA2 (Zitzler amp。最初的MOGLS是在遺傳進化過程中，每代遺傳操作生成新個體后，對現(xiàn)有群體中的所有個體進行局部搜索；后來Ishibuchi等人對局部搜索的步長選取、鄰域搜索效率做了進一步研究后，將局部搜索過程僅應(yīng)用于當前群體中的優(yōu)秀，顯著提高了算法效率，改進后的算法可獲得與SPEA、NSGAII相當?shù)膬?yōu)化性能。即, 使其中r 為子目標的數(shù)量。在決策和優(yōu)化問題中，最優(yōu)性取決于如何比較和排序候選解，及決策者的偏好結(jié)構(gòu)。(2)基于目標設(shè)計策略的算法，即基于準則的策略，每當個體選中后進行復(fù)制時根據(jù)不同的目標來決定是否被復(fù)制至配對池。另外，與單目標優(yōu)化不同的是，在個體保持不變的條件下，同一個體在這一代和下一代的適應(yīng)值可能不相等。因為EAs是并行地處理一組解，通過雜交和變異來搜索空間以尋找可能的最優(yōu)區(qū)域，通過選擇來搜索具有較高適應(yīng)度的個體?，F(xiàn)有多目標遺傳算法可根據(jù)統(tǒng)計概率密度估計的方法加以分類為如下三種策略來維持群體多樣性：(1)基于核函數(shù)的評價策略：基于核函數(shù)的評價策略主要通過計算以個體為“核”、群體中其他個體距離“核”的核函數(shù)之和，通過優(yōu)先保留核函數(shù)值較大的個體即較稀疏的解個體達到維持群體多樣性的目的。具有相同Pareto級別序號的解個體在實施共享適應(yīng)度值后，還必須按解的目標向量之間的空間距離進行小生境規(guī)模調(diào)整。如果使用伴隨群體的方式，則伴隨群體中包括當前的近似Pareto集，即伴隨群體中受控的個體被移去。遺傳算法的任務(wù)是種群出發(fā)，模擬生物進化的過程進行優(yōu)勝劣汰，最后得出滿足優(yōu)化要求的種群和個體。(6) 交叉操作:隨機地選擇用于繁殖的每一對個體的同一基因位，將其染色體在此基因位斷開并相互交換。由上述步驟可以看出，構(gòu)造遺傳算法時需要考慮的兩個主要問題是可行解的編碼方法和遺傳算子的設(shè)計，這也是設(shè)計遺傳算法的兩個關(guān)鍵步驟。1. 算法收斂性評價所謂的收斂性，實際上是指算法的真實結(jié)果集與理論上的最優(yōu)結(jié)果集之間的趨近度，即理論上的Pareto邊界和真正得到的Pareto邊界之間的差距。 (32) 其中，對于分布性的評價指標而言，只關(guān)注結(jié)果集的分布特性，用以檢測算法是否被阻在一個很小的范圍之內(nèi)進行搜索，而導(dǎo)致無法實現(xiàn)全局的最優(yōu)搜索的現(xiàn)象。因此，現(xiàn)有的性能評價體系從使用范圍上講，是基于實驗比較分析來實現(xiàn)的。這樣, 處于同一個Pareto 前沿的非劣解, 由于各自的小生境數(shù)不同, 最后的共享適應(yīng)度也不同。最后，將作為第一級非支配個體集合，并賦予該集合內(nèi)個體一個相同的非支配序，然后繼續(xù)對作上述分級操作并賦予相應(yīng)的非支配序，直到所有個體都被分級。由于經(jīng)過了排序和擁擠度計算，群體中每個個體都得到了兩個屬性：非支配序和擁擠度，則定義偏序關(guān)系（）：當滿足條件，或滿足且時，定義。在上圖中，由于子代和父代個體都包含在中，則經(jīng)過非支配排序以后的非支配集中包含的個體是中最好的，所以先將放入新的父代種群中。局部搜索過程應(yīng)用于新解而最大限度地發(fā)揮它的適應(yīng)度的效率[24]。連續(xù)權(quán)值策略和一個目標的選擇方式都不能為尋找所有的多目標問題的非劣解高效的服務(wù)，這是因為各種搜索方向需要尋找多種非劣解。本算法不會花相當長的時間，還有代數(shù)通過遺傳操作更新能夠反復(fù)聲明很多次。MOGLS的步驟：（1）初始化，隨機產(chǎn)生一個初始種群：是這個種群解的個數(shù)。（7）終止測試：如果一個提前確定的停止條件被滿足，結(jié)束算法，否則，返回第二步。已有的測試函數(shù)的設(shè)計原則主要有：（1）優(yōu)化問題為非凸情形下的優(yōu)化性能測試；（2）優(yōu)化問題目標空間不連續(xù)情形下的優(yōu)化性能測試；（3）多變量優(yōu)化問題的優(yōu)化性能測試。 采用NSGAⅡ和MOGLS對KUR算例進行優(yōu)化時，兩種算法均設(shè)置相同的進化參數(shù)，以便保證各算法的進化條件相同或相似，從而可以根據(jù)算法求解到的非劣解集的優(yōu)劣評價算法的相對性能[28]。采用三種算法分別對各算例獨立優(yōu)化30次，將所得非劣解合并，在完成30次獨立優(yōu)化后，剔除各算法非劣解并集中的相同個體及劣解，得到各算法優(yōu)化的最終非劣解集，如下圖所示。雖然實驗比較分析的方法已經(jīng)在本學(xué)科內(nèi)廣泛的被使用，且有它的一些優(yōu)點，但是它本身也存在著一些問題：1. 算法間的差異較大，可比性較差因為它們都是根據(jù)不同的特定問題而提出的，算法結(jié)構(gòu)、參數(shù)等都不盡相同，所以當問題改變的時候，一般需要修改算法才能適應(yīng)新問題，這使得算法間較難進行集成比較。3. 靜態(tài)的環(huán)境與參數(shù)目前的各種性能測試都只能針對靜態(tài)環(huán)境，即固定的參數(shù)。第三章本章首先詳細介紹了NSGAII和MOGLS的原理及流程，特別是兩種方法存在差異的適應(yīng)度評價和精英保留策略。 Pm = MaxGens = 500 PopSize = 100Pc = 。 Pm = MaxGens = 500 PopSize = 100Pc