第38卷第4期西南民族大學學報.自然科學版Jul. 2012Journal of Southwest University for Nationalities.Natural Science Edition文章編號: 1003-2843(2012)04-065804多目標優(yōu)化方法研究方詩虹,丁可偉,陳雅茜1(I.西南民族大學計算機科學與技術學院,四川成都610041;2. 西南民族大學預科教育學院,四川咸都610041)摘要:闡述了多目標優(yōu)化問題的特點,給出了該問題的數(shù)學模型及Pareto 最優(yōu)解的定義,介紹了用于解決多目標問題的傳統(tǒng)優(yōu)化方法和進化優(yōu)化方法，并著重介紹了基于遺傳算法的多目標優(yōu)化方法.最后對傳統(tǒng)方法和進化方法進行了比較.關鍵字:多目標優(yōu)化問題;單目標優(yōu)化問題; Pareto最優(yōu)解;遣傳算法中圖分類號: TP301.6文獻標識碼: Adoi: 0.396/j.ssm.1003-2483 2012.04.341引言現(xiàn)代社會各行各業(yè)的應用中，常常遇到需要使多個目標在給定區(qū)域上盡可能最優(yōu)的決策問題.例如在進行網絡設計時，在希望成本盡可能低的同時，網絡帶寬盡可能高,此外可能還需要考慮可靠性和可維護性等.這些目標的改善可能相互抵觸,在提高其中某個目標時，會導致其他目標效果的下降.例如低成本難以滿足高帶寬而好的可維修性會降低可靠性.所以，實際應用中必須在多個期望目標之間取得平衡，從而獲得-一個相對優(yōu)化的結果.這種多個數(shù)值目標在給定區(qū)域上的最優(yōu)化問題即多目標優(yōu)化問題(Muti-bjective Optimization Problem,MOP).2問題 的描述2.1多 目標優(yōu)化問題的數(shù)學模型單目標優(yōu)化問題(Single objective Optimization Problem, SOP)往往只有一個解存在，求得該解即得到了最優(yōu)解.而多目標優(yōu)化問題MOP與單目標優(yōu)化問題SOP相比，有著本質的區(qū)別".多目標優(yōu)化問題MOP可作如下數(shù)學描述:定義1一般由n個決策變量參數(shù)、k 個目標函數(shù)和m個約束條件組成的MOP問題,最優(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)為約束函數(shù).最大化與最小化問題可以相互轉化,本文以最大化多目標為例2.2 Pareto 最優(yōu)解中國煤化工收稿日期: 2012-04-24作者簡介:方詩虹(1980-), 女講師.YHCNMHG.基金項目:中央高校基本科研業(yè)務費專項資金(12NZYQN16)資助..第4期方詩虹等:多目標優(yōu)化方法研究659Francis Ysidro Edgeworth 于1881 年提出多目標問題“最優(yōu)解”的概念即解決多目標問題，實際上是求解- -組均衡解,而非單個目標全局最優(yōu)解.法國經濟學家和社會學家Vilfredo Pareto在1896年推廣了這個概念1, 他提出向量化概念從經濟學角度將本質上不可比較的多個目標轉化成單個指標進行優(yōu)化求解.定義2對于集合AS X,當且僅當決策向量x∈X;為非劣,有不3a∈A:a>x.(2)即當且僅當x在X,中是非劣的，決策向量x才是Pareto 最優(yōu)解.其中,對于決策向量a、x,當且僅當f(a)>f(x)時，有a>x,即a優(yōu)于x.2.3 Pareto 最優(yōu)解集的評價準則由于多目標優(yōu)化問題的結果并不是唯- - 確定的，所以對其非劣解集質量評價也相對困難的. - -般來說，- 一個比較理想的非劣解集應包括以下幾個方面以:(1)獲得的非劣解集與真實非劣解集的距離應盡可能小;(2)獲得的非劣解集應均勻分布;(3)獲得非劣解集應具有良好的擴展性,即非劣前沿的端點應盡可能接近單目標極值.為了方便對多目標優(yōu)化問題非劣解集質量進行評價,在隨后的研究中，人們采用一-些度量方法量化以上3個衡量標準，對算法的性能進行評價,主要有U-度量法+、寬廣性度量法(Maximum Spread-measure)5、 C-度量法'和S-度量法!"!3進化的多 目標優(yōu)化方法多目標進化算法(Multi-objective Evolutionary Algorithms, MOEAs)在處理大規(guī)模的搜索空間、在單輪優(yōu)化期間可以產生多個均衡解，且對目標最優(yōu)均衡面的形狀和連續(xù)性不敏感，可 以很好地逼近非凸或不連續(xù)的均衡面,能夠有效克服傳統(tǒng)方法局限性.Vanveldhuizen"2)按求解和決策的關系把多目標優(yōu)化求解方法分為三類:(1)先決策再搜索解:決策者先給出目標優(yōu)先等級，將多目標合成數(shù)量成本函數(shù),再由算法搜索最優(yōu)解,如評價函數(shù)法;(2)邊決策邊搜索解:決策者和算法互動，前者提供目標優(yōu)先關系，后者提供最新解,根據最新解產生更好的目標優(yōu)先關系，交互求解;(3)先搜索解再決策:算法搜索到解集后，再由決策者確定或選擇解,如理想點法.在眾多的方法中，先搜索再決策的方法較多,而使用遺傳算法作為進化方法的算法在MOEAs設計和應用中占主要地位.3.1 多目標遺傳算法對于如何求解多目標問題的Pareto 最優(yōu)解,目前已提出了多種基于遺傳算法的求解方法，主要有并列選擇法、權重系數(shù)變化法、排序選擇法、共享函數(shù)法和外部輔助選擇法等"!.3.2 權重系數(shù)變化法這是基于目標加權法的遺傳算法,例如Hajela和Lin提出的“可變目標權重聚合法”.在這種非Pareto方法中,每個目標均有一一個權重,但權重本身并不固定,為了搜索多個解,問題解和權重會動態(tài)變化，同時進化.這種方法計算效率較高，但在沒有足夠的信息時，無法確定合適的權重系數(shù)，只能通過權重系數(shù)組合函數(shù)的優(yōu)化結果來獲得最優(yōu)解.3.3排序選擇法Srinivas和Deb提出的“非劣分層遺傳算法(NSGA)”即屬于中國煤化工壽Pareto最優(yōu)個體的概念來對群體中的所有個體進行排序,由這個排序結果來實施MHC N MH G在前面的Pareto 最優(yōu)個體有更多機會遺傳到下一-代群體.經過數(shù)代循環(huán)后，最終得到Pareto 最優(yōu)解.其中,最優(yōu)個體排序方法如660西南民族大學學報.自然科學版第38卷下:StepI設置初始序號r=1;Step2確定群體中的Pareto最優(yōu)個體,定義其序號為r;Step3從群體中去掉最優(yōu)個體,并更改序號r=r+1;Step4回到Step2,直至將所有個體排序.Deb等人在2002年提出了NSGA-II,主要思想是對種群中的個體按Pareto進行排序,按照排序順序從小到大選擇個體,若遇相同序值的個體,則偏好位于目標空間中稀疏區(qū)域的個體.排序選擇法僅度量了各個個體之間的優(yōu)越次序,而未度量分散程度，故容易產生多個相似的Pareto 最優(yōu)解,難以生成分布較廣的解集..4 共享函數(shù)法這類算法的典型代表是Horm等人提出的“小生境Pareto遺傳算法".對某個個體而言,度量其附近存在多少種、多大程度相似個體的度量值,即小生境數(shù)(Niche Count).在進化算法中引入小生境方法后,對相同或相似個體數(shù)量加以限制，以便產生種類較多的不同最優(yōu)解共享函數(shù)法的過程如下:StepI從群體中隨機選取k個個體組成個體比較集合C ;Step 2從群體中隨機選擇兩個個體組成個體聯(lián)賽集合T ;Step 3比較集合T和C中各個個體的優(yōu)勝關系，如果T中的一個個體x比C中的所有個體都優(yōu)越，且T中的另-一個個體不比C中的所有個體優(yōu)越,則個體x遺傳到下一代群體中;如果無法獲得這樣的個體x,則從T中選擇小生境數(shù)較小的個體遺傳到下一代群體中.共享函數(shù)法能得到多種不同的Pareto最優(yōu)解但大量的評價和比較運算使其搜索效率較低.3.5外部輔助選擇法Zitzler和Thiele'提出的“強度Pareto進化算法‘及Cello和Toscano Pulido0提出的“微遺傳算法(Micro-GA)”等都屬于外部輔助選擇法,主要流程如下:StepI產生初始群體P和一個外部輔助非劣空的集合P';Step2將P中的非劣個體復制到P',將P'中的劣解剿除(第- -代無劣解);Step3對P'進行聚類處理,控制其規(guī)模不超過預定數(shù)N';Step4計算P和P'中個體適應度;Step5從PUP'中使用聯(lián)賽選擇機制進行選擇操作,直到配對池滿;Step 6交叉和變異;Step 7達到最大進化代數(shù)則停止否則轉到Step 2.外部輔助選擇法可以保持群體多樣性,聚類方法也可以保證外部集合的非劣個體數(shù)目不超過規(guī)定范圍，且不破壞其分布特征4結論傳統(tǒng)算法在處理多目標優(yōu)化問題上,主要優(yōu)點在于其計算量小、計算速度快;設計簡單,數(shù)學建模容易;具有充分的理論支持.進化算法盡管理論基礎還不完善，但由于其適應性、通用性、并行性和擴展性等優(yōu)點，已被廣泛應用于多目標問題求解,并取得了良好效果.實際問題往往由多個互相沖突的目標組成,傳統(tǒng)算法將各目標聚合成單目標函數(shù)求解,對Pareto 最優(yōu)解前端形狀敏感,不能很好處理前端凹部,對于大規(guī)模問題也很少真正被使用傳統(tǒng)方法存在著很大的局限性.進化算法能處理大規(guī)模搜索空間、在單輪優(yōu)化期間產生多個均衡解,有地直肥了件運古比的易四性但進化算法例如遺傳算法，也存在早熟和欺騙的問題，觖少完整的收斂性證明等中國煤化工在解決多目標問題時，并不存在一-種統(tǒng)-的最佳算法， 也MHC N M H G于其他算法的算法.正所謂“具體問題，具體分析”,在解決具體的多目標問題時，往往需要對已有算法進行設計和調整,使得它只在第4期方詩虹等:多目標優(yōu)化方法研究661求解該類問題時具有其他算法不能達到的最佳性能結構.參考文獻:[1]姚新勝. 滿意優(yōu)化原理及其在機械工程領域中的應用研究[D].成都:西南交通大學, 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) 鄭金華多目標進化算法及其應用[M].北京:科學出版社，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