细菌趋药性优化

细菌趋药性优化（通用3篇）

细菌趋药性优化 篇1

摘要：基于细菌群体趋药性(Bacterial Colony Chemotaxis,BCC)算法提出变速菌群趋药性(Gear Bacterial Colony Chemotaxis,GBCC)算法,将其应用于电力系统无功优化。GBCC算法引入带有权重系数的变速公式,使得GBCC算法前期能够较快地收敛于几个最优解的周围,后期能够在最优解周围进行细致搜索,克服了BCC算法易于收敛于局部最优解的缺点。建立基于GBCC算法的无功优化数学模型,给出GBCC算法的具体步骤。通过对IEEE30节点算例的测试,得到GBCC算法在无功优化问题上的收敛速度和优化效果。

关键词：菌群趋药性算法,变速菌群趋药性算法,无功优化,变速思想,收敛性,收敛速度

0 引言

电力系统无功优化是指从电力系统经济优化运行的角度,调整系统中各种无功控制设备,如发电机机端电压、有载调压变压器的分接头、可投切电容器的参数,在满足节点正常功率平衡及各种安全指标的约束下,实现目标函数最小化。它是实现电网经济调度的一种重要手段,对保证电网的电压水平、降低网损、增强系统的稳定性具有重大意义。

近年来,大量的智能优化算法被应用到电力系统无功优化上,如蚁群算法[1]、遗传算法[2]、粒子群算法[3,4]、菌群趋药性算法(BCC)[5,6,7,8]。但这些算法都存在一定的局限性,在实际的应用中得不到较好的结果。本文提出一种新的算法,即变速菌群趋药性算法(Gear Bacterial Colony Chemotaxis,GBCC)。该算法将变速运动的思想引入BCC算法,克服了BCC算法易陷入局部最优解的缺点,能够较快地得到全局最优解。

本文基于GBCC算法,建立了GBCC无功优化模型。通过IEEE30节点测试证明了算法有效性。

1 算法简述

1.1 BCC算法简介

BCC算法前提假设详见文献[5],以下简单介绍下BCC算法步骤。

1)假设细菌的移动速度为常数,取v=1。

2)给定系统参数

3)新的运动方向:新方向向左或向右偏移原来轨迹的夹角均服从高斯概率分布。

4)细菌在新方向上的移动时间τ:具体取值参看文献[4],这里不多介绍。

5)新位置的确定:细菌的移动速度是常数v=1,细菌的新位置

其中:为细菌新位置;为细菌上一时刻的位置;是正则化的新轨线的方向向量;l为新轨线的长度l=τ·v。

6)通过感知其周围同伴确定是否有更好的位置,如果有,它趋向移动到这些拥有较好位置的中心点。第i个细菌移动第k步时中心点由式(4)确定。

其中:为细菌i和j之间的距离。如果存在这个中心点,那么,细菌趋向这中心点运动的距离长度是

rand()为(0,2)之间服从均匀分布的随机值。

这样便得到了细菌的新位置xn′ew。

7)分别计算xnew和xn′ew的函数适应度值,哪个适应度值小细菌下一步就移向哪个新的位置。

1.2 GBCC算法

1.2.1 对BCC算法的三点改进

1)速度更新策略上的改进

BCC算法中假设细菌运动速度是恒定的,这样会使得细菌降低摆脱局部最优的能力,使得算法易于收敛于局部最优解。本文提出变速思想,速度更新公式为

其中:Pbest是细菌自身移动的最好位置;Gbest是菌群的最好位置;C1和C2为大于零的学习因子,分别表示两个优化解得权重;ω是惯性权重系数,调节其大小可以使算法能够较快收敛在几个最优解周围,进行细致搜索,寻找全局最优解。加快了细菌的寻优速度和跳出局部最优的能力。

2)方向决策上的改进

BCC算法假设细菌选择向左或向右运动的概率相同。GBCC算法中细菌下一步的方向由细菌自身最好的位置和细菌群体最好的位置两点共同决定。使得细菌群体中的每一个细菌都向着好的位置移动,加快了细菌的寻优速度。

3)中心点的改进

细菌群体趋药性算法中的群体交互模式,公式(4)、(5)确定细菌移动中心点。在BCC算法中没有很好地利用这一中心点,GBCC作如下改进。

单个细菌运动的位置向中心点移动

其中,rand()在(0,2)间服从均匀分布。

1.2.2 GBCC算法的步骤

(1)初始化细菌群体中各个细菌的位置,给定细菌初始移动速度,设定期望的初始精度εbegin和收敛精度εend。精度更新公式:ε=ε/α,α为大于1的常数。

(2)由公式(1)~(3)确定系统参数。

(3)根据细菌的群体经验,设细菌具有全局感知能力,利用公式(4)计算第i个细菌第k步移动的中心位置。

(4)根据细菌自身经验,确定细菌新位置,假定细菌在每个时间段上的运动是变速的。细菌移动的新位置

其中:是细菌上一步根据自身经验得到的位置;l=τ·v,v由速度更新公式(5)确定。

(5)综合考虑自身经验位置和群体经验位置,由公式(6)来确定细菌新的运动位置。

(6)重复步骤(2)~(5),直到满足精度为止。

2 电力系统无功优化

2.1 无功优化模型建立

目标函数(系统网损最小)

功率约束方程

式中:PGi,QGi分别为发电机节点的有功功率和无功功率出力;PLi,QLi分别为负荷节点的有功和无功功率;Gij,Bij,δij分别为节点之间的导纳、电纳和电压相角差;Qqi为节点i的无功补偿容量。

不等式约束,即控制变量及状态变量约束

其中:控制变量:VG、KT、QC分别为发电机机端电压、有载调压分接头和无功补偿容量;状态变量:VL、QG分别为负荷节点电压、发电机无功出力。

2.2 GBCC算法应用到无功优化的步骤(图1)

a)输入控制变量的维数和上下限值,设定状态变量的限值,初始精度εbegin和最终的精度εend。

b)单个细菌按照个体的经验独立移动,代入潮流方程得到位置。

c)按照整体经验移动,代入潮流方程得到位置。

d)按照公式(6)得到移动的新位置,代入无功优化目标函数,作为下一步位置信息。

e)判断是否达到精度,输出结果。

3 算例验证

为验证GBCC算法的有效性,采用Matlab7.1编程对IEEE-30节点系统进行无功计算,对比BCC算法和GBCC算法在无功优化上的效果。系统参数均为标幺值,电压相角单位是弧度,基准功率为100 MVA。

IEEE-30节点系统包括6台发电机(节电1、2、5、8、11、13,其中1节点为平衡节点,2、5、8、11、13为PV节点)、21条负荷母线及41条支路,有4台可调变压器分布在支路(6-9、6-10、4-12、27-28);有2个并联无功补偿装置补偿点(节点10、24)。

选取细菌个数20,初始精度为10-4,计算结果对比如表1。

由表2可以看出,GBCC算法网损下降比BCC算法多下降2.58个百分点,GBCC算法在时间上要明显少于BCC算法。验证了GBCC算法的有效性。

从图2可以看到,GBCC算法无论在算法的初期还是后期,收敛情况都要强于BCC算法。使得GBCC算法在收敛速度和寻优结果上都有所提高。

由图3可以看出,在电压方面优化前各节点电压的波动范围较大,优化后节点的电压都稳定在1.0附近,使得电压质量明显的改善。有利于电压的稳定及电能质量的提高并降低网损。

4 结论

GBCC算法由于引入了变速思想及速度更新公式,使得算法具有较强的逃离局部最优的能力,并且能够加快搜索全局最优解的速度。由算例可以看出GBCC算法具有高效、快速优化结果好的特点,是解决电力系统无功优化的新途径。

参考文献

[1]李秀卿,王涛,王凯,等.基于蚁群算法和内点法的无功优化混合策略[J].继电器,2008,36(1):22-26.LI Xiu-qing,WANG Tao,WANG Kai,et al.A hybrid strategy based on ACO and IPM for optional reactive power flow[J].Relay,2008,36(1):22-26.

[2]马晋弢,杨以涵.遗传算法在电力系统无功优化中的应用[J].中国电机工程学报,1995,15(5):347-353.MA Jin-tao,YANG Yi-han.Genetic algorithm in reactive power optimization[J].Proceedings of the CSEE,1995,15(5):347-353.

[3]张江维,王翠茹,袁和金,等.基于改进粒子群算法的电力系统无功优化[J].中国电力,2006,39(2):18-22.ZHANG Jiang-wei,WANG Cui-ru,YUAN He-jin,et al.Based on improved particle swarm optimization for reactive power[J].Electric Power,2006,39(2):18-22.

[4]陈建华,李先允,邓东华,等.粒子群优化算法在电力系统中的应用综述[J].继电器,2007,35(23):77-84.CHEN Jian-hua,LI Xian-yun,DENG Dong-hua,et al.A review on application of particle swarm optimization in power system[J].Relay,2007,35(23):77-84.

[5]Muller S D,Airaghi Marchetto S,Koumoutsakos P.Optimization based on bacterial chemotaxis[J].IEEE Transaction of Evolutionary Computation,2002,6(1):16-29.

[6]李威武,王慧,邹志君,等.基于细菌群体趋药性的函数优化方法[J].电路与系统学报,2005(1):58-63.LI Wei-wu,WANG Hui,ZOU Zhi-jun,et al.Function optimization method based on bacterial colony chemotaxis[J].Journal of Circuits and Systems,2005(1):58-63.

[7]魏志连,熊春友,荆易柯,等.基于改进BBC算法的电力系统无功优化研究[J].继电器,2007,35(21):18-21,27.WEI Zhi-lian,XIONG Chun-you,JING Yi-ke,et al.Reactive power optimization in power system based on improved bacterial colony chemotaxis arithmetic[J].Relay,2007,35(21):18-21,27.

[8]赵义术,李磊,王大鹏.基于细菌群体趋药性的电力系统无功优化[J].继电器,2007,35(16):50-54.ZHAO Yi-shu,LI Lei,WANG Da-peng.Power system reactive power optimization based on bacterial colony chemotaxis[J].Relay,2007,35(16):50-54.

细菌趋药性优化 篇2

Internet网络的兴起之后,各式网络服务争相出现,包括各种先进的多媒体业务蓬勃发展。传统的以文字和图片为主的服务已不能满足用户的需要,具有视频和音频的多媒体服务正成为主流。然而,目前的传输网络面临下列两个难题:首先,网络业务对传输时延、时延抖动等参数较为敏感;其次,多媒体业务消耗大量带宽,给现有的网络传输提出新的课题[1,2]。因此,QoS组播路由算法成了当前研究的热门。

学者们近期提出QoS路由的概念,其目的是:在当前网络传输中,寻找满足用户对时间、成、延迟、抖动、故障率等要求的最佳路线[3]。考虑到QoS路由问题是一个NP-C问题,较好的方法是采用进化算法求解。国外文献如Yen[4]提出用遗传算法(GA)求解,Forsati[5]提出用和谐搜索方法,Vijayalakshmi[6]提出采用人工免疫结合GA的方法。Rehab F[7]提出采用离散粒子群(Discrete PSO)与GA相结合的方法求解。

遗憾的是,上述的算法虽然可以较好地解决QoS问题,其本身也存在缺陷[8]。GA运行一定步数后,其向全局最小解的收敛速度过慢;人工免疫模仿人类的免疫系统,但数据存取操作频繁[9];ACA前期收敛较慢[10]。为此,有必要寻找新的性能更好的智能优化算法。

本文介绍一种新的优化算法,细菌趋药性算法(BCO),它的原理如下:细菌觅食过程当中,处于一个类似的化学引诱剂环境中,其运动行为总是最合理。因此BCO算法模拟这个过程,实现函数的优化。另外,最新的证据显示,细菌在引诱剂环境下的应激机制,类似于传统的梯度下降相。由于BCO性能优异,被称为第二代进化算法。

本文采用BCO对QoS组播路由问题进行仿真。实验表明,基于BCO用于QoS组播路由问题, 性能优于各类文献提出的算法。在节点数目较多的情况下,时间仅有其他算法的40%-60%左右。

1 数学模型

建立如下模型:假设网络为G=(V, E),其中V代表节点集合,E代表链路集合,每条链路存在一个三元组,即时延、时延抖动、代价三个QoS参数。不失一般性,假定两节点之间最多仅有一条边。组播会话的源节点S∈V,目的节点集M={m1, m2, …, mN}⊆V-{S},M中每个节点mi称为组成员,N为组成员的个数。

组播树T是G的子图,T中包含N条路径Pi,其根为源节点S,叶为目的节点mi。考虑到链路上的三元组,则组播树T与路径Pi存在下列关系:

$delay({\rm P}{}_i)={\displaystyle \sum _{x\in {\rm P}{}_i}d}elay(x)i=1,2,\cdots ,{\rm N}$ (1)

$delayjitter({\rm P}{}_i)={\displaystyle \sum _{x\in {\rm P}{}_i}d}elayjitter(x)i=1,2,\cdots ,{\rm N}$ (2)

$cost({\rm T})={\displaystyle \sum _{x\in {\rm T}}\cos }t(x)$ (3)

式中x表征对应的属于组播树T或路径Pi的节点与子链路。因此,QoS问题就是如下约束最优化问题。

式中Di表示第i个目的节点的延迟约束,Ji表示第i个目的节点的延迟抖动约束。

2 BCO简介

2.1 原 理

单个细菌在引诱剂环境下的反应运动遵循如下假设:

(1) 细菌的运行轨迹由一系列直线组成,速度、方向和运动时间等3个参数决定了其运行曲线。另外假设其速度为恒值。

(2) 细菌改变运动方向时,向左拐、向右拐的概率相同,均为50%。

(3) 细菌在运动轨迹上的移动时间,相邻轨迹间的夹角,满足给定的概率分布。

(4) 细菌在运动轨迹上的持续时间,满足指数分布,并随迭代步数逐渐减少。

(5) 细菌在运动轨迹上的持续时间,以及各段相邻轨迹间的夹角,独立于之前运动轨迹的方向和时间参数。

2.2 算法伪码

基于上述假设,BCO算法步骤如下[11]:

Step1 假定细菌的移动速度为常数1:

v=1 (7)

Step2 计算细菌在新方向上的移动时间τ,其数值由概率分布决定:

${\rm P}(X=\tau )=\frac{1}{{\rm T}}\exp \left(-\frac{\tau }{{\rm T}}\right)$ (8)

参数T由下式决定:

Step3 计算细菌的新运动方向,它与原轨迹的夹角根据新方向向左或向右偏转分别服从[12]:

${\rm P}(X=\alpha ,v=\mu )=\frac{1}{\sqrt{2\text{π}}\sigma }\exp \left[-\frac{(\alpha -v){}^2}{2\sigma {}^2}\right]$ (10)

${\rm P}(X=\alpha ,v=-\mu )=\frac{1}{\sqrt{2\text{π}}\sigma }\exp \left[-\frac{(\alpha -v){}^2}{2\sigma {}^2}\right]$ (11)

这里,变量X的数学期望μ = E(X)和对应的方差σ = Var(X)1/2[13,14]在fpr/lpr<0条件下为:

μ=62°(1-cosθ) (12)

σ=26°(1-cosθ) (13)

cosθ=exp(-τcτpr) (14)

式中τc为细菌的当前运动轨迹的相关时间,τpr为细菌上一步运动轨迹的持续时间[15];反之,若fpr/lpr≥0,则μ=62°,σ=26°。

Step4 计算细菌在变量空间中新的位置:

xnew=xold+nul (15)

其中xnew为细菌新位置,xold为细菌上一时刻位置,nu是归一化的新轨迹方向向量,l为新轨迹长度。

整个算法中,T0、τc与b为3个需要预先设定的参数,它们与期望的计算精度ε有关:

T0=ε0.3010-1.73 (16)

b=T0(T${}_0^{-1.54}$100.60) (17)

$\tau {}_c=\left(\frac{b}{{\rm T}{}_0}\right){}^{0.31}10{}^{1.16}$ (18)

3 实验与讨论

仿真实验采用随机生成的网络,见图1所示。节点数分别为20,30,40,50,60,分别令距离小于最大距离30%,24%,22%,20%, 18%的两个节点存在链路。源节点设为0号节点,目的节点取总结点数的10%,目的节点号随机产生。节点的延迟在[30ms, 120ms]内均匀分布,延时抖动在[0ms, 10ms]上均匀分布。链路的时延在[0ms, 40ms]上均匀分布,实验抖动在[0ms, 15ms]上均匀分布。费用在[0, 50]上均匀分布。仿真环境采用P4 3.6GHz处理器,2G内存,Matlab7.1。

对比算法采用和谐搜索(HS)[16]与人工免疫遗传算法(AIGA)[6]。实验中各算法的参数设置如下:本文算法中设置T0=0.0047,b=72.144,τc=287.3042。HS与AIGA按照试错法选取最优值。实验分两部分,第一部分观察算法的整体性能。固定解的大小,使这三种算法求解的结果基本达到最优解时停止,然后比较不同算法的运行时间,结果列于表1所示。

从表1可以看出,当节点数较少时,BCO略优;当节点数超过30时,BCO效率有重大改进,明显优于HS和AIGA。若节点数越多,BCO的性能优势越强。当节点数为60时,BCO消耗的时间仅有HS的35%,AIGA的42.5%。

实验第二部分观察算法的内部性能。我们对节点数为20的网络进行优化,图2显示了不同算法每步的优化结果。

从图2可以看出,BCO算法在前10代就已经接近全局最优点,然后在第10代-30代是迅速逼近。而HS与AIGA却会陷入局部最优点,如HS在第40代附近,AIGA在第30代附近,虽然其后跳出了局部最优,但是造成了时间和资源的耗费[17]。

4 结 语

BCO算法克服了传统进化算法的不足[18,19],在QoS组播路由问题中取得较好的效果。今后的进一步研究包括下面几个方面:1) 研究参数改变对BCO的影响,寻找适合BCO用于QoS组播路由的经验;2) 考虑将BCO推广到更多更广泛的领域中去,包括工业检测、信号处理、图像处理、机器人等方面;3) 考虑将BCO与其他优化算法相结合,例如GA、PSO、HSFL、ABC等性能优异的全局优化算法。

细菌趋药性优化 篇3

1)BCC算法计及邻域内群体信息对细菌个体运动的影响,提高了算法的总体收敛速度和求解效率,然而当邻域内群体信息优于个体自身的选择时,原有的个体信息将会被放弃,转而向邻域最优解靠拢。如果邻域最优解是局部最优解,那算法最终可能局部收敛。

2)如果某一细菌在算法初期陷入局部最优,而不幸的是该细菌又是群体中的最优个体,那它极有可能给其它细菌提供错误信息(Wrong Info),将其它细菌引入局部最优区域,从而使其它细菌错过到达全局最优的机会。

综合上述两点,影响算法收敛性的主要原因有:1)原本有可能到达全局最优的细菌个体被其它细菌误导,从而放弃原有的轨迹信息(群体对个体的影响);2)最先到达局部最优的细菌个体误导其它细菌,使其陷入局部最优(个体对群体的影响)。

多Agent系统(Multi-agent System,MAS)的概念起源于人工智能领域,是分布式人工智能的主要方向之一。Agent是对过程运行中的决策或控制任务进行抽象而得到的一种具有主动行为能力的实体,它可以利用数学计算或规则推理完成特定操作任务,并通过消息机制与过程对象及其它Agent交互以完成信息传递与协调[6,7,8]。

针对BCC算法的上述缺陷,本文结合多Agent系统的基本特征,构造一种全新算法———基于多Agent的细菌群体趋药性(MABCC)算法。

1 MABCC算法

MABCC(Multi-Agent Bacterial Colony Chemotaxis)算法是结合BCC算法和MAS的主要特征构造的一种全新算法,通过每个细菌Agent(Bacterial Agent:BA)相互之间的竞争与协作,使其能够更精确地收敛到全局最优解。

1.1 Agent意图的定义

在MABCC算法中,假设任意一个Agent为i,它相当于BCC算法中的一个细菌个体,它有一个被优化问题所决定的目标值。假设该优化问题是求取目标最小值,Agent i的目标就是在满足约束条件下尽可能减小其目标值。为了实现该目的,Agent根据自身所处的环境做出相应的动作,最大化地减小其目标值。

1.2 Agent环境的定义

当菌群被定义时,每个BA“居住”的环境属性就固定了,按照以下特性进行分类:

1)可知性:每个BA可以了解环境的全部状态。即菌群中所有BA的位置信息和目标值信息都是有效可知的。

2)确定性:下一步环境的状态是由当前状态和BA选择的动作来完全决定。BA不需要担心在一个可知的,确定的环境里的不确定问题。即一旦BA确定了下一步的位置信息,其目标值信息是确定的。

3)阶段性:BA只考虑下一步的动作和目标,不需要提前考虑将来。在这种环境下,BA可能被“当前利益”所诱导,而放弃了自身可能到达全局最优的机会。

1.3 Agent愿望扩展

在BCC算法中,BA由于重视“当前利益”而放弃“长远利益”,使得算法最终可能求得的是局部最优解而非全局最优解。MABCC算法给予BA更多的“自私性”,使得每个BA在决策中受周围环境的影响被限制在一定范围内。

MABCC假设:

1)在菌群中,虽然每个BA的愿望是一致的,但它们之间存在竞争。每个BA都希望自己可以最先找到最优解。如果过分“相信”当前处于群体最优的BA,先于其找到最优解的概率就比较小。

2)虽然BA的愿望是找到全局最优解,但更希望的是通过自身轨迹信息而非完全依靠环境信息。根据优先级,把BA的愿望扩展为:

{菌群找到全局最优解;自身最先找到全局最优解;尽量依靠自身轨迹信息}

愿望扩展后的BA不易被菌群误导,放弃原有的轨迹信息,从而保证算法最终尽可能地全局收敛。

1.4 Agent动作策略

BA的动作策略分为三个步骤:自立、协作与投机。

1)自立(Self-supporting)

对处在移动步数k的BAi,根据它自己记忆的上几步的位置信息按BC算法[3]确定在步数k+1时的新位置x軆'i,k+1。

2)协作(Cooperation)

BA的协作包含竞争,属于协作与自私相混合型[6]。

Step1:对处在移动步数k的BAi,感知其周围有更好位置的其它BA,对其进行筛选,选择协作者。筛选的原则为:假设菌群中当前位置最好的BA已陷入最优区域(局部或全局),将其看作是潜在的竞争对手,如果与其合作,能够到达或最早到达全局最优的概率就会变小,把其从协作者名单中删除。

Step2:确定经过筛选后的协作者BA的中心点Center(x軆i,k)和一个假定的朝这个中心方向移动的长度rand()·dis(x軆i,k,Center(x軆i,k)),确定位置x軆"i,k+1。

Step3:尽量保留自身轨迹信息。在算法迭代过程中综合权衡自身轨迹信息和群体优良信息以得到一个新的运动方向。引入惯性因子ω,k+1步时的新位置为:

式(1)中,ω可以根据经验设定一个[0,1]之间的数。在算法初期,BA应该更多地依据自身轨迹进行寻优;而在算法后期,由于菌群已聚集在某一特定的区域内,此时应该更多地依靠协作来进行寻优。因此,ω应该遵循先大后小的原则,参照文献[9],可以根据式(2)进行动态调节。

式中,N为当前迭代次数,Niter为算法总迭代次数。

Step4:计算位置的函数值,如果,那么BA就在k+1步移向点,否则就移向点

3)投机(Speculation)

每个BA的愿望之一就是自身先找到最优解,如果在当前位置BA依靠自身轨迹信息和群体优良信息都无法找到更优的位置(即陷入局部最优区域),此BA到了“穷途末路”的境地。那么,最先找到最优解的“愿望”就无法达成。投机策略,即将竞争对手的信息“占为己用”,朝着上次移动后最优BA的方向随机移动一定距离,使其更接近“最优解”。

虽然投机策略有可能将BA误导入新的局部最优区域,但使用此策略的BA自身已失去了找到全局最优的机会。因此,使用投机策略不会对菌群的寻优性能造成影响,反而加大了菌群找到全局最优的概率。

通过BA的自立、协作与投机策略,MABCC算法可以克服BCC算法的缺陷:一方面BA由于权衡了自身轨迹信息和群体优良信息而进行策略动作,不易被菌群误导陷入局部最优;另一方面最先达到最优(局部或全局)的BA由于被认定为竞争对手,其它BA不愿与其协作,因此避免了其将菌群误导入局部最优区域。

1.5 MABCC算法流程

MABCC算法的计算流程如图1所示。为了避免局部收敛,算法将群体交互对个体的作用弱化,牺牲了收敛速度。

2 算例分析

为了显示MABCC算法解决优化问题的能力,使用几个典型的算例进行仿真试验,并与BCC算法相对比。

2.1 Rastrigin函数

Rastrigin函数F(x,y)=20+(x2-10cos(2πx)+y2-10cos(2πy)),(x,y)∈[-600,600]。其空间图如图2所示。该函数有全局最小点,同时在区间范围内有大量的局部最小点。

采用BCC算法和MABCC算法分别对该函数进行优化:设置细菌的初始位置设置在(50,-50)。算法参数εbegin=2,εend=10-10,α=1.25,ωmax=0.9,ωmin=0.2。细菌数目为20,移动步数为100步。两种算法的优化结果见表1。

图3和图4分别给出了BCC算法和MABCC算法的菌群在移动结束后的分布情况。从图中可以看出,BCC算法中的菌群收敛精度为10-4,而MABCC算法中的菌群收敛精度为10-8,明显优于BCC算法。

2.2 Schaffer's f'6函数

Schaffer's f'6函数。其空间图如图5所示。该函数有一个全局最小点F(0,0)=-1,在全局最小点的周围,无限多个局部最小点(其函数值约为-0.99028)将全局最小点包围。Schaffer's f6函数的强烈震荡性质和全局最小点被无数多局部最小点环绕的特性使得它的优化十分困难[10]。

对于Schaffer's f6函数的优化,采用BCC算法和MABCC算法分别以相同的参数进行优化:细菌的初始位置设置在(100,-100)。算法参数εbegin=2,εend=10-10,α=1.25,ωmax=0.9,ωmin=0.2。细菌数目为20,移动步数为200步。随机运行100次,统计100次随机实验的优化结果。表2显示了两种算法的寻优性能。

图6显示了两种算法的寻优曲线。从图中可以看出,BCC算法由于强大的群交互能力而迅速收敛,菌群在大约20步前就可以趋近最优值。但是由于过度依赖群交互,BCC算法很容易陷入局部最优区域,从而无法找到全局最优解。而MABCC算法弱化了群交互,避免了菌群对BA的过度误导,虽然牺牲了一定的收敛速度(大约100步左右收敛),但找到全局最优解的性能要比BCC算法更加出色。

MABCC算法与BCC算法相比,虽然收敛速度有所降低,但是比BCC算法有更好的全局搜索能力。Schaffer's f6函数是一个著名的难以求解的问题,对该函数的试验也证明了MABCC算法的有效性。

3 结束语

MABCC算法引入多Agent系统的竞争与协作机制,通过BA的自立、协作与投机策略,克服了BCC算法由于过分依赖群体信息而容易陷入局部最优的缺陷。通过算例仿真,验证了MABCC算法的有效性及高效性,其收敛精度也令人满意。虽然MABCC算法牺牲了一定的收敛速度,但随着计算机运行速度的飞速发展,速度要求已远远不及精度要求。因此作为一种新的尝试,MABCC算法对求解较复杂的优化问题具有一定的启发意义。

表1 Rastrigin函数优化结果比较(上接第1606页)

摘要：针对细菌群体趋药性(Bacterial Colony Chemotaxis,BCC)算法由于过度依赖群体交互而容易陷入局部最优解的缺陷,结合多Agent系统(Multi-Agent System,MAS)的主要特征构造一种全新算法——基于多Agent的细菌群体趋药性(MABCC)算法。该算法通过每个细菌Agent相互之间的竞争与协作,弱化其对群体信息的依赖,使其能够更精确地收敛到全局最优解。对不同函数优化试例的仿真表明该算法比BCC算法有更好的全局寻优性能。

关键词：细菌群体趋药性算法,多Agent系统,竞争,协作,全局最优

参考文献

[1]Li Wei-wu,Wang Hui,Zou Zhi-jun,et al.Function Optimization Method Based on bac-terial Colony Chemotaxis[J].Journal of Circuits and System,2005,10(1):58-63.

[2]曹黎侠,张建科.细菌趋药性算法理论及应用研究进展[J].计算机工程与应用,2006(1):44-46.

[3]Sibyue D M,Jarno M,Stefane A,et a1.Optimization based on bacterial chemotaxis[J].IEEE Transactions on Evolutionary Computation,2002,6(1):17-19.

[4]Berg H C,Brown D A.Chemotaxis in escherichia coli analyzed by three-dimensional tracking[J].Nature,2002(239):500-504.

[5]Miiller S,Airaghi S,Marcheio J,et a1.Optimization algorithms based on a model of bacterial chemotaxis[C].Proc 6th Int Conj Simulationof Adoptive Becharior:Form Animals to Ammats,SAB 2000,2000:375-384.

[6]何炎祥,陈莘萌.Agent和多Agent系统的设计和应用[M].武汉:武汉大学出版社,2001.

[7]夏定纯,徐涛.人工智能技术与方法[M].武汉:华中科技大学出版社,2004.

[8]石纯一,张伟,徐晋晖,等.多Agent系统引论[M].北京:电子工业出版社,2003.

[9]刘霞,刘金凤,赵文彬,等.抑制局部最优的粒子群算法[J].大庆石油学院学报,2007,31(6):101-104.