路由.doc

..页眉.. 页脚. ABSTRACT : 南京邮电学院宋铜铃在通信需求量飞速增长的今天, 对网络的通信能力的要求也与日俱增。近年来, 对网络优化的探讨也在不断进行之中。而本课题所讨论的智能组合优化技术也是一种有益的尝试。 1. 网络优化的数学基础本课题的核心任务是通过各种手段(包括选择最佳路由,合理分配流量等) ,使网络具有更小的延时和可靠性。在此,有必要叙述一下网络时延的问题。对于采用分组交换方式的 网络来说, 其中每条链路的信息交换过程都可以等效为一个 M/M/1 排队问题。即分组的到达和离去都是一个马尔可夫( Markov ) 过程。它们服从泊松分布率。依据排队论的结论,可知一个链路每分组平均时延 T t为 T t= iiC??? 1 (s/ 分组) 式中? 1 为平均分组长度( bit/ 分组), C i 为链路容量( bit/s ), i?( 分组/s )为分组到达率。那么该条链路的平均对长 T L为 T L= ii iC????式( 1-1 ) 2. 网络时延的数学建模..页眉.. 页脚. 图1 美国 2 实验性主干网 vBNS 本课题的研究对象如图 1 所示。它是一个 12 节点、 17 条链路的分组交换网。对于其中每条链路 l 来说, 都有可能承担网络中任何两个结点之间的信息交换任务。因此, l 上的到达率为? r rlrX??,当某对节点 p 的路由 r 包含链路 l 时, rl?为1 ,否则为 0 。当节点对 p 选择路由 r 为其信息交换路由时, X r为1 ,否则为 0 。本网络的优化问题可建立数学公式如下: 最小化 Z ip=??????? LlRr r rlri Rr r rlrXC XT?????1 式( 2-1 ) 约束于??? Rr r rlriXC???10或? rl?10或? rX1 11???????njjjXXX?(设某条节点对有 n 条候选路由) 其中: L 为链路集合 R 为候选路由集合 r?为与 r 有关的节点对 p 的分组到达率 T 为网络总的分组到达率, T???? Rr r?。可以看出, 这个问题是一个多约束条件的 0-1 规划问题, 属于组合优化中的 NP 完备问题, 为了比较有效地找出最优解, 本文采用了遗传算法。下面将重点介绍遗传算法的有关原理。 3. 遗传算法遗传算法是一类借鉴生物界自然选择和自然遗传机制的并行随机群体搜索算法, 主要特点是群体搜索策略和群体中个体之间的信息交换, 搜索不依赖于梯度信息。它自身所隐含的并行性以及本质上的鲁棒性, 使其在解决复杂问题的搜索优化方面优于传统的算法, 具有广阔的应用前景。遗传算法是基于达尔文进化论的优胜劣汰、自然选择、适者生存和物种遗传思想的优化、搜索算法。遗传算法的基本模型如下: ..页眉.. 页脚. 图2 简单噶 GA 算法流程图其中, 选择是按照适者生存、优胜劣汰的原则,使适应度较大的个体有较大的概率为下一代提供模式。交叉是指在优等群体中按照一定的概率随机地选择匹配对, 随机的互换部分串位, 形成新的后代, 变异是指以一定的概率随机地改变串中某个或某几个位置的值。适应度是可行解的结合程度的评估, 这种评估需要考虑目标函数和边界约束条件的影响, 通常将边界条件化为惩罚值加在目标函数之上。适应度是对问题可行解优劣程度的直接评估。从本质上来说,遗传算法是一种优化策略,这是它最直接的应用领域。遗传算法进化的对象是问题参数集的编码,不是参数本身。这可以减少对不必要的冗余信息的处理, 降低算法复杂度。遗传算法是一种并行式算法, 具有隐式并行性, 能同时对搜索空间的多个解进行评估。它的随机搜索不是完全随机的,而是有导向的。 3 .1 遗传算法的模式定理开始产生初始群体评估个体适应度选择交叉变异遗传操作是否满足迭代停止条件? 是结束否..页眉.. 页脚. 在介绍模式定理之前,有必要先介绍几个有关模式的概念。 1. 模式:由字符集{0,1, *} 构成的字符串称作模式。其中 0、1 为确定信息, * 为不确定信息,可能是 0或 1。 2. 模阶: 模式中包含 0和1 字符的数目称作模式的阶, 简称模阶。记为 o(H) 。 3. 模长: 模式中确定性信息所在位置之间的最大距离称作模式的定义长度。简称模长。记为?(H) 。 4. 范式: 模式中* 可取 0或1,将“*”确定化后所得的字符串称作模式 H 的范式。对于模式 H 来说,每次交叉使之破坏的概率为 1 )(?l H?,l 为串长。若遗传操作中交叉概率为 P c ,则其遭到破坏的概率为 1 )(?l HP c?。因为相同模式之间进行交叉不会破坏该模式。因此, 对于模式 H 的破坏, 也依赖于群体中非 H 模式的个体数量。因为在遗传操作中,个体生存的概率与其适应度高低是呈正比的,因而模