基于遺傳算法的多目標優化問題

1基于pareto最優的多目標遺傳算法現在，通過進化方法解決多目標優化問題已成為研究的熱點。一般來說，多目標問題的最佳解不是一個解，而是一組相互無法比較的最優解的集合，這對傳統的優化方法提出了挑戰。然而，在許多優化方法中，由于進化算法的并行性，每個操作都可以得到一組解，因此可以快速有效地解決多目標問題。Schaffer于1985年提出了基于向量評估的遺傳算法(VEGA),在每一代中,它基于各目標函數的計算,用適應度比例法產生一定數目的子種群,然后將其混合起來形成新的一代,繼續執行交叉和變異的遺傳算法.但VEGA本質上仍然是加權和的方法.此后,又出現了許多成功的多目標進化方法.Fonseca等提出了著名的多目標遺傳算法(MOGA),它主要利用Pareto最優概念,將優于某個體的個體數量作為該個體的適應度值,并采用自適應小生境技術和受限雜交技術來提高種群多樣性.但該算法受小生境技術影響,并且適應度的計算隨著種群規模的擴大將非常耗時.Srinivas等提出了基于非控分類的多目標遺傳算法(NSGA),但其中非控分類算法復雜度較高.Leung提出了用多個適應度函數,從多個方向對解空間進行搜索,其中每個適應度函數都是單個目標的加權和,通過實驗設計方法選擇恰當的權值.它能找到分布一致的Pareto最優解,但權值的選擇非常困難.Zitzler等提出的SPEA方法和Knowles等提出的PAES方法都引入了精英機制來提高多目標進化算法的性能,但對精英種群的規模有著嚴格的限制.本文提出了多目標遺傳算法,它是在單目標搜索的基礎上,借助于精英選擇和個體遷移來保留Pareto最優解,同時加快算法的收斂速度.針對Pareto最優解數量過多,提出了限制目標函數值的精度來控制解的數量,并保持解的多樣性.根據每一代精英種群中Pareto最優解的更新情況,提出了多目標遺傳算法的新的終止條件.最后通過仿真實驗驗證了所提方法的快速性、有效性.通過仿真比較,該方法能得到一組高質量的Pareto最優解.2多目標數據集法2.1決策向量的xn考慮如下的多目標優化問題:minf(x)=(f1(x)?f2(x)???fm(x))?s.t.x∈[a?b].(1)minf(x)=(f1(x)?f2(x)???fm(x))?s.t.x∈[a?b].(1)其中:決策向量x∈Rn,即x=(x1,x2,…,xn);目標向量f(x)∈Rm.多目標優化問題中,各個目標通常是相互制約的關系,對其中一個目標進行優化往往以其他目標的性能降低為代價,且其最優解不是唯一的.為了對多目標問題的解進行比較,先給出Pareto最優解的定義.定義1稱x∈[a,b]是多目標優化問題的Pareto最優解,如果不存在y∈[a,b],使fi(y)≤fi(x),i=1,2,…,m,且至少有一個嚴格不等式成立.由定義1可知,Pareto最優解集中的解是彼此不可比較的,解集中的解數量越多,分布越廣泛,決策者的選擇空間越大,越能對實際多目標問題進行合理求解.2.2增加單目標尋優Dedieu提出了基于單目標遺傳算法與Pareto最優結合的MOGA.它先按多個單目標遺傳算法進行演化,然后利用Pareto最優概念,將進化過程中產生的所有個體進行比較,得到一組Pareto最優解.整個過程由于各個單目標的求解都獨立進行,因此求得的多目標解的質量不高,算法收斂速度不快.本文在文獻的基礎上,提出了基于精英選擇和個體遷移的遺傳算法求解多目標優化問題.下面詳細描述精英選擇和個體遷移策略.每個單目標問題所生成的個體集合稱為子種群,所有子種群的集合稱為多目標種群,各個單目標的子種群規模是相同的,另外建立一個精英種群來保存Pareto最優解.在每生成新一代多目標種群后,都要基于Pareto最優概念,對精英種群中的個體進行更新,剔除劣解,吸收新的Pareto最優解,保證精英種群中的解都是目前意義上的Pareto最優解.進化過程結束后,精英種群中的所有Pareto最優解即是所求多目標問題的解.在進化過程中,為了加快向Pareto最優解收斂的速度,將精英種群中的優秀個體遷移到相應的單目標子種群中.具體地,將每個單目標的子種群和精英種群合并看作新的目標子種群,在這新的目標子種群中執行錦標賽選擇法,即從中隨機選擇指定數目為Tour的個體,比較后將該目標函數值最優的個體選擇作為該目標的父代個體,直至選擇出給定規模的父代個體.這樣每個單目標子種群的父個體中既包含了本目標中優秀的個體,也包含了從其他目標種群中遷移過來的屬于精英種群的優秀個體,加快了尋找最優Pareto解的速度.通常在搜索初期時,通過錦標賽選擇法生成的父代個體中優秀個體的復制次數較多,因為初期時精英種群中個體的數量較少,參與錦標賽選擇的個體較少.而隨著搜索的進行,精英種群中的個體數量會越來越多,于是參與錦標賽選擇的個體規模變得很大,選出來的相同優秀個體的復制次數會明顯減少.為了防止在搜索初期由于優秀個體的復制次數過多而導致收斂到局部區域,應保證被選擇的優秀個體的復制次數不超過某指定的上限.這樣除了能夠找到各個單目標的最優值,而且由于種群個體的多樣性還能夠找到更多的Pareto最優解.本文提出的方法彌補了文獻的不足.在多個單目標問題并行進行尋優的同時,通過精英選擇將各個單目標問題的Pareto最優解集中到精英種群中,然后通過個體遷移將精英種群中的某分目標的優秀解植入到相應分目標的種群中.這樣單目標尋優問題并不是自我封閉演化,而是與其他種群進行時時地信息交換,有利于多目標問題朝著Pareto前沿解的方向快速收斂,而各個單目標優化的對象不同,所以這種信息交換不會使算法出現早熟現象.2.3子代個體的產生本文的遺傳算法采用浮點數編碼.這樣對于一個具有n個決策變量的優化問題的個體編碼,是一個由n個在各自定義域內變化的實數變量組成的數組.本文的交叉算子采用線性交叉,具體如下:隨機選擇兩個父代個體,x1=(x1111,x1212,…,x1n1n),x2=(x2121,x2222,…,x2n).產生一個隨機數.如果該數大于交叉概率,則不執行交叉操作,直接將兩個父代個體復制為子代個體;否則,執行線性交叉.經過線性交叉后生成兩個子個體,分別為y1=(y11?y12???y1n)?y2=(y21?y22???y2n)?y1i=α1x1i+(1-α1)x2i?y2i=α2x1i+(1-α2)x2i?0≤α1≤1和0≤α2≤1隨機產生.每個個體的每個變量都有均等的變異機會,先選定一個個體的一個變量,然后產生一個隨機數,如果該數大于變異概率,則不執行變異操作;否則在該個體相應變量的定義域范圍重新隨機生成一個變量.2.4有限精度法許多多目標優化問題有大量的或無窮個Pareto最優解,為了控制Pareto最優解的數量,同時又不失多樣性,以便給決策者更多的選擇空間,學者們提出了多種算法.這些方法在能夠精確控制求解數量和保證解的分布均勻的同時,也使計算時間大量增加.事實上,大多數時候并不需要精確控制解的數量,而只是希望解的數量不要過大而影響算法的收斂速度,為此提出有限精度法.針對不同的問題,或同一問題的不同目標值,在不影響決策的情況下,設定不同的求解精度.當某些問題的目標值是較小的小數時,可以設定該目標值精確到小數點后某幾位;如果目標值是較大的數,則設定較高幾位有效,后面位數的數字不再考慮.精度的設定還要結合得到的最優解的數量來確定,通過改變精度觀察得到最優解數量的變化情況,盡量使最優解的數量不低于百位數也不高于千位數.有限精度法并不需要額外的計算量,因此不會增加算法的計算時間.這樣通過控制目標值的求解精度,可以有效控制Pareto最優解的數量,減少局部區域解的分布密度,有利于全局尋優,并加快收斂速度.2.5算法終止條件目前多目標遺傳算法終止條件大都給定一個最大進化代數,這樣使得算法往往還沒收斂到最優解就結束了;或者已經收斂了,但還在繼續搜索,降低了算法的性能.本文提出一個新的終止條件:如果連續指定的迭代次數Ttime中精英種群的Pareto最優解都沒發生變化,即新一代Pareto最優解集與上一代的Pareto最優解集完全一樣,則認為算法收斂,迭代結束.這個終止條件說明,該算法已經收斂到了Pareto最優解.2.6基于新一代子種群的pareto最優解集的方法Step1:初始化算法參數.交叉概率Pc,變異概率Pm,錦標賽競賽規模Tour,子種群規模Popsize,優秀個體復制次數的上限,各個目標值的計算精度,終止時連續迭代次數Ttime.Step2:針對多目標問題(1)中的m個目標,隨機生成m個具有Popsize個個體的子種群,采用浮點數對個體進行編碼,計算每個個體的目標函數值.Step3:對所有目標中的m×Popsize個個體的目標函數值進行比較,得到初始的Pareto最優解集,并保存到精英種群中.Step4:判斷終止條件是否滿足.如滿足,則結束算法;否則,繼續.Step5:先選定某個分目標,初始化該分目標子種群和精英種群中每個個體的復制次數為0;然后在該分目標的子種群和精英種群中,隨機選擇Tour個個體.其中每隨機選擇一個個體,都必須保證該個體的復制次數小于指定的上限,否則重新選擇,直到選擇出Tour個個體;然后通過競爭將該分目標函數值最優的個體選作該分目標的父代個體,同時該個體的復制次數加1.這個過程重復進行,直至完成該分目標的父代個體的選擇;然后再完成其他分目標的父代個體選擇.Step6:對每個分目標的父代子種群分別執行交叉、變異操作,產生m個目標的新一代子種群.Step7:通過m個新一代子種群中個體間的相互比較,得到新一代種群的Pareto最優解集.Step8:將由新一代種群產生的Pareto最優解集與精英種群中的Pareto最優解進行比較,剔除精英種群中的劣解,并將新的Pareto最優解包含進來,完成對精英種群的更新操作;然后返回Step4.3第一次隨機運行實驗實例1{minf1=2√x1?minf2=x1(1-x2)+5?s.t.1≤x1≤4?-20≤x2≤10.(2)實例2{minf1=1/(x21+x22+1)?minf2=x21+3x22+1?s.t.-3≤x1≤3?-5≤x2≤5.(3)實例3{minf1=0.758[x1(6.4×103-x22)+(103-x1)(104-x22)]?minf2=3.298×10-5[(14.096×107-x42-1108-x42)x31+109108-x42]?s.t.40≤x2≤75.2?0≤x1≤180(4.096×107-x42)9.78×106.(4)為了驗證本文算法的有效性,采用式(2)～(4)進行測試.算法參數均設定為:每個目標的子種群規模Popsize=50,交叉概率Pc=0.9,變異概率Pm=0.2,競賽規模Tour=5,最大終止迭代次數Maxgen=80.實例1的2個目標值都精確到小數點后2位,實例2的2個目標值都精確到小數點后3位,實例3的第1個目標值精確到千位,第2個目標值精確到小數點后7位.每個實例都隨機運行10次,從運行結果看,這10次隨機運行得到的Pareto最優解的分布區域和分布密度是相同的.只給出每個實例的第一次仿真結果如圖1～圖3所示,可以看出3個實例均能找到一組分布較均勻的Pareto最優解.對上述3個實例,通過仿真實驗來測試優秀個體的復制次數對結果的影響.每一個實例均分為7組實驗,即分別是優秀個體的復制次數上限為2,3,…,7,8.對每一個實例的每組實驗隨機運行10次,每一次最大終止迭代次數Maxgen=500,其余參數設定同上.為便于比較,在每次隨機運行時,相應實例的7組實驗都設定相同的隨機種子數,具有相同的初始條件.表1給出了10次隨機運行的最優解和劣解的累加量,其中每一次隨機運行的劣解的數量是通過這次隨機運行中7組實驗的所有最優解進行相互比較得到的.根據多次實驗得出,在搜索的前20代左右,優秀個體的復制次數較多,而且個體的復制次數最多不超過7.表1中給出的實例1和實例2的7組實驗的最優解的數量是相同的,且劣解的數量為0.這是因為在給定的精度下,該算法在最大終止迭代次數為500時已經收斂,個體的復制次數對結果沒有產生影響.而實例3的結果表明,限制個體的復制次數可以不同程度地減少劣解的數量,找到更多的Pareto最優解.實例4{minf1=x212+(x2+1)213+3?minf2=x212+(2x2+2)215+1?minf3=(x1+2x2-1)2175+(2x2-x1)227-13?s.t.-3≤x1?x2≤3.(5)通過實例4的仿真實驗進一步給出個體遷移策略和精英選擇方法的重要作用.采用兩種方法,一是本文提出的方法,二是在本文提出方法的基礎上將個體遷移策略取消,并在每個子種群中采用輪盤賭選擇法.每次實驗均采用如下設定參數:每個目標的子種群規模Popsize=50,交叉概率Pc=0.9,變異概率Pm=0.2,競賽規模Tour=3,終止條件的連續迭代次數Ttime=5.每個目標值都精確到小數點后3位數字.兩種方法10次隨機實驗的結果如表2所示.由表2可以看出,個體遷移策略在不損失多樣性的前提下,能大大加快算法的收斂