基于粒子群算法的细菌觅食全局优化算法.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.26M 资料格式：pdf 举报版权申诉

weixin_38689055-12106092-4744300845231524384.pdf-第1页.png

第1页 / 共6页

weixin_38689055-12106092-4744300845231524384.pdf-第2页.png

第2页 / 共6页

weixin_38689055-12106092-4744300845231524384.pdf-第3页.png

第3页 / 共6页

weixin_38689055-12106092-4744300845231524384.pdf-第4页.png

第4页 / 共6页

weixin_38689055-12106092-4744300845231524384.pdf-第5页.png

第5页 / 共6页

weixin_38689055-12106092-4744300845231524384.pdf-第6页.png

第6页 / 共6页

文本预览

中国科技论文在线 http://www.paper.edu.cn 基于粒子群算法的细菌觅食全局优化算法1 刘小龙，李荣钧华南理工大学工商管理学院，广州 (510640) E-mail:810963@qq.com 摘要：针对细菌觅食算法在优化过程中，环境感知能力较弱且容易陷入局部极值的缺陷，将粒子群算法的基本思想引入细菌觅食算法中，改进原算法的收敛速度和收敛能力，并据此建立了混合型的细菌觅食优化算法。为检验混合算法的性能，采用三种典型的高维复杂标准函数对这三种仿生算法进行了测试。结果表明，新算法具有良好的搜索速度与精度，可以有效弥补细菌觅食算法的速度不快和粒子群算法的精度不高缺陷，同时部分的避免了局部收敛的问题，从而适用于解决复杂函数的优化。关键词：粒子群算法；细菌觅食优化；混合优化算法 1 引言近年来，基于生物智能的启发式寻优算法已成为非线性、不可微分、多峰值、复杂问题的主流解决算法之一。在启发式算法的解决方法上，受自然界生物觅食行为的启发，各国不同的学者从中开发了许多不同的仿生算法，Dorigo M.等于 1991 年提出了蚁群优化算法(Ant Colonies Optimization, ACO)[1]，Eberhart 和 Kennedy 于 1995 年提出了粒子群优化算法 (Particle Swarm Optimization, PSO)[2]。Passino 等于 2002 年提出了细菌觅食算法(Biomimicry of Bacterial Foraging Optimization, BFO)[3]，该算法因具有群体智能并行搜索、易跳出局部极小值等优点，成为国外仿生算法研究领域的又一热点。鉴于国内对该算法的研究处于起步阶段，而该算法由于细菌趋化行为的随机性特征，导致趋化速度较慢，效率低下的缺陷，为了弥补这一缺陷，借助于不同智能仿生方法的某些共同机制和原理，利用某些仿生算法的内部运行机制的差异，进行算法的融合设计，成为了算法改进的自然途径。 2 基于粒子群算法的细菌觅食优化设计 2.1 粒子群算法 1995 年，J.Kennedy 和 R.C.Eberhartp 在他们提交给 IEEE 神经网络国际会议的论文中首次提出了粒子群优化算法（PSO）。PSO 是一种基于群集智能方法的演化计算技术，算法产生于一组初始解，通过迭代搜寻最优值，迭代过程中粒子始终追随个体极值和群体极值。同其它智能算法一样，PSO 算法的粒子在运算后期，由于缺乏有效机制跳出局部极值，容易发生“早熟”现象，因此其特征可以用速度较快、精度稍低来描述。假设所求问题维数为 D，种群规模为 m。粒子群优化算法首先初始化一群随机粒子（m 个随机解），假设用 xi 表示第 i 个粒子的位置，则 x i = ( x i 1 , x i 2 , , x id , LL , )iD x 每个粒子的位置都代表所求问题的一个候选解，这些解的好坏由适应度函数值决定，粒子在搜索时，由速度决定更新的方向和距离。用 pi 表示第 i 个粒子的历史最优位置，pg 表示整个种群的历史最优位置，vi 表示第 i 个粒子的速度，则：粒子的位置和速度根据如下方程进行更新： 1 本课题受高等学校博士学科点专项科研基金资助，项目编号：20060561002 - 1 -

中国科技论文在线 http://www.paper.edu.cn ⎧ ⎪ ⎨ ⎪⎩ v k 1 + id x k 1 + id = = v c ( k + ω ξ id 1 v x k k 1 + + id id p k id − x k id ) + c ( η 2 p k gd − x k id ) （1） k idv 是粒子 i 在第 k 次迭代中第 d 维的速度， gp k gdp k 这里，为其第 d 维的值，ω 为非负数，称为惯性权重，它使粒子保持运动惯性，使其具有扩展收索空间的趋势，有助于新区域的搜索。c1 和 c2 为正常数，称为学习因子，使粒子具有自我总结和向群体中优秀个体学习的能力，向自己的个体最优点以及群体内的全局最优点靠近。可见，是第 k 代全局最优解，粒子在搜索过程中，通过跟踪两个“极值”来更新自己，一个是粒子本身找到的最优位置，这个位置被称作个体极值 Pbest；另一个极值是粒子邻域目前找到的最优位置，通常被称作全局极值 Gbest。 2.2 细菌觅食算法生物学研究表明，大肠杆菌的觅食行为中主要包括以下步骤：寻找可能存在食物源的区域；决定是否进入此区域；在所选定的区域中寻找食物源；消耗掉一定量的食物后，决定是否继续在此区域觅食，或者迁移到一个更理想的区域。BFO 算法正是模拟 Ecoli 大肠杆菌在人体肠道内吞噬食物的觅食行为，所提出的一种新型仿生类优化算法。该算法在求解优化问题的一般过程为：产生初始解群体、计算评价函数的值、利用群体的相互影响进行优化。在 BFO 模型中，优化问题的解对应搜索空间中细菌的状态，即评价函数的适应值。BFO 算法的包括趋化（Chemotaxis）、复制（Reprodution）和迁移（Elimination and dispersal）3 个步骤。趋化是一种实现最优化觅食的行为，这种行为过程就是细菌向营养丰富地方的集中方式（即寻找越来越小的评价函数 J 值)，表现为不断寻找出路而实现的一种有倾向的游动。在细菌的趋化过程中，细菌的运动行为包括翻转（tumble）和游动（run）两种。首先，我们定义细菌向任意方向移动的单位步长为翻转，如果细菌完成一次翻转后的适应值得到改善，将沿同一方向继续移动若干步，直至适应值不再改善，或达到预定的移动步数为止，这一过程定义为游动。细菌觅食算法中的趋化行为，可描述如下：设细菌个体代表解空间的一个解，P（i, j , k , l）表示细菌个体 i 的位置，其中 j 表示第 j 代趋化循环，k 表示第 k 代复制循环，l 表示第 l 代迁移循环，方向调整用公式（2）表示。 P（i,j+1,k,l）=P（i, j, k, l）+C（i）φ（i）（2） =ϕ i )( i )( ∆ i )( T ∆ ∆ i )( （3）其中 C（i）表示按选定的方向游动的步长，∆（i）为变向中生成的随机向量，φ（i）表示进行方向调整后选定的方向。细菌觅食优化的趋化操作其实就是细菌在解空间中对可行解的搜索、判定和调整的过程，这种调整还包括依据适应度函数，来确定调整的依据、调整的方向和调整的力度等问题。大肠杆菌经过一段时间的趋化搜索之后，某些细菌的搜索策略已经很明显地失败了，为了提高搜索的精度和缩短搜索时间，一部分觅食能力强的细菌进行自身的分裂，分裂出的细菌与原来完全相同，以替换被淘汰掉的大肠杆菌。在此，算法设定趋化的生命周期，即临界趋化次数，细菌将遵循自然界“优胜劣汰，适者生存”原则进行繁殖。以趋化过程中各细菌适应值累加和为标准，较差的半数细菌死亡，较好的半数细菌分裂成两个子细菌。子细菌将继承母细菌所以的生物特性，且具有与母细菌相同的位置及步长。趋化过程可以确保细菌的 - 2 -

中国科技论文在线 http://www.paper.edu.cn 局部搜索能力，复制过程能加快细菌的搜索速度，但对于许多的优化问题，趋化和复制都无可避免的使细菌陷入局部极小地区。另外，细菌群体所依附的生存环境不可能一成不变，由于细菌对食物的消化而导致环境改变，也可能因为一些其它原因的影响而突然变化。比如说，当前环境的温度突然上升可以杀死该环境下的细菌，水的冲刷作用或其它生物的影响可以将细菌由一个环境带到一个新的环境。这样，某个区域内的细菌或者某个细菌群体便移动到了一个新的环境下开始生存。觅食算法中的迁移操作就是按照给定的概率 Ped，如果某细菌个体满足迁移操作的条件，那么就按照随机算法重新生成一个新个体，等同于将原个体迁移到一个新位置。BFO 引入迁移操作，有效地加强了该算法的全局寻优能力。 2.3 混合算法设计由粒子群算法的基本原理可以看出，粒子通过追踪自身局部最优和全部粒子的全局最优为目标更新位置。因此，我们借鉴这种思想，赋予细菌对于环境一定的感知能力，同样细菌可以通过比较自身历史最优和全部细菌的全局最优来进行迭代。相关研究表明，粒子群算法可以更快的寻找到局部最优点的大致位置，从而加快了细菌觅食优化算法的寻优速度和能力。在 BFO 算法中，最为主要的步骤是趋化操作。在实际的设计中，较大的变向与游动步长能够较快的进行收敛，也能够轻易地跳出局部最优点，但是也常常越过了全局最优点。相反，较小的游动步长收敛速度会很慢，也很容易进入局部最优区域而无法跳出，但是一旦找到全局最优点，那么就能达到较高的精度。因此，我们在细菌觅食算法的基础上，引入粒子群算法，其目的是为了给细菌的趋化操作提供方向性指引，算法设计的主要思路如图 1 所示。借助于这种方式，位置较差的细菌可以很快聚集到一个较好的区域内，而本身较好的细菌则在其邻域内进行下一步的局部搜索。算法的主要步骤设计如下： a)在变量的设计范围内对细菌规模数 s，迁移次数 Ned、繁殖次数 Nre、趋化次数 Nc，游动次数 Ns 和迁移概率进行参数设定。 b)细菌位置随机初始化，为每一个细菌随机产生任意方向的单位步长向量。 c)粒子群算法参数设计，设定每一个细菌的局部极值初始值、全部细菌的全局极值初始值。 d)趋化循环操作。对每一个细菌按照翻转方式更新位置，如果位置更好，则向前游动。 e)更新细菌个体的局部极值和细菌群的全局极值，按照粒子群算法的公式（1）来更 - 3 - 开始参数初始化 Ned,Nre,Nc,Ped,s,Ns 随机迁移 Ped 是是算法结束是繁殖 Sr=s/2 迁移次数 Ned 达到？否繁殖次数 Nre 达到？否趋化次数 Nc 达到？否带粒子群优化的趋化翻转（Delta）游动（Ns）粒子群更新图 1 混合细菌觅食优化算法流程图

中国科技论文在线新细菌的翻转方向，而非任意方向。 http://www.paper.edu.cn f)繁殖操作。对于经过一个趋化循环的细菌群体，对每个细菌按照适应度的累加和进行排序，淘汰掉适应值较差的半数细菌，从适应值较好的半数细菌中分裂出同样的细菌群，这批细菌继承母细菌的位置和特性。 g)迁移操作。经过一个繁殖操作的循环后，细菌有可能走向局部极值。在此，对于每一个细菌按照一定的迁移概率进行迁移，为了保证算法的收敛，设定一定的迁移细菌数目。在程序的设定中，最为主要的是趋化操作，其次是繁殖，最后是迁移。因此，该算法的趋化频率高于繁殖频率，而繁殖频率高于迁移频率。即一个细菌在繁殖前要经历许多个趋化步，在一次迁移前也要经历好几代的繁殖过程。 3 对比实验分析 3.1 检验函数为检验混合优化算法的性能，本文采用三个典型的标准函数[4]对三种相关算法进行了比较测试。（1）Rosenbrock 函数 f1：全局最优为 0，最优解分布在 X= (1, 1, 1, …, 1)处，该函数的解空间有非常多狭窄的通道，导致很难获得全局最优解。（2）Rastrigin 函数 f2：全局最优为 0，最优解分布在 X= (0, …, 0)处，该函数具有大量按正弦拐点排列的、很深的局部最优点，优化算法很容易在通往全局最优点的路径上陷入一个局部最优点。（3）Griewank 函数 f3：全局最优为 0，最优解分布在 X= (0, …, 0)处，该函数的变量间具有由乘积项产生的很强的相互影响，是激烈的多峰函数，其局部最优点的数量随维度不断增加。 xf )( 1 = f 2 x )( = n 1 ∑− i 1 = (100[ x i 1 + − x 22 ) i + ( x i − 2 ])1 n ∑ i 1 = [ x 2 i − 10 cos( x 2 π 2 ) + ]10 i f 3 x )( = 1 400 n ∑ i 1 = [ x 2 i n Π− i 1 = cos( i x i ]1) + 3.2 对比实验参数设置为了比较算法的性能，本文同时对混合粒子群的细菌算法、粒子群算法、细菌觅食算法在上述三个函数中进行了优化测试。对于细菌觅食算法，较大的趋化步数 Nc 可能取得更多的优化进展，但也会增加计算量；但 Nc 值太小，算法一般就会更多地依赖迁移以及繁殖。繁殖次数 Nre，能在一定程度上加速细菌的群集，使其快速到达最优点，但也可能聚集到了局部最优点；但如果 Nre 太小，则算法可能也会过早收敛。最后，较小 Ned 值会使算法不会依靠随机的迁移事件来实现全局优化，而尝试寻找有利的值域。对于迁移概率来说，较大的 Ped 值会使得算法退化为随机穷举搜索，使其更多地依赖于运气进行寻优。基于此，细菌觅食算法的主要参数 s=30，迁移次数 Ned=2、繁殖次数 Nre=4、趋化次数 Nc=30，游动次数 Ns=4、迁移概率 Ped=0.25。其中，粒子群算法采用惯性权重ω=0.7 的线性递减策略，学习因子 c1=c2=1.494，粒子数为 30。 - 4 -

中国科技论文在线 3.3 测试结果 http://www.paper.edu.cn 三种算法在三个函数上的测试次数均为 50 次，具体测试结果见表 1。其中：优化均值是指所有优化搜索结果中的最优平均值；标准差是以上成功搜索 50 次时最优值的标准差，当最优值小于允许误差时即认为本次搜索成功。为了更好地说明粒子群算法和细菌觅食算法的特点，同时与其他算法保持一致，本组测试结果，所有函数均采用两种不同的维度进行统计。函数维度优化均值（标准差）表 1 测试函数的优化均值和标准差 f1 f2 f3 10 30 10 30 10 30 4 结果讨论 PSO 11.237（4.552） 48.279（10.362） 3.135（0.288） 14.747（0.791） 0.234（0.020） 0.391（0.051） BFO 14.730（1.872） 56.372（16.429） 5.018（1.683） 17.826（5.182） 0.066（0.023） 0.076（0.011） PSO-BFO 0.412（0.066） 16.275（2.764） 0.102（0.013） 11.256（0.284） 0.027（0.004） 0.145（0.127）由表 1 可以看出，在维度较低（10 维）时，加入粒子群算法的细菌觅食优化不管是在优化的均值上，还是优化均值的标准差上，都明显的优于粒子群算法和细菌觅食算法。这说明在同样的允许误差下，混合算法的收敛概率大于细菌觅食算法，且同时大于粒子群优化算法。当函数的维度较高时，加入粒子群算法的细菌觅食算法对于提高搜索精度没有明显的帮助，收敛概率低于单纯的细菌觅食优化算法。这证实了粒子群算法与细菌觅食算法的不同特性：粒子群算法的搜索比较粗糙，但往往能相对快速确定全局极值的邻域；而细菌觅食算法的搜索比较精细，但容易收敛在局部极值。另外，改进后的混合粒子群-细菌觅食优化算法，无论在成功率还是在搜索速度上，均显著优于单一的粒子群算法和细菌觅食算法，上述实验成功证明了改进算法的实用性和有效性。综上所述，细菌觅食算法由于搜索趋化初期缺乏种群的多样性，导致搜索步调趋缓而收敛速度慢，如果后期的迁移算法不能有效的克服，该算法缺乏跳出局部极点的有效机制，容易产生早熟现象，故适用于进行精细搜索；另外，粒子群算法的快速聚群特性可加快搜索步调和提高收敛的速度，这一特性提高了细菌的环境感知能力，对于提高细菌群体的全局极值的位置判断具有指引作用，故适用于确定极值邻域。三种现行优化算法的测试表明，混合算法弥补了粒子群算法和细菌觅食算法的各自缺陷，其搜索性能不仅优于粒子群算法及细菌觅食算法的搜索性能，而且还能有效的提高搜索的速度，且适用于解决高维复杂函数的相应优化问题。参考文献 [1] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies，Proceedings of ECAL’91, European Conference on Artificial Life. Paris, France: Elsevier Publishing, 1991: 134-142. [2] Eberhart R C, Kennedy J. A New Optimizer Using Particle Swarm Theory，Proc. The Sixth Int. Symposium on Micro Machine and Human Science, Nagoya Japan: IEEE Robotics and Automation Society, 1995: 39-43. [3] Passino K M. Biomimicry of Bacterial Foraging for Distributed Optimization and Control [J]. IEEE Control - 5 -

中国科技论文在线 http://www.paper.edu.cn Systems Magazine (S0272-1708), 2002, 22(3): 52-67. [4] Tai-Chen Chen, Pei-Wei Tsai, Shu-Chuan Chu*, and Jeng-Shyang Pan. A Novel Optimization Approach: Bacterial-GA Foraging. Second International Conference on Innovative Computing, Informatio and Control (ICICIC 2007) The bacterial foraging algorithm for global optimization based on PSO School of Business Administration, South China University of Technology, Guangzhou (510640) Liu Xiaolong, Li Rongjun Abstract To overcome the drawbacks of bacterial foraging algorithm for the optimization process, that is the weak ability to perceive the environment and vulnerable to perception of local extreme. This article will merge the idea of PSO algorithm into the bacterial foraging to improve the speed and convergence capabilities of BFO algorithm and according to this established a hybrid optimization algorithm. To show the searching performances of new hybrid algorithm, using three typical high dimensional complexities of the standard functions to test these three bionic algorithms. The results show that the new algorithm has a good search speed and accuracy can effectively overcome the drawbacks, while the new algorithm partly avoid the problem of local convergence and thus apply to solve the complex functions Optimization. Keywords：PSO;Bacterial Foraging Optimization;Hybrid Optimization Algorithm 作者简介：刘小龙(1977.5)，男，博士研究生，主要研究方向为风险控制、管理决策。李荣钧(1946.2)，男，湖南永州人，教授，博导，主要研究方向为风险控制、人工智能。 - 6 -

分享到：

赞收藏

资料库

基于粒子群算法的细菌觅食全局优化算法.pdf

相关推荐

开发技术

热门标签

最新资料