细菌群体趋药性算法

细菌群体趋药性（Bacterial colony chemotaxis）算法

算法简介

细菌是一种单细胞生物体，是构成地球上各种高级生命体的最简单最基本的形体，尽管简单，但是他们可获知周围环境的信息，并有效的利用这些信息使自己生存下去，朝着对自己有利的环境移动，如营养丰富的区域，而逃避有毒的环境。所谓“趋向性”是指一个细胞对它周围环境的运动反应，它会改变下一步运动的方向和持续时间，细菌通过比较两步不同的环境属性来得到所需要的方向信息，如果这种反应与化学物质的浓度（可以是引诱剂或驱除剂）有关，就叫做趋药性。

细菌趋药性算法就是从以上过程获得灵感的而得到研究提炼出来的优化方法，最早由Bremermann及其同事进行，旨在利用细菌在化学引诱剂环境中的运动行为来进行函数优化，他们的研究表明了细菌在引诱剂环境下的应激机制和梯度下降相类似。这种算法分析了三维环境中的趋药性，并被用于神经网络的训练。另一种与之相类似的方法是引导加速随机搜索技术，这种方法被运用于飞行控制系统的优化和感知器优化。

算法的发展过程

早期细菌趋药性算法的研究是基于Berg、Brown和Dahlquist提出的细菌趋药性微观模型，前者分析了大肠埃希氏菌在氨基酸环境下的趋药性，并且给出了模型参数的实验测量值。后者研究了鼠伤寒沙门氏菌在氨基酸环境下的趋药性，他们都给出了一个数学模型和实验结果来证实他们的模型。Sibvue D.Muller及其同事们在此基础上进步综合，并且结合最新的生物学研究成果提出了细菌趋药性算法（Bacterial Chemotaxis,BC），从国内公开发表的论文看，最先研究该算法的是浙江人学的李威武等人。作为一种新的模拟生物行为的优化算法，它的实现思想及进化机制和传统的进化算法如:遗传算法、模拟退火算法、进化策略、免疫算法等有所不同，Muller的BC算法只依赖于单个细菌的运动行为，它不断地感受它周围的环境变化并且只利用它过去的经验来寻找最优点，BC算法具有较强的简单性、鲁棒性，但基本BC算法的性能只和基本的遗传算法相当，甚至在某些情况下性能还要比一些改进的遗传算法差。然而这种算法包含了细菌趋药性的基本概念，最近的生物发现也提供了更多的细节和模型。 尽管已经发现细菌相互之间存在一种信息共享机制，但对于交流的方式并不是很清楚，所以，在最初的细菌趋药性算法（BC）里一般地把细菌看作单独的个体，不考虑他们之间的相互作用，这种细菌模型与那些群居昆虫的相互作用模型不同（如蚂蚁，蜜蜂，黄蜂或者白蚁），他们的模型被被看作是具有群体智能的系统，具有很强的解决问题的能力。于是，一种新的基于细菌趋药性的扩展生物模型的优化方法被提出，即浙江大学李威武等人研究模拟了细菌个体间的信息传递与共享机制，并在基本BC算法的基础上引入了群体交互概念，从而提出了细菌群体趋药性算法。

算法步骤

1.单个细菌的描述

简单来说,细菌对引诱剂的反应运动遵守如下的假设：

①细菌的运动轨迹是由一系列连续的直线组成,并且由运动方向和移动距离2 个参数决定。

②细菌在进行下一步运动要改变运动方向时,向左转和向右转的概率相同。

③细菌在各段相邻轨迹间的夹角由概率分布来决定。

则单个细菌对应的算法步骤为：

①设定系统参数。

②选择移动方向。

③确定移动距离。

在整个优化过程中，细菌仅利用它上一步或上几步的位置信息来确定下一步的移动。一般认为这是一种随机梯度近似的搜索方法。

2.细菌群体信息交互模式

①寻找更优点坐标的位置。

②细菌向中心坐标移动。

③比较个体与群体移动的结果。

④改进策略。

⑤参数更新。