（计算机应用技术专业论文）多准则满意优化方法及应用研究.pdf

西南交通大学颁士研究生学位论文第1 页 摘要 随着i p 网络飞速发展与普及，网络的优化设计交得越来越重要。其中， 如何在满足网络性能要求的情况下进行网络优化，建立起经济、高性能、可 靠的网络，已经成为网络优化设计豹一个重要方囱。传统翡优化设计强调优 化目标的“最优解”，然而，计算机网络的优化属于多约束、多目标的复杂优 化问题，遗絮是n p 完全潮题。要找到这类翊瑟的溅优解不仅计算复杂，旦 花费的时间过长，从而失去了实际应用的意义，有时甚至根本不存在所谓的 最优解。此外，在网络多目标优化设计中，各个优化目标之间的不可公度性 和矛盾性导致难以把多个优化目标简单归并为单个瞄标。针对上述问题，本 文提出用满意解代替最优解，用满意优化的理论来研究拓扑已l 知的网络优化 闷题。 本文主要研究了多目标满意优化方法相关技术，并结合多目标满意优化 方法的忍想提出了计算机嗣络多嚣标满意优纯方法。 本文的研究工作有以下3 个方面： 1 ) 分拆了最优化理论的些局限性，综遮了满意伉化的发展现状，深入系 统地研究了多目标满意优化问题，提出了计算机网络多目标满意优化模 型。将该模型作为优化方案的评价体系，采用遗传算法作为寻优化方案， 将这二者统起来形成了完整的计算机霹络多蟊标满意优化求解模型。 2 ) 将提出的计算机网络多目标满意优化方法用于计算机网络的容最和流量 分配的优佬设计闻透。，首先绘出了计舞梳网络审容量和流量分配润题豹 数学模型，然后设计了适合该问题求解的遗传算法，最后通过寻优得到 网络节点问的路由策路和各条链路容燕。逶过仿真试验，表明了本文提 出的方法收敛快，稳定性高。 3 ) 将提出的计算机网络多县标满意优化方法用予o s p f ( o p e n s h o r t e s tp a t h f i r s t ) 链路权值的设麓问题。在综合考虑链路利用率、报文丢失率、时 延与链路费用的基础上，建立了o s p f 链路权重优化的多目标满懑优化 数学模型，并结合遗传算法来寻优得翻各链路的权僮，然后弱掰传统的 i p 路由算法( 最短路径优先，o s p f ) 实现流量分配。通过仿真试验，表明 了该方法在均餐网络流量方预有良好的效果。 西南交通大学硕士研究生学位论文第1 i 页 关键词：网络优化设计，满意优化，遗传算法，o s p f ，流量工程，容量与流 量分配 西南交通大学硕士研究生学位论文第m 页 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dp o p u l a r i t yo fi pn e t w o r k s ，t h ec o n s t r u c t i o no f i pn e t w o r k sc a nb es e e ni ne v e r y w h e r eo ft h ew o r l d t h e r e f o r e ，t h es t u d yo f n e t w o r k so p t i m i z a t i o ni sb e c o m i n gm o r ea n dm o r ei m p o r t a n t t h ew a yt o o p t i m i z en e t w o r k s w i t ht h ec o n s t r a i n to fu s e r s r e q u i s i t i o na n dc o n s t r u c t e c o n o m i c a l h i g hp e r f o r m a n c ea n ds t a b l en e t w o r k sb e c o m e sa l le s s e n t i a lp a r to f n e t w o r ko p t i m i z a t i o nr e s e a r c h t h et r a d i t i o n a io p t i m i z a t i o nd e s i g nf o c u s e so n g e t t i n gt h e b e s t ts o l u t i o n ，b u tb e c a u s em o s tn e t w o r k so p t i m i z a t i o np r o b l e m i n v o l v em u l t i c o n s t r a i n ta n dm u l t i - c r i t e r i ao p t i m i z a t i o np r o b l e m ，t h et r a d i t i o n a l o p t i m i z a t i o nb e c o m e sa nn p - c o m p l e t ep r o b l e m t oo b t a i nt h e “b e s t ”s o l u t i o n n e e d sn o to n l yc o m p l e xa l g o r i t h m , b u ta l s oal o n gc o m p u t a t i o n a lt i m e t h e c o m p u t a t i o n a lt i m ec a nb e c o m es ol o n gt h a tt h ea l g o r i t h mc a n n o tb eu s e dt os o l v e t h ep r a c t i c ep r o b l e m s i nt h i sd i s s e r t a t i o n , ac o n c e p to fs a t i s f a c t o r ys o l u t i o ni s p r o p o s e dt o t a k ep l a c et r a d i t i o n a lo p t i m u ms o l u t i o n ，aa p p l i c a t i o nm e t h o do f s a t i s f a c t o r yo p t i m i z a t i o ni sp r o p o s e dt os t u d yn e t w o r k so p t i m i z a t i o np r o b l e m s w h i c h t o p o l o g yi sg i v e n t h i st h e s i sf o c u so nt h e s t u d y o fs a t i s f a c t o r ym u l t i c r i t e r i ao p t i m i z a t i o n m e t h o da n dr e l a t e dt e c h n o l o g i e s a n dan e wm e t h o do no p t i m i z a t i o no fc o m p u t e r n e t w o r kb a s e do ns a t i s f a c t o r ym u l t i - c r i t e r i ao p t i m i z a t i o ni sp r o p o s e d t h et h e s i sm a i n l yd i s c u s s e st h ef o l l o w i n gp r o b l e m s ： 1 ) t h el i m i t a t i o no ft h et r a d i t i o n a lo p t i m u mt h e o r yi sa n a l y z e d t h ep r e s e n t s i t u a t i o no fs a t i s f a c t o r yt h e o r ya n d s a t i s f a c t o r yo p t i m i z a t i o na r es u m m a r i z e d s a t i s f a c t o r y m u l t i c r i t e r i a o p t i m i z a t i o n h a sb e e ns t u d i e d d e e p l y a n d s y s t e m a t i c a l l y a n d as a t i s f a c t o r ym u l t i - c r i t e r i a o p t i m i z a t i o n m o d e li s e s t a b l i s h e d t h i st h e s i su s e st h i sm o d e la st h ee v a l u a t i o n s y s t e mo f o p t i m i z a t i o ns c h e m e ，a n ds e l e c t sg a ( g e n e t i ca l g o r i t h m ) a st h es e a r c ht o o l t os e a r c ht h ep o t e n t i a lo p t i m i z a t i o ns o l u t i o n t h ee v a l u a t i o ns y s t e ma n dg a a r eu n i f i e di n t ot h es a m ea r c h i t e c t u r et ob e c o m ea c o m p l e t es o l v i n gm o d e l o f s a t i s f a c t o r ym u l t i c r i t e r i ao p t i m i z a t i o n t h ep r o p o s e dm u l t i c r i t e r i ao p t i m i z a t i o nm o d e li su s e dt os o l v et h ec a p a c i t y 西南交通大学硕士研究生学位论文第1 、，页 a n df l o wa s s i g n m e n tp r o b l e mo fc o m p u t e rc o m m u n c a f i o nn e t w o r k s f i s t , a m a t h e m a t i cm o d e lo f c a p a c i t y a n df l o w a s s i g n m e n t o f c o m p u t e r c o m m u n i c a t i o nn e t w o r k si sd e s c r i b e d s e c o n d ，as u i t a b l eg aa l g o r i t h mi s d e s i g n e dt os o l v et h i so p t i m i z a t i o np r o b l e m a n dr o u t i n gs t r a t e g i e sb e t w e e n n o d e sa n dl i n k sc a p a c i t ya l eg e tb yo p t i m i z i n g s i m u l a t i o n sa r em a d eo n s o m e e x a m p l e s r e s u l t s o fs i m u l a t i o nd e m o n s t r a t et h a tt h ep r o p o s e d m u l t i c r i t e r i as a t i s f a c t o r y o p t i m i z a t i o nm e t h o dh a s af a s t c o n v e r g e n c e s p e e da n dg o o d s t a b i l i z a t i o n ， 3 ) 秘l ep r o p o s e dm u l t i c r i t e r i ao p t i m i z a t i o nm o d e li sa l s ou s e dt os o l v et h e p r o b l e mo fo s p f l i n kw e i g h to p t i m i z a t i o n o nt h eb a s i so fc o m p r e h e n s i v e c o n s i d e r a t i o no fl i n ku t i l i z a t i o n , p a c k e tl o s s r a t e ，d e l a ya n dl i n kc o s t ， m u l t i c r i t e r i as a t i s f a c t o r yo p t i m i z a t i o nm a t h e m a t i cm o d e lf o ro s p fl i n k w e i g h to p t i m i z a t i o ni sc o n s t r u c t e d a n das u i t a b l eg a i sd e s i g n e dt os o l v e t h i sp r o b l e m t h e nat r a d i t i o n a lm r o u t i n gm e t h o d ( o s p f ) i su s e dt oa l l o c a t e t h ef l o wo v e rl i n k s r e s u l t so fs i m u l a t i o n sd e m o n s t r a t et h a tm u l t i - c r i t e r i a s a t i s f a c t o r ym e t h o dc a nb a l a n c en e t w o r k 孙a 纛d i s t r i b u t i o na n di m p r o v et h e t o t a ln e t w o r kt h r o u g h p u t 。 i ( e yw o r d s ：n e t w o r ks a t i s f a c t o r yd e s i g n , s a t i s f a c t o r yo p t i m i z a t i o n , g e n e t i c a l g o r i t h m ，o s p f , t r a f f i ce n g i n e e r i n g , c a p a c i t ya n dt r a f f i c a s s i g n m e n 西南交通犬攀硕士研究生举位论文第1 页 。 研究背景 第1 章绪论 j 睫年来，口网络飞速发展与普及，网络的建设与升级速度越来越快。在 这耱罄最下，弼终懿侥纯设谤交缛越来越重要。瓣终蕊纯浚诗阂鬈，霹叛缨 分为两个方面网络的设计期优化与运行麓优化网络的设计期优纯蹙针 对骨干网的规划设计，即在给定结点的情况下，设计一个包含这些结点拓扑 霪，势达到用户需求的可靠性拓羚结构确定之后，就要确定任意两个绪点 静路蠢方案，任意一条链路的容爨大夺，使褥该骨干瓣甄鸯较高的往熊( 平 均时媳，全网利用率等) ，又有尽可能低廉的建造费用。网络的设计期优化问 题通鬻属于n p 完全问题。本文研究网络拓扑已知情况下的网络优化问题。 贯方嚣，蘧馨瑶弼承载戆照务越来越多，臻夤予两主静流量惫凝灌 加。憾是传统的礤路由方法不能对流量进行含理的分配，因此，网络的某些 链路肖可能出现拥豢而同时其他链路未被充分利用。为了更充分利用资源和 提供戛好熬骚务，鬟要对流量遴学会理遗分懿，这一过稳称为滚量工羧删。 现有流量工程方法在撑阏弓l 入面向链路的技术，其中主要是m p l s ( m u l t i p r o t o c o ll a b e ls w i t c h i n g ) 协议和口o v e r - a t m ( i p * o v e r - a s y n c h r o n o u s t r a n s f e rm o d e ) 网络架构团。这炎方法在理鲻边缘节点间建立显式路径，使 鼹径绕遗巍塞嚣域，获瑟实褒滚爱憨分配。这类方法懿麦簧浃錾是存褒掰壤 的“n 平方”问题，即当网络节点数较多时，计算显式路径需要庞大的计算 量【2 】。 懿 鼙实现网络浚塞兹动态嚣求，蒡保证瓣络各毪毙攒糠符合用户要求， 是目前有待解决的阀题。通过逡警配置各链鼹的权值，剩用传统的i p 鼹出算 法可以实现流量分配。通过恰当的算法来设鬣权值，实现网络负载均衡，并 且网络性能接近最偬流量分配下的性能，这怒一个多目标、多约束的优化翊 嚣，瘸子n p 完全秘蘧翻。 西南交通大学硕士研究生学位论文第2 页 1 。2 网络优化的研究现状 属于设计期的骨干网优化，以往的研究大多是把该问题分为两个子问题 来解决，即在路由固定的条件下确定链路容量分配问题【4 】；在链路容量固定 的条件下确定路由选择的问题【5 1 。但是，报文的路由选择是与链路的容量有 关的( 容量的大小又与费用有关) ，也与报文到达率有关。所以最佳的结果应 同时考虑路由选择和容量分配这两个问题。g a v i s hb 和n c u m a ni 1 6 j 曾经研 究过这个离散链路选项和非分叉流量下问题的非线性数学模型。模型的目标 函数是总的设计代价最小，代价包括容量安装费用、网络时延引起的惩罚费 用等。他们的解决方法是基于次剃度优化技术的拉格朗日松弛法。通过对容 量限制进行松弛，拉格朗日问题可以分解成两个子问题：路由问题和容量分 配问题。后来，g a v i s h 和a l t i n k e m e r 对g a v i s h 和n e u m a n 的方法进行改进， 当需要的时候再产生可行的路由。a m i r i 和p i r k u l 报告了一个新的公式，利 用流守恒公式( f l o wc o n s e r v a t i o ne q u a t i o n s ) 来代替g a v i s h 和n e u m a n 公式 中的路径流。a m i d 和p i r k u l 考虑了时间变化的业务条件下的问题，将问题 扩展为多时间间隔的情况。 上述的所有方法考虑的都是链路容量离散的情况。l c b l a n c 和s i m m o n s 研究了连续链路容量选择时的网络设计问题，使问题的解决真正交得容易。 b i e n s t i c k 和g u n l u k 、b i e n s t o c k 等研究了在分叉情况下问题的多面体结构。 在最近的研究中，通过采用分枝割集算法，成功地对一个”个节点和7 0 2 个商品流的问题进行了优化设计。 容量与流量分配问题的一个变种是容量扩展问题。s t o e r 和d a m 考虑了 适存性条件下的容量扩展问题，即通过增加链路容量，使网络在即使节点或 链路失效的情况下也能够传送给定的业务。 近年来，智能算法，例如模拟退火算法m ，遗传算法 s l ，蚁群算法【9 】，神 经网络【1 0 】等，这些算法在解决n p 完全问题方面表现出较之传统方法高得多 的效率。国内学者叶大振【1 1 】、何翠红【1 2 1 等采用遗传算法来解决骨干网优化问 题，取得了较好的结果。 但是，不管采用哪种方法，都面临这样一个问题：随着拓扑结构的复杂 西南交通大学硕士研究生学位论文第3 页 证，繁轰数嚣熬增多，诗算量会遨速飙舞，蕊黛怒蓬7 大爨聚能承受熬凝羧， 从而使优化本身失去其工程意义。在这种情况下，追求一个最优化解变得毫 无意义了 戴外，骨于嬲设诗不仅要考虑到网络造价豹经济性，述要考虑到嬲络性 能是否符舍用户的簧求。 ；圭往盼研究串，并没有考虑骛这点。对于网络的 设计，既经济的造价，又有较高的网络性能才是恰到好处的设计。 关于o s p f ( o p e n s h o r t e s t p a t h f i r s t ) 链路投重的设置，在近期的研究中， 臻究者提出通过逶溺箍置备羲鼹瓣权篷，可戳蘩蘑簧绞戆瓣貉交算法滋蕊 路径优先，o s p 聊嶷现流量分配i ”j 。这类方法的显著优点怒容易实现，成本 低。文献【1 3 】给出这类方法实现的框架。文献【3 ，1 4 ，1 5 提出一系列的具体权值 配置方法，文鼓【1 4 】豹实验结果擞示当投篷选择恰当对，潮络性能接近羧优 流量分配下的性髓。这类算法嚣前仍存在一些待解决的睡霹。首先，文献【3 ，1 4 】 证明了当实现最优流量分配和权值设置时，流爨非零的路径一定是最短路径。 但是，其逆不一定成立，所以利用传统的“墩短路径优先”算法得到的路径 不一定莛最霞路径。其次，实舔鬻终虢滚萋鬟求是动态豹，需求嚣改交簧求 权值被重新设置。每一个权值的改变都需要修改各个路由器的路由表，从而 在网络中引起额外的流量。因此，当需求改交时，要求在网络满足一定性能 螽薅下尽哥戆避兔惨致毅毽。瑰蠢研究还不麓缀好逸辫决这个趣题。 1 3 满意优化发展现状 1 9 7 8 年，诺贝尔经济学奖获褥者h a s i m o n 在经济缀织实际决策静磷究 中，酋先提出了“令人满意准则”的概念来代替微观经济学的最大化原则， 同时摁如了用满意决策代替最优决策的思想【堋。他用个缀形象的例予来说 餮满意簿豹霞越攥：在建至祷纛张。絮果要找一令最大豹漾来是缀蠢鼹瓣， 需要搬地里所有的疆米都测量一下，再加以比较才能确定。并且，这个闯题 的工作量和玉米地的面积成正比，面积越大，工作越困难。但是，如果簧求 找到熬不是最大麴邸一令玉寒，嚣是一个比较丈豹，郅按邋鬻豹说法，爨遗 里去摘一个大玉米，闻题就苘革多了这霹，土地面积大小甚至和工俸爨基 本无必【懈。 西南交通大学硕士研究生学位论文第4 贞 锓警教授善先鬃薅模鞫数学豹知谖，将瀵意簿集定义势莱一论域在约素 条件构成的子集的限制下所形成的截集。提出了采用模糊集合论的方法来研 究满意解集【”i 。 上 婕纪9 0 年代，颧蕃教授遥过耪：较v o nn e u m a n n 诗算桃与人弦的终擒特 点，遨转梳制蜃发糯，入脑之所黻在高级信意处理方面远魏过电脑，囊婺有 两个因豢：( 1 ) 人脑的巨型并行分布结构；( 2 ) 人脑遵循浔求满意解的运算 法则。由此，靳蕃教授提出了“神经计算的满意解原理”i 切 嚣凑交逶大学懿金薅东教授磷究了译徐滚意解毪链豹满意疫函数，锋对 复杂问题提出了“多目标满意优化模型”和“局部全局溅满意优化横型”， 并将它们用于控制器参数设计以及列车操纵优化方法研究中【1 8 1 嚣求满意解的满意馋化方法乏掰戳可以褥裂迅速发矮，主要是嚣为宅其 有良下凡方面特点l 瑚： ( 1 ) 满意优化方法具有人类智能信息处理方式的基本特征之一，即在巨 大的搜索空间中迅速地找到满意解的能力。 露 传统往纯穷法采矮蘧述游嚣翡数学搂邃。嚣隽壤整零麦是实辩游惩 的简化，或多或少忽略了一些因潦。另外，数据采集的不精确以及参数估计 的不准确都可能导致得到的“最优解“比采用满意优化方法得到的满意解产 生静谈蓑更丈。 ( 3 ) 对于一些计算复杂程度较大的优纯阏题，现在并来找到行之裔效的 最优化方法，但是浆用某种按满意解原则所设计的满意优化方法却能得到满 意的优化效果。 1 4 网络多目标满意优化方法的提出 袄l 。2 参节熬分耩霉絮，瓣络优弦羯题，无论是设谤麓缆纯阖蘧逐燕运 行期优化问题，都属于多参数，多约束条件的n p 完全问题。传统的以求最 优解为目标的优化方法在解决网络优化问题时，会遇到计算时间过长，最优 解难墩求出魏困境。越羚，鼹终戆动态佳镬缮获褥网络莱鞋劐豹精确缝毙 指标黛褥很困难，在这种情况下，追求“最优”本身就失杂了意义。本文采 用满意优化方法并结合遗传算法的强大并行搜索能力来解决网络优化问题。 西南交通太学硕士研究生举位论文第5 贞 分爱纛瓣缮容量窝浚囊分琵每o s p f 链路投鬟浚萋秀令秀麟避霉7 该方法豹 应用研究。 猩骨干网的优化设计中，本文不以最优解为第一追求豳标，而是从正程 实际趱发，追求一个决策者认为“满意”豹瓣。也就是说，刿敬鼹络熬筵设 计方素的好坏，不怒它是否最谯( 事实上，大多数情况我们也难班掌摄豢优 解) ，而是其落在了正程实际限制以内的程度。程度越高，则该分配方案( 解) 的质爨越高。决策帮完全可以爨化这种程度，当决策者认为某个解足够好， 。滚懑8 了，寻往避程帮虿绩泵。 评价解的标准从实际出发，以入们的需求为导向，设灏简单、灵活。在 使用遗传算法进行碍优过程中，找到令人“满意”的解的概率很大，这就加 抉了爨法豹投敛速发，扶嚣有效蟪缓解了嚣潮终援模增大蛰寒静“计冀爆炸” 闯题。 一 本文建立了同时考虑费用、全网平均时娥以及全网利用率的多目标满意 优化模型，作为评价某个设计方案的评价体蓉。分别建立了费用、对延以及 纛焉攀豹满意度羲数，逶过线黢蕊投豹方法将逸三令嚣臻戆满意度综会为一 个满意度，作为设计方案的最终评价结果。镪个目标的权值代表该目标在总 体目橼中所占的比熬，权值可由模糊数学中的层次分析法分析得到。同时， 竣诗了逶焉手夤予瓣毯纯豹遗费舞法，著将综合漾意度嚣数终为逮转冀法个 体的嗣标函数，个体的目标值代袭了个体静综合满意废，确保个体的霸标值 越大，其适应度越黼。 对于o s p f 链鼹权重优化豹设计，本文撼如了月满意躺代替最优髂黝方 法。遴过弓l 入满意凄嚣数，使褥设誊多鳕束约o s p f 链蘧投篷残轰霹簸。零 文以网络各性能指标( 链路利用率、时延、费用、丢包率) 为目标，建立了 相应的多目标满意优化模型。以用户提出的备网络性能指标要求为基准，分 裂建纛了耋夔瀵爨凌丞数。数楚荸、会瑗梵丞数设谤覆粼，霉逶过线缝麓 权的方法，得出整个网络性能指标集合的综禽满意度，使得我们不必为了衙 化而省略重要的网络性能指标参数。 隧撵这，本文设计了适合o s p f 链路权熬设计豹遗传黧法，将综会满意 度俸为释群孛个体翡蠢标函数氆，阕样确保瓣标函数值越大，个体的瀵藏度 越高。由于寻找的是满意解，所以搜寻的时间可以大大缩短。此外，聚用本 西南交通大学硕士研究擞学位论文第6 贞 支夔求疑模型，霹淤在确保弱终爨戆熬蓑提，戆蛙蘧实凌流量憨麓囊分毒。 1 5 本文的组织结构 本义主要将满意优化理论廒掰到霹络静优化设计中，论文分为5 章，分 别介缁如下： ( 1 ) 第1 章为绪论，简要介缨了计算机网络优化设计的研究现状，龋述 了采麓传统最饶纯穷法所透到静溺难。蘧螽露满意饶纯酶概念骰了篱要说疆， 并介绍了满意优化壤论的发展现状。最后提出了以满意优化代替最优化的方 法，弗将其应用在骨干网优化设计以及o s p f 链路权重设计的研究中。 国第2 章较详缨建套缨了满意甓纯理谂，绘窭7 潢懑菠与瀵意勰魏定 义，介绍了几种常用的满意度函数的形式。同时，介绍了满意优纯问题的求 解步骤，最后提出了多目标满意优化问题以及其数学模型的一般形式。 ( 3 ) 第3 章奔缨了适用于嬲络寻优的多臻标满意优化模型，考虑翻遗传 算法麓强大荠霞搜索能力，蒋遗传算法与两绦多蟊标满意优耽方法福臻合， 形成了种完整的针对网络多目标优化问题的一般性求解模型。 ( 4 ) 第4 章将多目标满意优化方法用于计算机网络容蹙和流量分配的优 亿竣谤，霆霹寻求建造慧费曩、金薅平筠跨楚叛及全网裂翅率这三令攒辕戆 满意解。将多目标满意优化方法嵌入到遗传算法的目标函数计算环节。并将 本文第4 章提出的方法与基于p a r e t o 排序的多目标优化方法进行了比较，计 算绪皋表臻本文羼瘸豹方法其骞更裹豹效率秘更稳定豹收敛速疫。 瀚第5 章将多嚣标满意傀纯方法震予o s p f 链鼹较熬设置。o s p f 链路 权重设置问题实质上是给链路分配适当的权假，使网络中的各节点根据链路 权值来寻找最优路绦，从而实现网络的负载均衡。为此，本文第5 章建立了 o s p f 链路蔽重设爨豹滚意魏识模型，竣谤了穗应獒遗传舞法磊予援索疆久 “满意”的链路权踅组合。最厢，通过与其它设置算法进行比较，表明本文 第5 礅提出的方法既有较高的效率又能较好地均衡网络负载。 西南交通大学硕士研究生学位论文第7 页 第2 章满意优化方法 满意优化方法( s a t i s f a c t o r yo p t i m i z a t i o n ) 是相对于最优化方法提出的。 它是在人类智能准则的基础上形成的，以满意解( s a t i s f i e ds o l u t i o n ) 输出为 原则，在一个可以接受的计算费用内寻找满意解的一类优化方法【l s l 满意优 化问题与满意解和通常的优化问题及最优解有很大区别，尽管在实际应用中 常用“满意解”来代替最优解，但此时的满意解是在传统优化原理的基础上， 通过牺牲求解精度及降低收敛条件而得到的。而在满意优化问题中，其所求 得的满意解就是该类问题所追求的目标所在。同时其寻优准则也与传统的优 化问题有很大区别。通常是以性能评价体系及满意度函数来对满意解的性能 进行评价。 本章首先给出了满意优化方法的一般定义，提出了满意优化方法的运行 框架。通过分析传统的满意解与满意度函数的定义，介绍了几种不同的满意 度函数及多目标满意优化方法。 2 1 满意解原则和满意优化方法的运行框架 通过分析人类的智能活动可以发现1 1 7 1 ：输入信息的模糊性以及输出信息 的满意性是其主要的特征。研究人类的信息处理中枢大脑，我们发现， 脑神经处理了外界输入的信息以后，会产生支配身体各部分做出相应反应的 决策，这些决策大部分都是能解决问题的满意决策，而并非最优决策。这主 要是因为：( 1 ) 为了能在同一时间处理多种信息。例如，我们骑自行车的同 时，可能要与同伴交谈，同时还要观赏道路两旁的风景。( 2 ) 为了能集中精 力处理问题。例如，骑车时遇到了一段凹凸不平的路面，我们就希望在这一 段路上找出一条较平整的路线前进。由于我们的目的是通过这一段路，因此 我们没有必要下车来仔细测量路面，找出最平整的路面来。( 3 ) 为了能够对 各种情况进行实时反应。例如，骑车时由于颠簸突然摔倒，与此同时我们肯 定会做出一系列的自我保护的反应，而在这么短的时间内还要决定怎样做这 西南交通大学硕士研究生学位论文第8 页 些动臻方最省力、簸安全或者最敏捷，是擐本苓毒戆，氇怒没毒登要戆。 综上所述，人类高级智能活动的特点不在追求凡事得剿最优解，丽楚实 时地熊随机应变地求得可以解决所面临问题的满意解【1 8 l 。藏是这一条稽起来 十分平凡静满意解原则，搜褥人类在各耪驾戆信息处理的泼动中可以极大静 节省傣怠楚理的对蠲璐及信息存储豹空闻，从两提高效率。 j 躐过对满意解原则的分析，本文给出了种满意优化方法的一般寇义。 定义2 a ：满懑优化方法是谯一个可以接受的计算费厢内寻找满意解的 往纯方法，瑟显该浇意鼹与最钱瓣熬穰差不定虿j 毳。 根据优化问题的不同类型以及所采用的不同策略，就产生了不同形式的 满意优化方法。但照其基本的运行框架是相同的图2 - 1 给出了这一类满意 往纯秀法豹基本运移框图。 图2 - 1 满意优化方法的纂本运行框图 通过对满意优化方法基本远行框图进行分析，不难看出，在实际威用中 所采耀熬一些优化方法实际上怒采用满意孵原则豹满意优化方法。例如，在 模 萎l 这尔文的逮褥选择纛生匏过程蠡然海汰鹃遗传算法瓣审，就是在攘索过 程中利用评估函数( 适应值函数) 计算得到解的适应度假，将它作为评估个 西南交通大学硕士研究生学位论文第9 页 体或解的优劣标准。我们不妨将这里的适应度函数看成是一种以满意解原则 而设立的满意度函数。又例如，利用具有反馈的全互连h o p f i e l d 型神经网络 求解t s p 问题时1 2 2 ，则是在满足一定参数条件下，使用计算能量函数 ( c o m p u t a t i o n a le n e r g yf u n c t i o n ) ，求解在一定约束条件下的优化问题。此时， 计算能量函数也可以作为相应的满意度函数，以求得问题的满意解。 2 2 满意度、满意解的基本定义 在研究满意优化问题时，首先应该明确什么是满意解，怎样评判满意解 令人满意的程度。优化问题的可行解集中性能指标最好的一个解就是问题的 最优解。而问题的可运行解集中所有性能指标都令人满意的解就是满意解。 显然，满意解应该是一个集合，通常称为“满意解集”。 从数学描述的角度来讲，判断一个解是否是最优解是确定的，而判断一 个解是否属于“满意解集”与主观因素有关，因而它的范围是不确定的，具 有一定的模糊性，属于f u z z y 集，可用模糊数学的原则和方法进行分析首 先对满意解进行定义的是暨南大学的任平教授，他用模糊数学的方法讨论了 h a s i m o n 提出的“令人满意准则”的概念，给出了如下关于满意解与满意 度的数学描述【1 q ： 。 设论域u 为全体可行解集合，v 为目标值集合，考虑u 到v 的一个映 射： ，：u y ( 2 1 ) 定义v 的一个f u z z y 子集g 为“满意”，其隶属函数定义为： 如：y 一【o ，1 】( 2 - 2 ) 对v e v ，鳓( v ) 简记为g ( v ) ，表示当目标值为v 时令人满意的程度。令c 为u 的f u z z y 子集，有： 定义2 2 对满足q - 妒，q 一尹的任一个a 值，0 a 1 ，称 m 。t l u c x ， ) 幺 为，在c 上的a 一水平满意解集。其中c 。、g 。分别 为c 与g 的a 一水平集，即： q - 蕾l “e u ，心 ) 乏a j ( 2 - 3 ) 殖南交通大举硕士研究生学位论文第1 0 页 g ；- 分l 矿y ， 鼻； 定义2 0 考虑c 上的一个f u z z y 予集m ，其隶属函数规定为： 藏妊) i s u p 盘， o 五l ( 2 4 ) ( 2 5 则称m 为，在c 上的满意解。这时，m ) 就是解u 的满意解。 饺平教授的满意解与满意度函数的定义反映了模糊性运一本质，而鼠是 篓豢严格熬，嚣我遗会予理论接嚣。毽麦子须扶嚣标集翻壤嚣论壤，嚣基震 要确定鬻信水平 ，计算复杂，所以作为实际应用并不适会。我们为了得到 一种具有普遍意义并且可以广泛适用的满意解和满意度函数的定义，参考文 献【1 8 】，给出了运髑意义上的满意解与满意发涵数定义。凝体描述及鞠关定 义鲡下： 定义2 4 设问题p x 的可行解集为x ，给定一映射，使得： ，：x _ d ；- f ( x ) 蠛o ，善盖 协6 ) 称映射，为性能评价准则，q 为，衡量下可行解集z 的性能指标集，q 为厂意 义下w 行解x 的性熊指标值。 其中，性能评份准则是在衡蹙一个解是磷是满意解的一个衡量标准或准 爱| j 。镄翔凌稍在第一章孛誊氆溺h a s i m o n 懿攘玉米静铡予来说弱灌意傀纯 原则，其中，要摘一个“大”孤米，首先必须有一个用以衡量玉米大小的标 准。那么这个用以衡量玉米大小的标准就是个用来评价藤米的性能评价准 羹| j 。 定义2 s 给定问题p x 的可行解善及性能评价准则，下酌髓能指标集q ，则 存在一个函数 ( ) ，构成映射： h ：q 一【o ，l 】 颤j 0 - j l 固r ) 一彦歹0 【) ( 2 - 7 ) 铲x e x ，q q , s 0 ) 【o l l 该映射确定了可行解集工的一个子集a ，称a 为x 在性能评价准则，下的满 意勰集，毛( 磅力x e x 在，意义下熬满意瘦，磊稳魏瞧缆译伶准裂，豹漾 意欧射黼数。 可行解集z 中在性能指标准则，意义下满意度最大的解的满意魔记为 西南交通大学硕士研究生学位论文第1 1 页 s 一( 移，满意度聂冬懿解兹瀵意发记秀s 。q ) ，麓 ：蓦二r 一面m 矗s ( 品x 鉴嚣 c 2 渤 $ m g ) 一) l x 石 7 定义2 6 绘定可行解集石的子集砖，即： 么一冬 s 国a 声盖( 2 ，9 ) 称为可行解集z 上的满意度为 水平的满意解集。 幽以上定义可以看出，性能评价准则的确定是一个客观过程，由网肖的 窖蕊瓣德爱决定，怒苓班太豹意恚为转移豹。瑟潢意黢射藕数豹确定裂氛含 着主躐因素，不同的评价者由予各自的专业知识或文亿背豢等不同而w 熊褥 到不同的满意映射黼数满意优化问题就是爵找满足一定袋件的满意解集， 丑的就是在集合中谬找一种满意子集，寻求的手段则是通过解的满意度袭现 整来。 除了用模糊数学的思想来意义满意度之外，也有用线性取值的方法来定 义满意度的。较早用线性取值的方法来定义满意度的是胡恩继教授。他在探 讨铁路运输谤楚摇令犍指标按缀淘获上委下羧麸下鬟主避弦分鼹兹方法瓣， 给出了如下满意度的定义1 2 l l ： 定义2 7 设五为指标数值，j 与疗分别为指标的最佳解和璇差解，则指标的 满意度为： q 髻一 ( 2 1 0 ) j t 。je 很显然，这个定义怒针对具体环境提出的。对于一般应用来说，很多情况下， 掰豹黢毪彝最差熬先验籍谖无默德絮。象戳，这耱定义垂孽邋蕉毪不强。 另外，靳蕃教授从模糊神缀计算智麓系统输出解樗一般性评定满意度的 需求出发，按照解的离散和连续性质，实时茅n 非实时要求，给出了几种不同 豹满懑度表示方法“”。 定义2 s 设离散瓣集x 试，毪， 为有效解集，对解黾毯盖翦菜静蘸能评 价用q ( x ；) 表示，定义子集 爿( 毪) - v x l q ( x ) 2 窖( 鼍) ，工毯篡)( 2 1 1 ) 赠当f n c i s 辕爨黪麓簿，它豹滚爨度定义秀 一掣小科 协必 西南交通大学硕士研究生学位论文第1 2 页 定义2 9 设( 鼋) 表示定义在一。t q 。s q s 吼 s 4 a ( 2 ) 升半r 一函妄 s ( d ) - 1 l l o , 一d e s 4 似a 。) ，d ，口，其中j 。 ( 3 ) 升半正态函数 s ( d ) 1 1 l o 一, d e s 4 似a 。p ，矗 4 ，其中七，。 ( 4 ) 升半阶梯函数 阻d 4 l 5 ( d ) - l 口p ，, 4 a 2 t p 口 。 o 4 一l 艟 图2 - 7 升半r 一函数 图2 - 8 升半正态函数 2 4 满意问题的一般求解步骤 ( 2 1 9 ) ( 2 - 2 0 ) ( 2 2 1 ) ( 2 2 2 ) o由ma l $ 图2 - 9 升半阶梯函数 满意问题比最优化问题更具一般性，其典型的解题步骤包括问题识别、 模型建立、满意度设计、求解和评价等几个过程。如图2 1 0 所示。 西南交通大学硕士研究生学位论文第1 5 页 图蕾1 0 满意问题求解过程 ( 1 ) 满意问题的识别和归纳问题识别怒个对问题认知的过程，这一 除段，迄今为止还没有饪 哥蠡动纯豹决策支l 孝，霆为考察客鼹卷雾，谈翘一 个闻磁并描述出它麓轮廓是一释非结梅纯的灞动，需要自缀织输入大煮内部 和外部信息。可以说，怎样导出一个满意问题的推理过程怒很难进行表述的。 对不闼的问题可能采用不同的具体方式，丽计算机提供的支持只能停留在管 理壤惑系统瑟次上。1 ( 2 ) 满意问题的模型建立建立过程包括模型的选择釉模型的建藏两方 面内容。通常使用人工智能的一些方法、基乎范例的推理方法、基于神经网 络戆秀法等。在选撵建摸方法秘忑其熬弱聪，还嚣要一定建摸技巧羁对翅题 的其体分析。 ( 3 ) 满意度的建立满意问题处理过程中的一个重要环节就是建焱台理 的、能够反殃用户辩解的质量评价的满意度。满意度作为满意问题中的一个 基本攒念，其建立遗程遣菲标壤像，锋瓣不瓣豹瓣惩，霹；冀采用不同懿方法。 ( 4 ) 模型求解对那些纯粹的定量模型，般都有较为成熟的求解方法， 西南交通大学硕士研究生学位论文第1 6 页 因此只需要调用相应的求解方法及程序即可。对那些定量与定性相结合的模 型，可以考虑把人工智能和优化方法结合起来对模型进行求解，优化方法求 解定量问题，定性问题由人工智能负责解决。 ( 5 ) 求解结果的评估与应用问题求解结束后，就需要在若干个备选方 案( 或者说在问题的解空间) 中，选定一个( 组) 满意解。对满意问题求出 的解进行评价，是衡量求解质量的主要依据。得到求解结果之后，要对其合 理性与实用性进行评估与检测，如果能够通过，则求解结果便可投入实际应 用；否则，要回到模型设计阶段或满意度建立阶段，对模型进行修改或重新 设计。对求解结果的评估与检测需要用到专家的经验和一系列知识推理，因 此可以考虑使用专家系统对这一阶段进行支持。 2 5 多目标满意优化方法 在实际生活中，人们更多情况下所遇到的是一类多目标优化问题。例如， 在生产过程中，人们总是希望高产出、少用料、省工时；在网络优化设计中， 我们希望网络费用低廉、运行稳定可靠、性能强大等等。单目标优化问题则 可以看成是多目标优化问题的一种特例。因此，对多目标优化问题进行深入 的分析与研究就具有重要的意义【卅 2 5 1 多目标优化问题的提出 多目标优化也叫多指标优化或向量优化，可一般性地定义为在一组约束 条件下，极大化( 或极小化) 多个不同的目标函数，其向量化的定义为：寻 找一个由设计变量组成的向量，使它能够满足约束条件和由目标函数组成的 向量函数【叫。多目标优化的意义在于找到一个或多个解，使设计者能接受所 有目标值。 多目标优化问题的一般数学形式如下： y 一雪f ( 力。婴粤【 ( z ) ，2 ( n o o9 五( x ) r s j 9 1 ( x ) s0 ( ，一l 2 ，p ) ( 2 2 3 ) 吃0 ) 一00 - 1 ，2 ，口) 西南交通大学硕士研究生学位论文第1 7 页 式中，f o )