交叉细菌觅食优化算法

文摘

本文提出一种修改细菌觅食优化算法称为交叉细菌觅食优化算法,它继承了遗传算法的交叉技术。这可以用于即兴创作的评价最优目标函数值。使用交叉机制的想法是搜索附近位置的后代(50%的细菌),因为他们在不同的位置是随机产生的。在传统的细菌觅食优化算法,搜索从同一地点(50%的细菌复制),这是不可取的。七种不同的基准函数被认为是绩效评估。同时,提出了与以往方法的结果进行比较,揭示了该算法的有效性。

1。介绍

现在几个算法开发灵感来自大自然。产品表面算法背后的主要原则是解释为一个人的能力,在最短的时间内获得足够的能源。差的觅食过程中,动物觅食策略消除,和成功的传播(1]。最成功的觅食大肠杆菌(那些生活在我们的肠道细菌),使用化学感应器官检测营养和有毒物质的浓度在其环境。环境中的细菌然后通过翻滚和运行,避免有毒物质和接近食物补丁地区这一过程被称为趋化性。基于大肠杆菌觅食策略,Passino提出细菌觅食优化算法(BFOA) [2- - - - - -4单位时间内最大化能量摄入的)。以提高BFOA性能,已经进行大量的修改。一些修改直接基于组件的分析(5- - - - - -8而另一些则称为混合算法(9- - - - - -11]。

在过去的二十年里,遗传算法(GA)声称其适用性处理优化问题的学术和工业社区。可能解决一个特定问题编码染色体,它包含一组基因。每个染色体是指搜索空间,是由健康评估决定。遗传算法使用基本交叉和变异等遗传算子产生人口的遗传组成。交叉算子产生两个后代的信息重组两个父母。使用变异算子随机基因值改变。交叉和变异的适用性是由交叉概率和变异概率12]。

在本文中,我们提出的一些修改BFOA改进遗传算法中使用的交叉算子。这里50%的健康的细菌用于交叉和一些交叉概率产生50%的细菌的后代。这些后代细菌产生在不同的位置,开始搜索。但在BFOA, 50%的细菌复制相同的位置,从同一位置开始搜索。结果他们错过一些有用的参数搜索空间。这促使我们研究交叉BFOA,可以更有效地找到全局最优解。本文遵循组织。节2,我们描述了细菌觅食优化算法。部分3介绍了BFOA提出修改。部分4处理算法的比较与BFOA CBFOA,适应性BFOA (ABFOA) [8)和遗传算法(GA) (12使用一些常见的基准函数。最后,给出了结论和未来的工作范围5。

2。细菌觅食优化算法

假设我们想要找到最低的,我们没有测量或分析梯度的描述。在这里,我们使用这个nongradient BFOA解决优化问题。让是细菌,让的位置代表的成本优化问题,,。这些价值观指导我们对细菌的位置(无论是营养丰富、中性或有害环境)。基本上BFOA由四个主要机制被称为趋化作用,云集,繁殖,elimination-dispersal。

2.1。趋化性

流程模拟运动的细菌通过游泳和翻滚。让表示位置的成本th细菌,让代表趋化现象的,th繁殖,th elimination-dispersal事件。让步骤(在跑步过程中)被指定的随机方向的下跌。然后趋化运动可以表示为 在哪里是一个随机向量与每个元素躺在。

2.2。群集

在运动期间,细胞释放引诱剂、驱虫剂其他细胞信号,这样他们应该一起群,只要他们得到营养丰富的环境或避免有害环境。被指示为细胞间的吸引和排斥效应 在哪里目标函数值添加到实际的目标函数存在时间不同的目标函数,是细菌的总数,是变量的数量参与搜索空间,在优化领域是一个点,是th的组件th细菌位置。,,,用于信号是不同的系数。

2.3。繁殖

累积成本的人口按升序排序,然后最健康的细菌和其他死去对健康的细菌繁殖,每个分裂成两个细菌,被放置在相同的位置。这使我们能够保持一个恒定的人口规模,方便在编码算法。

2.4。消除分散

由于逐渐或突然改变当地的环境中,细菌的生命可能会受到影响。为了把这一现象,我们消除人口中的每一个细菌的概率和一个新的替换随机初始化搜索空间。

3所示。交叉细菌觅食优化算法

CBFOA的主要目的是找到一个函数的最小,这不是梯度。在这里是一个attractant-repellent概要和是一种细菌的位置。让代表人口中的每一个细菌的位置细菌在th趋药性的一步,th crossover-reproduction一步,th elimination-dispersal事件。来,让表示位置的成本th细菌在位置。让的步长随机方向代表了下跌。注意细菌的位置在接下来的趋化现象的措施

如果在位置成本更好的(低)的位置在哪里,那么大小的另一个步骤(方向相同)。这个游泳持续只要它降低了成本,但它是只允许的最大数量的步骤。我们必须以这样一种方式,这种细菌可以实现群一起通过一个引诱剂和防水的,细胞间信号效应的模仿(2)。我们认为聚集效应,th细菌,将山爬上 这样的细胞会试图找到营养,避免有害物质,同时试图向其他细胞,但不能太近。

后趋化现象的步骤,crossover-reproduction一步。让是crossover-reproduction步骤的数目。趋化现象的步骤后,人口会繁殖下一代由足够的营养。为了方便,我们可以考虑是一个正数(整除(4))。让 数量(人口)有足够的营养,这对下一代可以。crossover-reproduction步骤,人口是升序排序累积成本(高成本意味着营养价值更少);然后最健康的细菌和其他死去健康的细菌已经通过了交叉概率得到孩子的细菌。然后新的细菌可以由附加健康的(父母)细菌和数量子细菌的数量。这有助于搜索域在本质上是动态的父母细菌开始搜索在养分浓度的下一代更和儿童细菌搜索附近的地方,可能是由于使用BFOA搜索策略。

让elimination-dispersal事件的数量,为每个elimination-dispersal事件中的每个细菌人口受到消除传播的概率。这有助于跟踪环境条件的突然改变,可能影响生活的细菌,所以可以引入新的细菌在搜索领域。

3.1。交叉细菌觅食优化算法

首先初始化参数,,,,,,,,,在那里代表维搜索空间,代表细菌参与人口的数量,代表趋药性的步骤的数目,代表的最大长度,游泳代表crossover-reproduction步骤的数目,代表elimination-dispersal步骤的数目,代表交叉的概率,代表消除传播事件的概率,是在随机方向的大小的一步指定由一个下跌。如果我们使用群集,我们必须选择细胞间诱食剂的参数(深度引诱剂的细胞),(引诱剂的宽度信号),(高度排斥效应的大小),(大小宽度的效果)。我们也初始化随机搜索空间内。这个算法也模仿细菌群体趋药性、消除和传播步骤Passino报道(2)和解释部分2。在这篇文章中,新鲜的是复制步骤。而不是使用复制的过程中解释部分2这里,一个新想法crossover-reproduction介绍:(最初,)。

步骤1。Elimination-dispersal循环:。

步骤2。Crossover-reproduction循环:。

步骤3。趋化性循环:。(一)为细菌趋药性的一步如下。(b)计算成本函数。(c)然后计算(即。,add on the cell-to-cell signalling effects).(d)让保存这个值,因为我们可能会找到一个更好的通过运行成本。(e)下跌:生成一个随机向量与每个元素一个随机数。(f)移动:让。这导致步长方向的暴跌细菌。(g)然后计算,让=,。(h)游泳:(我)让(计数器长度)游泳。(2)而(没有爬下太长时间),(1)让;(2)如果(如果做得更好),让并使用这计算新当我们在(g);(3)其他的,让,从while循环;(3)去下一个细菌()如果,然后去(b)处理下一个细菌。

步骤4。如果请转到步骤3。在这种情况下,继续趋化作用,因为细菌的生命还没有结束。

第5步。交叉繁殖。(一)对于给定的和,为每一个,让是细菌的健康(衡量有多少营养对其一生和如何成功的在避免有毒物质)。这种细菌和趋化现象的参数按升序的成本(更高的成本意味着更低的健康)。(b)的最高的细菌值,另一个死亡细菌被视为父母细菌为下一代。(c)然后我们选择两组父母的细菌健康的细菌和交叉概率得到细菌数量的后代。(d)然后添加父(健康)细菌和数量细菌数量的后代形成完整的一套细菌。

步骤6。如果请转到步骤2。在这种情况下,我们还没有达到指定的数量的复制步骤,我们下一代的趋化现象的循环开始。

步骤7。消除分散:,与概率每个细菌,消除和分散,从而保持人口的细菌数量不变。要做到这一点,如果我们消除细菌,只是驱散一个随机位置优化领域。

步骤8。如果,然后去一步1;否则结束。

4所示。实验结果

本节说明了一些比较拟议的CBFOA BFOA [2),自适应BFOA [8],GA (12使用一些数值表中描述的基准测试函数1。

维搜索所有测试问题我们考虑这是50和500比较算法的性能。我们也选择两个基因变异在细菌或人口,一个和其他。这里我们需要交叉率固定,实现统一的交叉。对于算法的简单性,我们忽视了消除和传播事件。注意,考虑的参数表中给出的算法2。我们把100个独立运行的结果和报告的最低,均值和标准差的最后四个算法的目标函数值。这些结果如表所示3。最后,所有四种不同算法的性能见图1。

5。结论

最近,许多修改细菌觅食优化算法研究了改善学习和收敛速度。研究或多或少地集中得到局部最优或次优的解决方案。然而,本文提出一种修改细菌觅食优化算法寻找全局最优的解决方案适应交叉遗传算法的属性。说明了该算法的性能通过各种基准测试函数。从数值结果,很明显,提出CBFOA优于ABFOA, BFOA, GA早些时候报道。该算法有潜力,可用于各种优化问题、社会觅食模式工作的地方。

引用

1. 刘y和k . m . Passino”社会觅食细菌的生物仿生分布式优化:模型、原则、和紧急行为,”优化理论与应用》杂志上,卷115,不。3、603 - 628年,2002页。视图:出版商的网站|谷歌学术搜索
2. k . m . Passino”生物仿生的分布式优化和控制细菌觅食,”IEEE控制系统杂志,22卷,不。3,52 - 67年,2002页。视图:出版商的网站|谷歌学术搜索
3. 诉Gazi和k . m . Passino稳定性分析的成群的环境中引诱剂/讨厌的概要文件,”诉讼的美国控制会议安克雷奇,页1819 - 1824年,阿拉斯加,美国,2002年5月。视图:谷歌学术搜索
4. 诉Gazi和k . m . Passino”群的稳定性分析诉讼的美国控制会议安克雷奇,页1813 - 1818年,阿拉斯加,美国,2002年5月。视图:谷歌学术搜索
5. 答:亚伯拉罕,a Biswas s Dasgupta s Das,“分析细菌觅食优化算法的繁殖算子,”《IEEE国会进化计算(CEC ' 08)2008年6月,页1476 - 1483。视图:出版商的网站|谷歌学术搜索
6. a . Biswas s Das, s·达斯古普塔和a·亚伯拉罕”繁殖算子的稳定性分析细菌觅食优化”第五届国际会议上软计算的程序作为跨学科的科学和技术(CSTST ' 08)ACM,页564 - 571年,纽约,纽约,美国,2008年10月。视图:出版商的网站|谷歌学术搜索
7. s Das s Dasgupta a Biswas a·亚伯拉罕和东部赫拉,“稳定bacterial-foraging趋化现象的动力学的优化算法,”IEEE系统,人,控制论的一部分,39卷,不。3、670 - 679年,2009页。视图:出版商的网站|谷歌学术搜索
8. 美国Dasgupta s Das, a·亚伯拉罕,a Biswas”自适应计算趋化性细菌觅食优化:一个分析,“IEEE进化计算,13卷,不。4、919 - 941年,2009页。视图:出版商的网站|谷歌学术搜索
9. A Biswas s Dasgupta s Das, A·亚伯拉罕”微分的协同进化和细菌觅食优化全局优化,“神经网络世界,17卷,不。6,607 - 626年,2007页。视图:谷歌学术搜索
10. d·h·金,A·亚伯拉罕和j·h·曹”混合遗传算法全局优化和细菌觅食方法,”信息科学,卷177,不。18日,第3937 - 3918页,2007年。视图:出版商的网站|谷歌学术搜索
11. a . Biswas s Dasgupta s Das, a·亚伯拉罕”协同算法和细菌觅食优化数值指标,比较研究”软计算的进步,44卷,第263 - 255页,2007年。视图:出版商的网站|谷歌学术搜索
12. m·米切尔介绍了遗传算法,麻省理工学院出版社,1996年。

版权

版权©2012 Rutuparna熊猫和Manoj Kumar奈克。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。