细菌觅食算法

细菌觅食算法(Bacterial Foraging Algorithm,BFA)[亦有称为细菌觅食优化算法(Bacterial Foraging Optimization algorithm,BFO||BFOA)]由K.M.Passino于2002年基于Ecoli大肠杆菌在人体肠道内吞噬食物的行为,提出的一种新型仿生类算法。该算法因具有群体智能算法并行搜索、易跳出局部极小值等优点,成为生物启发式计算研究领域的又一热点。

细菌觅食算法模仿大肠杆菌在人体肠道内觅食行为,属于仿生类优化算法。在BFA模型中,优化问题的解对应搜索空间中细菌的状态,即优化函数适应值。BFA算法包括趋化(chemotaxis)、复制(reproduction)和驱散(elimination-dispersal)3个步骤。

①细菌向富养区域聚集的行为称为趋化。在趋化过程中,细菌运动模式包括翻转(tumble)和前进(run||swim)。细菌向任意方向移动单位步长定义为翻转。当细菌完成一次翻转后,若适应值得到改善,将沿同一方向继续移动若干步,直至适应值不再改善,或达到预定的移动步数临界值。此过程定义为前进。

②一旦生命周期结束,即达到临界趋化次数,细菌将进行繁殖。细菌的繁殖过程遵循自然界“优胜劣汰,适者生存”原则。以趋化过程中各细菌适应值累加和为标准,较差的半数细菌死亡,较好的半数细菌分裂成两个子细菌。子细菌将继承母细菌生物特性,具有与母细菌相同的位置及步长。为简化计算,可以规定复制过程中细菌总数保持不变。

③趋化过程可确保细菌的局部搜索能力,复制过程能加快细菌的搜索速度,但对于复杂的优化问题,趋化和复制无法避免细菌陷人局部极小现象发生。BFA引人驱散过程以加强算法全局寻优能力。细菌在完成一定次数的复制后,将以一定概率被驱散到搜索空间中任意位置。



发表评论

You must be logged in to post a comment.