（控制理论与控制工程专业论文）基于极值动力学的优化方法及其应用研究.pdf

基于极值动力学的优化方法及其应用研究 摘要 近年来，对n p 难的组合优化问题寻求高效的解决方法已成为优化领 域的一个极具挑战性的研究课题。除了传统的运筹学方法，现代启发式 方法正在得到越来越多的研究人员的关注和重视，已经广泛地应用于基 础研究和实际工程领域。现有的大多数启发式方法，如进化算法、人工 生命、模拟退火算法和禁忌算法等，都是从生物进化、统计物理和人工 智能等领域发展而来。 极值动力学优化算法( e x t r e m a lo p t i m i z a t i o n ，e o ) 是近年来出现 的一种新颖的、通用的、基于局部搜索的启发式方法，该方法是 从统计物理学发展而来。众所周知，模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 是模拟系统处于平衡态的一种优化方法，与s a 不同的 是，e o 算法的理论基础建筑在b a k s n e p p e n 生物进化模型之上，该模型 模拟处于远离平衡态的系统，具备自组织临界性( s e l f - o r g a n i z e dc r i t i c a l i t y ，s o c ) 。s o c 是指不管系统处于何种初始状态，不需要调整任何 参数，整个系统就可以演化到一个自组织临界状态，在该状态下，系统 呈现出幂律分布( p o w e r - l a w ) 。遗传算法通过对交配池中的所有可能 解实施选择、杂交和变异等遗传操作来达到寻优的目的，而e o 算法总 是不断地变异近似解的最差组成部分( 即所谓的极值动力学机制) 来达 到寻优的目的。正是这种内在的极值动力学机制，使得e o 具备很强的 爬山能力，尤其在求解带有相变点( p h a s et r a n s i t i o n s ) 的组合优化问题 时e o 更是展现出强大的优势。e o 算法的特点是收敛速度快，局部搜索 能力强，只有变异算子，无可调参数( 对于基本e o 算法) 或只有一个 可调参数丁( 对于7 - 一e o 算法) 。目前e o 算法已经被成功地应用于求解一 些n p 难的组合优化问题，如二分图，旅行商问题，图着色，旋转玻璃和 动态组合优化问题。但是，国外对于e o 算法在数值优化和多目标优化问 题方面的研究并不多，国内学者对e o 算法的研究更少之甚少。 本文主要研究求解无约束或带约束数值优化问题的e o 算法，并将求 解单目标优化问题的e o 算法扩展到多目标优化领域。本文的主要工作包 括： 一卜海交通大学博十学位论文 ( 1 ) 本文从分析e o 算法的机理入手，提出了一种求解约束连续优化问题 的新算法一一带自适应l 6 v y 变异的基于种群的e o 算法( p e o ) ，通 过求解6 个经典的约束连续优化问题，实验结果证实了p e o 能与3 种 流行的优化算法相匹敌，不失为一种求解数值约束优化问题的有效 方法。 ( 2 ) 为了弥补标准粒子群算法容易陷入局部极值点的不足，本文提出 了一种新颖的混合粒子群一极值动力学优化算法( p s o e o ) ，该 算法有效地结合了p s o 的全局搜索能力和e o 的局部搜索能力，使得 标准p s o 算法可以跳出局部极值点，从而弥补了标准p s o 算法的不 足。迄今为止，还没有文献提出将e o 和p s 0 结合起来的优化算法。 通过求解6 个经典的复杂单峰多峰函数，p s o e o 算法被证实了具有 避免早熟收敛的特点，是一种求解复杂数值优化问题的有效算法。 ( 3 ) 由于e o 算法只有变异操作，因此，变异算子对e o 算法的性能好坏 起到了重要作用。本文将高斯变异和柯西变异有效地结合起来，提 出了一种新颖的适合于求解数值优化问题的变异算子一一混合高斯 一柯西变异，该算子将“粗调”和“微调 很好地结合起来，并且 省去了决定何时在不同变异之间进行切换的麻烦。 ( 4 ) 本文将基于p a r e t o 支配概念的适应度评价方法引入到e o ，提出了一 种新颖的多目标极值动力学优化方法( m u l t i o b j e c t i v ee x t r e m a lo p t i m i z a t i o n ，m o e o ) ，使e o 算法成功地扩展到多目标优化领域。 接着，用m o e o 算法解决了多目标连续优化问题( 包括无约束问 题和带约束问题) ，实验结果表明m o e o 非常适合于求解多目 标连续优化问题，能够与3 种经典的多目标进化算法( 即n s g a i i ，s p e a 2 和p a e s ) 相匹敌。最后，提出了一种适合于求解多目 标彤1 背包问题的m o e o 算法。实验结果表明m o e o 算法具有快速的 收敛能力和良好的多样化性能，具有与3 种经典的多目标进化算法 ( 即n s g a ，s p e a 和n p g a ) 相竞争的优势。 ( 5 ) 本文利用m o e o 算法解决了4 个经典的机械组件设计问题。实验 结果表明：m o e o 算法找到的非劣解集在收敛性和多样性方面 有着良好的性能，能够与3 种经典的多目标进化算法( n s g a i i ，s p e a 2 和p a e s ) 相匹敌。因此，m o e o 算法是一个能解决实 际工程优化问题的行之有效的方法。 中文摘要 ( 6 ) 本文将m o e o 算法应用于求解5 个经典的股票投资组合优化问题。 实验结果表明：m o e o 找到的近似p a r e t o 前沿具有良好的收敛性能 和多样化性能，能够与算法n s g a i i 和s p e a 2 相匹敌，l 匕p a e s 更 优。因此，m o e o 算法是一个能解决实际管理决策优化问题的有效 方法。 关键词：极值动力学优化算法，多目标优化，进化算法，粒子群算法， 数值优化，p a r e t o 前沿，多目标0 1 背包问题，机械组件设计，投资组合 优化 s t u d i e so no p t i m i z a t i o nm e t h o d sw i t he x t r e r n a ld y n a m i c sa n d a p p l i c a t i o n s a b s t r a c t i l lr e c e n ty e a r s t h es t u d i e so nn p - h a r dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sh a v eb e e n a c h a l l e n g es u b j e c ti no p t i m i z a t i o nc o m m u n i t y i na d d i t i o nt ot r a d i t i o n a lo p e r a t i o n sr e s e a r c h ， t h em o d e mh e u r i s t i c sh a v e b e e na t t r a c t i v ei nf u n d a m e n t a lr e s e a r c ha n dr e a la p p l i c a t i o n s t h e a p p r o a c h e st oe v o l u t i o n a r ya l g o r i t h m ( e a ) ，a r t i f i c i a ll i f e ，s i m u l a t e da n n e a l i n g ( s a ) a n dt a b u s e a r c he ta 1 a r ed e v e l o p e df r o mt h en a t u r e so fb i o l o g i c a le v o l u t i o n ，s t a t i s t i c a lp h y s i t sa n d a r t i f i c i a li n t e l l i g e n c ee ta 1 r e c e n t l y an o v e lg e n e r a l - p u r p o s el o c a ls e a r c ho p t i m i z a t i o na p p r o a c h ，s o - c a l l e d “e x - t r e m a lo p t i m i z a t i o n ( e o ) ”h a sb e e np r o p o s e db a s e do nt h ef u n d a m e n t a l so fs t a t i s t i c a l p h y s i c s i nc o n t r a s tt os a w h i c hi si n s p i r e db ye q u i l i b r i u ms t a t i s t i c a lp h y s i c s ，e oi sb a s e d o nb a k - s n e p p e n ( b s ) m o d e lo fb i o l o g i c a le v o l u t i o nw h i c hs i m u l a t e sf a r - f r o me q u i l i b r i u m d y n a m i c si ns t a t i s t i c a lp h y s i c s t h eb sm o d e li so n eo ft h em o d e l st h a ts h o wt h en a t u r e o fs e l f - o r g a n i z e dc r i t i c a l i t y ( s o c ) t h es o cm e a n st h a tr e g a r d l e s so ft h ei n i t i a ls t a t e ，t h e s y s t e ma l w a y st u l l e si t s e l ft oac r i t i c a lp o i l l th a v i n gap o w e r - l a wb e h a v i o rw i t h o u ta n yt u n - i n gc o n t r o lp a r a m e t e r i nc o n t r a s tt og e n e t i ca l g o r i t h m s ( g a s ) w h i c ho p e r a t eo na ne n t i r e “g e n e p o o l ”o fh u g en u m b e ro fp o s s i b l es o l u t i o n s ，e os u c c e s s i v e l ye l i m i n a t e st h o s ew o r s t c o m p o n e n t si nt h es u b o p t i m a ls o l u t i o n s t h ee x t r e m a ld y n a m i c sm e c h a n i s mi ne op r o v i d es i g n i f i c a n th i l l - c l i m b i n ga b i l i t y , w h i c he n a b l e se ot op e r f o r mw e l lp a r t i c u l a r l ya tt h e p h a s et r a n s i t i o n s e oh a sm a n ya d v a n c e df e a t u r e s ，s u c ha sf a s tc o n v e r g e n c es p e e d ，s t r o n g a b i l i t yo fl o c a ls e a r c h ，o n l ym u t a t i o no p e r a t o r , n oa d j u s t a b l ep a r a m e t e rf o rb a s i ce o o ro n l y o n ea d j u s t a b l ep a r a m e t e r7 f o r7 - - e o e oh a sb e e ns u c c e s s f u l l ya p p l i e dt os o m en p h a r d c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ss u c ha sg r a p hb i - p a r t i t i o n i n g ，t r a v e l i n gs a l e s m a np r o b - l e m ( t s p ) ，g r a p hc o l o r i n g ，s p i ng l a s s e sa n dd y n a m i cc o m b i n a t o r i a lp r o b l e m s h o w e v e r , s o f a rt h e r eh a v eb d e no n l yl i m i t e dp a p e r ss t u d y i n go nt h em e c h a n i s mo fe oa p p l i e dt on u m e r - i c a lo p t i m i z a t i o np r o b l e m so rm 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 s ( m o p s ) t h i sp a p e rm a k e sa ni n v e s t i g a t i o no nt h em e c h a n i s mo fe of o rs o l v i n gt h eu n c o n - s t r a i n e do rc o n s t r a i n e dn u m e r i c a lo p t i m i z a t i o np r o b l e m s ，a n df u r t h e re x t e n d se ot od e a l w i t ht h em o p s t h em a i nr e s e a r c hw o r ki n c l u d e s ： v 上海交通大学博十学位论文 ( 1 ) b a s e do nt h ea n a l y s i so nt h em e c h a n i s mo fe o ，t h i sp a p e rp r e s e n t san e wa l g o r i t h m n a m e d p o p u l a t i o n b a s e de ow i t ha d a p t i v el r v ym u t a t i o n ( p e o ) c o m p a r e dw i t ht h r e e s t a t e - o f - t h e a r ts t o c h a s t i cs e a r c hm e t h o d sw i t hs i xb e n c h m a r kf u n c t i o n s ，i th a sb e e n s h o w nt h a to u r a p p r o a c hi sag o o dc h o i c et od e a lw i t ht h en u m e r i c a lc o n s t r a i n e do p t i - m i z a t i o np r o b l e m s ( 2 ) t oo v e r c o m et h el i m i t a t i o no fs t a n d a r dp s o ，t h i sp a p e rp r o p o s e san o v e lh y b r i da l g o r i t h m ，c a l l e dh y b r i dp s o e oa l g o r i t h m ，t h r o u g hi n t r o d u c i n ge ot op s o t h eh y b r i d a p p r o a c he l e g a n t l yc o m b i n e st h ee x p l o r a t i o na b i l i t yo fp s o w i t ht h ee x p l o i t a t i o na b i l i v yo f e oa n dt h u st h eh y b r i da l g o r i t h mc a nh e l ps t a n d a r dp s ot o j u m po u to f t h el o c a l o p t i m a t h ep r o p o s e da p p r o a c hi sv a l i d a t e du s i n gs i xc o m p l e xu n i m o d a l m u l t i m o d a l b e n c h m a r kf u n c t i o n s t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e da p p r o a c h i sc a p a b l eo fa v o i d i n gp r e m a t u r ec o n v e r g e n c e t h u s ，t h eh y b r i dp s o e oa l g o r i t h m c a nb ec o n s i d e r e dag o o da l t e r n a t i v et os o l v ec o m p l e xn u m e r i c a lf u n c t i o no p t i m i z a - t i o np r o b l e m s ( 3 ) s i n c et h e r ei sm e r e l ym u t a t i o no p e r a t i o ni ne o ，t h em u t a t i o no p e r a t o rp l a y sak e y r o l ei ne os e a r c h i nt h i sp a p e r , w ep r e s e n tan e wm u t a t i o nm e t h o db a s e do nm i x i n g g a u s s i a nm u t a t i o na n dc a u c h ym u t a t i o n ，c a l l e dh y b r i dg a u s s i a n - c a u c h ym u t a t i o n t h en e wm u t a t i o no p e r a t o rc o m b i n e st h ea d v a n t a g e so fc o a r s e g r a i n e ds e a r c ha n d f i n e g r a i n e ds e a r c h u n l i k es o m es w i t c h i n ga l g o r i t h m sw h i c hh a v et od e c i d ew h e n t os w i t c hb e t w e e nd i f f e r e n tm u t a t i o n s d u r i n gs e a r c h ，t h eh y b r i dg c m u t a t i o nd o e sn o t n e e dt om a k es u c hd e c i s i o n s ( 4 ) i no r d e rt oe x t e n de o t os o l v et h em o p s ，i nt h i sw o r k , w ep r o p o s ean o v e lm u l t i o b j e c t i v eo p t i m i z a t i o na l g o r i t h m ，c a l l e dm u l t i o b j e c t i v ee x t r e m a lo p t i m i z a t i o n ( m o e o ) ， t h r o u g hi n t r o d u c i n gt h ef i t n e s sa s s i g n m e n tb a s e do np a r e t oo p t i m a l i t yt oe o i nt h i s p a p e r , m o e oh a sb e e ns u c c e s s f u l l ya p p l i e dt os o l v i n gu n c o n s t r a i n e do rc o n s t r a i n e d m o p s t h es 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 p p r o a c hi sh i g h l yc o m p e t i t i v ew i t ht h r e es t a t e - o f - t h e a r tm u l t i o b j e c t i v ee v o l u t i o n a r ya l g o r i t h m s ( m o e a s ) ，i e ， n s g a i i ，s p e a 2a n dp a e s t h i sp a p e ra l s os u c c e s s f u l l ye x t e n d sm o e ot os o l v e t h em u l t i o b j e c t i v e0 1k n a p s a c kp r o b l e m s t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a t t h ep r o p o s e da p p r o a c hi sh i ：g h l yc o m p e t i t i v ew i t ht h r e es t a t e o f - t h e a r tm o e a s ，i e ， n s g a ，s p e aa n dn p g a ( 5 ) t h ep r o p o s e dm o e oa l g o r i t h mi sa p p l i e dt oh a n d l i n gf o u rm e c h a n i c a lc o m p o n e n td e s i g np r o b l e m sr e p o r t e di nt h es p e c i a l i z e dl i t e r a t u r e t h ee x p e r i m e n t a lr e s u l t sd e m o n 一 英文摘要 s t r a t et h a tm o e oc a l lf i n dt h en o n d o m i n a t e ds o l u t i o n sw i t hg o o dp e r f o r m a n c ei nb o t h a s p e c t so fc o n v e r g e n c ea n dd i v e r s i t y t h er e s u l t sa l s os h o wt h a tm o e oi sh i g h l y c o m p e t i t i v ew i t hn s g a - i i ，s p e a 2a n dp a e s t h u sm o e oc a nb ec o n s i d e r e dag o o d a l t e r n a t i v et os o l v ee n g i n e e r i n gm o p s ( 6 ) t h em o e oa l g o r i t h mi sa p p l i e dt os o l v i n gf i v eb e n c h m a r ks t o c kp o r t f o l i oo p t i m i z a t i o np r o b l e m s i ti sd e m o n s t r a t e dt h a tm o e oi sh i g h l yc o m p e d f i v ew i t hn s g a i ia n d s p e a 2 ，a n ds u p e r i o rt op a e s a sac o n s e q u e n c e , m o e oi sa l le f f e e t i v em e t h o df o r d e a l i n gw i t hm o p si nt h ef i e l d so fm a n a g e m e n t sa n dd e c i s i o n m a k i n g k e yw o r d s ： e x t r e m a lo p t i m i z a t i o n , 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 , e v o l u t i o n a r ya l g o - r i t h m , p a r t i c l es w a r mo p t i m i z a t i o n , n u m e r i c a lo p t i m i z a t i o n , p a r e t of r o n t , m u l t i o b j e c f i v e0 1 k n a p s a c kp r o b l e m s ，m e c h a n i c a lc o m p o n e n td e s i g n ，p o r t f o l i oo p t i m i z a t i o n v h 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名：监! 坠壁 日 期：衅年+ 月扯日 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名：髂! 臣蜀虫 日期：瑚年月撕 指导教师签名： 日期：碰年厶月妇 第一章绪论 1 1 极值动力学优化算法的研究现状 1 9 9 9 年，b o e r c h e r 和p e r c u s 提出了一种通用的、基于局部搜索的启发式算法一一 极值动力学优化算法( e x t r e m a lo p t i m i z a t i o n ，e o ) 【1 2 1 。该算法是从b a k - s n e p p e n 生 物演化模型( 简称b s 模型) 1 6 】发展而来。b s 模型通过演化，可以使整个系统表现出自 组织临界性( s e l f - o r g a n i z e dc r i t i c a l i t y ，s o c ) 【7 l 。自组织临界性是b a k 等人于1 9 8 7 提 出的研究复杂系统的重要概念。这一理论认为，多种内部组元相互作用的复杂系统 可以自主地达到一个临界状态，并维持在这个状态。在临界状态下，一个微小的扰 动会对大量数目的组元造成影响，造成“雪崩 现象。而组元改变发生的概率与组 元某一特征成幂律关系( p ( k ) k 吖) ，其中丁为可调节的参数，这种关系与初 始状态无关。e o 算法与大多数进化算法不同的是，它没有引入种群( p o p u l a t i o n ) l 拘概 念，也就是说只有单一个体( i n d i v i d u a l ) 或染色体( c h r o m o s o m e ) ，而个体内部的 组元为基因( g e n e ) 或基因片段。因此，个体的所有组元就构成了一个系统，可以 将其看成一个复杂系统，它也表现出自组织临界性。e o 算法总是选择当前个体中适 应度最差的组元及其相邻的组元进行变异，从而使整个系统最终演化到自组织临界 状态。这种演化机制被称为极值动力学机制( e x t r e m a ld y n a m i c s ) ，算法的英文名称 也是由此而来。e o 算法至今仍然没有正式的中文名称，为了将e o 算法与传统的对目 标函数求极值的优化方法相区别，本文作者根据e o 算法的极值动力学特性，把它称 为“极值动力学优化算法”。正是这种内在的极值动力学机制，使得整个系统不需 要调整任何参数，就可以演化到一个自组织临界状态，在该状态下，各种大小的系 统结构都会出现。e o 算法可以看作是对个体自身的自我完善，通过改变适应度最差 的组元，使得个体总是朝着最优的结构演化，大大加速了收敛的速度；同时，通过 改变与最差组元相邻的组元( 此处“相邻的组元”的含义是指有着相互作用关系的 两个组元) ，使得整个系统能够协同进化( c o e v o l u t i o n ) 。众所周知，模拟退火算 法( s a ) 是模拟系统处于平衡态的一种优化方法，与模拟退火算法不同的是，e o 是 模拟系统处于远离平衡态的一种优化方法，而现实世界中大部分系统都是处于远离 平衡态的，因此，对e o 算法展开深入的研究更具有现实意义。 e o 算法的特点是收敛速度快，局部搜索能力强，仅有一个变异操作算子，而且 无可调参数( 对于基本e o 算法) 或只有一个可调参数丁( 对于丁e o 算法) 。因此， 用e o 算法解决优化问题设计简单，容易实现。但是，e o 的发展历史尚短，理论基础 还不够完善，对e o 算法的收敛性缺乏理论分析和证明；其次，e o 算法中适应度函数 的定义对于加快收敛速度和找到全局最优解起着至关重要的作用，但是，对于不同 的问题，其适应度函数的定义都有所不同。因此，研究如何针对不同的问题来定义 合适的适应度函数也具有重要的理论意义。 由于e o 算法是从统计物理中发展而来的，所以最初关于e o 算法的文献大多数 发表在国际著名的物理期刊上，如物理评论专辑e ( p h y s i c a lr e v i e we ) 、物理评论 卜海交通大学博士学位论文 快报( p h y s i c a lr e v i e wl e t t e r ) 等等，故对e o 算法的理论研究和应用研究大部分局 限在物理学领域，还没有引起国际运筹学和进化计算界的广泛重视。因此，至今 研究e o 算法的文献并不多，但足，随着对e o 算法研究的逐渐深入，人们已经发现 其优越的局部搜索能力和快速收敛能力。在2 0 0 6i e e e 进化计算会议( 2 0 0 6i e e e c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n ，c e c 2 0 0 6 ) 上( c e c 是进化计算领域顶级会 议之一) ，一篇研究e o 算法的文献 1 7 1 被发表了。该文献通过比较e o 算法和蚁群算 法在动态组合优化问题中的应用，向人们展示了e o 算法强大的寻优能力，这说明 了e o 算法正在引起进化计算领域专家们的关注，相信在不久的将来，e o 算法将成为 国际进化计算界研究的新热点。 迄今为止，主要有以下三种改进的e o 算法： ( 1 ) 7 - e o 算法【2 1 。由于基本的e o 算法总是选择最差的组元进行变异，故在求解组 合优化问题中，算法比较容易陷入局部极值点。为此，b o e t t c h e r 不l l p e r c u s 在 基本e o 算法的基础上，引入了一个可调参数7 _ ，从而提出了一种改进算法一 一7 e o 算法，新算法在求解组合优化问题时不易陷入局部极值点。 ( 2 ) 通用e o 算法( g e n e r a l i s e de x t r e m a lo p t i m i z a t i o n ，g e o ) 算法i 1 0 8 ，- 0 9 。基本 的e o 算法是针对组合优化问题提出来的，对于数值优化问题不太适 用，g e o 算法是在7 - e o 算法的基础上进行改进的算法，用来求解数值优化 问题 1 0 8 1 ，并且已经比较成功地应用于若干工程优化问题【1 0 6 10 9 1 。 ( 3 ) 连续e o 算法( c o n t i n u o u se x t r e m a lo p t i m i z a t i o n ，c e o ) 算法 1 2 1 。c e o 算法由 基本的e o 算法和局部搜索策略结合而成，该算法对每次迭代得到的局部最优 解的邻域再进行局部搜索，这样可以提高最优解的精度，但是会延长搜索时 间，增加了计算成本。 另外，只有一小部分文献提出了将e o 算法和其他算法相结合的混合算法。譬 如，m e s h o u l 和b a t o u c h e 【1 8 l 将蚁群算法和7 - e o 算法相结合，提出了一种求解图像配 准问题的混合算法，该算法对蚁群算法产生的解再进4 步用丁e o 算法进行局部搜 索，从而可以得到更精确的解；c h e n 等人【1 6 1 将丁e o 作为变异算- 了引入到改进的遗 传算法，从而提出了一种求解约束组合优化问题的遗传e o 算法( g e n e t i ce x t r e m a l o p t i m i z a t i o n ，g e o ) ，并将该算法应用于生产调度问题。 目前，e o 算法已经被成功地应用于求解一些组合优化问题，如二分图【2 1 ，图 着色1 8 1 ，旋转玻璃( s p i n g l a s s ) 9 1 ，旅行商问题【1 5 1 ，可满足问题【2 0 】，动态优化【 1 ， 模式识男j l j 1 9 ，2 0 i ，信号滤波，分子动力学模拟【1 2 】，复杂网络【2 2 】，车间调度【m 1 等问 题。但是，国外对于e o 算法在数值优化【1 0 8 ，1 剜和多目标优化1 1 0 5 1 0 7 方面的研究并不 多，国内学者对e o 算法的研究更少之甚幢】。 1 2 多目标优化方法概述及其研究现状 在现实世界中，很多问题通常由多个可能相互冲突的目标组成，即在不降低一 种目标值的情况下不能任意提高其他目标的性能，因此只能在各个目标之间取均衡 一2 一 第一章绪论 后的结果。例如在购买小汽车时，人们既希望它的价格比较低，同时又希望它的性 能比较好，但是往往性能比较好的汽车的价格都比较高，因此，只能选择一个折衷 的结果。再如在设计新产品时，既要考虑是产品具有较好的性能，又要考虑使其制 造成本最低，同时还要考虑产品的可制造性、可靠性以及可维修性等性能，这些设 计目标的改善可能相互抵触，譬如好的维修性会引起可靠性的降低，因此须在这些 设计目标之间取一个折衷结果。这种多个目标在给定区域上的最优化问题就是多目 标优化问题( 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 s ，m o p s ) 。这里所谓的多目标优 化是指对多个子目标同时实施最优化。一般地，单目标优化问题的最优解可以清楚 地定义，但是多目标优化问题的最优解不能简单地定义，因为多目标优化的结果并 不是单个解，而是一组均衡解，即所谓的p a r e t o 最优解。不同目标之间采用均衡的思 想方法在决策过程中具有十分重要的作用。 1 2 1 多目标优化的基本概念 不失一般性，假殴本文讨论的都是极小化问题。所有极大化问题可以转换为栖 小化问题。一般地，多目标优化问题的数学描述如下1 2 3 】： 找到一个向量言= ( z ：，旌，) 使之满足以下m 个不等式约束： 和p 个等式约束 并最小化以下向量函数： q , ( - g ) o ，i = 1 ，2 ，m ， 如( 才) = o ，j = 1 ，2 ，p ， ( 1 2 ) f ( 7 ) = ( ( 7 ) ， ( 7 ) ， ( 才) )( 1 3 ) 式中才= ( z 1 ，z 2 ，z n ) q 是决策向量，每个决策变量鼢由上下界约束：如x i u i ，i = 1 ，2 ，n 。 m o p s 的本质在于大多数情况下各个子目标可能是相互冲突的，某子目标的改 善可能引起其他子目标性能的降低，即同时使多个目标均达到最优解一般是不可能 的，否则就不属于多目标优化研究的范畴。解决m o p s 的最终目的只能在各个子目标 之间进行协调权衡和折衷处理，使各个子目标函数尽可能达到最优。因此，m o p s 的 最优解与单目标优化问题的最优解有着本质的区别。为了正确理解m o p s ，有必要对 其解的概念进行定义。以下四个概念在多目标优化中是十分重要的 2 3 l 。 定义1 a ：p a r e t o 支配( p a r e t od o m i n a n c e ) ：称向量刁 = ( u 1 ，乱七) 支配 ( d o m i n a t e ) - g = ( v 1 ，v k ) ( 记为言一 才) ，当且仅当v i 1 ，后】：“t v ia ( 可 1 ，尼- ：吻 吻) 。 定义1 2 ：p a r e t o 最优( p a r e t oo p t i m a l i t y ) ：决策变量7 q 成为q 上的p a r e t o 最优 解( p a r e t oo p t i m a ls o l u t i o n ) ，当且仅当不存在才q ，使得- g = f ( 可) = ( ( - g ) ， ( 可) ) 支配育= f ( - g ) = ( ( 7 ) ， ( 才) ) 。 一3 一 上海交通大学博十学位论文 定义1 3 ：p a r e t o 最优解集( p a r e t o o p t i m a ls e t ) ：p a r e t o 最优解集b 由所有p a r e t o 最优 解组成，即p s = 7 q 卜1 j 可q ：f ( 可) f ( 7 ) ) 。 定义1 4 ：p a r e t o 最优前沿( p a r e t o o p t i m a lf r o n t ) ：p a r e t o 最优前沿p f 是p a r e t o 最优解 集r 在目标空间中的映像，即斥= f ( 彳) = ( f l ( - z ) ，厶( 言) ) 1 7 p s 。 由以上定义可见，所谓p a r e t o 最优解就是不存在比这个解方案至少一个目标更 好而其他目标不劣的解，也就是不可能优化其中部分目标而使其它目标不劣化。因 此，p a r e t o 最优解集里的元素就所有目标而言，彼此之间不需再进行性能优劣的比 较。 多目标优化问题的通用框架如图1 1 所示。图1 1 表明，在决策空间( d e c i s i o n s p a c e ) 中的p a r e t o 解集( p a r e t os e t ) 通过目标函数厂映射到目标空间( o b j e c t i v e s p a c e ) 中的p a r e t o 前沿( p a r e t of r o n t ) ；同样地，在决策空间中的近似p a r e t o 解集 ( p a r e t os e ta p p r o x i m a t i o n ) 也通过目标函数，映射到目标空问中的近似p a r e t o 前沿 ( p a r e t of r o n ta p p r o x i m a t i o n ) 。因此，寻找近似p a r e t o 解集是多目标优化过程的关 键，而多月标优化算法的输出结果是一组非劣解或近似p a r e t o 最优解集。 1 2 2 传统的多目标优化方法及其局限性 传统的多目标优化方法是将各子目标聚合成一个带权重系数的单目标函数， 系数由决策者来确定，或者由优化方法来自动调整。为了捩取近似p a r e t o 最优解 集，一些研究者采取4 i 同的系数来实施动态优化。常见的方法有加权法1 1 3 1 】、约束 法1 1 3 1 1 、目标规