多目標優(yōu)化方法研究

第38卷第4期西南民族大學(xué)學(xué)報.自然科學(xué)版Jul. 2012Journal of Southwest University for Nationalities.Natural Science Edition文章編號: 1003-2843(2012)04-065804多目標優(yōu)化方法研究方詩(shī)虹,丁可偉,陳雅茜1(I.西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院,四川成都610041;2. 西南民族大學(xué)預科教育學(xué)院,四川咸都610041)摘要:闡述了多目標優(yōu)化問(wèn)題的特點(diǎn),給出了該問(wèn)題的數學(xué)模型及Pareto 最優(yōu)解的定義,介紹了用于解決多目標問(wèn)題的傳統優(yōu)化方法和進(jìn)化優(yōu)化方法，并著(zhù)重介紹了基于遺傳算法的多目標優(yōu)化方法.最后對傳統方法和進(jìn)化方法進(jìn)行了比較.關(guān)鍵字:多目標優(yōu)化問(wèn)題;單目標優(yōu)化問(wèn)題; Pareto最優(yōu)解;遣傳算法中圖分類(lèi)號: TP301.6文獻標識碼: Adoi: 0.396/j.ssm.1003-2483 2012.04.341引言現代社會(huì )各行各業(yè)的應用中，常常遇到需要使多個(gè)目標在給定區域上盡可能最優(yōu)的決策問(wèn)題.例如在進(jìn)行網(wǎng)絡(luò )設計時(shí)，在希望成本盡可能低的同時(shí)，網(wǎng)絡(luò )帶寬盡可能高,此外可能還需要考慮可靠性和可維護性等.這些目標的改善可能相互抵觸,在提高其中某個(gè)目標時(shí)，會(huì )導致其他目標效果的下降.例如低成本難以滿(mǎn)足高帶寬而好的可維修性會(huì )降低可靠性.所以，實(shí)際應用中必須在多個(gè)期望目標之間取得平衡，從而獲得-一個(gè)相對優(yōu)化的結果.這種多個(gè)數值目標在給定區域上的最優(yōu)化問(wèn)題即多目標優(yōu)化問(wèn)題(Muti-bjective Optimization Problem,MOP).2問(wèn)題 的描述2.1多 目標優(yōu)化問(wèn)題的數學(xué)模型單目標優(yōu)化問(wèn)題(Single objective Optimization Problem, SOP)往往只有一個(gè)解存在，求得該解即得到了最優(yōu)解.而多目標優(yōu)化問(wèn)題MOP與單目標優(yōu)化問(wèn)題SOP相比，有著(zhù)本質(zhì)的區別".多目標優(yōu)化問(wèn)題MOP可作如下數學(xué)描述:定義1一般由n個(gè)決策變量參數、k 個(gè)目標函數和m個(gè)約束條件組成的MOP問(wèn)題,最優(yōu)化目標如下:maxy= f(x)=(f(x),&(x).f(x))x=(x,+x,-.x.)eX(1)y-=(y>2.-.y.)cYs4. e;(x)≤0， i=,..,m .其中x表示決策向量，X表示決策空間, y,表示目標向量, Y表示目標空間，e(x)為約束函數.最大化與最小化問(wèn)題可以相互轉化,本文以最大化多目標為例2.2 Pareto 最優(yōu)解中國煤化工收稿日期: 2012-04-24作者簡(jiǎn)介:方詩(shī)虹(1980-), 女講師.YHCNMHG.基金項目:中央高?；究蒲袠I(yè)務(wù)費專(zhuān)項資金(12NZYQN16)資助..第4期方詩(shī)虹等:多目標優(yōu)化方法研究659Francis Ysidro Edgeworth 于1881 年提出多目標問(wèn)題“最優(yōu)解”的概念即解決多目標問(wèn)題，實(shí)際上是求解- -組均衡解,而非單個(gè)目標全局最優(yōu)解.法國經(jīng)濟學(xué)家和社會(huì )學(xué)家Vilfredo Pareto在1896年推廣了這個(gè)概念1, 他提出向量化概念從經(jīng)濟學(xué)角度將本質(zhì)上不可比較的多個(gè)目標轉化成單個(gè)指標進(jìn)行優(yōu)化求解.定義2對于集合AS X,當且僅當決策向量x∈X;為非劣,有不3a∈A:a>x.(2)即當且僅當x在X,中是非劣的，決策向量x才是Pareto 最優(yōu)解.其中,對于決策向量a、x,當且僅當f(a)>f(x)時(shí)，有a>x,即a優(yōu)于x.2.3 Pareto 最優(yōu)解集的評價(jià)準則由于多目標優(yōu)化問(wèn)題的結果并不是唯- - 確定的，所以對其非劣解集質(zhì)量評價(jià)也相對困難的. - -般來(lái)說(shuō)，- 一個(gè)比較理想的非劣解集應包括以下幾個(gè)方面以:(1)獲得的非劣解集與真實(shí)非劣解集的距離應盡可能小;(2)獲得的非劣解集應均勻分布;(3)獲得非劣解集應具有良好的擴展性,即非劣前沿的端點(diǎn)應盡可能接近單目標極值.為了方便對多目標優(yōu)化問(wèn)題非劣解集質(zhì)量進(jìn)行評價(jià),在隨后的研究中，人們采用一-些度量方法量化以上3個(gè)衡量標準，對算法的性能進(jìn)行評價(jià),主要有U-度量法+、寬廣性度量法(Maximum Spread-measure)5、 C-度量法'和S-度量法!"!3進(jìn)化的多 目標優(yōu)化方法多目標進(jìn)化算法(Multi-objective Evolutionary Algorithms, MOEAs)在處理大規模的搜索空間、在單輪優(yōu)化期間可以產(chǎn)生多個(gè)均衡解，且對目標最優(yōu)均衡面的形狀和連續性不敏感，可 以很好地逼近非凸或不連續的均衡面,能夠有效克服傳統方法局限性.Vanveldhuizen"2)按求解和決策的關(guān)系把多目標優(yōu)化求解方法分為三類(lèi):(1)先決策再搜索解:決策者先給出目標優(yōu)先等級，將多目標合成數量成本函數,再由算法搜索最優(yōu)解,如評價(jià)函數法;(2)邊決策邊搜索解:決策者和算法互動(dòng)，前者提供目標優(yōu)先關(guān)系，后者提供最新解,根據最新解產(chǎn)生更好的目標優(yōu)先關(guān)系，交互求解;(3)先搜索解再決策:算法搜索到解集后，再由決策者確定或選擇解,如理想點(diǎn)法.在眾多的方法中，先搜索再決策的方法較多,而使用遺傳算法作為進(jìn)化方法的算法在MOEAs設計和應用中占主要地位.3.1 多目標遺傳算法對于如何求解多目標問(wèn)題的Pareto 最優(yōu)解,目前已提出了多種基于遺傳算法的求解方法，主要有并列選擇法、權重系數變化法、排序選擇法、共享函數法和外部輔助選擇法等"!.3.2 權重系數變化法這是基于目標加權法的遺傳算法,例如Hajela和Lin提出的“可變目標權重聚合法”.在這種非Pareto方法中,每個(gè)目標均有一一個(gè)權重,但權重本身并不固定,為了搜索多個(gè)解,問(wèn)題解和權重會(huì )動(dòng)態(tài)變化，同時(shí)進(jìn)化.這種方法計算效率較高，但在沒(méi)有足夠的信息時(shí)，無(wú)法確定合適的權重系數，只能通過(guò)權重系數組合函數的優(yōu)化結果來(lái)獲得最優(yōu)解.3.3排序選擇法Srinivas和Deb提出的“非劣分層遺傳算法(NSGA)”即屬于中國煤化工壽Pareto最優(yōu)個(gè)體的概念來(lái)對群體中的所有個(gè)體進(jìn)行排序,由這個(gè)排序結果來(lái)實(shí)施MHC N MH G在前面的Pareto 最優(yōu)個(gè)體有更多機會(huì )遺傳到下一-代群體.經(jīng)過(guò)數代循環(huán)后，最終得到Pareto 最優(yōu)解.其中,最優(yōu)個(gè)體排序方法如660西南民族大學(xué)學(xué)報.自然科學(xué)版第38卷下:StepI設置初始序號r=1;Step2確定群體中的Pareto最優(yōu)個(gè)體,定義其序號為r;Step3從群體中去掉最優(yōu)個(gè)體,并更改序號r=r+1;Step4回到Step2,直至將所有個(gè)體排序.Deb等人在2002年提出了NSGA-II,主要思想是對種群中的個(gè)體按Pareto進(jìn)行排序,按照排序順序從小到大選擇個(gè)體,若遇相同序值的個(gè)體,則偏好位于目標空間中稀疏區域的個(gè)體.排序選擇法僅度量了各個(gè)個(gè)體之間的優(yōu)越次序,而未度量分散程度，故容易產(chǎn)生多個(gè)相似的Pareto 最優(yōu)解,難以生成分布較廣的解集..4 共享函數法這類(lèi)算法的典型代表是Horm等人提出的“小生境Pareto遺傳算法".對某個(gè)個(gè)體而言,度量其附近存在多少種、多大程度相似個(gè)體的度量值,即小生境數(Niche Count).在進(jìn)化算法中引入小生境方法后,對相同或相似個(gè)體數量加以限制，以便產(chǎn)生種類(lèi)較多的不同最優(yōu)解共享函數法的過(guò)程如下:StepI從群體中隨機選取k個(gè)個(gè)體組成個(gè)體比較集合C ;Step 2從群體中隨機選擇兩個(gè)個(gè)體組成個(gè)體聯(lián)賽集合T ;Step 3比較集合T和C中各個(gè)個(gè)體的優(yōu)勝關(guān)系，如果T中的一個(gè)個(gè)體x比C中的所有個(gè)體都優(yōu)越，且T中的另-一個(gè)個(gè)體不比C中的所有個(gè)體優(yōu)越,則個(gè)體x遺傳到下一代群體中;如果無(wú)法獲得這樣的個(gè)體x,則從T中選擇小生境數較小的個(gè)體遺傳到下一代群體中.共享函數法能得到多種不同的Pareto最優(yōu)解但大量的評價(jià)和比較運算使其搜索效率較低.3.5外部輔助選擇法Zitzler和Thiele'提出的“強度Pareto進(jìn)化算法‘及Cello和Toscano Pulido0提出的“微遺傳算法(Micro-GA)”等都屬于外部輔助選擇法,主要流程如下:StepI產(chǎn)生初始群體P和一個(gè)外部輔助非劣空的集合P';Step2將P中的非劣個(gè)體復制到P',將P'中的劣解剿除(第- -代無(wú)劣解);Step3對P'進(jìn)行聚類(lèi)處理,控制其規模不超過(guò)預定數N';Step4計算P和P'中個(gè)體適應度;Step5從PUP'中使用聯(lián)賽選擇機制進(jìn)行選擇操作,直到配對池滿(mǎn);Step 6交叉和變異;Step 7達到最大進(jìn)化代數則停止否則轉到Step 2.外部輔助選擇法可以保持群體多樣性,聚類(lèi)方法也可以保證外部集合的非劣個(gè)體數目不超過(guò)規定范圍，且不破壞其分布特征4結論傳統算法在處理多目標優(yōu)化問(wèn)題上,主要優(yōu)點(diǎn)在于其計算量小、計算速度快;設計簡(jiǎn)單,數學(xué)建模容易;具有充分的理論支持.進(jìn)化算法盡管理論基礎還不完善，但由于其適應性、通用性、并行性和擴展性等優(yōu)點(diǎn)，已被廣泛應用于多目標問(wèn)題求解,并取得了良好效果.實(shí)際問(wèn)題往往由多個(gè)互相沖突的目標組成,傳統算法將各目標聚合成單目標函數求解,對Pareto 最優(yōu)解前端形狀敏感,不能很好處理前端凹部,對于大規模問(wèn)題也很少真正被使用傳統方法存在著(zhù)很大的局限性.進(jìn)化算法能處理大規模搜索空間、在單輪優(yōu)化期間產(chǎn)生多個(gè)均衡解,有地直肥了件運古比的易四性但進(jìn)化算法例如遺傳算法，也存在早熟和欺騙的問(wèn)題，觖少完整的收斂性證明等中國煤化工在解決多目標問(wèn)題時(shí)，并不存在一-種統-的最佳算法， 也MHC N M H G于其他算法的算法.正所謂“具體問(wèn)題，具體分析”,在解決具體的多目標問(wèn)題時(shí)，往往需要對已有算法進(jìn)行設計和調整,使得它只在第4期方詩(shī)虹等:多目標優(yōu)化方法研究661求解該類(lèi)問(wèn)題時(shí)具有其他算法不能達到的最佳性能結構.參考文獻:[1]姚新勝. 滿(mǎn)意優(yōu)化原理及其在機械工程領(lǐng)域中的應用研究[D].成都:西南交通大學(xué), 2002.[2PARETO V. Cours DEconomie Politique[M]. Lausanne: F Rouge, 1896.[3] ZITZLER E, DEB K, THIELE L.Comparison of Multi- objective Evolutionary Algorithm: Empirical Results[J. EvolutionaryComputation, 2000, 8(2): 173-195.[4} LEUNG Y W, WANG Y E. U-measure: A qualiy measure for muliobjecive programming U IEEE Transactions Oil Systems Manand Cybemetics. Part A:Systems and Humans, 2003, 3(33) 337-343.[5] K DEB. Multi objecive opimization using evolutionary algorithm[M. New York: John Wiley&Sons, Lid, 2001.6) 鄭金華多目標進(jìn)化算法及其應用[M].北京:科學(xué)出版社，2007.[7] SCHOA 1. Fault tolerant design using single and multi-iteria genetic aigorithms[D]. Canbridge: Depatnent of Acronautics andAstronautics, Massachusetts Institute of Technology, 1995.Research on methods of multi-objective optimizationFANG Shi-hong, DING Ke-wei, CHEN Ya-xi(Soubwest University for Nationalitis Chengdu 610041, P.R.C.)Abstract: This paper expounds the features of multi-objective optimization problem, and presents the mathematical model ofMOP and the theory of Pareto optimal solution. It introduces the classical optimization and evolutionary optimization,especially the mouti-objctive evolutionary optimization based on genetic algorithm. Finally, it compares these two mcthods.Key words: multi- objective optimization problem; single- objective optimization problem; Pareto optimal solution; geneticalgorithm中國煤化工MHCNMHG