（控制理论与控制工程专业论文）基于决策者满意度的多目标模糊优化算法研究.pdf

摘要 基于决策者满意度的多目标模糊优化算法研究 摘要 现代经济、工业的发展使得优化技术在各个领域得到广泛应用，随着对优化目标要求的不断提 高，追求多个目标同时优化已经成为系统最后决策的关键。在复杂决策环境中，多个目标之间存在 的相互冲突和不可公度性常常使得最优解不存在，因此不能简单应用单目标优化方法来解决。此外， 在多目标优化问题中贯穿着决策者给予的各种偏好信息，如何从众多p 盯c t o 最优解中找到最终的解 就成为解决多目标优化问题的核心内容。而且不确定性因素也使得传统的优化方法和优化理论难以 直接得到应用，给求解带来了困难和挑战。为此，本论文基于决策者满意度的思想，利用模糊优化 方法对具有不同类型偏好信息的多目标优化问题进行了研究。 主要工作包括以下几个方面： 对于有语言偏好信息的多目标优化问题，基于更重要目标具有更高期望满意度的原则，利用期 望满意度序来表示目标之间通过语言描述的模糊重要性要求。针对不同模糊目标要求和不同优 化目的，分别设计了两步式和改进加法模型两种模糊优化算法。其中两步式方法主要是通过对 最大综合满意度的松弛形成了两步优化模型，在未改变原问题性质的前提下，实现了对目标优 化和重要性偏差的折衷。而改进加法模型的优化算法则借助了目标规划的方法，形成了基于参 数的单目标评价模型，适用于各种模糊目标关系，参数的调节兼顾了期望满意度之和与重要性 偏差之间的平衡。在最优性和参数分析的基础上，数值仿真例子表明了两种算法的有效性、灵 活性和灵敏性。 针对有优先级的多目标优化问题，通过用满意度序取代期望满意度序，将重要性要求转化为优 先级关系，改进了应用于模糊重要性的两步式和加法模型两种优化算法。在改进的两步式算法 中，保持第一步优化模型不变，利用满意度序形成了第二步优先级模型，对最大综合满意度的 松弛实现了目标优化和优先级要求。在改进的有优先级加法模型优化算法中，将满意度序转化 为偏差变量间的比较关系，利用参数的调节对目标满意度之和与目标之间的优先级差别进行了 折衷，两种模型的有效性和灵敏性在数值例子和分布参数系统、生产决策等仿真研究中得到了 验证。 研究了有局部偏好信息的多目标优化问题，在决策者满意度思想基础上，提出了基于可变容许 国家自然科学基金资助项目( 批准号：6 0 4 7 4 0 5 1 ) 和国家教育部新世纪优秀人才资助项目 摘要 度的交互式模糊优化方法。利用变容许度带来的隶属度函数结构变化来反映优化过程中偏好信 息的变化，对于基于模糊目标的优化问题，辅助优化模型的引入，确保了优化算法的可行性， 利用两阶段模型或修改的两阶段模型得到的解具有p a r e t o 最优性或弱p a r e t o 最优性。此外，对 于目标和约束中带模糊系数的多目标优化问题，本论文利用模糊数截集的方法形成了基于参数 的优化问题，在可变容许度方法的基础上，实现了内、外两层交互式的优化过程，参数的调节 和容许度的改变体现了决策者局部偏好的变化，满意的a - p a r e t o 最优解或弱a - p a r e t o 最优解 可以通过求解带参数的两阶段模型得到。仿真例子验证了以上优化算法的有效性。 对于有后验偏好信息的多目标优化问题，决策者满意度表现为后验满意度。首先利用多目标遗 传算法n s g a i i 来获得多目标优化问题均匀分布的近似p a r e t o 最优解集，然后将决策者对目标 的模糊要求应用于优化问题中，形成基于模糊目标的多目标优化问题，得到每个解对应目标的 满意度值。最后，淘汰优化算法使得最优解集缩减为只包含m - p a r e t o 最优解的子集，传统的模 糊c 均值聚类算法可以将包含一定数量解的子集进行分类，得到有代表性的子集，以便决策者 能够轻松选择出最终的满意结果，数值和调度优化仿真说明了三步优化策略的可行性。 关键词：多目标优化，决策，满意度，偏好信息，模糊优化，交互式 a b s t r a c t r e s e a r c h0 1 1f u z z ym u l t i p l eo b j e c t i v eo p t i m i z a t i o nb a s e do nd e c i s i o n m a k e r ss a t i s f y i n gd e g r e e a b s t r a c t t h er e p a i dd e v e l o p m e n to fm o d e r ni n d u s t r ya n de c o n o m ym a k et h e o p t i m i z a t i o nt e c h n i q u eb eg r e a t l y u s e di nm a n yk i n d so ff i e l d s w i t hh i g h e rr e q u i r e m e n t so ft h eo p t i m i z a t i o no b j e c t i v ea r ep u tf o r w a r d ，t h e s i m u l t a n e o u so p t i m i z a t i o no fm u l t i p l eo b j e c t i v e si st h ek e yf a c t o rf o rt h ef i n a ld e c i s i o ni nt h es y s t e m s u n d e rt h ec o m p l e xd e c i s i o nm a k i n ge n v i r o n m e n t s ，m u l t i p l eo b j e c t i v e sa r ca l w a y sc o n f l i c t i n ga n d n o n c o m m e n s u r a b l e , w h i c ho f t e nr e s u l ti ni n e x i s t e n c eo fo p t i m a ls o l u t i o n t h e r e f o r em u l t i p l eo b j e c t i v e o p t i m i z a t i o np r o b l e m ( m o o p ) c a n tb ee f f i c i e n t l ys o l v e du s i n gt h eo p t i m i z a t i o nm e t h o d sf o rs i n g l e o b j e c t i v ep r o b l e m i na d d i t i o n ，t h e r ea r ea l lk i n d so fp r e f e r e n c ei nm o o et h e nh o wt of i n dt h ef i n a lo n e f r o mt h ep a r e t oo p t i m a ls o l u t i o n sb e c o m e si m p o r t a n ti ns o l v i n gm o o p m o r e o v e rt h eu n c e r t a i n t i e sa l s o c a u s em a n yd i f f i c u l t i e st od i r e c t l yu s et h ec o n v e n t i o n a lo p t i m i z a t i o na p p r o a c h e sa n do p t i m i z a t i o nt h e o r i e s ， a n db r i n gc h a l l e n g e sf o rm o o eh lt h i st h e s i s ，b a s e do nd e c i s i o nm a k e r ( d m ) ss a t i s f y i n gd e g r e e ，t h e m o o p sw i t hd i f f e r e n tt y p e so f p r e f e r e n c e sa r es t u d i e du s i n gf u z z yo p t i m i z a t i o nm e t h o d s 。 1 1 圮m a i nc o n t e n t sa r ea sf o l l o w s ： f o rt h em o o pw i t hl i n g u i s t i cp r e f e r e n c e t h eo r d e ro ft h ed e s i r a b l es a t i s f y i n gd e g r e e si su s e dt o e x p r e s st h ev a g u ei m p o r t a n c er e q u i r e m e n ta m o n gt h eo b j e c t i v e ss h o w e db yl i n g u i s t i ci n f o r m a t i o n b a s e do nt h ep r i n c i p l et h a tt h em o r ei m p o r t a n to b j e c t i v eh a sh i g h e rd e s i r a b l es a t i s f y i n gd e g r e e ，a sf o r t h ed i f f e r e n tt y p e so ff u z z yg o a l sa n do p t i m i z a t i o nr e q u i r e m e n t s ，t h et w o s t e pf u z z yo p t i m i z a t i o n a l g o r i t h ma n de n h a n c e da d d i t i v em o d e lf u z z yo p t i m i z a t i o na l g o r i t h ma r ed e s i g n e d t h ef o r m e r f o r m u l a t e st h et w o s t e po p t i m i z a t i o nm o d e l sb yr e l a x i n gt h em a x i m u mo v e r a l ls a t i s f y i n gd e g r e e i t g u r a n t e e st h e o r i g i n a lc h a r a c t e r i s t i c so ft h ep r o b l e ma n dr e a l i z e st h et r a d e o f f b e t w e e nt h eo p t i m i z a t i o n a n di m p o r t a n c ed i f f e r e n c e t h el a t t e rg i v e st h es i n g l eo b j e c t i v ef o r m u l a t i o n sw i t hp a r a m e t e rb a s e do n g o a lp r o g r a m m i n g i ti ss u i t a b l ef o ra l lk i n d so ff u z z yr e l a t i o n s t h eb a l a n c eb e t w e e nt h es u mo ft h e d e s i r a b l es a t i s f y i n gd e g r e e sa n di m p o r t a n c ed i f f e r e n c ei sa c t u a l i z e dt h r o u g hr e g u l a t i n gt h ep a r a m e t e r a f t e rt h eo p t i m a l i t ya n dp a r a m e t e ra n a l y s i s e s ，t h en u m e r i c a le x a m p l e sa r ei l l u s t r a t e dt ov e r i f yt h e i r s u p p o r t e db yt h en a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no f e r c h i n a ( 6 0 4 7 4 0 51 ) a n dt h ep r o g r a mf o rn e y a , c e n t u r y e x c e l l e n tt a l e n t si nu n i v e r s i t yo fc h i n a ( n c e t ) e f f e c t i v e n e s s ，f l e x i b i l i t ya n ds e n s i t i v i t y f o c u s m g 0 1 1t h em o o pw i t hp r e e m p t i v ep r i o r i t y u s i n gt h eo r d e ro ft h es a t i s f y i n gd e g r e e si n s t e a do f t h a to ft h ed e s i r a b l eo n e s ，t h ei m p o r t a n c er e q u i r e m e n ti st r a n s f o r m e di n t op r i o r i t y c o r r e s p o n d i n g l y , t h et w o - s t e pa l g o r i t h ma n de n h a n c e da d d i t i v em o d e la l g o r i t h mf o rv a g u ei m p o r t a n c ea r em o d i f i e d f o r t h ef o r m e r , 谢mt h es a m ef i r s ts t e pm o d e l ，t h ep r i o r i t ym o d e li sf o r m u l a t e dv i at h eo r d e ro ft h e s a t i s f y i n g 。d e g r e e s t h eo p i t i m i z a t i o na n dp f i o f i wr e q u k e m e h ti sa c q u i r e db ym e a n so ft h er e l a x a t i o n o ft h em a x i m u mo v e r a l ls a t i s f y i n gd e g r e e f o rt h el a t t e r , t h eo r d e ro ft h es a t i s f y i n gd e g r e e si s t r a n s f o r m e di n t ot h ec o m p a r i s o nb e t w e e nd e v i a t i o n a lv a r i a b l e s t h et r a d e o f fb e t w e e nt h es u mo ft h e s a t i s f y i n gd e g r e e sa n dp r i o r i t yd i f f e r e n c ei sr e a l i z e db yr e g u l a t i n gt h ep a r a m e t e r t h ee f f e c t i v e n e s sa n d s e n s i t i v i t yo ft h et w oa p p r o a c h e sa r ev e r i f i e db yt h es i m u l a t i o no fn u m e r i c a le x a m p l e s ，d i s t r i b u t e d p a r a m e t e rs y s t e ma n dp r o d u c t i o nd e c i s i o nm a k i n gp r o b l e m c o n s i d e r i n gt h em o o p w i t hp r o g r e s s i v ep r e f e r e n c e ，t h ei n t e r a c t i v ef u z z yo p t i m i z a t i o nm e t h o db a s e d 0 1 1a l t e r n a t i v et o l e r a n c ei sp r o p o s e da c c o r d i n gt od m ss a t i s f y i n gd e g r e e t h ed i f f e r e n tm e m b e r s h i p f u n c t i o ns t r u c t u r e sr e s u l t e df r o mt h ea l t e r n a t i v et o l e r a n c er e f l e c tt h ec h a n g i n go ft h ep r e f e r e n c ed u r i n g t h eo p t i m i z a t i o np r o c e d u r e f o rt h eo p t i m i z a t i o np r o b l e mw i t hf u z z yg o a l s ，t h ea u x i l i a r ym o d e li s i n c o r p o r a t e di no r d e rt oe n s u r et h ef e a s i b i l i t yo ft h ep r o p o s e do p t i m i z a t i o na l g o r i t h m t h et w o p h a s e m o d e lo rr e v i s e dt w o - p h a s em o d e lg u a r a n t e e st h ep a r e t oo p t i m a l i t yo rw e a kp a r e t oo p t i m a l i t yo ft h e s o l u t i o n i na d d i t i o n ，t h em o o pw i t hf u z z yp a r a m e t e r si nt h eo b j e c t i v e sa n dc o n s t r a i n t si ss t u d i e d t h eo p t i m i z a t i o np r o b l e mb a s e do np a r a m e t e ri sf o r m u l a t e du s i n gt h ec u t s e to ff u z z yn u m b e r a c c o r d i n gt ot h ep r i n c i p l eo fa l t e r n a t i v et o l e r a n c e ，t h eo p t i m i z a t i o np r o c e d u r ei n c l u d i n gt h ei n n e ra n d o u t e ri n t e r a c t i o n si sr e a l i z e d t h er e g u l a t i o no fp a r a m e t e ra n dt h ea l t e r n a t i o no ft o l e r a n c ed e n o t et h e c h a n g i n go ft h ep r o g r e s s i v ep r e f e r e n c eo fd m t h es a t i s f y i n g 口一p a r e t oo p t i m a ls o l u t i o no rw e a k 口- p a r e t oo p t i m a ls o l u t i o nc a nb eo b t a i n e db ys o l v i n gt h et w o p h a s em o d e l sw i t hp a r a m e t e r t h e e x a m p l e ss h o wt h ee f f e c t i v e n e s so ft h em e t h o d s f o rt h em o o pw i t l lp o s t e r i o r ip r e f e r e n c e 。d m ss a t i s f y i n gd e g r e ei se x p r e s s e db yp o s t e r i o r is a t i s f y i n g d e g r e e f i r s t l y , t h eu n i f o r m l yd i s t r i b u t e da p p r o x i m a t ep a r e t oo p t i m a ls e to ft h em o o p i sa c q u i r e db y t h em u l t i p l eo b j e c t i v eg e n e t i ca l g o r i t h m ：n s g a i i t h e nt h em o o pw i t hf u z z yg o a l si sr e f o r m u l a t e d a c c o r d i n gt od m t h ec o r r e s p o n d i n gs a t i s f y i n gd e g r e e so fa l lt h eo b j e c t i v e sf o re a c hs o l u t i o na 他g o t f i n a l l y , t h ee l i m i n a t i n go p t i m i z a t i o nm e t h o dr e d u c e st h eo b t a i n e ds e tt ot h em p a r e t oo p t i m a ls u b s e t f u r t h e r m o r e ，t h et r a d i t i o n a lf u z z ycm e a n ( f c m ) c l u s t e r i n gc l a s s i f i e st h es u b s e ti n c l u d i n gm a n y m - p a r e t oo p t i m a ls o l u t i o n st oa c q u i r et h er e p r e s e n t a t i v es u b s e ts u c ht h a td mc a ne a s i l ys e l e c th i s p r e f e r r e dr e s u l t t h es i m u l a t i o n so ft h en u m e r i c a le x a m p l ea n ds c h e d u l i n go p t i m i z a t i o np r o b l e m d e m o n s t r a t et h ef e a s i b i l i t yo ft h et h r e e - s t e po p t i m i z a t i o ns t r a t e g y k e y w o r d s ：m u l t i p l eo b j e c t i v eo p t i m i z a t i o n ，d e c i s i o nm a k i n g ，s a t i s f y i n gd e g r e e ，p r e f e r e n c e ，f u z z y o p t i m i z a t i o n , i n t e r a c t i v e 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 学位论文作者签名：1 碉筵蚜 日期：妒7 年y 月7 驴e t 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密团。 ( 请在以上方框内打“”) 学位论文作者筝名：嘲a 震毛豸 指导挪签名：喜涉 日期：伽彳年岁月谚e 1 日期：矽p 7 年r 月谚日 上海交通大学博士学位论文 1 1 引言 第一章绪论 进行一项复杂的工作往往有许多个方案可供选择，为了取得好的效果，人们总是要设法按某种 标准从中挑选出最好的或满意的方案。当只用一个目标作为选择好坏的标准时。这类问题就称为单 目标优化问题。但是在大多数工程技术、生产管理决策以及国防建设等部门中，所遇到的问题往往 需要同时满足多个目标的要求，考虑多个目标在某种意义和给定约束条件下的最优化问题，即多目 标优化问题( h u a n g & m a s u d ，1 9 7 9 ；c h a n k o n g & h a i m e s ，1 9 8 3 ；胡毓达，1 9 9 0 ；徐玖平李军，2 0 0 5 ) 。 如在工业生产中，除了需要满足产品质量要求外，还需要考虑加工损耗和加工时间等因素：在投资 问题中，决策者总希望投资少、收益大。如此看来，多目标优化问题在各种实际部门中是大量存在 的，与单目标优化相比，显得尤为重要。 多目标优化的思想可以说是萌芽于1 7 7 6 年经济学中的效用理论。1 8 9 6 年，经济学家p a r e t o 首 先在经济平衡的研究中提出了多目标优化问题，引进了被称为p a r e t o 最优的概念。1 9 4 7 年，数学家 n e u m a n 和m o r g e n s t e r n 在对策论的著作中提及多目标决策问题，引起人们对多目标优化研究的重视。 1 9 5 1 年，数理经济学家k o o p m a n s 从生产和分配的效率分析中考虑了多目标优化问题，引入有效解 的定义并得到某些基本结果，他的工作为多目标优化学科奠定了初步的基础。2 0 世纪6 0 年代以来， 人们设计了不少求解多目标优化问题的处理方法，并运用它们去解决各种实际问题，取得了一定效 果。关于多目标优化的研究，不论在理论或应用方面都迅速、蓬勃地开展起来( 林锉云& 董加礼，1 9 9 2 ； m a r l e r a r o r a 。2 0 0 4 ) 。 多目标优化问题的求解是一个决策过程，对于由约束条件形成的可行域，需要根据多个目标的 要求，从中选择最满意的决策方案。然而在复杂的生产和决策环境中，多个目标之间常常是相互冲 突、不可公度的，而且还可能存在不确定性因素，因此求解多目标优化问题就成为一个迭代、重复 决策的过程。所谓相互冲突是指如果采用某一方案去改进某一目标值，会使另一目标的值变坏。这 就使得所有目标都能达到最优的解通常是不存在的或者很难找到的，决策者所能做到的就是在各个 目标之间进行折衷，通过牺牲某个或某些目标的性能来改善其它目标，所以寻找令决策者满意的解 就成为了分析者的主要任务。不可公度是指各个目标没有统一的度量标准，因而难以直接进行比较， 所以不能简单地把多个目标归并为单目标求解。以上这些特点就使得多目标优化成为了一个非常复 杂和特殊的问题，因此传统的单目标优化方法和理论已经不能满足多个目标的要求，设计合适的多 目标优化方法也就成为亟待解决的问题。 1 第一章绪论 在多目标优化问题中，偏好信息是其中至关重要、不可或缺的环，由于多个目标优化中p a r e t o 最优解的个数不是唯一的，所以解的偏爱和选择就成为了求解多目标优化问题的关键。针对有不同 类型偏好和不同性质的优化问题，存在着不同形式的模型和算法。目前没有统一、系统的最佳方法， 各种策略都有其优缺点，有的侧重于目标的综合性能，有的侧重于单个目标的优化：有的强调随机 不确定性，有的则突出模糊特点。总之，如何根据多目标优化问题的特点和决策者给出偏好的类型， 设计相应的优化模型和有效的求解算法，增强算法的实用性，反映解的性质和满意程度，充分发挥 决策者的作用，实现决策者和分析者之间的交互协调，都是目前研究的热点，也是本文研究课题的 出发点。 本章第二部分给出了多目标优化问题的一般描述，第三部分针对不同类型的偏好信息分别介绍 了多目标优化算法的研究现状，第四部分总结了多目标模糊优化算法不同策略的研究，第五部分介 绍了课题组的研究基础，指出了本文主要解决的问题及本文的研究工作和内容安排。 1 2 多目标优化问题的描述 解决多目标优化问题时，首先要建立相应的数学模型j 其次，与传统的单目标优化问题不同的 是，在多目标优化问题中不存在能够使得所有目标同时得到优化的最优解，因此必须给出其特有的 解的定义。 1 2 1 多目标优化问题的模型 一般的多目标优化问题可以归结为以下的共同模式： r a i n 石( 五，) m i n ，( 而，矗) m a ) 【“，) ( 1 1 ) m a x 五( 五，) s j g ，( 五，矗) 0 ，= 1 ，l l 呜( 五，毛) = o ，z = l ，m 2 在上述模型中的玎个变量，称为所考虑模型的决策变量，k ( k 2 ) 个被优化的数值函数 z ( 五，) ，( f = 1 ，尼) 称为模型的目标函数，限制条件毋( 而，吒) o ，( = 1 ，m 。) 和 岛( j c i ，毛) = o ，( ，= l ，m 2 ) 作为约束条件， g j ( x t ，) 和啊( 五，) 共同称为约束函数。 2 上海交通大学博士学位论文 模型( 1 - 1 ) 表示，在一定的约束条件下，对其中，个目标石( 玉，毛) ，z ( 西，) 的最小化 和对七一，个目标厶i ( ，毛) ，五( ，毛) 的最大化被同等地进行。由于是混合的对多个目 标进行优化，因此通常把该类问题称为多目标混合优化问题。 为了简化记号，本文把一组决策变量五，用向量形式表示为 x = ( ，吒) 满足x r 4 。那么七个目标函数可以表示为石( x ) ，左( z ) ，五( x ) ，相应的约束函数可以表示为 g i ( 芦) ，g ：( x ) ，民( 劝和 ( x ) ，如( x ) ，k ( x ) 。此外还要注意，由于鸟( 功= o 总可以写成 鸟( x ) o 且一鸟( x ) 0 ，因此为简单起见，本文将模型( 1 1 ) 中的约束条件统一写为如下形式 x g = x lg y ( x ) 0 时，最优化加权和目标只是 得至l j p a r e t o 最优解的充分条件( g o i c o e c h e ae ta 1 ，1 9 8 2 ) ，只有当所有目标和约束均为凸函数时，才能成 为必要条件( k o s k i ，1 9 8 5 ；m i