毕业答辩-遗传算法在网络路由选择中的应用.ppt

智能算法在网络路由选择中的应用,导师：答辩人：,本文的主要内容,组播QoS路由选择模拟退火算法遗传算法基于组播QoS路由的遗传模拟退火法,前言,对于QoS组播路由问题的研究大都采用启发式算法，由于目前存在的算法都具有较高的时间复杂度而不能满足实际应用的需求。本文将遗传算法与模拟退火算法相结合研究了一种遗传模拟退火算法，利用该算法作为求解QoS组播路由问题的优化算法.,一、组播QoS路由选择,路由选择QoS约束QoS组播路由数学模型,1.1路由选择,路由选择是发生在互联网络(如通过路由器连接的独立网络)上的数据分组转发过程，如下图所示。,1.2QoS约束,QoS即服务质量(QualityofService)RFC2216定义为：用带宽、分组延迟和分组丢失率等参数描述的关于分组传输的质量。业务QoS是应用业务对网络传输服务提出的一种可度量的要求，具体可以量化为带宽、延迟、延迟抖动、丢失率、吞吐量、花费等性能指标。,1.3QoS组播路由的数学模型,QoS组播路由问题可定义为：网络图G=(V,E)，多播源点sV，多播目的节点集D=d1,d2,dn，diV，i=1,2,n，QoS约束条件为端到端时延delay(e)：ER+，时延抖动jitter(e)：ER+（非负实数集），代价cost(e)：ER+，丢包率loss(e)：ER+和可用带宽bandwidth(e)：ER+。,1.3QoS组播路由的数学模型,寻找一棵多播树T(s,D)，满足：(1)时延约束：delay(P(s,di)DTi(2)时延抖动约束：jitter(P(s,di)DJi(3)丢包率约束：loss(P(s,di)PLi(4)可用带宽约束：bandwidth(P(s,di)Bi(5)代价优化：所有满足(1)到(4)约束的多播树，cost(T(s,D)最小其中，P(s,di)为多播树T(s,D)上源节点s到目的节点di的路径。Bi是带宽约束，DTi，DJi，PLi分别是目的节点di的时延、时延抖动和丢包率约束。,二、模拟退火算法,模拟退火算法原理参数控制,2.1模拟退火算法原理,模拟退火算法来源于固体退火原理，将固体加热至充分高的温度，再让其渐渐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而渐渐冷却时粒子趋于有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。,2.2模拟退火的步骤：,(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L(2)对k=1，L做第(3)至第6步。(3)产生新解S。(4)计算增量t=C(S)-C(S)，其中C(S)为评价函数。(5)若t0，然后转第2步。,2.3模拟退火参数设置,模拟退火算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点：(1)温度t的初始值设置问题；(2)退火速度问题；(3)温度管理问题；,三、遗传算法,简介原理,3.1遗传算法简介,遗传算法（GeneticAlgorithm）是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响专著AdaptationinNaturalandArtificialSystems，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。,3.2遗传算法原理,遗传算法是具有“生成+检测”（generate-and-test）的迭代过程搜索方法。遗传算法是一种群体型操作，该操作以群体中的所有个体为对象，选择、交叉、变异是遗传算法三个主要操作算子。遗传算法中包含了以下5个基本要素：(1)参数编码；(2)初始种群设定；(3)适应度函数的设计；(4)遗传参数设计；(5)控制参数设定(主要是指种群大小和遗传概率等)；,遗传算法的基本流程如下：(1)先确定待优化的参数大致范围，然后对搜索空间进行编码；(2)随机产生包含各个个体的初始种群；(3)将种群中各个个体解码成对应的参数值，用解码后的参数求代价函数和适应度函数，运用适应度函数评估检测各个个体适应度；(4)对收敛条件进行判断，如果已经找到最佳个体,则停止，否则继续进行遗传操作；(5)进行选择操作,让适应度大的个体在种群中占有较大的比例,一些适应度较小的个体将会被淘汰；(6)随机交叉,两个个体按一定的交叉概率进行交叉操作，并产生两个新的子个体；(7)按照一定的变异概率变异，使个体的某个或某些位的性质发生改变；(8)重复步骤(3)至(7)，直至参数收敛达到预定的指标。,四、基于组播QoS路由的遗传模拟退火法,混合策略参数设计,4.1混合策略,遗传模拟退火算法混合策略可描述为：通过遗传算法对初种群进行优化，模拟退火算法对遗传算法得到的进化种群进行进一步优化，并将优化后的种群作为父代种群返回给遗传算法进行遗传操作。遗传模拟退火算法在温度较高时表现出较强的概率突跳性，体现为对种群的“粗搜索”，温度较低时演化为趋化性局部搜索算法，体现为对种群的“细搜索”。这种混合不仅是算法结构上的结合，而且是搜索机制和进化思想上的相互补充，为较好解决复杂优化问题提供了有利的途径。,GSA流程图,4.2编码及初始种群的设定,4.2.1编码策略本算法采用路径编码表示法，从备选路径集中选择一条路径作为一个基因，可表示为T=(T1,T2,Ti,Tm)4.2.2种群初始化不同的染色体作为初始种群为G=G1,G2,Gk,Gpop_size,4.3适应度函数的设计,式中，为染色体的目标函数值(费用函数)，f(T)min为当前代进化种群中最小目标函数值，t为温度参数。,4.4遗传参数设计,4.4.1选择操作本算法采用赌轮选择法。设种群大小为M，个体i的适应度为Fi，则个体i被遗传到下一代种群的概率Pi为：,4.4.2交叉和变异操作,交叉概率Pc和变异概率Pm的计算公式为：,4.4.3遗传操作执行过程,(1)选择操作：根据当前代染色体的适应度函数值按赌轮选择方法选择两个父代染色体。(2)交叉操作：根据当前代染色体适应度函数值，计算这两个父代染色体的交叉概率Pc，产生0,1之间的随机数r,当rPc时，按上面的交叉操作策略执行交叉操作，生成一个新的子代染色体；否则直接把两个父代个体中适应度高的个体作为子代染色体保留。(3)变异操作：根据当前代染色体适应度函数值，计算由交叉操作生成的子代染色体的变异概率Pm，产生0,1之间的随机数r，当rPm时，按上面的变异操作策略，对交叉操作生成的染色体执行变异操作，生成一个新的子代染色体；否则直接保留由交叉操作生成的染色体为子代染色体。,4.5模拟退火参数设计,4.5.1初始温度的选取在本章算法中，取=f(T)0max-f(T)0min，式中f(T)0max、f(T)0min分别为初始种群中最大目标函数值和最小目标函数值。,4.5.2温度更新函数的选取,即温度的下降方法，用于在外循环中修改温度值。下降总次数法：该方法中式中t0为初始温度，K为算法温度下降的总次数。这个下降方法的优点是易于操作，而且可以简单地控制温度下降的总步数，它每一步下降的温度度数相等。这两种方法原理简单，易于实现。在本章算法中，采用第一种温度下降方法。,4.5.3邻域解集的构造方法,即状态产生函数，用于实现对旧状态进行小扰动产生新状态的过程。邻域解的构造过程采用“路径交换策略”，具体操作步骤如下：对于当前解xnow，随机选择一个目的节点diM，删除xnow中从源节点s到di的路径，形成一棵树xtmp，然后从目的节点di对应的备选路径集中选择s到di满足时延约束的其它路径加入到树xtmp中，构成新树xnow，则xnow成为当前解xnow的一个邻域解。,4.5.4状态接受函数,式中，Pt是当前解i到新解j的转移概率，fi是当前解i的函数值，fj是新解j的函数值，t是当前等温过程的温度，即控制参数，tR+。,