遗传算法在网络可靠性中的应用

遗传算法在网络可靠性中的应用

徐冰

遗传算法在网络可靠性中的应用

徐冰

（沈阳职业技术学院，辽宁沈阳110045）

摘要：智能优化算法作为解决诸多大规模复杂工程问题的有效方法，已经在很多领域显示出了其不可比拟的优越性。遗传算法作为智能优化方法的典范，以其高效性、通用性、鲁棒性和全局收敛性等一系列优点已经在许多领域得到广泛应用，在网络可靠性中同样适用。

关键词：智能优化算法；可靠性；遗传算法

引言：20世纪80年代以来，一些新颖的优化算法，如遗传算法、模拟退火算法、蚁群算法、粒子群算法及其各种混合优化策略等，通过模拟或揭示某些自然现象或过程而得到发展，其思想和内容涉及生物进化、物理学以及人工智能等方面，为解决大规模复杂问题提供了新的思路和手段。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在许多领域得到了成功应用和推广。在优化领域，由于这些算法构造的直观性与自然机理，因而通常被称为智能优化算法或称现代启发式算法。近年来，随着智能优化算法理论的不断发展丰富、应用研究的不断广泛深入，使其业已成为解决诸多大规模复杂工程实际问题的有利工具和有效方法。用遗传算法、模拟退火算法、蚁群算法、粒子群算法及其混合优化算法等智能优化方法来研究可靠性综合问题，特别是大型复杂网络的可靠性优化、冗余的最优分配以及网络的最优设计，是十分有效的，可以获得较传统方法和启发式方法更好的优化方案。

1算法简介

遗传算法（GeneticAlgorithm，GA）是一种借鉴生物界自然选择思想和遗传机制的全局随机搜索算法。它把问题的可能解组成种群，把每一个可能的解看作种群的个体，运行时，算法在整个种群空间内随机搜索，按一定的评估策略对每一个体进行评价，不断使用选择、交叉、变异这3种遗传算子，使问题的解不断进化，直至产生最优解。

GA基本内容包括编码结构、种群初始化、选择操作、遗传操作（交叉和变异）、目标函数以及适应度函数设计、终止条件选择等。其中，选择、交叉和变异三种操作是遗传算法的核心，选择操作是根据父代中个体适应度函数值大小进行选择或淘汰，保证了算法的最优搜索方向；交叉操作是产生新个体的主要方法，它决定GA的全局搜索能力；变异操作是产生新个体的辅助方法，它决定GA的局部搜索能力。

GA控制参数主要包括：种群规模、交叉率、变异率以及其它一些GA参数（如最大迭代次数等）。GA参数的选择对于算法的最终优化效果至关重要，目前，多以大量试验测试的方法来确定这些参数。

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

2算法设计

2.1编码结构。符号说明：

N节点集合；

（i，j）两节点i和j间的链路；

p链路的可靠度；

xij决策变量，

P（X）X的全终端可靠度；

R0网络要求的可靠度；

cij（i，j）的成本。

C0链路总成本上限；

每个代表具有个体位串长度为N（N-1）/2的一个网络在某种连通情况下可能链路的组合情况。例如，图1是一个由5个节点和7条链路构成的图的典型网络。

图1典型网络

表示此网络的位串是：

［1101101101］

［x12x13x14x15x23x24x25x34x35x45］

如下就是在后断点处的单点交叉的研究：

祖先1：

［1101101101］

［x12x13x14x15x23x24x25x34x35x45］

祖先2：

［1011001111］

［x12x13x14x15x23x24x25x34x35x45］

子孙1：

［1101001111］

［x12x13x14x15x23x24x25x34x35x45］

子孙2：

［1011101101］

［x12x13x14x15x23x24x25x34x35x45］

为了更形象地刻画交叉操作的实现过程，以图形方式对上述过程进行了辅助说明，如图2、3所示。

图2两个祖先个体网络拓扑图

（a）（b）

其中，图2a、b中网络拓扑分别对应祖先1和2两个个体，图3a、b中网络拓扑分别对应单点交叉后产生的子孙1和2两个个体。由此可见，子孙个体是在保留祖先个体部分链路的基础上通过交叉操作进行局部改变而得到的。

2.2目标函数和适值函数。对于极大化可靠度模型，将目标函数和适值评价函数设计为同一个函数

R（X）=RU（X）（1）

图3两个子孙个体网络拓扑图

（a）（b）

2.3选择。选择过程采用最优保留选择。首先按轮盘赌选择方法执行GA的选择操作，然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。其主要优点是保证GA终止时得到的最后结果是历代出现过的最高适应度的个体。

2.4遗传。GA中遗传包括交叉和变异两种操作。交叉操作是产生新个体的主要方法，它决定遗传算法的全局搜索能力；变异操作是产生新个体的辅助方法，它决定遗传算法的局部搜索能力。此处采用单点交叉和小概率变异。

结语：随着进化计算、智能优化算法的广泛应用和不断发展，使网络可靠性优化研究向前迈进了一大步，出现了大量研究与应用方面的文章，如有学者将遗传算法及其改进方法用于求解网络规划问题，取得了较为满意的优化方案[1，2]。有学者提出了一种近似评估通信网络可靠性的新方法，并以此作为可靠性指标对通信网络可靠性的优化设计问题进行了研究[3]。有学者将一种粗粒度并行遗传算法应用于求解计算机网络可靠性优化设计问题，并与传统串行遗传算法进行比较，验证了该算法的有效性[4]。有学者把遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法等进化算法应用于解决系统可靠性优化问题并进行了比较[5]，等等。其中，在网络终端可靠性优化研究上成果相对较少，更是今后研究工作的一个重点，也是努力的方向。

参考文献

[1]叶剑，席裕庚，曲润涛.基于遗传算法的可靠性网络规划设计[J].通信技术，1999（2）：15-18.

[2]刘强，李积源.基于遗传算法的通信网络可靠性优化设计[J].海军工程大学学报，2001，13（6）：102-106.

[3]郭伟，邬燕萍.通信网可靠性的评估及其优化设计[J].系统工程理论与实践，1998，18（11）：46-52.

[4]郭彤城，慕春棣.并行遗传算法在一类计算机网络可靠性优化问题中的应用[J].系统工程理论与实践，2003，23（1）：31-36.

[5]高尚，杨静宇，吴小俊等.可靠性优化的蚁群算法[J].计算机应用与软件，2004，21（12）：94-96.