毕业设计（论文）基于混沌遗传算法的组播路由研究

毕 业 设 计基于混沌遗传算法的组播路由研究*200630460116指导教师 学院名称工程学院 专业名称自动化论文提交日期2010年5月 论文答辩日期年月答辩委员会主席 _评 阅 人 _摘 要随着Internet的发展，涌现出了许多新的通信需求，如视频点播、多媒体会议、远程教学等，这些应用促进了多组播通信的发展。多组播路由问题是在一个给定的通信网络中找到一个总代价最小且满足带宽-时延约束的多个源点到多个目标点的路由集合。这是一个比单个源点到多个目标点的组播路由问题更加复杂的问题，是一个NP-hard问题。多组播路由问题的求解方法主要包括启发式算法和遗传算法。 遗传算法作为一种新的全局优化算法已在许多领域中取得了令人鼓舞的成就。但在实际工程应用中经常发生早熟收敛现象，且有时收敛速度非常慢，这在很大程度上限制了遗传算法的进一步普及和应用。 混沌现象在自然界中普遍存在，它揭示了非线性科学的共同特性：确定性和随机性的统一，有序性和无序性的统一，它具有遍历性、随机性和规律性等特点，能在定义域内按自身的规律不重复地遍历所有状态。混沌优化就是一种利用混沌变量搜索的有效方法，在搜索中，利用混沌运动的随机性和遍历性特点，可以在定义域内连续搜索，而且不会陷入局部极小。因此，比起随机搜索方法而言，混沌搜索对优化问题有着更高的效率，能够快速地搜索到全局最优解。 本文首先介绍了QOS（quality of service）多组播路由和研究现状、遗传算法和混沌理论的基本概念；然后研究了基于Tent映射的混沌遗传算法组播路由，成功地解决了QOS多组播路由优化问题；采用改进的遗传算法成功地解决了有QOS限制的多播路由选择问题，取得了满意的效果。 关键词：遗传算法 QOS多组播路由 混沌优化目 录1绪论11.1问题的提出11.2国内外研究现状22 QOS组播通信52.1 QOS组播通信52.2组播通信的工作原理52.3组播路由算法的分类72.3.1集中式路由算法和分布式路由算法72.3.2静态型和动态型72.3.3源基树型和共享树型72.4 QOS技术指标83遗传算法103.1遗传算法概述103.2遗传算法的发展历史113.3遗传算法的基本操作123.4遗传参数的选择163.5遗传算法的特点173.6遗传算法的性能评估指标184混沌理论194.1混沌的发展史194.2混沌基本概念204.2.1混沌的基本定义204.2.2混沌的基本特征214.3混沌信号的动力学特征描述224.3.1 Lyapunov指数和Lyapunov谱224.3.2测度嫡254.4几种典型的混沌序列264.4.1 Logistic映射及其参数特征264.4.2 Tent映射及其参数特征274.5混沌优化284.5.1函数问题的混沌优化研究294.5.2组合问题的混沌优化研究315遗传算法的改进335.1遗传算法的改进335.2混沌遗传算法的基本步骤346仿真结果及数据分析366.1仿真结果366.2结论37致谢参考文献英文摘要华南农业大学本科专业毕业设计成绩评定表1绪论1.1问题的提出随着互联网技术的发展和网络应用的普及，Internet的用户数量持续呈爆炸性增长，网络应用由传统的电子邮件转向Ftp、www等多媒体业务，另外基于Internet的新应用和新业务也在不断地推出，如电子商务、IP电话、视频会议等。但是要满足这些业务的需求，特别是要保证一些实时业务的带宽、时延等特殊需求，以目前Internet中的“尽力而为”的服务是难以完成的。“尽力而为”服务的特点是对所有应用提供同种数据传输服务，对网络资源缺乏有效的分配和管理，当网络负载较轻时，各个应用得到的传输服务质量尚可，但随着网络用户数目的增多，网络的负载也相应地增加。此时，各种应用的行为表现为无序地竞争网络资源，造成网络资源的不合理占用，各种应用各为其利，其结果是服务质量相互恶化，因此，必须对目前的Internet技术进行改进以提供有效的资源分配与管理。新型的网络应用，如视频会议、交互式游戏、声音/视频电话、实时多媒体播放、分布式计算、视频点播和远程教学等应用涉及到多个用户的交互，本质上具有多组播的特征，为了支持大量存在的此类应用，多组播技术的研究成为这个领域的热点。目前主要的通信方式有：单播、广播、多播、组播、多组播。（1）单播：在发送者和接收者之间实现点对点网络连接。单播的实现一般采用Dijkstra提出的最短路径算法或Bellman-Ford算法来建立点到点的路由。当只有两个终端参与同一进程时，一般采用单播方式。如果要以单播的方式实现多点间的通信，需要在源节点和目的节点之间分别建立单独的数据通道，在每条数据通道上传输一份数据的拷贝，从而实现点到多点的通信。当源节点只给很少量的目的节点传送数据时，一般没有什么问题，但是如果有大量的目的节点希望得到同一份数据的拷贝时就会导致源节点负载增加、时延增加，而且很有可能造成网络拥塞。采用单播方式实现多点传送，在网络中传送大量的冗余分组，会导致带宽的浪费，如果采用组播通信就可以解决这个问题。（2）广播：点到所有节点的通信方式。这种通信方式是指向每一个目的节点都传送一个分组的拷贝，是多点传递的最普遍的形式。它可以通过多个单次分组的传送完成，也可以通过单独的连接传送分组的拷贝，直到接收方均接收到一个拷贝为止。广播的主要缺点是每个广播都要发送数据给所有机器，使数据被网络中大多数机器丢弃，消耗了所有机器上的资源，使用范围非常小。（3）组播：发送者和每一接收者之间建立点对多点的网络连接，如果一个发送者同时给多个接收者发送相同的数据，也只需复制一份相同的数据包，它减少了骨干网络出现拥塞的可能性，提高了数据传输效率。组播通信方式的应用使得无论有多少个接收者，在整个网络的任何一条链路上只传送单一的数据包。涉及组播技术的应用很多，包括预定音频/视频、推送技术、信息公告、实时数据多播(如股票价格发布)等。（4）多组播：多点到多点的通信方式。包括分布式虚拟环境、视频会议系统、电子白板、网络游戏、聊天组等。但是网络用户对网络服务质量提出了许多新的要求，如传输的时延、带宽等，在网络的通信中，有一种可能的情况是，需要将不同的信息包从多个源点发送到各自的多个目的点，而这些信息包通过网络时的最佳路由同样要求满足一定的服务质量，我们称之为多组播路由问题。在QOS多组播路由问题中，例如由于多个信息包同时经过同一条网络链路时占用的带宽不能超过某一个限制，使得各信息包的最佳组播树的生成产生了竞争。1.2国内外研究现状组播路由可以形式化为图论中的有约束Steiner树问题。目前，对于有QOS约束的组播路由问题已有很好的解决方法1-5。（1）最短路径算法和最小生成树算法常规的组播路由算法有最短路径算法(Dijkstra算法和Bellman-Ford算法)和最小生成树算法(Prim算法)。最短路径算法使组播树从源节点到目的节点的每条路径上链路权重(Weight)之和最小。如果权重代表链路时延，则结果树就是最小时延树。如果所有链路的权重都为1，结果树就是最小跳树。Prim算法是求得一棵覆盖所有组成员且权重最小的树。算法采用的是贪婪策略，在树的生长过程中，每次选择的边都是使树权重增加最少的边。（2）Steiner树算法Steiner树的组播路由算法致力于构造一棵总费用最小的组播树。如果组播树覆盖了图中的所有节点，则Steiner树问题便转化为最小生成树问题。目前有大量的启发式算法，如KMB算法6 、TM算法和Rs算法等，其中KMB算法是由Kou、Markousky和Berman提出，具有良好的性能，是一个较为有效的算法，其所获得的组播树的平均费用仅高于Steiner费用的5%，而其算法的时间复杂度为。Steiner树算法可用来解决树优化问题，但对于有约束的业务使用该类算法很难找到满足端到端的约束条件。（3）基于QOS约束的Steiner树算法在进行树优化的组播路由中加入不同的QOS约束(例如带宽、时延、时延抖动或者它们的组合)，则Steiner树问题就扩展为带QOS约束的Steiner树问题，这个问题是NP-hard问题。目前大多数都采用启发式算法和智能优化算法来解决这类问题。在启发式源路由算法中最有代表性的是Kompella等提出的KPP7算法和ZHU等提出的BSMA8算法。KPP算法扩展了KMB算法，首先求出任意两个网络节点之间满足时延约束的最小代价路径，并以此来构造完全封闭图，然后以基于最小生成树的启发式算法产生路由树，算法的时间复杂度是，其中是端到端时延上限。BSMA算法首先使用Dijkstra最短路径算法求出从源节点到各目的节点的最小时延树，在不违反时延约束的条件下。通过前k条最短路径算法替换其中代价较高的超边，使树的总代价不断降低。该算法求到的组播树的代价最小，是当时所有时延约束启发式算法中性能最好的一个，但是该算法的时间复杂度很高，是，不适合求解大型网络。在启发式分布路由算法中，Kompella等提出了一种分布式算法来构建时延约束的Steiner树。算法要求网络中每个节点维护一个到其它所有节点的最小时延距离矢量。最初它所构建的树只包括源节点，然后向树中增加一个目的节点，直到该树包含了所有的目的节点。算法使用以下方法选择每次增加的目的节点。源节点向已构建的部分组播树上节点以组播形式发送一个find消息，树上节点收到find消息后，在自己的输出链路上寻找不在树中的接收节点并且要使选择函数最小化。如果找到了这样的侯选路径，树上的节点向源节点回送一个response消息，它包含了侯选路径的标识，当源节点收到所有的response消息之后，将选择一条使选择函数最小的最优路径，并把该路径加入到树中。该算法的缺点是需要多次传送控制消息。（4）QOS组播路由算法QOS包括许多方面，例如端到端的时延、路径带宽、路径中的数据丢失率等。其中，端到端的时延是实时通信应用中一个非常关键的因素。对于实时通信来说，如果时延过长、就会引起用户听觉和视觉上的不舒服，甚至引起语意的无法理解。端到端的时延波动也很重要，例如，在电话会议中，要保证各地的与会者同时听到发言者的讲话，从会场向各地传递消息的时延必须有一定的限制。而对于视频点播，则为了保证一定的图象质量，网络必须提供足够的带宽和可以接受的数据丢失率。对于QOS组播路由问题，要满足最优化和一定约束两个要求。其中研究的最多的就是受限组播树，包括时延受限最小费用组播树和带宽受限组播树问题。另外时延波动受限的组播树问题也是研究的热点。（5）QOS多组播路由算法目前解决多点到多点组播路由问题一般有两种方法：一是将多点到多点问题看成是多个点到多点的问题，即为每个源节点构造一棵基于源的组播树(sources-percific multicast tree)；二是为所有的源节点和目的节点建立单棵(或多棵)组播树，这样建立的组播树称为共享组播树(shared multicast tree)。构造共享树和信源树有许多相似的地方，但有一个最重要的区别是：构造共享树需要首先选择一个组播中心。从严格意义上讲，共享树并非只能有一个中心，但是选定一个节点为其中心便于管理和操作，找出最优共享树是非常困难。大多数共享树构造算法首先选择一个节点作为中心，然后基于该中心构造共享组播树。文献9提出了一种启发式算法DCMMHA，来解决有时延约束的多共享组播树问题(DCMSMT)。此文算法按照特定规则生成候选中心列表，在不违反时延约束条件下，将源节点和目的节点加入共享树，并且对己选择中心进行更新。（6）智能优化算法近年来，研究人员将智能优化算法应用到求解组播路由问题中，取得了良好的效果。这些智能优化算法主要包括遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法和人工神经网络等。遗传算法10具有简单性、并行性，健壮性和易于实现等优点，适用于在庞大而复杂的搜索空间中寻找最优解，在搜索过程中自动获取和积累有关搜索空间的知识，自适应地搜索控制过程，不断地缩小搜索空间，从而得到优化解，甚至最优解。近年来，随着对遗传算法的研究不断深入，发现采用该算法来求解NP完全问题能取得较好的效果。该方法同样适合求解QOS组播路由问题，目前遗传算法己在QOS组播路由问题得到初步的应用，使得QOS路由选择方法简单有效。以上是对于组播路由问题的研究现状，算法己经比较成熟。但是随着网络规模的不断扩大和网络应用对服务质量的不断提高，双向请求应用不断涌现，即任何一端(多点和点)都有可能发起请求，还有各种网络应用要求多个用户的参与，例如资源查找、数据收集、网络竟拍、信息询问和Juke Box等10-11促进了对QOS多组播路由问题的研究。2 QOS组播通信2.1 QOS组播通信组播是指从源节点将同一份信息传递到多个目的节点的过程。组播源节点是指发起组播通信的节点，在“点对多点”的通信模式中，一次通信业务中只有一个组播源节点，在“多点对多点”的通信模式中，一次通信业务中可以有几个组播源节点；目的节点是指组播通信的接收者，通常在一次组播通信会有多个目的节点。QOS组播路由是指在一个给定的通信网络中找到一个总代价最小且满足QOS约束(如带宽、时延等)的多个源节点到多个目的节点的路由集合。但是随着网络规模的不断扩大和人们对网络服务质量的要求不断提高，单单能够确定QOS组播路由是不够的，这就要求我们提出一种新的解决方案，就是在给定的网络中找到由多个源节点到多个目的节点的满足QOS约束的最优路径集合，这就是QOS多组播路由问题。2.2 组播通信的工作原理 组播是从一个发送者向多个接收者或者多个发送者向多个接收者发送数据包的过程。组播源把数据包发送到特定的组播组，而只有属于该组播组的地址才能接收到数据包。组播以最佳的方式将数据传输给所有主机，组的成员可以是动态的，即组的成员可以在任何时间加入一个组或离开一个组，组的大小和位置没有限制，一个主机可以是多个组的成员。组播可以大大节省网络带宽，提高数据传送速率，减少主干网出现拥塞的可能性。因为无论有多少个目标地址，在整个网络上只传送单一的数据包。组播组中的主机可以是在同一物理网络，也可以是不同的物理网络(如果有组播路由器的支持)。为了满足多媒体实时应用的需求，很有必要寻求网络层对组播业务的支持，使组播技术满足此类应用的要求，建立组播树就可以实现这种需求。组播树是覆盖所有源节点和目的节点的一棵生成树，它具有以下优点：（1）信息可以沿着树的分支并行的传到各个目的节点，这可以降低信息传送时延；（2）信息只在树的分支处进行复制，从而降低了信息复制的份数，这样可以节省带宽资源，提高资源利用率，降低拥塞的发生12-13。组播路由选择问题是指给定一个源节点S，一组目的节点，寻找一棵满足一定QOS约束C的最优可行多播树，如图1所示；也可以是一组源节点，一组目的节点，寻找多棵满足一定QOS约束C的最优可行多播树集，如图2所示。图1. 一个源节点到多个目的节点组播通信图 2. 多个源节点到多个目的节点多组播通信多组播通信典型应用包括：（1）多点会议：音/视频和白板应用构成多点会议应用。在多点会议中。不同的数据流拥有不同的优先级。传统的多点会议采用专门的多点控制单元来协调和分配它们，采用组播可以直接由任何一个发送者向多个接收者发送数据，多点控制单元用来控制当前发言权，这类应用对带宽和时延要求都比较高。（2） 资源同步：如日程、目录、信息等分布数据库的同步。它们对带宽和时延的要求一般。（3）并行处理：如分布式并行处理。它对带宽和时延的要求都比较高。（4）协同处理：如共享文档的编辑。它对带宽和时延的要求一般。（5）远程学习：这实际上是媒体广播应用加上对上行数据流(允许学生向老师的提问)的应用。（6）讨论组：类似于基于文本的多点会议，还可以提供一些基本的表达。2.3组播路由算法的分类目前组播路由算法很多，可以根据不同的角度、不同的准则来分类。2.3.1集中式路由算法和分布式路由算法集中式路由算法是指在节点掌握网络的整个拓扑结构信息的基础上，确定路由的算法。分布式算法不需要每个组成员掌握整个网络的拓扑，每个组成员在只有局部信息的条件下就可参与路由的确定。集中式路由的源路由采用集中式处理的方式，因此在发出路由请求时，可以立即获得预先存在的路由信息，进行路由计算；分布式路由不需要每个组成员掌握整个网络的拓扑，这对大型网络的多播路由是十分有利的。2.3.2静态型和动态型静态型是指在组播树生成以后就不再发生变化了，它不能根据当前组成员的加入或离开来调整路由，而是就近嫁接到开始选择好的路径上传送，它的路由修改要经过一定时间的运行后进行。显然这对于大部分应用来说是不合适的，而动态型则与此相反，在会话阶段，它允许节点动态地加入和离开，这符合实际的要求，但同时也给算法带来了新的问题，由于动态路由算法对路由的频繁修正，将会使通信系统不稳定。2.3.3源基树型和共享树型源基树算法为组中每一个发送者建立一棵以发送者所在子网为根的组播树，每个路由器维护状态的组播路由表，源基树算法只适用于广播业务，另一类算法则为组内所有发送者与接收者建立一棵共享树，无论哪个源端都是用同一个组播树传输数据，这类算法适用于会议型业务(如计算机会议)，会议型业务具有以下特征：（1）既有一对多型传输，也有多对多型传输；（2） 对信息传送的时延有严格的要求；（3）数据量大，且媒体多样要求不同的处理；（4）在改变发言者时要进行快速的路由切换。2.4 QOS组播的关键指标 目前的Internet仅提供尽力而为的传送服务，业务量尽快传送，没有明确的时间和可靠性保障。 随着网络多媒体技术的飞速发展，现有的尽力传送服务已无法满足各种应用对网络传输质量的不同要求，需要Internet提供多种服务质量类型的业务，而尽力而为的服务仍将提供给那些只需要连通性的应用。网络提供给用户的QOS是由各种网络参数决定的，QOS的关键指标主要包括：带宽、时延、时延变化(包括抖动和漂移)、可用性、吞吐量和包丢失率等，下面详细叙述： （1）带宽：单位时间内传送的数据包数量。多媒体业务的数据传输量往往较大，因此需要网络为其分配最小带宽。如标准电话为64kbits/s，压缩过的HDTV为25-34Mbits/s，视频会议为0.1-2Mbits/s。（2）时延：指一项服务从网络入口到出口的平均经过时间。许多服务都是高度不能容忍时延的。当时延超过200-250毫秒时，交互式会话是非常麻烦的。为了提供高质量话音和会议电视，网络设备必须能保证低的时延。产生时延的因素很多，包括分组时延、排队时延、交换时延和传播时延。传播时延是信息通过铜线、光纤或无线链路所需的时间，传播时延总是存在的。时延变化是指同一业务流中不同分组所呈现的时延不同。高频率的时延变化称作抖动，而低频率的时延变化称作漂移。（3）可用性：是当用户需要时网络即能工作的时间百分比。可用性主要是设备可靠性和网络存活性相结合的结果。对它起作用的还有一些其他因素，包括软件稳定性以及网络演进或升级时不中断服务的能力。（4）吞吐量：是在一定时间段内对网上流量(或带宽)的度量。一般讲，吞吐量越大越好。（5）包丢失率：不管是比特丢失还是分组丢失，对分组数据业务的影响比对实时业务的影响都大。在通话期间，丢失一个比特或一个分组的信息往往用户注意不到。在视像广播期间，这在屏幕上可能造成瞬间的波形干扰，然后视像很快恢复如初。即便是用传输控制协议(TCP)传送数据也能处理丢失，因为传输控制协议允许丢失的信息重发。事实上，一种叫做随机早丢(RED)的拥塞控制机制在故意丢失分组，其目的是在流量达到设定门限时抑制TCP传输速率，减少拥塞，同时还使TCP流失去同步，以防止因速率窗口的闭合引起吞吐量摆动。但分组丢失多了，会影响传输质量。QOS组播技术具有以上诸多的关键指标，但是带宽约束和时延约束是其中最关键的两个指标，对组播技术的性能影响最大，所以本文的算法主要考虑带宽约束和时延约束。3遗传算法遗传算法研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国密执安大学的Holland教授与其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过20余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来，智能计算己成为人工智能研究的一个重要方向。3.1遗传算法概述遗传算法的寻优过程是一个迭代过程，通过基因转换机制，每一代中的基本特征被遗传到下一代。一般来说，遗传算法主要包括以下三个操作算子：选择(selection)、交叉(crossover)和变异(mutation)。简单地说，选择就是从一个旧群体中挑出生命力强的个体用于产生新群体的过程。它意味着适应度高的个体在下一代中复制自身的个数多；交叉是指随机从群体中选择两个个体，并按较大的概率交换这两个个体的某些位；变异是以较小的概率对群体中某些个体的位进行改变。遗传算法包含如下五个要素：（1）参数编码；（2）初始群体的产生；（3）适应度函数的设计；（4）遗传操作设计；（5）控制参数的设计。遗传算法的一个周期的运行如图3所示 图3. 遗传算法的进化过程示意图3.2遗传算法的发展历史 遗传算法起源于对生物系统进行的计算机模拟研究。早在20世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程等研究工作。进入20世纪60年代后，Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。下面简要介绍一下遗传算法在国内外的发展历程。20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。20世纪70年代初，Holland教授提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统(Classifier Systems，简称CS)，开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。1975年，De Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。例如：对于50-100群体，经过10-20代的进化，遗传算法能以很高的概率找到最优解或近似最优解。1989年，Goldberg出版了专著搜索、优化和机器学习中的遗传算法(Genetic Algorithms in Search，optimization and Machine Learning)。该书系统的总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。1992年，Koza将遗传算法应用到计算机程序的优化设计及自动生成，提出了遗传编程(简称GP)的概念。他将一段LISP语言程序作为个体的基因座，把问题的解编码为一棵树，基于遗传和进化的概念，对由树组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。Koza成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。我国有关遗传算法、进化计算的研究从20世纪90年代以来一直处于不断上升的地位，特别是近年来，遗传算法、进化计算的应用在许多领域取得了令人瞩目的成果。武汉大学刘勇、康立山等于1995年出版了非数值并行计算(第2册)遗传算法；潘正军、康立山等于1998年出版了演化计算；周明、孙树栋于1999年出版了遗传算法原理；王小平、曹立明于2002年出版了遗传算法理论、应用与软件实现。3.3遗传算法的基本操作(1)参数编码如何将问题描述成串的形式，即参数编码。在参数优化等问题中，一般将各参数用二进制编码，构成子串，再将子串拼接起来构成“染色体”串，但是不同的串长和不同的码制，对问题求解的精度和GA (Genetic Algorithm)收敛时间会有很大影响，对于复杂问题如变结构控制器，神经网络等，如何将问题描述成串的形式就不那么简单了，而且同一问题可能有不同的编码方法。由于遗传算法不能直接处理解空间的数据，因此必须通过编码将其表示成遗传空间的数据结构。目前常用的编码方式有二进制编码、实数编码等。(2)初始群体设定由于遗传算法的群体型操作需要，必须为遗传操作准备一个由若干个初始解组成的初始群体。需要说明的是，初始群体的每个个体都是通过随机方法产生的。初始群体也称为进化的初始代，即第一代(first generation)。(3)个体适应度评价在遗传算法中，以个体适应度值的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度值越大，个体被遗传到下一代群体中的概率也越大；反之，个体的适应度值越小，该个体被遗传到下一代的概率也越小。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度值必须为正数或零，不能为负数。对于求目标函数最小值的优化问题，理论上只需要简单地对其增加一个负号就可以将其转化为求目标函数最大值的优化问题，即： (3.1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度值F(X)就等于相应的目标函数值f(X)，即： (3.2)但是实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度值都是非负数这个要求。所以必须寻求出一种通用且有效的由目标函数值到个体适应度值之间的转换关系，由它来保证个体适应度值总取非负数。为满足适应度值总取非负数的要求，遗传算法一般采用以下两种方法将目标函数值f(x)变换为个体的适应度值F(x)。方法一：对于求目标函数最大值的优化问题，变换方法为： (3.3)式中为一个适当的相对较小的数，它可用下面几种方法之一来选取。预先指定的一个较小的数;进化到当前代为止的最小目标函数值;当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为： (3.4)式中，为一个适当的相对较大的数，它可用下面几种方法之一来选取。预先指定的一个较大的数;进化到当前代为止的最大目标函数值;当前代或最近几代群体中的最大目标函数值。(4)选择算子选择算子(selection operator)的作用是从当前群体中选择出一些比较优良的个体，并将其复制到下一代群体中。选择操作是建立在群体中个体的适应度值评估基础上的，其中最常用的选择算子是比例选择算子。比例选择算子是指个体被选中并遗传到下一代群体中的概率与该个体的适应度值大小成正比。比例选择实际上是一种有退还随机选择，也叫赌盘(Roulette Wheel)选择，如图4所示，因为这种选择方式与赌博中的赌盘操作原理颇为相似。图4 赌盘选择法的示意图整个赌盘被分为大小不同的一些扇面，分别对应着价值各不同的一些赌博物品。当旋转着的赌盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。虽然赌盘的指针具体停止在哪个扇面是无法预测的，但指针指向各个扇面的概率却是可以估计的，它与各个扇面的圆心角大小成正比；圆心角越大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。与此类似，在遗传算法中，整个群体被各个个体所分割，各个个体的适应度值在全部个体的适应度值之和中所占的比例也大小不一，这个比例值瓜分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。赌盘选择的特点是对于种群中的所有个体，无论其适应度值大小，都有被选择的机会。适应度值小的个体被选中的概率小，因此，一般来说，经过选择后它在种群中的数量会减少；而适应度值大的个体被选中的概率大，因此，经过选择后它在种群中的数量将会增加。这正是体现了“适者生存”的原则。比例选择算子的具体执行过程是： 首先计算出群体中所有个体的适应度值的总和； 其次计算出每个个体的相对适应度值的大小，它即为各个个体被遗传到下一代群体中的概率； 最后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个体被选中的次数。(5)交叉算子在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样，在遗传算法中起核心作用的是遗传操作的交叉算子(crossover operator)。交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。 目前，主要有单点交叉、二点交叉、多点交叉三种方式。单点交叉是最常用的交叉操作算子。单点交叉算子的具体执行过程如下： 对群体中的个体进行两两随机配对。若群体大小为，则共有对相互配对的个体组。其中表示取不大于x的最大的整数； 对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为L，则共有(L-l)个可能的交叉点位置； 对每一对相互配对的个体，依设定的交叉概率,在其交叉处相互交换两个个体的部分染色体，从而产生出两个新的个体。单点交叉运算如图5所示：图5 单点交叉二点交叉的操作与一点交叉类似，只是设置两个交叉点(依然是随机设定)，二点交叉运算如图6所示： 图6 两点交叉多点交叉是前述两种交叉的推广。一般来讲，多点交叉较少采用，因为它会影响遗传算法的在线性能和离线性能。(6)变异算子变异算子(mutation operator)的基本内容是对群体中的个体串的某些基因座上的基因值作变动。就基于字符集0，l的二值码串而言，变异操作就是把某些基因座上的基因值取反。若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0。一般来说，变异算子操作的基本步骤如下：在群体中所有个体的码串范围内随机地确定基因座；以事先设定的变异概率来对这些基因座的基因值进行变异；遗传算法导入变异的目的有两个：一是增强遗传算法局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解领域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的染色体会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现早熟收敛现象。此时，变异概率应取较大值。图7基本位变异3.4遗传参数的选择(1)群体规模群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果不佳。大的群体更希望包含大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而，群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛。在实验中，群体规模一般取20160。(2)交叉概率Pc交叉概率控制着交叉算子应用的频率，在每代新的群体中，大约有个串实行杂交。交叉概率越高，群体中串的更新就越快。如果交叉概率过高，高性能的串被破坏得要更快。如果杂交概率过低，搜索会由于太小的探索率而可能停滞不前。一般取交叉概率为0.50.9。(3)变异概率，变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以概率，进行随机改变，每代大约发生PmNpopL次变异，其中L为串长。一个低水平的变异概率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异概率产生实质上是随机搜索。一般取变异概率为0.0010.2。3.5遗传算法的特点为解决各种优化计算问题，人们提出了各种各样的优化算法，这些优化算法各有各的长处，各有各的适用范围，也各有各的限制。遗传算法是一类可用于复杂系统优化计算的随机搜索算法，与其它一些优化算法相比，主要有以下几个不同之处：(1)遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行计算，但遗传算法不是直接利用决策变量的值，而是以决策变量的某种形式的编码为运算对象。编码处理方式更显示出了其独特的优越性。(2)遗传算法不是从单个点，而是同时从多个初始点开始搜索。传统的优化算法往往是从解空间的一个初始点开始迭代搜索过程。遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索。对这个群体所进行的选择、交叉、变异等操作，产生出的仍是新一代的群体，在这之中包括了很多群体信息。这些信息可以避免一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。(3)遗传算法利用适应值信息，无须导数或其它辅助信息。遗传算法仅使用由目标函数变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其它一些辅助信息。再者，直接利用目标函数值或个体适应度值，也使得我们可以把搜索范围集中到适应度值较高的部分搜索空间，从而提高了搜索效率。(4)遗传算法利用概率转移规则，而非确定性规则。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都己证明在一定条件下，遗传算法总能以概率1收敛到问题的最优解。当然，交叉概率和变异概率等参数也会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用中是一个比较重要的问题。另一方面，与其它一些算法相比，遗传算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能的低。(5)遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到全局最优解；其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算。3.6遗传算法的性能评估指标 目前，遗传算法的评估指标大多采用适应度值。在没有特别具体要求的情况下，一般采用各代中群体的平均适应度值和最优个体的适应度值，即在线性能(on-line performance)和离线性能(off line performance)。定义3.1：设为环境e下策略s的在线性能，为第t代中相应于环境e的群体的平均适应度值，则可以表示为： (3.5)在线性能表示算法在直到当前为止的时间内得到的所有性能值的平均值。定义3.2：设为环境e下策略s的离线性能，为第t代中相应于环境e的群体中的最优适应度值，则可以表示为： (3.6)离线性能表示算法在执行中得到的最优性能值的平均值。4混沌理论4.1混沌的发展史英文中的chaos一词源于古希腊的“Xoas”，意思是指万物出现之前就存在一个虚无广褒的空间，而英文中的“chaos”是指“杂乱无章、混乱无序”之意，中文翻译成“浑沌”，演绎成“混沌”。所谓混沌是指在确定性系统中出现的某种紊乱的、不清楚的或不规则的现象，也是一种非常普遍的非线性现象，在自然界随处可见，它貌似无规则、类似随机，无序之中显现出有序，也正是混沌的这一诱人现象吸引了全世界许多科学家的关注。早在十八世纪末，科学家就开始探索自然界的一些捉摸不定的现象。法国数学家Poincare在研究三体运动时，就把动力学系统和拓扑学两大领域结合起来，提出了Poincare猜想，指出了混沌存在的可能性，但由于当时条件的限制，他的想法没能引起人们的重视，直到1963年，美国麻省理工学院著名的气象学家Lorenz发表了“Deterministic nonperiodic flow”一文14，文中对一个来自于湍流模型的简单三阶自治系统进行了研究，指出了非周期性与不可预测性之间的联系，并描述了对初值条件的敏感性这一混沌基本性质，从此才正式揭开混沌发展史的篇章；1964年， Henon M等人发现了二维不可积Hamilton系统中的确定性随机行为，称之为Henon吸引子；1971年，法国物理学家Ruell D和荷兰数学家Takens F将“怪引子”概念引入耗散系统，提出了一种新的湍流发生机制以揭示湍流发生的机制，即Ruelle-Takens定理，也就发现了第一条通向混沌的道路15；1975年，华人科学家Li T Y和美国数学家Yorke J A发表了“Period three implies chaos”的著名文章16，深刻揭示了从有序到混沌的演化过程，被认为是混沌的第一次正式表述；1976年，美国生物学家R May发表了“Simple mathematical models with very complicated dynamics”一文，指出在生态学中一些非常简单的确定性的数学模型具有极为复杂的动力学行为，其中包括分叉和混沌，并用虫口方程来说明非常简单的一维迭代映射也能产生复杂的周期倍化和混沌运动，这就是著名的Logistic模型；同年， Gollub J P等人从实验中也得到了耗散系统确实存在奇怪吸引子的结论；1978年，美国物理学家Feigenbaum M J发表了“Quantitative universality for a class of nonlinear transformation”的文章17，并和他的同事一起在研究以Logistic映射为代表的很大一类单峰映射时，发现了倍周期分叉现象中的标度性和普适常数，从而使混沌在现代科学中具有了坚实的理论基础；同年，Newhouse等人证明出二维环面可以直接失稳而称为混沌吸引子；1980年， Holmes P J发展了Melnikov理论的分析方法，将其用于二维系统中稳定流形和不稳定流形是否相交的判别上，也就可以判别出系统是否发生了混沌；1981年， Takens F提出了判定怪引子的实验方法；1983年，中国著名科学家郝柏林发表了“分岔、混沌、奇怪吸引子及其他”的文章18；1984年，郝柏林编辑的混沌一书在新加坡出版；1986年，中国第一届混沌会议在桂林召开，为我国广泛开展混沌科学研究起到了促进作用；1987年, Grassberger P和Procaccia提出重构动力系统的理论和方法，通过由时间序列中提取分数维、Lyapunov指数等混沌特征量，从而使混沌理论研究进入到实际应用阶段；同年，Hbler在自己的博士论文中描述了一种控制混沌现象的方法，后来他和Jackson以及他们的一些同事们在此基础上进一步推广和完善，总结出了著名的“纳入轨道”和“强迫迁徙”法；1988年，Pettini通过观察极大Lyapunov指数方式时发现适当的参数扰动就可以达到消除Duffing系统的混沌现象19；1990年，美国Maryland 大学的Ott，Grebogi和Yorke三人提出了一种比较系统和严密的参数扰动方法，可以通过逐次局部线性化配合小参数调整的手段来实现控制混沌现象的目的，称之为OGY方法；同年，Ditto等人利用OGY方法首次在磁弹体上实现了对不动点的稳定控制；也是同年，美国海军实验室的Pecora和Carroll提出了混沌同步原理并首次在电子线路上实现20；。进入90年代后就是混沌与其它学科相互渗透、相互促进、广泛应用的年代，对它的研究几乎涉及到了科学研究的每一个领域，如生物学、天文学、数学、物理学、化学、工程学、电子学、信息科学、气象学、宇宙学、地质学、经济学、人脑科学等。近年来，关于混沌方面的文章也大量涌现，在这些文献中，数学家和理论物理学家们正试图利用数学工具给混沌以合理的定义，给相平面、空间中复杂缠绕的轨线以合理的数学解释；应用物理学家和工程应用学者们则在具体的领域中构造混沌或是控制混沌，利用混沌所具有的特性为民造福，这都说明了混沌在现代科学技术中的重要地位。4.2混沌基本概念4.2.1混沌的基本定义混沌目前尚无通用、严格的定义，但混沌一词首先是由Li T Y和Yorke J A在1975年发表的“Period three implies chaos”一文中提出的，称为Li-Yorke定义，这个定义是用如下的定理叙述的：定理4.1 若：是连续自映射，是中一个子区间，如果存在不可数集合满足：，并且（或），则以下性质成立：对于任意自然数1,2，区间上具有的周期为的周期点；存在一个不包含周期点的不可数集合，满足对任给的，有 (4.1) (4.2)对于任给的 及的任意周期点，有 (4.3)当映射能满足上述定理中的所有性质时，则称在上是混沌的，证明见文献。其中表示重函数关系，称