（计算机应用技术专业论文）基于多目标遗传算法求解steiner树问题.pdf

， ；， ，0，010_一二-o 0+， f 1j_1一j，i 、 ，o 。；差0；vr”二a“i、0f，矗羹f孙 at h e s i si nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y m u l t i o b j e c t i v eg af o rt h es t e i n e rt r e ep r o b l e m b yl u a nw e i s u p e r v i s o r - a s s o c i a t ep r o f e s s o rd i n gs h a h n o r t h e a s t e r nu n i v e r s i t y m o n t h m a y 2 0 0 8 如誊馥轧；燕r。0，b 0一。，硒h 0。， ，鬣敝蔷鬻罨滢；j；羲，。 侮馥鬻琴#“ j1 1， - 一 夸 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 0 白二 恩。 学位论文作者签名： 豇武 e l 期：撕男d 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年口 学位论文作者签名： 签字日期： 袤剖 导师签名： 签字日期： 、钆f h。r，0 ，#t*氩f驴i二 - h 气 东北大学硕士学位论文摘要 基于多目标遗传算法求解s t e i n e r 树问题 摘要 s t e i n e r 树问题是组合优化中的一个经典问题，它在很多领域得到了广泛应用和深入 发展。但当前对s t e i n e r 树问题的研究大都集中在单个目标上，即最终只需要达到一种 优化目标。而现实中需要解决的问题，往往不止一个目标，而是多个目标相互制约、影 响，由此提出了多目标的s t e i n e r 树问题，使s t e i n e r 树问题变成多目标优化问题。 目前有很多种解决多目标优化问题的算法，但这些传统的算法只是提供了一些不同 的途径，将多目标优化问题转化为单目标优化问题，然后采用较为成熟的单目标优化方 法来进行求解。其解决问题的基础仍是依赖单目标优化，往往难以得到令人满意的最优 解集。由于遗传算法内在的并行性，善于在全局范围内进行搜索，适用于解决多目标优 化问题。本文提出利用多目标遗传算法解决一种两个目标的s t e i n e r 树问题。 本文的算法中，s t e i n e r 生成树由贪婪算法计算，多目标遗传算法对每一代的个体搜 索其p a r e t o 最优解集，直到算法结束，最终得到一组p a r e t o 最优解，这些解包含了总体 开销和边数两个目标，使决策者可以根据喜好选取最适当的方案。为了证明算法的有效 性和先进性，测试了b e a s l e y 提供的b p r o b l e m 数据集，并选择了解决s t e i n e r 树问题的 三种经典算法进行了单个目标的比较，结果说明，本文的算法能搜索到单目标s t e i n e r 树的最优解，同时能搜索到多目标s t e i n e r 树的p a r e t o 最优解集。 关键词：多目标遗传算法；s t e i n e r 树；多目标优化；p a r e t o 最优；贪婪算法 一h 一 k 产 。缸几j 东北大学硕士学位论文 a b s t r a c t m u l t i 一0 b j e c t i v eg af o rt h es t e i n e rt r e ep r o b l e m a b s t r a c t s t e i n e rt r e ep r o b l e mi sac l a s s i c a ip r o b l e mi nc o m b i n a t o r i a lo p t i m i z a t i o n ，i th a sb e e n b r o a d l yu s e da n dd e e p l yd e v e l o p e di nm a n yf i e l d s c u r r e n t l y , t h es t u d yo fs t e i n e r t r e e p r o b l e ma l m o s tf o c u s e do no n eo b j e c t i v e ，t h a ti st oo b t a i no n l yo n eo p t i m i z a t i o no b j e c t i v e b u tt h ep r o b l e m sw ef a c e di nt h er e a lw o r l da r ea l w a y sn o to n l yo n eo b je c t i v e ，t h e ya l w a y s h a v es e v e r a lo b j e c t i v e sw h i c hr e s t r i c to ra f f e c to n ea n o t h e r s oak i n do fs t e i n e rt r e ep r o b l e m w i t hm o r et h a no n eo b j e o i v ei sp r o p o s e di nt h i sp a p e r ，h e n c es u c hp r o b l e mi st r a n s l a t e di n t o m u l t i o b j e c t i v ep r o b l e m ( m o p ) m u l t i o b j e c t i v ep r o b l e ms h o u l db ef o u n dan u m b e ro fs o l u t i o n s ，b u tt h e s et r a d i t i o n a l a l g o r i t h m sj u s tp r o v i d es e v e r a ld i f f e r e n ta p p r o a c h e st ot r a n s l a t et h em o p i n t os i n g l e o b je c t i v e p r o b l e m ( s o p ) ，t h e nu s et h er e l a t i v e l yp e r f e c ta l g o r i t h m sf o rs o p t os o l v et h ep r o b l e m t h e f o u n d a t i o no fs u c ha l g o r i t h m si sr e l i e do ns i n g l e o b j e c t i v eo p t i m i z a t i o n ，s oi t sh a r dt oo b t a i n t h es a t i s f a c t o r ys o l u t i o ns e te v e r yt i m e m o g ai sd e e m e dt ob eap e r f e c ta l g o r i t h mf o rm o p b e c a u s em o g ai si n t r i n s i c a l l ys u i t a b l ef o rp a r a l l e li m p l e m e n t a t i o na n dc a nf i n dt h eg l o b a l o p t i m u m o fap r o b l e mw i t hv e r yh i g hp r o b a b i l i t y i nt h i sp a p e r , am o g ai sp r o p o s e dt os o l v e ak i n do fs t e i n e rt r e ep r o b l e mw i t ht w oo b j e c t i v e s i nt h ea l g o r i t h mo ft h i sp a p e r ，t h es t e i n e rs p a n n i n gt r e ei sc a l c u l a t e db a s e do fg r e e d y a l g o r i t h m ，t h em o g aa p p r o a c hp e r f o r m sa s e a r c hf o rp a r e t o o p t i m a ls e ta n de v o l v e st h e mi n e a c hg e n e r a t i o nu n t i lt h ea l g o r i t h ms t o p s i nt h el a s tg e n e r a t i o n ，ap a r e t o o p t i m a ls e ti sf o u n d t h e s es o l u t i o n si nt h es e tp r o v i d ee n o u g hi n f o r m a t i o no ft r e ew e i g h tc o s ta n de d g en u m b e r f o rd e c i s i o nm a k e rt oc h o o s et h eb e s tw a y i no r d e rt o p r o v et h ea l g o r i t h mr o b u s t ，t h e b - p r o b l e ms e tf r o mb e a s l e y i st e s t e d t h r e ec l a s s i c a la l g o r i t h m sf o rs t e i n e rt r e ep r o b l e ma r e u s e dt ob ec o m p a r e di ns i n g l eo b j e c t i v e f r o mt h ee x p e r i m e n t a lr e s u l t s ，t h ea l g o r i t h mc a nf i n d t h eo p t i m a ls o l u t h i no fs i n g l e o b j e c t i v es t e i n e rt r e e ，a n di tc a na l s of i n dt h ep a r e t o - o p t i m a ls e t o fm u l t i o b j e c t i v es t e i n e rt r e e k e yw o r d s ：m u l t i - o b j e c t i v eg a ；s t e i n e rt r e e ；m o p ；p a r e t oo p t i m a l i t y ；g r e e da l g o r i t h m l i i 一 _。研v ，藩0 。产卜 - k ，协 、： 东北大学硕士学位论文 目录 目录 声明l 中文摘要1 i a b s t r a c t i i i 第1 章绪论。1 1 1 问题背景。1 1 2s t e i n e r 树问题概述2 1 3 遗传算法和多目标遗传算法概述3 1 3 1 遗传算法概述。3 1 3 2 多目标遗传算法概述。4 1 4 本文主要研究内容及章节安排5 第2 章s t e i n e r 树问题和多目标优化问题7 2 1s t e i n e r 树问题的定义7 2 2s t e i n e r 树问题的启发式算法7 2 3 多目标优化问题简介1 2 2 3 1 多目标优化问题的产生、发展及应用王2 2 3 2 多目标优化问题的模型、基本概念。1 3 2 3 3 多目标优化算法简介1 6 2 4 本章小结1 8 第3 章多目标遗传算法1 9 3 1 遗传算法基本概念和基本理论1 9 3 1 1 遗传算法的产生与发展1 9 3 1 2 遗传算法的基本操作2 0 3 1 3 遗传算法的一般流程2 2 3 2 多目标遗传算法基本理论2 4 3 2 1 多目标遗传算法一般流程2 4 3 2 2 多目标遗传算法常用策略2 4 3 3 多目标遗传算法分类2 6 3 3 1 按不同的选择机制分类。2 6 3 3 2 按不同的决策方式分类2 8 3 4 多目标遗传算法的研究现状2 9 3 5 常见多目标遗传算法简介。2 9 3 6 本章小结3 2 一一 东北大学硕士学位论文 一 掺 f ： 目录 第4 章基于m o g a 求解s t e i n e r 树问题3 3 4 1 问题描述3 3 4 2 算法流程3 5 4 2 1 编码3 5 4 2 2 初始化3 7 4 2 3 平价3 8 4 2 4 选择4 0 4 2 5 交叉4 1 4 2 6 变异4 3 4 2 7 区别相同个体4 5 2 8 检查生成树4 6 章小结4 8 章实验与结果4 9 法参数4 9 验方法4 9 验结果5 2 章小结5 5 章总结与展望5 7 文献5 9 诩! 6 1 一v 一 。o卜p j 知 t k 东北大学硕士学位论文第1 章绪论 1 1 问题背景 第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 np r o b l e m ，m o p ) 却没有高效实用的解决方法【1 】。然而现实世 界中的多数优化问题都涉及多个目标的优化，而且这些目标通常不是独立存在的，它们 往往是融合在一起且处于相互竞争状态，每个目标有不同的意义和比重，它们的竞争和 复杂性使得对其优化变得十分困难。 在现实生活中，人类改造自然的方案规划与设计过程总体上反映了“最大化效益， 最小化成本 这一基本优化原则，在合作对策问题中如何求解最优策略以获得共赢目标， 在竞争对策问题中如何使得自己的利益实现最大、对方的受益最小，以及控制工程中的 稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问题等，实际上都是多 目标的优化问题，因此多目标优化问题在现实世界中随处可见，所以对多目标优化问题 的研究成为个引人注目的研究领域，具有一定的现实意义。 s t e i n e r 树问题是组合优化中的一个经典问题，它在计算机通信领域的多播路由、无 线传感器网络、网络全局优化等方面得到了广泛的应用和深入的发展【2 1 。当前对s t e i n e r 树问题的研究大都集中在单个目标上，即最终只需要达到一种优化目标。许多研究考虑 到了带约束的s t e i n e r 树，即在对单一目标进行优化的前提下，限制了一些目标节点的 取值范围，如带时延约束的多播路由等，但即便这样，这个问题仍然是一种单目标优化 问题。本文考虑的是一种两个目标的s t e i n e r 树问题，即要找到这样一棵s t e i n e r 树，它 在保证一个目标尽可以最优的情况下，另一个目标也要尽可能最优。对应于现实中的问 题，可以考虑要找到一棵多播树，这棵树的造价要尽可能低，而树中包含的节点要尽可 能少，因为信息在网络中传递的过程中，所经过的节点越少，出现错误的机率就会越少。 因此，这项研究是很有现实意义的。 对s t e i n e r 树问题的研究已经有了几十年的历史，很多启发式算法相继被提出并发 展，但这些算法考虑的都是单目标优化问题，不适合多目标全局优化。近年来，在解决 多目标优化问题上，一些智能算法逐渐受到关注，而多目标遗传算法由于天生的并行性， 善于在全局范围内进行搜索，被认为是一种解决多目标优化问题的优秀算法。本文将在 综合分析现有解决s t e i n e r 树问题的算法、解决多目标优化经典算法和现有常见的多目 标遗传算法的基础上，考虑利用多目标遗传算法解决一种两个目标的s t e i n e r 树问题。 一1 一 东北大学硕士学位论文第1 章绪论 1 2s t e i n e r 树问题概述 1 6 3 8 年，法国数学家费马在他所写的一本关于求极值的书中，提到一个选址问题： 平原上的三个城镇问要兴建一个公用的煤气供应站，把它定在什么位置，才能保证由供 应站到三个城镇的输送管道的总长最短? 这个问题被称为费马问题。 费马问题很容易就被推广到若干个点的情况。瑞士数学家s t e i n e r ( 1 7 9 仁1 8 6 3 ) 将 问题推广成：在平面上求一点，使得这一点到平面上给定的若干个点的距离之和最小。 这可以看作s t e i n e r 树( s t e i n e rt r e e ) 问题的雏形，但s t e i n e r 在这个问题上未曾作过什么 贡献。 其后，德国的两位数学家韦伯( w e b e r ，1 8 4 2 _ 1 9 1 3 ) 和维斯菲尔德( w i e s z f e l d ) 分别 在1 9 0 9 年和1 9 3 7 年将该问题作为工厂选址问题提出来：某地有给定的若干个仓库，每 个仓库的其他相关因素可以换算成一个权重表示，求一建造工厂的合适地点，使工厂到 每个仓库的距离与权重乘积的总和最小，则这个工厂的地址是最经济、便利的。维斯菲 尔德并给出了一个算法用以求出工厂地址的近似值。我国在2 0 世纪5 0 年代未期也曾提 出类似的选址问题。1 9 7 0 年，美国数学家库恩( k u h n ) 指出了维斯菲尔德的算法不是 一个收敛算法，并给出了收敛的算法。我国的王长钰在1 9 7 8 年也给出了收敛的算法。 s t e i n e r 树问题得到进一步发展是由于库朗( c o u r a n t ) 和罗宾斯( r o b b i n s ) 在1 9 4 1 年的一本科普性读物什么是数学中提到了费马问题。书中说，s t e i n e r 对此问题的推 广是一种平庸的推广。要得到一个有意义的推广，需要考虑的不是引进一个点，而应是 引进若干个点，使引进的点与原来给定的点连成的网络最小。他们将此新问题称为 s t e i n e r 树问题，并给出了这一新网络的一些基本性质。本文所指s t e i n e r 树问题即依据 此定义1 3 l o 设x 为平面上给定万个点的点集。连接任意给定两点的线段叫做一条边，此两点为 此边的端点。设g 是由某些边做成的图形。边的端点叫做g 的顶点。若对g 的任意两个 顶点皆可通过g 的某些边把它们连起来，则称g 为可连通的。此时若g 上任何两顶点只 有一条路可连通，则g 称为一棵树。更进一步，若g 的顶点集包含x 中所有点，则称g 为x 的生成树( s p a n n i n gt r e e ) 。当给定点甩 3 时，x 的生成树不止一个，其中费用最 小的一条叫做s t e i n e r 最小树( s t e i n e rm i n i m a lt r e e ) ，记作s m t 。若此s m t 的s t e i n e r 点中有等于给定点的点，则称此s m t 为退化的，此给定点称为退化点。 库朗等人的推广大大扩充了这一问题的应用范围，也增加了问题的难度。试想：假 若平面上给定了1 0 0 个点，要在平面增加若干个( 至多为9 8 个) 点并把它们连成一个 网络，同时要使得这一网络的长度是所有连接这1 0 0 个点的网络中最短的。如何去找这 些点，如何把这些点连起来? 一2 一 ，0，h白，k illi毒 东北大学硕士学位论文第1 章绪论 对于平面上任意给定的四个点，求它们的s m t 并不难，波拉克( p o l l a k ) 在1 9 7 8 年最早给出了解法。当给定点的数目大于等于4 时，点集的s t e i n e r 树就不止一棵。没 有退化点的s t e i n e r 树称为完整s t e i n e r 树，记作f s t 。对给定的点集，若将它的所有的 f s t 和具有退化点的s t e i n e r 树加在一起，其数目可以大得惊人。例如当给定点的数目为 6 时，此数目为5 6 2 5 ，当给定8 个点时，则为2 6 4 3 7 9 5 。给定的点越多，这个数目增长 得越快。 要从众多的s t e i n e r 树中求出长度最小者，计算量相当繁重。但有些投资数额巨大 的工程，比如从西伯利亚修建一条天然气管道到上海，沿途向许多城市输送天然气，只 要在设计上能节约百分之二三，也是一个很大的数字。另外一些问题，例如计算机的微 型集成电路芯片，由于同一线路布局的芯片需要量很大，在设计上若能尽量缩短线路总 长，也会极大节约成本。因此，如何寻找s m t 变成了许多运筹学工作者所关心的问题。 求解s m t 问题已被证明为n p c ( n p c o m p l e t e ) 问题，不可能出现有效算法，即所谓的 多项式算法来处理这一问题。在第三章中，将对s t c i n e r 树的具体定义和一些解决s t e i n e r 树问题的启发式算法作进一步介绍。 本文要求解的s t e i n e r 树，并非简单地寻找s m t ，而是要寻找边尽可能少的s m t ， 这样就需要同时考虑总费用和总边数两个目标，而这样的多目标s t e i n e r 树问题已经被 证明为n p h a r d 问题。具体定义和解决方法将在第四章作以全面阐述。 1 3 遗传算法和多目标遗传算法概述 1 3 1 遗传算法概述 电子计算机问世以来，生物模拟便构成了计算机科学的一个组成部分。其目的之一 便是从研究生物系统出发，探索产生基本认知行为的微观机理，然后设计具有生物智能 的机器或模拟系统以解决复杂问题。如遗传算法、神经网络和细胞自动机等都是从不同 角度模拟生物系统而发展起来的研究方向。 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) ，是一种模拟自然界生物进化过程的全局随机搜 索算法，由美国m i c h i g a n 大学的h o l l a n d 教授于2 0 世纪6 0 年代首先提出【4 1 。它将计算 机科学与进化论思想有机结合起来，借助于生物进化机制与遗传学原理，根据优胜劣汰 和适者生存的原则，通过模拟自然界中生物群体由低级、简单到高级、复杂的生物进化 过程，使所要解决的问题从初始解逐渐逼近最优解或准最优解。算法起始于一个代表问 题潜在解集的群体，该群体包含若干经过基因编码的个体，每个个体携带不同的染色体， 代表了问题不同的解。初始群体产生后，按照适者生存和优胜劣汰的原理，即根据问题 中个体的适应度大小，按照相应的规则挑选个体，借助于自然遗传学的遗传算子进行组 一3 一 东北大学硕士学位论文第1 章绪论 合交叉和变异，产生出代表新的解集的群体。如此逐代进化，产生出越来越好的近似解。 这些操作模拟群体自然进化过程，后代群体比前代更加适应环境，末代群体中的最优个 体经过解码，可以作为问题近似最优解【5 l 。 与传统方法相比，遗传算法的主要特点是： ( 1 ) 使用参数编码集，而不是参数本身进行工作； ( 2 ) 在点群中而不是在一个单点上进行寻优； ( 3 ) 仅使用问题本身所具有的目标函数进行工作，而不需要其他任何先决条件或 辅助信息； ( 4 ) 使用随机转换规则而不是确定性规则来工作。 作为一种新的全局优化搜索算法，遗传算法简单易用，不容易陷入局部最优，即使 在所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找 到全局最优解。由于它固有的并行性，遗传算法也非常适用于大规模并行分布处理。近 年业，遗传算法在数值优化、组合优化、自动控制、模式识别和人工生命等众多领域得 到了深入发展和广泛应用。 1 3 2 多目标遗传算法概述 遗传算法应用于单目标问题之后的2 0 多年以后，多目标遗传算法( m u l t i o b j e c t i v e g e n e t i c a l g o r i t h m s ，m o g a ) 逐渐成为研究热点，十几年来出现了许多基于进化方法的 多目标优化技术。遗传算法思想在多目标优化问题中的首次应用可以追溯到1 9 6 7 年， 在r o s e n b e r g 的研究中提出模拟单细胞有机物的化学遗传特性中采用多属性研究方法1 6 1 。 虽然在他的研究中最终只应用了单一属性方法，但正是他的研究开创了这个领域的研 究。遗传算法真正意义上应用于多目标优化领域是在9 0 年代初期最早出现的。 遗传算法的操作需要适应度值的信息，那么，对于多目标优化问题来说最直接的方 法就是采用加权的方法将各个目标函数整合成一个单目标优化问题。从概念上讲，权重 和方法可以看作是将多目标优化中采用的方法向遗传算法进行扩展。该方法给每个目标 函数分配权重，然后将加权目标组合为单一目标函数。事实上，在遗传算法中使用的权 重和方法与在传统多目标优化算法中使用的权重和方法在本质上有很大不同。在多目标 优化中，权重和方法用来获得妥协解。使算法运行的唯一要求是合适的权重向量，但是 对于给定问题，通常很难获得一组合适的权重。在遗传算法中，最初权重和方法用来使 遗传搜索向着p a r e t o 前沿( p a r e t of r o n t ) 进行。随着进化的进行，权重适应性地重新调 整，因此并不一定需要良好的权重向量来使遗传算法运行。另外，权重和方法在传统多 目标优化中的缺点也可以被遗传算法基于群体搜索和进化搜索的力量削弱。最近提出了 三种权重设置的方法：固定权重方法、随机权重方法和适应性权重方法。固定权重方法 一4 一 p 1 -；0，；4 东北大学硕士学位论文第1 章绪论 可以看作是对传统标量化方法的模仿，而随机权重方法和适应性权重方法用来更全面的 利用遗传算法的搜索能力。m u r a t a ，i s h i b u c h i 和t a n a k a 提出了一种随机权重方法 ( r a n d o m w e i g h ta p p r o a c h ) 来获得目标是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 9 9 2 年，w i e n k e e t a l 使用目标规划法和遗传算法结合来解决 核物理学中的问题。 早期的多目标遗传算法一般都是遗传算法和一些经典的多目标优化技术的结合产 物，它们普遍效率不高、局限性大、鲁棒性差。之后出现了基于多群体的v e g a 、基于 字典序的方法、基于博弈论的方法等等，这些方法的特点是实用性差、解的精度不高、 不能保证求得最优解。目前多目标遗传算法的研究热点是采用p a r e t o 机制的多目标优化 技术，包括n s g a ，n s g a - i i ，n p g a ，s p e a 等等。 1 4 本文主要研究内容及章节安排 本文在广泛深入地查阅国内外文献的基础上，对遗传算法、多目标遗传算法、s t e i n e r 树问题和多目标优化问题的理论基础和基本方法进行了详尽的讨论和分析。介绍了遗传 算法、多目标遗传算法的一般流程和基本理论，讨论了现有的解决s t e i n e r 树问题的启 发式算法和解决多目标优化问题的经典算法，在此基础上提出了两个目标s t e i n e r 树问 题，并提出用多目标遗传算法解决这一问题。 第一章对问题提出的背景作了概括说明，并对文中涉及的s t e i n e r 树问题、多目标 优化问题和多目标遗传算法进行了概述。 第二章对s t e i n e r 树问题和涉及到的一些概念进行了定义，对目前常用的求解s t e i n e r 树问题的启发式算法进行了介绍，并介绍了多目标优化问题的基础知识和常用算法。 第三章对遗传算法及多目标遗传算法的发展和基本概念作了介绍，对两种算法的基 本理论和工作流程作了简要说明。重点介绍了多目标遗传算法的常用策略、分类和一些 常见的多目标遗传算法。 - - 5 - 东北大学硕士学位论文第1 章绪论 第四章首先定义了本文所要解决的两个目标的s t e i n e r 树问题，并详尽叙述了用多 目标遗传算法解决此问题的各个步骤，对算法的每个细节都作了具体的阐述。 第五章介绍了算法的实验，具体介绍了算法的参数、实验方法和实验结果，并与三 种解决s t e i n e r 树问题的经典算法相比较，说明本文算法的有效性和先进性。 第六章对研究工作作了总结，对存在的不足进行了分析，并对下一步的研究提出了 展望。 一6 一 东北大学硕士学位论文第2 章s t e i n e t 树问题和多目标优化问题 第2 章s t e i n e r 树问题和多目标优化问题 2 1s t e i n e r 树问题的定义 对s t e i n e r 树问题的研究早在2 0 世纪6 0 年代就开始了，到现在为止，已经有了很 多这方面的文献。s t e i n e r 树问题的应用不仅在通信方面，在电路图的自动布线、交通线 路的经济规划、车辆的调度和编组、通信线路的铺设等方面都有应用。s t e i n e r 树问题有 很多种类型，如网格( g r i d ) _ l 的s t e i n e r 树问题、e u c l i d e a n 平面上的s t e i n e r 树问题、一般 连通图中的s t e i n e r 树问题等。本文主要研究无向连通带权图中的s t e i n e r 树问题，首先 给出无向带权连通图上s t e i n e r 树问题的定义川。 首先可以把目标网络抽象为无向连通图g ；，e ) ，其中y 为节点的集合，e 为边 的集合，在每条边e e 上定义一个权值函数c ( e ) ：e r + ，表示每条边的费用，给定一 个节点子集q v ，s t e i n e r 树问题就是要寻找一棵搜索给定节点集合q 且费用最小的最 优s t e i n e r 树= 吒，) ，其中q k y ，q e 。用c ( ) 表示树的费用，即 c ( r o , ，) 一 ：c 0 ) 。 西磊 从最优s t e i n e r 树的定义可知，最优s t e i n e r 树中的叶子节点都应是q 中的节点，一 般称q 中的节点为基本节点；最优s t e i n e r 树中除基本节点外的其它节点被称为s t e i n e r 点，图g 中所有可能成为s t e i n e r 点的节点集合记为s ，易知q o s = 9 ，v = q u s 。 表面上s t e i n e r 树问题似乎与n 个点的最小生成树非常类似，二者优化的目标都是代 价最小的树，但两者有本质的区别。最小生成树问题搜索的目标是确定的，即所有的目 标节点都已经给出，需要做的是针对这些已知点找到一棵最小树，这种寻优在多项式时 间内是可以计算的；而s t e i n e r 树问题是n p h a r d 的，解决该问题的难点在于无法确定 最优解中s t e i n e r 点的个数和它们的位置。 2 2s t e i n e r 树问题的启发式算法 最小生成树和最短路问题都是s t e i n e r 树问题的特例，当q y 时，s t e i n e r 树问题就 转化为最小生成树问题，当给定节点集合中只包含两个节点时，即l ql = 2 时，就变为最 短路问题。最小生成树问题和最短路问题都存在多项式时间的最优解法。但s t e i n e r 树 问题不存在多项式时间的最优解法，它是一个n p 完全问题1 8 1 。我们知道如果一个最优 化问题是n p 问题，除非p = n p ，否则不能在多项式时间内精确地求解该问题，一个合 一7 一 东北大学硕士学位论文第2 章s t e i n e r 树问题和多目标优化问题 理的目标是寻找该问题的一个启发式算法，使我们能在一个低阶多项式时间内得到一个 “接近”最优的解。 对s t e i n e r 树问题一般讨论解决它的启发式算法。启发式算法并不保证给出最优解， 那么如何评价启发式算法的好坏呢? 主要是基于两个方面的考虑：首先是时间复杂性方 面的要求，即要求有一个多项式时间界；其次是性能方面的要求，即希望所求的近似解 尽可能“接近”最优解。可以从不同角度来评价启发式算法的性能，大体上可分为三类： 第一类是以算法在最坏情况下的行为为标准，研究算法得到的近似解与最优解的接近程 度，越接近越好。第二类是以算法的平均行为为标准，研究得到最优解的概率。第三类 是局部搜索算法，寻找局部最优解，这种方法有时很好，有时很差，只能通过实践加以 评定。对于算法最坏情况下的性能比，可以从理论上给出一个上界。但最坏情况下的性 能不能说明算法的实际性能如何，因为在实际应用中，算法体现出来的是平均性能，最 后情况很少发生。而算法的平均性能是较难从理论上给出的，为此要通过仿真实验来研 究算法的平均性能。 在介绍启发式算法之前，首先给出几个定义和符号。 g ；，e ) 表示无向连通图，v 为节点集合，e 为边的集合，s 为所有可能成为 s t e i n e r 点的节点集合，q 为基本节点集合，q n s = j 2 j ，v = q a s 。 t t ( 峰，岛) 表示覆盖节点集合q 的一棵生成树，q v ，露e 。 c j ( 表示边g ，j ) c e 的费用，c ： e r + ，v ( f ，j ) e 。 比表示节点f 到节点_ 的最短路的费用，即节点f 到节点距离。 p ( i ，j f ) 表示节点i 和j 之间的最短路径。 d ( i ，t ) = m i n d 盯l _ 屹】表示树z 外节点f 到树t 一 嵋，写) 的距离：称节点j 为树z 中距离节点f 最近的节点，如果节点_ 满足下面条件：对树中任意节点k 有不等式如sd 趾 成立。 z r 表示在求解s t e i n e r 树问题时，用启发式算法得到的树t 的费用；z 叫表示对应 的最优树的费用。 下面对己有的s t c i n e r 树问题的启发式算法做一介绍。启发式算法的优点在于算法 实现较简单，算法复杂度不高，s t c i n c r 树问题的启发式算法基本上都是借鉴最小生成树 和最短路算法的思想。 1 基于最短路思想的s t e i n c r 树启发式算法 这个算法直接应用了最短路算法，它最后的结果为最短路径树( s p t ) ，其主要步骤 如下【9 l = 初始时，树丁中只包含任意一个基本节点w ，即r 一( ，彩) ； 一8 东北大学硕士学位论文第2 章s t e i n e r 树问题和多目标优化问题 对所有其他的基本节点i e q 一 以，f 用最短路与w 相连，并将最短路p ( i ，w ) 加入 到树中，最终形成树r 。 这个算法得到的树的费用较大，因为它并没有考虑全树的费用，而只保证从源节点 到其它所有节点的费用最小，这种算法适合于通信网络中，要求从源节点到所有目的节 点进行传输的时延最小的情况。 2 基于最小生成树思想的s t e i n e r 树启发式算法 这个算法实现起来也很简单，其主要步骤如下【9 l ： 求出图g 的最小生成树t ； 检查此树r 中的叶子节点是否都是基本节点，如果存在非基本节点的叶子节点， 则删去这些节点以及与之邻接的边，这样做直到树丁中所有的叶子节点都是基本节点。 这个算法直接利用了最小生成树算法，然后进行简单的剪枝操作，由于思想比较简 单，所以较容易实现。 上面介绍的两个算法的优点在于实现起来比较简单，并且算法的性能有时好于后面 介绍的较为复杂的算法，但是这两个算法最坏情况下的性能比不是很好，而后面介绍的 几个算法其最坏情况下的性能比不大于2 。 3 a r i n s ( a r b i t r a r yi n s e r t i o n ) 算法 这个算法的基本思想是依次将树外的基本节点通过最短路与树相连。 初始时，树t = ( w ，d ) ，只有一个基本节点w ； 任选一个不属于树丁的基本节点p ，找到树丁中距离它最近的节点 ，+ ，即 y + k 满足d ，am i n d p 。i ，巧) ，然后将此节点通过最短路p ( i ，p + ) 加入到树中，这 样做直到所有的基本节点都连接到树中。 a r i n s 算法通过最短路将节点同树相连，这是是动态多播算法常用的方法。下面介 绍的算法是a r i n s 算法更进一步的改进。 4 d n h ( d i s t a n c en e t w o r kh e u r i s t i c ) 算法 d n h 算法在某些文献中又被称为k m b 算法，是解决s t e i n e r 树问题最著名的一个 算法。它用到了距离完全图和最小生成树算法，其基本思想是i l o l ： 构造图g 的距离完全图g a ( q ，e i ) ，其中v ( u ，v e 是图g 中节点u 到节点v 的 最短路径，即边似，v ) e 的费用等于g 中节点u 到节点v 的最短路的费用； 构造图g 的最小生成树t ； 将r t 中的边再转换为g 中的最短路径，形成子图g s ； 求t p , 仗的最小生成树不； 删除瓦中非基本节点的叶子节点，最后得到所求的树7 。 一9 一 东北大学硕士学位