人工蜂群优化算法

人工蜂群优化算法（共7篇）

人工蜂群优化算法 篇1

0 引 言

人工蜂群算法(Artificial Bees Colony,简称ABC)是一种群体智能算法,于2005年被Karaboga[1]正式提出。与传统的智能算法,如差分进化算法(DE)[2]、遗传算法(GA)[3]、粒子群算法(PSO)[4]等相比,人工蜂群算法具有控制参数少、计算简洁、易于实现等优点,故已被广泛应用于工程领域[5,6,7]。但标准ABC算法仍不可避免地存在一些缺点:如后期收敛速度慢、局部搜索能力差等。针对这些问题,本文采用反向学习策略改善初始解,引入自适应比例选择策略替代轮盘赌策略,应用基于指数分布突变策略更新蜜源位置等方法得到一种新的改进人工蜂群算法,将其应用于水电站优化调度中,并通过比较人工蜂群算法、基本粒子群算法调度结果,验证了该算法的可行性和高效性。

1 水电站优化调度模型

1.1 目标函数

本文以电站年发电量最大为模型的优化目标,目标函数如下:

$\text{m}\text{a}\text{x}E={\displaystyle \sum _{t=1}^{{\rm T}}A}Q{}_t{\rm H}{}_t\text{Δ}t(1)$

式中:E为水电站的年发电量,kWh;A为水电站的综合出力系数;Qt为水电站在t时段的发电流量,m3/s;Ht为水电站在t时段的平均发电净水头,m;T为水电站调度年内计算总时段(本文计算时段为月,T=12);Δt为第t时段的小时数,h。

1.2 约束条件

(1)水库的水量平衡约束:

$V{}_{t+1}=V{}_t+(q{}_t-Q{}_t-S{}_t)\text{Δ}t(2)$

式中:Vt、Vt+1分别为水电站第t时段初、末的水库蓄水量,m3;qt为水电站第t时段的平均入库流量,m3/s;Qt、St分别为水电站在t时段的发电流量、弃水流量,m3/s;Δt为第 时段时长,s;t=1,…,T。

(2)水库的蓄水量约束:

$V{}_{\min ,t}\le V{}_t\le V{}_{\max ,t}(3)$

式中:Vmin,t为水电站第t时段允许水库最小蓄水量,m3;Vmax,t为水电站第t时段允许水库最大蓄水量,m3。

(3)水库的下泄流量约束:

$Q{}_{\min ,t}\le Q{}_t\le Q{}_{\max ,t}(4)$

式中:Qmin,t为第t时段的水库应保证的最小下泄流量,m3/s;Qmax,t为第t时段水轮机最大过流流量,m3/s。

(4)水电站的出力约束:

${\rm N}{}_{\min ,t}\le {\rm N}{}_t\le {\rm N}{}_{\max ,t}(5)$

式中:Nmin,t、Nmin,t分别为水电站允许出力的上、下限,kW,需要考虑机组额定出力、保证出力等才能确定。

(5)变量边界约束:

$V{}_{({\rm K}+1,1)}=V{}_{({\rm K},1)}V{}_{({\rm K}+1,n)}=V{}_{({\rm K},n)}(6)$

式中:V(K,1)、V(K+1,1)为分别为迭代第K、K+1次后的起始库容,m3;V(K,n)、V(K+1,n)分别为迭代第K、K+1次后的末库容,m3。

(6)变量非负约束。

上述所有决策变量均为非负变量。

$X\ge 0(7)$

式中:X为决策变量组成的向量。

2 基于水电站调度的人工蜂群算法

在ABC算法中,人工蜂群分别由引领蜂(employed bees)、跟随蜂(onlooker bees)和侦察蜂(scout bees)组成。其中,引领蜂和跟随蜂各占一半,一个引领蜂对应一个被发现的花蜜源(一个蜜源的位置代表所求优化问题的一个可行解),即引领蜂数目等于蜜源数目。当某个引领蜂放弃蜜源后就变成侦察蜂。本文在水电站水库优化调度中以水库库容作为决策变量,即以调度期内各月的库容序列作为蜜源的位置,以调度期内电站的发电量作为适应度函数。基于水电站调度的ABC算法搜索过程如下:

(1)随机生成SN个初始库容序列(花蜜源),每个库容序列Vi(i=1,2,…,SN)是一个T维向量。

$V{}_{i,t}=V{}_{\min ,t}+r{}_{i,t}(V{}_{\max ,t}-V{}_{\min ,t})(8)$

式中:Vi,t为解向量Vi的第t维的分量;t∈{1,2,…,T};Vmin,t、Vmax,t分别为水电站第t时段允许水库最小、最大蓄水量;ri,t为(0,1)之间的随机数。

(2)引领蜂在记忆中邻近的蜜源(库容序列)内搜寻一个新的蜜源,

$V{}_{i,t}^u=V{}_{i,t}+\text{ϕ}{}_{i,t}(V{}_{i,t}-V{}_{j,t})(9)$

式中:V${}_{i,t}^u$为新解库容向量V${}_i^u$的第t维的分量;j∈{1,2,…,SN},j≠i;Vj,t为库容向量Vj,t的第j维的分量;ϕi,t为[-1,1]之间的随机数。

V${}_i^u$即为对Vi邻域内搜寻所得新的可行解。若V${}_i^u$对应的适应度值(发电量)优于Vi的适应度值,则用V${}_i^u$代替Vi,否则保持原库容序列Vi不变。

(3)引领蜂用摇摆舞和蜂巢内的跟随蜂分享蜜源信息,根据每个蜜源(库容序列)的适应度,计算其被跟随蜂选中的概率,其表达式如下:

$p{}_i=F{}_i/{\displaystyle \sum _{j=1}^{S{\rm N}}F}{}_j(10)$

式中:Fi为第i个可行库容序列(蜜源位置)的适应度值(发电量)。

(4)跟随蜂根据概率以轮盘赌的方式选择相应的蜜源(库容序列),进而在其邻域内按照(9)式进行搜索。

(5)如果一个蜜源的位置(库容序列)不能在预先设定的循环次数limit内进一步改进,则该处的引领蜂放弃蜜源,变为侦察蜂,并按照(8)式重新开始随机搜索新的蜜源。被放弃的蜜源将会由该侦察蜂找到的新蜜源所取代。

(6)记录迄今为止发现的最好的蜜源(库容序列)位置。

(7)检查终止条件。假如最优蜜源的位置(最优库容序列)是可接受的或达到最大迭代次数,停止计算并返还最好的蜜源位置;否则,返回(2)重新计算。

3 改进人工蜂群算法

为了改善ABC算法的性能,本文从以下3个方面加以改进。

3.1 基于反向学习的种群初始化

根据概率论原理,相比随机产生的初始解,相反解有50%的概率更接近所求问题的最优解,因此,为加速收敛,常选择二者中更优的个体作为初始种群[8]。

令V=(v1,v2,…,vT)为T维空间中的一点,其中vt∈[Vmin,t,Vmax,t],t=1,2,…,T,则其反向点V′定义为V′=(v′1,v′2,…,v′T),其中v′t=Vmin,t+Vmax,t-vt。

如果V′对应的适应度值比V的适应度值更优,则用V′替代V;否则保持V不变。

3.2 跟随蜂选择蜜源方式的改进

在ABC算法中,跟随蜂是以轮盘赌的方式来进行概率选择蜜源,但是作为一种贪婪选择方式,轮盘赌本身容易导致群体多样性的下降,使算法极易陷入局部最优。而自适应比例选择机制[9]在理论上可以有效地解决优化算法中过早收敛的问题,使系统最终演化到全局极小点。根据该机制跟随蜂进行蜜源选择的概率由(10)式变为下式:

${\rm P}{}_i=\frac{(F{}_i){}^{\lambda }}{{\displaystyle \sum _{j=1}^{S{\rm N}}(}F{}_j){}^{\lambda }}(11)$

其中,幂指数λ应用式(12)求得:

$\lambda =\frac{k}{\frac{F{}_{\max }}{\overline{F}}-1}(12)$

式中:Fmax、$\overline{F}$为集合{Fi:i=1,2,…,SN }中的最优适应度值(最优发电量)、平均适应度值(平均发电量),k为系数。

从式(11)中可以看出,当$\overline{F}/F{}_{\max }=(k+1){}^{-1}$时,λ=1。当$\overline{F}/F{}_{\max }<(k+1){}^{-1}$时,λ<1;其中,当λ→0时,Pi=1/SN。当$\overline{F}/F{}_{\max }>(k+1){}^{-1}$时,λ>1;其中,当λ→∞时,如果Fi<Fmax,Pi=0;如果Fi=Fmax,Pi=1/M(M为最优个体的个数)。自适应比例选择机制动态调整了搜索最优解过程中的选择压力,使得群体在早期保持较高的多样性,而在后期缩小了搜索空间,加快了当前最优解的改变速度。

3.3 指数分布突变策略

在标准ABC算法中,(9)式中[-1,1]之间的随机数ϕi,t使得Vi在其邻域内搜寻新的蜜源(库容序列)时具有一定的盲目性,在本文中引进指数分布的比例因子SFi,t加以改进[10],故公式(9)将被下式代替:

$V{}_{i,t}^u=V{}_{i,t}+SF{}_{i,t}\text{ϕ}{}_{i,t}(V{}_{i,t}-V{}_{j,t})(13)$

式中:V${}_{i,t}^u$为新的库容序列V${}_i^u$的第t维的分量;j∈{1,2,…,SN},j≠i;Vj,t为库容向量Vj,t的第j维的分量;ϕi,t为[-1,1]之间的随机数。

SFi,t是从指数分布的随机数中产生的。

$SF{}_{(i,t),k}=\beta SF{}_{i,t}+(1-\beta )2{}^{r[k]}(14)$

式中:k值取为1或者2;r[1]∈[α1,0]、r[2]∈(0,α2]为2个随机数,其中α1<0、α2>0。SFi,t取为使V${}_{i,t}^u$对应的适应度值(发电量)更优的SF(i,t),1或者SF(i,t),2。

4 应用实例

本文以新安江水电站为例进行中长期优化调度计算。新安江水电站位于浙江建德市新安江镇以北约4.5 km的铜官峡中,是我国自行设计、自制设备和自己建设的第一座大型水电站。电站以发电为主,兼有防洪、灌溉、渔业、航运、旅游等综合功能。电站装机容量810 MW(9×90 MW),保证出力178 MW,多年平均年发电量18.9亿kWh。坝址控制流域面积10 442 km2,水库正常蓄水位108.0 m,死水位86.0 m,目前为了生态景观需要,其库水位一般不低于89.0 m,调节库容102.7亿m3,库容系数0.968,具有多年调节性能。新安江水库的水位库容关系曲线、下游水位流量关系曲线分别见图1、图2所示。以该电站某典型年3月初至次年2月底为计算调度期,以月为时段。调度期起始水位和终止水位均假定为98.0 m。

智能算法的参数取值对算法性能有一定影响,参数值一般需要根据反复实验获得的经验值来设置。文中人工蜂群算法的参数取值根据参考文献[10]确定,参数α1=-15、α2=10、β=0.10。蜂群个数取为80,其中引领蜂和跟随蜂各占一半,都为40,蜜源数量SN=40。基本粒子群算法参数选择参见文献[11],学习因子c1=c2=2,惯性因子ω=1最大速度vmax=5。计算代数取为2 000。计算流程图见图3所示。

按照上述的原始资料及算法参数,利用MATLAB软件编程实现改进蜂群算法并进行求解。为了比较,同时给出了ABC算法和基本粒子群算法(PSO)的水电站优化调度结果。在计算中为了消除初始解的不同所带来的影响,ABC算法初始解也采用反向学习策略产生。计算结果如图4所示。

从图4中可以看出,①与粒子群算法相比,人工蜂群算法和改进人工算法的收敛速度更快;②在改进人工蜂群算法计算过程中,由于侦察蜂随机搜索到的解不一定是可行解,故此造成该算法相比人工蜂群算法,在收敛速度上并没有提高;③改进人工蜂群算法的计算结果为18.29亿kWh,结果优于人工蜂群算法的18.24亿kWh、粒子群算法的18.21 kWh。

5 结 语

(1)相比于基本粒子群算法,人工蜂群算法具有更快的收敛速度。这是由于人工蜂群算法迭代时采用蜜源邻域搜索及跟随蜂进一步优化机制,在轮盘赌选择机制的基础上,重点搜索可能出现全局最优解的区域。而基本粒子群算法优化依赖于历史最优解和当前最优解,致使其更容易陷入局部最优。

(2)人工蜂群算法作为一种新兴的人工智能算法,在水库调度领域具有很好的应用前景。本文中采用反向学习策略改善初始种群、引进自适应选择策略改进跟随蜂选择蜜源概率、应用基于指数分布突变策略提高全局搜索能力等方法对人工蜂群算法加以改进。相比人工蜂群算法,改进后的人工蜂群算法更容易跳出局部最优解,具有较强的全局搜索能力。

(3)今后,可进一步研究将人工蜂群算法和其他智能算法相结合,整合各个算法的优点,提高收敛速度和寻优能力,为求解水电站水库(群)优化调度问题提供更优的途径。另外,目前智能算法参数的取值更多地依赖于反复试验,如何在理论上确定能使算法达到最优的参数值,也是以后需要重点解决的问题。

摘要：首先建立了水电站水库优化调度模型。在对人工蜂群算法描述的基础上,为有效避免标准人工蜂群算法局部搜索能力差等缺点,提高寻优能力,设计了一种以反向学习策略搜寻初始解、以自适应比例选择策略代替轮盘赌法、以基于指数分布突变策略更新蜜源位置的改进人工蜂群算法。应用MATLAB软件将改进后的人工蜂群算法应用于新安江电站水库优化调度中。仿真结果表明,改进人工蜂群算法具有更好的全局搜索能力,调度结果优于人工蜂群算法和粒子群算法。

关键词：水库调度,人工蜂群算法,反向学习,自适应选择,指数分布突变策略

参考文献

[1]Basturk B,Karaboga D.An artificial bee colony(ABC)algorithmfor numeric function Optimization[C]∥USA:IEEE Swarm Intel-ligence Symposium,Indiana,2006:3-4.

[2]刘波,王凌.差分进化算法研究进展[J].控制与决策,2007,22(7):721-726.

[3]段玉倩,贺家李.遗传算法及其改进[J].电力系统及其自动化学报,1998,10(1):39-52.

[4]黎晓峰,薛保菊,李维乾.基于改进粒子群算法的水库优化调度研究[J].水力发电,2008,34(11):107-109.

[5]胡中华,赵敏.基于人工蜂群算法的无人机航迹规划研究[J].传感器与微系统,2010,29(3):35-38.

[6]Suri B,Kalkal S.Review of artificial bee colony algorithm tosoftware testing[J].International Journal of Research and Re-views in Computer Science,2011:706-711.

[7]Tasgetiren M F,Bulut O,Fadiloglu M M.A discrete artificialbee colony algorithm for the economic lot scheduling problem[C]∥IEEE congress on evolutionary computation,2011:347-353.

[8]Rahnamayan S,Tizhoosh H R,Salama M M A.Opposition-based differential evolution algorithms[C]∥Canada:IEEE Con-gress on Evolutionary Computation,2006:2 010-2 017.

[9]杨新武,刘椿年.遗传算法中自适应的比例选择策略[J].计算机工程与应用,2007,43(20):25-27.

[10]Alam M S,Kabir M W,Islam M.Self-adaptation of MutationStep Size in Artificial Bee Colony Algorithm for ContinuousFunction Optimization[C]∥Proceedings of 13IntemationalConference on Computer and Information Technology,2010:69-74.

[11]水电站优化调度人工蜂群新算法[J].水电自动化与大坝监测,2012,36(3):66-69.

人工蜂群优化算法 篇2

由于国家规范给定的暴雨强度公式形式是非线性模型,此模型中多采用传统的图解法和线性最小二乘法相结合的非线性方法[2]或优选回归法[3]确定公式中的参数,采用这种方式不但计算复杂、通用性差,最重要的是不能够得到全局的最优解。为了克服这些弊端,近年来在优化暴雨强度公式中参数时采用遗传算法[4]、蚁群算法[5]等方法,并取得了很好的效果。

2005年Karaboga通过模拟蜜蜂的群体采蜜行为而提出了一种基于群体智能的随机优化算法,即人工蜂群算法[6]。虽然对于人工蜂群算法的研究和应用还处于初级阶段,但是由于其具有控制参数少、易实现以及计算间接等优点,引起越来越多学者的关注。本文优化了人工蜂群算法应用到不同重现期暴雨强度公式中的参数,同时分析比较了遗传算法的优化结果。通过仿真试验结果表明,利用人工蜂群算法能有效的提高暴雨强度公式参数估计的精度。

1 人工蜂群算法及暴雨强度公式参数的优化

1.1 人工蜂群算法

在人工蜂群算法中,引领蜂、跟随蜂以及侦查蜂三部分组成了人工蜂群。利用人工蜂群算法求解优化问题时,食物源的位置代表优化问题的一个可能解,蜜蜂采蜜的过程即搜寻最优解的过程。考虑全局优化问题:minf(X)s.t.X∈S奂Rn,每一个食物源的位置对应一个可行解,优化问题的函数值或适应值取决于每个食物源的优劣程度。解的个数(SN)等于引领蜂或跟随蜂的个数。用一个D维的向量Xi=(xi1,xi2,…,xi D)表示第i个食物源的位置(i=1,2,…,SN,D为搜索空间的维数)。首先,ABC随机产生SN个解(食物源)的初始种群,每个解Xi=(xi1,xi2,…,xi D)(i=1,2,…,N)为一个D维的向量。经过初始化,蜜蜂对所有的食物源进行循环搜索,循环次数为MCN。通过不断的搜索以及比较食物源,从而确定更好的食物源位置。

引领蜂和跟随蜂根据下式进行邻域搜索

式中,k∈{1,2,…,SN},j∈{1,2,…,D},这两个数都是随机选取的,但k≠i,rij是[-1,1]上均匀分布的随机数,它控制xij邻域的生成范围。

在此算法中,跟随蜂通过观察引领蜂的摇摆舞判断食物源的收益率,最终选择哪个食物源采蜜主要依据收益率。收益率通过适应值来表示,选择概率Pi由下式确定:

式中fiti为第i个解的适应值。

在人工蜂群算法中,还有一个重要的控制参数“limit”,它用来记录某个解被更新的次数。假定某个解连续经过limit次循环之后没有得到改善,表明这个解陷入局部最优,那么这个位置就要被放弃,与这个解相对应的引领蜂也转变为侦察蜂。假设被放弃的解是xi,则侦察蜂通过下列公式替换xi:

式中j∈{1,2,…,D}。

1.2 暴雨强度公式参数的优化暴雨强度公式的一般形式为

式中,i为暴雨强度(mm·s-1);t为降雨历时(min);A、B、n皆为待定参数,它们确定了在不同重现期的暴雨强度i与降雨历时t的相关性。采用人工蜂群算法确定式(4)中的参数A、B、n,可构造目标函数如下:

其中ti′为同一重现期观测值i′的暴雨强度的历时;i′为暴雨强度的实际观测值,m为同一重现期的不同暴雨强度i′的次数。

不同重现期的暴雨强度实际观测值i′和降雨历时t的有关数据列于表1,资料来源于文献[4]。

不同重现期的暴雨强度和降水历时满足关系(4),应用人工蜂群算法对其参数A、B、n进行优化。将表1中同一重现期的实际观测值i′的暴雨强度相应的降雨历时t的数据代入式(4),在满足目标函数式(5)的情况下,应用人工蜂群算法对参数A、B、n进行优化。优化时,人工蜂群算法的种群规模为400,最大迭代次数为600,limit=100,其中种群规模和最大迭代次数与文献[4]采用的遗传算法设置相同。7组不同重现期的参数A、B、n的优化结果见表2。将优化得出的参数值代入式(4),计算出不同重现期的暴雨强度的计算值i和均方根误差σ亦见表2。

2 试验结果比较

表2中列出了遗传算法(GA)[4]对同一实例的不同重现期的暴雨强度公式中的参数A、B、n的优化结果和暴雨强度的计算值iGA及相应的均方根误差σ。

通过表2可以看出,暴雨重现期越短,参数的优化效果越好。相对遗传算法,人工蜂群算法的优化效果更明显。虽然遗传算法不受模型的连续、可微条件的限制,但是由于其自身的缺陷容易产生早熟收敛的现象,很难得出问题全局的最优解。但是人工蜂群算法不但具有上述优点,且容易获得全局最优解,因此,能够获得精度更高的模型参数。

3 结论

人工蜂群算法是一种基于群体智能的演化算法,能够很好的解决连续空间的优化问题。另外,使用人工蜂群算法优化暴雨强度公式的参数时具有较高的精度,且方法简单、通用。

参考文献

[1]GBJ14-87,室外排水工程规范[S].北京:中国建筑工程出版社,1988.

[2]王敏,谭向诚.北京城市暴雨和雨型的研究[J].水文,1994,3:1-6.

[3]杨开,程晓如.暴雨强度公式中系数B统计算法一例[J].人民长江,1996,27(3):16-22.

[4]李祚泳,彭荔红.基于遗传算法的暴雨强度公式参数的优化[J].高原气象,2003,22(6):637-639.

[5]邹长武,熊建秋,李祚泳.改进的蚂蚁算法及其在暴雨强度公式参数优化中的应用[J].四川大学学报(工程科学版),2005,37(5):9-13.

多目标人工蜂群算法研究 篇3

无论在科学研究还是工程应用上, 大多数问题都是多目标优化问题, 存在多个彼此冲突的目标, 如何获取这些问题的最优解, 一直是学术界和工程界关注的焦点问题。与单目标优化问题不同, 多目标优化的本质在于, 大多数情况下, 某目标的改善可能引起其他目标性能的降低, 同时使多个目标均达到最优是不可能的, 只能在各目标之间进行协调权衡和折中处理, 使所有目标函数尽可能达到最优。

智能优化算法是一类通过模拟某一自然现象或过程而建立起来的优化方法, 因其对函数要求低、进化过程与初始值无关、搜索速度快等优点, 迅速成为科研热点。发展较快的算法有Dorgo等[1]人提出的蚁群算法 (Ant Colony Optimization’ACO) 和Kennedy等[2]人提出的;粒子群算法 (Particle Swam Optimization’PSO) 等。人工蜂群算法 (Artificial Bee Colony’ABC) 也越来越多地受到人们的关注。这类算法和传统的数学规划相比, 智能优化方法更适合求解多目标优化问题。近年来很多学者对在多目标智能优化方法的理论与应用方面取得了一系列研究成果。其中比较成熟的算法有多目标进化算法 (MOEA) [3]、张勇德等[4]提出来的多目标蚁群算法、Ulungu等[5]设计了完整的多目标模拟退火算法 (MOSA) 和Coello Coello等[6]提出的多目标粒子群算法 (MOPSO) 。

MOPSO对多目标优化问题的处理方法和MOEA有些类似, 但与MOEA不同, MOPSO一般不必进行适应度复制, 简化算法设计;但MOPSO必须为每个粒子从外部档案中选取一个合适的全局最好位置。这是MOEA设计中没有的。MOPSO的主要步骤包括外部档案维护、全局最好位置选取、自身最好位置更新以及如何保证粒子始终在搜索空间内飞行等。

本文在原有算法的基础上借用MOEA的相应方法并引入MOPSO最优解和最优位置的思想, 实现人工蜂群算法的多目标优化。

1 人工蜂群算法基本原理

人工蜂群算法 (ABC) 是基于密封采蜜行为的一种蜂群算法, 是由土耳其埃尔吉耶斯大学的Dervis Karaboga[7]在2005年提出的。

1.1 ABC算法原理

在ABC算法中, 将人工蜂群按分工分为三种:采蜜蜂、观察蜂和侦察蜂。其中采蜜蜂和观察蜂各占一半, 每一个食物源只有一个采蜜蜂, 即采蜜蜂的数量等于食物源的数量。当采蜜蜂对应的食物源食物消耗完, 采蜜蜂就会成为侦察蜂。它们之间分工协作, 互传信息, 使采蜜工作向高效的方向进化。三种蜜蜂之间可以互换角色。采蜜蜂是发现优质蜜源并进行初步邻域搜索的蜜蜂, 它的数量和蜜源数量相等;观察蜂等待采蜜蜂传递蜜源质量信息, 以此判断对哪个采蜜蜂的蜜源进行邻域搜索;侦察蜂则进行全局随机搜索, 以发现质量更高的新蜜源。每只蜜蜂对应了一个解, 采蜜蜂代表构成当前种群的现有解;观察蜂代表潜在的邻域搜索解, 有机会进入种群成为现有解;侦查蜂则代表全局随机搜索解, 可以代替废弃的现有解。

1.2 算法主要步骤[8]

步骤1将采蜜蜂随机初始化, 一一对应一个食物源, 并根据目标函数计算该处的食物浓度。记录最优位置和最优适应度。假设有SN个食物源, 每个食物源xi=|xij| (i=1, 2, …, SN, j=1, 2, …, D) , D为目标空间的维数。初始化时通过式 (1) 随机产生SN个解。

步骤2每只采蜜蜂进行如下操作:随机选取采蜜蜂中的一个邻居, 随机选取某一维度, 按照公式 (2) 更新位置, 式中k∈{1, 2, …, SN}, 但k≠i, SN为采蜜蜂的数目, j∈{1, 2, …, D}, D为目标空间的维数, 如果新位置的适应度更优, 则更新到该位置否则该采蜜蜂的未更新计数Basi加1。

步骤3按照公式 (3) 计算每只采蜜蜂被选中的概率, 式中, fi是第i个解的目标函数值, fiti为第i只采蜜蜂的适应度。

步骤4每只观察蜂进行如下操作:按照轮盘赌策略选择一只采蜜蜂, 并根据公式 (3) 进行更新位置, 如果新位置最优, 则被选择的采蜜蜂更新到该位置, 否则该采蜜蜂的未更新计数Basi加1。一只采蜜蜂可以被多只观察蜂重复选择, 因此适应度优的采蜜蜂被选择的几率更大, 次数更多。

步骤5记录此代发现的最优食物源的位置和浓度。

步骤6选取Bas数最大的采蜜蜂, 如果大于Limit, 则将该采蜜蜂视为侦察蜂, 对其位置、适应度和Bas计数初始化。参数Limit的作用是使长期得不到更新的采蜜蜂获取重生。

步骤7如果迭代次数小于最大代数Max Cycles, 转到步骤2, 否则输出最优值。

2 多目标人工蜂群算法

2.1 优化算法设计

标准的人工算法由于采蜜蜂和观察蜂在更新食物源位置时采用的是随机选取邻居的策略导致局部开发能力较弱, 因此借鉴粒子群算法, 引入全局最优解记录全局最优位置, 使得采蜜蜂在探索新的食物源位置时受到全局最优位置的引导, 从而提高算法的性能, 也可以减少计算量。

记录全局最优解的位置, 使采蜜蜂不按照公式 (1) 而按照公式 (4) 来进行更新位置, 其中为至今发现的全局最优位置。

本文引入多目标进化算法中的Pareto非劣排序和拥挤距离[9]以及全局最优解的概念, 将人工蜂群算法与多目标优化思想结合。每个单目标问题所生成的个体集合称为子种群, 所有子种群的结合称为多目标种群, 各个但目标的子种群规模是相同的, 另外建立一个外部档案来保存Pareto最优解。在每生成新一代多目标种群后都根据非劣排序对外部档案中的个体进行更新, 保证外部档案中的解都是目前意义上的Pareto最优解。

2.2 Pareto支配关系

设p和q是进化群体中任意两个不同的个体, 称p支配q则必须满足下列两个条件:

(1) 对所有的子目标, p不比q差, 即fk (p) ≤fk (q) , (k=1, 2, …, r) 。

(2) 至少存在一个子目标, 使得p比q好, 即

其中r为子目标向量。

此时称p为非支配的, q为被支配的, 表示为其中是支配关系。

2.3 非劣排序

对集合进行非劣排序的具体过程如下:

(1) 令每个解x∈H对应的支配数即支配解x的所有个体数量nx=0, 以及解对应的集合Sx, 即解x所支配的个体集合为空集, 然后对应集合H中的每个解q, 如果则, Sx=Sx∪{q}如果则nx=nx+1。最终得到每个解对应的支配数nx和集合Sx, 并将nx=0的解放入前端F1中, 且xrank=1。

(2) i=1

(3) 令Q为空集, 对于每个解x∈Fi, 执行如下操作:

对于每个解q∈Sx, nq=nq-1;如果nq=0, 则qrank=i+1且Q=Q∪{q}。

(4) 如果Q不为空集, 则i=i+1, Fi=Q, 转到 (3) ;否则, 停止迭代。

2.4 个体的密度值

拥挤距离用来估计一个解周围其他解的密集程度。个体的密度值为个体与第K个最邻近个体间的距离为种群规模为档案的最大规模。

2.5 外部档案

外部档案更新策略:对于每个新解, 如果新解受档案成员支配, 则拒绝新解加入档案中;如果新解支配了部分档案成员, 则移出那些受支配的成员, 同时将新解加入档案中;如果新解和档案中的所有成员彼此不受支配, 则直接将新解加入档案中。当档案大小超过或达到规定的最大规模时, 计算所有档案成员的拥挤距离, 并从大到小排序, 保留其中拥挤距离最大的个档案成员, 其他成员从档案中剔除。

2.6 算法描述

步骤1初始化种群, 设定Limit参数。设cycle=0。初始化时通过式 (1) 随机产生SN个解构成初始种群P0。

步骤2对Pcycle进行非劣排序, 得到一个非劣前端集F。

步骤3对非劣前端依次加入容量为的空集H。如果加入Fi (0<i<m) 时H内的个体超过个, 则将Fi的每个元素按拥挤密度升序排列, 依次加入H直至被填满。

步骤4记住搜索过程中的最优蜜源位置。

步骤5若cycle达到规定的最大迭代次数, 算法结束, 当前状态下的H即为Pareto最优解集;否则Pcycle+1=H, 转步骤6。

步骤6令Pcycle+1中蜜源为采蜜蜂蜜源, 观察蜂与采蜜蜂个数相等。Pcycle+1中每只采蜜蜂按照 (3) 式寻找一个新的蜜源位置, 并计算该位置的适应度, 如果新位置优于原来的位置, 则用新位置替换掉原来的位置, 否则保留原来的位置。观察蜂再按照轮盘赌策略选择一只采蜜蜂根据公式 (4) 进行更新位置。

步骤7所有观察蜂搜索完毕后, 将种群中未参与运算的采蜜蜂Bas数加1。

步骤8确定放弃蜜源的位置, 如果存在该蜜源, 则该处的采蜜蜂变为侦察蜂, 根据 (4) 式随机生成的蜜源替换该蜜源。得到新的规模为的种群Qcycle, 将其加入Pcycle+1。对于Pcycle+1中重复的个体只保留一个。

步骤8 cycle=cycle+1, 转步骤2。

3 实验测试

为了试验新算法, 做了一个仿真实验。实验环境AMD Trinity APU A8-4500M 1.9GHz处理器, 4GB内存, 在win7平台下用C++编译运行。

采用测试函数DTLZ6[10]。设定算法的进化代数为1000, 存储档案数目500, 目标维数为22, 蜜源个数100, 目标函数个数为3。测试结果如下:

多目标人工蜂群算法运行1000代的总时间为280.38S。此时第1000代的档案集为此算法最优解集。

同样参数下对函数采用多目标粒子群算法 (MOPSO) 进行测试, 测试结果为:

MOPSO运行1000代总时间为132.99, 最后第1000代的档案集为此算法最优解集。

经过试验, 从图表的分析中可以得出, 多目标人工蜂群算法是一种行之有效的优化方法, 但在运行效率方面, MOPSO较多目标人工蜂群算法好, 多目标人工蜂群算法运行速度相对较慢。

4 总结

本文讨论了人工蜂群算法基本原理以及算法具体过程, 以人工蜂群算法为基础, 提出了一个基于Pareto占优的多目标人工蜂群算法。将其应用在测试函数上能获得很好的结果, 而且思路简单, 易于实现, 为进一步改善及应用打下良好的基础。

摘要：人工蜂群算法是一种模仿蜜蜂采蜜行为的新兴群体智能算法。本文在人工蜂群算法的基础上采用多目标进化算法中的Pareto非劣排序和个体密度值的概念并借鉴粒子群算法, 引入全局最优解记录全局最优位置, 提出了一个基于Pareto占优的多目标人工蜂群算法。最后验证了算法的可行性。

关键词：人工蜂群算法,Pareto,粒子群算法,采蜜行为

参考文献

[1]Dorgo M, Maniezzo V, Colorni A.The ants system:optimization by a colony of cooperating agents[J].IEEE Transations on System, Man and Cybernetics Part B:Cybernetics, 1996, 26 (1) :29-41.

[2]Kennedy J, Ebethart R.Particle swarm optimization[C]//Proceeding of IEEE International Conference on Neural Networks.Piscataway, NJ:IEEE Computer Society, 1995:1942-1948.

[3]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007

[4]张勇德, 黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策, 2005, 20 (2) :170-173.

[5]Ulungu L E, Teghem J.Multi-objective combinatorial optimization problems[J]:A survey.Journal of Multicriteria Decision Analysis, 1994, 3:83-104.

[6]Coello Coello CA, Pulido G T, Lechuga M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transations on Evolutionary Computation, 2004, 8 (3) :256-279.

[7]Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-TR06[R].Erciyes University, Engineering Faculty, Computer Engineering Department, 2005

[8]袁亚杰.一种改进的人工蜂群算法[J].中国科技信息, 2011, 24 (055) :102-103

[9]Deb K, Pratap A, Agarwal S, et, al.A fast and elitist multiob-jective genetic algorithm NSGA-I[IJ].IEEE Trans on Evolutionary Computation, 2002, 6 (2) :182-197.

基于变异机制的人工蜂群算法 篇4

1 人工蜂群算法

ABC模拟实际蜜蜂高效的采蜜机制来处理函数优化问题, 将人工蜂群分为3类:引领蜂、跟随蜂和侦查蜂, 前两种蜜蜂用于蜜源的开采, 而侦查蜂为避免蜜源种类的过少[3]而不断的寻找新的蜜源并替代原来不需要或者说已经使用过的蜜源。每个食物源代表一个待求问题的解而该食物源花蜜的多少代表这个解的优劣程度。待找最优蜜源的过程如下:随机产生2N个位置, 通过简单的选择选取较优异的N个作为蜜源的位置, 引领蜂找到这些蜜源并标记他们记, 然后在这些标记蜜源附近按式 (1) 搜索新蜜源:

式中:Vij为新蜜源的位置, xij为已标记过蜜源的第i维位置, xkj为随机选择的不等于i的已标记过蜜源的第j维位置, Rij为[-1, 1]间的随机数。根据前后蜜源的花蜜数量选择较优的蜜源替代初始标记的蜜源, 并继续在标记蜜源附近用 (1) 式搜索新蜜源, 并与初始标记蜜源比较, 按照上述的方法反复循环迭代, 直到达到算法的终止条件。

2 基于随机选择的人工蜂群算法

众所周知ABC的优化效果较好, 但由于算法本身选择方式的局限性使其算法容易陷入局部最优, 在迭代的进程中【4】每代的最差解都必定会参与到新解的产生之中从而直接影响了算法的收敛速度且易使算法发生早熟。为此, 该文在最差蜜源的选择和对算法的早熟方面做了比较好的改进[5]。

2.1 最差蜜源的替换

在ABC迭代的过程中, 由于每代的最差蜜源按 (1) 式进行交叉操作而产生新的蜜源, 但是最差蜜源却几乎不可能对产生的最优蜜源做出贡献[6], 这就影响了算法的收敛速度。因此可用一个新的蜜源代替最差蜜源取消最差蜜源的破话作用。为此采取如下公式进行代替:

式中:Vij为新蜜源的位置, xij为最差蜜源的第j维位置, xkj为随机选择的不等于i的最差蜜源的第j维位置, c和d为[0, 1]间的随机数。在原来公式的基础上又增加了一个随机数【6】, 使得蜜源在相互交换时的变化更大, 从而大大的增加了蜜源变异的可能。

2.2 对算法早熟的解决

由于ABC采用轮盘赌的选择策略, 就不可避免的会早熟和陷入局部最优, 为解决这个问题, 该文在随机选择的基础上又引入了变异的思想[7]。

1) 变异机制的引入

虽然ABC在优化问题上的运用方面取得了较好的效果, 但易陷入局部最优。为有效解决这个问题而引入变异【8】的思想。ABC之所以会早熟就是因为在当前蜜源中找不到比此蜜源较优的蜜源, 而陷入局部最优并过早收敛。为了能找到较优的蜜源可以引入若干新的蜜源以替代原来被搜索过的蜜源;即改变整个蜜源的结构。伪代码如下:

2) 变异时替换蜜源的量的大小和limit的值

文中算法产生变异时选择替换的蜜源数是整个种群的10%, limit的值为50, 具体还要由具体实验来决定[9]。

3 实验仿真和结果分析

为了验证本文的一系列设想, 进行了大量的仿真测试。实验仿真是在Inter (R) Pentium (R) D, CPU 3.00GHZ、1.25G内存的计算机上实现, 程序采用Matlab7.10语言编程实现。为便于描述以VABC代表新提出的ABC, 为了验证本文提出的VABC的优化效果选用函数优化领域广泛采用的4个标准测试函数进行测试。前3个的理论最优值都为0, 最后一个的最优值为-4.1898n, 把本函数与原ABC的运行效果进行比较。

ABC相应参数设定如下:引领蜂、跟随蜂的数量都取N=40, 蜜源的数量取N/2=20, 测试函数和蜜源的维数都取100维, limit为50, 各个函数迭代8000次。各算法均随机运行50次, 并取这50次数据的平均值、方差、最优值、最差值、平均收敛代数和平均运行时间来考察算法的寻优性能。为了能够更好的证明的优越性各项数据与原ABC的运行结果相比较。具体结果见表1。

由表1中数据可以得出如下结论:

1) 在抑制早熟上VABC有着显著的效果, 反映在上表中就是收敛的代数比较大。

2) 在算法的精确度上VABC有着比较明显的提高, 从最优值、平均值和最差值上均优于原ABC, 且VABC的方差较小, 说明结果比较稳定。

3) 运行时间上两算法相差不大, 但是VABC在取得良好效果的同时时间不长可见优势明显。

4 结束语

针对ABC易陷入局部最优、收敛速度慢的缺点, 该文利用了变异的概念实现了局部替换, 由此提出了一种改进的人工蜂群算法—VABC。本算法跟传统的ABC相比在解决函数优化类问题上优势明显。

摘要：针对人工蜂群算法存在的收敛速度慢、易陷入局部最优的缺点, 利用变异方法来取代传统的选择模型。对4个标准测试函数的仿真表明本文提出的随机选择算法不仅能延长算法的收敛速度还能在算法的精度上有着明显的提高, 改进后的性能明显优于人工蜂群算法。

关键词：人工蜂群算法,变异,收敛速度

参考文献

[1]Karaboga D, Basturk B.On the performance of artificial bee colony (ABC) algorithm[J].Applied Soft Computing, 2008, 8 (1) :687-697.

[2]LIU Xingbao, CAI Zixing.Artificial bee colony programming made faster[J].Natural Computation, 2009 (8) :14-16.

[3]Kabboga D, Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony (ABC) algorithm[J].Journal of Global Optimization, 2007, 39 (3) :459-471.

[4]Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//Proceeding of International Computational for Modeling Control and Automation.Sydney, Australia, 2005:695-701.

[5]暴励志, 曾建湖.自适应收索空间的混沌蜂群算法[J].计算机应用研究, 2010, 27 (4) :1331-1335.

[6]丁海军, 冯庆娴.基于Boltzmann选择策略的人工蜂群算法[J].计算机工程与应用, 2009, 45 (31) :53-55.

[7]罗钧, 樊鹏程.基于遗传交叉因子的改进蜂群优化算法[J].计算机应用研究, 2009, 26 (10) :3751-3753.

[8]Penev K, Littlefair G, Free Search:a comparative analysis[J].Information Sciences, 2005, 172 (1) :173-193.

基于人工蜂群算法的电网故障诊断 篇5

电网故障诊断即利用保护和断路器的动作信息识别发生故障的元件和误动作的保护与断路器,找出最能解释警报信号的故障假说。目前国内外已提出多种故障诊断方法,如逻辑处理方法[1]、专家系统[2]、粗糙集[3]和Petri网络[4]等。其中专家系统难以获取完备的知识库,无学习能力,并且容错性较差。Petri网络建模时间长,模型重用性差,对网络结构依赖性较大。近年来,智能仿生算法得到了较大发展,由于其具有通用性强、对复杂问题的处理能力极强等特点,且本质上属于数值计算,非常适用于复杂工程问题的求解,因此把智能仿生算法[5]引入电力系统故障诊断中具有重要意义。智能仿生算法中,人工神经网络[6]和遗传算法[7]在电力系统故障诊断中的应用已趋于成熟,量子免疫算法[8]和二进制群智能算法[9]等也在故障诊断中取得了一定进展,当然这些方法在故障诊断应用中也存在一些问题[10]。人工神经网络的主要问题是其性能取决于样本是否完备,而要获取大型电力系统的完备样本集非常困难;与复合数据库交互的功能较弱;不擅长处理启发式的知识;不能确定如何保证人工神经网络训练时收敛的快速性和避免陷入局部最小,缺乏解释自身行为和输出结果的能力。虽然遗传算法具有鲁棒性较强等特点,但是在保护、断路器误动作的情况下,可能出现多个最优解的结果。

人工蜂群(Artificial Bee Colony,ABC)算法是Karaboga等人[11]提出的一种模拟蜜蜂群智能采蜜行为的群集智能随机优化算法。由于算法简单,鲁棒性强,目前国内许多学者对该算法进行了改进,如引入遗传交叉因子[12]、混沌搜索策略[13]、反向学习的变异策略[14]以及与其他智能算法混合[15]的人工蜂群算法。本文从代数(数值)和几何(图)角度出发,提出了两种优化的人工蜂群算法,用于解决电网故障诊断中的0-1规划问题[16],为电网故障诊断提供了一种新的解决手段。

1 电网故障诊断优化模型

基于优化模型的电网故障诊断的基本思想是根据故障元件和保护、开关动作之间的逻辑关系,引入目标函数,从而把故障诊断问题转换成0-1规划问题,然后根据优化算法找出最能解释警报信号的故障假说。根据参考文献[17],可将电网故障诊断问题表示为使式(1)所示的目标函数最小化问题。

undefined

式中:S为n维向量,表示系统中元件的状态(n为系统中元件的数目),Si=0表示第i个元件为正常状态,Si=1表示第i个元件为故障状态;nr为保护总数目;nc为断路器总数目;rk为R中的第k个元素,表示第k个保护的实际状态(未动作状态或动作状态),其中R为nr维向量,表示nr个保护的实际状态;r*k(S)为R*(S)中的第k个元素,表示第k个保护的期望状态,如果第k个保护应该动作,则r*k(S)=1,否则r*k(S)=0,R*(S)为nr维向量,表示nr个保护期望状态,R*(S)的值由S的状态决定;cj为C中的第j个元素,表示第j个断路器的实际状态,cj=0表示第j个断路器处于未跳闸状态,cj=1表示第j个断路器处于跳闸状态,C为nc维向量,表示nc个断路器的实际状态;c*j(S,R)为C*(S,R)中的第j个元素,表示第j个断路器的期望状态,如果第j个断路器应该跳闸,则c*j(S,R)=1,否则c*j(S,R)=0,C*(S,R)为nc维向量,表示nc个断路器的期望状态,C*(S,R)的值由S和R的状态决定。

2 基于ABC算法的电网故障诊断

ABC算法是建立在蜜蜂自组织模型和群体智能基础上的一种优化算法。在模型中,虽然各社会阶层的蜜蜂只能完成单一的任务,但是蜜蜂通过摇摆舞、气味等信息交流方式,使得整个蜂群可以协同完成采集花粉等工作。为了协同完成采蜜的工作,将人工蜂群分为引领蜂、跟随蜂和侦察蜂3类。引领蜂具有使食物源保持优良的作用,跟随蜂根据蜜源质量选择食物源,侦查蜂为避免蜜源种类过少,随机搜索新的食物源。蜂群寻找食物源的过程就是寻找优化问题最优解的过程,而食物源就是优化问题解空间的点。食物源的质量对应优化问题的适应度,适应度值高的食物源质量较优。笔者根据电网故障诊断的0-1规划特点,分别从代数[16]和几何[9]两个角度建立ABC算法。

2.1 基于代数思想的ABC算法

2.1.1 算法原理

基于代数思想的ABC(1-ABC)算法从数值角度出发,把状态向量看作空间内的一个解(数值),并通过该解向外发散寻找另一个解。

假设在D维的搜索空间中,由N个蜜蜂组成蜂群,第i个食物源所在位置为Xi=(xi1,xi2…xiD),其中i=1,2…N,xij(j=1,2…D)∈{0,1}。蜜蜂当前所在位置的蜜源质量(目标函数适应值)为Y=fit。开始时所有蜜蜂都为侦察蜂,随机生成N个蜜源。对蜜源质量进行排名,根据排名情况确定各蜜蜂的类型,从而进入采蜜阶段。

首先,引领蜂对搜索到的蜜源质量进行排名,并把排名信息传递给跟随蜂。在跟随阶段,跟随蜂根据蜜源的质量、以一定的概率Pk选择食物源,质量越高的食物源被选择的概率越大。采用转盘式选择方法计算概率,计算式为

undefined

式中:fit(k)表示第k只引领蜂搜索到的蜜源质量;M表示引领蜂的个数。

跟随蜂P选中食物源Xi后,在食物源邻域可视范围内通过式(4)生成一个新的食物源。在侦查阶段,侦察蜂随机搜索新的食物源。为了控制某个蜜蜂连续成为引领蜂,保证解的多样性,设置参数limit,当连续成为引领蜂limit次之后,引领蜂将转变成侦察蜂。

undefined

2.1.2 算法步骤

程序初始化。

输入:从电网故障诊断系统中读取开关跳闸信息、保护动作信息、设备及其连接信息,按照式(1)形成适应度评价函数。

蜂群初始化:确定蜜蜂种群数,初始时刻所有蜜蜂都为侦察蜂,确定所有侦察蜂搜索的蜜源位置。

(1) 设变量k=1。

(2) while(k≤gen),其中gen为最大迭代次数。

(3) 确定蜜蜂类型:根据式(1)对蜜蜂搜索到的蜜源质量进行排名,排名靠前的为引领蜂,排名一般的为跟随蜂,排名较差的为侦察蜂。

(4) 跟随蜂采蜜:跟随蜂按式(2)、(3)选择引领蜂所在的蜜源进行采蜜,并根据式(4)在蜜源附近的区域寻找新的蜜源。

(5) 侦察蜂采蜜:侦察蜂随机搜索新的蜜源进行采蜜。

(6) if(i≥limit)。

(7) 引领蜂变成侦察蜂搜索新的蜜源,跳转至步骤(5)执行。

(8) Sbest←保存质量最好的蜜源。

(9) k++。

(10) End while。

输出:输出为全局质量最优的蜜源Sbest,即对应电网各元件状态。若某位置值为1,则表明对应的元件故障,若为0则表明元件正常。

程序结束。

2.2 基于几何思想的ABC算法

2.2.1 算法原理

基于几何思想的ABC(2-ABC)算法从图的角度出发,把状态向量中的元素看作一个城市,遍历所有城市的路径看作蜜源位置,从而将故障诊断问题转化成寻找最短路径的问题[18]。由于电网故障诊断是0-1规划问题,因此蜜蜂每次寻找路径只需从路径0和1中进行选择,根据参考文献[9],对该问题进行数学描述:

定义有向图G=(C,L),顶点集合C={c0(VS),c1(Vundefined),c2(Vundefined),c3(Vundefined),c4(Vundefined)…c2N-3(Vundefined),c2N-2(V1N-1),c2N-1(Vundefined), c2N(Vundefined)}。其中VS表示起始顶点,顶点Vundefined的表达式为

undefined

边集合L={(VS,Vundefined),(VS,Vundefined),(Vundefined,Vundefined),(Vundefined,Vundefined),(Vundefined,Vundefined),(Vundefined,Vundefined)…(Vundefined,Vundefined),(Vundefined,Vundefined),(Vundefined,Vundefined),(Vundefined,Vundefined)},其中,Vundefined表示指向下一个顶点Vundefined和Vundefined的两条边,即边(Vundefined,Vundefined)和边(Vundefined,Vundefined)。这两条有向边代表蜜蜂采蜜允许选择的状态0和1。蜜蜂遍历的有向图如图1所示。

更新策略中存在两级因子,即引领因子和转移因子。引领因子是指通过上一级引领路径直接确定的城市之间引领强度的大小,转移因子是指蜜蜂从城市i到城市j的转移强度,与引领因子和更新策略有关。进化代数每增加一次,各条路径上的转移因子就要归零一次,以保证转移因子没有遗留历史信息,仅根据本代路径信息更新。

本文采取的引领因子更新策略是对所有蜜蜂完成一次迭代循环之后,对所有路径的长度进行排序,得到引领路径矩阵LR,取长度排名前δ位的为引领因子。引领因子更新策略为

undefined

式中:n表示进化代数;λij表示第k只蜜蜂在第n次迭代循环中留在路径ij上的引领因子。

λij的计算式为

undefined

式中:Q为引领常数;Lk为第k只蜜蜂在本代所走的路径长度。

确定引领因子后,要根据引领因子动态确定每一个待选城市的转移因子。由于蜜蜂所选的路径只有2条,这2条路径中至少有1条路径被引领蜂走过,因此转移因子更新为

undefined

式中:ρundefined表示第k只蜜蜂从城市i到城市j的转移因子;σ(σ≤1)为没有被引领蜂走过的路径转移因子的调节参数。

确定转移因子后,蜜蜂在采蜜过程中根据转移概率决定转移方向,转移概率为

undefined

式中:α为转移因子ρij的重要程度参数;ηij为启发因子;β为ηij的重要程度参数;BS、BF、BL分别表示侦察蜂、跟随蜂以及引领蜂的集合。

ηij表达式为

undefined

式中:Lmin(n)表示上一代搜索到的最短路径长度;L(n)表示如果ij不属于Lmin(n),则把Lmin(n)中与ij相对应的路径i(-j)长度改为与路径ij长度相同。

同样,为了控制某个蜜蜂连续成为引领蜂,设置参数limit。

2.2.2 算法步骤

程序初始化。

输入:从电网故障诊断系统中读取开关跳闸信息、保护动作信息、设备及其连接信息,按照式(1)形成适应度评价函数。

蜂群初始化:确定蜜蜂种群数,初始时刻所有蜜蜂都为侦察蜂,确定所有侦察蜂搜索的蜜源位置。

(1) 设置k=1。

(2) while(k≤gen),其中gen为最大迭代次数。

(3) 确定蜜蜂类型:将蜜蜂遍历的有向图的最短路径按式(1)进行排名,排名靠前的为引领蜂,排名一般的为跟随蜂,排名较差的为侦察蜂。

(4) for(i=1;i≤D;i++),其中D为电网元件数目。

(5) 各种类型的蜜蜂根据状态转移概率进行0-1路径选择。

(6) End for

(7) if(i≥limit)。

(8) 引领蜂变成侦察蜂并搜索新的蜜源,跳转至步骤(5)执行。

(9) 将蜜蜂遍历的路径代入目标函数,求出这代的最短路径并更新转移因子。

(10) Sbest←保存最短路路径。

(11) k++。

(12) End while。

程序结束。

3 仿真分析

3.1 测试算例系统

根据参考文献[17]中的算例系统(如图2所示)进行仿真测试,该系统有28个元件、40个断路器和84个保护,其中有36个为主保护,48个为后备保护。实验程序在VC++6.0平台用C语言编写。

1-ABC算法的参数设定:限制次数limit=5,寻找邻近蜜源的范围visual=3,最大迭代次数K=100。

2-ABC算法的参数设定:限制次数limit=5,转移因子的重要程度参数α=5,启发因子的重要程度参数β=2,引领常数Q=2,调节参数δ=0.3,最大迭代次数K=100。

3.2 仿真结果分析

3.2.1 与其他算法的对比分析

为了检验ABC算法的性能特性,将其与参考文献[19]提出的遗传算法(GA)和参考文献[20]提出的一种改进的故障诊断方法进行了对比,结果见表1。其中,A和B表示母线,T表示变压器,L表示线路,S和R分别表示线路的送端和受端,m、p和s分别表示主保护、第一后备保护和第二后备保护,QF表示开关。从表1可以看出,ABC算法具有唯一性和准确性,而GA在遇到复杂故障问题时解不唯一,参考文献[20]中提出的算法在算例3中的结果不是最优解。

3.2.2 ABC算法的合理性验证

采用表1中的算例6来验证采用1-ABC算法和2-ABC算法来进行电网故障诊断是否具有合理性。

图3、图4分别给出了1-ABC算法和2-ABC算法在t=0、t=t1以及t=t2(t1

(注:GA的数据来源于参考文献[19])

3.2.3 不同种群规模下ABC算法的性能分析及比较

为进一步比较算法性能,选取表1中的算例6,比较种群规模分别为5、10、20、100时,采用1-ABC算法、2-ABC算法以及GA三种方法求解电网故障诊断时收敛于最优值的概率A、最大收敛代数B、收敛的平均迭代次数C以及程序平均运行时间D,连续运行20次的统计结果见表2。GA参数设定:最大迭代次数K=100,交叉率Pc=0.3,变异率Pm=0.07。

图5、图6给出了3种算法在N=5、N=10、N=20时的平均最小适应度值和当代最小适应度值随迭代次数的变化曲线。

从图中可以看出,ABC算法在收敛性能和进化性能等方面明显优于GA。另外,在算法结构上,ABC算法具有以下优点:(1) 编程简单,易于实现,空间复杂度好,占用的计算机存储空间少。(2) 鲁棒性强,进化速度快,通过不同类型的蜜蜂进行采蜜,具有全局搜索能力和局部搜索能力,实用性强。(3) 迭代次数大大少于GA,迭代时间短,实时性好。(4) 成功率大大高于GA,保证了电网故障诊断的准确性。

4 结语

根据电网故障诊断优化模型的0-1规划特点,分别从代数和几何角度优化了ABC算法,验证了两种优化后的算法在电网故障诊断中应用时具有合理性,并且总是能够找出最能解释警报信号的故障假说。将ABC算法与GA进行比较分析,结果显示ABC算法的收敛速度和优化结果均优于GA。在两种ABC算法中,基于几何思想的ABC算法具有更好的稳定性和搜索能力,但是从表2中的平均运行时间可以看出,基于几何思想的ABC算法时间复杂度稍差于基于代数思想的ABC算法。ABC算法比GA更能满足电网故障诊断的实时性和准确性,对于稳定性和精准度要求很高的场合,基于几何思想的ABC算法更具有适用性。

摘要：针对电网故障诊断中的0-1规划问题,从代数和几何角度优化了人工蜂群算法。仿真结果表明,人工蜂群算法具有可行性和合理性,并且综合性能显著优于传统的遗传算法;在两种人工蜂群算法中,基于几何思想的人工蜂群算法具有更好的稳定性和搜索能力,更加适用于对稳定性和精准度要求很高的场合。

终端区飞机排序的人工蜂群算法 篇6

关键词：航空运输,航班进场排序,人工蜂群算法

不断增大的空中交通流量和受限的空域及跑道资源将会直接导致终端区内航班起飞和着陆的延误。终端区内航班延误不仅会造成一定的经济损失, 而且还会产生较大的安全隐患。因此, 在确保安全和经济的前提下, 如何减少航班进场延误, 已成为空中交通流量管理的一个重要的研究内容。

由于空中等待成本较高, 因此合理的飞机进场顺序成为减少航班进场延误的有效手段。实际运行中, 通常采用先到先服务 (first come first serve, FCFS) 的方法解决。该方法依据飞机预计到达时间 (estimated time of arrival, ETA) 的次序作为最后进场着陆的顺序, 不涉及任何优化, 因此会产生较大的延误。在理论研究中, 将进场问题划归为经典运筹学中的多目标规划问题[1]。在对该问题模型求解的算法方面, 许多专家学者引入了不同的求解方案。2001年, 徐肖豪、黄宝军等人将模糊综合评定方法引入飞机排序[2]。2004年, 徐肖豪等人运用遗传算法解决了双跑道的飞机进场问题[3]。2006年, 李志荣等人将蚁群算法引入飞机排序问题[4]。2008年, 徐肖豪等人运用混合人工鱼群算法求解飞机排序问题[5]。这些算法在求解问题的数量上升时, 仍存在算法效率下降, 收敛速度低, 容易早熟陷入局部最优解等问题。

人工蜂群算法 (artificial bee colony algorithm, ABC) 最早由Karaboga在求解函数数值优化问题时系统的提出[6]。它是一种模仿蜜蜂采蜜行为的群智能多点并行随机搜索优化算法。针对前述求解方法, ABC算法采用多点并行搜索, 因而在问题规模上升时, 仍能保证较好的收敛速度。随机更新搜索域, 在一次循环内最优搜索解附近进行邻域搜索, 依概率接受最优搜索解, 这些方法都保证了算法在求解问题过程中可以跳出局部最优解, 获得较好的全局寻优能力, 避免算法早熟[7]。再者, 该算法不需要了解问题的先验知识, 对初值要求不高, 只对问题优劣作比较, 具有一定的鲁棒性。本文研究了人工蜂群算法在终端区飞机排序中的应用, 并给出相关仿真算例。

1 航班排序模型

对于单跑道条件下, 设有n架航班降落在终端区内, 其集合为

E (i) 为第i架飞机的预计到达时间, S (i) 为第i架飞机的实际到达时间。不考虑飞机提前到达的情况, 则第i架飞机的延误时间为

若不考虑延误的时间成本, 则求解目标即为总延误时间最小。对于单跑道而言, 目标函数为

对于双跑道而言, 目标函数为

式 (4) 中, E1 (i) 和E2 (i) 分别为第i架飞机到达第1和第2条跑道的预计到达时间。

针对前述目标函数, 相应的约束条件主要定义为两类:

出于实际问题本身的约束, 不考虑航班提前到达的情况, 故应有预计到达时间小于实际到达时间, 即

出于航班本身安全性考虑, 飞机之间应满足最小安全间隔, 本文按尾流间隔处理。

2 人工蜂群算法

2.1 基本原理

人工蜂群算法是基于蜜蜂采蜜行为而形成的群智能算法。形成采蜜的群智能行为需要3个基本要素:食物源 (food) ;被雇佣蜜蜂 (employed bee, 其中一部分可能会成为引领蜂) 及未雇佣蜜蜂[unemployed bee, 包括跟随蜂 (on-look bee) 和侦查蜂 (scout bee) ]。

其中, 食物源代表各种可能的解。食物源的价值取决于多种因素, 如食物源距离蜂巢的远近, 食物源本身的丰富程度以及食物源开采的难易程度或危险程度等。在本文中, 考虑简单性, 用量化的收益率来衡量食物源优劣。结合到飞机排序问题中, 食物源就是同一组航班的不同排列次序。

雇佣蜂发现食物源, 并将食物源的具体信息 (包括食物源距蜂巢的距离, 食物的丰富程度等) 通过摇摆舞与其他蜜蜂分享。未雇佣蜜蜂通过雇佣蜂分享的信息, 跟随雇佣蜂采集食物源。当食物源开采殆尽或附近有更好的食物源时, 未雇佣蜜蜂转为侦查开采其他更好的食物源。

基于上述两类蜜蜂, 有3种基本行为模式:搜索食物源, 被食物源招募和放弃食物源。在算法的初始, 蜜蜂的行为是搜索食物源。当有蜜蜂找到收益率高的食物源时, 其余的蜜蜂有可能跟随这只蜜蜂, 被该食物源招募。当某个食物源开采殆尽时, 蜜蜂放弃该食物源。飞机排序问题和蜜蜂采蜜行为对应关系如表1所示。

2.2 角色描述

引领蜂:引领蜂是雇佣蜂的一种, 其数量和食物源相对应。引领蜂具有记忆功能, 会将自己搜索到食物源的相关信息存储起来, 并以一定概率分享给其他蜜蜂。由于分享的概率与食物源的收益率相关。在ABC算法中, 引领蜂对所有食物源进行循环搜索, 循环次数为C (C=1, 2, …, Maxcycle) 。随后, 引领蜂对相应的食物源进行一次邻域搜索, 搜索按公式 (6) 计算:

式 (6) 中, i≠k (k为i邻域的食物源) , k的取值从1到n (n为食物源个数) , j的取值为从1到d (d为食物源的维数, 即解向量的维数) , Φij为[-1, 1]之间的随机数, 用来控制邻域的范围。如果搜索到的食物源的收益率优于从前, 则用新的食物源位置代替原有的食物源位置, 否则按原有的食物源位置不变。所有的引领蜂完成搜索之后, 把食物源的信息传递给跟随蜂。结合到航班排序问题, 每一个食物源就是一种航班序列, 食物源的收益率对应的就是该种航班序列的延误水平。引领蜂的任务就是对不同延误水平的航班序列进行循环搜索, 以期找到一定延误水平下的优选航班序列, 为下一步跟随蜂进行进一步优化做准备。

跟随蜂:跟随蜂是在蜂巢附近等待引领蜂传递食物源信息的蜜蜂。它们会以一定的概率跟随引领蜂去开采相应的食物源。选用概率按公式 (7) 计算。

式 (7) 中, fi为第i个食物源的收益率, n为食物源个数。跟随蜂在选中某一食物源后, 同样进行邻域搜索, 搜索按公式 (6) 计算。邻域搜索完成后, 保留收益率较好的食物源。在航班排序问题中, 跟随蜂是以一定概率接受引领蜂搜索出的一定延误水平的航班序列, 然后在此基础上进行领域搜索, 最后保留延误最小的航班序列作为本次循环的结果。

侦查蜂:侦查蜂是由跟随蜂在产生放弃食物源的行为的情况后由引领蜂转化而成。当某个食物源开采殆尽时, 该食物源对应的引领蜂即转化为侦查蜂, 并同时放弃该处食物源。判断是否产生放弃食物源行为是由参数limit来控制, 它用以记录某处食物源的开采次数, 也即解的更新次数。事实上某个解若经历了limit次循环后没有得到提高, 可以认为在此处陷入了局部最后, 那么这个解应该被放弃, 该处的引领蜂转为侦查蜂, 开辟新的搜索空间。开辟新搜索空间按公式 (8) 计算。

式 (8) 中, sol是更新后的搜索空间, ub为参数上限, lb为参数下限, rand (1, D) 是元素在[0, 1]之间随机取值的D维解向量。对应到航班排序问题, 即可认为某个航班序列在有限次邻域搜索后, 延误水平没有得到改进, 那么放弃该序列。由于排序问题的规模有限, 故每轮循环中认为只有一只侦查蜂。

2.3 算法流程

基于以上原理和角色描述, 可得出ABC算法的流程。

2.4 收敛性能分析

收敛性是算法的重要性能指标, 本文选择了常用的收敛准则。前后迭代点的逼近是否满足一定的精度, 即为

式 (9) 中:ε是足够小的整数。连续运行20次后, 前后迭代点的差值均小于ε, 则认为符合收敛准则, 算法结束。

3 仿真算例分析

3.1 仿真算例

某机场现为双跑道设置, 某时刻有10架飞机准备降落[5]。这十架飞机的航班代码分别为HC0、LC1、HC2、HC3、SC4、HC5、LC6、HC7、HC8、SC9。其中第一个字母代表飞机的类型。根据国际民航组织的规定, 有三种类型的飞机, 分别是重型 (H) 、大型 (L) 和小型 (S) 。相邻的不同类型的飞机之间的最小尾流间隔标准S可以用一个3×3的时间矩阵 (单位为min) 来表示。

其中, 行代表后机的类型, 列代表前机的类型, 依次分别为小型, 中型和重型。每架飞机的延误如公式 (2) 所述。

相应的飞机到达跑道的预计时间ETA由一个3×10的矩阵表示, 第一行表示到达1号跑道的时间, 第二行表示到达2号跑道的时间, 第三行表示相对应飞机的类型。

3.2 仿真结果

预计到达时间为, 1号跑道E1= (11.0, 15.0, 6.0, 6.0, 9.0, 7.0, 15.0, 6.0, 6.0, 9.0) , 2号跑道E2= (10.0, 17.0, 7.0, 7.0, 12.0, 6.0, 17.0, 7.0, 7.0, 12.0) 。从表2中可看出, 总延误时间从FCFS算法得出的12.5 min减少到ABC算法得出的6.5 min, 延误减少了48%。仿真的具体结果如表2至表5所示, 其中表2, 表3为FCFS算法的双跑道仿真结果, 表4, 表5为ABC算法的双跑道仿真结果。

另, 援引文献[6]中的算法性能仿真比较表, 并加入ABC算法进行比较, 结果如表6所示。

3.3 结果分析

从仿真结果中可以得出以下结论:

(1) ABC算法与FCFS算法相比, 在减少延误的方面有较为明显的效果, 但是需要更多的计算时间。其原因在于, FCFS算法不采用任何优化措施, 不改变航班的降落次序, 因此用时较短, 也理所当然的会产生较大的延误。ABC算法是一种优化算法, 在寻优过程中不可避免的需要耗费一些时间, 因此, 算法计算时间多于FCFS, 但延误小于FCFS。

(2) ABC算法于其他智能算法相比, 从计算延误结果和用时两方面均能取得较好结果。

(3) ABC算法虽然在计算用时上有所耗费, 但是依然在可接受的秒这一数量级, 即使算法效率有所下降, 当相比较减少的延误量而言, 这点耗费占的比重并不大。飞机在空中等待, 一方面安全性得不到保障, 另一方面也会造成一定量的经济损失。因此, 从这个角度来看, 以算法的计算用时的损耗来减少飞机的延误, 这是可取的, 说明ABC算法在减少飞机排序延误上是可行的。

4 结论

鉴于以往算法在求解飞机降落排序问题时, 存在算法效率下降, 收敛速度低, 容易早熟陷入局部最优解等问题。本文用人工蜂群算法来求解双跑道模式下飞机降落排序问题, 通过仿真实验对4种算法进行了对比分析。结果显示, 在问题规模不大的前提条件下, 用人工蜂群算法来求解双跑道下飞机排序问题, 可以得到较好的寻优结果, 且算法不易陷入局部最优解。

参考文献

[1] Beasley J E, Krishnamoorthy M, Sharaiha Y M, et al.Scheduling aircraft landings—the static case.Transportation Science, 2000;34 (2) :180—197

[2] 徐肖豪, 黄宝军.终端区飞机排序的模糊综合评定方法研究.航空学报, 2001;22 (3) :259—261

[3] 徐肖豪, 姚源.遗传算法在终端区排序中的应用.交通运输工程学报, 2004;4 (3) :121—126

[4] 李志荣, 张兆宁.基于蚁群算法的航班着陆排序.交通运输工程与信息学报, 2006;4 (2) :66—19

[5] 王飞, 徐肖豪, 张静.终端区飞机排序的混合人工鱼群算法.交通运输工程学报, 2008;8 (3) :68—72

[6] Basturk B, Karaboga D.A powerful and efficient algorithm for numeric function optimization:artificial bee colony (ABC) algorithm.Journal of Global Optimization, 2007;39 (2) :459—471

人工蜂群优化算法 篇7

0-1背包问题是一个典型的组合优化难题, 有着广泛的实际应用背景, 许多优化问题都可以通过一系列背包问题子问题来解决。随着问题规模的增长, 求解背包问题的时间复杂性增长非常快, 从计算复杂性理论来看, 背包问题是个NP完全问题, 在最坏的情况下的时间复杂性为O (2n) 。贪婪算法、遗传算法[1]、蚂蚁算法[2,3]等, 是该问题的求解方法所采用的主要启发式算法, 因此设计新的高效算法来求解背包问题具有重要的实际意义。

人工蜂群算法[4]是一种基于群体智能的随机优化算法, 它是Karaboga于2005年提出的。蜜蜂根据各自的分工进行不同的活动, 人工蜂群算法比遗传算法、粒子群算法具有更好的优化性能。实现蜂群信息的共享和交流, 从而找到问题的最优解。由于人工蜂群算法目前未能有效解决离散及组合优化问题, 所以只能用于求解连续空间的优化问题, 这已成为限制其发展的瓶颈问题。

针对0-1背包问题的特点, 对人工蜂群算法的运算规则进行重新定义, 利用启发式信息, 使算法既具有人工蜂群算法的整体优化特性, 同时在算法中加入贪婪算法这个很有效的局部搜索方法, 又加快了算法的收敛速度。

通过对0-1背包问题测试算例的仿真实验和与其它算法的比较, 表明了本文算法在迭代相同次数的情况下更容易找到最优解, 体现了算法的可行性和高效性。为我们将人工蜂群算法应用到离散问题, 特别是组合优化问题具有一定的启发性, 也为进一步深入研究奠定了基础。

1 0-1背包问题的描述

0-1背包问题的一般提法为:已知n个重量和价值分别为wj>0和cj>0 (j=1, 2…n) 的物品, 背包的容量假设为C>0, 如何选择哪些物品装入背包可使在背包的容量限制之内所装物品的价值最大。引入变量xj, 当物品j被选择装入时, xj=1, 否则, xj=0。则该问题的数学模型为:

2 人工蜂群算法

在人工蜂群算法中, 蜂群由采蜜蜂、观察蜂和侦察蜂三个部分组成, 每个蜜源的位置代表优化问题的一个可能解, 蜜源的收益度 (蜜量) 对应于问题的适应度 (函数值) 。首先, 人工蜂群算法随机产生初始种群, 即N个初始解 (N为采蜜蜂的数目也为蜜源数目) 。每个解xi (i=1, 2, …, N) 为一个D维的向量 (D为搜索空间的维数) 。经过初始化, 采蜜蜂、观察蜂和侦察蜂开始进行循环搜索。采蜜蜂记住自己以前的最优解, 在采蜜源附近邻域搜索, 搜索公式为

式中, k∈{1, 2, …, N}和j∈{1, 2, …, D}是随机选择的下标, 并且k≠i, 准是[-1, 1]上均匀分布的随机数。随着迭代次数的增加, (xij-xkj) 之间的距离缩小, 搜索的空间也缩小, 即搜索的步长缩小, 动态的调整步长有助于算法提高精度, 并最终获得最优解。

采蜜蜂采用贪婪准则, 比较记忆中的最优解和邻域搜索解, 当搜索解优于记忆最优解时, 替换记忆解;反之, 保持不变。所有的采蜜蜂完成搜索过程后, 观察蜂据此按与花蜜量相关的概率选择一个蜜源位置, 将蜜源信息通过舞蹈区与观察蜂共享。蜜量大的采蜜蜂吸引观察蜂的概率大于蜜量小的采蜜蜂。检查新位置的花蜜量, 若新位置没有大的改变, 则保持不变。观察蜂像采蜜蜂那样对记忆中的位置做一定的改变, 若新位置优于记忆中的位置, 则用新位置替换原位置。一个观察蜂选择某个蜜源的概率为:

式中fiti为第i个解的适应值。

在人工蜂群算法中, 还有一个重要的控制参数“limit”, 它用来记录某个解被更新的次数。假定某个解连续经过limit次循环之后没有得到改善, 表明这个解陷入局部最优, 那么这个位置就要被放弃, 与这个解相对应的采蜜蜂也转变为侦察蜂。假设被放弃的解是xi, 则侦察蜂通过下列公式替换xi:

3 求解0-1背包问题的人工蜂群算法

目前人工蜂群算法, 对于离散域上组合优化问题难以解决, 它只是应用于连续域上的数值优化问题, 主要是因为计算公式 (3) 是基于实数域上的四则运算, 公式 (3) 对自然数不满足封闭性, 而离散域上组合优化问题的解通常由自然数表示。

由公式 (1) 、 (2) 所示的数学模型可知, 0-1背包问题是带约束的离散优化问题, 为了使人工蜂群算法能处理离散优化问题, 有必要对人工蜂群算法的运算规则 (3) 进行重新定义。我们采用如下运算规则:

即当xij, xkj相等均为0或1时, x′ij也为0或1, 因为xkj是从群体中随机选取出来的, 且它与xij的取值相同, 则令x′ij等于xij正确的概率应该会大一些;当xij, xkj不相等时, x′ij的取值由f (xi) 和f (xk) 的优劣来决定, 以概率使x′ij=xij, 以概率使x′ij=xkj。在新的运算规则下, 当xij为0-1变量时, 新产生的个体x′ij也为0-1变量, 这使得人工蜂群算法可以对0-1背包问题进行求解。

采用人工蜂群算法求解0-1背包问题时在迭代过程中形成的新个体未必满足约束条件, 因此需要对形成的新个体进行调整, 使用启发式修正算子, 用来保证个体满足约束条件, 在这里我们引入了局部搜索机制—贪婪算法, 同时在保证个体满足约束条件的前提下尽量增加其适应值。

若个体不满足约束条件, 按物品j的价值密度ρj=cj/wj, (j=1, 2, …n) , 由小到大的方向将xj=1变为xj=0, 直到将不满足约束条件的个体变成满足约束条件;若个体满足约束条件, 在保证满足约束条件的前提下, 尽量增加其适应值, 这是对个体质量的改良。按ρj由大到小的方向将xj=0变成xj=1。

4 仿真实验

为了说明算法的效果, 采用VC++为本文算法编写了程序。我们选用文献[5]采用的4个算例来进行测试, 并与文献[5]中的基本郭涛算法和改进的郭涛算法进行对比, 其中改进的郭涛算法也采用了本文使用的贪婪算法。每次试验均进行100次。对于算例1和算例2, 基本郭涛算法和改进的郭涛算法的种群大小为50, 最大进化代数为2000;对于算例3和算例4, 基本郭涛算法和改进的郭涛算法的种群大小为50, 最大进化代数为10000;本文算法对4个算例的种群大小均为20, 最大进化代数均为200。本文算法与基本郭涛算法和改进的郭涛算法的试验结果见表1。

在种群数小于基本郭涛算法和改进的郭涛算法的情况下, 从表1的结果中可以看出, 本文提出的算法, 每次都可以找到问题的最优解, 仍取得了比他们好的求解结果, 表明了本文算法对0-1背包问题的求解具有良好的性能。

5 结论

人工蜂群算法对离散及组合优化问题难以优化, 只是擅长连续空间的优化问题, 是一种基于群体智能的演化算法。本文通过重新定义人工蜂群算法的邻域搜索公式, 使其可以求解0-1整数规划问题。通过4个0-1背包问题的仿真实验, 表明所提算法的可行性和有效性。同时, 本文算法简单易行、方便操作, 可以用来求解许多可以转化为0-1背包问题的组合优化问题。

摘要：提出了一种用于求解0-1背包问题的人工蜂群算法, 详细阐述了该算法求解背包问题的具体操作过程。算法主要使用了两个思想策略:启发式贪婪算法和人工蜂群算法。通过对其它文献中仿真实例的计算和结果对比, 表明该算法对求解0-1背包问题的有效性, 这对人工蜂群算法解决其它离散问题会有很大帮助。

关键词：人工蜂群算法,背包问题,群体智能

参考文献

[1]李娟, 方平, 周明.一种求解背包问题的混合遗传算法[J].南昌航空工业学院学报, 1998, 12 (3) :31-35.

[2]秦玲, 白云, 章春芳等.解0-1背包问题的蚁群算法[J].计算机工程, 2006, 32 (6) :212-214.

[3]熊伟清, 魏平.二进制蚁群进化算法[J].自动化学报, 2007, 33 (3) :259-264.

[4]Karaboga.D.An idea based on honey bee swarm fornumerical optimization[R].Technical Report-TR06, Kayseri:ErciyesUniversity, Engineering Faculty, Computer Engineering Department, 2005.