遗传算法在网络路由选择中的应用毕业设计说明书.doc

大庆石油学院本科生毕业设计（论文）摘 要随着 Internet 的发展，多媒体通信和分布式环境下的协同工作等应用促进了组播通信的发展。服务质量（QoS）组播路由带有 QoS 约束参数。目前，对于 QoS 组播路由问题的研究大都集中在采用启发式算法进行求解，然而由于这些算法都具有较高的时间复杂度而不能满足实际应用的需求。本文将遗传算法与模拟退火算法相结合研究了一种遗传模拟退火算法，利用该算法作为求解QoS 组播路由问题的优化算法，主要研究了QoS 组播路由问题。对适应度函数进行调整，改进了交叉和变异操作，并结合模拟退火算法，用模拟退火算法对遗传操作的个体进行优化，增强了路由选择的全局与局部搜索能力，加快了算法的收敛速度。关键词： 组播；服务质量；路由算法；遗传模拟退火算法AbstractWith the development of Internet,the recent emergence of multimedia communications and cooperative works in distributed environments provides anincentive to development of multicast communication.The problem in search of multicast routing with many QoS constrains.For the moment,most previous researchers have focused on developing heuristic algorithms to solve this problem.However,these algorithms have high comutation complexity so they are not fit in practicality. Aiming at the limitation of genetic algorithm,the paper proposes a novel genetic simulated annealing algorithm which combine genetic algorithm with simulated annealing algorithm.The paper mainly researches multicast routing with many QoS constrains.Aiming at the limitation of genetic algorithm,the fitness function is adjusted,and the optimized reserved strategy is used.The crossover and mutation methods are improved,and simulated annealing algorithm is combined with.The algorithm has fast convergence speed and better performance.Keywords:Multicast;Quality of service;Routing algorithm;Genetic simulated annealing algorithm目 录第1章 概述11.1 课题的研究背景和意义11.2 路由选择的概念11.3 组播路由11.4 研究现状31.5 本论文所做的工作31.6 本章小结4第2章 组播QoS路由52.1 通信网络模型52.2 QoS约束62.3 QoS 组播路由的数学模型62.4 本章小结8第3章 模拟退火算法93.1 模拟退火算法原理93.2 模拟退火算法的应用93.3 模拟退火算法的参数控制113.4 本章小结11第4章 遗传算法124.1 简介124.2 遗传算法研究现状124.3 遗传算法原理134.4 本章小结17第5章 一种基于组播QoS路由的遗传模拟退火法185.1 基本思想185.2 算法的效率性分析195.3遗传模拟退火算法在组播QoS路由中的应用205.4算法的整体描述295.5 本章小结31结 论32参考文献33致 谢34II大庆石油学院本科生毕业设计（论文）第1章 概述1.1 课题的研究背景和意义标准Intemet协议(IP)的网络提供尽力而为的数据传输。当越来越多的主机联入到Internet的时候，对网络服务的需求也就超过了网络的承载能力，由此产生网络性能的逐渐恶化，进而造成传输延时的变化(抖动)，甚至引起分组丢失，这就给对传输延时对有实时要求的应用(例如：传送多媒体信息)带来了问题。为了提供能够满足要求的服务，必须制订有关服务质量水平的规定，来区分具有严格定时要求的业务和能容忍延时、抖动和分组丢失的业务。这就是服务质量(QoS)要做的事情。QoS不是创造带宽，而是管理带宽，因此它能应用得更广泛，能满足更多的应用需求。QoS的目标是要提供一些可预测性的质量级别，以及控制超过目前IP网络最大服务能力的服务3。1.2 路由选择的概念路由选择是网络最复杂同时也是最重要的功能，路由选择技术已经出现了大约25年。路由选择的概念实际上可追溯到20世纪50年代，当时计算技术仍是一门神秘科学。 建立并使用全球互联网改进了发现、访问并与远程主机通信的手段。表面上，全球互联网会提供冗余，换句话说，穿过某一网络、在任意给定的一对主机之间会有许多不同的物理路径。逻辑上讲，如果到达某目的节点有许多不同路径。某些路由可能会比其它路由提供总距离较短或者性能较好的路径。因此，比较所有可能的路由然后选择最好的一条或几条路由是符合逻辑的。发现、计算并比较到达远程网络和主机的过程即是路由选择。1.3 组播路由可以根据不同情况对路由算法进行分类：单播路由和组播路由；源路由；分布式路由和层次路由；静态和动态路由；单路路由和多路路由；域内和域间路由；链路状态和距离矢量路由，本文主要研究组播路由。组播路由是由单播路由构成的，根据树约束、链路约束和目标函数，组播路由可分为以下十二大类：(1)单链路约束问题(link constrained problem)：规定一个链路约束来构造可行组播树。例如，带宽约束路由。(2)多链路约束问题(multiple link constrained problem)：规定两个或多个链路约束来构造可行树。例如，带宽和缓冲约束路由。(3)单树约束问题(tree constrained problem)：规定一个树约束来构造可行组播树。例如，时延约束路由。(4)多个树约束问题(multiple tree constrained problem)：规定两个或多个树约束来构造可行组播树。例如，时延和时延抖动约束路由。(5)链路及树约束路由(link and tree constrained problem)：规定一个链路约束和一个树约束来构造可行树。例如，时延和带宽约束路由。(6)链路优化问题(link optimization problem)：使用一个链路优化函数来构造一个优化的组播树。例如，最大化组播树链路带宽。(7)树优化问题(tree optimization problem)：使用一个树优化函数来构造一个优化的组播树。例如，最小化组播树代价。这就是著名的Steiner树问题。(8)链路约束链路优化问题(link constrained link optimization problem)：规定一个链路约束并使用一个链路优化函数来构造一个满足约束的最优组播树。例如，带宽约束缓冲优化问题。(9)链路约束树优化问题(link constrained tree optimization problem)：规定一个链路约束并使用一个树优化函数来构造一个满足约束的最优组播树。例如，带宽约束Steiner树问题。(10)树约束链路优化问题(tree constrained link optimization routing problem)：使用一个树约束和链路优化函数来构造一个优化的组播树。例如，时延约束带宽优化问题。(11)树约束树优化问题(tree constrained tree optimization routing problem)：使用一个树约束和树优化函数来构造一个优化的组播树。例如，时延约束Steiner树问题。(12)链路约束及树约束树优化路由问题(link and tree constrained tree optimization routing problem)：使用链路和树约束和树优化函数来构造一个优化的组播树。例如，带宽时延约束的树优化问题。第(1), (2)类问题很容易处理，我们可以通过从网络拓扑中删除那些不合要求的链路来满足链路约束。文献3证明当约束条件包含两个或两个以上的加法。第(1),(2)类问题很容易处理，可以通过从网络拓扑中删除那些不合要求的链路来满足链路约束。证明当约束条件包含两个或两个以上的加法型度量(如延迟，代价)，或者包含加法型度量和乘法型度量(如丢包率)的组合时，路由选择问题为NP完全问题。只有最大最小性约束与其它可加性、可乘性约束的组合问题是容易处理的，因此问题(3), (5)在多项式时间内可解，而问题(4)是NP完全的。文献13提出了一个关于问题(6)的多项式时间解法。如果从网络拓扑中删除那些不满足约束条件的链路，问题(8), (10)都可转化为问题(6)。问题(7)(Steiner树问题)、(9)、(11)和(12)(约束的Steiner树问题)己经被证明是NP完全的。1.4 研究现状为进行有效的组播通信，确定组播路由是非常关键的，组播路由算法就是用来确定组播树的。组播树的建立是在每个路由器上设置路由表，路由表上给出了信息传送的组成员，以及此路由器应选择哪个邻接点。由于网络的动态变化，每个路由器的路由表也需要定期更新。此外路由表的设置要保证不能有回路的产生，下面对组播路由算法进行介绍，这里主要研究QoS组播路由问题。随着网络技术的迅速发展，交互式会议电视、分布式网络对战游戏、协同文档编辑、视频点播、网络电话、远程实时医疗等已经开始应用，这些应用涉及到网络的QoS问题。QoS包括许多方面，例如端到端时延、端到端时延抖动、路径带宽、路径中的数据丢失率等。对于组播 QoS 路由问题，一般有两种 QoS 要求，即最优化(Optimization)和给定某个约束(Constraint)。这些要求的组合就形成了用户对网络提出的各种QoS要求。如要求组播树中源节点到各个组成员的时延要不高于时延约束，且组播树的费用要求最小，这就是组播的路径时延受限和组播树优化的组合。组播 QoS路由问题中研究最多的是受限组播路由问题，也称为QoS组播路由问题，即满足带宽、时延等约束条件下的费用最小组播路由问题，本文将在第 2 章对QoS组播路由问题进行详细的介绍。1.5 本论文所做的工作本文采用遗传算法和模拟退火算法结合的算法来解决多约束QoS组播路由问题,两种算法的结合,有利于丰富优化过程中的搜索行为,增强全局和局部意义下的搜索能力和效率,极大地发挥了遗传算法的全局搜索能力和模拟退火算法的局部搜索能力,克服遗传算法局部搜索能力差及其早熟现象和模拟退火算法全局搜索能力差、效率不高的问题。在第一章中讲述了网络路由选择的问题，并介绍了组播路由，接着讨论了QoS的研究现状。第二章主要介绍了QoS算法、QoS的网络模型、QoS数学模型等。随后的第三章和第四章中还研究了模拟退火算法以及遗传算法，最后在第五章中介绍了遗传模拟退火算法在路由选择中的问题。1.6 本章小结QoS不是创造带宽，而是管理带宽，因此它能应用得更广泛，能满足更多的应用需求。本章讲述了QoS组播路由的研究背景，阐述了路由选择的概念和意义，接着研究了组播路由以及组播路由研究的现状，最后交代了本论文所做的工作，采用遗传算法和模拟退火算法结合的算法来解决多约束QoS组播路由问题，并讨论了混合算法的优势。第2章 组播QoS路由2.1 通信网络模型路由选择本质上是图论中的问题3，可借鉴文献13中的定义描述网络的拓扑图。设无向图 N（V，E）表示网络，其中 V 表示结点集合，每个结点代表一个路由器，E表示边的集合，每条边代表两相邻路由器之间存在的链路。为每个结点和边设一些度量权值，用来刻画相关的网络特性。sV 为路由起点（即源结点），dV-s为路由终点（目的结点）。用 R+表示正实数集，R+表示非负实数集。对任一条边（链路）eE，定义四种度量：(1)链路时延函数delay(e)：ER+,表示分组通过链路 e 传输所需要的时间。(2)链路费用函数cost(e)：ER+，表示一个抽象概念，随实际而定（如管理费用权值、跳数等），表示分组传输对某些资源的一些消耗。(3)链路带宽函数bandwidth(e)：ER+，表示链路 e 可提供的带宽。(4)延时抖动函数delay_jitter(e)：ER+，表示分组在链路e上传输时的延时抖动。对任一网络结点（路由器）nV，也定义四种度量：1.结点时延函数delay(n)：VR+，表示分组在某结点的时延，如路由器上分组队列太长，时延会增加。2.结点费用函数cost(n)：VR+，表示结点的费用消耗。3.延时抖动函数delay_jitter(n) ：VR+，表示分组在结点的延时抖动。4.包丢失率paket_lost(n)：VR+，表示分组在结点的丢失率。针对以上定义，数据包在网络上特定路由路径的传输性能可有如下表示：= (2-1) minbandwidth(e),e (2-2) (2-3)1- (2-4) (2-5)其中，p(s,d)表示从源结点s到目的结d的路由路径，是由一系列结点和连接结点的边组成的一条通路。式(2-1)表示路径的延时等于该路径上所有路由器与链路的延时之和；式(2-2)表示路径可提供带宽等于路径上链路带宽的最小值；式(2-3)表示路径的延时抖动等于路径上路由器与链路的延时抖动之和；式(2-4)表示路径的包丢失率等于路径上路由器的包丢失率之积；式(2-5)表示路径的费用等于路径上路由器与链路的费用之和。所构建的抽象模型中，每个边和结点的度量分别反映网络相关方面的性能。用无向图来描述网络，是为了研究方便而对实际问题的一种简化（假设双向链路的性能相同，实际并非如此），在此定义的边和结点的度量，也是本文所研究路由策略时所要重点讨论的度量。2.2 QoS约束QoS即服务质量(Quality of Service)的定义为：服务质量是一个网络元素保证其通信量和服务需求获得满足的能力。RFC2216定义为：用带宽、分组延迟和分组丢失率等参数描述的关于分组传输的质量。RFC2386 的定义为：服务质量(QoS)是网络在传输业务流时，业务QoS是应用业务对网络传输服务提出的一种可度量的要求，具体可以量化为带宽、延迟、延迟抖动、丢失率、吞吐量、花费等性能指标。网络在传输相应数据业务时，必须满足这组要求。QoS需求可以通过一个约束集来描述。链路约束定义了从源节点到目的节点的每一条链路的约束，如一个单播的带宽约束要求构成这条单播路径的所有链路的剩余带宽都大于或等于某个预定的值;树约束定义了对组播中整个组播树的约束，可分为两种情况：(1)对组播树中从源节点到目的节点的每条路径上性能度量的组合值的约束。例如，组播树时延的约束就是对树中从源节点到目的节点路径中最大时延的约束。 (2)对从同一源节点到任意两个目的节点路径上的性能度量的不同组合值的约束。例如，目的节点之间的时延抖动约束定义为从相同源节点到任意两个不同目的节点路径上的端到端时延差异。 定义2.2.1可行路径(可行树)是网络中从源点到一个(一组)目的节点的一条路径(组播树)，并且该路径(树)具有足够的尚未分配的资源，能够满足特定的QoS需求。定义2.2.2服务质量路由(QoSR)是一种基于数据流QoS请求和网络可用资源进行路由的机制。或者，QoSR是一种动态路由协议，并且在其路径选择标准里可能包含可用带宽、链路和端到端路径利用率、资源消费量、延迟、跳数以及抖动等QoS参数5。2.3 QoS 组播路由的数学模型QoS组播路由是一种基于数据流QoS请求和网络可用资源进行组播路由的机制，在其路径选择标准里可能包含可用带宽、链路和端到端路径利用率、时延、跳数以及抖动等QoS参数。其主要目标包括两点：(1)为每一个接纳的QoS业务连接请求，找到满足其QoS要求的多播路由；(2)优化全局资源利用率，平衡网络负载，从而最大化网络接受其他QoS请求的能力，该问题数学模型定义如下：QoS路由选择问题可以描述为一个无向赋权图G = (V,E)，其中V = 为网络节点集，可以表示为交换机、路由器，也可以为子网，E =e为网络链路,对任意一条链路e，均有五个权值函数：端到端时延delay (e )：ER+，时延抖动 jitter (e)：ER+，代价cost(e)：ER+，丢包率 loss(e)：ER+和可用带宽 bandwidth (e)：ER+，从节点i到节点j的路径 p(i,j)是一个节点的序列，其中对序列中任意的Vi,ViVn和它的后续节点Vi+1有 e =E，对于任意一条路径 p (i ,j)具有QoS属性：时延、时延抖动、代价，丢包率和带宽，并且具有如下性质：其时延 (2-6)时延抖动 (2-7)代价 (2-8)丢包率1- (2-9)可用带宽Min(bandwidth() (1-10)其中=，=,V2 ,V3 ,Vn-1QoS 组播路由问题可定义为：网络图 G = (V,E)，多播源点 sV，多播目的节点集 D = d1 ,d2,dn，di V，i=1,2,n，QoS 约束条件为端到端时延delay (e)：ER+，时延抖动jitter (e)：ER+，代价cost( e)：ER+，丢包率loss (e)：ER+和可用带宽 bandwidth (e)：ER+。寻找一棵多播树 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是带宽约束， DT i，DJ i，PL i分别是目的节点d i的时延、时延抖动和丢包率约束。上述模型中，QoS路由的度量包括带宽、时延、时延抖动、代价和丢失率等。度量的性质随QoS要求的不同，不再如传统路由协议采用的跳数，链路代价只是可加性的，例如，丢失率是乘积性的，而带宽是极值性的。当QoS单播路由问题要在路径的计算过程中同时考虑两个或两个以上可加性或乘积性度量时，则属于NP完全问题，对于QoS组播路由结论仍然成立4。2.4 本章小结本章对基于遗传算法的 QoS组播路由选择策略做了一些研究。QoS组播路由，就是要寻找一棵包含源结点与目的结点的，满足每个目的结点QoS约束的组播树，因为网络中路由器转发能力往往是有限制的。本章首先介绍了通信网络的模型、阐述了QoS的定义，然后针对本文将要讨论的QoS组播路由问题，也建立了相应的数学模型。第3章 模拟退火算法3.1 模拟退火算法原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。模拟退火的步骤： (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L。(2) 对k=1，L做第(3)至第6步。 (3) 产生新解S。 (4) 计算增量t=C(S)-C(S)，其中C(S)为评价函数。(5) 若t0，然后转第2步。 模拟退火算法求得的解与初始解状态S(是算法迭代的起点)无关，模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法，模拟退火算法具有并行性14。3.2 模拟退火算法的应用求解tsp的模拟退火算法模型可描述如下：解空间：s是遍访每个城市恰好一次的所有回路,是1,n的所有循环排列的集合,s中的成员记为(,),并记=。初始解可选为(1,n)。目标函数：此时的目标函数即为访问所有城市的路径总长度或称为代价函数， 我们要求此代价函数的最小值。 新解的产生：随机产生1与n之间的两相异数k与m。若km,则将(，) 变为(， ， ， ， ，)。上述变换方法可简单说成是“逆转中间或者逆转两端”。 也可以采用其他的变换方法,有些变换有独特的优越性,有时也将它们交替使用,得到一种更好方法。代价函数差 设将(， )变换为(,，), 则代价函数差为：根据上述分析,可写出用模拟退火算法求解tsp问题的伪程序： begin procedure tspsa： s=1,n; s为初始值 init-of-t; t为初始温度 termination=false;while termination=false begin for i=1 to i do begin generate(s form s); 从当前回路s产生新回路s t:=f(s)-f(s);f(s)为路径总长 if(trandom-of-0,1) s=s;if the-halt-condition-is-true then termination=true;end; t_lower; end; end;模拟退火算法的应用很广泛,可以较高的效率求解最大截问题(max cut problem)、0-1背包问题(zero one knapsack problem)、图着色问题(graph colouring problem)、调度问题(scheduling problem)等等。3.3 模拟退火算法的参数控制模拟退火算法的应用很广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点：(1) 温度t的初始值设置问题 温度t的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一。初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间；反之,则可节约计算时间,但全局搜索性能可能受到影响.实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。(2) 退火速度问题模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。实际应用中,要针对具体问题的性质与特征设置合理的退火平衡条件。(3) 温度管理问题 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式： t(t+1)kt(t)式中k为正的略小于1.00的常数,t为降温的次数13。3.4 本章小结本章中阐述了模拟退火算法的原理以及实现的具体步骤，还研究了该算法应用到商旅问题上的例子，最后还介绍了该算法的参数控制问题，包括温度的初始值设定、退火速度、温度管理等。模拟退火算法已广泛应用与组合优化、神经网络、结构优化设计、系统控制、机器学习和并行算法等研究领域，可以预见，随着科学技术的发展，模拟退火算法将会更广泛的应用与其他领域。第4章 遗传算法4.1 简介遗传算法（Genetic Algorithm）3是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解12。4.2 遗传算法研究现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。 1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。 国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题。2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化【11。4.3 遗传算法原理遗传算法是具有“生成+检测”（generate-and-test）的迭代过程搜索方法。遗传算法是一种群体型操作，该操作以群体中的所有个体为对象，选择(selection)、交叉(crossover)、变异(mutation)是遗传算法三个主要操作算子。它们构成了主要的遗传操作(genetic operation),使遗传算法具有了其他传统方法所没有的特性。遗传算法中包含了以下5个基本要素：(1)参数编码；(2)初始种群设定；(3)适应度函数的设计；(4)遗传参数设计；(5)控制参数设定(主要是指种群大小和遗传概率等)；遗传算法的基本程序实现流程如下：(1) 先确定待优化的参数大致范围, 然后对搜索空间进行编码；(2) 随机产生包含各个个体的初始种群；(3) 将种群中各个个体解码成对应的参数值, 用解码后的参数求代价函数和适应度函数, 运用适应度函数评估检测各个个体适应度；(4) 对收敛条件进行判断, 如果已经找到最佳个体, 则停止,否则继续进行遗传操作；(5) 进行选择操作, 让适应度大的个体在种群中占有较大的比例, 一些适应度较小的个体将会被淘汰；(6) 随机交叉, 两个个体按一定的交叉概率进行交叉操作, 并产生两个新的子个体；(7) 按照一定的变异概率变异, 使个体的某个或某些位的性质发生改变；(8) 重复步骤(3) 至(7) , 直至参数收敛达到预定的指标。使用遗传算法需要确定的运行参数有：编码串长度、交叉和变异概率、种群规模。编码串长度由问题的所要求的精度来决定。交叉概率控制着交叉操作的频率, 交叉操作是遗传算法中产生新个体的主要方法, 所以交叉概率通常应取较大值, 但如果交叉概率太大的话又可能反过来会破坏群体的优良模式, 一般取0.4-0.99 。变异概率也是影响新个体产生的一个因素, 如果变异概率太小, 则产生新个体较少; 如果变异概率太大, 则又会使遗传算法变成随机搜索, 为保证个体变异后与其父体不会产生太大的差异, 通常取变异概率为0.0001- 0.1 以保证种群发展的稳定性。种群规模太大时, 计算量会很大, 使遗传算法的运行效率降低, 种群规模太小时, 可以提高遗传算法的运行速度, 但却种群的多样性却降低了, 有可能找不出最优解, 通常取种群数目20- 100。从理论上讲, 不存在一组适用于所有问题的最佳参数值, 随着问题参数的变化, 有效问参数的差异往往是十分显著的。4.3.1 编码编码就是把一个问题的可行解从其解空间转换到遗传算法能够处理的搜索空间的转化方法, 编码形式决定了重组算子的操作。遗传算法是对编码后的个体作选择与交叉运算, 然后通过这些反复运算达到优化目标。遗传算法首要的问题是通过编码将决策变量表示成串结构数据。我们常用的是二进制编码, 即用二进制数构成的符号串来表示每个个体。通常根据搜索精度(sca_var)、决策变量上界(range(2) 和下界(range(1)来确定各个二进制字符串的长度(bit_n), 搜索精度为sca_var =(range (2) - range (1)./(2bit_n1),然后再随机产生一个的初始种群(be_gen),其规模为popusize。下面用encoding 函数来实现编码和产生初始的种群：function be_gen , bit_n=encoding(sca_var,range(1) , range(2),popusize)bit_n=ceil(log2 ( range(2)- range(1)./sca_var);be_gen= randint( popusize, sum(bit_n);4.3.2 译码决策变量经过编码之后, 各个个体构成的种群be_gen 要通过解码才能转换成原问题空间的决策变量构成的种群vgen, 这样才能计算其相应的各个适应度值。另外, 译码首先要求出二进制数对应的十进制数decimal,然后根据下面的公式求出实际决策变量X: X=range(1)+decimal*sca_dec 。通常可以用decoding 函数来实现。译码的过程：functionvgen,fitness=decoding(fcn , be_gen,bit_n,range(1),range(2)popusize=size(be_gen,1);n_var=length(bit_n);sca_dec=(range(2)- range(1)./(2bit_n- 1);bit_n=cumsun(bit_n);bit_n=0 bit_n;for i=1:n_varbe_var(i)=be_gen(:,bits(i)+1:bit_n(i +1);var(i)=range(1)(i)+sum(ones(popusize,1)*2.(size(be_var(i),2)-1:-1:0).*be_var(i),2).*sca_dec(i);endvgen=var(1,:);for i=1:popusizefitness(i)=eval(fcn,(var_gene(i,:) );end4.3.3 选择选择就是利用码后求得的各个个体的适应度的大小, 从中选出一些适应度高的个体, 并淘汰一些适应度较小的个体以生成交配池的过程。然后再对优良的个体进行交叉和变异操作。在选择算子中, 先找出当前群体中适应度最高和最低的个体, 将最佳个体bes_ind 保留并替换最差个体, 直接进入下一代, 将剩余个体evol_gen 按适应值比例选择法进行操作, 即采用轮盘赌( roulette wheel) 方式来实现。这种方式首先计算每个个体的适应值, 然后计算出该适应值在群体适应值总和中所占的比例, 来表示该个体被选中的概率, 这样既能保证最佳个体的适应度值不会减小, 最佳个体不会被交叉变异操作所破坏, 也能不断提高该群体的平均适应度值。比例选择法体现了生物进化过程中“优胜劣汰, 适者生存”的思想, 并且保证将优良的基因遗传给下一代。我们可以用下面的函数来实现选择算子：function evol_gen, bes_ind,max_fitness=selection(old_gen, fitness)min_fitn,expo(b)=min(fitn); max_fitn,expo(a)=max_(fitn);popusize=length(fitness);bes_ind=old_gen(expo(a),:);expo=1:popusize;expo(expo(a)=0;expo(expo(b)=0;expo=nonzeros(expo);evol_gen=old_gen(expo,:);evol_fitness=fitness(expo,:);evol_popusize=popusize- 2;posel=evol_fitness/sum(evol_fitness);poselcum=cusum(posel);r=rand(1,evol_popusize);selected=1+sum(poselcum*ones(1,evol_popusize)ones(evol_popusize,1)*r);evol_gen=evol_gen(selection,:);4.3.4 重组重组算子是产生新个体的主要方法, 它决定了遗传算法的全局搜索能力。重组操作的作用是将原有的优良基因遗传给下一代个体, 并生成包含更优良基因的新个体。通常使用的遗传算子是一点交叉法, 就是按交叉概率pc(0pc1)实施交叉操作, 两个个体编码串(string) 在交叉位置处(crossp) 相互交换各自的部分编码,从而形成新的一对个体,程序如下：function new_gen=recombination(old_gen,pc)nouse,match=sort(rand(size(old_gen,1),1);match_gen=old_gen(match,:);pairs=size(match- gen,1)/2;bit_n=size(match_gene,2);string=rand(pairs,1)pc;crossp=randint(string,1,1,bit_n);crossp=string.*crossp;for i=1:pairsnew_gen(2* i- 1 2* i,: )=match_gen(2* i- 1 2* i ,1:crossp(i) ) match_gen(2* i 2* i - 1,crossp(i)+1:bin_n);end另外, 一点交叉法操作的信息比较小, 交叉点的位置的选择可能会带来较大的偏差, 一点交叉算子不利于长距离的保留和重组。4.3.5 变异变异算子是模拟自然界生物进化的中染色体的基因突变现象, 从而改变染色体的结构和物理性状。变异算子是产生新个体的辅助方法, 它决定了遗传算法的局部搜索能力。变异操作通过按照变异概率(mp)随机反转某位等位基因的二进制字符的值来实现。程序如下：function new_gen=mutation(old_gen, pm )mpoints=find(rand(size(old_gen)pm);new_gen=old_gen;new_gen(mpoints)=1- old_gen(mpoints);end当重组操作发生早熟收敛时, 这时引入变异算子会有很好的效果。一方面, 变异算子可以使群体进化中丢失的等位基因信息得以恢复, 保持群体基因中的差异性, 防止发生早熟收敛；另一方面, 当种群规模较大时, 在重组操作基础上引入适度的变异, 也能够提高遗传算法的局部搜索效率10。4.4 本章小结遗传算法提供了一种求解复杂系统优化问题的通用框架，对问题的种类有很强的鲁棒性。本章中主要阐述了遗传算法的原理以及现状，随后着重介绍了遗传算法实现的一般步骤以及遗传算法的各个算子(编码、译码、选择、重组、变异)的概念解析以及代码实现，为之后遗传算法与模拟退火算法结合打下了基础。第5章 一种基于组播QoS路由的遗传模拟退火法5.1 基本思想在算法的研究过程中，主要目标之一就是使设计的算法是稳健的，即广泛适用于多种问题。遗传算法就有这个性质，算法中的二进制表示法几乎可以对任何问题进行编码，并且遗传算子不包含关于搜索区域的任何知识。尽管传统的遗传算法是稳健的，但是就任何一个特殊领域而言，遗传算法一般不是最成功的最优化算法，它们往往比不上专门处理该领域问题的原有算法。一个有效的途径就是采取混合的策略，即把遗传算法与原有算法有效地结合起来，设计一个新的混合算法，在性能上超过遗传算法和原有算法。混合遗传算法是在标准遗传算法中融入局部搜索算法的思想，其特点主要体现在它引入局部搜索的过程。基于种群中各个个体所对应的表现型，进行局部搜索，从而找到各个个体在目前环境下的局部最优解，以便达到改善种群总体性能的目的。模拟退火算法是局部搜索算法的扩展，它依据 Metropolis 准则接受新解，因此除接受优化解外，还在一定范围内接受恶化解，这正是模拟退火算法与局部搜索算法的本质区别所在，理论上说，它是一个全局优化算法。遗传算法和模拟退火算法都是模仿自然界的某些规律来进行问题求解，如何将它们有机地结合起来，是目前一个很有意义的研究课题。遗传算法和模拟退火算法都是全局随机优化算法，它们在传统的基于梯度的优化方法难以解决的复杂优化问题中显示了优良的求解特性，得到广泛研究和应用。虽然遗传算法有较强的全局搜索性能，但它的爬山能力弱，在实际应用中容易产生早熟收敛的问题，且在进化后期搜索效率较低。而模拟退火算法却具有摆脱局部最优解的能力，能抑制遗传算法的早熟现象。因此，考虑将模拟退火算法的思想引入遗传算法，有效地缓解了遗传算法的选择压力9。遗传算法最为严重的问题是“过早收敛”问题。由于种群规模是有限的，经选择复制、交叉和变异操作后，使得高于种群平均适应度的个体在下一代中得到更多的复制，这样不断进行，一旦某些个体在种群中占有绝对优势，则遗传算法就会强化这种优势，从而使搜索范围变窄，表现为种群收敛于一些相同的串。由于“遗传漂移”，迅速收敛的种群达到的未必是全局最优，这就是“过早收敛”问题。造成这个问题的主要原因之一就是遗传算法的变异概率太小，以至于不能驱使搜索转移。保持种群的多样性可以预防“过早收敛”，但是无限制的多样性会导致种群最终很难收敛。受限的多样性是让种群中的一些个体分别代表解空间中不同的局部最优区域。将模拟退火算法的 M