一种离散细菌菌落优化算法研究

摘要：为了拓宽智能优化算法解决实际问题的能力，提出一种离散的细菌菌落优化算法。首先，设计新的个体编码方式以及进化方式；其次，融合禁忌搜素算法，克服算法易陷入早熟的不足；最后，与其它算法在Taillard标准调度测试问题集上比较实验，验证了算法的有效性。仿真表明，算法能够寻求到问题的最优组合。

关键词：智能优化；离散优化算法；细菌菌落；禁忌搜索

中图分类号：TP312文献标识码：A文章编号文章编号：1672-7800（2013）012-0052-03

作者简介：宋德逻（1987-），男，西南林业大学机械与交通学院硕士研究生，研究方向为智能控制、群集智能优化算法；李明（1977-），男，博士，西南林业大学机械与交通学院副教授，研究方向为智能控制、群集智能优化算法。

0引言

细菌觅食优化算法[1] （bacterial foraging optimization， BFO）作为智能计算家族的一员，是2002年由Passino等人模拟人类大肠杆菌觅食行为提出的。该算法分为趋向性操作、复制操作、迁徙操作三大步骤。随后Abraham等人论证了细菌的繁殖操作有利于提高算法的收敛速度，同时算法还具备构造直观、易于理解、实现方便、收敛速度快等优点。目前细菌觅食优化算法已经成功应用于求解连续函数优化问题如PID控制器参数设计[2]、神经网络权值训练[3]、金融预测[4]等诸多领域。

但是细菌算法在离散域中的应用尚不多见，文中通过设计一种基于工序序列编码转换方案，同时在趋化操作中通过引入自适应步长和差分进化算子，使得无需修改BFO运算规则即可实现对车间作业调度问题寻优。易军等[6]提出了基于变邻域趋化操作实现对车间调度问题寻优的BFO算法。以上两种求解离散域问题的BFO算法，都只是提供一种基于工序的编码方式，并且对BFO趋化步骤进行相应的改进。其本质仍是将离散域中的优化问题转化到连续域中进行求解，并没有直接在离散域中对问题进行求解。由于基本的BFO算法只是模拟了细菌的有限次觅食和趋化过程，个体缺乏记忆能力，使得算法易陷入早熟以及局部最优的危险，同时这类细菌算法并没有模拟细菌生命周期短、繁殖速度快的优点。为此，李明等人通过模拟细菌菌落进化而提出了一种细菌菌落优化算法（Bacterial colony optimization algorithm， BCO）[7]，该算法不仅建立了群体生长繁殖的进化机制，还提出了一种算法自然结束的准则。

但是与其它细菌算法一样，该算法目前还只能解决连续函数优化问题，对于离散问题特别是组合优化问题的研究尚不多见。为此，本文提出一种离散的细菌菌落优化算法（A discrete bacterial colony optimization algorithm，DBCO）。首先，通过提出一种新的编码方式，以及改进BCO算法进化方式，使其能够解决离散优化问题；其次，当算法陷入局部最优时通过融合禁忌搜索方式，跳出局部最优；最后，在Taillard测试问题集[8]中对算法的性能进行测试，验证算法的有效性。

1BCO 算法

细菌菌落优化算法（BCO）是李明等提出的一种模拟细菌菌落生长演化规律的群体智能优化方法。算法首先在解空间中放置单个细菌，通过比较个体以及群体最优的适应值大小选择运动方式，其运动方式有3种：泳动、翻滚、停留；其次，根据细菌年龄更新种群，并且根据细菌繁殖快的特点设置了最大种群规模；最后，算法提出了一种不以迭代次数或精度为结束条件的结束方式，一旦种群中个体全部死亡后，算法自然结束。算法中泳动、翻滚、停留3种进化方式更新原则如下：