细菌觅食优化算法求解物流网络问题

连续优化问题的细菌觅食改进算法戴秋萍;马良;郗莹【摘要】为更有效解决连续优化问题,提出了一种基于群体搜索的群智能优化算法——细菌觅食算法.该算法模拟了细菌觅食全过程,并对细菌个体的初始化、趋化操作中的搜索步长和搜索方向进行了改进.改进后的算法有效避免了算法陷入局部最优,而算法中采用的搜索步长,进一步提高了优化的收敛速度.经大量实验仿真表明,细菌觅食算法能够有效地求解连续优化问题.将仿真结果与其它算法对比,证明了细菌觅食算法的搜索质量优于其它算法.【期刊名称】《上海理工大学学报》【年(卷),期】2013(035)002【总页数】4页(P103-106)【关键词】连续优化问题;细菌觅食;局部优化【作者】戴秋萍;马良;郗莹【作者单位】上海理工大学管理学院,上海200093;上海理工大学管理学院,上海200093;上海理工大学管理学院,上海200093【正文语种】中文【中图分类】N945.15经典的优化算法在函数优化问题中，常常要求函数连续可微，因此在求解过程中需要借助一些基于梯度信息的数学技巧，并且在接近最优解时容易出现锯齿现象，造成收敛速度缓慢［1］.20世纪50年代中期，人们从生物进化的机理中得到启发，创立了仿生学，并提出了许多解决复杂优化问题的智能方法，如神经网络、遗传算法［2］、进化策略、蚂蚁算法［3］等，这些方法在连续函数优化问题中取得了较好的结果.本文提出了一种新的智能优化算法——细菌觅食算法对连续函数优化问题进行求解.细菌觅食算法（bacterial foraging optimization，BFO）是由Passino［4］于2002年提出来的一种仿生随机搜索算法，该算法具有群体智能性，并可进行并行搜索.目前，BFO已被用于车间调度问题、自适应控制领域、噪声干扰下的谐波估计问题和PID（proportional integral derivative）控制器的设计等方面，并获得了较好的效果［5-6］.本文对细菌觅食算法操作步骤进行了改进，有效地改善了该算法极易陷入局部最优的缺点，使其在解决复杂连续优化问题时，全局搜索能力大大增强.另外，通过大量仿真实验验证了该算法的有效性.细菌觅食算法是基于大肠杆菌在觅食过程中体现出来的智能行为的一种新型仿生优化算法，其具有群体智能性、并行性等特点.细菌觅食算法包括趋化操作（chemotaxis）、复制操作（reproduction）和迁徙（elimination and dispersal）操作.这3种操作方式是模仿细菌觅食的趋向行为、复制行为和迁移行为的抽象［7-8］.a.趋化操作大肠杆菌在寻找食物源的过程中，其运动是通过表层的鞭毛实现的.当鞭毛全部逆时针摆动时，大肠杆菌将会向前行；当鞭毛全部顺时针摆动时，它会减速至停止.鞭毛的摆动对应着细菌个体对当前适应值的判断，并决定是否对其位置进行调整和确定调整的方向和力度.趋化操作模拟了大肠杆菌的这个运动过程，包括游动和翻转两个操作.设pi（j，k，l）表示细菌个体i的当前位置，j表示第j次趋化行为，k表示第k 次复制行为，l表示第l次迁徙行为.则其中，φ（j）表示游动的方向；C（i）表示前进步长.b.复制操作设群体规模为S，在完成设定次数的趋向操作之后，将群体中的个体按照其适应度值进行排序，将排在后面S／2的个体删除，剩下的个体进行自我复制，保证群体规模的稳定性.c.迁徙操作迁徙操作按照预先设定的一个概率发生，若某一个个体满足迁徙操作发生的条件，那么即将此个体删除，并生成一个新的个体代替.相当于将原来个体重新分配到一个新的位置，即以一定的概率将个体随机驱散到搜索空间.2.1 初始化操作改进在细菌觅食算法中，细菌种群的大小直接影响细菌寻求最优解的能力.种群数量越大，其初始覆盖区域越大，靠近最优解的概率就越大，能避免算法陷入局部极值，但同时增加了算法的计算量.因此，本文将初始化操作进行了改进.改进后，在细菌规模较小的情况下，能比较有效地改善初始化后细菌群体的覆盖范围（见图1、图2）.确定群体规模S之后，将群体搜索的空间分成S个区域，每个细菌个体的初始位置为S个区域的中心点，随即细菌将在各自区域内搜索.由图1可知，细菌个体随机生成时，菌群可能在搜索空间内分布不均，在搜索最优解过程中，极有可能在限定的游动步长内无法找到最优解而陷入局部最优.2.2 趋化操作改进细菌觅食算法中，趋化操作是细菌觅食过程中最重要的一个步骤.基本细菌觅食算法在进行趋化操作时，细菌个体是根据历史信息按固定步长朝着食物源方向游动.在解决连续函数优化问题，尤其是多峰函数优化问题时，传统的操作方式易使得细菌个体错过最优解，本文对趋化搜索方式进行了改进.将细菌个体所在区域切分为n×n块，每个细菌在进行翻转操作时，仅在细菌周围的8个方向中随机选取，游动过程中每游动一次前进步长缩短为原来步长的0.8倍，C（i）=0.8C（i）.当细菌个体游动次数并未达到设定游动次数时，细菌将再进行一次翻转操作.趋化操作步骤：a.确定细菌个体i，确定游动方向φ（j）.b.细菌游动pi（j+1，k，l）=pi（j，k，l）+ C（i）φ（j）.c.判断当前位置是否更优，是则个体i被新个体取代，继续步骤b，步长C（i）变为0.8C（i）.d.判断是否达到设定游动次数，未达到转步骤a，达到游动次数细菌个体i趋化操作结束.2.3 复制操作改进细菌觅食过程中，一段时间后，细菌会根据个体位置的适应度值进行优劣排序.排在后面的S／2个细菌死亡，而排在前面的S／2个细菌进行自我复制，随即细菌往较小范围聚集.在求解多峰连续优化问题时，菌群极有可能跳过最优解而陷入局部最优.本算法将细菌个体首先随机与邻域周围的一个细菌进行交叉变异，变异后的细菌个体适应度值若优于原个体，原个体将被替代.通过一次改进后的复制操作后，整个菌群完成一次更新，菌群规模不变，每个细菌个体仅在各自区域及邻域内进行变异和适应度值比较，从而有效地防止了菌群向较小范围内聚集.改进后的复制操作不再只是觅食能力强的细菌个体单纯的自我繁殖过程，整个菌群群体都朝着更优的方向游动，提高了菌群整体的寻优能力.改进后复制操作过程如图3所示.前述细菌觅食算法采用Matlab 7予以实现，在PC系列机的Windows 7系统环境下运行通过.本文通过大量实例验证了此改进算法的有效性，下面给出4个算例及求解结果分析（见图4～7，图5～7见下页）.算法相关参数设定：细菌规模为225，趋向操作数为10，复制操作数为4，迁徙操作数为2.算例1由函数示意图可知，该函数最优解处于中间区域，周围有很多局部极值围绕着最优解，用传统的细菌觅食算法陷入局部最优的可能性非常大.元胞蚁群算法、混沌算法均可得到最优解1，LINGO软件得到的最优解为0.646 848 8，Matlab优化工具得到的结果为0.990 3.算例2该问题的最优解被最差解包围，4个局部值点为（-5.12，5.12）、（-5.12，-5.12）、（5.12，5.12）、（5.12，-5.12），函数值均为2 748.78.运行改进后的细菌觅食算法求解该问题能够有效地获得最优解.算例3该函数在（1，1）处有最小值0，且在最优解附近存在病态，用常规方法容易陷入局部最优，难以搜索到最优解.算例4该算例可看出是典型的多峰函数，运用传统算法求解最优解相当困难.遗传算法目前所求最优解为38.827 533，运行LINGO软件与Matlab得到的解均小于38. 表1为该算法求解上述函数运行30次后的结果分析.其中平均偏差率为算法运行30次解的平均值与最优解的比值.首先对细菌初始化操作进行了改进，改变了传统的细菌觅食算法中的初始方式，使得菌群规模较小的情况下，能有较大的覆盖面.此外，本算法对细菌个体的搜索方式也进行了适当改进，增强了个体的局部搜索能力.为防止菌群在复制操作中过快地向小范围聚集而陷入局部最优，菌群进行变异性复制，不仅保证了菌群整体朝更优方向游动，同时大大提高了此算法的全局搜索能力.通过实验表明，改进后的细菌觅食算法在求解连续优化问题时，稳定性好，能够快速有效地找到最优解.通过与其它算法相比可得出以下结论：a.改进后的细菌觅食算法改进了传统细菌觅食算法的缺点，有效地改善了传统算法的收敛速度和全局寻优能力，所获最优解质量得到改善.b.改进后的细菌觅食算法能够有效解决连续优化问题，为连续优化问题提供一种新的解决方法.【相关文献】［1］马良，朱刚，宁爱兵.蚁群优化算法［M］.北京：科学出版社，2008.［2］张惠珍，马良.基于变尺度混沌优化策略的混合遗传算法及在神经网络中的应用［J］.上海理工大学学报，2007，29（3）：215-219.［3］邱模杰，马良.约束平面选址问题的蚂蚁算法［J］.上海理工大学学报，2000，22（9）：61-62.［4］ Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine，2002，22（3）：52-67.［5］梁艳春，吴春国，时小虎，等.群体智能优化算法理论与应用［M］.北京：科学出版社，2009.［6］张娜.细菌觅食优化算法求解车间调度问题的研究［D］.吉林：吉林大学，2007.［7］胡海波，黄友锐.混合粒子群算法优化分数阶P／D控制参数研究［J］.计算机应用，2009，29（9）：2483 -2486.［8］李亚楠.菌群优化算法的研究［D］.哈尔滨：哈尔滨工业大学，2009.。

基于改进细菌觅食优化算法的输电网规划王瑞;王起琦;段柯均;赵丹【摘要】针对大规模输电网规划中细菌觅食算法(BFO)容易陷入局部最优、搜索精度和后期收敛速度明显下降的问题,使用改进细菌觅食算法(IBFO)建立了基于线路建设费用、网损费用以及正常运行时的过负荷惩罚费用最低的输电网规划模型,通过对IEEE-18节点和巴西南部46节点系统的计算,验证了IBFO在求解大规模输电网规划问题时收敛更快,更易寻得全局最优解.【期刊名称】《吉林电力》【年(卷),期】2015(043)002【总页数】4页(P29-32)【关键词】输电网规划;细菌觅食优化(BFO)算法;改进细菌觅食优化(IBFO)算法;禁忌表;趋向性操作;迁徙操作【作者】王瑞;王起琦;段柯均;赵丹【作者单位】东北电力大学,吉林吉林132012;国网营口供电公司,辽宁营口115000;东北电力大学,吉林吉林132012;东北电力大学,吉林吉林132012【正文语种】中文【中图分类】TM715输电网规划问题在数学上是一个带有大量约束条件的非线性组合优化问题。

近年来，由于现代启发式算法具有实现简单，不受目标函数的形态约束，能够实现多维有效搜索等特点，在输电网规划问题求解中得到了快速的发展，如差分进化算法［1］、人工鱼群算法［2］、粒子群算法［3］、蚁群算法等［4］，每种方法各有其利弊，但是这些方法拓展了输电网规划求解的思路，有利于快速精确获得最优规划方案。

细菌觅食优化（BFO）算法［5］是近年来提出的一种模拟细菌觅食行为的仿生进化算法。

在求解大规模输电网规划问题时，该算法容易陷入局部最优，搜索精度和后期收敛速度明显下降。

利用禁忌表和能量因子分别针对算法中的趋向性操作和迁徙操作进行改进，从而增强算法的全局搜索能力及跳出局部极值的能力，减少了逃逸现象的发生并提高算法的收敛速度和搜索精度，使改进细菌觅食优化算法（IBFO）适用于大规模输电网规划问题的求解。

本文使用IBFO 算法，在已有的负荷预测和电源规划的基础上，根据已经存在的网络结构和已知的待选线路，从而得出满足运行要求的经济性最佳的网络方案，其规划后的结果使方案投资费用、运行费用以及正常运行时的过负荷费用三项之和最小。

改进的细菌觅食优化算法求解0-1背包问题杜明煜;雷秀娟【摘要】As a new intelligent optimization algorithm,Bacteria Foraging Optimization ( BFO) algorithm is generally used to solve contin-uous problems. In order to solve discrete problems,an improved BFO algorithm was proposed in this paper,which adopted linearly de-creasing thoughts and random steps of the bacterial tumble instead of fixed steps and random direction to promote chemotaxis solution, and applied to 0-1 knapsack problem. By contrast with Genetic Algorithms (GA),Discrete Particle Swarm Optimization (DPSO) and basic BFO algorithm on both small-scale and large-scale 0-1 knapsack problems,the simulation results indicate that the improved BFO algorithm performs better with high search capability.%细菌觅食优化算法作为一种新兴的智能优化算法，一般用来解决连续域的问题。

为了解决离散域问题，提出了一种改进的细菌觅食优化算法。

采用线性递减的思想和随机的游动长度代替固定步长和随机游动方向，改进了趋向性操作方案，并将其应用于解决0-1背包问题。

细菌网络优化算法研究及其应用随着科技的发展，在许多领域中，优化问题已经成为了一种关键性的挑战。

而针对这些优化问题，开发出结构简单且有效的算法显得尤为重要。

本文将介绍一种相对新颖的优化算法，即细菌网络优化算法，并探讨它在实际应用中的表现。

一、细菌网络优化算法的基本原理细菌网络优化算法（Bacterial Foraging Optimization，BFO）是一种基于生物群体行为的优化算法。

算法的核心思想来自于细菌自身寻找食物的行为。

细菌寻找食物的过程中，会披着足够的细胞浓度分布，在食物源附近细菌的浓度会越来越高，但是又不会过度聚集，避免唾液中穴位的堵塞。

在这个过程中，每个细菌既会遵循自己的方向，又会受到周围细菌的相互作用的影响。

在BFO算法中，将每个细菌所在的位置看作是定义域中的一个可行解。

每个细菌通过移动来搜寻最优解。

移动的方向和距离由细菌所处环境状况和其感知到的周围细菌状况决定。

每一步移动后，细菌会评估自己所处位置是否比之前更好，如果是，则会保留此位置；如果不是，则会再次移动。

细菌的移动既受到灵敏度因素的影响，又会受到化学变量因素的影响，来达到不断寻找最优解的目的。

细菌网络优化算法和其他优化算法有一些相同的特点。

例如，BFO算法也可以根据对象函数进行优化。

不过，BFO算法具有一些独特的性质，例如可以自适应选择存活的细菌、在算法的早期阶段尽可能增加多样性，等等。

二、细菌网络优化算法的应用BFO是一种灵活而有效的优化算法，应用广泛。

下面我们就具体探讨该算法在实际问题中的表现。

1. 硬件设计中的应用在硬件设计中，通过BFO算法，可以实现诸如液晶显示器像素点优化、射频集成电路元器件布局、滤波器设计和集成传感器组件的优化等任务。

在这种情况下，BFO算法往往具有明显的优势，因为使用传统的经典优化算法，如粒子群算法或模拟退火算法，往往需要使用较复杂的算法或手动调整参数来达到最优结果。

2. 机器学习中的应用机器学习中常见的优化问题是选择权值。

针对库区分配优化问题的改进型细菌觅食算法杨文强;邓丽;牛群;费敏锐【摘要】针对自动化立体仓库库区分配优化问题建立了堆垛机平均运行时间模型,为求出其最优解,提出一种改进型细菌觅食算法.在求最优解的过程中,根据当前全局最优解和局部最优解,分阶段对趋化步长进行自适应调整;同时根据细菌个体对种群多样性的贡献率对其迁移概率进行设定,不但提高了收敛速度,而且保证了寻优的全局性.结合工业现场实例与原始细菌觅食算法和遗传算法进行了仿真对比,结果表明所提算法在解的质量及收敛速度上都具有明显的优势.【期刊名称】《计算机集成制造系统》【年(卷),期】2014(020)007【总页数】7页(P1684-1690)【关键词】自动化立体仓库;细菌觅食算法;步长自适应调节;种群多样性【作者】杨文强;邓丽;牛群;费敏锐【作者单位】上海大学机电工程与自动化学院,上海200072;上海市电站自动化技术重点实验室,上海200072;上海大学机电工程与自动化学院,上海200072;上海市电站自动化技术重点实验室,上海200072;上海大学机电工程与自动化学院,上海200072;上海市电站自动化技术重点实验室,上海200072;上海大学机电工程与自动化学院,上海200072;上海市电站自动化技术重点实验室,上海200072【正文语种】中文【中图分类】TP3910 引言随着成本的不断降低，自动化立体仓库在加工制造领域得到了普遍应用。

然而，在生产过程中，如果不对其进行合理的分区，不仅会降低仓库的利用率，还会降低生产效率［1-2］。

目前关于立体仓库库区分配优化方面的研究较少，Heragu等［3］按功能把仓库分为备用存储区、订单存放区和直接发货区，同时建立了仓库材料费用数学模型，并通过一种启发式算法对各功能区尺寸进行优化求解；Jane［4］以平衡堆垛机之间的负载为优化目标，对存储区位分配进行了研究；Moon等［5］在产品数量变化时，从随机存储、分类存储两个方面对库区再分配策略进行了研究；Petersen等［6］对分类存储进行研究，得出在存储与检索效率上，分类存储相对于随机存储和基于体积的存储具有一定优势的结论；肖建等［7］根据需求相关性以及李英德等［8］根据货物间的相关性，对货物的货位区进行分配优化，以使拣货时间最短，然而他们定义的相关性有很大的主观性，不具有通用性；杨朋等［9］以最小化单位指令周期的行程时间为目标，对货区分配优化问题进行了研究。

细菌觅食优化算法的研究与改进细菌觅食优化算法的研究与改进随着计算机科学和生物学的不断发展，人们开始探索将生物现象与计算机算法相结合，以寻找新的问题解决方法。

在这个过程中，细菌觅食优化算法应运而生。

细菌觅食优化算法模拟了细菌在寻找食物的过程，通过模仿细菌的行为，通过进化算法来优化问题的解决方案。

本文将探索细菌觅食优化算法的研究与改进，以及其在实际问题中的应用。

一、细菌觅食优化算法的基本原理细菌觅食优化算法灵感来源于真实世界中细菌的群体觅食行为。

细菌觅食过程主要包括趋化运动、荧光成像和滞留趋化三个阶段。

在趋化运动阶段，细菌通过运动来寻找食物。

荧光成像阶段主要是细菌根据环境中剩余食物的浓度情况进行判断，以便向食物浓度高的区域聚集。

在滞留趋化阶段，细菌会在食物附近停留，直到找到食物。

细菌觅食优化算法主要包括三个步骤：初始化种群、选择操作和更新种群。

首先，根据问题的维度和范围，初始化一定数量的细菌个体。

每个细菌个体都有一个状态向量和一个适应度值。

然后，根据每个细菌的适应度值，选择一定数量的细菌进行进化。

进化的过程包括变异和交叉操作，以获得新的细菌个体。

最后，根据进化后的细菌个体来更新种群，并继续下一轮的进化。

通过多轮的进化，细菌个体的适应度值逐渐提高，找到最优解的几率也会增加。

二、细菌觅食优化算法的改进方向尽管细菌觅食优化算法在一些问题上取得了不错的结果，但在一些复杂问题上仍然存在一些局限性。

为了进一步提高算法的性能，需要对算法进行改进。

以下是几个改进方向：1. 改进选择操作目前细菌觅食优化算法中的选择操作通常是基于轮盘赌选择，即根据细菌的适应度值来进行选择。

但这种方法可能导致一些细菌个体被选择过多或过少，从而影响算法的进化效果。

因此，可以考虑引入其他选择操作，如锦标赛选择、随机选择等，通过不同的选择策略来增加算法的多样性。

2. 引入多种变异操作目前细菌觅食优化算法的变异操作通常是随机生成一个新的状态向量。