带有权重偏好的多目标进化算法

江　珊，陈　磊，刘海林

(广东工业大学 应用数学学院，广东 广州 510520)



带有权重偏好的多目标进化算法

江珊，陈磊，刘海林

(广东工业大学 应用数学学院，广东 广州 510520)

摘要:对于现实生活中的一些多目标优化问题，往往存在着多个决策者的偏好.提出了一种新的偏好方式：决策者对目标函数的权重偏好，该方法在Delphi法下由决策者对目标函数的重要性打分形成，能够更好地体现出决策者的偏好，并且简单易行.结合M2M算法，形成了一种求解多目标优化问题的混合算法.数值实验显示,在不同偏好下，多目标优化问题的结果也不一样，这与实际情形相吻合.在实际生活中，这种方法也具有一定的现实意义.

关键词:权重偏好； 多目标进化算法； 优化

在实际生活中，有很多多目标决策问题[1-3]，而在决策者所给出的多目标之间往往是相互冲突的.所以,多目标决策往往只能综合考虑所有目标后,得到一组非劣解(本文常称为Pareto解[4]).作为当今研究的热点问题,许多文献[5-8]都对寻找多目标优化问题Pareto解的方法进行了研究，并且在多领域应用[9-10].但这些方法所求得的解是整个多目标优化问题的非劣解集，而对于如何挑选解得工作仍交由决策者来做.由决策者在所给出的许多Pareto解集里面，选择自己偏好的解，这需要决策者的一些专业知识以及专家的意见，才能够挑选出满意的解，因而这对于决策者来说是非常困难的.所以在有的多目标优化问题中，人们往往只对与他们偏好有关的Pareto解感兴趣.

近些年来，决策者在解决多目标优化问题的时候，加入个人的偏好，成为了一个热点话题.一般所加入的偏好方式有多种，比如，有的决策者偏好目标函数的部分区域，有的偏好一个点，有的会给出一个参考方向，而有的会给出目标函数的重要性等等[11-16].决策者不同，所加入的个人偏好也会不相同.本文将提出一种新的偏好方式，在Delphi[17]法下，决策者对目标函数的重要性进行打分，然后分析这些打分，得到目标函数的权重范围；再经过本人提出的处理分值的方法，不仅能够求得目标函数的多组权重，得到多目标问题的偏好解，而且还能够具体地反映出决策者的偏好解与权重范围的集中程度的关系，从而更方便决策者挑选偏好解.

1多决策者偏好权重的产生

多目标优化问题的模型

其中，x是决策变量，f(x) 是目标向量且各个目标可以是冲突的，x 是Rn中的超矩形域，表示决策空间.

1.1Delphi法简介

Delphi是群决策中的一种交互式方法，采用背对背的通信方式征询专家小组成员的预测意见，经过几轮征询，使专家小组的预测意见趋于集中，最后做出符合市场未来发展趋势的预测结论.Delphi 法使用时第一轮成员的反应常常是非常分散的，在以后的各轮，通过信息反馈和交互，群的反应即种群中多个成员反应的平均值将愈来愈集中.引入Delphi法来处理多目标优化问题的优点是专家对目标函数的重要性打分具有一定的代表性、真实性、合理性.经过三四轮的打分，目标函数的重要性分值就会趋于稳定，而且相对比较集中，那么得到的最后的结果就是相对比较稳定的目标函数的权重范围.

1.2目标函数偏好权重的产生

1.2.1采用德尔菲法得到最后一轮的结果

1.2.2给出每个目标函数的打分区间以及每个区间的概率

1.2.3采用轮盘赌的方法得到目标的权重

这样就确定了目标函数的权重，然后再采用M2M[18]的方法进行优化求解.

2仿真测试

2.1测试问题

问题1

问题2

问题3

2.2测试方法分析

首先测试的3个问题，前两个是有2个目标函数优化问题，第3个是3个目标函数的优化问题，那么可以采用基于Pareto方法的M2M算法进行计算，求出问题的非支配解集和Pareto曲线，然后采用本文所提出的方法进行偏好分析，最后得到具体的权重.首先对3个问题进行计算:种群规模为100，进化代数为10 000，交叉率为0.7，变异率为0.01.

问题1、2、3的无偏好Pareto曲线图分别见图1、图2、图3.

图1　问题1无偏好Pareto解

采用Delphi法进行打分，假设10个专家对这3个问题的各个目标函数的重要性打分如表1、表2所示.(令问题1和2的两个目标函数的打分一样的情况)

图2　问题2无偏好Pareto解

图3　问题3无偏好Pareto解

专家目标函数f1目标函数f2总分170301002663410035842100465351005633710066040100759411008613910096535100106733100

首先可以计算出两个目标函数的权重偏好范围，由表1得到，f1的打分区间为[58,70],f2的打分区间为[30,42]，所以f1的权重偏好范围为[0.58,0.7],f2的权重偏好范围为[0.3,0.42].从表2得到问题3的3个目标函数的权重偏好范围分别为[0.3,0.42],[0.24,0.3],[0.32,0.45].然后采用上面的权重选取方法，求出问题的偏好解.

表2　专家对问题3的打分(偏好2)

那么这3个问题在这两组打分下的最优解(问题1和问题2的打分一样的情况下)见图4、图5、图6.

图中粗线部分表示求得的偏好解，细线部分表示没有偏好的最优解集.

图4　问题1偏好Pareto解

图5　问题2偏好Pareto解

图6　问题3在偏好2下的Pareto解

当把问题1、2两个问题目标函数的打分互换一下，就可以得到偏好3，如表3所示.

表3交换表1中专家对问题1、2的打分(偏好3)

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

专家目标函数f1目标函数f2总分130701002346610034258100435651005376310064060100741591008396110093565100103367100

此时问题1、2得到的偏好解分别如图7、图8所示.

在第3组权重下，放大问题1、问题2所得的偏好图分别如图9、图10所示.

2.3测试结果分析

从所得到的图4～8中可以看到，所求出的偏好解是最优解的一部分，而且对目标函数是二维的问题很容易看出，在第1组偏好下所求得的解是偏向f2的，因为由偏好权重看出，目标函数f2要比f1重要.在第2组交换打分后的偏好下所求得的解是偏向f1的，因为由偏好权重看出，目标函数f1要比f2重要.

图7　问题1在偏好3下的Pareto解

图8　问题2在偏好3下的Pareto解

图9　问题1在偏好3下解的扩大

图10　问题2在偏好3下解的扩大

在所得到的只有偏好解的图形9、图10中可以看出，偏好解是有一部分集中、一部分分散的，这与决策者的打分完全一致的，如果决策者的打分很平均，那么得到的偏好解也很平均.所以此种处理打分的方法能够很好地体现决策者的偏好，具有一定的现实意义.

3结论

首先介绍了处理偏好权重的方法，然后通过实例计算得到了期望的结果.结果证明了这种方法在处理权重上是十分有效的.这种方法不用对优化算法进行修改，只是利用原有的优化方法来进行计算，这种处理偏好的方法易于理解和使用；对于任意维的多目标都可以求出偏好权重，需要做的是对于原有的解决多目标优化权重算法的改进，从而更好地结合此种方法，获得更好的偏好解.

参考文献：

[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].北京：科学出版社，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] 蒲保兴，杨路明，谢东.嵌入用户偏好区域的多目标优化算法[J].小型微型计算机系统, 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] 张金凤.多目标进化算法在垃圾收运系统中的应用[J].广东工业大学学报, 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]谢桂芩; 涂井先.分区域多目标进化算法在协同车辆路径问题中的应用[J].广东工业大学学报, 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] 余进，何正友，钱清泉.基于偏好信息的多目标微粒群优化算法研究[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] 崔逊学，林闯.一种基于偏好的多目标调和遗传算法[J].软件学报, 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] 徐玖平, 陈建中.群决策理论与方法及实现[M].北京：清华大学出版社，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-)，女，硕士研究生，主要研究方向为最优化方法及应用.

基金项目:广东省自然科学基金资助项目(2012B091100033)

收稿日期:2014- 06- 23