（应用数学专业论文）基于遗传算法的最小组播路由算法.pdf

摘要 由于计算机网络的迅速发展，目前出现了许多新的实时性业务， 如多媒体业务，它对网络提出了更高的要求，既要满足实时性，又要 高效的利用网络资源。它对路由机制提出了以下要求：( 1 ) 满足时实 应用的端到端的时延要求；( 2 ) 有效的管理网络资源。当前i n t e r n e t 上的路由机制主要是根据最短径算法，它只能在给定的单个代价准则 下找到基于最短时延或最多某种可用资源的路径。寻找满足时延约束 的最小代价路径是一个n p 完全问题。实验表明，本文提出的基于遗 传算法的最小组播路由选择算法能够使得路由选择既能满足时延的 要求，又能够有效的管理网络资源，即可以使碍网络费用接近于最小。 本文算法是在已有文献的基础加以改进，主要是下面两方面得到 改进。首先，该算法通过改进基因的编码方案，使得算法实现简单； 其次，在遗传算法的交叉操作时，采用保留相同链路的方法，使得算 法收敛更快。通过计算机仿真实验结果说明本文算法要大大优于已有 文献算法。 关键词：q o s ；组播路由算法；遗传算法；n p 一完全问题；斯坦利最 小树 a b s t r a c t a st h ed e v e l o p m e n to f c o m p u t e r a n dn e t w o r ka tp r e s e n t ，i ta p p e a r sa l o to fn e wr e a l t i m es e r v i c e s ，s u c ha sm u l t i m e d i as e r v i c e s ，w h i c hn e e d t h en e t w o r kt o g u a r a n t e e t h er e a l - t i m e r e q u i r e m e n t a n dt h en e t w o r k r e s o u r c e e f f i c i e n t l y i tp u t s f o r w a r dr e q u e s tt o r o u t i n g m e c h a n i s ma s f o l l o w ：( 1 ) e n d t o e n dd e l a yc o n s t r a i n t s ，( 2 ) t h e n e t w o r kr e s o u r c e e f f i c i e n t l y n o w , i n t e r n e tr o u t i n gm e c h a n i s ma c c o r d i n ga st h es h o r t e s t a p p r o a c ha r i t h m e t i c ，w h i c ho n l yc a nf i n dt h es h o r t e s td e l a yc o n s t r a i n t s a p p r o a c h o rm o s ts o m ea v a i l a b l er e s o u r c ea p p r o a c ho ns i n g l er u l e i ti sa n p c o m p l e t ep r o b l e mt of i n dal o w - c o s ta p p r o a c h ，w h i c hs a t i s f yd e l a y c o n s t r a i n t i nt h i s p a p e r , a na p p r o a c h b a s e do n g e n e t i ca l g o r i t h m i s p r o p o s e d ，w h i c hf i n d s t h el o w - c o s tm u l t i c a s t i n gt r e ew i t he n d t o - e n d d e l a yc o n s t r a i n t s a n dt h en e t w o r kr e s o u r c ee f f i c i e n t l y t h i sp a p e ra l g o r i t h mi m p r o v e so nl i t e r a t u r ea l g o r i t h m f i r s t l y , t h i s p a p e ra l g o r i t h mi m p r o v e st h em e t h o do fg e n e t i cc o d i n g ，w h i c hl e a d st o t h e a l g o r i t h m r e a l i z a t i o nm o r ee a s i l y s e c o n d l y , t h i sp a p e ra l g o r i t h m a d o p t sk e e p i n gt h e s a m ea p p r o a c hi nc r o s s o v e ro fg e n e t i ca l g o r i t h m ， w h i c hl e a d st ot h e a l g o r i t h mc o n s t r i n g e n c ym o r eq u i c k l y a tl a s t ，i t s h o w st h i sp a p e r a l g o r i t h mi sb e t t e r t h a nl i t e r a t u r ea l g o r i t h mb yt h er e s u l t o f e x p e r i m e n t k e y w o r d ：q o s ；m u l t i c a s t i n ga p p r o a c ha l g o r i t h m ；g e n e t i ca l g o r i t h m ； n p c o m p l e t ep r o b l e m ；m i n i m u m s t e i n e rt r e e 北京邮电大学硕士论文绪论 第一章绪论 1 1 遗传算法发展现状简介 近年来，一种在思路和方法上别开生面的新的优化算法一遗传算法 ( g e n e t ica l g o r i t h m s ，简称g a s ) 正在迅速发展。遗传算法以其很强的解决问题 的能力和广泛的适应性渗透到研究与工程的各个领域，并取得了良好的效果。 在国外，几种会议已设遗传算法的专题，而且已有专门的遗传算法国际会议， 每两年召开一次，目前为止，发表了数千篇论文，对其基本理论、方法和技巧 做了较充分的研究。今天，遗传算法的研究已成为国际学术界跨学科的热门话 题之一。 遗传算法的基本恩想起源达尔文的生物进化论，“适者生存，不适者淘汰”。 目前已用于科学研究和工程实际中的种种搜索和优化问题，如管道线路优化、 机器学习、模型识别，神经网络结构参数优化及权重学习、精调模糊逻辑控制 器、飞船控制系统优化等。 遗传算法是一种随机的全局多点搜索算法，同其它搜索方法，如：随机查找、 梯度下降、模拟退火等算法相比的主要优点是简单、通用、鲁棒性强。遗传算 法实现全局并行搜索，搜索空间大，并且在搜索过程中不断地向可能包含最优 解的方向调整搜索空间，以便寻找到最优解或准最优解。用遗传算法解决的问 题越复杂，目标越不明确，其优越性越明显。由于遗传算法可以较有效求解组 合优化和复杂函数的优化问题，目前许多学科的研究人员都开始探索采用这种 技术来解决各自学科中长期未能很好解决的困难的优化问题。 1 2 组播路由现状简介 组播( m u l t i c a s t ) 是一种可以由源结点同时向多个目的结点发送信息的通信 方式。* t 4 a g - 由问题是信息由源结点到多个目的结点发送的过程中路由的选择 北京邮电大学硕士论天 绪论 问题。随着计算机网络技术的发展，新兴的大量多媒体业务的应用如电视会议、 远程教学等，均涉及到多个用户参与，这不仅需要消耗大量的网络资源，而且 视频、音频等多媒体业务对网络服务质量( q o s ) 也提出的更高的要求。因此，支 持组播服务、支持q o s 将是未来网络必需具备的特点。因此，根据目前状况， 有必要研究满足一定q o s 要求的组播路由算法。 组播路由的拓扑结构通常采用树型结构。这样，一方面可保证信息到不同 信宿的并行传输，另一方面也保证了数据复制最少，从而减少冗余信息的传递 和降低网络资源的；肖耗。目前对于组播路由问题已经提出了多种算法。其中最 常见的是把组播路由问题形式化为图论中的斯坦利问题，通过求解斯坦利最小 树m s t ( 1 1 1 i n i m u ms t e i i l o rt t e e ) 来求解代价最小的组播树“。“。这一问题被证 明是n p 一完全问题“，提出了很多启发式算法进行求解，例如k m b 算法“1 、m p h 算法”1 、s p h 算法“1 等，在斯坦利问题中增加q o s 限制条件，提出了采用受限斯 坦利最小树解决组播路由问题的算法。文献“7 、“给出了引入时延限制的斯坦利 树的启发式算法，即在满足一定时延要求的情况下寻找代价最小的斯坦利树。 这对实时性有特殊要求的多媒体业务来说是非常必要的。除了启发式算法外， 文献”1 提出了神经网络的方法计算满足特定时延和时延抖动要求的斯坦利最小 树。文献”提出采用遗传算法解决时延受限的组播路由问题。但是，文献“”中 的算法采用单点交叉算法，其收敛速度不尽人意。文献”也提出了一种遗传算 法的解决方案，然而，他们在父代交叉操作后生成的斯坦利树不连续，需要进行 修补，实现起来有一定的难度。好的路由算法应该具有简单和快速的特点。为 此，本文将提出一种基于遗传算法的最小组播路由算法，它具有实现简单、收 敛速度快等优点。 1 3 本文算法要求 本文将提出一种基于遗传算法的最小组播路算法，该算法主要是在j ，x _ f - k 献的基础上加以改进，改进后的算法应该具有实现简单、收敛速度快、鲁棒性 强、通用性好等特点。同时，本文算法将同文献1 的算法加以比较。同文献“” 北京邮电大学硕士论又绪论 相比，主要在两方面要加以改进。首先，本文算法通过改进基圆台勺编码方案， 使得算法实现简单；其次，在遗传算法的交叉操作时，采用保留相同链路的方 法，使得算法收敛更快。通过计算机仿真实验结果说明本文算法要大大优于已 有文献“的算法。 1 4 本文结构安排 为了清楚的叙述本文提出的基于遗传算法的最小组播路由算法，接下来将分 为三大章节来加以叙述，第二章介绍遗传算法的发展现状基本理论及其应凰 第三章简要介绍本文将涉及到的相关通信网理论基础及其相关算法。第四章是 本文的重点，详细介绍本文提出的基于遗传算法的最小组播路由算法的设计和 实现过程，并且同文献“”的算法进行仿真比较，得出结论。 北京邮电大学硕士论文 遗传算法的基本原理及其应用 第二章遗传算法的基本原理及其应用 2 1 遗传算法简介 遗传算法是近年来迅速发展的一种全新的优化仿生算法，该算法源于六十 年代，密执安( r a i c h i g a n ) 大学教授 1 0 l l a n d 在研究机器学习过程中，提出的一 种随机搜索方法。其核心思想源于d a r w i n 的进化论和m e n d e l 的遗传学说。“适 者生存，不适者被淘汰”这一自然规律的生物进化过程本身是一个自然的、并 行发生的、稳健的优化过程，这一优化过程的目标是对环境的适应性，生物物 种通过生物的遗传、变异来优化达到目的。基于自然选择和遗传机制，遗传算 法已广泛用于困难搜索、优化和机器学习等问题，并且已取得丰硕成果。 2 1 1 遗传算法概要 对于一个求函数最大值的优化问题，一般可描述为以下数学规划模型： i m a x厂( z )( 2 一i ) s x r( 2 2 ) ir s u( 2 3 ) 上式中，x = x ，x ：，x 。】1 为决策变量，f ( x ) 为目标函数，式( 2 - 2 ) 、( 2 - 3 ) 为约束条件，u 是基本空间，r 是u 的一个子集。满足约束条件的解x 称为可行 解，集合r 表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。 它们之间的关系如图2 - 1 所示。 基本空间 行解集合 图2 - 1最优化问题的可行解及可行解集合 4 北京邮电大学硕士论文 遗传算法的基本原理及其应用 对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有 的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰 值的。随着研究的深入，发现要求解上述问题的精确解是n p 一完全问题，故转而 求近似最优解。求解最优解或近似最优解的方法主要有三种：枚拳法、启发式 算法和搜索算法。 随着问题种类的不同，以及规模的扩大，要寻找一种能以有限代价来解决 上述最优化问题的通用方法仍是一个难题。而遗传算法对解决这类问题提供了 一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。 遗传算法中，将n 维决策向量x = 【x 。，x ：，x 。】1 用n 个记号x ( i ；1 ，2 ，n ) 所组成的符号串x 来表示： x = 置x 2 以j x = 【x ix 2 ，矗 2 把每一个x 。看作一个遗传基因，它的所有可能取值称为等位基因，这样，x 就可 看做是由n 个遗传基因所组成的一个染色体。染色体x 也称为个体x ，对于每一 个个体x ，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表 现型x 的目标函数值相关联，x 越接近于目标函数的最优点，其适应度越大；反 之，其适应度越小。 遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的搜索是通 过对染色体x 的搜索过程来进行的，从而由所有的染色体x 就组成了问题的搜 索空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由m 个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗 传算法的过程也是一个反复迭代过程，第t 代群体记做p ( t ) ，经过一代遗传和 进化后，得到第t + l 代群体，它们也是由多个个体组成的集合，记做p ( t + 1 ) 。 这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应 度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个 体x ，它所对应的表现型x 将达到或接近于问题的最优解x o 生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。 北京邮电大学硕士论文 遗传算法的基本原理及其应用 与此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用 所谓的遗传算子作用于群体p ( t ) 中，进行下述遗传操作，从而得到新一代群体 p ( t + 1 ) 。 1 选择( s e l e c t i o n ) ：根据各个个体的适应度，按照一定的规则或方法， 从第t 代群体p ( t ) 中选择出一些优良的个体遗传到下一代群体p ( t + 1 ) 申。 2 交叉( c r o ss o v e r ) ：将群体p ( t ) 内的各个个体随机搭配成对，对每一对 个体，以某个概率( 称为交叉概率，c r o s s o v e rr a t e ) 交换它们之间的 部分染色体。 3 变异( m u t a t i o n ) ：对群体p ( t ) 中的每一个个体，以某一概率( 称为变异 概率，m u t a t i o nr a t e ) 改变某一个或某一些基因座上的基因值为其他 的等位基因。 2 1 2 遗传算法的运算过程 图2 2 所示为遗传算法的运算过程示意图。由图中可以看出，使用上述三 神遗传算子( 选择算子、交叉算子、变异算子) 的遗传算法的主要运算过程如下 所述。 步骤一：群体初如化。设置进化代数计数器f 卜0 ；随机产生n 个个体的初始种 群p ( 0 ) 。 步骤二：个体评价。利用目标函数计算p ( t ) 中各个个体适应度的值。 步骤三：选择运算。根据所设计的选择算子对各个个体进行选择操作，例如， 以z 窆，为概率( f l 为第i 个个体适应度的值) 对个体进行选择，共 i - i 选择n 次，若某个个体被选择到k 次( 0 = k = n ) ，则将其染色体复制k 个放入匹配集中。 步骤四：交叉运算。在匹配集中随机选取两个个体，并产生【o ，1 】间均匀分布的 伪随机教r 。，如果r i p 。( p 。为选定的交叉概率) ，则进行交叉，将交 叉后的两个个体加入新的解群中；否则，直接将这两个个体加入新的 解群。重复此过程n 2 次，使新的解群中包含n 个个体。 6 北京邮电大学硕士论文遗传算法的基本原理及其应用 步骤五：变异运算。对新的解群中每个个体，产生 0 ，i 】间均匀分布的伪随机数 r ：，如果r 。 p ，( p 。为选定的变异概率) ，则进行变异，并由伪随机数 程序确定发生变异的位置；否则不进行变异。群体p ( t ) 经过选择、交 叉、变异运算之后得到下一代群体p ( t + 1 ) 。 步骤六：终止条件判断。若迭代次数达到预先设定的值或收敛指标已经满足， 则以进化过程中所得到的具有最大适应度的个体作为最优解输出，停 止迭代；否则，转到步骤二。 遗传算法的运算过程示意图 图2 2 2 1 3 遗传算法的特点 遗传算法同其它传统的搜索方法相比，具有以下特点： ( 1 ) 遗传算法是处理参数集合的编码，而不是直接对参数本身。也就是说，其 操作是在给定字符串上进行的。 北京邮电大学硕士论文 遗传算法的基本原理及其应用 ( 2 ) 遗传算法的搜索是从问题解的编码组开始搜索，而不是从单个解开始。也 就是说，遗传算法同时搜索解空间中的许多点，而不是单个点，因而能够 快速全局收敛。 ( 3 ) 遗传算法使用目标函数值( 适应度) 这一信息进行搜索，而不需导数等其 它信息，因而具有广泛的适应性。 ( 4 ) 遗传算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定 规则，因此能搜索离散的有噪声的多峰值复杂空间。 ( 5 ) 遗传算法在解空间内进行充分的搜索，但并不是盲目的穷举或瞎碰( 评价 为选择提供了依据) 。因此其搜索时间和效率往往优于其它优化算法。 2 1 4 遗传算法的应用“” 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科和领域。遗传 算法的应用按其方式可分三大部分：基于遗传的优化计算、基于遗传的优化编 程、基于遗传的机器学习，分别简称为遗传计算( g e n e t i cc o m p u t a t i o n ) 、遗传 编程( g e n e t i c p r o g r a m m i n g ) 、遗传学习( 6 e n e t i c l e a r n i n g ) 。 大多数学科都面r 临复杂问题优化的困扰，遗传算法可能会带来一种新的希 望，当然，任何方法都有其特长和局限，因此在进行遗传算法应用研究时，要 明确如何用遗传算法，比传统方法有何优点，最好有具体的比较。 2 1 4 1 遗传计算 遗传计算是遗传算法最直接、最简单的应用，其应用面也最广。自d e j o n g 起，函数优化已成为经典的例子，常规采用二进制编程，目前使用实数编码的 研究增多。与函数优化问题区别最大的是组合优化问题，使用序号编码，使用 特殊的交换操作，下面根据应用领域介绍遗传算法的应用。 在自动控制学科中，m i c h a l e w i c z 等用浮点数编码的遗传算法研究了离散时 间最优控制问题，陈根社运用遗传算法进行了r i c c a t i 方程求解。m u r d o c k 等用 遗传算法分析了控制系统的鲁棒、稳定问题。k r is n a k u m a r 等用遗传算法进行了 航空控制系统的优化。p o t t e r 等运用遗传算法研究了数字p i d 控制器的调节。 k r is t i n s s o f t 和d u m a n t 深入研究了连续和离散的系统的参数辨识问题，用遗传 算法寻找零极度点。m a c l a y 等的研究也显示了基于遗传算法的参数辨识的潜力。 北京邮电大学硕士论文遗传算法的基本原理及其应用 f r e e m a n 等用遗传算法精调模糊逻辑控制器。p a r k 等研究了一种新的基于遗传 的模糊推理系统，用于产生优化参数集，获得了良好的性能。自动控制是近年 来遗传算法应用的活跃领域，由于遗传算法有天然的增强式学习能力，因此在 系统辨识、非模型控制系统设计，模糊控制器设计等方面的研究将会更为深入。 以上综述的研究大多只是原理性的，面对实际应用对象的很少，以后的研究将 会向实用推进。 在机器人学中，d a y i d o r 研究了把机器人当作模型未知的生物体，运用遗传 算法优化机器人的连续轨迹精度。y u n 和x i 研究了在机器人关节空间运用遗传 算法求最优轨迹。p e a r c e 用遗传算法学习机器人行为之间的协调参数。z h a o 等 运用遗传算法对带有操作手的移动机器人进行路径规划。p a r k e r 和g o l d b e r g 研 究了用遗传算法求解冗余度机器人的逆运动学方程。u e y a m a 和f u k u d a 等运用遗 传算法研究了细胞机器人系统的结构位形优化、运动规划及行为协调。机器人 是复杂的难以精确建模的系统，可以自然地类比为生物体，运用遗传算法对机 器人结构、运动行为进行优化的研究将更活跃和深入。 遗传算法的兴起伴随着神经网络的复活，令人新奇的是神经网络已成为遗传 算法应用最为活跃的领域。神经网络的应用面临着两大问题：神经网络拓扑结 构的优化设计与高效的学习算法。遗传算法已成为解决该两大问题的有力工具， 用于优化神经网络的结构权重和学习规则。y a o 给出了该方面的详细综述。该领 域的研究都显示了良好的性能和潜在的应用前景。 遗传算法已渗透到了许多学科，如工程结构优化、计算数学、制造系统、航 空航天、交通、计算机科学、通信、电子学、电力、材料科学等等。 2 1 4 2 遗传编程 遗传算法除了优化计算外还可以应用于更为复杂的情况，而要求强有力的编 码表达是最关键的。k a z a ，d e j o n g 等发展了遗传编程的概念。k a z a 运用l i s p 编程语言来编码，l i s p 符号串表示树，串中由特定问题域的各种函数和终端组 成，群体进行复杂超平面的搜索。k a z a 成功地把遗传编程用于人工智能、机器 学习、符号处理等。 遗传编码是遗传算法应用的深入，目前还不成熟，许多问题有待解决。 9 北京邮电大学硕士论文遗传算法的基本原理及其应用 2 1 4 3 遗传学习 遗传学习系统是由遗传算法为内核构成的增强式学习系统，一般地，群体 由产生式规则组成，利用和环境的接触来学习、完成给定任务。h o ll a n d 奠定了 基于遗传的机器学习的框加，h o 【l a n d 和r e i t m a n 发展了第一个遗传学习系统， 称谓认知系统一号，c s i 成为g l 后继研究的模板，又称为分类器系统。在此基 础上，s m i t h 发展了l s 一1 ，s c h a f f e r 发展了l s - 2 。遗传学习已被应用于许多领 域，在机器人学中，w i ls o n 运用分类器系统进行了传感器一马达的协调研究， 然后发展了a n i m a t t 系统，进行模拟人工生物在环境中自主适应的研究，d o r i g o 结合遗传学习和基于行为的机器人进行了简单的、模拟生物在变化的环境中学 习趋光和避热两种行为模式的研究。遗传学习的其它应用有：模式识别和工程 等等。遗传学- - j 本身的研究也正在深入。 2 2 基本遗传算法 2 2 1 基本遗传算法的形式化定义 基本遗传算法可以定义为一个8 元组： s g a = ( c ，e ，p o ，m ，中，f ，甲，t ) 式中 c - - 一个体的编码方法； e - - 一个体适用度评价函数； p o 一一初始群体； m 一一群体大小： 中一一选择算子； r 一一交叉算子； 掣一一变异算子； t 一一遗传运算终止条件。 o 北京邮电大学硕士论文遗传算法的基本原理及其应用 2 2 2 基本遗传算法描述 下图2 3 给出了基本遗传算法的伪代码描述。 基本遗传算法的伪代码描述 p r o c e d u r es g a b e g i n i n i t i a l i z ep ( o ) t = o ： w h i l e ( t o 、1 0 ，矿，( ) + c , m 0 其中，c 。是一个较小的数，可以用下面方法选取： 1 预先指定的一个较小的数。 2进化到当前代为止的最小目标函数值。 北京邮电大学硕士论文遗传算法的基本原理及其应用 3 当前或最近几代群体中的最小目标函数值。 方法二：对于求目标函数最小值的优化问题，变换方法为： f ( 舶：j x 一厂( x ) ，i f m ) 、【0 ，i ff ( x ) c 眦 其中c ，是一个较大的数，可以用下面方法选取： 1 预先指定的一个较大的数。 2 进化到当前代为止的最大目标函数值。 3 当前或最近几代群体中的最大目标函数值。 2 2 4 2 比例选择算子 比例选择算子的具体执行过程是： 1 先计算出群体中所有个体的适应度的总和。 2 其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传至, j - f 一代群体中的概率。 3 最后再使用模拟轮盘赌操作( 即0 1 之间的随机数) 来确定各个个体被 选中的次数。 2 2 4 3 单点交叉算子 具体执行过程如下： 对群体中的个体进行两两随机配对。若群体大小为m ，则共有j m 2l 对 相互配对的个体组。其中l x 2l 表示不大于x 的最大整数。 对每一对相互配对的个体，随机设置某一基因位之后的位置为交叉点。 若染色体的长度为n ，则共有( n 一1 ) 个可能的交叉点位置。 对每一对相互配对的个体，依设定的交叉概率p 。在其交叉点处相互交换 两个个体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示意如下所示： a ：1 0 1 1 0 1 1 1 1 0 0 单点交叉a ：1 0 1 1 0 1 1 1 1 1 1 b ：0 0 0 1 1 1 0 0 1 1 1b 。：0 0 0 1 1 1 0 0 0 0 交叉点 北京邮电大学硕士论文 遗传算法的基本原理及其应用 2 2 4 4 基本位变异算子 基本位变异算子的执行过程如下： 对个体的每一个基因位，依变异概率p 。指定其为变异点。 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值 来代替，从而产生出一个新的个体。 基本位变异运算的示意图如下所示： 爿：1 0 l 0 | 1i o l 0 1 0 ! 垂! 堕垡墼爿：1 0 1 q01 0 1 0 1 0 变异点 2 3 遗传算法的数学理论 2 3 1 模式定理 定义1 ：模式表示一些相似的模块，它描述了在某些位置上具有相似结构特 征的个体编码串的一个子集。 以二进制为例，个体是d j - - - 值字符集v = ( 0 ，1 ) 中的元素所组成的一 个编码串，而模式却是由三值符号集v + = ( 0 ，1 ，) 中的元素所组成的一 个编码串，其中“”表示通配符，它既可是1 ，也可是“0 ”。 定义2 ：在模式h 中具有确定基因值的位置数目称为该模式的模式阶，记为 o ( h ) 。 定义3 ：模式h 中第一个确定基因值的位置和最后一个确定基因值的位置之 间的距离称为该模式的模式定义长度，记为艿( h ) 。 设进化到第t 代时， - 3 前群体p ( t ) 中能与模式h 匹配的个体数( 样本数) 记为 m ( h ，t ) ，下一代群体p ( t + 1 ) 中能与模式h 匹配的个体数( 样本数) 记为m ( h ，t + 1 ) 。 基本遗传算法在经过选择算子、交叉算子和变异算子连续作用下，m ( h ，t + 1 ) 和 m ( h ，t ) 的关系如下： 螂+ 1 ) 冽鼢等 1 一见罟_ d ( 毋川 式中 北京邮电大学硕士论文 遗传算法的基本原理度其应用 f ( h ，t ) 是第t 代群体中模式h 所隐含个体的平均适应度； f ( f ) = f ( t ) m 是第t 代群体的平均适应度。 p 。是交叉概率，p 。是变异概率。 由上式可得以下模式定理： 遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义长 度，并且平均适应度高于群体平均适应度的模式将按指数级增长。 2 3 2 积木块假设与遗传算法欺骗问题 积木块假设：个体的基因块通过选择、交叉、变异等遗传算子的作用，能 够相互拼接在一起，形成适应度更高的个体编码串。 模式定理说明了积木块的样本数是呈指数级增长，即说明了用遗传算法寻 求最优样本的可能性，积木块假设说明了用遗传算法求解各类问题的基本思想， 即通过基因块之间的相互拼接能够产生出问题更好的解。 遗传算法的欺骗问题：( 遗传算法的早熟问题) 通过遗传算法求解易于陷入 局部最优，到目前为止有很多改进方法，并且对于具体的问题可以设计具体的 遗传算子来加以解决。 2 3 3 隐舍并行性 遗传算法处理的有效模式总数约与群体规模m 的立方戍正比。也就是说， 虽然在进化过程的每一代中只处理了m 个个体，但实际上并行处理了与m 的立 方成正比例模式数。这种并行处理过程有别于一般意义下的并行算法的运行过 程，是包含在处理过程内部的一种隐合并行( i m p l i c i t f a r a l l e l is i l l ) 性。通过 这种隐含并行性，使得我们可以快速地搜索出一些比较好的模式。 2 3 4 遗传算法的收敛性分析 定理1 基本遗传算法收敛于最优解的概率小于1 。 定理2 使用保留最佳个体策略的遗传算法能收敛于最优解的概率等于1 。 由定理1 知，基本遗传算法收敛于最优解的概率小于1 ，其应用可靠性就值 得怀疑，必需在理论上确保该算法能收敛于最优解，定理2 改进的遗传算法， 即保留最佳个体策略的遗传算法就可以从理论上确保能够收敛于最优解，也为 实际中搜索最优解的过程提供了保证。 5 北京邮电大学硕士论文 遗传算法的基本原理及其应用 2 3 5 适应度函数的自相关分析 定义1 在环境e 下策略s 的在线性能x 。( s ) 定义为： 1r x a s ) = 专无( f ) t = l 式中，f 。( t ) 是在环境e 下第t 时刻的平均目标函数值或平均适应度。 由上述定义的在线性能指标表示了算法从开始运行一直到当前为止的时间 段内性能的平均值，它反映了算法的动态性能。 定义2 在环境e 下策略s 的离线性能x 。( s ) 定义为： z ( s ) = 专f ( f ) 1 k i 式中，f ( f ) 是在环境e 下 o ，t 时间段内最好的目标函数值或最大的适应度。 由上述定义的离线性能指标表示了算法运行过程中各进化代的最佳性能值 的累积平均，它反映了算法的收敛性能。 经过分析和计算有以下重要结论： 结论1 群体的规模越大，遗传算法的离线性能越好，越容易收敛。 结论2 规模较大的群体，遗传算法的初始在线性能较差；而规模较小的群 体，遗传算法的初始在线性能较好。 结论3 虽然变异概率的增大也会增加群体的多样性，但它却降低了遗传算 法的离线性能和在线性能，并且随着变异概率的增大，遗传算法 的性能越来越接近于随机搜索算法的性能。 结论4 使用保留最佳个体模型或期望值模型的遗传算法比基本遗传算法 的性能有明显的改进。 结论5 对于广义交叉算子，随着交叉点数的增加会降低遗传算法的在线性 能和离线性能。 2 4 a t # 算法的发展动态 遗传算法是目前研究得最为广泛的一类模拟进化算法。其基本思想源于六 十年代。当时j h o t a n d 在研究机器学习过程中，提出了一种借鉴生物进化机 北京邮电大学硕士论文 遗传算法的基本原理及其应用 制的所谓自适应机器学习方法，19 7 5 年他发表( ( a d a p t a ti o n i 1 1n a t ur a la n d ar t i f l c i a l s y s t e r n s ) ) 的专著，如今发展成为标准形式的遗传算法。遗传算法 的最初提出及其早期研究均在非数值计算方面( 作为一种自适应机器学习方 法) ，而近几年的研究才向人们展示了它对于解全局优化问题的成功应用。， 遗传算法自提出，特别是八十年代中期以来，已得到广泛研究与应用。其 研究的内容大体集中在以下几个方面： 2 4 1 有关算法随机搜索机理的研究 遗传算法是通过作用于一个初始种群，而循环执行复制、杂交、变异及选 择过程的随机迭代，故阐明如此简单的循环操作如何有效搜索整个编码空间以 达到全局优化之目的有特别重要的意义。在这方面，j t t o l l a n d 等人发展的所 谓“模式( s c h e m a ) 理论”引人注目。一个模式是指编码空间( 即所使用的染色体 的全体。当应用l 位二进制串编码时，该空间为 o ，1 。) 中具有相同构形 ( c o n f i g u r a t i o n ) 的编码的子集。所谓具有相同构形是指：这个子集中诸编码 串在某些位上具有相同的码值。例如，在编码空间 o ，1 l 。中，集合 m = ( 1 0 1 0 1 + 0 ) ：+ 表示o 或1 是一个模式。给定一个模式，一个编码称为与该模式相匹配，如果在模式的确 定位上，此编码的值与模式的值相同，例如，编码( 10 0 0101 100 ) 、 ( 1010 1010 0 0 ) 均与上述所指定的模式m 相匹配。任一给定编码必与许 多模式相匹配。模式理论的核心在于：遗传算法能够有效搜索的根本原因是， 它充分利用了模式所描述的编码之间的相似性，虽然算法仅作用于n 个编码组 成的种群，但这n 个编码实际上包含o ( n ，1 阶个模式的信息。这一性质常被称作 是遗传算法的隐含并行性( i m p l i c i tp a r a l l i s m ) 。 模式理论可以较好的解释遗传算法的搜索机制。对于任一模式，定义它的 阶为模式中确定码值的个数，而定义它的长度为模式中第一个确定码值位与最 后一个确定码值位之间的差，则h 0 1 l a n d 证明了如下的模式定理：“具有短长度 的、低价的、适应性在群体平均之上的模式将在遗传算法中以指数增长率在子 代中被采样”。 北京邮电大学硕士论文 遗传算法的基本原理及其应用 2 4 2 有关算法的全局最优性( 或收敛性) 研究 生物进化的“趋势向上”性似乎应蕴舍遗传算法的最终收敛性，这一研究 的目的在于从理论上对这一事实给出证明。a e e i b e n 等( 1 9 9 1 ) 首先证明了 遗传算法( 一个更为抽象的形式) 在e l i t is t 选择情形下的收敛性： p ( 1 i m 以n s o ) = 1 ( 其中x 。表示算法所产生的第n 代种群，s 。表示问题( p ) 的最优解集) ；g r u d o l p h ( 1 9 9 4 ) 在l i m p ( z 。= ，) = 1 的收敛意义下( 其中乙代表算法所产生的 第n 代种群中的最优适应值，厂+ 为问题( p ) 的最优函数值) ，证明了如果选 择算子采用自然选择策略，则算法不收敛，而如果对算法采取记录每一代中最 佳个体的策略，则改进的算法收敛；张讲社等( 1 9 9 6 ) 对繁殖概率的赋值采取 “模拟退火选择规则”的遗传算法证明了其收敛性。与算法收敛性紧密相关的 一个问题是遗传算法的过旱收敛( p r e m a t u r ec o n v e r g e n c e ) 。它出现在算法还 未达到全局最优情形而不再产生适应性更强的后代。研究表明：遗传算法的过 早收敛主要由杂交算子引起。在模式空间中存在大量所谓的早熟集( p r e m a t u r e s e t ) ( 即在选择与杂交算子复合作用下的不变集) ，而在杂交算子作用下，遗 传算法总以非零概率“撞入”早熟集。由于早熟集的吸收性，从而使算法产生 过旱收敛。 2 4 3 有关染色体编码格式的讨论 遗传算法的作用对象是优化变量的染色体编码( 即实变量的某种离散化近 似) 。如令e 表示n 的编码空间( 即n 中所有实变量编码的全体。通常，e ： o ，1 1 。， 即采用l 位二进制编码) ，则求解问题( p ) 的遗传算法实质上是通过寻求组合 优化问题 ( p ) ： m a x j ( y ) ：y e 1 的最优解来达到求解问题( p ) 的目的( 从这个意义讲上，遗传算法的特征相似 于求解连续性问题的离散方法) 。采取编码方式求解问题( p ) 究竟是利大还是 弊大，至今仍存在许多争论。但通常认为：采用编码方式( 特别是二进制编码) 有以下优点：a ) 可很好地指导搜索，使得有关某种结构的个体容易生存，以产 1 8 北京邮电大学硕士论文 遗传算法的基本原理及其压用 生适应性更强的后代；b ) 使算法具有隐合并行性，使在相对少量的种群上进行 的操作实质上隐含着大范围的搜索。采用编码方式的缺陷是：由于连续问题( p ) 化归到组合问题( p ，) 求解，使算法的求解精度受到很大影响。这些优点和缺点当 遗传算法用于( 组合) 优化问题的求解时均有明显体现。 2 4 4 遗传算法研究热点 上述有关遗传算法研究的几个方面应该说还是相当初步的。对它的进一步 深入探讨正构成当前计算智能研究的“热点”。概括地说，当前有关遗传算法 的研究兴趣主要集中在以下几个方面： 夺有关算法的理论基础：这特别包括遗传算法的收敛性、收敛速度估计、过早 收敛的机理探索与预防、杂交算子的几何意义与统计解释、参数设置( 如种 群规模、编码长度等) 对算法效率的影响等方面。我们认为：有关算法的收 敛速度估计是当前特别值得化大力气加以探讨的问题( 目前尚无好的结果) ， 因为它能从理论上对遗传算法的任何修正形式，提供判别标准，以指明改进 遗传算法效能的正确方向。 夺有关算法与其它优化技术的比较与融合：作为已知较为成熟的全局优化算法 一模拟退火方法，它与遗传算法的结合已有不少研究。然而，充分利用遗传 算法的大范围群体搜索性能与已知局部优化方法的快速收敛性来产生有效 的全局优化方法，研究仍不多见。我们感到，这种整体搜索策略与快速局部 优化方法的混合是从根本上提高遗传算法计算效能的措施。这方面还需要做 大量的理论分析与实验研究。 令有关遗传算法的并行化研究：遗传算法的群体、随机搜索特征使它有明显的 可并行化特性。设计它的各种并行化执行策略及其建立相应并行算法的理论 基础均是具有重要意义的工作。 夺遗传算法在人工神经网络、机器学习、复杂组合优化问题求解、金融市场分 析和预测、专家系统等领域已有广泛应用。一般说，根据具体应用领域来有 效改进遗传算法是可能的和实际的( 而相反，泛泛地对一般问题研究显得极 其困难) 。所以，针对具体应用问题，深化研究遗传算法( 如参数设置、遗 传算子构造等) 是当前特别值得提倡的工作。 9 北京邮电走学硕士论文 通信网相关理论简介 第三章通信网相关理论简介 3 1 通信网组成要素 通信网是通信系统的系统，因而通信系统的部件必然是通信网的部件，故 通信网必然包括终端机和传输线路，终端机又包括发端机和收端机。通信系统 的简单叠加只能形成不经济的全联结网，网中必须有交换或转接设备。因而通 信网必须还包括交换设备。因此通信网的组成部分主要包括三种：一是终端机， 二是传输线路，三是交换设备。但只有这些设备，往往还不能形成一个完善的 通信网，尤其是自动化程度较高而人工干预较少的网。我们把上述部件称为构 成通信网的“硬件”，则必须还需要一套相应的“软件”。这套“软件”指的是 各种规定，包括信令、协议和各种标准及各种相关算法。没有这些“软件”要 达到对通信网的各种质量指标是不可想象的。从某种意义上来说，这些“软件” 是构成通信网的核心，决定网的性能，它们使用户之间、用户和网络资源之间 和各个转接点之间有共同的“语言”，使网能够合理地运行和正确地被控制，达 到任意两介用户之间能快速接通和相互交换信息。质量的一致性、运转的可靠 性以及信息的透明性等要求也必须通过“软件”才能够得到满足。本文对通信 网的“硬件”就不加介绍，只简单介绍一下本文所涉及到的一些质量指标。首 先是经济性，即信号在信道上传输所需的费用。其次是时延，即信号在该信道 上传输所需要的时间，包括排队时间和传输时间等。 3 2 通信网结构 通信网的拓扑结构是一个很重要的问题，它不但影响网的造价和维护费用， 也与满足对网的各种要求起着重要的作用。这是通信网的规划和设计中第一层 次的问题。通信网的结构是在发展的，但传统的网都是转接式的，包括电路转 接和信息转接，是由交换点和传输线路构成。从数学模型来说，这是一个图论 北京邮电太学硕士论文 通信网相关理论简介 问题。下面就介绍一下本文算法所需涉及到的一些图论基本知识。 图论作为组合数学的分支，近年来得到较快的发展，已e l 益广泛地应用于 各种网路、电路分析、可靠性设计、集成电路设计、以及计算机领域等。本节 将从本文的需要出发简要介绍图论的基础知识。 3 2 1 图的基本定义 设有端集：v = ( v l ，v 2 ，a ，v 。) 和边集： e = 霸，p 2 ，a ，e 。 当边集e 是端集v 中二个元的关系r v v 叶e 时，则v 和e 组成图g ，写成 g = 矿，e ) 根据端间关系的性质，可以将图分为有向图和无向图。当v ，和v ，有某种关 系等价于v 和v 有某种关系，这图就称为无向图；反之，则称为有向图。为了 方便起见，本文只讨论无向图。 3 2 2 有权图 上述图的定义中，只规定了拓扑特性而并不考虑具体几何特性。在实际问 题中，往往不能完全排除这些特性，就需对端和边赋予某些实值，这样的图就 称为有权图。边和端上所赋的值称为权值或权。一条边和一个端的权值可以是 多个，用来表示几种性质。对于通信网，端代表交换局，边代表信道；端的权 值可以为该局的造价，交换容量等，边的权