网络可靠性优化

网络可靠性优化方法总结概述：目前较流行的智能优化方法包括遗传算法以及群智能算法。这两种优化算法的共同特点就是模拟生物行为方式，进行全局随机搜索，在单目标或多目标问题中找到最优解。应用到网络中比如用于网络路由的自适应调整，解决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、锦标赛选择法为了能够清楚的理解蚂蚁系统的数学模型，仍以求解平面上n个城市的旅行商问题（TravelingSalesmanProblem，TSP）为例说明在网络方面的主要应用网络路由问题：蚁群算法在动态组合优化问题研究中的应用主要集中在通讯网络方面.随着Internet上广泛的分布式多媒体应用对服务质量（QualityofService，QoS）需求的增长，各种服务应用对网络所能提供的QoS提出了不同的要求，而路由是实现QoS的关键之一．将蚁群算法用于解决受限路由问题，目前可以解决包括带宽、延时、包丢失率和最小花费等约束条件在内的QoS组播路由问题，比现有的链路状态路由算法具有明显的优越性，应用蚁群算法求解更复杂的QoS问题还需要深入讨论．无线传感器网络路由协议问题：作为一种新的信息获取方式和处理模式，无线传感器网络(Wirelesssensornetwork，WSN)目前已经成为国内外备受关注的研究热点．WSN是由众多具有通信和计算能力的传感器节点，以多跳通信、自组织方式形成的网络．节点传感器电池供电，电源能量、通信能力计算能力都是有限的．WSN路由协议研究中的一个重要问题是路由的选择要结合节点的能量信息，使得节点的能量消耗能够均衡，延长网络生命周期．蚁群优化算法求解模式将问题求解的快速性、全局优化特征以及高度的自组织性等特点合理结合，与无线传感网低能耗、自组织的大规模网络路由快速建立要求极其相似，有助于建立面向数据为中心的路由协议．目前，已有许多学者研究蚁群优化算法在WSN路由协议中的应用．粒子群算法(PSO)粒子群优化(ParticleSwarmOptimization，PSO)算法是另一种群智能算法。在粒子群算法中引用了鸟群的概念。PSO也是一种基于群体的优化工具，同时也是一种基于迭代的优化工具。PSO算法原理PSO首先生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都是优化问题的一个可行解，并根据目标函数构造一个适应度函数（fitnessfunction）。以该适应度函数作为评价标准。每个粒子在解空间中运动，该粒子运动的速度由个体的飞行经验和群体的飞行经验进行动态的调整，并经逐代搜索最后得到最优解。在每一代中，粒子将跟踪两个极值，一个是粒子本身迄今找到的最优解,另一个是整个种群中迄今找到的最优解.PSO算法流程PSO的算法流程如下：（1）初始化一群随机粒子，包括粒子的随机位置和速度；（2）计算每个粒子的适应度值；（3）对于每个粒子，将其适应度值与其经历过的最优位置Pbest进行比较，如较好，则将其作为当前的最优位置Pbest；（4）对于每个粒子，将其适应度值与全局所经历过的最优位置gbest进行比较，如较好，则重新设置gbest的索引号；（5）根据PSO算法的两个计算公式变化粒子的速度和位置；（6）如果得到的适应度值足够好或达到预设的最大迭代次数GAP，则返回第2步。网络方面的主要应用：无线传感器网路，近年来，将群智能算法应用于无线传感器网络问题引起了众多研究者的关注．网络节点位置优化是无线传感网络研究的核心问题之一．由于无线传感网络中移动节点的位置优化可以抽象为以移动节点位置构成的非整数向量为输入参数，网络有效覆盖区域面积大小为优化目标的优化问题．对于此类问题，微粒群优化算法相比其它算法具有更高的收敛速度、更强的全局搜索能力此外，微粒群算法在无线传感器网络路由协议中的应用也表现出了良好的优化性能。人工鱼群算法人工鱼群算法是李小磊等在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法。与传统人工智能系统的自上而下的设计思路相比,该算法采用了自下而上的设计方法。所以,首先应着重构造鱼群自治体的模型,具体模型描述如下:(1)觅食行为:平时我们会看到鱼在水中游来游去,这一般可视为一种随机移动。当鱼群发现食物时,会向着食物逐渐增多的方向快速游去。(2)聚群行为:鱼在游动过程中为了保证群体的生存和躲避危害而形成了一种生活习性——会自然地聚集成群。在这个群体中,每条鱼都需要遵循一些局部相互作用的规则:①分隔规则:尽量避免与临近伙伴过于拥挤;②内聚规则:尽量朝临近伙伴的中心移动;③对准规则:尽量与临近伙伴的平均方向一致。(3)追尾行为:在鱼群的游动过程中,当其中一条或几条食物时,其临近的伙伴会尾随其后快速到达食物点。(4)约束行为:在寻优过程中,由于群聚行为、随机行为等操作的作用,容易使人工鱼的状态变得不可行,此时就需要加入相应的约束对其进行归整化,使它们由无效状态或不可行状态转变为可行的。(5)公告板:公告板用来记录最优人工鱼的状态。各人工鱼在寻优过程中,每次行动完毕就比较自身状态与公告板的状态,若自身状态优于公告板状态,就将公告板状态改写为自身状态,这样公告板记录下的