路由.doc

ABSTRACT:
南京邮电学院宋铜铃
在通信需求量飞速增长的今天,对网络的通信能力的要求也与日俱增。近年来,对网络优化的探讨也在不断进行之中。而本课题所讨论的智能组合优化技术也是一种有益的尝试。
网络优化的数学基础
本课题的核心任务是通过各种手段(包括选择最佳路由,合理
分配流量等),使网络具有更小的延时和可靠性。在此,有必要叙述一下网络时延的问题。
网络来说,其中每条链路的信息交换过程都可以等效为一个M/M/1排队问题。即分组的到达和离去都是一个马尔可夫(Markov)过程。它们服从泊松分布率。依据排队论的结论,可知一个链路每分组平均时延Tt为
Tt= (s/分组)
式中为平均分组长度(bit/分组),Ci为链路容量(bit/s),(分组/s)为分组到达率。那么该条链路的平均对长TL为
TL= 式(1-1)
网络时延的数学建模

图1 2实验性主干网vBNS
本课题的研究对象如图1所示。它是一个12节点、17条链路
的分组交换网。对于其中每条链路l来说,都有可能承担网络中任何两个结点之间的信息交换任务。因此,l上的到达率为,当某对节点p的路由r包含链路l时,为1,否则为0。当节点对p选择路由r为其信息交换路由时,Xr为1,否则为0。本网络的优化问题可建立数学公式如下:
最小化
Zip= 式(2-1)
约束于
(设某条节点对有n条候选路由)
其中:L为链路集合
R为候选路由集合
为与r有关的节点对p的分组到达率
T为网络总的分组到达率,T。
可以看出,这个问题是一个多约束条件的0-1规划问题,属于组合优化中的NP完备问题,为了比较有效地找出最优解,本文采用了遗传算法。
下面将重点介绍遗传算法的有关原理。
遗传算法
遗传算法是一类借鉴生物界自然选择和自然遗传机制的并行随机群体搜索算法,主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。它自身所隐含的并行性以及本质上的鲁棒性,使其在解决复杂问题的搜索优化方面优于传统的算法,具有广阔的应用前景。
遗传算法是基于达尔文进化论的优胜劣汰、自然选择、适者生存和物种遗传思想的优化、搜索算法。
遗传算法的基本模型如下:

开始
产生初始群体
评估个体适应度
选择
交叉
变异
遗传操作
是否满足迭代停止条件?
是
结束
否
图2 简单噶GA算法流程图
其中,选择是按照适者生存、优胜劣汰的原则,使适应度较大的个体有较大的概率为下一代提供模式。交叉是指在优等群体中按照一定的概率随机地选择匹配对,随机的互换部分串位,形成新的后代,变异是指以一定的概率随机地改变串中某个或某几个位置的值。适应度是可行解的结合程度的评估,这种评估需要考虑目标函数和边界约束条件的影响,通常将边界条件化为惩罚值加在目标函数之上。适应度是对问题可行解优劣程度的直接评估。
从本质上来说,遗传算法是一种优化策略,这是它最直接的应用领域。遗传算法进化的对象是问题参数集的编码,不是参数本身。这可以减少对不必要的冗余信息的处理,降低算法复杂度。遗传算法是一种并行式算法,具有隐式并行性,能同时对搜索空间的多个解进行评估。它的随机搜索不是完全随机的,而是有导向的。
遗传算法的模式定理
在介绍模式定理之前,有必要先介绍几个有关模式的概念。
模式:由字符集{0,1,*}构成的字符串称作模式。其中0、1为确定信息,*为不确定信息,可能是0或1。
模阶:模式中包含0和1字符的数目称作模式的阶,简称模阶。记为o(H)。
模长:模式中确定性信息所在位置之间的最大距离称作模式的定义长度。简称模长。记为(H)。
范式:模式中*可取0或1,将“*”确定化后所得的字符串称作模式H的范式。
对于模式H来说,每次交叉使之破坏的概率为,为串长。若遗传操作中交叉概率为Pc,则其遭到破坏的概率为。因为相同模式之间进行交叉不会破坏该模式。因此,对于模式H的破坏,也依赖于群体中非H模式的个体数量。因为在遗传操作中,个体生存的概率与其适应度高低是呈正比的,因而模式H由于交叉操作而被破坏的概率为,其中为非H模式个体适应度之和,为所有个体适应度之和。设遗传操作的变异概率为,则模式H中的确定位不遭破坏的概率为,由于H中共有位确定位,因而模式不遭变异性破坏的概率为。
综上所述,我们可以得出修正的模式定理:
式(3-1)
其中表示在代种群中隐含模式H串的个数。
式(3-1)反映出模式增长的两个主要因素:(1)个体的适应度高低;(2)个体在群体中的数量。


编码
在进行遗传操作之前,首先要对所求问题的解进行编码。
一般来说,编码应遵循一下原则:
编码长度尽可能短;