多目标优化问题的研究

东莞理工学院学报第21卷第3期Vol.21 No.32014年6月JOURNAL OF DONGGUAN UNIVERSITY OF TECHNOLOGYun.__ 2014多目标优化问题的研究朱君蔡延光汤雅连杨军(广东工业大学 自动化学院，广州510006 )摘要:针对传统方法求解多目标优化问题的局限性，应用一种新的算法求解。遗传算法从问题解的串集开始搜索，覆盖面大，可以同时处理群体中的多个个体，利于全局择优，减少陷入局部最优的风险，而最小生成树具有过程简单清晰、适用性广泛的特点，结合两者的优点，构造了基于生成树的遗传算法。首先通过加权目标规划法求出最优解，然后通过遗传算法和基于生成树的遗传算法求解，结果表明，对于小规模的多目标优化问题，两种算法都可以求出最优解，在求解时间方面，基于生成树的遗传算法比遗传算法更优越。关键词:多目标优化问题;最小生成树;遗传算法中图分类号: TP2文献标识码: A文章编号: 1009-0312 (2014) 03 -0046 -04在现实生活中，某个设计方案只要求某- -项目标达到最优，这是单目标优化问题。如果设计方案期望某几项指标均能达到最优值，这样的问题就称为多目标优化设计问题。比如厂家生产某种产品，既要求投人资金少，工人少，降低成本，又要工作效率高，利润高，这就是-个多目标优化问题。现实生活中，多多标优化问题"中的各个子目标一般是相互矛盾的，也就是同时使所有子目标都达到最优是不可能的，最终目标是尽最大可能达到最优化，它的解并不是唯一-的，而是由多个最优解组成的满意解，集合中的各个元素称为Pareto最优解或非劣最优解。由于该问题模型在现实生活中普遍存在，所以本文研究的多目标优化问题具有实际应用意义。目前，多目标优化问题也得到了广泛的研究。谢涛等人23介绍了基于Pareto最优概念的多目标演化算法中的主要技术和理论结果，详细介绍了基于偏好的个体排序、适应值赋值及共享函数等。王跃宣等人”考虑了对约束条件的处理问题，提出了求解带约束的多目标优化遗传算法，利用邻域比较与存档操作遗传算法处理多个相互冲突的目标的优化;马瑞等人[41 提出了解决多目标优化问题的新方法和综合考虑水火协调及能源、环境和经济等多目标优化的分组分段电力市场竞标新模型，结果表明了算法的正确性和模型的有效性;李宁等人5提出了一种新的基于粒子群的多目标优化算法，用搜索过程中所发现非劣解的一部分构成精英集,通过小生境技术和部分变异的方法提高非劣解集的多样性和分散性;.张丽霞等人61应用多目标决策理论求解网络计划的多目标优化模型;王晓鹏?1在自适应遗传算法的基.础上引入群体排序技术、小生境技术和Pareto 解集过滤器，建立了适用于多目标优化设计的Pareto遗传算法，设计表明Pareto遗传算法是十分有效的。1多目标优化问题描述多目标优化问题!8起源于许多实际复杂系统的设计、建模和规划问题，包括工业制造、城市运输、森林管理、产品制造、城市布局、网络布局等。几乎每个重要的现实决策问题都要考虑不同约束和处理若干相互冲突的子目标。多目标优化问题可以表达成下面的形式，如式(1) 和(2)所示。max{z =f(x),2 =fe(x)(1)中国煤化工s.t. g;(x)≤0,i =(2)MHCNM HG收稿日期: 2013-12-04 .基金项目:国家自然科学基金(61074147; 61074185); 广东省自然科学基金(S201 1010005059; 83510090000002); 广东省教育部产学研结合项目(2012B091000171; 201 I B090400460);广东省科技计划项目(2012B050600028 ; 2010B090301042)。作者简介:朱君(1991-), 男，江西新余人，硕士生，主要从事组合优化、物流信息技术与应用方向研究。第3期.朱君，等:多目标优化问题的研究472两种求解MOP的方法2. 1加权目标规划现实的决策环境中各个目标的重要程度是不可能完全-致的，决策者可以判断分析各个目标的重要性，而且子目标在总目标中也占不同的重要程度，可以通过加权系数进行目标规划求解。加权系数是达成函数中各目标偏差变量的系数。加权系数是一种可 以用数量来衡量的指标，对属于同- -优先等级的不同目标可按其重要程度分别给予不同的加权系数来反映各加权目标规划的数学模型如下，式(3)为目标函数，式(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;:多目标规划的设计变量;cg:目标约束的系数;e;:第i个目标的期望值;f; :目标中d;的系数:f :目标中d;的系数;d; ,di :偏差变量。2.2基于生 成树的遗传算法遗传算法的基本特点是多方向和全局搜索，带有潜在解的种群能够-代代地维持下来。最小生成树问题( minimim spanning tree problem)由Boruvka8于1926年首次提出，此后，最小生成树问题被广泛应用于许多组合优化问题中。最小生成树问题中，考虑连通图G = (V,E),其中V = {vr,0,.,on} 是顶点的有效集合,E = {e,是边的有限集合。边将顶点之间连接起来。每个边有一个正实数权重W = {w,v,.,wm}表示距离或费用。最小生成树问题就是寻找图G中连接所有顶点的具有最小权重的子图。Pareto解集的求解过程1)设置迭代标志k = 1,当前迭代世代t产生的Pareto解集E(t) = {φ|;2)若k > i_ size,停止;否则,执行3);3)评价染色体Ar,得到解F。= [f:(A)f2(A)--f(A1)],将其与E中所有Pareto解比较;(i):若任何Pareto优于它，执行4);(i):若它优于部分Pareto解，则用它代替E中较差的解;(i):若它是新解，则加入E中。4):h =k+1，返回2)。整个算法的伪代码如下:procedure: st GA/ 'mtpbegint←0 :初始化P(t) ;计算P(t)的目标函数值;确定Pareto 解集E(1) ;计算P(1)的适应值中国煤化工while不满足终止条件doYHCNM HGregin对P(1)进行杂交和变异，得到C(1) ;更新Pareto解集E(t) ;计算C(t)的目标函数值;48东莞理工学院学报2014年.计算C(t)的适应值;从C(1)中选择P(1 +1) ;1←1+1 ;end3仿真分析某工厂准备开发3种产品，重点是确定3种产品的生产计划，并尽量达成目标。总利润不低于120万元，3种产品的单位利润分别为元8、9元和2元;有50名工人，每生产3种产品各1万件分别需要的工人数量为6、1和5名;总投资资金不超过60万元，且生产3种产品需要投人成本2、9和6元。各目标的惩罚权重和各产品的单位贡献如表1和表2所示。表1各目标的惩罚权表2各产品的单位贡献目标因素惩罚权重产品1产品2 产品31总利润低于目标的每一-万元，5总利润/万元大于等于120工人低于目标的每-一个人, 3工人/名.等于50超过目标的每-一个人，13投资资金超过目标的每- -万元，2投资资金/万元小于等于603.1加权目标规划法求解MOP建立数学模型1)决策变量产品i的产量x:(i = 1,2,3);正偏差变量d↑、 负偏差变量d;(i = 1,2,3)2)目标函数Opt imization terminat ed.1.各产品需要生产的数量为(万件) :minz=5d*+3d2+d3+2d;7. 17396.95650. 00003)约束条件' 8x1 +9x2 +2x3 +d°-di = 1202.偏差变量为:6x1 +x2 +5x3 +dI -d2 = 50序号正偏差负偏差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取整数求解结果:应用Matlab 求解界面如图1所示。生3.实际获得利润、需要工人及投入资金分别为:实际获得利润为: 120. 000000产产品1、2和3的数量分别为71739件、69565 件和需要工人为: 50. 000000件。除了第3个目标，其他2个目标都能达成，获投入资金为: 76. 956522得利润120万元，需要工人50人，投入资金76. 96万4.各目标的达成情况为:3元。03.2 应用两种算法求解MOPstGA的参数设置:初始种群pop_ size= 30，交.图1应用 Matlab求解界面叉概率p。=0.8，变异概率pm = 0.02，最大迭代次中国煤化工数maxgen=1000，运行30次。GA的参数设置:初始种群pop_ size =30，交叉概率p。MHCNMHG.=0.02，最大迭代次在Intel (R) CoreTM i3 CPU 2. 53CHz、内存为2.0 G、安装系统为win7 的PC机上采用MatlabR2010b编程实现。第3期朱君，等:多目标优化问题的研究49表3 GA和 st-GA求解MOP的结果;Ast-CA最优解占总运行次数的百分比运行时间/s100 。1.340.91求解结果:由表3可知，通过两种算法都可以求得满意解，但是st-GA比GA消耗更少的时间就可以找到最优解，所以，针对多目标优化问题，st GA更适用。4结语本文应用一种新的算法求解多目标优化问题。由于遗传算法从问题解的串集开始搜索，覆盖面大,可以同时处理群体中的多个个体，利于全局择优，减少陷人局部最优的风险，而最小生成树具有过程简单清晰、适用性广泛的特点，构造了基于生成树的遗传算法。结果表明，对于小规模的多目标优化问题，虽然两种算法都可以求出最优解，但在求解时间方面，基于生成树的遗传算法比遗传算法更优越,应用改进的算法求解大规模的多目标优化问题是下一-步要研究的内容。参考文献1] 肖晓伟，肖迪，林锦国,等，多目标优化问题的研究概述倡[J].计算机应用研究, 2011, 28(3) :805 - 809.[2] 谢涛，陈火旺，康立山、多目标优化的演化算法[J].计算机学报, 2003, 26(8): 997 - 1003.[3] 王跃宜,刘连臣，牟盛静，等.处理带约束的多目标优化进化算法[J].清华大学学报:自然科学版, 2005, 45(1): 103 - 106.[4] 马瑞，贺仁睦,颜宏文,等.考虑水火协调的多目标优化分组分段竞标模型[J].中国电机工程学报, 2004, 24(11): 53-57.[5] 李宁，邹彤，孙德宝基于粒子群的多目标优化算法[J].计算机工程与应用, 2005, 41(23): 43 -46.[6] 张丽霞，侍克斌.施工网络进度计划的多目标优化[J].系统工程理论与实践, 2003, 23(1): 56-61.[7] 王晓鹏.多目标优化设计中的Pareto 遗传算法[J].系统工程与电子技术，2003, 25(12): 1558 - 1561.[8] 玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,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