冯 帆，王博凯，杨淑莹

（天津理工大学 智能计算及软件新技术重点实验室，天津 300384）

基于细菌觅食优化算法的图像聚类方法研究

冯 帆，王博凯，杨淑莹

（天津理工大学 智能计算及软件新技术重点实验室，天津 300384）

利用细菌觅食优化算法研究图像聚类问题，采用群体智能模式实现问题解的搜索.首先提取图像特征以确定解的编码形式，初始化种群，在此基础上利用细菌觅食优化算法的细菌迁徙算子、繁殖算子和趋化算子实现群体内个体之间的相互合作和竞争，提高了算法的搜索能力，实验证明该算法具有较强的适应性和鲁棒性.

细菌觅食优化算法；群体智能；优化算法

细菌觅食优化算法（Bacterial Foraging Optimization，BFO）是Passino在2002年基于大肠杆菌在人体肠道内的觅食行为提出的一种新型仿生类群体智能算法［1］.与其他进化算法相比，细菌觅食优化算法具有较强的适应性和鲁棒性［2］，其良好的并行性提高了算法的性能和效率，算法简单、灵活，可与其他各种算法相结合产生新的进化优化算法.由于具有群体智能算法的特点以及较强的搜索能力和易跳出局部极小值等优点，细菌觅食优化算法被广泛应用于各种群智能识别方面的问题［3］.本研究将细菌觅食优化算法应用于图像聚类问题，并通过仿真实验检验算法性能.

1 细菌觅食优化算法

大肠杆菌的觅食行为可分为以下几个过程［4］：

（1）寻找可能存在食物源的区域.

（2）通过先验知识判断是否进入该觅食区域.

（3）消耗掉一定量的食物或觅食区域环境变恶劣等不适合生存的条件出现后，细菌死亡或迁移到另一个适合的觅食区域.

细菌觅食优化算法是根据以上3个过程提出的一种仿生随机搜索算法，与其他的群智能算法相同，细菌觅食优化算法在搜索最优解时，首先要对所求问题的解进行编码，然后根据算法中细菌的行为进行信息交流和更新，最终得到最优解.

2 算法的行为算子

在BFO模型中，优化问题的解对应搜索空间中细菌的状态，即优化函数适应值.BFO算法主要依靠自身特有的趋化（Chemo taxis）、复制（Repro－duction）和迁徙（Elimination－dispersal）3种基础算子［5］进行细菌个体位置的更新和群体最优位置的搜索，进而实现种群的进化.

2.1 趋化算子

细菌向有利于自身的环境（食物源）靠近，在算法中表现为细菌位置的改善.设qi（j，k，l）为细菌个体i当前的位置，其中j表示细菌的第j代趋化算子，k表示细菌的第k代复制算子，l表示细菌的第l代迁徙算子，细菌觅食优化算法中细菌的位置按照θi（j＋1，k，l）＝θi（j，k，l）＋C（i）φ（j）进行调整，其中，C（i）表示细菌每次前进的步长，φ（j）表示细菌随机翻滚的方向.

细菌位置更新过程中，每个细菌首先向一个随机的方向前进一个步长，判断其适应度是否得到改善.如果适应度得到改善，就按此方向继续前进，直到适应度不再改善或达到最大的前进次数；如果按此方向前进一个步长后适应度值没有得到改善，就随机向另一个方向前进一个步长，直到每只细菌都完成预定的趋化算子次数后执行复制算子.

2.2 复制算子

适应环境的细菌复制自身在算法中表现为依据适应度值对执行完趋化算子后的种群进行排序，适应度值较低的半数细菌个体死亡，适应度值高的半数细菌个体复制自身，生成新的群体.然后新产生的群体再次循环执行趋化算子和复制算子，直至群体执行完预定的复制算子次数后执行迁徙算子.

2.3 迁徙算子

在环境恶化的情况下，细菌死亡或者移动到另一个有利环境在算法中表现为某些细菌一定概率的死亡并随机产生新位置的细菌.如果种群中的某个个体满足迁徙算子发生的概率，则这个细菌个体死亡，并随机在解空间的任意位置生成一个新的个体.整个种群执行完一次迁徙算子后，细菌再次循环执行趋化算子、复制算子和迁徙算子，直到执行完预定的迁徙算子次数，种群更新并输出最优解，算法结束.

在细菌觅食优化算法的3种行为算子中，趋化算子是BFO算法的核心部分，决定了搜寻食物源时细菌位置的改变方式以及细菌能否找到食物源，对算法的收敛性和优劣具有极其重要的影响.复制算子保证了细菌种群总体优良性能的提高，使群体向最优的方向移动，有利于达到全局最优［6］.迁徙算子产生的新个体与灭亡的个体一般具有不同的位置，即不同的觅食能力，它可对趋化算子产生一定促进作用，因为迁徙操作随机生成的新个体可能更靠近食物源区域，这样更有利于趋化算子跳出局部最优解并寻找到全局最优解.

3 基于细菌觅食优化算法的图像聚类设计

3.1 特征提取

以含有9个手写字母的图像样品为例对基于细菌觅食优化算法的图像聚类方法进行验证，待测样品如图1所示.图1中，字母右上角的数字为每个样品的编号.

图1 待测样品图Fig.1 Samples for clustering

对于模式识别的聚类问题，特征提取是十分关键的重要环节.采用图像处理方法［7］将含有9个样本的待测样品图像进行分割，分别将9个样品所在的外切矩形区域平均分成7×7个矩形子区域，并以每个子区域中黑像素占子区域总像素个数的百分比作为特征值.

3.2 确定解的编码形式

每种聚类方案都对应一个解，所有解均采用十进制编码，向量总长度为9位.首先，随机生成初始解，如（2，3，1，1，2，1，3，3，2，2，1，3），即第3、4、6和11个样品被分到第1类，第1、5、9和10个样品被分到第2类，第2、7、8和12个样品被分到第3类.

3.3 适应度函数的设定

设样品集为X＝｛Xi，i＝1，2，…，n｝，其中Xi为d维（d＝49）特征向量，需要算法求解的问题是找到一个可使类内距离总和达到最小的聚类方案.

式（1）中：Cj表示第j个聚类中心；d（Xi，Cj）为样品到对应聚类中心的距离；Jc为各类样品到对应聚类中心的距离之和.

个体的适应度值为实数，可表示为

由式（2）可知，个体所代表的划分方案的类间距离之和Jc越小，个体的适应度fitness越大，聚类结果越准确.

3.4 细菌觅食优化算法的实现步骤

（1）随机初始化种群，包括种群大小N和聚类数目.对于第i只细菌，先将每个样品随机指派为某一类作为最初的聚类划分，并计算各类的聚类中心作为细菌i的位置编码，计算细菌的适应度值，反复进行生成N只细菌，并记录最优细菌.

（2）外层循环细菌执行迁徙算子.

（3）中层循环细菌执行繁殖算子.

（4）内层循环细菌执行趋化算子，根据式（1）更新细菌个体.

（5）如果没有达到预定的趋化算子次数，则重复执行（4）.

（6）如果没有达到预定的繁殖算子次数，重复执行（3）.

（7）如果没有达到预定的迁徙算子次数，重复执行（2）；如果达到最大迁徙算子次数，则循环结束，更新并输出最优解.

4 仿真实验

利用细菌觅食优化算法得到的聚类方案如图2所示，最优解如表1所示，可以发现相同的数字被归为一类，实现了聚类的预期效果.

图2 最优聚类结果Fig.2 Result of optimal clustering

表1 最优解Tab.1 Optimal solution

5 结论

本研究分析了细菌觅食优化算法的原理和仿生机制，并将其应用于图像聚类问题的求解，仿真实验结果证明基于细菌觅食优化算法的图像聚类方法具有较强的可行性与准确性，为进一步的算法优化研究及其在其他领域的应用奠定了基础.

［1］ MIILER S D，MARCHETTE J，AIRAGHIEL S.Optimization based on bacterial chemotaxis［J］.Transactions Evolutionary Computation，2002，6（1）：17－19.

［2］ 储颖，邵子博，糜华，等.细菌觅食算法在图像压缩中的应用［J］.深圳大学学报：理工版，2008，25（2）：153－157.

［3］ MISHRA S.Bacterial foraging technique－based optimized active power filter for Load Compensation［J］.IEEE Transactions on Power Delivery，2007，22（1）：457－465.

［4］ LI W W，WANG H，ZOU Z J，et al.Function optimization method based on bacterial colony chemotaxis［J］.Journal of Circuit's and System，2005，10（1）：58－63.

［5］ PASSINO K M.Biomimicry of bacterial for aging or distributed optimization and control［J］.Control System Magazine，2002，22（3）：52－67.

［6］ 麦雄发，李玲.混合PSO的快速细菌觅食算法［J］.广西师范学院学报：自然科学版，2010（4）：91－94.

［7］ 杨淑莹.图像模式识别—VC＋＋技术实现［M］.北京：清华大学出版社，2005：17－36.

Research on image cluster based on bacterial foraging optimization algorithm

FENGFan，WANGBo－kai，YANGShu－ying

（Key Laboratory of Intelligence Computing and Novel Software Technology，Tianjin University of Technology，Tianjin 300384，China）

Bacterial foraging optimization algorithm is used for researching image clustering problem.Swarm intelligent model is used for achieving the search for the solution.Firstly，image characteristic is extracted to determine the coding solution form and the population is initialized.Then migrating operator，breeding operator and chemotaxis operator of the bacterial foraging optimization algorithm are employed to realize mutual cooperation and competition among individuals within the group，and the search capability of the algorithm is improved.Finally，the results of experiment show that the proposed algorithm is of strong adaptability and robustness.

bacterial foraging optimization algorithm；swarm intelligence；optimization algorithm

TP311

A

1671－1114（2012）02－0056－03

2012－01－10

国家自然基金资助项目（61001174）；天津市高校发展基金资助项目（20071308）

冯 帆（1987－），男，硕士研究生.

杨淑莹（1964－），女，教授，主要从事计算机仿真、模式识别与智能系统和动态目标跟踪方面的研究.

（责任编校 亢原彬）