（控制科学与工程专业论文）基于进化算法的多目标优化方法研究.pdf

摘要 多目标优化方法具有很强的工程应用背景。近年来，基于进化算法求解多目标 优化问题已成为国际学术界的一个研究热点。本文研究了多目标优化进化算法的关 键技术和算法的应用问题，主要内容如下： ( 1 ) 提出了一种引入偏好信息的多目标优化进化算法。给出了一种将目标间 的相对重要程度进行量化的偏好处理方法，分析了该方法中的参数对偏好处理结果 的影响。基于模糊逻辑构造了一种“强度优于”排序关系，替代常规的p a r e t o 支 配关系判断候选解间的优劣，分析了两种排序关系间的联系。根据“强度优于”关 系设计了一种新型的适应度评价方法。通过图形用户界面在多目标优化进化算法中 交互式地引入决策者的偏好信息，使算法搜索到期望区域内的解。对算法的计算复 杂度进行了分析。使用所提算法求解具有5 个优化目标的柔性机械手控制系统的参 数优化问题，仿真结果表明所提算法能够有效地处理高维多目标优化问题，并能够 减轻决策者的决策负担。 ( 2 ) 提出了一种保持群体多样性的多目标优化进化算法。基于信息熵的概念 给出了一种适用于多目标空间的群体多样性测度。该测度将群体当前的进化状态与 算法的运行机制相关联，探索位于稀疏区域内的精英个体附近的新个体，对精英个 体的保留数目加以控制，依据群体多样性测度的优劣自适应地调整算法新一代群体 的组成方式，并在“利用精英个体 和“探索新区域个体两种模式之间进行转换， 以防止算法因对当前精英个体的过度依赖而产生停滞或早熟现象。对算法的计算复 杂度进行了分析。在多模态测试函数和机械设计问题中的仿真结果表明，所提算法 具有较优的收敛性能和分布特性。 ( 3 ) 针对可以分解的多目标优化问题，提出了一种多目标优化合作型协同进 化算法。使用玎个子群体分别进化问题的n 个决策变量，结合多目标优化问题的特 点，设计了一种能够提高候选解多样性的子群体间合作方式。对算法的计算复杂度 进行了分析。在一组标准测试函数中的仿真结果表明，所提算法具有较高的求解效 率。针对难以分解的多目标优化问题，提出了一种子群体个数动态变化的合作型多 目标优化协同进化算法。给出了一种在多目标优化条件下的进化算法群体停滞判别 准则，设计了多目标优化协同进化算法中子群体新增和灭绝的条件以及算法的终止 准则。对算法的计算复杂度进行了分析，在一组标准测试函数中的仿真结果表明， 所提算法能够在保证算法收敛性能与多样性的同时，尽可能多地节约计算资源。 ( 4 ) 研究了多目标优化进化算法的应用问题。建立了机械手运动学逆解问题 的多目标优化模型，针对该问题的特点，在本论文提出的保持群体多样性的多目标 优化进化算法中，采用了一种能够保证约束条件始终满足的个体生成方式，并基于 改进后的算法求解具有3 个优化目标的冗余机械手运动学逆解问题。建立了单机器 人路径规划问题的多目标优化模型，针对该问题的特点，在本论文提出的保持群体 多样性的多目标优化进化算法中，引入了基于问题先验知识的启发式群体初始化方 法和智能进化算子，使所提算法能够同时优化问题的多个性能指标。建立了多机器 人路径规划问题的多目标优化模型，给出了一种多机器人间的协调策略，使用本论 文提出的多目标优化合作型协同进化算法规划多机器人的运动路径。 关键词：多目标优化进化算法，适应度评价，偏好，p a r e t o 支配，强度优于，模糊 逻辑，多样性，协同进化 i i a bs t r a c t m u l t i o b j e c t i v eo p t i m i z a t i o na p p r o a c h e sh a v e b e e nw i d e l yu s e di nt h ef i e l do f e n g l n e e n n ga p p l i c a t i o n s m a n yr e s e a r c h e r sh a v eb e e na t t r a c t e db yt h er e s e a r c ho ns o l v i n g m u l t i 。o b j e c t i v eo p t i m i z a t i o np r o b l e m sb a s e do ne v o l u t i o n a r ya l g o r i t h m s t h ek e ； t e c h n i q u ei s s u e sa n da p p l i c a t i o n so fm u l t i - o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m s a r es t u d i e di nt h i sd i s s e r t a t i o n ，a n dt h em a i nr e s e a r c hw o r ki sc o n c l u d e da sf o l l o w s ： ( 1 )am u l t i - o b j e c t i v e o p t i m i z a t i o ne v o l u t i o n a r y a l g o r i t h mi n c o r p o r a t i n g p r e t e r e n c ei n f o r m a t i o ni sp r o p o s e d ap r e f e r e n c eh a n d l i n gm e t h o dt oq u a n t i f yt h er e l a t i v e i m p o r t a n c eb e t w e e np a i r so fo b je c t i v e si sp r o p o s e d ，a n dt h ei n f l u e n c eo ft h ep a r a m e t e r so n t h er e s u l t so ft h ep r e f e r e n c eh a n d l i n gi sd i s c u s s e d an e wo u t r a n k i n gr e l a t i o nc a l l e d ”s t r e n g t hs u p e r i o r ”i sc o n s t r u c t e db a s e do nf u z z yl o g i ct oc o m p a r ec a n d i d a t es o l u t i o n s i n s t e a do ft h ec o m m o n l yu s e dp a r e t od o m i n a n c er e l a t i o n t h er e l a t i o n s h i pb e t w e e nt h e s e t w oo u t r a n k i n gr e l a t i o n si sa n a l y z e dt h e o r e t i c a l l y an o v e ls t r a t e g yo ff i t n e s se v a l u a t i o ni s d e s i g n e db a s e do nt h e ”s t r e n g t hs u p e r i o r ”r e l a t i o n t h ep r e f e r e n c ei n f o r m a t i o no ft h e d e c i s i o nm a k e ri i n c o r p o r a t e di n t ot h ea l g o r i t h mi n t e r a e t i v e l yv i et h eg r a p h i c a lu s e r i n t e r f a c ei no r d e rt og u i d et h ea l g o r i t h mt of i n dt h es o l u t i o n sl o c a t e di nt h ed e s i r e dr e g i o n s t h ec o m p u t a t i o n a lc o m p l e x i t yo ft h ea l g o r i t h mi sa n a l y z e d t h ep r o p o s e da l g o r i t h mi s a p p l i e dt oap a r a m e t e ro p t i m i z a t i o np r o b l e mi nt h ec o n t r o ls y s t e mf o ram a n i p u l a t o rw i t h 5o b j e c t i v e s s i m u l a t i o nr e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mc a nd e a lw i t hh i g h d i m e n s i o n a lm u l t i - o b j e c t i v eo p t i m i z a t i o n p r o b l e m se f f e c t i v e l y , a n di tc a nr e d u c et h e b u r d e no ft h ed e c i s i o nm a k e r ( 2 )a m u l t i o b je c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h mk e e p i n gd i v e r s i t yo f t h ep o p u l a t i o ni sp r o p o s e d am e t r i cb a s e do ne n t r o p yt om e a s u r et h ed i v e r s i t yo ft h e p o p u l a t i o ni nt h ec a s eo fm u l t i o b j e c t i v es p a c ei sp r o p o s e d t h ee v o l v i n gs t a t eo fc u r r e n t p o p u l a t i o ni sa s s o c i a t e dw i t ht h er u n n i n gm e c h a n i s mo ft h ea l g o r i t h mb yt h ed i v e r s i t y m e t r i c i te x p l o r e sn e wi n d i v i d u a l si nt h ev i c i n i t yo fe l i t i s ti n d i v i d u a l sl o c a t e di nt h es p a r s e r e g i o n ，c o n t r o l st h en u m b e ro fe l i t i s ti n d i v i d u a l s ，a d ju s t st h ef o r m a t i o no ft h ep o p u l a t i o ni n t h en e w g e n e r a t i o na d a p t i v e l ya c c o r d i n gt ot h ed i v e r s i t ym e t r i c ，a n dc o n v e y sb e t w e e nt h e t w os e a r c h i n gm o d e sw h i c ha r ee x p l o i t a t i o no fe l i t i s ti n d i v i d u a l sa n de x p l o r a t i o no fn e w i n d i v i d u a l ss oa st op r e v e n tt h ea l g o r i t h mf r o ms t a g a t i o no rp r e m a t u r e t h ec o m p u t a t i o n a l c o m p l e x i t yo ft h ea l g o r i t h mi sa n a l y z e d s i m u l a t i o nr e s u l t si nac o m p l e xm u l t i m o d a l f u n c t i o na n dam e c h a n i c a ld e s i g np r o b l e mi n d i c a t et h a tt h ep r o p o s e da l g o r i t h mh a sg o o d p e r f o r m a n c eo fc o n v e r g e n c ea n dd i s t r i b u t i o n ( 3 ) f o rt h ed e c o m p o s a b l ep r o b l e m ，ac o o p e r a t i v ec o e v o l u t i o n a r ya l g o r i t h mf o r m u l t i o b j e c t i v eo p t i m i z a t i o ni sp r o p o s e d 以s u b p o p u l a t i o n sa r es e tt oe v o l v e 疗d e c i s i o n i i i v a r i a b l e so ft h ep r o b l e mr e s p e c t i v e l y c o n s i d e r i n gt h ec h a r a c t e r i s t i c so fm u l t i o b je c t i v e o p t i m i z a t i o np r o b l e m s ，an o v e lf o r mo fc o l l a b o r a t i o na m o n gs u b p o p u l a t i o n sw h i c hc a r l i n c r e a s et h e d i v e r s i t yo ft h ec a n d i d a t e s o l u t i o n si s d e s i g n e d t h ec o m p u t a t i o n a l c o m p l e x i t yo ft h ea l g o r i t h mi sa n a l y z e d s i m u l a t i o nr e s u l t si nas u i t eo fs t a n d a r dt e s t f u n c t i o n si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mh a sh i 曲s e a r c h i n ge f f i c i e n c y f o rt h e u n d e c o m p o s a b l ep r o b l e m ，am u l t i o b j e c t i v eo p t i m i z a t i o nc o e v o l u t i o n a r ya l g o r i t h mw i t h d y n a m i c a l l yv a r y i n gn u m b e ro fs u b p o p u l a t i o n si sp r o p o s e d an e wc r i t e r i o nj u d g i n gt h e s t a g n a t i o no ft h ep o p u l a t i o ni ne v o l u t i o n a r ya l g o r i t h m si nt h ee x i s t e n c eo fm u l t i p l e o b j e c t i v e si sp r e s e n t e d ，a n dt h ec o n d i t i o n so fa d d i n ga n dd e l e t i n gs u b p o p u l a t i o n sa n dt h e s t o p p i n gc r i t e r i o no ft h ea l g o r i t h ma r ei n d u c e d t h ec o m p u t a t i o n a lc o m p l e x i t yo ft h e a l g o r i t h mi sa n a l y z e d s i m u l a t i o nr e s u l t si nas u i t eo fs t a n d a r dt e s tf u n c t i o n si n d i c a t et h a t t h ep r o p o s e da l g o r i t h mc a ns a v ec o m p u t a t i o n a lr e s o u r c e sa sm a n ya s p o s s i b l ew h i l e e n s u r i n gt h ep e r f o r m a n c eo fc o n v e r g e n c ea n dd i v e r s i t yo ft h ea l g o r i t h m ( 4 ) t h ea p p l i c a t i o n so fm u l t i - o b je c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m sa r e s t u d i e d t h em u l t i o b je c t i v eo p t i m i z a t i o nm o d e lo ft h ei n v e r s ek i n e m a t i c sp r o b l e mo ft h e r e d u n d a n tm a n i p u l a t o ri sc o n s t r u c t e d f o rt h ec h a r a c t e r i s t i co ft h i sp r o b l e m ，an e w w a y t o p r o d u c ei n d i v i d u a l sw h i c hc a l le n s u r et h es a t i s f a c t i o no ft h ec o n s t r a i n t si sa d o p t e di nt h e p r o p o s e dm u l t i - o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h mk e e p i n gd i v e r s i t yo ft h e p o p u l a t i o n t h ei m p r o v e da l g o r i t h mi se m p l o y e dt os o l v et h ei n v e r s ek i n e m a t i c sp r o b l e m o ft h er e d u n d a n tm a n i p u l a t o rw i t h3o b je c t i v e s t h em u l t i o b je c t i v eo p t i m i z a t i o nm o d e lo f t h es i n g l er o b o tp a t h p l a n n i n gp r o b l e mi sc o n s t r u c t e d f o rt h e c h a r a c t e r i s t i c so ft h i s p r o b l e m ，t h e h e u r i s t i cm e t h o db a s e do nd o m a i nk n o w l e d g ei s e m p l o y e di n t h e i n i t i a l i z a t i o n ，a n dt h r e ei n t e l l i g e n te v o l u t i o n a r yo p e r a t o r sa r ea d o p t e di nt h ep r o p o s e d m u l t i - o b je c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h mk e e p i n gd i v e r s i t yo ft h ep o p u l a t i o n ， w h i c hm a k et h ea l g o r i t h mo p t i m i z em u l t i p l eo b j e c t i v e so ft h ep r o b l e ms i m u l t a n e o u s l y t h em u l t i - o b je c t i v eo p t i m i z a t i o nm o d e lo ft h em u l t i r o b o tp a t h p l a n n i n gp r o b l e mi s c o n s t r u c t e d ac o o r d i n a t e ds t r a t e g ya m o n gr o b o t si sp r e s e n t e d t h ep a t h so fm u l t i p l e r o b o t sa r ep l a n n e db a s e do nt h ep r o p o s e dc o o p e r a t i v ec o e v o l u t i o n a r ya l g o r i t h mf o r m u l t i o b j e c t i v eo p t i m i z a t i o n k e y w o r d s ：m u l t i o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m s ，f i t n e s se v a l u a t i o n ， p r e f e r e n c e ，p a r e t od o m i n a n c e ，s t r e n g t hs u p e r i o r , f u z z yl o g i c ，d i v e r s i t y , c o e v o l u t i o n i v 博士论文基于进化算法的多目标优化方法研究 缩略词 缩略词英文全称中文全称 e a e v o l u t i o n a r ya l g o r i t h m 进化算法 m o e a多目标优化进化算法 m u l t i - o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r y a l g o r i t h m v e g av e c t o re v a l u a t e dg e n e t i ca l g o r i t h m 向量评估遗传算法 h a j e l a 和l i n 提出的 h l g a h a je l aa n dl i n sg e n e t i ca l g o r i t h m 遗传算法 小生境p a r e t o 遗传算 n p g an i c h e dp a r e t og e n e t i ca l g o r i t h m 法 n s g a n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m 非支配排序遗传算法 n o n d o m i n a t e ds o r t i n gg e n e t i c 非支配排序遗传 n s g a i i a l g o r i t h m - i i算法一i i m o g a g e n e t i ca l g o r i t h mf o rm u l t i o b je t i v e 多目标优化遗传算法 o p t i m i z a t i n s p e a s t r e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m 强度p a r e t o 进化算法 s p e a 2 s t r e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m2 强度p a r e t o 进化算法2 p a r e t o 存储的进化 p a e s p a r e t oa r c h i v e de v o l u t i o ns t r a t e g y 策略 e s e v o l u t i o n a r ys t r a t e g y 。进化策略 小生境p a r e t o 遗传 n p g a 2n i c h e dp a r e t og e n e t i ca l g o r i t h m2 算法2 g ag e n e t i ca l g o r i t h m 遗传算法 e p e v o l u t i o n a r yp r o g r a m m i n g 进化规划 缩略词博士论文 “没有免费的午餐 n f l n of r e el u n c h 定理 i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i c l c g a国际遗传算法会议 a l g o r i t h m s w o r k s h o po nf o u n d a t i o no fg e n e t i c f o g a遗传算法基础研讨会 a l g o r i t h m s e v o l u t i o n a r yd y n a m i cw e i g h t e d动态加权组合进化 e d a a g g r e g a t i o n算法 g u i g r a p h i c a lu s e ri n t e r f a c e 图形用户界面 a h p a n a l y t i ch i e r a r c h yp r o c e s s 层次分析法 m u l t i - o b je c t i v eo p t i m i z a t i o ne v o l u t i o n a r y 引入偏好信息的多目 p i m o e a a l g o r i t h mi n c o r p o r a t i n gp r e f e r e n c e 标优化进化算法 i n f o r m a t i o n 月黟名r a n d o mw e i g h t e da g g r e g a t i o n 随机加权组合算法 c o n t r o l l e dc o n t r o l l e dn o n d o m i n a t e ds o r t i n gg e n e t i c 加以控制的非支配排 n s g a i i a l g o r i t h m i i 序遗传算法一i i m u l t i o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r y 保持群体多样性的多 k d m o e a a l g o r i t h mk e e p i n gd i v e r s i t yo ft h e 目标优化进化算法 p o o u l a t i o n c o o p e r a t i v ec o e v o l u t i o n a r ym u l t i o b j e c t i v e 非支配排序合作型多 n s c c g a a l g o r i t h mu s i n gn o n d o m i n a t e ds o r t i n g目标协同进化算法 c o o p e r a t i v ec o e v o l u t i o n a r ya l g o r i t h mf o r 多目标优化合作型协 m o c c e a m u l t i o b j e c t i v eo p t i m i z a t i o n 同进化算法 m u l t i - o b je c t i v eo p t i m i z a t i o n 子群体个数动态变化 c o - e v o l u t i o n a r ya l g o r i t h mw i t h 的多目标优化协同进d v n m o c e a d y n a m i c a l l yv a r y i n gn u m b e r o f s u b p o p u l a t i o n s 化算法 x 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谫 的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：年月 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论丈的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：年月 日 博士论文基于进化算法的多目标优化方法研究 1 绪论 1 1研究的目的与意义 多目标优化是最优化领域中的一个重要研究方向。在工程设计、经济管理、自 然与社会科学中的许多实际问题均需要同时对多个目标进行优化。这些问题包括生 产调度、自动控制、城市运输、资本预算、水资源管理、能量分配、后勤补给、网 络通信、机械设计与制造等，可以说多目标优化问题无处不有、无处不在。当前随 着科学技术的迅猛发展，系统的规模增大，约束条件增多，非线性严重。优化问题 的复杂化对多目标优化方法的性能提出了更高的要求，也给多目标优化方法的研究 带来了巨大的挑战。 多目标优化问题中的各个目标并不是独立存在的，它们之间往往是相互矛盾、 相互冲突的，因此与单目标优化问题不同，多目标优化问题通常不存在一个唯一的 最优解，也就是说，要同时使所有的目标均达到最优值是不可能的，而只能在它们 之间进行协调，找出问题的一组折中解。传统的优化方法，如梯度法皑1 、单纯形法瞳1 、 模拟退火法1 、禁忌搜索法凹1 等，主要针对单目标优化问题，它们一次运行只能搜索 到一个解，且这些方法的可行性易受到问题搜索空间的形状( 如凹凸性) 、连续性以 及目标函数的可微性的限制，因此它们不适合求解同时具有多个解的复杂多目标优 化问题。在早期的应用中，常常采用加权求和法h 1 、目标规划法嵋1 、m i n m a x 法1 等 决策方法将多个目标转换为单个目标函数，再使用上述传统优化方法求得问题的某 一个解。 进化算法( e v o l u t i o n a r ya l g o r i t h m ，简称e a ) 。即是模拟生物在自然环境中的 进化过程而形成的一类自适应全局优化概率搜索算法。进化算法同时对整个群体进 行操作，可以在算法的一次运行中并行搜索到多个解，它具有很强的通用性，可以 处理传统优化方法难以解决的复杂优化问题，例如非连续、多模态等问题。因此， 进化算法特别适用于求解同时存在多个解的多目标优化问题。 上世纪八十年代中期，进化算法被首次应用于多目标优化问题中啤1 。从九十年代 中期开始，多目标优化进化算法( m u l t i o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r y a l g o r i t h m ，简称m o e a ) 这个新兴的研究领域才开始得到长足的发展。它体现了现代 科学技术发展中生命科学与工程科学相互交叉、相互渗透和相互促进的特征和趋势。 多目标优化进化算法赋予了进化算法新的内涵，由此形成的一个崭新领域正引起众 多学者的浓厚兴趣。进化算法在多目标优化问题中的应用对构造新一代人工智能系 第1 章绪论博j 二论文 统的研究具有重要的意义，广泛适用于经济学、几何学、物理、机械设计、数值优 化等领域。 然而，由于多目标优化问题自身蕴含的特点，使得现有的基于单目标进化算法 的理论模式和研究成果的人工进化模型不再适用。这对进化算法在多目标优化问题 中的合理应用提出了挑战。尽管目前己发展的多目标优化进化算法种类较多，但尚 缺乏系统研究，很多理论问题有待于进一步探讨旧1 0 1 。这些问题包括如何处理高维多 目标优化问题( 目标个数大于等于3 ) 、引入决策者的偏好信息、维护进化群体的多 样性、减少个体适应度评价的次数、保证算法的收敛性、度量算法搜索到的近似 p a r e t o 最优解集的性能等。 1 2多目标优化问题中的基本概念 以下给出多目标优化问题中的几个重要定义： 定义1 2 1 一多目标优化问题1 ：不失一般性，假设求解多目标最小化问题， 则多目标优化问题的数学模型可描述如下： r a i n 涉= f ( x ) = ( z ( x ) ，六( x ) ，以，( x ) ) s t g ，( x ) 0 ，f = 1 , 2 ，h ，工x r ”，y y r ( 1 2 1 ) 其中，工为决策向量，y 为目标向量，x 为决策向量x 形成的决策空间，y 为目标 向量j ，形成的目标空间。吕( x ) 0 ，f - 1 , 2 ，h 为x 需满足的h 个约束条件。 定义1 2 2 一可行解集n ：可行解集x ，定义为满足式( 1 2 1 ) 中的约束条件 g ( x ) 0 ，f = 1 , 2 ，h 的决策向量x 的集合，即 x ，= 扛xg ，( x ) o ，i = 1 , 2 ，h ( 1 2 2 ) x ，的图形( 即可行区域) 所对应的目标空间表示为： = f ( x ，) = k x ，舻( x ) ( 1 2 3 ) 式( 1 2 3 ) 的物理意义是对于可行解集x ，中的所有x ，经优化函数映射形成目标空 间中的一个子空间，该子空间对应的决策向量均属可行解集。 定义1 2 3 一p a r e t o 支配n ：设x ，为多目标优化问题的可行解集， ，( x ) = ( 石( x ) ，六 ) ，厶 ) ) 为目标向量，x x ，x l x ，。称x kp a r e t o 支配一( 简 称支配，记作耳- x t ) 当且仅当 vf 1 ，2 ，朋 ：，( x - ) 厂( x ，) ( 1 2 4 ) 且3 1 , 2 ，研) ：厂( x t ) 六( x ，) 博j 二论文幕十进化算法的多目标优化方法f i 】i = 究 定义1 2 4 一p a r e t o 最优n 1 。：如果在某一集合中不存在任何其它解x 。p a r e t o 支 配x ，则称x 为该集合中的p a r e t o 非支配解( 简称非支配解) ；如果x 为多目标优化 问题整个可行解集中的p a r e t o 非支配解，则称x 为该问题的p a r e t o 最优解。 定义1 2 5 一p a r e t o 最优解集1 ：一个多目标优化问题所有p a r e t o 最优解的集 合构成了该问题的p a r e t o 最优解集。 定义1 2 6 一p a r e t o 最优前沿1 ：一个多目标优化问题所有p a r e t o 最优解对应 的目标向量集合构成了该问题的p a r e t o 最优前沿。 p a r e t o 最优解集存在全局最优和局部最优的概念之分。 定义1 2 7 一局部p a r e t o 最优解集1 ：对于决策向量集b x ，b 称为局部 p a r e t o 最优解集，当且仅当 v x 8 b ：不存在x x ： x ax x 占i i 0 。 定义1 2 8 一全局p a r e t o 最优解集1 ：对于决策向量集b x ，b 称为全局 p a r e t o 最优解集，当且仅当 。 vx r b ：不存在x x r ：x 一 x r ( 1 2 6 ) 由定义1 2 7 和定义1 2 8 可见，局部p a r e t o 最优解集中的解只是在它的邻域 范围内是p a r e t o 非支配的，它们并不是整个问题的p a r e t o 最优解；而全局p a r e t o 最优解是在问题的整个决策空间中都是p a r e t o 非支配的，它们是问题的p a r e t o 最 优解。 由上述定义可以得出以下结论： ( 1 ) 在绝大多数情况下，多目标优化问题的若干个目标之间是相互冲突的，因 此，类似于单目标优化中的最优解在多目标优化问题中是不存在的，而只 存在p a r e t o 最优解。多目标优化问题的p a r e t o 最优解仅仅只是它的一个 可以接受的“不坏”的解。多目标优化问题通常具有很多个p a r e t o 最优 解； ( 2 ) 提高p a r e t o 最优解在任何一个目标上的性能，都必然会导致它在其它至 少一个目标上的性能降低。 ( 3 )当多目标优化问题各个目标间的相对重要性( 即偏好信息) 未知时，可以 认为多个p a r e t o 最优解之间是相互平等的，无法比较它们的优劣； ( 4 ) 多目标优化问题的多个p a r e t o 最优解构成了一个集合。对于实际应用问 题，必须由决策者依据对问题的了解程度和其个人偏好，从问题的p a r e t o 最优解集中挑选出一个或一些“足够满意”的解作为最终解。因此求解多 第1 章绪论 博：f ：论文 目标优化问题的首要和关键步骤是求出其所有的p a r e t o 最优解。 ( 5 ) 大多数情况下，多目标优化问题的p a r e t o 最优前沿曲面位于目标向量空 间( 即可行决策空间对应的目标空间) 的边界，图1 - 2 1 给出了一个二目 标最小化问题的p a r e t o 最优前沿曲线图。图中， 和厶分别为两个最小 化目标函数， 工。点和点分别为问题的两个p a r e t o 最优解，当从工。点 移动到点时，在函数厶上的性能变优，但在z 上的性能却变差。毛点 p a r e t o 支配x ，点。 z 图1 2 1二目标最小化问题的p a r e t o 最优前沿曲线图 1 3多目标优化进化算法的研究现状 自八十年代中期以来，国内外学者先后提出了多种具有不同特点的多目标优化 进化算法。一般情况下，进化算法在求解多目标优化问题时主要有两个性能要求】： 一是保证算法的收敛性，即在目标空间中，所求得的近似p a r e t o 最优解集与真实的 p a r e t o 最优解集应尽可能接近：二是维护进化群体的多样性，使得最终求得的解集 在目标空间中具有较好的分布特性( 如均匀分布) ，且分布范围尽可能宽广。为了满 足以上要求，需确定适当的个体适应度评价与选择策略，以引导算法朝p a r e t o 最优 前沿的方向进行搜索，同时采取有效的群体多样性保留方法，以防止算法早熟收敛。 此外，精英保留策略、偏好信息的引入等也是多目标优化进化算法中常用的技术方 法，而度量算法求得的近似p a r e t o 最优解集性能的测度、标准测试问题、算法的理 论基础、算法在实际优化问题中的应用等也是多目标优化进化算法领域的几个研究 方向。 博七论文 基十进化算法的多日标优化方泫研究 1 3 1 适应度评价 在多目标优化问题和单目标优化问题中分别使用进化算法，最大的区别在于对 个体适应度的评价。单目标优化问题中，个体的性能由目标函数值来度量，因此个 体适应度往往就等于目标函数值或者对目标函数值进行适当的数学变换。而在多目 标优化问题中，由于同时存在着多个相互矛盾的优化目标，使得恰当的选择机制， 特别是如何对个体适应度进行适当的评价，成为进化算法最终能否收敛到p a r e t o 最 优解集的关键因素。 目前，多目标优化进化算法主要有三种适应度评价策略：组合函数法、基于群 体但未引入p a r e t o 支配概念的方法、基于群体且引入p a r e t o 支配概念的方法