（通信与信息系统专业论文）wdm波长网络优化设计和动态路由的研究.pdf

w d m 波长网络优化设计和动态路由的研究 摘要 波分复爱网络由于具有多种优点被认为是未来骨干网的发眨方 向，它豹优点包括惫分利用光乎巨大带宽资源，同时侉输多种不1 j j 类型约信号，对数据f | 各式透鹄，节约链路投资，高度的绝网灵活性 知可袁| 生： 渡妥路由网络忌波长复喇嘲络的一种，亡是透过波妥求选择路 三的，波长路由阀络由于应用了波分复用技术，使得列络容量威f 亡 提葡，同时它乖j 用波长来远择路由，大大提高了波长利爿率 r 卜丁 ；夏长路由网络非常适合于大容量高速速率数握的传输，此# j 投长 路由网终骘设计和刚终运行时的路由的研究显得十分重要， 沦文首先扶经济的角度来讨论_ 望：i f j 进行网路分配的算 云也孰 是说为事先给定的静态连接约需求分配刚络资源。论文考患蚴优化 目盱是使得分配的光纤数量最少换句话说也就是讨蹬如仁j 自d 置一 z 芒数量均光纤，使得整个网络司以容纳事先给顶定的所有静态连接， 论又的童j 新之处仁于，弓f 入了遗传算法对该问题进行籍决并对遗 乓算j 圭中各个参数对解决司题的影响作了讨论，最后_ ! 丕把该算法 l 线性整数规划肄法约结果做了： 较。 接着，论文从减小阻塞率的焦度分析了如何在波矢网中配置定 数量翦波长转换器使网络的殂塞塞最小。论文甲提出了，个算泫 扫对于穷举法，可以大大减少计算约数量，并能最终得至l j 最优化的 结果= 二坶交盎丕兰至主兰皇堡三一一一 一一 ，_l7 。篙鉴篙? 羔兰鬻纛繁篓慧尊嚣裂。 其分布式的实现方法二且讨论了波长重逸异j 击1 掰且。一“”、 连给出了双向网络和鱼一司j j j 络的波长重选算法。 关键词： 波分夏后网络，波长路吉，网络分配，遗传算法，渡长转 换波长重选 二每交道太学颐= 学位蹙z a l g o r i t h m s0 fn e t w o r kd 巨s i g n0 p t 1 z a t l 0 n a n dd y n a m i cr 0l t r n g r nw a v e l e n g t hr o u t r n gm ：t w o r k s a b s t r a c t i t i se x p e c t e dt h a tw a v e l e n 尊h d i v i s i o n m u l t i p l e x e df w d m ) n e t w o r k sw o u l db e t h eb a c k b o n en e t w o r k si nt h ef u t u r et h e i ra d v a n t a g e si n c l u d eg r e a tu t i l i z a t i o no f f i b e rb a n d w i d t h ，r r a n s f e n - i n gs i g n a l so f d i f f e r e n tk i n da ts a m et i m e 、t r a n s p a r e n tc 。d a t a f o r m a t ，s a v el i n ki n v e s t m e n ta n dh i g hf l e x i b i l i t ya n dr e l i a b i l i t yo fc o m p o s i n g 1 e t u o r k s d 。e l e n 婴hr o u t i n gn e t w o r ki sak i n do f v , , 1 d mn e t x - , o r k ：h a tr o u t e sb yw a v e l e n g t h b y d ，t e c h n o l o g y w a v e l e n 豇hr o u t i n gn e t w o r k sh a v es e v e r a lt i m e sf ，。c a p a c i t yd s n o r m a ls i n g l ew a v e l e n g t hn e t w o r k a n dw i t hr o u t i n gb yw a v e l e n g t h 【h ee f f i c i e n c 、o 【1 i i g h t w a , , ei ns u c hn e t w o r ki sm u c hh i g h e rs oi ti sn e c e s s a o t or e s e a r c ht h ei t e t d , o r k d e s i g np r o b l e ma n dr u n t i m er o u t i n gp r o b l e m i nt h ep a p e rn e t w o r k p r o v i s i o n i n ga l g o r i t h m ，w h i c hs o l v e st h ep r o b l e mo f a l l o c a t i o nr e s o u r c e st oa c c o m m o d a t e ss t a t i cc o n n e c t i o nr e q u e s t 、i sc o n s i d e r e dt h e a i mo fo p t i m i z a t i o ni st or e d u c ef i b e ru s a g e 、ied e t e r m i n e st h en u m b e ro ff i b e rt h a t n e e d st oa c c o m m o d a t e ss t a t i cc o n n e c t i o nr e q u e s t st h ep a p e rg i v e st h ei d e at h a t s o l , ? i n gt h ep r o b l e mb ) ? g e n e t i ca l g o r i t h mi nt h ep a p e r ，t h ei n f l u e n c eo f d i f f e r e n t p a r a m e t e r si sa l s od i s c u s s e da n dt h er e s u l t so f g e n e t i ca l g o r i t h ma n di n t e g e rl i n e a r p r o 罗a m m i n ga t - ed e m o n s t r a t e d t h e n ，t h ep r o b l e mo fw a v e l e n g t hc o n v e r t e r sp l a c e m e n tr e g a r d i n gr e d u c en e t w o r k b l o c k i n gr a t ei sd i s c u s s e da na l g o r i t h mi sp r o p o s e dt or e d u c ec o m p u t a t i o n c o m p l e x i t yc o m p a r e de x h a u s t i v es e a r c hm e t h o dt h ea l g o r i t h mc a ng i v et h eb e s t r e s t 】i t 上晦交墟天学i = 学i 主论文 f o rd y n a m i cr e q u e s t s ad i s t r i b u t e dr o u t i n ga l g o r i t h mw il lb eg i 。e nw a , , e i e n g t h r e r o u t i n ga l g o r i t h m sw i l la l s oh et a k e ni n t oa c c o u n tt or e d u c eb l o c k i n gr a t ei nb o t h b d i r e c t e dn e t v , o r ka n dd i r e c t e dn e t w o r k k e yw o r d sw a v e i e n 昏h d i v i s i o n m u l t i p l e x e dn e t w o r k s 、w a v e l e n m hr o u t i n g r z e t w o r kp r o ；i s i o n i n g ? g e n e r i ca l g o r i t h m ? - 旨i e l e n g t hc o n v e r r i n g ，# 。r e l e n g t h r e r o u t i n g 上海交通大学硕士学位论文 第一章w d m 波长网概述 随着人类信息化的发展，特别是i n t e m e t 的巨大发展，对于通信的需求呈现 出加速增长的趋势。而各种各样新出现的业务也对于通信网的容量和带宽提出 了更高的要求。光纤具有巨大的带宽优势和优异的传输性能。为了在一根光纤 中传输更高速率的数据，已经提出了包括时分复用( t d m ) ，光时分复用 ( o t d m ) 1 1 ，光波分复用( w d m ) ( ”，光频分复用( f d m ) 及微波副载波复 用( s c m ) 3 1 的技术。而其中w d m 技术最为成熟。 1 1 光波分复用技术 光波分复用技术( w d m ) 的原理是在一根光纤中同时传输多波长光信号的 一项技术。其基本的原理是在发送端将不同波长的光信号组合起来进行复用， 并把信号耦合到光缆线路的一根光纤中进行传输。在接收端，则把组合的光信 号进行解耦( 解复用) ，然后进行进一步的处理，把恢复出的信号送入不同的终 端，因此，这项技术被称为光波长分割复用技术，简称为光波分复用技术。 光复用技术主要有以下接个特点： 4 1 a ) 波分复用于系统的传输速率和电调制方式无关，即波分复用的信道对信 息比特和数据格式是透明的，这对把一个已有的光纤通信系统改变为光波分复 用通信系统具有很大的方便性，新加入的另一个系统在调制方式和传输速率上 不受原系统的约束或限制，不同容量的光纤系统以及数字和模拟信号均可以兼 容传输。 b ) 由于波分复用器件具有互易性( 双向可逆) ，即一个器件既可以分波，又 可以和波，因此可以在一根光纤上实现全双工通信( 双向传输) 。 c ) 波分复用技术可充分利用原有光纤线路扩大传输容量，以保持干线原有 的通信枢纽地位，并能解决业务繁忙时信息溢出的矛盾，而且迅速，简易，成 本低廉，特别是当光纤线路费用占的比例很大时，采用波分复用技术有着巨大 上海交通大学硕士学位论文 的经济效益。在一般的光纤通信系统中，只能传输一个光波长信道的光信号， 而这远远没能利用光纤的有效带宽。利用波分复用技术能大大提高光纤传输带 宽的利用率。 d ) 在长途光纤干线中，当进一步提高光纤传输速率时，光电器件由于速度 过高而受到限制，通过使用光波分复用技术扩大传输容量，可以减低系统高速 化对光电器件带来的某些苛刻要求。 e ) 光波分复用不排斥每个光信道采用的电复用方式，而且可以相互结合， 联合使用使之达到更高的复用水平，例如对现有的数字光纤通信进行光波复用， 实际上就是时分复用和波分复用的结合，每个不同波长信道中都是已经进行了 时分复用的光信号在传输。 波分复用通信传输系统主要有双纤单向传输和单纤双向传输两种结构。在 双纤单向传输系统中，所有的光通路同时在一根光纤上延同一方向传送，在发 送端将载有各种信息的具有不同波长的已调制光信号 ，兄：，旯，通过光复用 器组合在一起，并在一根光纤中单向传输，由于个信号是通过不同光波长携带 的，所以彼此之间不会混淆。在接收端通过光解复用器将不同光波长的信号分 开，完成多路光信号传输的任务。反方向通过另一根光纤传输，原理相同。 而在单纤双向传输系统中，光通路在一根光纤上同时向两个不同的方向传 输，所用的波长相互分开，以实现彼此双方全双工的通信联络。单向的w d m 系 统在开发和应用方面都比较广泛。双向w d m 系统的开发和应用相对来说要求 更高，这是由于双向w d m 系统在设计和应用是必须要考虑到几个关键的系统 因素，如要抑制多通道干扰，同时要使用双向光纤放大器。但是与单向w d m 系 统相比，双向w d m 系统可以减少使用光纤和线路放大器的数量。 1 2w d m 网的分层结构 根据i t u - tg8 7 2 建议，w d m 网的结构如图1 - 1 ( a ) 所示，分为电路层，电 通道层，电复用层，光层以及物理层。其中光层又可以分为光信道层，光复用 层和光传输层，如图1 - l ( b ) 所示 上海交通大学硕士学位论文 其中，光信道层( o p t i c a lc h a n n e ll a y e r ) 负责为来自电复用段层的客户信 息选择路由可分配波长，为灵活的网络选路安排光通道的连接，处理光信道的 开销，并且提供光信道层的检测，管理功能。并且在故障发生时，通过重新选 路或者直接把工作业务切换到预定的保护路由来实现保护倒换和网络恢复的功 能。 光复用层( o p t i c a lm u l t i p l e x i n gs e c t i o nl a y e r ) 保证了两个波长传输设备之 间的多波长复用光信号的传输完整性，为多波长信号提供网络功能。其功能主 要包括：为灵活的多波长网络选路重新安排光复用段功能，为保证多波长光复 用段适配信息的完整性处理光复用段开销，为网络的运行和维护提供光复用段 的检测和管理的功能。 光传输层( o p t i c a lt r a n s m i s s i o ns e c t i o nl a y e r ) 为光信号在不同类型的光传 输媒质( 如g 6 5 2 ，g6 5 3 ，g 6 5 5 光纤等) 上提供传输功能，同时实现对光放 大起或中继器的检测和控制功能等。通常涉及功率均衡，e d f a 增益控制和色 散的积累和补偿的问题。 电路层 电通道层 电复用层 光层 物理层( 光纤) 电路层电路层虚通道 p d h 通道层s d h 通道层虚通道 电复用段层电复用段层( 没有) 光信道层 光复用段层 光传输层 物理层( 光纤) ( b ) f i g1 - 1 ：l a y e r e ds t r u c t u r eo f o p f i c a ln e t w o r k ( a ) w d mn e t w o r k ( b ) s t r u c t u r eo f o p f i c a ll a y e r 图1 1 光通信网路的分层结构 ( a ) w d m 网络( b ) 光层分解 w d m 网常见的拓扑结构有线形网，星型网【5 】，树型网，环型网 6 7 】和网孔形 网。 与其它的拓扑相比，网孔型的网络可靠性最高，但是结构比较复杂，相关 的控制和管理也相当复杂。通常仅在要求高可靠性的骨干网中使用。本文的重 上海交通大学硕士学位论文 点就是讨论在任意拓扑结构下的网孔型的网络光通道层。 1 3 波长路由网络 波长路由网络吲是由可以进行波长路由的网络和一些点到点的光纤连接而组 成的。波长路由网络具有路由的功能，它能够按照网络中端到端的连接来选择 输出端口。如图1 2 所示的网络中一共存在着三条端到端的连接。由于从结点1 到结点5 的连接和结点1 到结点4 的连接没有公共的链路，所以两条连接可以 使用相同的波长来进行传输。而从结点2 到结点3 的链路因为和从结点到结点 5 的链路有公共的链路，因此，不能使用相同的波长来进行传输。 f i g1 - 2 ：w a v e l e n g t hr o u t i n gn e t w o r k 图1 - 2 波长路由网络 波长路由结点中最重要的器件就是光交叉连接器( o x c ) ，波长交叉连接器的 输入输出端口分为中继线( t r u n k ) 端口和本地端口( 1 0 c a l ) ，中继线端口通过光 纤与其他波长路由结点相连，本地端口则用于本地的业务上下路。所有的业务 的起点和终点都在本地端口。当交叉连接器只含两个中继端口时，相应的结点 被称为光交叉复用器( o a d m ) 。交叉连接器由波长复用器，解复用器，交换矩 阵组成，还有可能还包括波长转换器。 9 1 波长路由网络可以为用户提供两种端到端的连接方式，波长路径( w a v e l e n g t h p a t h ) ，简称w p 和虚波长路径( v i r t u a lw a v e l e n g t hp a t h ) ，简称v w p 。着两种 不同的方式，取决于交换结点是否提供了波长转换的功能。 上海交通大学硕士学位论文 w p 方式是指在从源结点到目的结点的一条通信通道l ，在这条通道通过的 所有链路上都分配了一个相同的波长供这条通信通道使用。在一条物理链路上， 可以同时有多条连接通过，但是不同连接之间所用的波长必须不同。网络可以 根据用户的请求建立或拆除光路。 p 1 方式则就灵活多了。由于在波长路由结点上配置了波长转换器，因 此可以在从源结点到目的结点的连接所通过的各条链路上分配不同的波长，则 在为v 、p 连接寻找路由和分配波长时可以一段一段链路考虑。而、v p 连接则 要复杂的多，必须要在全网的范围里寻找如何为w p 连接分配波长。 论文首先从经济的角度来讨论如何进行网络分配的算法，也就是说为事先 给定的静态连接的需求分配网络资源。文中考虑的优化目标是使得分配的光纤 数最少，换句话说，也就是说如何配置一定数量的光纤，使得整个网络可以容 纳事先给定的所有静态连接。在问题的讨论中，论文引入了遗传算法对问题进 行解决，并对遗传算法中各个参数对解决问题的影响做了讨论，最后还把该算 法与线性整数规划的解法做了比较。 其次，论文从减小阻塞率的角度分析了在如何在波长网中配置少量的波长 转换器，使得网络的阻塞率最小的问题。文中提出了一个算法，相对于穷举法， 可以大大减小计算的强度，最终还是能够得到最优化解的方法。 接着论文对在动态的情况下，如何进行路由和波长分配的算法，并研究了 在动态条件下，对波长进行重新选路的问题。 上海交通大学硕士学位论文 第二章网络分配优化算法 2 ，1 概述 网络资源分配是指把网络资源合理的分配，以满足静态的流量需求m 】。有 效的网络资源分配算法可以以最小的代价满足所指定的流量需求。在w d m 网 络中，网络资源分配是指在给定网络的拓扑和静态流量要求下，合理的选择路 由和分配波长。 在这一类问题中通常有两种情况。一种是在给定光纤数量的限制下，寻找 一个分配方案，使得所需要的光波长数量最少。另一种情况则是在每一条光纤 所能容纳的波长数给定的情况下，寻找一个分配方案，使得需要的光纤数最少， 或者所能容纳的最大容量。 1 3 1 在文献 1 4 1 7 中讨论了在传统的单波长网络中，网络设计的一般方法，可 以使用在w d m 网络中。在本文中，讨论主要集中于在w d m 网络中，对于一 组静态的连接，利用遗传算法找出一个最优的分配方案。在本文的讨论中，假 设在光波长网络中，并不存在波长转换器。因此，对于给定的一个连接，在每 一个从源到目的的通路上，每一个链路所使用的波长都是相同的( 波长一致性 约束) 。因此，在两个相邻的结点之间，有可能存在多条光纤的情况。而对于每 一条光纤，其费用反映了光纤的材料，光放大器以及终端设备的费用。算法的 目标是找到一个分配方案，使整个网络的费用最小。 2 2 问题的数学模型 在本文中所讨论的网络是一带权重的无向图g = ( ，e d ) ，其中n 代表结点 的集合，e 代表链路的集合，d = ( d ( e ) ：p d ，表示链路的权重的集合，是一实 6 上海交通大学硕士学位论文 数的集合。在本文中，链路的权重表示在链路上部署一条光纤的费用。在每一 条光纤上可用的波长的集合表示为w 。用u = n x n 表示网络中结点对的集合。 预先给定的网络流量的需求是用一个整数向量来表示的5 = ( 5 ( u ) ：i t ，其中 5 ( u ) 表示在给定结点对之间所需要建立的连接数。假定在网络中每一个端到端 的连接只能在事先给定的可行路径中，其中可行路径表示为p ( u ) 。如果 p p ( u ) 且w w ，则称( p ，w ) 为结点对u 的可行路径。 定义一个分配方案为一个向曩口= ( a ( p ，w ) ：p p ( “) ，“u ，w w ) ，且口0 ， ，嘣。) 。，a ( p ，w ) = j ) ( 对于每一个结点对“u ) 。对于在口分配方案下， 每一个链路的负荷表示为 z ( g ，w ) = a ( p ，w )( 2 - 1 ) h e u _ 口e p ( o ) 1 6 p 如果a ( p ，w ) 表示在通路p 在波长w 上所分配的连接的数量，那么在通路p 上 每一个链路都占用了波长w 。则每一条链路e 上所需要的光纤的数量则表示为 m a x 。，x ( e ，w ) ，而对于分配方案口，总费用表示为 ， ) 2 萎) 学z ( 2 - 2 ) 综上，整个问题可以表述为如下所述 给定一个网络g ，波长的集合w ，流量需求艿以及可行路径集合 ( p ) ：“u ) ，搜索一个最优方案，使得 m i n d ( p ) r ( p ) 畦e ( 2 3 ) 对于每一g e ，w ，x ( e ，w ) t c ( e ) ，且口是一个整数向量。 其中 p ) ：e d 和0 p ，w ) ：，j p ) 甜u ，w 即为变量， ( x ( e ，w ) ：e e ，w ) 由( 2 1 ) 决定。 这是一个典型的整数线性规划问题，但是即使对于一个普通规模的网络来说， 7 上海交通大学硕士学位论文 其变量和约束的数目也是很大的。如表2 1 所示，即使是网络的规模非常小时， 整个整数线性规划的问题的规模还是非常大的。 以图2 1 为例，说明如何计算所要优化的函数的值。 在图2 1 中，一共有四个结点，五条链路。假定在相邻的结点之间的光通路 都是双向的，因此整个图为一无向图。图的相邻结点之间的权重正比于两个结 点之间的距离，对应的实际问题，则表示两个结点之间单条光纤的费用，通常 与光纤的长度相关。在图中，除了结点2 和4 之间的权重为2 之外，其余的权 重都为1 。 结点的个数 93 28 8 变量的个数 6 9 88 9 7 86 8 9 5 4 约束的个数 3 4 01 8 8 81 1 8 4 0 t 曲2 1 ：p r o b l e ms c a l er e l a t e d t o n o d e n u m b e r 表2 - 1 ：问题规模与结点个数的关系 n o d e l n o d e3 n o d e2 n o d e4 f i g2 - l ：s a m p l ec a a p h o f 4n o d e s 图2 - 1 ：四个结点的图例 假定在每一对结点之间，有两条可行路径存在。可行路径的指定，是在进 行分配算法之前就已经做出的。通常反映了在两个结点之间需要有多条可行的 路径，以保证在结点之间的某一条链路出现问题时，可以选择替代的路径，使 得结点之间的通信不中断。可行路径的计算，可以通过在图中计算两个结点之 间的最短路径和次短路径来实现，如果需要指定更多的可行路径，那么可以依 上海交通大学硕士学位论文 次计算两个结点之间的不同通路，从中选择出最短的若干条。 在图1 1 所指定的拓扑中，指定的任意两个结点之间的可行路径为如表2 2 所示。在问题中，假定结点之间的链路是双向的，因此整个图为一个无向图。 在图例中，为了简化说明，假定如果从结点a 到结点b 的可行路径为p l ，p 2 ， 那么从结点b 到结点a 的可行路径为p 1 和p 2 的反向。 结点对可行路径一可行路径= ( 1 ，2 ) l = 2l = 4 = 2 ( 1 ，3 ) 1 = 31 = 4 = 3 ( 1 ，4 ) 1 = 41 = 2 = 4 ( 2 ，3 ) 2 = 1 = 32 = 4 = 3 ( 2 ，4 ) 2 = 42 = l = 4 ( 3 ，4 ) 3 = 43 = 1 = 4 t a b2 - 2 ：a d m i s s i b l ep a t ho f e a c hn o d e p a i r 表2 2 ：结点对之间的可行路径 结点流量需通过路径1波通过路径波 对求数长号2 数长号 ( 1 ，4 ) 2l01 o ( 2 , 4 ) 11o0o t a b2 - 3 ：t r a 伍cd e m m d v sp a t h d w a v e l e n # m s i g n m e m 表2 3 ：流量需求与路径和波长分配的关系 如果对任意两点之间的，所需要的流量如表1 - 3 所示，如果用表1 3 所指出 的可行路径和波长的指派，且每根光纤上只能容纳一个波长，那么根据表1 - 2 的指派，可以看到结点2 到结点4 之间的通路在结点1 和结点4 的连接中都使 用了同个波长，因此，在这两个连接中，不能在同一根光纤上传输，所以结 上海交通大学硕士学位论文 点2 和结点4 之间要部署两根光纤，而结点1 和结点4 以及结点l 和结点2 之 间只要部署一根光纤，因此总的费用为2 + l + 1 + 1 = 5 。 当然在上述的情况中，展示的是最坏的情况，而算法的目的则是避免这种 情况，使得整个网络中所使用的光纤数越少越好，从而使整个网络的费用最低。 2 3 遗传算法 解决如此大规模的整数线形规划问题，如果应用普通的线性规划算法来解决 的话，其空间复杂度和时间复杂度即使是对于一个普通大小规模的网络也是非 常大的，而对于较大规模的问题，则是无法在可行的时间和空间内解决的。 为了解决大规模的问题，利用遗传算法来解决该问题。遗传算法是一种宏 观意义上的仿生算法，它模仿的机制是一切生命和智能产生的过程。他通过模 拟达尔文的“优胜劣汰，适者生存”的原理激励好的结构，通过模拟孟德尔遗 传变异理论在迭代的过程中保持已有的结构，同时寻找更好的结构。1 遗传算法与其他一些优化算法相比，主要有以下几个特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利 用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的 值，而是以决策变量的某种形式的编码作为运算对象。这种对决策变量的编码 处理方式，使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，可 以模仿自然界中生物的遗传和进化等机理，也使得可以很方便的应用遗传操作 算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问 题，编码处理的方式曼显示出了其独特的优越性。 ( 2 ) 遗传算法直接以目标函数的值作为搜索的信息。传统的优化算法不仅需 要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能 确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可 以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助 1 0 上海交通大学硕士学位论文 信息。这个特性对很多目标函数是无法或很难求导数的函数，或者是导数不存 在的函数的优化问题，以及组合优化的问题，应用遗传算法时就显得比较方便， 因为它避开了函数求导的这个障碍。另外，直接利用目标函数值为个体适应度， 也可以使得把搜索范围集中到适应度比较高的那部分搜索空间中，从而提高了 搜索的效率。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解 空间的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息 毕竟不多，所以搜索效率不高，有时甚至使搜索过程限于局部最优解而停滞不 前。遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程，而 不是从一个单一个体开始搜索。对这个群体所进行的选择，交叉，变异的运算， 产生出的是一代新的群体，因此在这之中包含了很多群体信息。这些信息可以 避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算 法所特有的一种隐含并行性。 ( 4 ) 遗传算法使用概率搜索的技术。很多传统的优化算法往往使用的是确定 性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关 系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法 的应用范围。而遗传算法食欲一种自适应概率搜索技术，其选择，交叉，变异 等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽 然这种概率特性也会使群体中产生些适应度不高的个体，但是随着进化过程 的进行，新的群体中总会更多的产生出一些优良的个体，实践和理论都已经证 明了在定的条件下遗传算法总是以概率1 收敛于问题的最优解。当然，交叉 概率和变异概率会影响搜索效果和搜索效率。另方面，与其他的一些算法相 比，遗传算法的鲁棒性又会使参数对其搜索效果的影响会尽可能的低。 遗传算法的整个过程如下所示： 1 9 1 1 ) 初始化可行解的染色体群 2 ) 计算每个染色体的适应度函数 3 ) 如果符合停止条件转9 ) ，否则转4 上海交通大学硕士学位论文 4 ) 对染色体实行选择算子 5 1 对染色体实行交叉算子 6 1 对染色体实行变异算子 7 1 选择适应度最高的染色体组成下一代染色体群，并计算适应度函数 8 1 转3 ) 9 1 结束 遗传算法的实现包含了编码，适应度函数，选择算子，交叉算子，变异算子 以及参数的选择。 编码的实现 在上述的网络模型中，需要求得网络资源的最优配置的分配方案，使得整 个网络的开销函数为最小值，因此，所要进行编码的就为网络的分配方案。 对于个给定的静态流量矩阵，所要进行的编码的就为对于每一个连接，对 其通过的路径和所使用的波长进行编码。在本问题中，采用的是二进制的编码 方案，即每一个连接有n 个可行路径，把其编码为0 一n l ，并转换成二进制数， 对于每一个连接可以采用的f 个波长之中的个，把其编码为0 f - 1 ，并转换 成二进制数。即对于一个连接，如果对于每一个连接，其可行路径共有两条， 而其每一条光纤上的波长数为8 的话，可以采用l 位和3 位二进制的数来表示。 比如，对于某连接，如果采用的是1 号可行路径和3 号波长，那么它的二进制 编码就为1 0 1 1 。对于所有的连接，都采用上述的方法进行编码，然后把所有的 编码连接在一起，成为一个长的的二进制串，作为整个分配方案的编码。 适应度函数 在问题中，需要优化的目标函数是计算整个网络的开销，并使其尽可能的小。 在使用遗传算法优化的过程中，需要把已经编码的二进制串，还原成编码方案， 然后计算目标函数的值。与编码过程类似，首先把编码的长的二进制串分解成 等长的二进制节，每一个小节表示某一个连接的可行路径和使用波长的编码， 把二进制数还原成整数，得到整个配置方案。然后根据每一条连接的配置，在 1 2 上海交通大学硕士学位论文 每个连接通过的链路上，标记所使用的波长。然后统计每一条链路上所使用的 波长。如果在一条链路上，使用的波长各不相同，那么，该条链路上只需要配 置一条光纤，如果在链路上有不同的连接的可行路径通过，但是使用了同一个 波长，那么连接和连接之间就有冲突，就需要配置第二条甚至更多的光纤来满 足建立连接的需求。 在遗传算法中，一个的染色体编码的适应度函数和其后的选择算子和杂交算 子的应用密切相关，要求一个较优的染色体编码的适应度函数值应该比一个较 劣的染色体编码的适应度函数值为大。而在本问题中，目标函数的优化，需要 得到个最小值。因此需要把最优化的最小值转化成遗传算法的最大值。提出 了几种转化的方案，并在数字仿真中，做出详细分析。 假定优化函数的值为m ，其对应的适应度函数的值为f ，则定义以下几种转 换方案 1 ( 8 ) f 2 玄 ( 2 - 4 ) 直接利用倒数关系把最小值转化成最大值 1 ( 6 ) ，2 志 ( 2 5 ) 与( a ) 方案类似，也利用了倒数关系，但是首先在目标函数的值上减去了一个 常数( 其中常数c 的确定通过实验法来确定) ，这样可以在优化时使得较优的 配置方案的适应度函数值在和较差的配置方案的适应度函数值比较时，有显著 的差别，以提高遗传算法的效率。 f c ) f = c m( 2 6 ) ( c ) 方案利用个常数c 减去目标函数的值，来转化目标函数。 选择算子 遗传算法利用选择算子来对群体中的个体进行优胜劣汰操作，适应度高的个 体遗传到下一代群体中的概率比较大，适应度较低的个体遗传到下一代中的概 率比较小。遗传算法中的选择操作就是用来确定如果从父代群体中按某中方式 选择那些个体遗传到下一代的群体中的一种遗传运算。其操作的目的是为了避 1 3 上海交通大学硕士学位论文 免基因缺失，提高全局收敛性和计算效率。 在计算中，使用比例选择的方法来进行选择算子。比例选择法是一种回放式 随机采样的方法。其基本思想是：各个个体被选中的概率与起适应度的大小成 正比。 如果整个群体的大小为m ，个体i 的适应度为只，则个体被选中的概率以为 因此，适应度高的个体被选中的概率叫大，反之，适应度低的个体被选重的 概率也就小。 另一方面，由于采用的是比例选择的方式，随机的从父代群体中选取个体遗 传到子代中，概率较大的个体有可能选择不上。为了避免这种情况，除了在应 用比例选择的方法之外，使用了最优保存的策略，即在每一次进行选择之前， 遍历父代群体的所有个体，从中找出适应度最佳的个体，并且保存下来。在每 一次的迭代之后，都要进行如上述的操作，保存迭代至今的最优解。 交叉算子 在生物的自然进化过程中，两个同源的染色体通过交配而重组，形成新的染 色体，从而产生出心得个体或物种。交配重组是生物遗传和进化过程中的一个 重要的环节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。 遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互 交换其他部分的基因，从而形成两个新的个体。交叉运算是遗传算法的重要特 征，它在遗传算法中起着关键的作用，是产生新个体的主要方法。 遗传算法中，在交叉运算之前，还必须先对群体中的个体进行配对。常用 的配对策略是随机配对，即将群体中的m 个个体，以随机的方式配成i 等i 对 个体组，交叉操作是在这些配对的个体组中的两个个体之间进行的。 1 4 m # 酗 p 上海交通大学硕士学位论文 在本问题的讨论中，使用了单点交叉和双点交叉的交叉算子。 单点交叉，是指在个体的编码中，随机设置一个交叉点，然后在该点随机的 交换两个个体的部分染色体。比如如下的两个染色体片段 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 如果指定第7 位为交叉点，那么把上面两个染色体在第7 位以后的染色体部 分，可以得到 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 l o l 0 0 1 0 对于双点交叉，则是在个体的编码串中，随机选择两个交叉点，然后，交换 两个个体在所设定的两个交叉点之间的部分染色体。 在交叉算子实行的过程中，有可能会产生无效的染色体编码，即二进制串无 法映射回对应的网络分配的方案，那么采取以下的方法来修复染色体。 由于采取的是把整数映射到二进制数的方法，因此，在反向映射时，整数的 范围有可能会超出预定的范围，那么就在允许的范围内，随机选择一个可行的 整数，作为非法值的替代，并且映射回二进制，作为二进制串的修复值。 在交叉操作中有交叉算子实行的概率p ，在该概率下，配对的染色体实行交 叉算子。 变异算子 在遗传算法中，使用变异算子主要有以下两个目的： ( 1 ) 改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角 度出发找到了一些较好的个体编码结构，他们已经接近或者有助于接近问题的 最优解。但是如果只使用交叉算子没有办法对整个搜索空间的细节进行局部搜 索。如果此时利用变异算子来调整个体编码中的部分基因，就可以从局部的角 度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索的能力。 上海交通大学硕士学位论文 ( 2 ) 还可以维持群体的多样性，防止出现早熟。变异算子用新的基因替换原 有的基因，可以防止算法的早期收敛，维持群体的多样性。 在问题中，采取的是基本位变异的算法，其操作是在个体的编码上以变异概 率p 。，随机指定一位，然后改变该位的值，即从1 变为0 ，0 变为1 。 2 4 数字仿真及分析 2 4 1 一个中等规模的问题的仿真 在数字仿真中，使用如图2 - 2 的拓扑，其中共有1 1 个结点和1 8 条链路，链 路的权为相邻接点之间的距离( 即部署一根光纤的代价和接点之间的长度成正 比) 。种群的大小为6 0 ，终止条件是在8 0 0 代后无条件终止。在遗传算法中 p 。= o8 ，p 。= 0 1 f i g1 - 2 ：t b p o l o 盱o f n u m e r i c ds i m u l a f i o n 图i - 2 ：数字仿真的拓扑结构 适应度函数取f = 砺i 1 ，其中c = 2 2 5 0 是经过多次计算，取略小于最优值 的一个常数。在仿真中，指定的结点对之间的连接一共是3 0 0 个，对于每一对 结点之间，指定的可行路径为2 条，分别是最短路径和次短路径。相邻结点之 间的链路，每一条光纤可以放置8 个波长。 上海交通大学硕士学位论文 仿真的结果如下图2 - 3 所示 由图2 - 3 可以看到，遗传算法在迭代开始时，适应性函数的增长较快，而到 迭代次数达到6 0 0 以后，其适应性函数的值就逐渐开始放慢增长的速度，也就 是说算法开始逐渐收敛，直到8 0 0 次的迭代次数结束。 f i g2 - 3 ：s i m u l a t i o nr e s u l t ( a ) v a l u eo f t a r g e t f u n c t i o n ( b ) v a l u e o f f i t n e s sf u n c t i o n 图2 - 3 ：仿真结果( a ) 目标函数的值( b ) 适应性函数的值 1 7 上海交通大学硕士学位论文 242 不同参数对问题解的影响 小不同的从目标函数到适应性函数的映射对结果的影响 在前面的小节中，提出了三种不同的从目标函数到适应性函数，分别为直 接取倒数，减去一个常数后取倒数，以及用一个大的整数减去目标函数的方法 来得到适应性函数值。 利用2 41 中的网络拓扑，对三种不同的从目标函数到适应性函数映射方法作了 一个比较，并且对于第二和第三种的情况中，常数的不同取值，也作出了分析。 函数映射方法目标函数值 迭代次数 1 2 9 7 48 7 6 m c = 2 5 0 02 9 6 8 6 9 8 1c 。= 2 2 5 02 8 7 56 1 2 m c c = 2 0 0 02 9 3 07 2 6 c mc = 4 0 0 0 3 1 6 68 5 7 c = 3 5 0 03 0 2 69 1 8 c = 3 3 0 03 0 6 38 1 8 t a b 2 - 4 ：r e s u l to f d i f f e r e n tm a pf u n c t i o n 表2 - 4 ：不同映射函数的结果的比较 根据表2 4 的结果，可以看到，在三种不同从目标函数到适应性函数的映射 函数，对结果的影响是不同的，在三种映射方法中，减去一个常数值，然后取 倒数的方法结果最优，而直接取倒数的方法结果次之，而用一个常数减去目标 函数值的结果最差。分析其原因，对于一二两种方法，在取倒数前，首先减去 一个常数的做法，使得在迭代次数进入较后阶段时，较优的解的适应度函数要 比较劣解的适应度函数的值要相差更多倍数，使得解收敛的速度加快。 另一方面，在减一个常数然后取倒数的方法中，常数的选择也有一定的讲 究。如果常数取得太小，那么，优劣解适应性函数值之间的差别不是非常大， 对于解的收敛有一定的影响，如果常数取得太大，那么，优劣解之间适应性函 数的值会相差很多，那么在遗传算法迭代时，会使优的解迅速占领整个种群， 上海交通大学硕士学位论文 这样会使算法陷入局部最优解，而很难得到全局最优解 b ) 不同的种群大小对结果的影响 在2 41 的算法中，选择的种群的大小是6 0 ，那么种群的大小是否会对算 法产生不同的影响，通过给定不同的种群大小，来看解的特性。 种群大小目标函数值迭代次数 53 3 0 81 2 0 9 1 03 1 5 51 1 7 5 2 03 0 2 89 5 9 4 02 9 0 28 4 5 6 02 8 7 56 1 2 8 02 8 7 05 6 7 1 0 02 8 8 35 1 8 t a b 2 - 5 ：r e s u l to f d i f f e r e n tg r o u ps i z e 袁2 - 5 ：不同种群大小的结果的比较 通过上表可以看出，在种群非常小的时候，由于解的多样性得不到体现， 因此，算法的性能没有充分体现出来，也就是说，算法的收敛速度很慢。然而 当种群数量达到一定程度后，解的多样性已经充分得到了体现，因此，在优化 的过程中，基本上都能够达到较优的结果，此时再增加种群的规模，对于搜索 更优化的解所产生的意义不大。 c ) 不同的交叉概率对结果的影响 交叉的概率是指在种群两两配对之后，两个个体之间是否进行染色体基因 交换的过程，不同的概率对算法的影响如表2 - 6 所示 通过表2 - 6 可以看到，在交叉概率较小时，算法的性能比较差，而随着交叉 概率的逐步增大，算法的性能也就随之变得好起来，而到一定值之后，交叉概 率对于算法的影响就不是那么大了。在交叉概率较小时，配对的染