《毕业设计论文基于混沌遗传算法的组播路由研究.doc》由会员分享，可在线阅读，更多相关《毕业设计论文基于混沌遗传算法的组播路由研究.doc（50页珍藏版）》请在三一办公上搜索。
1、毕 业 设 计基于混沌遗传算法的组播路由研究*200630460116指导教师 学院名称工程学院 专业名称自动化论文提交日期2010年5月 论文答辩日期年月答辩委员会主席 _评 阅 人 _摘 要随着Internet的发展，涌现出了许多新的通信需求，如视频点播、多媒体会议、远程教学等，这些应用促进了多组播通信的发展。多组播路由问题是在一个给定的通信网络中找到一个总代价最小且满足带宽-时延约束的多个源点到多个目标点的路由集合。这是一个比单个源点到多个目标点的组播路由问题更加复杂的问题，是一个NP-hard问题。多组播路由问题的求解方法主要包括启发式算法和遗传算法。 遗传算法作为一种新的全局优化算法
2、已在许多领域中取得了令人鼓舞的成就。但在实际工程应用中经常发生早熟收敛现象，且有时收敛速度非常慢，这在很大程度上限制了遗传算法的进一步普及和应用。 混沌现象在自然界中普遍存在，它揭示了非线性科学的共同特性：确定性和随机性的统一，有序性和无序性的统一，它具有遍历性、随机性和规律性等特点，能在定义域内按自身的规律不重复地遍历所有状态。混沌优化就是一种利用混沌变量搜索的有效方法，在搜索中，利用混沌运动的随机性和遍历性特点，可以在定义域内连续搜索，而且不会陷入局部极小。因此，比起随机搜索方法而言，混沌搜索对优化问题有着更高的效率，能够快速地搜索到全局最优解。 本文首先介绍了QOS（quality of
3、 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遗
4、传算法的发展历史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遗传算法的改进3
5、35.2混沌遗传算法的基本步骤346仿真结果及数据分析366.1仿真结果366.2结论37致谢参考文献英文摘要华南农业大学本科专业毕业设计成绩评定表1绪论1.1问题的提出随着互联网技术的发展和网络应用的普及，Internet的用户数量持续呈爆炸性增长，网络应用由传统的电子邮件转向Ftp、www等多媒体业务，另外基于Internet的新应用和新业务也在不断地推出，如电子商务、IP电话、视频会议等。但是要满足这些业务的需求，特别是要保证一些实时业务的带宽、时延等特殊需求，以目前Internet中的“尽力而为”的服务是难以完成的。“尽力而为”服务的特点是对所有应用提供同种数据传输服务，对网络资源缺乏
6、有效的分配和管理，当网络负载较轻时，各个应用得到的传输服务质量尚可，但随着网络用户数目的增多，网络的负载也相应地增加。此时，各种应用的行为表现为无序地竞争网络资源，造成网络资源的不合理占用，各种应用各为其利，其结果是服务质量相互恶化，因此，必须对目前的Internet技术进行改进以提供有效的资源分配与管理。新型的网络应用，如视频会议、交互式游戏、声音/视频电话、实时多媒体播放、分布式计算、视频点播和远程教学等应用涉及到多个用户的交互，本质上具有多组播的特征，为了支持大量存在的此类应用，多组播技术的研究成为这个领域的热点。目前主要的通信方式有：单播、广播、多播、组播、多组播。（1）单播：在发送者
7、和接收者之间实现点对点网络连接。单播的实现一般采用Dijkstra提出的最短路径算法或Bellman-Ford算法来建立点到点的路由。当只有两个终端参与同一进程时，一般采用单播方式。如果要以单播的方式实现多点间的通信，需要在源节点和目的节点之间分别建立单独的数据通道，在每条数据通道上传输一份数据的拷贝，从而实现点到多点的通信。当源节点只给很少量的目的节点传送数据时，一般没有什么问题，但是如果有大量的目的节点希望得到同一份数据的拷贝时就会导致源节点负载增加、时延增加，而且很有可能造成网络拥塞。采用单播方式实现多点传送，在网络中传送大量的冗余分组，会导致带宽的浪费，如果采用组播通信就可以解决这个问
8、题。（2）广播：点到所有节点的通信方式。这种通信方式是指向每一个目的节点都传送一个分组的拷贝，是多点传递的最普遍的形式。它可以通过多个单次分组的传送完成，也可以通过单独的连接传送分组的拷贝，直到接收方均接收到一个拷贝为止。广播的主要缺点是每个广播都要发送数据给所有机器，使数据被网络中大多数机器丢弃，消耗了所有机器上的资源，使用范围非常小。（3）组播：发送者和每一接收者之间建立点对多点的网络连接，如果一个发送者同时给多个接收者发送相同的数据，也只需复制一份相同的数据包，它减少了骨干网络出现拥塞的可能性，提高了数据传输效率。组播通信方式的应用使得无论有多少个接收者，在整个网络的任何一条链路上只传送
9、单一的数据包。涉及组播技术的应用很多，包括预定音频/视频、推送技术、信息公告、实时数据多播(如股票价格发布)等。（4）多组播：多点到多点的通信方式。包括分布式虚拟环境、视频会议系统、电子白板、网络游戏、聊天组等。但是网络用户对网络服务质量提出了许多新的要求，如传输的时延、带宽等，在网络的通信中，有一种可能的情况是，需要将不同的信息包从多个源点发送到各自的多个目的点，而这些信息包通过网络时的最佳路由同样要求满足一定的服务质量，我们称之为多组播路由问题。在QOS多组播路由问题中，例如由于多个信息包同时经过同一条网络链路时占用的带宽不能超过某一个限制，使得各信息包的最佳组播树的生成产生了竞争。1.2
10、国内外研究现状组播路由可以形式化为图论中的有约束Steiner树问题。目前，对于有QOS约束的组播路由问题已有很好的解决方法1-5。（1）最短路径算法和最小生成树算法常规的组播路由算法有最短路径算法(Dijkstra算法和Bellman-Ford算法)和最小生成树算法(Prim算法)。最短路径算法使组播树从源节点到目的节点的每条路径上链路权重(Weight)之和最小。如果权重代表链路时延，则结果树就是最小时延树。如果所有链路的权重都为1，结果树就是最小跳树。Prim算法是求得一棵覆盖所有组成员且权重最小的树。算法采用的是贪婪策略，在树的生长过程中，每次选择的边都是使树权重增加最少的边。（2）S
11、teiner树算法Steiner树的组播路由算法致力于构造一棵总费用最小的组播树。如果组播树覆盖了图中的所有节点，则Steiner树问题便转化为最小生成树问题。目前有大量的启发式算法，如KMB算法6 、TM算法和Rs算法等，其中KMB算法是由Kou、Markousky和Berman提出，具有良好的性能，是一个较为有效的算法，其所获得的组播树的平均费用仅高于Steiner费用的5%，而其算法的时间复杂度为。Steiner树算法可用来解决树优化问题，但对于有约束的业务使用该类算法很难找到满足端到端的约束条件。（3）基于QOS约束的Steiner树算法在进行树优化的组播路由中加入不同的QOS约束(例
12、如带宽、时延、时延抖动或者它们的组合)，则Steiner树问题就扩展为带QOS约束的Steiner树问题，这个问题是NP-hard问题。目前大多数都采用启发式算法和智能优化算法来解决这类问题。在启发式源路由算法中最有代表性的是Kompella等提出的KPP7算法和ZHU等提出的BSMA8算法。KPP算法扩展了KMB算法，首先求出任意两个网络节点之间满足时延约束的最小代价路径，并以此来构造完全封闭图，然后以基于最小生成树的启发式算法产生路由树，算法的时间复杂度是，其中是端到端时延上限。BSMA算法首先使用Dijkstra最短路径算法求出从源节点到各目的节点的最小时延树，在不违反时延约束的条件下。
13、通过前k条最短路径算法替换其中代价较高的超边，使树的总代价不断降低。该算法求到的组播树的代价最小，是当时所有时延约束启发式算法中性能最好的一个，但是该算法的时间复杂度很高，是，不适合求解大型网络。在启发式分布路由算法中，Kompella等提出了一种分布式算法来构建时延约束的Steiner树。算法要求网络中每个节点维护一个到其它所有节点的最小时延距离矢量。最初它所构建的树只包括源节点，然后向树中增加一个目的节点，直到该树包含了所有的目的节点。算法使用以下方法选择每次增加的目的节点。源节点向已构建的部分组播树上节点以组播形式发送一个find消息，树上节点收到find消息后，在自己的输出链路上寻找不
14、在树中的接收节点并且要使选择函数最小化。如果找到了这样的侯选路径，树上的节点向源节点回送一个response消息，它包含了侯选路径的标识，当源节点收到所有的response消息之后，将选择一条使选择函数最小的最优路径，并把该路径加入到树中。该算法的缺点是需要多次传送控制消息。（4）QOS组播路由算法QOS包括许多方面，例如端到端的时延、路径带宽、路径中的数据丢失率等。其中，端到端的时延是实时通信应用中一个非常关键的因素。对于实时通信来说，如果时延过长、就会引起用户听觉和视觉上的不舒服，甚至引起语意的无法理解。端到端的时延波动也很重要，例如，在电话会议中，要保证各地的与会者同时听到发言者的讲话，
15、从会场向各地传递消息的时延必须有一定的限制。而对于视频点播，则为了保证一定的图象质量，网络必须提供足够的带宽和可以接受的数据丢失率。对于QOS组播路由问题，要满足最优化和一定约束两个要求。其中研究的最多的就是受限组播树，包括时延受限最小费用组播树和带宽受限组播树问题。另外时延波动受限的组播树问题也是研究的热点。（5）QOS多组播路由算法目前解决多点到多点组播路由问题一般有两种方法：一是将多点到多点问题看成是多个点到多点的问题，即为每个源节点构造一棵基于源的组播树(sources-percific multicast tree)；二是为所有的源节点和目的节点建立单棵(或多棵)组播树，这样建立的组
16、播树称为共享组播树(shared multicast tree)。构造共享树和信源树有许多相似的地方，但有一个最重要的区别是：构造共享树需要首先选择一个组播中心。从严格意义上讲，共享树并非只能有一个中心，但是选定一个节点为其中心便于管理和操作，找出最优共享树是非常困难。大多数共享树构造算法首先选择一个节点作为中心，然后基于该中心构造共享组播树。文献9提出了一种启发式算法DCMMHA，来解决有时延约束的多共享组播树问题(DCMSMT)。此文算法按照特定规则生成候选中心列表，在不违反时延约束条件下，将源节点和目的节点加入共享树，并且对己选择中心进行更新。（6）智能优化算法近年来，研究人员将智能优化
17、算法应用到求解组播路由问题中，取得了良好的效果。这些智能优化算法主要包括遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法和人工神经网络等。遗传算法10具有简单性、并行性，健壮性和易于实现等优点，适用于在庞大而复杂的搜索空间中寻找最优解，在搜索过程中自动获取和积累有关搜索空间的知识，自适应地搜索控制过程，不断地缩小搜索空间，从而得到优化解，甚至最优解。近年来，随着对遗传算法的研究不断深入，发现采用该算法来求解NP完全问题能取得较好的效果。该方法同样适合求解QOS组播路由问题，目前遗传算法己在QOS组播路由问题得到初步的应用，使得QOS路由选择方法简单有效。以上是对于组播路由问题的研究现状，算法己经
18、比较成熟。但是随着网络规模的不断扩大和网络应用对服务质量的不断提高，双向请求应用不断涌现，即任何一端(多点和点)都有可能发起请求，还有各种网络应用要求多个用户的参与，例如资源查找、数据收集、网络竟拍、信息询问和Juke Box等10-11促进了对QOS多组播路由问题的研究。2 QOS组播通信2.1 QOS组播通信组播是指从源节点将同一份信息传递到多个目的节点的过程。组播源节点是指发起组播通信的节点，在“点对多点”的通信模式中，一次通信业务中只有一个组播源节点，在“多点对多点”的通信模式中，一次通信业务中可以有几个组播源节点；目的节点是指组播通信的接收者，通常在一次组播通信会有多个目的节点。QO
19、S组播路由是指在一个给定的通信网络中找到一个总代价最小且满足QOS约束(如带宽、时延等)的多个源节点到多个目的节点的路由集合。但是随着网络规模的不断扩大和人们对网络服务质量的要求不断提高，单单能够确定QOS组播路由是不够的，这就要求我们提出一种新的解决方案，就是在给定的网络中找到由多个源节点到多个目的节点的满足QOS约束的最优路径集合，这就是QOS多组播路由问题。2.2 组播通信的工作原理 组播是从一个发送者向多个接收者或者多个发送者向多个接收者发送数据包的过程。组播源把数据包发送到特定的组播组，而只有属于该组播组的地址才能接收到数据包。组播以最佳的方式将数据传输给所有主机，组的成员可以是动态
20、的，即组的成员可以在任何时间加入一个组或离开一个组，组的大小和位置没有限制，一个主机可以是多个组的成员。组播可以大大节省网络带宽，提高数据传送速率，减少主干网出现拥塞的可能性。因为无论有多少个目标地址，在整个网络上只传送单一的数据包。组播组中的主机可以是在同一物理网络，也可以是不同的物理网络(如果有组播路由器的支持)。为了满足多媒体实时应用的需求，很有必要寻求网络层对组播业务的支持，使组播技术满足此类应用的要求，建立组播树就可以实现这种需求。组播树是覆盖所有源节点和目的节点的一棵生成树，它具有以下优点：（1）信息可以沿着树的分支并行的传到各个目的节点，这可以降低信息传送时延；（2）信息只在树的
21、分支处进行复制，从而降低了信息复制的份数，这样可以节省带宽资源，提高资源利用率，降低拥塞的发生12-13。组播路由选择问题是指给定一个源节点S，一组目的节点，寻找一棵满足一定QOS约束C的最优可行多播树，如图1所示；也可以是一组源节点，一组目的节点，寻找多棵满足一定QOS约束C的最优可行多播树集，如图2所示。图1. 一个源节点到多个目的节点组播通信图 2. 多个源节点到多个目的节点多组播通信多组播通信典型应用包括：（1）多点会议：音/视频和白板应用构成多点会议应用。在多点会议中。不同的数据流拥有不同的优先级。传统的多点会议采用专门的多点控制单元来协调和分配它们，采用组播可以直接由任何一个发送者
22、向多个接收者发送数据，多点控制单元用来控制当前发言权，这类应用对带宽和时延要求都比较高。（2） 资源同步：如日程、目录、信息等分布数据库的同步。它们对带宽和时延的要求一般。（3）并行处理：如分布式并行处理。它对带宽和时延的要求都比较高。（4）协同处理：如共享文档的编辑。它对带宽和时延的要求一般。（5）远程学习：这实际上是媒体广播应用加上对上行数据流(允许学生向老师的提问)的应用。（6）讨论组：类似于基于文本的多点会议，还可以提供一些基本的表达。2.3组播路由算法的分类目前组播路由算法很多，可以根据不同的角度、不同的准则来分类。2.3.1集中式路由算法和分布式路由算法集中式路由算法是指在节点掌握
23、网络的整个拓扑结构信息的基础上，确定路由的算法。分布式算法不需要每个组成员掌握整个网络的拓扑，每个组成员在只有局部信息的条件下就可参与路由的确定。集中式路由的源路由采用集中式处理的方式，因此在发出路由请求时，可以立即获得预先存在的路由信息，进行路由计算；分布式路由不需要每个组成员掌握整个网络的拓扑，这对大型网络的多播路由是十分有利的。2.3.2静态型和动态型静态型是指在组播树生成以后就不再发生变化了，它不能根据当前组成员的加入或离开来调整路由，而是就近嫁接到开始选择好的路径上传送，它的路由修改要经过一定时间的运行后进行。显然这对于大部分应用来说是不合适的，而动态型则与此相反，在会话阶段，它允许
24、节点动态地加入和离开，这符合实际的要求，但同时也给算法带来了新的问题，由于动态路由算法对路由的频繁修正，将会使通信系统不稳定。2.3.3源基树型和共享树型源基树算法为组中每一个发送者建立一棵以发送者所在子网为根的组播树，每个路由器维护状态的组播路由表，源基树算法只适用于广播业务，另一类算法则为组内所有发送者与接收者建立一棵共享树，无论哪个源端都是用同一个组播树传输数据，这类算法适用于会议型业务(如计算机会议)，会议型业务具有以下特征：（1）既有一对多型传输，也有多对多型传输；（2） 对信息传送的时延有严格的要求；（3）数据量大，且媒体多样要求不同的处理；（4）在改变发言者时要进行快速的路由切换
25、。2.4 QOS组播的关键指标 目前的Internet仅提供尽力而为的传送服务，业务量尽快传送，没有明确的时间和可靠性保障。 随着网络多媒体技术的飞速发展，现有的尽力传送服务已无法满足各种应用对网络传输质量的不同要求，需要Internet提供多种服务质量类型的业务，而尽力而为的服务仍将提供给那些只需要连通性的应用。网络提供给用户的QOS是由各种网络参数决定的，QOS的关键指标主要包括：带宽、时延、时延变化(包括抖动和漂移)、可用性、吞吐量和包丢失率等，下面详细叙述： （1）带宽：单位时间内传送的数据包数量。多媒体业务的数据传输量往往较大，因此需要网络为其分配最小带宽。如标准电话为64kbits
26、/s，压缩过的HDTV为25-34Mbits/s，视频会议为0.1-2Mbits/s。（2）时延：指一项服务从网络入口到出口的平均经过时间。许多服务都是高度不能容忍时延的。当时延超过200-250毫秒时，交互式会话是非常麻烦的。为了提供高质量话音和会议电视，网络设备必须能保证低的时延。产生时延的因素很多，包括分组时延、排队时延、交换时延和传播时延。传播时延是信息通过铜线、光纤或无线链路所需的时间，传播时延总是存在的。时延变化是指同一业务流中不同分组所呈现的时延不同。高频率的时延变化称作抖动，而低频率的时延变化称作漂移。（3）可用性：是当用户需要时网络即能工作的时间百分比。可用性主要是设备可靠性
27、和网络存活性相结合的结果。对它起作用的还有一些其他因素，包括软件稳定性以及网络演进或升级时不中断服务的能力。（4）吞吐量：是在一定时间段内对网上流量(或带宽)的度量。一般讲，吞吐量越大越好。（5）包丢失率：不管是比特丢失还是分组丢失，对分组数据业务的影响比对实时业务的影响都大。在通话期间，丢失一个比特或一个分组的信息往往用户注意不到。在视像广播期间，这在屏幕上可能造成瞬间的波形干扰，然后视像很快恢复如初。即便是用传输控制协议(TCP)传送数据也能处理丢失，因为传输控制协议允许丢失的信息重发。事实上，一种叫做随机早丢(RED)的拥塞控制机制在故意丢失分组，其目的是在流量达到设定门限时抑制TCP传
28、输速率，减少拥塞，同时还使TCP流失去同步，以防止因速率窗口的闭合引起吞吐量摆动。但分组丢失多了，会影响传输质量。QOS组播技术具有以上诸多的关键指标，但是带宽约束和时延约束是其中最关键的两个指标，对组播技术的性能影响最大，所以本文的算法主要考虑带宽约束和时延约束。3遗传算法遗传算法研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国密执安大学的Holland教授与其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过20余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来，智能计算己成
29、为人工智能研究的一个重要方向。3.1遗传算法概述遗传算法的寻优过程是一个迭代过程，通过基因转换机制，每一代中的基本特征被遗传到下一代。一般来说，遗传算法主要包括以下三个操作算子：选择(selection)、交叉(crossover)和变异(mutation)。简单地说，选择就是从一个旧群体中挑出生命力强的个体用于产生新群体的过程。它意味着适应度高的个体在下一代中复制自身的个数多；交叉是指随机从群体中选择两个个体，并按较大的概率交换这两个个体的某些位；变异是以较小的概率对群体中某些个体的位进行改变。遗传算法包含如下五个要素：（1）参数编码；（2）初始群体的产生；（3）适应度函数的设计；（4）遗传
30、操作设计；（5）控制参数的设计。遗传算法的一个周期的运行如图3所示 图3. 遗传算法的进化过程示意图3.2遗传算法的发展历史 遗传算法起源于对生物系统进行的计算机模拟研究。早在20世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程等研究工作。进入20世纪60年代后，Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。下面简要介绍一下遗传算法在国内外的发展历程。20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统
31、的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。20世纪70年代初，Holland教授提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统(Classifier Systems，简称CS)，开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。1975年，De Jong在其博士论文中结合模式定理
32、进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。例如：对于50-100群体，经过10-20代的进化，遗传算法能以很高的概率找到最优解或近似最优解。1989年，Goldberg出版了专著搜索、优化和机器学习中的遗传算法(Genetic Algorithms in Search，optimization and Machine Learning)。该书系统的总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。1992年，Koza将遗传算法应用到计
33、算机程序的优化设计及自动生成，提出了遗传编程(简称GP)的概念。他将一段LISP语言程序作为个体的基因座，把问题的解编码为一棵树，基于遗传和进化的概念，对由树组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。Koza成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。我国有关遗传算法、进化计算的研究从20世纪90年代以来一直处于不断上升的地位，特别是近年来，遗传算法、进化计算的应用在许多领域取得了令人瞩目的成果。武汉大学刘勇、康立山等于1995年出版了非数值并行计算(第2册)遗传算法；潘正军、康立山等于1998年出版了演化计算；周明、孙树栋于1999年出版了遗传算法原理；王
34、小平、曹立明于2002年出版了遗传算法理论、应用与软件实现。3.3遗传算法的基本操作(1)参数编码如何将问题描述成串的形式，即参数编码。在参数优化等问题中，一般将各参数用二进制编码，构成子串，再将子串拼接起来构成“染色体”串，但是不同的串长和不同的码制，对问题求解的精度和GA (Genetic Algorithm)收敛时间会有很大影响，对于复杂问题如变结构控制器，神经网络等，如何将问题描述成串的形式就不那么简单了，而且同一问题可能有不同的编码方法。由于遗传算法不能直接处理解空间的数据，因此必须通过编码将其表示成遗传空间的数据结构。目前常用的编码方式有二进制编码、实数编码等。(2)初始群体设定由
35、于遗传算法的群体型操作需要，必须为遗传操作准备一个由若干个初始解组成的初始群体。需要说明的是，初始群体的每个个体都是通过随机方法产生的。初始群体也称为进化的初始代，即第一代(first generation)。(3)个体适应度评价在遗传算法中，以个体适应度值的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度值越大，个体被遗传到下一代群体中的概率也越大；反之，个体的适应度值越小，该个体被遗传到下一代的概率也越小。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度值必须为正数或零，不能为负数。对于求目标函数最小值的优化问题，理论上只需要简单地对其增加一个负号就可以将其转化为求目标
36、函数最大值的优化问题，即： (3.1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度值F(X)就等于相应的目标函数值f(X)，即： (3.2)但是实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度值都是非负数这个要求。所以必须寻求出一种通用且有效的由目标函数值到个体适应度值之间的转换关系，由它来保证个体适应度值总取非负数。为满足适应度值总取非负数的要求，遗传算法一般采用以下两种方法将目标函数值f(x)变换为个体的适应度值F(x)。方法一：对于求目标函数最大值的优化问题，变换方法为： (3.3)式
37、中为一个适当的相对较小的数，它可用下面几种方法之一来选取。预先指定的一个较小的数;进化到当前代为止的最小目标函数值;当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为： (3.4)式中，为一个适当的相对较大的数，它可用下面几种方法之一来选取。预先指定的一个较大的数;进化到当前代为止的最大目标函数值;当前代或最近几代群体中的最大目标函数值。(4)选择算子选择算子(selection operator)的作用是从当前群体中选择出一些比较优良的个体，并将其复制到下一代群体中。选择操作是建立在群体中个体的适应度值评估基础上的，其中最常用的选择算子是比例选择算子。
38、比例选择算子是指个体被选中并遗传到下一代群体中的概率与该个体的适应度值大小成正比。比例选择实际上是一种有退还随机选择，也叫赌盘(Roulette Wheel)选择，如图4所示，因为这种选择方式与赌博中的赌盘操作原理颇为相似。图4 赌盘选择法的示意图整个赌盘被分为大小不同的一些扇面，分别对应着价值各不同的一些赌博物品。当旋转着的赌盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。虽然赌盘的指针具体停止在哪个扇面是无法预测的，但指针指向各个扇面的概率却是可以估计的，它与各个扇面的圆心角大小成正比；圆心角越大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。与此类似，在遗传算法中
39、，整个群体被各个个体所分割，各个个体的适应度值在全部个体的适应度值之和中所占的比例也大小不一，这个比例值瓜分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。赌盘选择的特点是对于种群中的所有个体，无论其适应度值大小，都有被选择的机会。适应度值小的个体被选中的概率小，因此，一般来说，经过选择后它在种群中的数量会减少；而适应度值大的个体被选中的概率大，因此，经过选择后它在种群中的数量将会增加。这正是体现了“适者生存”的原则。比例选择算子的具体执行过程是： 首先计算出群体中所有个体的适应度值的总和； 其次计算出每个个体的相对适应度值的大小，它即为各个个体被遗传到下一代群体中的概率； 最
40、后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个体被选中的次数。(5)交叉算子在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样，在遗传算法中起核心作用的是遗传操作的交叉算子(crossover operator)。交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。 目前，主要有单点交叉、二点交叉、多点交叉三种方式。单点交叉是最常用的交叉操作算子。单点交叉算子的具体执行过程如下： 对群体中的个体进行两两随机配对。若群体大小为，则共有对相互配对的个体组。其中表示取不大于x的最大的整数； 对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为L，则共有(L-l)个可能的交叉点位置； 对每一对相互配对的个体，依设定的交叉概率,在其交叉处相互交换两个个体的部分染色体
