東莞理工學(xué)院學(xué)報(bào)第21卷第3期Vol.21 No.32014年6月JOURNAL OF DONGGUAN UNIVERSITY OF TECHNOLOGYun.__ 2014多目標(biāo)優(yōu)化問題的研究朱君蔡延光湯雅連楊軍(廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州510006 )摘要:針對(duì)傳統(tǒng)方法求解多目標(biāo)優(yōu)化問題的局限性，應(yīng)用一種新的算法求解。遺傳算法從問題解的串集開始搜索，覆蓋面大，可以同時(shí)處理群體中的多個(gè)個(gè)體，利于全局擇優(yōu)，減少陷入局部最優(yōu)的風(fēng)險(xiǎn)，而最小生成樹具有過程簡(jiǎn)單清晰、適用性廣泛的特點(diǎn)，結(jié)合兩者的優(yōu)點(diǎn)，構(gòu)造了基于生成樹的遺傳算法。首先通過加權(quán)目標(biāo)規(guī)劃法求出最優(yōu)解，然后通過遺傳算法和基于生成樹的遺傳算法求解，結(jié)果表明，對(duì)于小規(guī)模的多目標(biāo)優(yōu)化問題，兩種算法都可以求出最優(yōu)解，在求解時(shí)間方面，基于生成樹的遺傳算法比遺傳算法更優(yōu)越。關(guān)鍵詞:多目標(biāo)優(yōu)化問題;最小生成樹;遺傳算法中圖分類號(hào): TP2文獻(xiàn)標(biāo)識(shí)碼: A文章編號(hào): 1009-0312 (2014) 03 -0046 -04在現(xiàn)實(shí)生活中，某個(gè)設(shè)計(jì)方案只要求某- -項(xiàng)目標(biāo)達(dá)到最優(yōu)，這是單目標(biāo)優(yōu)化問題。如果設(shè)計(jì)方案期望某幾項(xiàng)指標(biāo)均能達(dá)到最優(yōu)值，這樣的問題就稱為多目標(biāo)優(yōu)化設(shè)計(jì)問題。比如廠家生產(chǎn)某種產(chǎn)品，既要求投人資金少，工人少，降低成本，又要工作效率高，利潤高，這就是-個(gè)多目標(biāo)優(yōu)化問題。現(xiàn)實(shí)生活中，多多標(biāo)優(yōu)化問題"中的各個(gè)子目標(biāo)一般是相互矛盾的，也就是同時(shí)使所有子目標(biāo)都達(dá)到最優(yōu)是不可能的，最終目標(biāo)是盡最大可能達(dá)到最優(yōu)化，它的解并不是唯一-的，而是由多個(gè)最優(yōu)解組成的滿意解，集合中的各個(gè)元素稱為Pareto最優(yōu)解或非劣最優(yōu)解。由于該問題模型在現(xiàn)實(shí)生活中普遍存在，所以本文研究的多目標(biāo)優(yōu)化問題具有實(shí)際應(yīng)用意義。目前，多目標(biāo)優(yōu)化問題也得到了廣泛的研究。謝濤等人23介紹了基于Pareto最優(yōu)概念的多目標(biāo)演化算法中的主要技術(shù)和理論結(jié)果，詳細(xì)介紹了基于偏好的個(gè)體排序、適應(yīng)值賦值及共享函數(shù)等。王躍宣等人”考慮了對(duì)約束條件的處理問題，提出了求解帶約束的多目標(biāo)優(yōu)化遺傳算法，利用鄰域比較與存檔操作遺傳算法處理多個(gè)相互沖突的目標(biāo)的優(yōu)化;馬瑞等人[41 提出了解決多目標(biāo)優(yōu)化問題的新方法和綜合考慮水火協(xié)調(diào)及能源、環(huán)境和經(jīng)濟(jì)等多目標(biāo)優(yōu)化的分組分段電力市場(chǎng)競(jìng)標(biāo)新模型，結(jié)果表明了算法的正確性和模型的有效性;李寧等人5提出了一種新的基于粒子群的多目標(biāo)優(yōu)化算法，用搜索過程中所發(fā)現(xiàn)非劣解的一部分構(gòu)成精英集,通過小生境技術(shù)和部分變異的方法提高非劣解集的多樣性和分散性;.張麗霞等人61應(yīng)用多目標(biāo)決策理論求解網(wǎng)絡(luò)計(jì)劃的多目標(biāo)優(yōu)化模型;王曉鵬?1在自適應(yīng)遺傳算法的基.礎(chǔ)上引入群體排序技術(shù)、小生境技術(shù)和Pareto 解集過濾器，建立了適用于多目標(biāo)優(yōu)化設(shè)計(jì)的Pareto遺傳算法，設(shè)計(jì)表明Pareto遺傳算法是十分有效的。1多目標(biāo)優(yōu)化問題描述多目標(biāo)優(yōu)化問題!8起源于許多實(shí)際復(fù)雜系統(tǒng)的設(shè)計(jì)、建模和規(guī)劃問題，包括工業(yè)制造、城市運(yùn)輸、森林管理、產(chǎn)品制造、城市布局、網(wǎng)絡(luò)布局等。幾乎每個(gè)重要的現(xiàn)實(shí)決策問題都要考慮不同約束和處理若干相互沖突的子目標(biāo)。多目標(biāo)優(yōu)化問題可以表達(dá)成下面的形式，如式(1) 和(2)所示。max{z =f(x),2 =fe(x)(1)中國煤化工s.t. g;(x)≤0,i =(2)MHCNM HG收稿日期: 2013-12-04 .基金項(xiàng)目:國家自然科學(xué)基金(61074147; 61074185); 廣東省自然科學(xué)基金(S201 1010005059; 83510090000002); 廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目(2012B091000171; 201 I B090400460);廣東省科技計(jì)劃項(xiàng)目(2012B050600028 ; 2010B090301042)。作者簡(jiǎn)介:朱君(1991-), 男，江西新余人，碩士生，主要從事組合優(yōu)化、物流信息技術(shù)與應(yīng)用方向研究。第3期.朱君，等:多目標(biāo)優(yōu)化問題的研究472兩種求解MOP的方法2. 1加權(quán)目標(biāo)規(guī)劃現(xiàn)實(shí)的決策環(huán)境中各個(gè)目標(biāo)的重要程度是不可能完全-致的，決策者可以判斷分析各個(gè)目標(biāo)的重要性，而且子目標(biāo)在總目標(biāo)中也占不同的重要程度，可以通過加權(quán)系數(shù)進(jìn)行目標(biāo)規(guī)劃求解。加權(quán)系數(shù)是達(dá)成函數(shù)中各目標(biāo)偏差變量的系數(shù)。加權(quán)系數(shù)是一種可 以用數(shù)量來衡量的指標(biāo)，對(duì)屬于同- -優(yōu)先等級(jí)的不同目標(biāo)可按其重要程度分別給予不同的加權(quán)系數(shù)來反映各加權(quán)目標(biāo)規(guī)劃的數(shù)學(xué)模型如下，式(3)為目標(biāo)函數(shù)，式(4) 為約束條件。minf= 2(rd; +fid)(3)2 Cyxj +d;-dt= e,i = 1,2,,m .s. t.(4)x;≥0,j = 1,2,.,nd; ,dt≥0,i = 1,2,.",mx;:多目標(biāo)規(guī)劃的設(shè)計(jì)變量;cg:目標(biāo)約束的系數(shù);e;:第i個(gè)目標(biāo)的期望值;f; :目標(biāo)中d;的系數(shù):f :目標(biāo)中d;的系數(shù);d; ,di :偏差變量。2.2基于生 成樹的遺傳算法遺傳算法的基本特點(diǎn)是多方向和全局搜索，帶有潛在解的種群能夠-代代地維持下來。最小生成樹問題( minimim spanning tree problem)由Boruvka8于1926年首次提出，此后，最小生成樹問題被廣泛應(yīng)用于許多組合優(yōu)化問題中。最小生成樹問題中，考慮連通圖G = (V,E),其中V = {vr,0,.,on} 是頂點(diǎn)的有效集合,E = {e,是邊的有限集合。邊將頂點(diǎn)之間連接起來。每個(gè)邊有一個(gè)正實(shí)數(shù)權(quán)重W = {w,v,.,wm}表示距離或費(fèi)用。最小生成樹問題就是尋找圖G中連接所有頂點(diǎn)的具有最小權(quán)重的子圖。Pareto解集的求解過程1)設(shè)置迭代標(biāo)志k = 1,當(dāng)前迭代世代t產(chǎn)生的Pareto解集E(t) = {φ|;2)若k > i_ size,停止;否則,執(zhí)行3);3)評(píng)價(jià)染色體Ar,得到解F。= [f:(A)f2(A)--f(A1)],將其與E中所有Pareto解比較;(i):若任何Pareto優(yōu)于它，執(zhí)行4);(i):若它優(yōu)于部分Pareto解，則用它代替E中較差的解;(i):若它是新解，則加入E中。4):h =k+1，返回2)。整個(gè)算法的偽代碼如下:procedure: st GA/ 'mtpbegint←0 :初始化P(t) ;計(jì)算P(t)的目標(biāo)函數(shù)值;確定Pareto 解集E(1) ;計(jì)算P(1)的適應(yīng)值中國煤化工while不滿足終止條件doYHCNM HGregin對(duì)P(1)進(jìn)行雜交和變異，得到C(1) ;更新Pareto解集E(t) ;計(jì)算C(t)的目標(biāo)函數(shù)值;48東莞理工學(xué)院學(xué)報(bào)2014年.計(jì)算C(t)的適應(yīng)值;從C(1)中選擇P(1 +1) ;1←1+1 ;end3仿真分析某工廠準(zhǔn)備開發(fā)3種產(chǎn)品，重點(diǎn)是確定3種產(chǎn)品的生產(chǎn)計(jì)劃，并盡量達(dá)成目標(biāo)?？偫麧櫜坏陀?20萬元，3種產(chǎn)品的單位利潤分別為元8、9元和2元;有50名工人，每生產(chǎn)3種產(chǎn)品各1萬件分別需要的工人數(shù)量為6、1和5名;總投資資金不超過60萬元，且生產(chǎn)3種產(chǎn)品需要投人成本2、9和6元。各目標(biāo)的懲罰權(quán)重和各產(chǎn)品的單位貢獻(xiàn)如表1和表2所示。表1各目標(biāo)的懲罰權(quán)表2各產(chǎn)品的單位貢獻(xiàn)目標(biāo)因素懲罰權(quán)重產(chǎn)品1產(chǎn)品2 產(chǎn)品31總利潤低于目標(biāo)的每一-萬元，5總利潤/萬元大于等于120工人低于目標(biāo)的每-一個(gè)人, 3工人/名.等于50超過目標(biāo)的每-一個(gè)人，13投資資金超過目標(biāo)的每- -萬元，2投資資金/萬元小于等于603.1加權(quán)目標(biāo)規(guī)劃法求解MOP建立數(shù)學(xué)模型1)決策變量產(chǎn)品i的產(chǎn)量x:(i = 1,2,3);正偏差變量d↑、 負(fù)偏差變量d;(i = 1,2,3)2)目標(biāo)函數(shù)Opt imization terminat ed.1.各產(chǎn)品需要生產(chǎn)的數(shù)量為(萬件) :minz=5d*+3d2+d3+2d;7. 17396.95650. 00003)約束條件' 8x1 +9x2 +2x3 +d°-di = 1202.偏差變量為:6x1 +x2 +5x3 +dI -d2 = 50序號(hào)正偏差負(fù)偏差1. 00002x1+9x2+6x3+d3-d3=602. 000000.0000x;≥0,i = 1,2,33. 0000 16. 95650.000d*≥0,d;≥0,i = 1,2,3,di和d2取整數(shù)求解結(jié)果:應(yīng)用Matlab 求解界面如圖1所示。生3.實(shí)際獲得利潤、需要工人及投入資金分別為:實(shí)際獲得利潤為: 120. 000000產(chǎn)產(chǎn)品1、2和3的數(shù)量分別為71739件、69565 件和需要工人為: 50. 000000件。除了第3個(gè)目標(biāo)，其他2個(gè)目標(biāo)都能達(dá)成，獲投入資金為: 76. 956522得利潤120萬元，需要工人50人，投入資金76. 96萬4.各目標(biāo)的達(dá)成情況為:3元。03.2 應(yīng)用兩種算法求解MOPstGA的參數(shù)設(shè)置:初始種群pop_ size= 30，交.圖1應(yīng)用 Matlab求解界面叉概率p。=0.8，變異概率pm = 0.02，最大迭代次中國煤化工數(shù)maxgen=1000，運(yùn)行30次。GA的參數(shù)設(shè)置:初始種群pop_ size =30，交叉概率p。MHCNMHG.=0.02，最大迭代次在Intel (R) CoreTM i3 CPU 2. 53CHz、內(nèi)存為2.0 G、安裝系統(tǒng)為win7 的PC機(jī)上采用MatlabR2010b編程實(shí)現(xiàn)。第3期朱君，等:多目標(biāo)優(yōu)化問題的研究49表3 GA和 st-GA求解MOP的結(jié)果;Ast-CA最優(yōu)解占總運(yùn)行次數(shù)的百分比運(yùn)行時(shí)間/s100 。1.340.91求解結(jié)果:由表3可知，通過兩種算法都可以求得滿意解，但是st-GA比GA消耗更少的時(shí)間就可以找到最優(yōu)解，所以，針對(duì)多目標(biāo)優(yōu)化問題，st GA更適用。4結(jié)語本文應(yīng)用一種新的算法求解多目標(biāo)優(yōu)化問題。由于遺傳算法從問題解的串集開始搜索，覆蓋面大,可以同時(shí)處理群體中的多個(gè)個(gè)體，利于全局擇優(yōu)，減少陷人局部最優(yōu)的風(fēng)險(xiǎn)，而最小生成樹具有過程簡(jiǎn)單清晰、適用性廣泛的特點(diǎn)，構(gòu)造了基于生成樹的遺傳算法。結(jié)果表明，對(duì)于小規(guī)模的多目標(biāo)優(yōu)化問題，雖然兩種算法都可以求出最優(yōu)解，但在求解時(shí)間方面，基于生成樹的遺傳算法比遺傳算法更優(yōu)越,應(yīng)用改進(jìn)的算法求解大規(guī)模的多目標(biāo)優(yōu)化問題是下一-步要研究的內(nèi)容。參考文獻(xiàn)1] 肖曉偉，肖迪，林錦國,等，多目標(biāo)優(yōu)化問題的研究概述倡[J].計(jì)算機(jī)應(yīng)用研究, 2011, 28(3) :805 - 809.[2] 謝濤，陳火旺，康立山、多目標(biāo)優(yōu)化的演化算法[J].計(jì)算機(jī)學(xué)報(bào), 2003, 26(8): 997 - 1003.[3] 王躍宜,劉連臣，牟盛靜，等.處理帶約束的多目標(biāo)優(yōu)化進(jìn)化算法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版, 2005, 45(1): 103 - 106.[4] 馬瑞，賀仁睦,顏宏文,等.考慮水火協(xié)調(diào)的多目標(biāo)優(yōu)化分組分段競(jìng)標(biāo)模型[J].中國電機(jī)工程學(xué)報(bào), 2004, 24(11): 53-57.[5] 李寧，鄒彤，孫德寶基于粒子群的多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用, 2005, 41(23): 43 -46.[6] 張麗霞，侍克斌.施工網(wǎng)絡(luò)進(jìn)度計(jì)劃的多目標(biāo)優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐, 2003, 23(1): 56-61.[7] 王曉鵬.多目標(biāo)優(yōu)化設(shè)計(jì)中的Pareto 遺傳算法[J].系統(tǒng)工程與電子技術(shù)，2003, 25(12): 1558 - 1561.[8] 玄光男,程潤偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2003.Research on Multiobjective Optimization ProblemZHU Jun CAI Yan- guang TANG Ya4ian YANG Jun( School of Automation，Guangdong University of Teehnology , Guangzhou 5 10006, China)Abstract Aiming at the limitation of the traditional methods to solve the multi -objective optimization problem, this paperapplies a new kind of algorithm to it. Genetic Algorithm ( GA) starts to search from the set of solution with its big coverage able tohandle more than one individual at the same time，beneficial to global optimization, reducing the risk of fall into local optimum,while the minimum spanning tree has the characteristics of simple process and wide applicability . Combined with the advantages ofthe both algorithms ，genetic algorithm is constructed on the basis of spanning tree . By finding the optimal solution by weighted goalprogramming method，and then solving the problem by the genetic algorithm and genetic algorithm based on spanning tree， the resultshows that for small. scale multi objective optimization problem，two algorithms can find out the optimal solution，and in terms of sol-ving time，genetic algorithm based on spanning tree is superior to genetic algorithm .Key words multiobjective optimization ; minimum spanning tree ; genetic algorithm中國煤化工MYHCNM HG