基于遗传算法的计算机通信网络可靠性分析及优化.doc

《基于遗传算法的计算机通信网络可靠性分析及优化.doc》由会员分享，可在线阅读，更多相关《基于遗传算法的计算机通信网络可靠性分析及优化.doc（6页珍藏版）》请在三一办公上搜索。

1、精品论文基于遗传算法的计算机通信网络可靠性分析及优化张子木 北京邮电大学信息与通信工程学院，北京 (100876) E-mail: zhangzimu88摘要：随着计算机技术和通信技术的迅猛发展，计算机通信网络将遍及社会生活的方方面面，如何设计一个高性能、低成本、易扩充的网络拓扑结构是摆在每个网络管理人员面前的 一个不可回避的现实问题。计算机通信网络拓扑结构设计问题的关键在于其主干网拓扑结构的规划设计，主干网设计过程中要考虑的一项关键技术指标就是网络的可靠性。本文在分析计算机网络可靠性理论的基础上，讨论了计算机通信网络中的遗传算法，在给定的优化设计 可靠度目标要求下，完成了对一组网络通信系统的

2、优化分析，结果显示本文进行的基于遗传算法的计算机通信网络可靠性优化设计方案是有效的,文中提出的具体优化方案具有实际应 用价值和现实指导意义。关键词：可靠性；计算机通信网络；多目标优化 中图分类号：TP3931引言随着计算机通信网络技术的迅速发展，系统可靠性研究越来越为人们所关注。系统可靠 性最优化问题也称网络综合性分析，传统的研究方法有动态规划、Lagrange乘子法、梯度法、 启发式方法、几何规划以及整数规划等1-5。近年来，随着神经网络与进化计算技术的发展， 网络综合性分析的研究得到了长足发展。通信网络的优化设计问题，主要是考虑网络成本、 平均时延和可靠性这些因素。尤其是现在通信网络飞速发

3、展，可靠性和网络成本是其主要的 两个因素。网络的优化设计的核心问题是如何使网络的可靠性尽可能高，而网络费用尽可能 低，但这是个NP-hard问题3,4。计算机通信网络可靠性优化与设计是由 Boesch 首先提出来的，主要涉及网络可靠性优 化和网络可靠性的拓扑结构规划设计问题。Aggarwal 等人以计算机通信网络为例，对基于全终端可靠性的大规模网络拓扑优化设计问题进行了较为详尽的研究和探讨3。SmithA E, Deeter 等人对全终端网络可靠性优化问题进行了探索性的研究，并将启发式方法、遗传算法 等首次应用与求解该类优化问题，取得了较传统方法更为有效的满意结果。在进行网络可靠 性优化设计过

4、程中网络可靠性的计算至关重要，有关网络可靠性计算问题 Satyanarayana 等 人已给出了一些算法，Elmallan, Ayoub 等人对 K 一终端可靠度问题进行了深入的分析，提出了一些算法，Jan R H 等人在对全终端网络可靠性进行深入研究的基础上，给出了全终端可靠度界的计算公式。Smith A E 等人在 Jan R H 等人的全终端可靠度界的基础上进行了改 进，提出了一种更为有效的上界。对于一般网络，Colbourn, Satyanarayana 等人验证了计算2 一终端可靠度、K 一终端可靠度和全终端可靠度是 NP 难问题3。总体来说，国外在该方 面的研究已有了较为深入的研究

5、，业已出现了不少有价值的研究成果。目前基于可靠性约束的多目标网络优化方面在国内研究较少，传统的都是以网络最小费 用作为约束条件进行网络拓扑结构设计，本文将在分析计算机网络可靠性理论基础上，提出 并进行采用遗传算法的计算机通信网络可靠性的多目标优化设计研究，旨在通过理论和具体 实例的分析，为相关研究提供一些技术支持和理论指导。-6-2计算机通信网络的可靠性理论2.1 网络可靠性与可靠度的定义计算机网络可靠性有关概念作为一门系统工程科学，经过半个多世纪的发展，己经形成 了较为完整、健全的体系。国内外的有关学者将计算机网络可靠性的测度归纳为四大类：计 算机网络的连通性、计算机网络的生存性、计算机网络

6、的抗破坏性、计算机网络部件在多模 式下工作的有效性2,4。计算机网络如果正常工作，网络中的基础结点及部件必须为各个用 户终端提供可靠的链路。因此，计算机网络的连通性在可靠性相关领域研究中最为广泛。计 算机网络的连通性一般用计算机网络可靠度来衡量。2.1.1 计算机通信网络可靠性 计算机通信网络在规定的条件(操作方式、维修方式、负载条件、温度、湿度、辐射等)下，规定的时间(1000 小时、一个季度等)内，网络保持连通和满足通信要求的能力，称之为计算机通信网络可靠性。它反映了计算机通信网络拓扑结构支持计算机通信网络正常运行的 能力，是计算机通信网络规划、设计与运行的重要参数之一。2.1.2 计算机

7、通信网络可靠度 计算机通信网络在规定的条件(操作方式、维修方式、负载条件、温度、湿度、辐射等)下，规定的时间(1000 小时，一个季度等)内，网络完成规定功能的概率，称之为计算机通信网络的可靠度，记为 R(t)，其中 R (t ) = P T t 。计算机通信网络可靠度具有三个类型：(1) 2 一终端可靠度，即在概率图中，指定源点 s 和汇点 t 之间至少有一条正常运行的链 路的概率，记为 Rel2(G)。(2) 一终端可靠度，即在概率图中，指定 个结点所构成集合中的任意两对结点之间， 均有正常运行的链路的概率，记为 Re l (G)。(3) 全终端可靠度，即在概率图中，指定任意两结点之间，均

8、有正常运行的链路的概率， 记为 Re lA (G)。从以上定义可以得到，当 =2 或 =n 时， 一终端可靠度就是 2 一终端可靠度或者全终 端可靠度，因此 2 一终端可靠度和全终端可靠度可以看成是 一终端可靠度的特例。一般情 况下，用 Re l(G)来表示上述三种计算机通信网络可靠度的总称。2.2 网络可靠性模型在系统工程研究领域中，许多复杂系统甚至是复杂巨系统都可模型化为网络模型，进而 将网络模型再进一步模型化为图的可靠性问题来求解，例如能源供给网络，通信网络，交通 运输网络，部队装备物资保障网络等等。计算机通信网络可靠性问题也可以模型化为图的可 靠性问题。计算机通信网络模型采用概率图 G

9、(V, E)来表示，其中结点集合 V 表示计算机网 络的用户终端，主机或服务器等，边集合 E 表示计算机通信网络的链路。该类问题一般有 以下六点假设：(1)计算机通信网络是连通的，可用数学上的图 G(V, E)来刻画，且图 G 中任何两结点之 间不多于一条直接相连的链路；(2)计算机通信网络链路介质的可靠度与介质的长度无关； (3)计算机通信网络结点本身不发生故障； (4)计算机通信网络结点和链路的工作状态只有两种：正常与故障，且故障的发生是相互独立的；(5)计算机通信网络结点和链路的正常运行的概率已知，且计算机通信网络结点和链路 的正常状态在概率统计上是相互独立的；(6)计算机通信网络模型也

10、可以用多状态模型来刻画。 计算机通信网络模型的概率图，是对图的各边以及结点的正常运行状态赋予一定的概率值以后所得到的图。图的可靠性问题包含两个方面的内容：一是分析问题，即计算一个给定 图的可靠度；二是设计问题，即在给定所有元素后，设计具有最大可靠度的图。图的可靠度 不方便求解时，可先求其失效度(可靠度+失效度=1)，然后再求其可靠度。图的结点和链路 失效模型可分为链路失效模型、结点失效模型、结点和链路混合失效模型等三种类型，其中 “结点和链路棍合失效模型”最为常用。3通信网络可靠度的智能算法分析计算机通信网络可靠度的现代智能算法非常适用于网络结点和链路数目较多，网络规模 较大的复杂的计算机通信

11、网络可靠度的计算。计算机通信网络可靠度的现代智能算法对于传 统精确算法不能解决的计算机通信网络可靠度的计算问题显得特别有效。目前比较流行的现 代智能算法有遗传算法、模糊遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法、神经网 络方法、模糊神经网络方法等。与此同时，随着算法复杂性理论(Computational Complexity Theory)的完善，在优化问题中，已经不再一味强调要求得到最优解。1978 年，美国著名的人工智能专家 H. A. Simon 提出用满意方案代替最优方案的思想， 把满意解的寻求过程命名为“satisficing”，提出了“令人满意准则”。而在同一时期，人工智能 (

12、Artificial Intelligence)方面的研究取得了惊人的成就。在研究知识在人工智能领域的重要作用时，一些学者将“智能”定义为1：当一个系统具有可运用的知识时，智能就是在巨大的搜索空间中迅速地找出一个满意解的能力。任平教授首先对满意解进行了数学分析，利用模糊 数学的隶属函数、子集、截集等概念，将满意解定义为某一论域在约束条件构成的子集的限 制下所形成的截集，同时提出使用模糊集合论的方法来研究满意解集2。上世纪九十年代， 西南交通大学的靳蕃教授在研究人工神经网络(ANN : Artificial Neural Network)过程中，通过 比较传统的 Von Neumann 计算机与

13、人脑的结构特点、运行机制和求解方法，发现人脑之所 以在高级智能信息处理领域比电脑“聪明”，不仅在于前者的巨大并行分布拓扑结构，因为它 寻求满意解的运算原则。在此基础上，首先提出了“神经计算的满意解原理”。上海交通大学 席裕庚教授在研究复杂工业过程环境的基础上，总结出控制是有约束多目标多自由度优化的 特点(CMMO)，提出了满意控制概念和原理框架 Izollzil。对于多目标满意优化问题，西南交 通大学的金炜东教授研究了评价满意解性能的满意度函数，针对优化问题的比较复杂的情况 提出了串行求解结构和并行求解结构，提出了一种多目标满意优化计算模型和“局部一全局 型满意优化模型”，并将其应用于列车操纵

14、优化、控制器参数优化设计、数字滤波器优化设 计等方面，获得了令人满意的效果。从而将满意优化的研究在理论和实际应用上又向前推进 了一步。本文中利用遗传算法来计算计算机通信网络的可靠度，通过实例仿真，实现了遗传算法 的计算过程。4基于遗传算法的计算机通信网络优化算法遗传算法(Genetic Algorithm, GA)是一种借鉴生物界自然选择思想和遗传机制的全局随机搜索算法。它把问题的可能解组成种群，把每一个可能解看作种群的个体，运行时，算法在整个种群空间内随机搜索，按一定的评估策略对每一个体进行评价，不断使用选择、交叉、 变异这 3 种遗传算子，使问题的解不断进化，直至产生最优解。GA 执行流程

15、如图 1 所示。遗传算法的主要步骤如下：图 1 GA 基本流程图(1) 确立一种编码方案，经编码后的序列成为染色体，组成编码的元素称为基因(Gene)随机产生一组初始染色体，该组染色体成为初始群体；(2) 适应度运算：将群体中的各染色体解码，成为一组解，通过运算，求出各染色体的 适应度；(3) 选择运算：以适应度的大小确定各条染色体遗传到下一代群体中的概率，并随机生 成下一代中的染色体；(4) 交叉运算：对群体中的染色体配对后，按交叉概率互换部分染色体；(5) 变异运算：按变异概率，在变异点改变其染色体的基因值。重复进行 2)-5)步骤的迭代运算，直到产生满足停止规则的优良个体为止。将满意优化

16、 和遗传算法结合后，在用遗传算法寻优的过程中，以综合满意度函数值作为适应值，得到的 达到用户要求的最高综合满意度的主干网设计即为优化结果。GA 基本内容包括编码结构、种群初始化、选择操作、遗传操作(交叉和变异)、目标函 数以及适应度函数设计、终止条件选择等。其中，选择、交叉和变异三种操作是遗传算法的 核心，选择操作是根据父代中个体适应度函数值大小进行选择或淘汰，保证了算法的最优搜 索方向；交叉操作是产生新个体的主要方法，它决定 GA 的全局搜索能力；变异操作是产生 新个体的辅助方法，它决定 GA 的局部搜索能力。GA 控制参数主要包括：种群规模、交叉率、变异率以及其它一些 GA 参数(如最大迭

17、代 次数等)。GA 参数的选择对于算法的最终优化效果至关重要，目前，多以大量试验测试的方 法来确定这些参数。遗传算法作为一种典型智能优化方法，同传统优化方法相比具有如下特点：(1) 一般而言，遗传算法的操作对象是参数的编码，而非参数本身，从而避免了约束条 件限制 (如可导性、连续性、单峰性等)，拓宽了算法的应用范围；(2) 遗传算法的搜索方式是多点并行搜索，而非单点搜索，从而可以有效地防止搜索过 程收敛于局部最优；(3) 遗传算法的评估策略依赖于目标函数和适应度函数的值，而与辅助信息和辅助知识无关，从而减小了对问题的依赖程度；(4) 遗传算法的寻优规则是不确定性概率变迁规则，而非确定性规则，从

18、而引导搜索向 全局最优解方向前进。正因为遗传算法在解决大空间、非线性、全局寻优等复杂问题时具有传统方法所不具备 的上述一系列独特的优越性，所以它自从 70 年代由美国学者 Holland J H 提出以来，己经得 到了广泛的研究和应用。但遗传算法仍存在许多缺陷和不足之处：1)遗传算法容易出现过早 收敛现象，即在进化群体中少数个体的适应度函数值远大于其它个体，因此，它们参与选择 复制操作的概率很大，受交叉、变异操作的影响很小，于是，经过少数几次迭代后，这些个 体就占据了整个群体，进化过程提前收敛；2)遗传算法的局部搜索能力较差，主要原因是遗 传算法的交叉操作容易破坏当前模式，使得小范围的精确搜寻

19、很困难：3)遗传算法在进化后 期搜索效率较低，这使得最终搜索得到的结果往往不是全局最优解，而是局部最优解。GA 是近年来提出的一种新型优化方法，它具有全局性好、易操作、并行搜索、群体寻 优的特点3-5。由于 GA 不受优化问题本身性质、优化准则形式、模型结构形式、被优化参 数数目和有无约束条件等的限制，它仅仅采用目标函数在概率准则引导下进行并行全局自适 应自动搜索，就能够处理传统优化方法难以解决的复杂问题，具有极高的鲁棒性和广泛的适 用性，因此 GA 主要应用于诸如可靠性设计方面的一些 NP-hard 问题。5优化结果分析本文中提出的 GA 是在 matlab 环境下运行，GA 参数为：种群大

20、小 POPXZE=100，最大 迭代次数 MAXGEN=500，交叉率 pc=0.3，变异率 pm=0.7，程序迭代次数为 32 次，每次运 行都随机生成不同的种群，然后取这 20 次得到的最好结果进行比较。若在优化时，将网络费用，平均时延和可靠性放在同等重要的位置，则在计算综合满意 度时将这三个性能指标的权值分别取 Wc =Wr= Wd =1/3，优化结果如表 1。由于在初始化和 变异的过程中，将不满足可靠性约束的解去掉，可以不考虑可靠性，然后将网络费用，平均 时延放在同等重要的位置，则在计算综合满意度时三个性能指标的权值分别取 Wc= Wd=0.5，Wr =0，优化结果如表 1；可见通过这

21、些不同权重的可靠度条件下，均能得到较好的 满意度。可以说采用了遗传算法后，在最短的时间内可找到令人满意的解，能成功解决了高可靠性低成本的 NP-hard 问题，快速实现并解决计算机通信网络的拓扑优化问题。表 1 不同权值下的各性能指标与 GA 优化结果权值网络费用可靠性费用满意度可靠性满意度综合满意度Wc =Wr=Wd=1/360110.99510.984Wc=Wd =0.5, Wr =06090.93540.9740.9620.9956结论(1) 讨论并分析了计算机通信网络可靠度的理论，可知可靠度反映了计算机网络拓扑结 构支持计算机网络正常运行的能力，是计算机网络规划、设计与运行的重要参数。

22、(2) 将多目标优化和遗传算法结合后，在最短的时间内找到令人满意的解，成功解决了 高可靠性低成本的 NP-hard 问题。参考文献1 虞红芳，詹柔莹，李乐民. 一种启发式的计算机局域网拓扑优化设计方法J. 通信技术 2002(3)：18-20 2 Jong Ryul Kim and Mitsuo Gen. Genetic algorithm for solving bicriteria network topology design problemJ. IEEE 1999: 2272-22793 叶剑，席裕庚，曲润涛. 基于遗传算法的可靠性网络规划设计J. 通信技术, 1999, (2) :

23、15-184 刘强，李积源. 基于遗传算法的通信网络可靠性优化设计J. 海军工程大学学报, 2001, 13 (6): 102-106 5 孙立山，郝燕玲. 基于混合遗传算法的网络拓扑设计J. 计算机工程, 2006, 32 (3) : 25-27Computer Communication Network Reliability Analysis andOptimization Design Based on Genetic AlgorithmZhang ZimuSchool of Information and Communication Engineering, Beijing Univ

24、ersity of Posts andTelecommunications, Beijing (100876)AbstractWith the rapid development of computer and communication technology, the computer network ispopular throughout peoples lives. It is an inevitable problem how to design a network topology structure of high capacity, low cost, easy expansi

25、on to every network manager. The key of computer communication network topology structure is the planning design of back-bone network topology structure, and during the back-bone network designing, the key guideline is network reliable capacity. Based on analyzing the fundamental of computer communi

26、cation network theory, this paper introduced the principle of Genetic Algorithm, and to meet the demand of the given network optimal design reliability, accomplished the optimization analysis of a set of network communication systems. The result showed that the method of computer communication network reliability optimization design Based on Genetic Algorithm that this paper proposed is highly effective, and the concrete optimal design plan has practical application significance.Keywords: Reliability; Computer Communication Network; Multiple-objective Optimization Design