基于灵敏度分析的Pareto解改进计算方法
第31卷 第12期2009年12月
文章编号:1001 506X(2009)12 2977 05
系统工程与电子技术
SystemsEngineeringandElectronicsVol.31 No.12Dec.2009
基于灵敏度分析的Pareto解改进计算方法
范培蕾,张晓今,杨 涛
(国防科学技术大学航天与材料工程学院,湖南长沙410073)
摘 要:由于多目标优化算法得到的Pareto最优解集通常是离散分布的点,并非连续曲线(曲面),大多数情况下无法为决策者提供较多完全符合决策要求的Pareto解。根据多目标优化与决策的关系,定义了偏好模型以量度对优化目标的满意程度,并通过灵敏度分析提出了一种Pareto改进解的计算方法,旨在确定是否存在更符合偏好要求的改进解。结果证明,此方法能有效地对Pareto最优解集中的元素进行改进,提供给决策者更多符合偏好要求的候选解,辅助决策人员选择最终方案。
关键词:Pareto前沿;改进解;灵敏度分析;偏好函数中图分类号:TH122 文献标志码:A
MethodofParetoimprovedsolutionsbasedonsensitivityanalysis
FANPei lei,ZHANGXiao jin,YANGTao
(Coll.ofAerospaceandMaterialsEngineering,NationalUniv.ofDefenseTechnology,Changsha410073,China) Abstract:OwingtoParetosolutions discretedistribution,notacontinuouscurve/surface,derivedfroma
multi objectiveevolutionaryalgorithm,thedecision makercouldnotgetParetosolutionsfortotallymeetingdesignrequirementsinmostcases.Accordingtotherelationshipbetweenmulti objectiveoptimizationanddeci sion makingmachine,thepreferencerequirementandpreferencefunctionareproposedtomeasurethesatisfac tionlevelforobjectivevalues.AndamethodofParetoimprovedsolutionsbasedonsensitivityanalysisisusedtoascertainwhetherthereexistsomemoresolutionswhichmightevenmoremeetpreferencerequirements.Simu lationresultsshowthatParetosolutionsfromthecandidatesetareimprovedeffectivelywhileassistinginprovi dingmoreParetosolutionsformeetingpreferencerequirementstobethefinalscheme.
Keywords:Paretofront;improvedsolutions;sensitivityanalysis;preferencefunction
0 引 言
近年来,多目标优化算法的研究越来越多,应用越来越广,为解决工程实际中的多目标优化问题提供了有效的解决方法[1 4]。但是,通常多目标优化计算得到的是离散分布的Pareto前沿点,而非连续的曲线(曲面),需设计人员根据实际偏好要求对离散分布的点进行比较或改进,继而进行决策分析。基于如何有效地从Pareto最优解集中选择符合偏好要求的Pareto解这一问题,本文提出了一种基于灵敏度分析的Pareto解改进计算方法,旨在确定是否存在更符合偏好的Pareto改进解,为决策人员选择工程最终方案奠定基础。
因而设计者和决策者可以根据对目标函数的重视程度从Pareto最优解集中进行选择,根据具体设计要求选取最满意的解。通常方法是决策者按照某些定量或定性的邻域约束、目标偏好或难以表达的专家经验等,从非劣解集中选取唯一现实可行的最优方案。
图1为多目标优化器与决策器的系统构成图。其中,Pareto最优解集的搜索过程由优化器实现,Pareto解的选择和比较过程由决策器完成。决策器由决策专家或具有领域决策知识的专家系统承担,它可从Pareto最优解的搜索过程中不断提取、变化与丰富决策信息,并逐步引导优化器向感兴趣的非劣最优区域移动。一般决策者根据对目标的偏好关系与程度、目标期望值、效用函数等因素来形成偏好知识以选择Pareto解[5 6]。本文采用决策者对优化目标的偏好关系对Pareto解进行比较分析。
1 偏好要求及偏好函数分析
由于Pareto最优解集中的任何解都可能成为最终解,
收稿日期:2008 09 09;修回日期:2009 06 05。
作者简介:范培蕾(1979 ),女,博士研究生,主要研究方向为飞行器总体优化设计。E mail:[email protected]
2978
系统工程与电子技术第31卷
图1 多目标优化与决策器的系统构成
为表达决策者对优化目标的满意程度,将优化目标按取值范围分为极好、较好、一般、较差、极差、不可行等几个区域,并采用偏好函数对其进行量度,即通过偏好函数将具有不同物理意义的优化目标映射到无量纲实数空间,以同等对待具有不同物理意义的优化目标设计准则。对于最小化的多目标优化问题,假定偏好函数符合指数变化规律,随优化目标fi的增大逐渐增大,趋向于较差的目标值,其优化目标偏好函数值为
~
图2 Pareto解的改进计算示意图
2.1 灵敏度分析
灵敏度是在给定Pareto解处某一优化目标fi沿Pareto前沿变化对其他优化目标的影响[7
]。在目标函数空间,灵敏度可看作Pareto前沿在给定解处沿某一优化目标下降方向的导数,如图3所示。
f
i
=exp( i(fi-fi))(1)
式中,fi为优化目标;f0i为偏好区域中极好与较好的分界点坐标值,需设计人员根据偏好要求进行定义;参数 i为偏好函数系数,需根据fi的取值范围确定。
假定偏好函数取值范围为[0,10],优化目标位于可行区域的偏好函数值为7.4,即当fi>7.4时,优化目标fi的设计变量不满足偏约束限制;当f
~ ~
i
!7.4时,根据偏好
函数值将优化目标分为不同的偏好区间。为保证各偏好区间的宽度尽量一致,在可行区域选取如下分界点:4.5,2.7,1.6,1.0,即当f极差;当f当f
~
~
~
~
i
∀(4.5,7.4]时,优化目标fi偏好评价为
图3 灵敏度示意图
i
∀(2.7,4.5]时,优化目标fi偏好评价为较差;
~
i
∀(1.6,2.7]时,优化目标fi偏好评价为一般;当
i
f
i
∀(1.0,1.6]时,优化目标fi偏好评价为较好;当f
min
i
∀
假定Pareto解X处起作用约束gk的梯度J
gk为
Jgk=
k
=dX
kkk
,,∃,12n
(4)
[0,1.0]时,优化目标fi偏好评价为极好;假设优化目标fi在可行区域内的取值范围为[f
i(ff0i)。
max
i
,fmaxi],则只需保证
maxi
-fi)!ln7.4 i!ln7.4/(f-fi)(2)
max
i
偏好函数系数 i由式(2)确定,通常取 i=ln7.4/(f-
2 Pareto改进解计算方法
假定多目标优化问题有两个优化目标
min
ff
12
如果约束函数gk为基于径向基函数的响应面模型,Jgk
中元素可按式(4)计算。令P表示可行方向,即起作用约束gk保持不变,则
T-1
P=I-JTJgk(5)gk(JgkJgk)
将优化目标fi的梯度Jfi向可行方向P投影即可得到优化目标fi沿可行方向上的方向导数Dfi,即
Dfi=
Pi
=JfiP=dX
iii
,,∃,P12n
(6)
=f1(x)=f2(x)
(3)
如果决策人员的偏好要求为优化目标f1、f2偏好要求均为较好以上,而多目标优化计算得到的Pareto前沿上不存在符合此偏好要求的解,仅有较符合的Pareto解F1、F2。因此,在进行灵敏度分析的基础上,沿Pareto前沿方向进行搜索计算,对较符合偏好要求的Pareto解进行改进,确定改进解F#1
、F#2,为进行多目标决策分析及确定最终解奠定基础(见图2)。
同理,如果目标fi为基于径向基函数的响应面模型,
则Jfi中各元素为
ft0i
=-%(xk-xik)&e
i=1t0 xk
求解式(7)可得
T-1T
dX=(DfiDfi)DfidPfi
则优化目标fi沿可行改变方向的灵敏度为
Pj-1
=Dfj(DTfiDfi)DTfi,i∋jdPfi
m
-xj-xj
i
2
(7)(8)(9)
第12期
将灵敏度信息表示为矩阵形式
1
T=[tij]=
PdPf
12
范培蕾等:基于灵敏度分析的Pareto解改进计算方法
2979
步骤4 根据式(4)和式(5)求取当前解[Xt,Ft]的起
PdPf1!dPfm
21
Pm
∃
dPf1∃
PmdPf2!∃
j
作用约束gk及可行方向P,根据式(6)求取优化目标fi沿方向P的导数Dfi;
(10)
步骤5 根据Dfi沿改进优化目标f点[X#t,F#t],计算预测点起作用约束g#k;
步骤6 判断预测点[X#t,F#t]的起作用约束g#k是否在约束边界上,若是,则当前预测点为Pareto改进解[X#t,F#t],计算终止;否则,令t=t+1,沿g#k的梯度方向J#gk向约束边界投影计算新预测点[X#t,F#t];
步骤7 判断是否t
此种计算方法可对候选集S中的任一Pareto解进行改进,确定更符合设计人员偏好要求的Pareto改进解,实现对Pareto前沿的遍历搜索计算。
i
的方向生成预测
!
dPfm
式中,元素tij表示优化目标ftij>0,则fi与f则需在fi与ffi与f
j
j
j
i
1
与f之间的权衡关系,若
之间不存在矛盾,可同时改进;若tij
之间权衡,无法同时改进;若tij=0,则表示
不存在相关性。
对于多目标优化问题,其任一Pareto解的权衡矩阵中每一行至少将有一个元素小于零,否则所有优化目标都可同时得到改进,该解将不是Pareto最优解。2.2 Pareto改进解计算方法
利用多目标优化算法求解多目标问题可以得到一个均匀分布的Pareto最优解集,大多数情况下此解集不一定能够完全符合决策人员的偏好要求。基于如何能够从Pareto最优解集中求解更为符合偏好要求的Pareto改进问题
,本文提出了一种基于灵敏度分析的Pareto解改进计算方法,基本原理是首先从Pareto最优解集中构造一个较符合决策人员偏好要求的候选集S,并任意选取解[X0,F0]作为计算起始点,再通过灵敏度分析方法搜索计算[X0,F0]附近的Pareto前沿点,获取Pareto改进解[X#t,F#t](见图4)。
3 仿真分析
考虑到多目标优化问题的复杂性,本文以Viennet4测试函数为例进行仿真分析,验证此种计算方法的有效性和可行性。
f1=++3
213min
f2=
22
+-13
17517
2
2
22
f3=++15
827
(11)
-4!x1,x2!4s.t.
4x1+x2-4>0x1+1>0-x1+x2-2>0
3.1 确定偏好区间及偏好函数模型
首先根据设计变量的变化范围预估各优化目标的取值范围,构造偏好函数,确定各优化目标的偏好区间。假定Viennet4函数中,优化目标f1极好与较好偏好区间的分界点是f1=4.5,预估可行区域内优化目标f1最大值为
图4 Pareto改进解计算示意图
fmax
1=9.0;优化目标f2极好与较好偏好区间的分界点是
2
假定设计人员对优化目标fi偏好要求较高,则计算过程如下:
步骤1 确定迭代计算的最大次数tmax;
步骤2 判定Pareto最优解集中是否存在较符合偏好要求的解,构造候选集S={[Xi,Fi]}(i=1,2,∃,n),并令t=0;
步骤3 从S中任选Pareto解[Xt,Ft]作为计算起始点,如果候选集S为空,则说明无法进行改进计算,难以获取Pareto改进解,计算结束;否则,转步骤4;
f02=-12.8,预估可行区域内优化目标f-11.8;优化目标f
3
最大值为f
max
3
max20
=
极好与较好偏好区间的分界点是f3=
=26。那
18,预估可行区域内优化目标f3最大值为f
么,由式(1)确定偏好函数系数为 1=0.4448, 2=2.0015, 3=0.2502,并构造偏好函数为(见图5)
~
fff
123
=exp[0.4448(f1-4.5)]=exp[2.0015(f2-12.8)]=exp[0.2502(f3-18)]
(12)
~ ~
2980
系统工程与电子技术第31卷
图5 偏好函数图
3.2 求解优化目标
采用多目标粒子群优化算法[8 10]求解Viennet4测试函数,参数设置为:c1=2.1,c2=2.32,权重系数wmax=0.8,wmin=0.3,种群规模n=80,进化代数Gen=500。由于多目标粒子群算法的随机性,本文进行了10次随机计算,均得到了分布性较好的Pareto最优解集(见图6)。可以看出,采用多目标粒子群优化算法求解Viennet4优化函数可以得到均匀分布的
Pareto最优解集,且解的数量较多,为进行Pareto解改进计算及其决策分析提供了更多符合偏好要求的候选解。
表1 部分Pareto最优解的偏好函数值列表目标f1
1
目标f
2
f偏好区间极好极好极好较好极好较好极好极好较好较好∃
f
2
偏好区间极差较差较差极好极差较好一般极差极差较差∃
目标f3
3
f偏好区间一般较差一般较差一般较差一般一般极好较好∃
0.8560.7070.8671.340.8691.0770.9530.7191.4511.202∃
5.9643.9003.3870.8716.1731.1942.3255.5496.9823.295∃
1.8833.0172.2153.3241.8202.8992.2722.6810.8671.110∃
(1)假定设计人员对优化目标f1偏好要求较高,同时
要求f2和f3不至于较差。
由表1构造候选集S={[X7,F7]},选取解[X7,F7]进行分析,可知优化目标f2和f3位于一般的偏好区间内,无须进行Pareto改进计算即已满足偏好要求。
(2)假定设计人员对优化目标f2偏好要求较高,但同时要求f1和f3不至于较差。
由表1构造候选集S={[X4,F4]},并将解[X4,F4]作为计算起始点,采用灵敏度方法对其附近进行Pareto前沿
图6 Pareto最优解集求解结果
3.3 Pareto解改进过程
为便于决策人员从Pareto最优解集中选取符合偏好要求的解构造候选集并计算偏好函数,本文采用柱状图表示各优化目标偏好函数值,柱状图能够较直观地显示Pareto最优解集中各优化目标的偏好区间,更有效地帮助决策人员确定最终解以进行方案设计。从图6的求解结果中随机选取部分Pareto解进行分析(见表1),可以看出Viennet4测试函数各优化目标相互矛盾,难以同时达到最优。因此,设计人员需按照具体偏好要求进行比较分析,选择较符合偏好要求的Pareto解构成候选集S并进行计算,得到Pareto改进解。由于实际工程问题中偏好要求较复杂,因此本文只选取了其中三种情况进行分析。
计算。解[X4,F4]的优化目标f1位于较好偏好区间内,而f3位于较差的偏好区间内,所以在改进过程中期望进一步减小f3,使得Pareto改进解满足偏好要求。沿f3减小的梯度方向改变[X4,F4],按上述计算方法得到Pareto改进
44
解[X#4,F#4]=[X4,F4]及偏好区间(见图7(a))。可以看出,
改进解[X#4,F#4]使得优化目标f3位于一般的偏好区间,同时使得f1和f2偏好函数值改变较小,偏好区间没有改变,均已达到偏好要求。
(3)假定设计人员对优化目标f3偏好要求较高,但同时要求f1和f2不至于较差。
由表1构造候选集S={[X9,F9],[X10,F10]}。首先选取优化目标f3处于极好区间的[X9,F9]作为起始点进行迭代计算。解[X9,F9]的优化目标f1位于较好的偏好区间内,而f2位于极差的偏好区间内,因此在改进时期望进一步减小优化目标f2,执行上述计算过程得到Pareto改进解[X#9,
第12期
3
3
范培蕾等:基于灵敏度分析的Pareto解改进计算方法
2981
F#9]=[X9,F9]及偏好区间(见图7(b))。可以看出,改进解
[X#9,F#9]使得优化目标f2位于一般的偏好区间上边界上,但导致f1和f3偏好函数值改变较大,均位于一般的偏好区间内,已不能达到预定偏好要求。因此,解[X9,F9]的改进过程
失败,需重新选择Pareto解。降低优化目标f3的偏好要求
至较好区间,从候选集S中选取[X10,F10]作为起始点进行
33
改进(见图7(c))。可以看出,改进解[X#10,F#10
]=[X10,F10]
已完全满足偏好要求,终止计算。
图7 改进解的求解过程示意图
3.4 综合比较
为验证改进计算方法在提供符合决策人员偏好要求的Pareto解方面的优越性,本文针对3.3节中的不同偏好要
求情况,对改进计算与未进行改进计算时的候选解的个数进行了比较,如表2所示。此外,本文采用其他多目标优化方法进行了仿真计算,结果表明:此种改进计算方法能够提供给决策者更多(几乎2倍)的候选解以进行决策分析,充分验证了此种计算方法的有效性。
表2 符合偏好要求的候选解个数比较
偏好要求
MOEAMOPSO
(1)
NSGA2SPEA2MOPSO
(2)
NSGA2SPEA2MOPSO
(3)
NSGA2SPEA2
候选解个数
未改进计算
2
23655885
改进计算后
3
[1**********]11
要求的候选集中的元素进行改进计算。通过与未进行改进计算的多目标优化结果相比,该方法能够提供给决策人员更多的候选解,辅助决策人员进行决策分析,确定工程设计的最终方案。
参考文献:
[1]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版
社,2006.
[2]姚望舒.多目标进化算法及其应用的研究[D].南京:南京大学,
2005.
[3]HuXiaohui,EberhartR.Multi objectiveoptimizationusing
dynamicneighborhoodparticleswarmoptimization[C](Proc.oftheCongressonEvolutionaryComputation,2002:96 109.[4]FonsecaCM,FlemingPJ.Anoverviewofevolutionaryalgo
rithminmulti objectiveoptimization[J].EvolutionaryCompu tation,1995,3(1):1 16.
[5]吴龙军.模糊优化理论在多目标多阶段决策系统中的应用[D].
长沙:中国科学技术大学,2004.
[6]王鲁.基于遗传算法的多目标优化算法研究[D].武汉:武汉理
工大学,2006.
[7]廖林清,陈益.基于灵敏度分析的工程稳健优化设计方法及其
应用[J].机械设计与制造工程,2000,29(6):7 13.
[8]李宁,邹彤,孙德宝.基于粒子群的多目标优化算法[J].计算
机工程与应用,2005,41(23):43 46.
[9]SierraMR,CoelloCAC.ImprovingPSO basedmulti objective
optimizationusingcrowding,mutationand∀ dominance[C](3rdInternationalConferenceonEMO,2005,3410:505 519.[10]FonsecaCM,FlemingPJ.Multi objectiveoptimizationand
multipleconstraintshandingwithevolutionaryalgorithms):applicationexample[R].UniversityofSheffield,1995.
4 结束语
为向决策人员提供完全符合要求的Pareto解,本文根
据多目标优化器与决策器的关系,首先,由决策者针对优化目标的偏好关系,确定了偏好函数系数,并采用偏好函数对优化目标的满意程度进行了量度;然后,在对Pareto前沿进行灵敏度分析的基础上,提出了Pareto解改进计算方法;最后,采用测试函数Viennet4进行仿真计算。结果证明,基于灵敏度信息的Pareto解改进方法能够针对不同偏好要求的多种情况进行分析并构造候选集,可有效地对满足偏好