混合蛙跳算法应用研究（共6篇）
混合蛙跳算法应用研究 篇1
著名的旅行商 (TSP) 问题[1]是一个典型的组合优化问题, 通常用来测试元启发式算法的效率。两位研究员Muzaffar Eusuff和Kevin Lansey通过观察, 模仿和模拟青蛙在池塘中的离散的石头上的觅食行为, 于2003年提出了一种新的元启发式算法—混合蛙跳算法 (Shuffled Frog Leaping Algorithm, SFLA) [2]。混合蛙跳算法使用模因内青蛙个体的交换以及整个蛙群的全局信息交流来对问题进行优化, 它结合了基于基因的模因算法以及基于社会行为的粒子群算法的优点, 概念简单, 参数少, 具有强大的全局搜索能力以及易于实现。尽管混合蛙跳算法的提出主要是为了解决多目标工程问题, 比如水资源的分布[3], 桥面维修[4]和车间作业调度安排[5], 而通过研究混合蛙跳算法在TSP中的应用, 能够促进其在进化机制理论方面的研究, 从而有助于混合蛙跳算法在多目标优化问题的广泛使用。
1 混合蛙跳算法的数学模型
混合蛙跳算法中每一个青蛙个体的数据结构是相同的, 但拥有不同的适应性。每个青蛙表示对优化问题的一个可行的解决方案。整个青蛙族群根据特定的规则, 被划分为一定数量的青蛙模因组, 每一个模因组代表了一种类型的模因。模因组中的青蛙根据特定规则在解空间中进行局部搜索。
假设初始蛙群由F随机生成青蛙U (i) , i=1, 2, …, F, 第i个青蛙的是印度可以进行评估, 并把模因组中的青蛙进行降序排列。由图1所示, 整个蛙群的F只青蛙被划分为m个模因组, 每一个模因组有n只青蛙, 而且满足F=mn。
为了避免混合蛙跳算法陷入局部最优解, 算法根据每个青蛙个体的适应度, 将整个蛙群分成m个模因组。青蛙个体的适应度越高, 就越容易被选中。假设PX是全局最优解;对于每一个模因组, PB和PW分别代表该模因组内最优解和最差解。混合蛙跳算法的局部搜索过程在每一个模因组中中展开, 比如, 每一个模因组中的最差青蛙个体根据如下公式来进行更新:
其中:S代表混合蛙跳算法的更新步长, q
模因组中的青蛙个体进行更新后, 如果的解U (q) 要优于模因组中原先的最差解PW, 就用U (q) 来替代PW;否则, 就用PX来替代PB, 来重复的执行式 (1) 和式 (2) 所表述的更新策略;如果结果仍然没有改进, 就随机产生一个可行解来替代PW。每个模因组独立进行演化, 直到达到指定的迭代次数。之后, 所有的青蛙开始进行全局信息交换。就这样, 算法的局部搜索过程和全局信息交换交叉进行, 直到达到预定的收敛条件。
2 混合蛙跳算法求解TSP问题
TSP是启发式算法的测试基准, 试图找到NP难组合优化问题的近似最优解决方案。本文将混合蛙跳算法应用到TSP问题当中。
2.1 初始蛙群的位置
每一个青蛙个体的位置向量都代表一个TSP问题的可行解。第i个青蛙由U (i) = (ei1, ei2, …eiN) , 其中ei1, ei2, …eiN分别代表N个城市的序列, 表明了青蛙在ei1出发, 经过城市序列ei2, …eiN, 最终返回到城市ei1。适应度函数f (i) 被定义为每一个青蛙个体所找到的路径长度的倒数。
2.2 模因组的建立
模因组选择青蛙的个体的概率取决于该青蛙个体相对应的适应度, 因此, 青蛙个体的适应度越好, 就越容易被模因组选择。本文构建的模因组选择青蛙个体的概率为:
其中Pj表示第j只青蛙被模因组选中的概率, n表示模因组中青蛙的个数。由于模因组中的青蛙通常按照适应度的值递减排列, 所以式 (3) 表示的选择概率会随着青蛙个体适应度的递减而减小, 这与之前的假设是一致的。
2.3 更新最差青蛙个体
在每一个模因组内最差青蛙个体根据如下规则进行更新:对于模因组中的第q只青蛙U (q) , 随机选择PB中的一段子序列来替换PW中对应位置的城市序列, 并保持PW中其它位置的城市序列没有改变;如果得到的城市序列与TSP规则相冲突, 就随机调整该解中其它元素的位置, 从而生成新的可行解。该更新思想如图2所示。
如果U (q) 的适应度的至要优于PW适应度的值, 那么就用U (q) 来替代PW;否则, 就用全局最优解PX来替代PB, 并重新执行以上操作直到产生一个新的可行解U (q) 。
如果U (q) 的适应度的值优于PW适应度的值, 用新的U (q) 来替换PW, 否则就随机产生一个可行解来替代PW。
2.4 参数设置的分析
混合蛙跳算法中的参数包括青蛙种群的数量F, 模因组的数量m, 模因组中青蛙的个数q, 以及局部搜索过程的迭代次数。模因组中的青蛙个数q的设置, 应该使得局部搜索的效率得到提高。q的值如果设置偏大, 就能够使得模因间的交流要用到更多的时间;q的值如果较小, 就表明模因组中的局部搜索时间较少。我们一般依据问题的规模来设置q的值。
模因组中青蛙个数n以及模因数量m满足如下约束F=mn。这就表示m的值越大, 模因组之间的全局交换能力就越强, 但算法需要更多的时间。参数n的作用是提高模因中解的多样性, 但是如果n的值偏大, 就会增大局部搜索的时间。
2.5 混合蛙跳算法求解TSP的执行步骤
(1) 初始化参数F, m, q等。
(2) 生成F个初始蛙群。
(3) 计算每只青蛙适应度的值。
(4) 构建m个模因组, 并进行局部搜索。
(5) 局部搜索之后, 进行全局搜索。
(6) 如果收敛条件满足, 输出最优解。否则, 转到步骤 (4) 。
混合蛙跳算法的流程图如下所示:
3 实验仿真
为了验证混合蛙跳算法的有效性, 本文选取TSP算例对算法进行验证, 并将计算结果与文献[6]提出的基于分段混合蛙跳算法 (S-SFLA) 进行对比。设需要遍历的城市数为N, 青蛙族群数目m=N, 每个模因组青蛙个数n=N/3, 模因组内局部搜索次数为k=n, 全局迭代次数为1500。实验结果如下:
从实验结果可以看出, 笔者设计的求解混合蛙跳算法在所有TSP算例上均能找到最优解, 而且最差解的质量比文献[6]提出的算法效果要好。
4 结束语
笔者将混合蛙跳算法应用到TSP问题中, 首先确定了初始蛙群的位置, 其次设计了模因选择概率来构建模因组, 并对每个模因组内的最差青蛙个体进行了更新, 最后对混合蛙跳算法的参数设置进行了分析, 实验结果证明了算法的有效性。
参考文献
[1]王剑文, 戴光明, 谢柏桥, 等.求解TSP问题算法综述[J].计算机工程与科学, 2008, 30 (2) :72-74.
[2]崔文华, 刘晓冰, 王伟, 等.混合蛙跳算法研究综述[J].控制与决策, 2012, 27 (4) :481-493.
[3]Muzaffar Eusuff, Kevin Lansey.Optimization of water distribution network design using the Shuffled Frog Leaping Algorithm[J].J Water Resour Plan Manage, 2003, 129 (3) :10-25.
[4]Hatem Elbehairy, Emad Elbeltagi, Tarek Hegazy.Comparison of Two Evolutionary Algorithms for Optimization of Bridge Deck Repairs[J].Computer-Aided Civil and Infrastructure Engineering, 2006, 2006 (21) :561-572.
[5]Alreza Rahimi-Vahed, Ali Hossein Mizaei.Solving a bi-criteria permutation flow-shop problem using shuffled frog leaping algorithm[C].Soft Computing, Springer Verlag, 2007.
[6]郭小燕, 王联国, 代永强.基于分段混合蛙跳算法的旅行商问题求解[J].计算机工程, 2014, 40 (1) :191-194.
混合蛙跳算法应用研究 篇2
超声速平头圆柱绕流DSMC/EPSM混合算法研究
本文将EPSM算法与DSMC方法结合,构造了可模拟含近连续流区及过渡流区的DSMC/EPSM混合算法.运用混合算法模拟马赫数等于5.37时超声速平头圆柱绕流,并与DSMC结果进行比较,证明了DSMC/EPSM混合算法的有效性,并对两种算法的计算效率进行了比较.
作 者：吴明巧 陈伟芳 任兵 作者单位：国防科技大学航天与材料工程学院,湖南长沙,410073 刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA 年，卷(期)： 20(2) 分类号：V211.25 V211.3 关键词：DSMC/EPSM混合算法 平头圆柱 稀薄气体流动 DSMC混合蛙跳算法应用研究 篇3
1 量子混合蛙跳算法在过程神经网络优化中的应用
1.1 个体编码方案设计
|0〉和|1〉是微观粒子基本状态在量子计算中的表现形式, 用其线性组合|φ〉=α|0〉+β|1〉可表示单量子比特的所有状态, 但其应符合|α|2+|β|2=1的要求。因此, 可按照叠加理论, 将量子比特的全部状态均表示为:
可见, 量子比特是由θ及φ两个变量所刻画的矢量空间, 并可利用Bloch球面进行直观的描述。设种群为m, 优化空间为n维, 采用Bloch球面坐标编码, 可将第i个待优化的个体编码为:
1.2 QSFLA的种群评估
1.2.1 个体解空间变换
QSFLA中的每只青蛙都有三组Bloch坐标, x=cosφsinθ, y=sinφsinθ, z=cosθ, 各自都表示一个优化解。考虑到x、y、z都∈[-1, 1], 需对其进行解空间变换。设待优化问题的第j维变量∈[Min (j) , Max (j) ], 可将解空间变化表示如下:
1.2.2 QSFLA的种族评估
依次将青蛙个体各自对应的解代入到适应度函数, 对其适应度进行计算。确保整个种群中最优青蛙所对应的幅角为θg和φg, 而子种群中的最优青蛙相对应的幅角则为θb和φb, 子种群中的最差青蛙相对应的幅值为θw和φw。
1.3 QSFLA的种群进化
1.3.1 QSFLA个体更新
针对子种群中最差的青蛙量子位幅角增量的更新:
在此借助量子旋转门改变量子比特的相位:
基于量子旋转门的量子位概率幅更新:
对上式进行分析, Δθ和Δφ两转角的大小和符号分别决定着收敛速度和方向, 因此极为关键。为不影响算法效率, 可将其看做是Block球面的旋转, 即量子比特在上面绕着某一固定轴进行旋转。通过旋转可使两个参数同时改变, 以提升优化能力。
1.3.2 自适应混沌旋转角度算子
混沌优化方法适用于小空间搜索, 在较大空间中搜索效果较弱, 与蛙跳算法子群内部的全局遍历十分适应。其公式如下:
上式中, 结合旋转角度和进化代数进行适应调整, 在进化初期, 便可实现算法较大幅角的搜索工作。进化代数不断增加, 幅角随之减小, 为进化后期的精细搜索提供了便利。Lj+1=μLj (1-Lj) , μ=4是一个Logistic混沌序列, 可让旋转操作在解空间内进行遍历, 对提高搜索效率较为有利。为提高收敛速度, 用δmin和δmax分别表示允许旋转角的最小及最大值。通过自适应调整, 使得局部优化的遍历性有所增强, 且不需要将量子门转角的方向与当前最优个体对比, 有利于促进种群的进一步优化。
2 量子混合蛙跳算法的改进
在混合蛙跳算法分组中, 若采用标准的分法, 适应值较差的青蛙常分在最后一组, 则其向最好青蛙学习的效果较弱。为此, 提出一种新方法:初始种群P, 先按照标准分组的方式将种群分为m个子群, 均包含有n只青蛙;然后从其他组随机选择一只与该组中的最优青蛙进行对比更新, 得到一个新青蛙, 使得每组扩大到n+ (m-1) 个青蛙, 使得分组更为多样;当每组进化迭代完成后, 再将各组进行重新合并, 形成一个新种群, 对其中青蛙的适应值进行计算闭关重新排序, 取前P个进入下一轮迭代。
3 结束语
混合蛙跳算法综述 篇4
最优化问题[1]存在于人类日常生活中的方方面面,人类从事任何活动的实质归结为认识世界和建设世界,认识世界就是为了更好地建设世界,然而建设世界的本质就是依靠优化决策。最优化问题是一个古老的课题,早在在古代战国时期,就有了孙膑为田忌赛马献策赢了齐威王这一经典事件[2];在第二次世界大战期间,英国成立了专门的作战研究小组,目的是为了最有效地利用有限的战备资源去赢取最大的胜利[1]等。随着科学技术日新月异的发展和应用领域的不断扩展,常规的优化方法[2,3,4](例如牛顿法,拉格朗日乘数法,共轭梯度法等)已经无法满足越来越复杂的优化问题的求解需要,因此寻找更为有效的优化方法显得越来越重要。
一些学者提出模拟自然界生态系统机制的新型智能优化算法,并用来解决复杂优化问题,取得了一定的效果。群体智能优化算法正是基于此基础上产生的。群体智能优化算法[5,6]自20世纪90年代提出以来受到广泛的关注,通过对自然界中社会性生物的群体行为进行模拟和建模,研究其内在的原理,并以此为基础解决许多工程应用,科学计算,社会经济等领域的实际问题。由于其求解能力强,计算结构简单,吸引了众多演化计算领域专家的注意,形成了许多新的研究热点并取得显著的成就。目前群体智能优化算法广泛应用于农业、通讯、交通、金融、材料、化工、能源及国防等领域中。
混合蛙跳算法[5,6,7](Shuffled frog leaping algorithm,SFLA)是近几年兴起的一种新型的后启发式群体智能优化算法,它继承其他优化算法的优点同时,还具有寻优能力更强,参数更少的优点,目前已广泛应用于模式识别[8],函数的优化[9,10,11,12],信号与信息处理[13,14]等领域中并取得了成功。由于混合蛙跳算法提出的时间不长,无论在理论研究还是实践应用方面都处于起步阶段。
1 混合蛙跳算法
1.1 SFLA算法的数学模型
混合蛙跳算法是2003年由Eusuff和Lansey提出的一种新的群体智能优化算法,它概念简单,参数少,计算速度快,全局寻优能力强。
在一个D维的目标搜索空间中,随机生成P只青蛙(解)组成初始群体,第i只青蛙表示问题的解为Xi=(xi1,xi2,…,xiD)。青蛙个体按适应度值从优到劣排列,将整个群体分为M个子群体。其中排名第1的青蛙分入第1子群体,排名第2的青蛙分入第2子群体,第M只青蛙分入第M子群体,第M+1只青蛙分入第1子群体,第M+2只青蛙分入第2子群体,依次类推,直到全部青蛙划分完毕。
每个子群体进行局部深度搜索,即在子群体的每次迭代中,首先确定当前迭代中子群体的最差个体Xw、最好个体Xb和全局最好个体Xg;只对该子群体中当前的最差个体Xw进行更新操作,更新策略如下。
蛙跳步长更新公式
青蛙个体的位置更新公式
其中,Ωi表示青蛙个体的更新步长,i=1,2,…,N;rand()为均匀分布在[0,1]之间的随机数;||Ωmax||表示所允许更新的最大蛙跳步长;||Ωmin||表示所允许更新的最小蛙跳步长。执行更新策略(1)(2)。如果newXw的适应度值优于原来Xw的适应度值,则用更新后的个体的位置(解)取代原来群体中的当前最差个体的位置(解)。如果没有改进,则更新策略变为如下过程。
蛙跳步长更新公式:
青蛙个体的位置更新公式:
执行更新策略(3)(4)。如果newXw的适应度值仍然没有改进,则随机产生一个新的Xw。
当所有子群体的局部深度搜索完成以后,将所有的青蛙个体重新混合排序并再次划分子群体,然后再进行局部深度搜索,如此反复直到满足混合迭代次数。
1.2 SFLA算法的实现流程
第1步:随机初始化青蛙种群,设置SFLA算法中的参数:种群中的青蛙个体总数N,青蛙个体(解)的维数d,每个子群体中的个体数m,子群体的个数n,子群体内的局部迭代次数cyc,全局混合迭代次数cyc,允许更新的最大蛙跳步长Ωmax和最小蛙跳步长Ωmin。
第2步:计算每只青蛙个体的适应度值。
第3步:将当前所有的N只青蛙个体按照适应度值从优到劣进行排序。
第4步:将每只青蛙个体依次划分到各个子群体中,共划分为n个子群体。
第5步:对每一个子群体,重复执行以下步骤cyc次:
(1)根据适应度值更新当前迭代中子群体的最好个体的位置Xb和全局最好个体的位置Xg,并确定当前迭代中子群体的最差个体的位置Xw;
(2)按照1.1节中所描述的更新策略对Xw进行更新。
第6步:当所有子群体都完成了局部深度搜索后,若满足全局混合迭代次数cyc,进化过程结束,输出全局最优值;否则,将全部的青蛙个体重新混合,转至第3步重新计算。
以上算法实现流程如图1所示。
2 混合蛙跳算法的研究现状
2003年,Eusuff和Lansey首次提出混合蛙跳算法,由于其结构简单、参数少、运行速度快、易于实现的优点,得到了国内外学者的广泛关注。然而混合蛙跳算法存在算法迭代后期容易陷入局部极值点,出现早熟收敛现象,同时收敛速度变慢,寻优时间变长,无法搜索到精度更高的最优点等缺陷。因此,目前对混合蛙跳算法的研究主要集中在算法改进和算法应用方面。
混合蛙跳算法由于提出的时间不长,无论在理论研究还是实践应用方面都处于起步阶段。群体智能优化算法不是一门理论严谨的学科,主要是以实验为主,因此关于算法的理论研究主要集中在算法收敛性证明上。骆剑平等人[15]通过求解差分方程分析了混合蛙跳算法的运动轨迹并证明了算法的全局收敛性;Elbeltagi等人[16]对比研究了遗传算法、粒子群优化算法、蚁群算法和混合蛙跳算法的数学模型和优化性能;
目前,针对混合蛙跳算法存在的缺陷,为了提高算法的优化性能,国内外学者从各个方面对算法提出了改进。罗雪晖等人[17]将调整序思想引入到混合蛙跳算法的局部搜索阶段,将变异操作引入到全局信息交换阶段,从而提出一种改进的混合蛙跳算法并将其应用于求解旅行商问题(Travelling salesman problem,TSP),实验结果表明该算法在求解旅行商问题上具有更好的搜索性能和顽健性;骆剑平等人[15]把具有极强局部搜索能力的幂律极值动力学优化融合在混合蛙跳算法中,从而拓展了算法的搜索精度和空间;郑仕链等人[18]提出新的蛙跳移动步长公式,每次蛙跳移动步长中引入上一次的移动距离,包含了对过去经验的记忆,因此具有更强的寻优能力;Alireza等人[7]提出一种混合多目标蛙跳算法,并将其应用于流水线平衡装配线排序问题中;Elbeltagi等人[19]提出一种新的参数用来加速算法的搜索范围,并分析了该参数对算法优化性能的影响,最后将所提算法用来求解离散和连续两类问题,结果表明改进算法十分有效并且可行;文献[9]通过适当地延长蛙跳步长并且加入惯性部分,提出一种改进的蛙跳步长更新公式,同时为了进一步改进混合蛙跳算法的局部深度搜索能力和加速收敛,将进化算法引入到混合蛙跳算法的局部深度搜索阶段,从而提出一种改进的混合蛙跳算法;文献[20]将模拟退火算法和混合蛙跳算法相结合,从而改进了算法迭代后期陷入局部极值的缺点,并将其应用于求解最优潮流问题(Optimal power flow,OPF);文献[21]提出一种求解多目标柔性作业车间调度问题的改进混合蛙跳算法,该算法通过几种策略来构成初始种群,并依据一种新的准则来划分子群体,同时在全局信息交换阶段引入两种变异因子,在局部深度搜索阶段嵌入一些不同的局部搜索方法,从而提高算法的求解性能。
与其他群体智能优化算法一样,混合蛙跳算法由于其独特的优势被广泛应用于实际优化问题中。例如,旅行商问题[22]、电力系统优化[23]、作业车间调度问题[24,25]、函数优化[10,11,12]、财务调度问题[26]、水资源分配[27]、图像处理[13]、背包问题[28]、聚类问题[29]等方面,文献[30]提出一种多目标优化的改进混合蛙跳算法,并用来求解配电馈线重组问题;文献[31]中将一种改进的混合蛙跳算法应用于工业CSTR反应器的醋酸乙烯聚合中;文献[32]中将混合蛙跳算法应用求解离散优化问题中。
3 结束语
混合蛙跳算法在提出的短短几年时间里得到了国内外学者的广泛关注,成为人工智能领域中的研究热点。虽然混合蛙跳算法被成功用于求解实际优化问题,但是由于其提出的时间不长,无论是在理论研究还是实际应用都处于起步阶段。目前关于混合蛙跳算法并没有一套完整的理论体系,未来的工作应当注重算法收敛速度证明并总结出一套完整的理论模型;由于现实生活中需要解决的优化问题各式各样,如何突破原有混合蛙跳算法模型的束缚,设计出更为有效的群体智能优化算法将在未来工作中继续研究。
混合蛙跳算法应用研究 篇5
无线传感器网络WSN由一组传感器节点以自组织方式构成。每个节点兼备路由器和主机两种功能,不仅要执行感知、传输数据等应用任务,还要参与路由发现、维护以及网络构建等任务。WSN中节点一般采用电池供电,节点大部分情况下被布置在无人看守的环境中,电池不能补充和更换,节点能量受限。在这种情况下要延长网络生存时间就必须降低节点工作时能量消耗,试验表明节点能量主要消耗在通信模块上。无线通信中的传输数据的能量消耗与有效半径的2-4次方相关,减小节点的有效传输半径可以降低节点能量消耗。
另外WSN还有着不同于传统无线网络的其他特征:首先WSN中节点数量庞大,传统的以IP地址为基础的路由协议不适合WSN;其次WSN的应用背景主要是多个源节点感知数据,然后将感知数据传给目的节点Sink,不要求建立网络中任意两点之间的路由路径,这给设计高效的路由协议带来了可能性。因此采用合适的、高效的路由协议是降低无线传感器网络整体能耗的关键。这就需要我们设计一个满足需要的高效的路由协议。
1 相关工作
研究工作者们提出了许多的路由算法,比如SPIN[1](基于协商的路由算法)、DD[2](定向扩散协议)、LEACH[3]、TTDD[4](基于虚拟网格的路由协议)、LAR[5](位置辅助路由协议)等路由协议。他们都很好地解决了无线传感器网络的某方面的问题,但也都存在各自的问题。比如SPIN协议中出现了多个节点向同一个节点同时发送REQ的情况,有关的退避机制需要考虑。DD算法不能用于大规模的网络,主要用于具有大量查询而只有少量事件的应用场景,如果网络拓扑结构频繁变动,它的性能将大幅下降。
在WSN中,从源节点到基站或是到基站的某条传输路径一旦确定,就不会频繁改动,这样就会出现由于路径上的传输节点的失效或暂时不可用导致数据包传输失败,为此需要重新更新路由,增大了能耗和传输延迟。为了解决这个问题,研究工作者们提出了多路径路由[6,7]的概念。多路径路由协议通过将数据流分散到多个不同的路径上传送以实现负载的均衡性,在WSN中体现为能量的均衡性,并且可以通过增加冗余路径来提高网络的可靠性。优化增加了网络的可靠性,但同时也增加了网络能耗。
混合蛙跳算法[8]可以实现路由优化的目的,但是传统的混合蛙跳算法不能将可行解中的优良性能很好地保留在青蛙群体中,它的收敛速度也比较慢,这就表明了传统的混合蛙跳算法不适用于能量有限的无线传感器网络中。
针对以上问题,我们提出了一种改进的混合蛙跳算法来全局优化多路径路由。考虑到混合蛙跳算法的计算量大,所需要的资源信息较多,我们将混合蛙跳算法的执行在基站完成。这样就解决了由于建立多路径导致的网络能量浪费,又实现了多路径路由的优点,实现了WSN多路径路由的全局优化。
2 WSN路由优化算法
混合蛙跳算法是一种基于群体智能的生物进化算法。在WSN中,青蛙群体由一群具有相同结构的青蛙组成。整个群体被分为多个族群,每个族群有自己的思想,执行局部优化策略。在局部优化迭代结束后,各个族群之间进行思想交流,实现族群间的混合运算。达到了路由优化的目的。
2.1 网络模型
WSN网络模型假设如下:
1) 所有节点随机均匀地分布在一矩形区域内。且位置已知。
2) 所有节点与基站均保持静止,节点初始能量相同,并无法补充能量。基站的能量无限大。
3) 所有节点均同构,且唯一ID,并具有数据融合功能。
4) 每个节点的传输功率相同,有效通信距离均一样。
将无线传感器网络模型表示为一个有向图G=(V,E),其中V表示所有节点的集合,E表示所有边的集合。令r为节点v∈V的发射范围,L表示相邻节点间的距离。随机生成F只青蛙组成初始群体,每个青蛙个体表示一条源节点到基点的可行路径为U = (U1,U2 ,…,Ud),其中d表示解空间的维数。例如5个传感器节点组成的网络链路如图1所示。
随机生成的初始群体:
U1={S,1,2,BS} U2={S,1,3,2,BS}
U3={S,1,2,4,BS} U4={S,3,2,BS}
U5={S,1,2,3,4,BS} U6={S,4,BS}
U7={S,3,2,4,BS} U8={S,3,1,2,BS}
U9={S,3,4,BS} U10={S,4,3,2,BS}
2.2 算法描述
路由协议的好坏极大地影响整个网络的性能。好的路由协议不仅能够降低整个网络的能量消耗,延长网络生存周期,还能提高网络的稳定性。基于混合蛙跳算法的多路径路由的优化主要考虑了传输数据的能耗和可靠性两方面来全局优化多路径路由。以下为优化算法的具体步骤:
1) 初始化参数
在无线传感器网络中,按一定规则随机生成F只青蛙组成初始群体,计算青蛙个体的适应度f(i)。青蛙个体的适应度函数定义为:
其中D(u,x)表示源节点u在链路(u,x)上分配的数据流量,g(x,u)表示节点u在链路(x,u)上接收单位数据所消耗的能量,R(x,u)表示节点u在链路(x,u)上接收到的数据流量,t(u,x)表示节点u在链路(u,x)上发送单位数据所消耗的能量,W(u)表示感知的数据量。
2) 构造子族群
将生成的青蛙按适应度降序排列划分成m个族群,构造子族群。在随机生成初始群体之后,将青蛙个体按适应度f(i)降序排列存储于X={Ui},i=1,2,…,F,然后按照以下划分原则将整个青蛙群体分成m个族群Y1,Y2,…,Ym,每个族群中包含n只青蛙,满足下列关系:
Yij=X[j+(i-1)×n] i=1,2,…,m j=1,2,…,n
假设m=3,F只青蛙按适应度由高到低排列,位置位于第1 的青蛙分入第1 族群,第2 的青蛙分入第2 族群,第3 的青蛙分入第3 族群,第4的青蛙分入第1 族群,依次类推,将所有青蛙个体划分到3 个族群中。
3) 局部优化
将青蛙种群划分的多个族群进行局部优化。在每一个子族群中,具有最好适应度的可行路径表示为Ub,最差适应度的可行路径表示为Uw 。对每个子族群的局部优化,主要是对Ub和Uw进行交叉替换操作。具体的操作可如下进行:
(1) 在Ub和Uw中查找它们的公共基因,即查看两条路径是否同时经过某个节点,如果存在公共基因表明可以进行交叉。如果没有,则表明这两个个体不能交叉。
(2) 从选中的这个公共基因开始,直到下一个公共基因 (如果两条路径仅有一个相同节点,则取目的节点为下一个公共节点) ,对Uw进行链路交换。
例如: Ub={S,1,3,4, BS}
Uw={S,1,2,4,BS}
节点1、节点4为公共节点,经过交叉后,Ub不变。Uw变为:
Uw={S,1,3,4,BS}
计算交叉后的最差青蛙的适应度f′(w),如果f′(w)大于交叉前最差青蛙的适应度f(w),则交叉成功,否则交叉失败。如果交叉失败,再选用全局最优青蛙与最差青蛙进行交叉替换。交叉后判断交叉前后的最差青蛙的适应度,如果f′(w)大于f(w),则交叉完成,否则随机产生一个新的青蛙代替原来的最差的青蛙,交叉结束。
(3) 交叉后再对子族群中的所有的青蛙进行变异。每一个青蛙都以固定的概率p进行变异,大量实验表明p的值取0.02比较理想。子族群中的最优青蛙Ub也可能变异,为了防止变异后的Ub变得比原来的适应度差,如果变异后的Ub的适应度f′(b)大于变异前的适应度f(b),则发生变异,否则不进行变异。
4) 全局优化
所有子族群经过一定次数的局部优化后,将所有族群的青蛙混合在一起,重新计算适应度f(i),按适应度f(i)降序排列,重新划分族群,再进行局部优化,如此循环直到满足收敛条件为止。
2.3 算法分析
随机生成青蛙种群的时候,在可行路径中的节点的选择时,加入了节点的剩余能量的考虑。剩余能量越大的节点被选中的概率越大。概率q=E1/E2,E1表示节点的剩余能量,E2表示节点的初始能量。剩余能量的考虑缓解了部分节点因大量使用而死亡的问题。
改进的混合蛙跳算法改进了子族群青蛙局部优化方法,主要是对子族群中青蛙进行交叉变异操作,对子族群中最优青蛙和最差青蛙的交叉操作,考虑了多种情况,避免了局部早熟。随后进行概率变异操作,变异中如果最优的青蛙如果发生变异,要进行比对。这样不仅保证了青蛙个体的多样性,而且保留了青蛙的优良性,缩短了找到全局最优解的时间。
在每次的优化后保存最优的青蛙和次优的青蛙。采用这样的多路径路由可获得比单路路由更好的网络吞吐率和可伸缩性。如果最优路径中的某一个或几个节点的剩余能量很低,并且下一轮的路由更新还没开始,最优路径就不能传输数据。多路径路由就可以只使用次优的路径进行传输,保证了网络的流通,增加了网络的可靠性。
3 算法实现和实验仿真
3.1 算法流程
1) 基站收集网络初始信息。得到网络各个节点的邻居矩阵N和感知数据集合{W(u)|u∈V}。
2) 对网络节点ID编码并初始化青蛙群体。
3) 依据青蛙适应度划分生成青蛙种群。
4) 针对子族群中最优青蛙和最差青蛙进行选择替换操作,然后子群青蛙按概率0.02进行变异。
5) 混合子族群,再重复3)、4)操作;直到满足收敛条件为止。
6) 输出青蛙种群中适应度最优和次优的青蛙作为问题的满意解。
3.2 实验仿真
在下面的实验中,通过仿真网络中节点的通信和节点的能量消耗,主要从网络能量消耗方面进行了实验分析。
基本参数设定
网络的负荷根据控制系统的一般要求设置为:周期性发送和感知数据,各节点的发送数据周期为0.01 s～0.10 s,感知数据周期为0.1 s～0.5 s。青蛙更新迭代次数IT=10。定义网络生存周期为网络从运行开始到网络中死亡节点的百分数低于原来总节点数的50%时所持续的时间。
选择经典的传感网络路由算法定向扩散(DD) 算法作为比较对象。在同一环境下分别对混合蛙跳算法和DD算法的网络生存周期进行仿真测试。仿真结果如图2所示。
从图2中可以看出,采用改进的混合蛙跳算法的WSN路由优化算法具有更长的网络生存周期,并且随着感知数据量的增大,网络生存周期延长的效果越明显。说明混合蛙跳算法对于大数据量的全局优化更加突出。
4 结 语
本文在分析了现有的混合蛙跳算法的基础上,结合无线传感器网络的特点,提出了一种适合于无线传感器网络的路由优化算法。改进的混合蛙跳路由优化算法考虑到了节点的剩余能量,并且复杂的优化计算问题由能源充足、计算和存储能力强大的基站解决,平衡了节点能量负载,节省了能量消耗。仿真实验表明,相比DD算法,新算法均衡了网络能量消耗,有效地提高了网络生存周期,改善了网络性能。
参考文献
[1]WHeinzelman,J Kulik,HBalakrishnan.Adaptive Protocols for Infor-mation Dissemination in Wireless Sensor Networks[C]//Proc.5thACM/IEEE Mobicom,Seattle,WA,Aug 1999:174-85.
[2]C Intanagonwiwat,R Govindan,D Estrin.Directed Diffusion:a Scala-ble and Robust Communication Paradigm for Sensor Networks[C]//Proc.ACMMobi-Com2000,Boston,MA,2000:56-57.
[3]Heinzelman W,Chandrakasan A,Balakrishman H.Energy efficientcommunication protocol for wireless microsensor networks[C]//Proc ofthe 33rd Hawaii International Conference on Systern Sciences.Maui:IEEE Computer.
[4]HLuo,Fan YE,J Cheng,et al.TTDD:A Two-tier Data DisseminationModel for Largescale Wireless Sensor Networks[J].Wireless Net-works,2005,11(2):161-175.
[5]Young-Bae Ko,Nitin H Vaidya.Location-Aided Routing(LAR)inmobile ad hoc networks[J].ACM/Baltzer Wireless Networks(WI-NET)Journal,2000,6(4):307-321.
[6]Lees J,Gerlam.Sp litmultipath routing with maximally disjoint paths inAd Hoc networks[EB/OL].[2008-06-18].http://www.hp l.hp.com/personal/Sung-Ju_Lee/abstracts/papers/icc2001b.pdf.
[7]周集良,李彩霞,曹奇英.基于遗传算法的WSNs多路径路由优化[J].计算机应用,2009(2):521-524.
混合蛙跳算法应用研究 篇6
关键词：舰船电力系统,网络重构,混合蛙跳算法,离散化
混合蛙跳算法[1,2]是2003年由Eusuff和Lansey提出的一种结合了模因算法 (Memetic Algorithm, MA) 和粒子群优化算法 (Particle Swarm Optimization, PSO) 的新式后启发群体智能优化算法, 它继承了其他优化算法的优点的同时, 还具有概念简单, 参数更少, 计算速度更快的优点。目前已初步应用于神经网络, 函数优化, 参数辨识等领域, 并已经获得了成功。舰船电力系统网络重构其实质就是构建一个在故障状态下进行调节、调度和控制的电力网络管理自动化系统, 来最大限度地减少各种故障给电力系统带来的影响, 增强系统的稳定运行能力及连续供电能力, 完成对电力系统影响最小的电力恢复。
本文根据舰船电力系统的特点、重构指标以及网络拓扑, 考虑到负荷优先级以及发动机容量和电流限制问题, 提出了基于混合蛙跳算法的舰船电力系统网络重构方法, 结合具体算例进行分析研究, 结果表明混合蛙跳算法具有较高的收敛速度和精度。
1 舰船电力系统网络重构
1.1 舰船电力系统结构图
大型舰船电力系统中发电机通过主配电板和联络线构成环形供电系统[3], 使用径向模式的载荷分布, 如图1所示, 包括4个电站、8台发电机, 通常由3个电站供电, 1个备用。主配电板直接联接有些重要负载, 其他的负载由区域配电板 (负载中心) 进行供电, 发电机和供电负载之间具有任意性。图1中, G为电站, C为区域配电板, L为载荷。为了确保一级负载的供电可靠性, 正常情况下选用两路供电, “—”代表正常的供电线路, “---”代表备用的供电线路。
1.2 目标函数
按照舰船负载的重要程度, 可分为3级, 其中, 1、2级负载为重要负载。舰船电力系统重构时与陆地配电网以网损或经济运行为目标函数不同, 舰船电力系统的故障恢复问题是一个多目标决策问题。在任何情况下, 必须要保证重要负载的供电, 同时使负载损失的总量达到最小。
因此, 综合考虑到开关的操作次数最少, 以及全部重要负载的恢复供电, 创建如下舰船电力系统网络重构模型[4]:
目标函数为:
式1) 中, i=1, 2, 3…, N1, j=1, 2, 3…, N2, k=1, 2, 3…, N3;分Lg1、Lg2、Lg3别为1、2、3级负载的个数, 负载总数NL=N1+N2+N3;λ1, λ2, λ3分别为1、2、3级负载的比例系数, μ为开关比例系数;xi, xj=1或0, 分别表示负载的供电和卸载;zr=0或1 (r=1, 2, …, M) , 分别表示在重构中开关保持不变或发生变化。
1.3 约束条件
式中, Ii为第i条线路的电流值, Imax为线路运行所允许的最大电流值;Pi为第i条线路的功率值, 、Pmin、Pmax分别为线路运行所允许的最大功率值和最小功率值。
2) 放射状条件约束。对每一个重要负荷, 在恢复供电时, 正常路径和备用路径有且仅有一条闭合, 即zia+aiβ=1 i=1, 2, …, Ω3)
式中, zia, aiβ=0或1, 分别表示为同一负载的正常、备用开关处于打开或闭合状态;Ω为转换开关的个数。
3) 优先性约束。优先运行重要负载, 然后再考虑级别低的负载。
2 混合蛙跳算法
2.1 混合蛙跳算法基本原理
混合蛙跳算法 (Shuffled frog leaping algorithm, SFLA) 是2003年由Eusuff和Lansey提出的新型进化算法, 它概念简单, 参数少, 收敛速度快, 全局寻优能力强。下面综合介绍下混合蛙跳算法:
设青蛙种群规模为U, 子群体个数为N, 每个子群体含有M只青蛙, 则U=M*N。第j个个体在D维目标搜索空间内的位置 (解) 为Xj=ΣXj1, Xj2, …, Xj DΣ, 计算出每个青蛙个体的适应度值, 从优到劣排列, 在迭代过程中, 将第一个青蛙放到第一个子群体, 第二个青蛙放到第二个子群体, 依次分配, 直到第N个青蛙放到第N个子群体, 然后, 第N+1个青蛙放到第1个子群体, 第N+2只青蛙分入第2个子群体, 依次循环下去, 直到所有青蛙分配完毕。
在子群体每次迭代后, 确定出适应度最差个体Xw= (Xw1, Xw2, …, Xw D) 和最优个体Xb=ΣXb1, Xb2, …, Xb DΣ, 比较各子群体, 确定全局最优个体Xg=ΣXg1, Xg2, …, Xg DΣ。每次进化后, 对最差个体进行更新操作, 方法如下:
蛙跳步长更新公式:
青蛙个体的位置更新公式:new Xw=Xw+Qj5)
其中, Qj表示青蛙个体更新的步长, j=1, 2, …, M;Rand () 是[0, 1]之间的随机数;‖Qmax‖表示所允许的最大蛙跳更新步长;‖Qmin‖表示所允许的最小蛙跳更新步长。使用公式4) 、5) 更新。如果new Xw的适应度值优于原来的适应度值, 则用new Xw的位置 (解) 代替原来Xw的位置 (解) 。如果没有改进, 则使用以下方法进行更新:
蛙跳步长更新公式
使用公式6) 7) 更新。如果new Xw的适应度值仍然没有改进, 则在解空间中随机生成一个解代替Xw。当所有的子群体实现了子群内的局部搜索后, 再次混合所有的青蛙, 依次排列划分出子群体进行迭代, 反复循环, 直到满足迭代次数。
2.2 适应度函数
适应度函数也称评价函数, 根据函数值可以判断生物个体是否有更多的能力来繁衍后代, 它是判断生物个体优劣的一个重要依据。因此, 适应度函数的选取直接关系到算法的性能。本文选用的适应度函数为:
上式中, 表达式参见式1) , Nc是发电机的数量;Nl是负载的数量, α1, α2表示惩罚系数;△P, △I表示如下:
其中, 式9) 为违反发电机功率约束的惩罚函数, 式10) 为违反发电机电流约束的惩罚函数。选取α1, α2=1.0e8。式9) 中的Plim表示发电机功率的极限值, 当发电机功率超过上限Pmax, Plim为上限值Pmax, 当发电机功率小于下限Pmin, Plim为下限值Pmin;式10) 中的Ilim与Plim类似。由本文所研究的重构问题是最小优化问题, 因此, 青蛙个体适应度值越小越好。
2.3 混合蛙跳算法的离散化求解过程
本文中混合蛙跳算法仅针对连续问题, 而舰船电力系统网络重构是个多目标、非线性、离散化问题。因此, 必须在SFLA产生初始种群后进行离散化处理。其方法是:将负荷进行二进制0、1、2编码[5], 其中, 0代表失电, 1代表正常线路供电, 2代表备用线路供电。在故障情况下, 有些负载会失去正常线路供电, 有些负载为了保证重要负载的恢复供电, 会改由备用线路供电, 则负载的供电情况有以下四种情况:
有正常有备用:[0, 0.5) →0, [0.5, 1.5]→1, (1.5, 2]→2
有正常无备用:[0, 0.25) →0, [0.5, 2]→1
无正常有备用:[0, 1) →0, [1, 2]→2
无正常无备用:[0, 2) →0
3 算例分析
以图1所示的舰船电力系统简化结构图为例, 各发电机的实际功率不得超过320k W, 各条线路的实际电流值不得超过420A, 故障前所有负荷均由正常供电线路供电。系统负荷数据及有关参数见表1[6]。
故障一:假设电力系统中, L5, L11失去正常供电。目标函数式1) 中的参数为:λ1=1, λ2=1, λ3=0.01。SFLA参数设置为:种群大小为600, 总进化代数为100。最佳方案如表2所示:L5、L11由备用路径恢复供电, L8改用备用路径恢复供电, L4卸载。开关操作次数是4次, 最佳收敛代数是3, 平均收敛代数是3.8。与单纯的遗传算法 (SGA) [6], 改进粒子群算法 (IPSO) [7]相比较, SGA卸载负载过多, 导致开关操作次数很大, 在有限的时间内, 优势很小;IPSO收敛很快, 但是还没有达到开关次数最小的效果;SFLA达到了开关次数最少, 收敛快的目的。
故障二:假设电力系统中, L3, L12, L13失去正常供电, L10失去备用, 设置与故障一相同。最佳方案如表3所示:L3、L13由备用路径恢复供电, L12卸载。与启发式遗传算法 (HGA) [8], 粒子群算法 (PSO) [5]相比较, SFLA的故障恢复方案明显优于GA、HGA算法所得到的结果, PSO方案已达到最优, 但是在相同的开关操作次数下, SFLA收敛更快。
通过两个算例可知, 应用混合蛙跳算法 (SFLA) 可以保证在最小的开关操作次数下恢复所有重要负载的供电, 且收敛速度快。可见, SFLA在求解离散化问题上具有较强的搜索能力。
4 结论
随着世界各国综合国力的提高, 军事力量的增强, 舰船的研究也越来越深入。依照舰船电力系统网络重构的特征, 建立了以快速恢复重要负载, 最大限度的确保重要负载的供电恢复和开关次数最小为目标的故障修复离散化模型, 应用混合蛙跳算法来进行故障恢复, 通过算例与其他方法分析比较, 证实了蛙跳算法在舰船重构问题上的适用性, 具有更强的稳定性, 收敛性。
参考文献
[1]Eusuff M M, Lansey K E.Shuffled frog-leaping algorithm:A memetic meta-heuristic for disvrete optimization[J].Engineering Optimization, 2006.
[2]J.A.Jordaan, R.Zivanovic, "Dynamic leapfrog algorithm for power system state estimation", IEE Proc.-Gener.Transm.Disirih.Vol.150, No.1, January 2003.
[3]兰海, 肖云云, 张利军等.多Agent的船舶电力系统网络重构技术[J].船舶与海洋工程学报, 2010.
[4]张毅, 杨秀霞.舰船电力系统网络重构研究综述[J].电工技术学报, 2005.
[5]王锡淮, 李军军, 肖健梅等.基于梯度DPSO算法在舰船电力系统网络重构[J].电工技术学报, 2007.
[6]杨秀霞, 张晓峰, 张毅, 陈迎春.基于启发式遗传算法舰船电力系统网络重构研究[J].中国电机工程学报, 2006.
[7]陈雁, 孙海顺, 文劲宇等.改进粒子群算法在船舶电力系统网络重构中的应用[J].电力自动化设备, 2011.