网络可靠性优化方法总结 概述：目前较流行的智能优化方法包括遗传算法以及群智能算法。这两种优化算法的共同特点就是模拟生物行为方式，进行全局随机搜索，在单目标或多目标问题中找到最优解。应用到网络中比如用于网络路由的自适应调整，解决 QoS 组播路由问题，在费用最低情况下求解使整个网络可靠性最有拓扑等等 遗传算法（GA） 遗传算法 (GA)是一种借鉴生物界自然选择思想和遗传机制的全局随机搜索算法。它把问题的可能解组成种群，把每一个可能解看作种群的个体，运行时，算法在整个种群空间内随机搜索，按一定的评估策略对每一个体进行评价，不断使用选择、交叉、变异这3种遗传算子，使问题的解不断进化，直至产生最优解。

GA基本内容包括编码结构、种群初始化、选择操作、遗传操作(交叉和变异)、目标函数以及适应度函数设计、终止条件选择等。其中，选择、交叉和变异三种操作是遗传算法的核心，选择操作是根据父代中个体适应度函数值大小进行选择或淘汰，保证了算法的最优搜索方向；交叉操作是产生新个体的主要方法，它决定GA的全局搜索能力；变异操作是产生新个体的辅助方法，它决定GA的局部搜索能力。 GA控制参数主要包括：种群规模、交叉率、变异率以及其它一些GA参数(如最大迭代次数等)。GA参数的选择对于算法的最终优化效果至关重要，目前，多以大量试验测试的方法来确定这些参数。 (1) 编码。 • 遗传算法不能直接处理解空间的数据，因此需要通过编码把问题的解表示成遗传空间里的染色体。 (2) 群体初始化。 • 需要考虑两个问题： • 1、群体的规模 • 2、群体个体产生方法 ： • (a) 在遗传空间中直接产生，即在遗传空间中随机地产生染色体。 • (b)编码产生。 （3）适应度评估 • 选择操作是以染色体的适应度为依据进行的，适应度通过适应度函数计算得到。染色体的适应度应该要能准确地描述染色体所对应的解的性能好坏：染色体的适应度越大，表明解的质量越高，该个体被选择成为父代进而产生后代的的概率越大。

• 通常，在设计适应度函数时，要遵循以下原则： • (1) 单值性。 (2) 非负性。 (3) 计算量小。

• 适应度函数对遗传算法的影响主要体现在三个方面： • (1) 适应度函数和选择算子共同决定了群体中各个染色体产生后代的概率。适应度越大的个体产生后代的概率越大。 • (2) 遗传算法的终止条件受到适应度函数的影响。 • (3) 问题的约束条件在适应度函数中考虑。 （4）选择算子 • 从当前群体中挑选出优良的个体直接遗传到下一代或通过交叉操作产生新个体，从而将解的优良性状遗传给子代。越优良的个体，被选成父代进行遗传操作的机会越大。保证了方法的最有搜索方向。 • 几种常见的选择算子: • 1、轮盘赌选择法 • 2、锦标赛选择法 • 3、排序选择法 • 4、最佳个体保存法 （5）交叉算子 • 交叉算子模拟自然界生物进化过程中的基因重组，把两个父个体的部分结构进行重组替换从而产生适应度更高的个体。交叉操作保证了算法的全局搜索能力。

• 交叉操作一般需要以下两个步骤来完成： • (1) 选择一对个体作为父个体。 • (2) 根据某个概率，即交叉概率，实施交叉操作，从而产生一个新个体。 • （6）变异算子 • 变异算子模拟自然界生物进化过程中的基因突变，变化个体中的某些结构从而引入初始群体中不包含的基因模式。 • 变异算子的作用： • 1、变异算子使得遗传算法具有局部最优搜索能力。当遗传算法通过交叉算子接近问题解空间的最优领域时，变异算子可以加速遗传算法收敛于最优解。 • 2、变异算子随机地引入初始群体中不含的个体模式，保持群体的多样性，防止遗传算法由于过早收敛从而陷入局部最优。 • 变异算子的步骤一般是： • (1) 选择变异个体。 • (2) 在变异个体中选择基因座（发生变异的位置）。 • (3) 按照变异概率对个体进行变异操作。 优点 • 1)一般而言，遗传算法的操作对象是参数的编码，而非参数本身，从而避免了约束条件限制(如可导性、连续性、单峰性等)，拓宽了算法的应用范围 • 2)遗传算法的搜索方式是多点并行搜索，而非单点搜索。从而可以有效地防止搜索过程收敛于局部最优。 • 3)遗传算法的评估策略依赖于目标函数和适应度函数的值，而与辅助信息和辅助知识无关，从而减小了对问题的依赖程度。 • 4)遗传算法的寻优规则是不确定性概率变迁规则，而非确定性规则，从而引导搜索向全局最优解方向前进 缺点 • 1)遗传算法容易出现过早收敛现象。 • 2)遗传算法的局部搜索能力较差，主要原因是遗传算法的交叉操作容易破坏当前模式，使得小范围的精确搜寻很困难。 • 3)遗传算法在进化后期搜索效率较低，这使得最终搜索得到的结果往往不是全局最优解，而是局部最优解。

群智能算法(OPA)：包括蚁群优化算法，粒子群算法，人工鱼群算法等。

蚁群算法（ACO） 蚁群优化算法（Ant colony optimization ACO）是一种随机搜索算法，它基于对自然界真实蚁群的集体觅食行为的研究，模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。 AS 算法主要包括两个基本阶段：适应阶段和协作阶段．在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息素数量越大，则该路径越容易被选择，时间越长，信息素数量越少；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解． 蚁群算法实现步骤 为了能够清楚的理解蚂蚁系统的数学模型，仍以求解平面上n个城市的旅行商问题（Traveling Salesman Problem，TSP）为例说明 在网络方面的主要应用 (1) 网络路由问题：蚁群算法在动态组合优化问题研究中的应用主要集中在通讯网络方面.随着 Internet 上广泛的分布式多媒体应用对服务质量（Quality of Service，QoS）需求的增长，各种服务应用对网络所能提供的 QoS 提出了不同的要求，而路由是实现 QoS 的关键之一．将蚁群算法用于解决受限路由问题，目前可以解决包括带宽、延时、包丢失率和最小花费等约束条件在内的 QoS 组播路由问题，比现有的链路状态路由算法具有明显的优越性，应用蚁群算法求解更复杂的 QoS 问题还需要深入讨论． (2) 无线传感器网络路由协议问题：作为一种新的信息获取方式和处理模式，无线传感器网络(Wireless sensor network，WSN)目前已经成为国内外备受关注的研究热点．WSN 是由众多具有通信和计算能力的传感器节点，以多跳通信、自组织方式形成的网络．节点传感器电池供电，电源能量、通信能力计算能力都是有限的．WSN 路由协议研究中的一个重要问题是路由的选择要结合节点的能量信息，使得节点的能量消耗能够均衡，延长网络生命周期．蚁群优化算法求解模式将问题求解的快速性、全局优化特征以及高度的自组织性等特点合理结合，与无线传感网低能耗、自组织的大规模网络路由快速建立要求极其相似，有助于建立面向数据为中心的路由协议．目前，已有许多学者研究蚁群优化算法在 WSN 路由协议中的应用． 粒子群算法(PSO) 粒子群优化( Particle Swarm Optimization， PSO) 算法是另一种群智能算法。在粒子群算法中引用了鸟群的概念。PSO 也是一种基于群体的优化工具，同时也是一种基于迭代的优化工具。 PSO 算法原理 PSO 首先生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都是优化问题的一个可行解，并根据目标函数构造一个适应度函数（fitness function）。以该适应度函数作为评价标准。每个粒子在解空间中运动，该粒子运动的速度由个体的飞行经验和群体的飞行经验进行动态的调整，并经逐代搜索最后得到最优解。在每一代中，粒子将跟踪两个极值，一个是粒子本身迄今找到的

最优解,另一个是整个种群中迄今找到的最优解. PSO 算法流程 PSO 的算法流程如下： （1） 初始化一群随机粒子，包括粒子的随机位置和速度； （2） 计算每个粒子的适应度值； （3） 对于每个粒子，将其适应度值与其经历过的最优位置 Pbest进行比较，如较好，则将其作为当前的最优位置 Pbest； （4） 对于每个粒子，将其适应度值与全局所经历过的最优位置 gbest进行比较，如较好，则重新设置 gbest的索引号； （5） 根据 PSO 算法的两个计算公式变化粒子的速度和位置； （6） 如果得到的适应度值足够好或达到预设的最大迭代次数GAP，则返回第 2 步。 网络方面的主要应用：无线传感器网路，近年来，将群智能算法应用于无线传感器网络问题引起了众多研究者的关注．网络节点位置优化是无线传感网络研究的核心问题之一．由于无线传感网络中移动节点的位置优化可以抽象为以移动节点位置构成的非整数向量为输入参数，网络有效覆盖区域面积大小为优化目标的优化问题．对于此类问题，微粒群优化算法相比其它算法具有更高的收敛速度、更强的全局搜索能力此外，微粒群算法在无线传感器网络路由协议中的应用也表现出了良好的优化性能。 人工鱼群算法 人工鱼群算法是李小磊等在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法。与传统人工智能系统的自上而下的设计思路相比,该算法采用了自下而上的设计方法。所以,首先应着重构造鱼群自治体的模型,具体模型描述如下: (1) 觅食行为:平时我们会看到鱼在水中游来游去,这一般可视为一种随机移动。当鱼群发现食物时,会向着食物逐渐增多的方向快速游去。 (2) 聚群行为:鱼在游动过程中为了保证群体的生存和躲避危害而形成了一种生活习性——会自然地聚集成群。在这个群体中,每条鱼都需要遵循一些局部相互作用的规则: ①分隔规则:尽量避免与临近伙伴过于拥挤;