江　珊，陳　磊，劉海林

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520)

?

帶有權(quán)重偏好的多目標進化算法

江珊，陳磊，劉海林

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，廣東 廣州 510520)

摘要:對于現(xiàn)實生活中的一些多目標優(yōu)化問題，往往存在著多個決策者的偏好.提出了一種新的偏好方式：決策者對目標函數(shù)的權(quán)重偏好，該方法在Delphi法下由決策者對目標函數(shù)的重要性打分形成，能夠更好地體現(xiàn)出決策者的偏好，并且簡單易行.結(jié)合M2M算法，形成了一種求解多目標優(yōu)化問題的混合算法.數(shù)值實驗顯示,在不同偏好下，多目標優(yōu)化問題的結(jié)果也不一樣，這與實際情形相吻合.在實際生活中，這種方法也具有一定的現(xiàn)實意義.

關(guān)鍵詞:權(quán)重偏好； 多目標進化算法； 優(yōu)化

在實際生活中，有很多多目標決策問題[1-3]，而在決策者所給出的多目標之間往往是相互沖突的.所以,多目標決策往往只能綜合考慮所有目標后,得到一組非劣解(本文常稱為Pareto解[4]).作為當今研究的熱點問題,許多文獻[5-8]都對尋找多目標優(yōu)化問題Pareto解的方法進行了研究，并且在多領(lǐng)域應(yīng)用[9-10].但這些方法所求得的解是整個多目標優(yōu)化問題的非劣解集，而對于如何挑選解得工作仍交由決策者來做.由決策者在所給出的許多Pareto解集里面，選擇自己偏好的解，這需要決策者的一些專業(yè)知識以及專家的意見，才能夠挑選出滿意的解，因而這對于決策者來說是非常困難的.所以在有的多目標優(yōu)化問題中，人們往往只對與他們偏好有關(guān)的Pareto解感興趣.

近些年來，決策者在解決多目標優(yōu)化問題的時候，加入個人的偏好，成為了一個熱點話題.一般所加入的偏好方式有多種，比如，有的決策者偏好目標函數(shù)的部分區(qū)域，有的偏好一個點，有的會給出一個參考方向，而有的會給出目標函數(shù)的重要性等等[11-16].決策者不同，所加入的個人偏好也會不相同.本文將提出一種新的偏好方式，在Delphi[17]法下，決策者對目標函數(shù)的重要性進行打分，然后分析這些打分，得到目標函數(shù)的權(quán)重范圍；再經(jīng)過本人提出的處理分值的方法，不僅能夠求得目標函數(shù)的多組權(quán)重，得到多目標問題的偏好解，而且還能夠具體地反映出決策者的偏好解與權(quán)重范圍的集中程度的關(guān)系，從而更方便決策者挑選偏好解.

1多決策者偏好權(quán)重的產(chǎn)生

多目標優(yōu)化問題的模型

其中，x是決策變量，f(x) 是目標向量且各個目標可以是沖突的，x 是Rn中的超矩形域，表示決策空間.

1.1Delphi法簡介

Delphi是群決策中的一種交互式方法，采用背對背的通信方式征詢專家小組成員的預(yù)測意見，經(jīng)過幾輪征詢，使專家小組的預(yù)測意見趨于集中，最后做出符合市場未來發(fā)展趨勢的預(yù)測結(jié)論.Delphi 法使用時第一輪成員的反應(yīng)常常是非常分散的，在以后的各輪，通過信息反饋和交互，群的反應(yīng)即種群中多個成員反應(yīng)的平均值將愈來愈集中.引入Delphi法來處理多目標優(yōu)化問題的優(yōu)點是專家對目標函數(shù)的重要性打分具有一定的代表性、真實性、合理性.經(jīng)過三四輪的打分，目標函數(shù)的重要性分值就會趨于穩(wěn)定，而且相對比較集中，那么得到的最后的結(jié)果就是相對比較穩(wěn)定的目標函數(shù)的權(quán)重范圍.

1.2目標函數(shù)偏好權(quán)重的產(chǎn)生

1.2.1采用德爾菲法得到最后一輪的結(jié)果

1.2.2給出每個目標函數(shù)的打分區(qū)間以及每個區(qū)間的概率

1.2.3采用輪盤賭的方法得到目標的權(quán)重

這樣就確定了目標函數(shù)的權(quán)重，然后再采用M2M[18]的方法進行優(yōu)化求解.

2仿真測試

2.1測試問題

問題1

問題2

問題3

2.2測試方法分析

首先測試的3個問題，前兩個是有2個目標函數(shù)優(yōu)化問題，第3個是3個目標函數(shù)的優(yōu)化問題，那么可以采用基于Pareto方法的M2M算法進行計算，求出問題的非支配解集和Pareto曲線，然后采用本文所提出的方法進行偏好分析，最后得到具體的權(quán)重.首先對3個問題進行計算:種群規(guī)模為100，進化代數(shù)為10 000，交叉率為0.7，變異率為0.01.

問題1、2、3的無偏好Pareto曲線圖分別見圖1、圖2、圖3.

圖1　問題1無偏好Pareto解

采用Delphi法進行打分，假設(shè)10個專家對這3個問題的各個目標函數(shù)的重要性打分如表1、表2所示.(令問題1和2的兩個目標函數(shù)的打分一樣的情況)

圖2　問題2無偏好Pareto解

圖3　問題3無偏好Pareto解

專家目標函數(shù)f1目標函數(shù)f2總分170301002663410035842100465351005633710066040100759411008613910096535100106733100

首先可以計算出兩個目標函數(shù)的權(quán)重偏好范圍，由表1得到，f1的打分區(qū)間為[58,70],f2的打分區(qū)間為[30,42]，所以f1的權(quán)重偏好范圍為[0.58,0.7],f2的權(quán)重偏好范圍為[0.3,0.42].從表2得到問題3的3個目標函數(shù)的權(quán)重偏好范圍分別為[0.3,0.42],[0.24,0.3],[0.32,0.45].然后采用上面的權(quán)重選取方法，求出問題的偏好解.

表2　專家對問題3的打分(偏好2)

那么這3個問題在這兩組打分下的最優(yōu)解(問題1和問題2的打分一樣的情況下)見圖4、圖5、圖6.

圖中粗線部分表示求得的偏好解，細線部分表示沒有偏好的最優(yōu)解集.

圖4　問題1偏好Pareto解

圖5　問題2偏好Pareto解

圖6　問題3在偏好2下的Pareto解

當把問題1、2兩個問題目標函數(shù)的打分互換一下，就可以得到偏好3，如表3所示.

表3交換表1中專家對問題1、2的打分(偏好3)

Tab.3Exchange expert’s scores of Questions 1 and 2 in Table 1(Preference 3)

專家目標函數(shù)f1目標函數(shù)f2總分130701002346610034258100435651005376310064060100741591008396110093565100103367100

此時問題1、2得到的偏好解分別如圖7、圖8所示.

在第3組權(quán)重下，放大問題1、問題2所得的偏好圖分別如圖9、圖10所示.

2.3測試結(jié)果分析

從所得到的圖4～8中可以看到，所求出的偏好解是最優(yōu)解的一部分，而且對目標函數(shù)是二維的問題很容易看出，在第1組偏好下所求得的解是偏向f2的，因為由偏好權(quán)重看出，目標函數(shù)f2要比f1重要.在第2組交換打分后的偏好下所求得的解是偏向f1的，因為由偏好權(quán)重看出，目標函數(shù)f1要比f2重要.

圖7　問題1在偏好3下的Pareto解

圖8　問題2在偏好3下的Pareto解

圖9　問題1在偏好3下解的擴大

圖10　問題2在偏好3下解的擴大

在所得到的只有偏好解的圖形9、圖10中可以看出，偏好解是有一部分集中、一部分分散的，這與決策者的打分完全一致的，如果決策者的打分很平均，那么得到的偏好解也很平均.所以此種處理打分的方法能夠很好地體現(xiàn)決策者的偏好，具有一定的現(xiàn)實意義.

3結(jié)論

首先介紹了處理偏好權(quán)重的方法，然后通過實例計算得到了期望的結(jié)果.結(jié)果證明了這種方法在處理權(quán)重上是十分有效的.這種方法不用對優(yōu)化算法進行修改，只是利用原有的優(yōu)化方法來進行計算，這種處理偏好的方法易于理解和使用；對于任意維的多目標都可以求出偏好權(quán)重，需要做的是對于原有的解決多目標優(yōu)化權(quán)重算法的改進，從而更好地結(jié)合此種方法，獲得更好的偏好解.

參考文獻：

[1]JARED L C, David H M.A review and evaluation of multiobjective programming techniques[J].Water Resources Research, 1975, 11(2):208-220.

[2] LOUCKS D P.Conflict and choice: Planning for multiple objectives[C]∥ Blitzer C R, Clark P B, Taylor L. Economy wide Models and Development Planning. New York ：New York Oxford University Press，1975：236-321.

[3] PETER C F.A survey of multiattribute/multicriterion evaluation theories[C]∥Zionts S.Multiple Criteria Problem Solving. Berlin：Berlin Springer-Verlag，1987：181-224.

[4] 陳鋌.決策分析[M].北京：科學(xué)出版社，1987.

[5] PARMEE I C, CVETKOVIC D, WATSON A H.Multiobjective Satisfaction within an Interactive Evolutionary Design Environment[J].Evolutionary Compution, 2008, 8(2):197-222.

[6] KE L J，ZHANG Q F，BATTITI R.MOEAD-ACO: A multiobjective evolutionary algorithm using decomposition and ant[J].IEEE Transactions on Systems Man and Cybernetics Part A—Systems and Human, 2013, 10(99):1-15.

[7] CHENG J，ZHANG G X，LI Z D，et al.Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems[J].Soft Computing, 2012, 16(4):597-614.

[8] 蒲保興，楊路明，謝東.嵌入用戶偏好區(qū)域的多目標優(yōu)化算法[J].小型微型計算機系統(tǒng), 2009, 30(1):144-147.

PU B X，YANG L M,XIE D.Multi-objective Optimization Algorithm Embedded by User Preference Region[J].Journal of Chinese Computer Systems, 2009, 30(1):144-147.

[9] 張金鳳.多目標進化算法在垃圾收運系統(tǒng)中的應(yīng)用[J].廣東工業(yè)大學(xué)學(xué)報, 2011, 28(2):76-80.

ZHANG J F.The application of the multi-objective evolutionary algorithm in the collection and transportation system of solid waste[J].Journal of Guangdong University of Technology, 2011, 28(2):76-80.

[10]謝桂芩; 涂井先.分區(qū)域多目標進化算法在協(xié)同車輛路徑問題中的應(yīng)用[J].廣東工業(yè)大學(xué)學(xué)報, 2011, 28(4):38-44.

XIE G Q, TU J X, The application of multi-objective evolutionary algorithm in collaborative vehicle routing[J].Journal of Guangdong University of Technology, 2011, 28(4):38-44.

[11] CVETKOVIC D, PARMEE I C.Preferences and their application in evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation, 2012, 6(1):42-57.

[12] KIM J H, HAN J H, KIM R H,et al. Preference-based solution selection algorithm for evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation, 2012, 1(16):20-34.

[13] LI Z H, LIU H L.Preference-based evolutionary multi-objective optimization[J].Proceedings International Conference on Computational Intelligence and Security, 2012, 1(5):168-173.

[14] 余進，何正友，錢清泉.基于偏好信息的多目標微粒群優(yōu)化算法研究[J].控制與決策, 2009, 24(1):66-70.

YU J, HE Z Y, QIAN Q Q.Multi-objective particle swarm optimization algorithm based on the preference information research[J].Control and Decision-making, 2009, 24(1):66-70.

[15] 崔遜學(xué)，林闖.一種基于偏好的多目標調(diào)和遺傳算法[J].軟件學(xué)報, 2005, 16(5):761-770.

CUI X X, LIN C.Multi-objective mixed genetic algorithm based on preference[J].Journal of Software, 2005, 16(5):761-770.

[16] ZITZLER E, DEB K, THIELE L.Comparison of multiobjective evolutionary algorithms: empirical results[J].Evolutionary Compution, 2000, 8(2):173-195.

[17] 徐玖平, 陳建中.群決策理論與方法及實現(xiàn)[M].北京：清華大學(xué)出版社，2009, 414.

[18] LIU H L, GU F Q, ZHANG Q F.Decomposition of a multi-objective optimization problem into a number of simple multi-objective subproblems[J].IEEE Trans Evol. Computation Press, 2014, 5(1):16-22.

ulti-objective Evolutionary Algorithm with Weight Preference

MJiang Shan, Chen Lei, Liu Hai-lin

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:For the multi-objective optimization in real life，there are many preferences of decision makers. This paper proposes a new preference: the weight preference of objective function which derives and scores from its importance according to policy makers by Delphi method. This preference, expressive and facilitating, combines with M2M algorithm into a hybrid algorithm for solving multi-objective optimization problems. The experiments show that various preferences lead to different results in working out the multi-objective optimization problem, which coincides with the actual practice. Apart from its theoretical contribution, this preference also has its realistic significance.

Key words:weight preference; multi-objective evolutionary algorithm; optimization

中圖分類號:TP301

文獻標志碼:A

文章編號:1007-7162(2016)01- 0067- 06

doi:10.3969/j.issn.1007- 7162.2016.01.013

作者簡介:江珊(1989-)，女，碩士研究生，主要研究方向為最優(yōu)化方法及應(yīng)用.

基金項目:廣東省自然科學(xué)基金資助項目(2012B091100033)

收稿日期:2014- 06- 23