基于细菌觅食行为的多目标分布估计算法概要

本文格式为Word版，下载可任意编辑——基于细菌觅食行为的多目标分布估计算法概要

收稿日期：２０１１唱０１唱１７；修回日期：２０１１唱０４唱２６基金项目：国家自然科学基金资助项目（６０９６２００６）

简介：乔英（１９８２唱），女（土族），青海乐都人，讲师，主要研究方向为多目标进化算法及其应用（ｊｉａｎｇｑｉａｏｙｏｎｇ＠１２６．ｃｏｍ）；高岳林（１９６３唱），男，陕西榆林人，教授，博士，主要研究方向为最优化理论方法及应用、智能计算与智能信息处理、金融数学与金融工程；江巧永（１９８３唱），男，浙江温岭人，硕士研究生，主要研究方向为多目标进化算法及其应用．

基于细菌觅食行为的多目标分布估计算法倡

乔英，高岳林，江巧永

（北方民族大学信息与系统科学研究所，银川７５００２１）

摘要：为加强多目标分布估计算法（ＭＥＤＡ）的局部探寻能力，将细菌的觅食（ＢＦ）行为引入到多目标分布估计算法中，提出一种基于细菌觅食行为的多目标分布估计算法（ＭＥＤＡ唱ＢＦ）。数值试验选取四个常用测试函数，并与ＮＳＧＡ唱ＩＩ、ＭＥＤＡ两个多目标算法进行比较，结果说明ＭＥＤＡ唱ＢＦ算法在收敛性和多样性两方面都有较好的性能。

（ｘ０巢ｘ１）当且仅当

ｆｉ（ｘ０）≤ｆｉ（ｘ１）ｉ＝１，２，…，ｍｆｉ（ｘ０）＜ｆｉ（ｘ１）

愁ｉ∈｛１，２，…，ｍ｝（２）

ｂ）Ｐａｒｅｔｏ最优。假使解ｘ０是Ｐａｒｅｔｏ最优的当且仅当撤愁ｘ１巢ｘ０。

第２８卷第１０期２０１１年１０月计算机应用研究

ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＶｏｌ畅２８Ｎｏ畅１０Ｏｃｔ畅２０１１

ｃ）Ｐａｒｅｔｏ最优集。所有Ｐａｒｅｔｏ最优解的集合ＰＳ＝｛ｘ０｜

撤愁ｘ１巢ｘ０

｝，又称为非劣最优解集。ｄ）Ｐａｒｅｔｏ最优前端。所有Ｐａｒｅｔｏ最优解对应的目标函数

值所形成的区域ＰＦ：

ＰＦ＝｛ｆ（ｘ）＝（ｆ（ｘ１），ｆ（ｘ２），…，ｆ（ｘｍ））｜ｘ∈ＰＳ｝

ｅ）集合Ａ称为局部Ｐａｒｅｔｏ最优解集，当且仅当

橙ａ∈Ａ，撤愁ｘ∈Ｘ，ｘ巢ａ∧‖ｘ－ａ‖＜ε∧‖ｆ（ｘ）－ｆ（ａ）‖＜δ（３）

２分布估计算法

分布估计算法是进化计算领域一类新兴的随机优化算法，它是遗传算法与统计学习的结合。该算法用统计学习的手段构建解空间内个体分布的概率模型，然后运用进化的思想进化该模型。该算法不同于遗传算法，它没有传统的交织、变异操作，是一种全新的进化模式，通过对概率模型的采样实现种群的进化。

１）建立概率模型假定当前进化种群听从固定高度柱状分布，固定高度柱状模型将决策变量ｘｉ的探寻空间［ａｉ，ｂｉ］分为高度一致的Ｈ份（Ｈ个子区间），其每个子区间的样本个数一致，然后根据落在每个子区间的样本计算它的取值范围。

２）随机采样方法新种群是通过对概率模型随机采样产生，每个决策向量中的ｘｉ可由如下方式产生：随机选择一个子区间ｈｓ（ｓ＝１，２，…，Ｈ）；按均匀分布从该子区间取一值；独立地重复这个采样过程，屡屡即可获得多个新的个体，进而得到一个新的种群。

３ＭＥＤＡ唱ＢＦ算法

与传统进化算法不同，分布估计算法是基于整个进化种群（内部种群）Ｐｏｐ建立数学模型，直接描述整个群体的进化趋势，是对生物进化宏观层面上的数学模型，具有良好的全局探寻能力，但局部探寻能力较差

［１８］

。由Ｐａｓｓｉｎｏ提出的细菌觅食

理论是基于这样一个假设：细菌通过涌动和翻滚两种趋化性运动寻觅并获得食物，以单位时间内最大化所获得的能量为目标

［１９，２０］

。根据觅食理论，自然选择寻常会淘汰觅食能力差的

个体，而留下具有良好觅食策略的个体基因，由于这些个体在繁殖方面有更大的优势。每一代都进行这样的自然选择，那么好多代之后，较差的觅食策略或者被淘汰掉，或者进行调整而演化成良好的策略。可以看出，细菌觅食的行为侧重于局部探寻，而分布估计算法侧重于全局探寻，两者结合可充分利用两者各自的优点，实现优势互补。但是如何有效地将两者结合起来是一个困难的问题，处理不当甚至会降低多目标分布估计算法的性能。下面着重阐述这一问题。

根据式（３）可知，在Ｐａｒｅｔｏ最优解的附近可能存在更好的解。若细菌对Ｐａｒｅｔｏ最优解集（外部种群）中个体进行觅食（涌动和翻滚）的作用等价于对Ｐａｒｅｔｏ最优解进行局部爬山操作，则有可能找到更优的解，以此来替换进化种群的较劣解。这样实现了内部种群与外部种群之间的信息交流，提高种群的多样性和进化动力。首先进化种群按非劣分类方式［４］

进行排

序，则上述内容具体操作如下：

ｆｏｒｋ＝１：ＮＣ，对每个细菌ｋ按如下方式实现：ａ）翻滚。产生一个随机向量Θ（ｋ），以确定细菌涌动一次

后的位置，向量Θ（ｋ）的每一个元素为区间［－１，１］的随机数。ｂ）涌动。在Ｐａｒｅｔｏ最优解集中随机选出一个解Ｏｐｔｉ

（ｊ，：），令

Ｏｐｔｉ（ｊ，：）＝ｗＯｐｔｉ（ｊ，：）＋Ｃ（ｋ）Θ（ｋ）Θ（ｋ）Θ（ｋ）为细菌涌动一次后的位置。

ｃ）替换。Ｐｏｐ（Ｎ－Ｎｃ＋ｋ，：）＝Ｏｐｔｉ（ｊ，：）。其中：ＮＣ为细

菌个数；ｗ为惯性因子；Ｃ（ｋ）为趋化步长；Ｐｏｐ（Ｎ－Ｎｃ＋ｋ，：）为进化种群Ｐｏｐ的第Ｎ－Ｎｃ＋ｋ个个体；Ｎ为进化种群的规模。

４ＭＥＤＡ唱ＢＦ算法的具体步骤

ａ）设置算法参数ｎ、Ｎ、Ｃ、ＮＣ、Ｈ、Ｇｍａｘ等。ｂ）在决策空间中均匀生成初始种群Ｐｏｐ。

ｃ）将群体Ｐｏｐ中的非支配解参与Ｐａｒｅｔｏ最优解集中。ｄ）根据分布估计方法产生新个体，当新个体支配原个体，

保存新个体；当新个体支配于原个体，保存原个体；当新个体与原个体相互不支配，两者都保存。这样得到一个规模介于Ｎ～

２Ｎ的复合种群。

ｅ）将复合种群的非支配个体参与到Ｐａｒｅｔｏ最优解集，选出

Ｐａｒｅｔｏ最优解集中的非支配个体。当非支配个体数大于Ｎ时，对非支配个体按ＮＳＧＡ唱Ⅱ的拥挤度距离从大到小进行排序，选

出前Ｎ个非支配个体保存在Ｐａｒｅｔｏ最优解集中，其余个体全部删除。ｆ）根据ＮＳＧＡ唱Ⅱ的选择策略从复合种群中选出新一代进化种群。ｇ）执行细菌的翻滚、涌动和替换操作。

ｈ）假使达到最大迭代次数，则终止，输出Ｐａｒｅｔｏ最优解集；否则返回ｄ）。５数值试验

５畅１算法性能评价指标

多目标优化问题的解质量评价主要集中在所求得的解与

理论最优值之间的差距，以及求得的解的分散程度。这里采用Ｖｅｌｄｈｕｉｚｅｎ等人在１９９８年提出来的收敛度指标［２１］

来衡量所求

解与理论解之间的差距，用Ｄｅｂ等人在２００２提出来的多样度指标［４］

来评价解的分散程度。收敛度指标公式如下：ＧＤ＝

∑ｎｉ＝１ｄｉｎ（４）

其中：ｎ为最优解数目，ｄｉ为所求得第ｉ个个体在目标空间与理论Ｐａｒｅｔｏ最优前沿的最小欧氏距离。世代距离ＧＤ越小，算法迫近Ｐａｒｅｔｏ最优解集的程度越好；当所得到的解刚好与从最优前端取得的点重合时，ＧＤ＝０。

多样度指标公式如下：Δ＝

ｄｆ＋ｄｌ＋∑ｎ－１ｉ＝１｜ｄｉ－ｄ｜ｄｆ＋

ｄｌ＋（ｎ－１）ｄ（５）

其中：ｄｉ为所求得解个体相互之间在目标空间中的欧氏距离；ｄ为这些距离的平均距离；ｄｆ、ｄｌ分别为所求得解的边界与理论解的边界之间的距离。当获得的非劣解完全均匀地分布在均衡面上，ｄｆ＝０，ｄｌ＝０，所有ｄｉ＝ｄ，这时Δ＝０。因此，Δ指标反映非劣解能否均匀地分布在整个均衡面上。

５畅２数值试验及分析

为测试ＭＥＤＡ唱ＢＦ算法的性能，选取ＺＤＴ１、ＺＤＴ２、ＺＤＴ３、ＺＤＴ４四个常用的多目标测试函数［４］

进行数值试验，并与ＮＳ唱ＧＡ唱Ⅱ、ＭＥＤＡ进行比较。为了便于与文献［４］结果进行比较以及考虑比较的公允性，ＭＥＤＡ唱ＢＦ、ＭＥＤＡ和ＮＳＧＡ唱Ⅱ均采用

实数编码方式，并且其共有参数尽量设置一致。对实数编码

ＮＳＧＡ唱Ⅱ，按文献［４］的建议进行参数设置，种群规模Ｎ＝１００，最大进化数Ｇｍａｘ＝２５０，采用模拟二进制交织和多项式变异算子，分布参数ηｃ＝２０，ηｍ＝２０。在ＭＥＤＡ唱ＢＦ和ＭＥＤＡ算法中，ｗ和Ｃ（ｋ）取０～１之间的随机数，ＮＣ＝１０，Ｈ＝２０，Ｐａｒｅｔｏ最优解集的上限为１００。为减少诸多随机因素的影响，对三种算法均独立运行３０次，取平均结果。表１和２分别给出了三种算法对四个测试函数得到的收敛度指标的均值（上行）、方差（下行）和分散度指标的均值（上行）、方差（下行）。图１是

ＭＥＤＡ唱ＢＦ、ＮＳＧＡ唱Ⅱ、ＭＥＤＡ算法关于ＺＤＴ１、ＺＤＴ２、ＺＤＴ３、ＺＤＴ４的试验对比图。

表１三种算法对四个测试函数收敛度指标的统计结果

函数ＮＳＧＡ唱ⅡＭＥＤＡＭＥＤＡ唱ＢＦＺＤＴ１０．０３３４８２０．００８３５９０．００１４１６０．００４７５００．００００２００．００００００ＺＤＴ２０．０７２３９１０．００４３１６０．００１１６７０．０３１６８９０．００００１００．００００００ＺＤＴ３０．１１４５０００．００８８５５０．００４３８１０．００７９４００．００００１６０．００００００ＺＤＴ４

０．５１３０５３３．０８６５３６０．００２８７８０．１１８４６０

９．３６６６８６０．０００３２３

表２三种算法对四个测试函数分散度指标的统计结果

函数ＮＳＧＡ唱ⅡＭＥＤＡＭＥＤＡ唱ＢＦＺＤＴ１０．３９０３０７０．４３４０８８０．２４３７４１０．００１８７６０．０１３５４００．０００３５１ＺＤＴ２０．４３０７７６０．３９０５１００．２４８８１１０．００４７２１０．００９１６６０．０００４６２ＺＤＴ３０．７３８５４００．５８０３６００．５０２７４５０．０１９７０６０．００４２１００．０００４１２ＺＤＴ４

０．７０２６１２１．２６７０１９０．２６１７１７０．０６４６４８０．０２５７７２０．０００５７６

从表１和２可以看出，ＭＥＤＡ唱ＢＦ算法对四个测试函数得到的收敛度指标和分散度指标均优于其他两种算法。从图１试验对比图可以看出，ＭＥＤＡ唱ＢＦ算法得到的Ｐａｒｅｔｏ曲线与真

实Ｐａｒｅｔｏ曲线拟合得更好一些。６终止语

ＭＥＤＡ唱ＢＦ算法将分布估计算法应用于多目标优化问题，

有效地结合了分布估计算法良好的全局探寻能力和细菌觅食行为的局部探寻能力强的优点。数值试验和仿真结果说明白ＭＥＤＡ唱ＢＦ在收敛性和分散性两方面都有很好的表现，是一种有效的多目标进化算法，细菌觅食行为的参与提高了ＭＥＤＡ算法的性能。

１９９９：９８唱１０５．

［８］ＣＯＥＬＬＯＣＡ，ＰＵＬＩＤＯＧＴ，ＬＥＣＨＵＧＡＭＳ．Ｈａｎｄｉｎｇｍｕｌｔｉｐｌｅｏｂ唱

ｊｅｃｔｉｖｅｓｗｉｔｈｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓｏｎＥｖｏｌｕ唱ｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，２００４，８（３）：２５６唱２７９．

［９］ＪＩＡＯＬｉ唱ｃｈｅｎｇ，ＧＯＮＧＭａｏ唱ｇｕｏ，ＳＨＡＮＧＲｏｎｇ唱ｈｕａ，ｅｔａｌ．Ｃｌｏｎａｌｓｅ唱

ｌｅｃｔｉｏｎｗｉｔｈｉｍｍｕｎｅｄｏｍｉｎａｎｃｅａｎｄａｎｅｒｇｙｂａｓｅｄｍｕｌｔｉ唱ｏｂｊｅｃｔｉｖｅｏｐｔｉ唱ｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ３ｒｄＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＥｖｏｌｕｔｉｏｎａｒｙＭｕｌｔｉ唱ｃｒｉｔｅｒｉｏｎＯｐｔｉｍｉｚａｔｉｏｎ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００５：４７４唱４８９．

［１０］ＧＯＮＧＭａｏ唱ｇｕｏ，ＪＩＡＯＬｉ唱ｃｈｅｎｇ，ＤＵＨａｉ唱ｆｅｎｇ，ｅｔａｌ．Ｍｕｌｔｉ唱ｏｂｊｅｃｔｉｖｅ

ｉｍｍｕｎｅａｌｇｏｒｉｔｈｍｗｉｔｈｎｏｎ唱ｄｏｍｉｎａｔｅｄｎｅｉｇｈｂｏｒ唱ｂａｓｅｄｓｅｌｅｃｔｉｏｎ［Ｊ］．ＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，２００８，１６（２）：２２５唱２５５．

［１１］Ｍ册ＨＬＥＮＢＥＩＮＨ，ＰＡＡＳＳＧ．Ｆｒｏｍｒｅｃｏｍｂｉｎａｔｉｏｎｏｆｇｅｎｅｓｔｏｔｈｅｅｓ唱

ｔｉｍａｔｉｏｎｏｆｄｉｓｔｒｉｂｕｔｉｏｎｓＩ．ｂｉｎａｒｙｐａｒａｍｅｔｅｒｓ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ４ｔｈＩｎ唱

ｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＰａｒａｌｌｅｌＰｒｏｂｌｅｍＳｏｌｖｉｎｇｆｒｏｍＮａｔｕｒｅ．Ｂｅｒ唱ｌｉｎ：Ｓｐｒｉｎｇｅｒ唱Ｖｅｒｌａｇ，１９９６：１７８唱１８７．

［１２］ＫＨＡＮＮ，ＧＯＬＤＢＥＲＧＤＥ，ＰＥＬＩＫＡＮＭ．Ｍｕｌｔｉ唱ｏｂｊｅｃｔｉｖｅＢａｙｅｓｉａｎ

ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ，ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ２００２００９［Ｒ］．Ｕｒｂａｎａ唱Ｃｈａｍｐａｉｇｎ：ＵｎｉｖｅｒｓｉｔｙｏｆＩｌｌｉｎｏｉｓａｔＵｒｂａｎａ唱Ｃｈａｍｐａｉｇｎ，２００２．［１３］ＬＡＵＭＡＮＮＳＭ，ＯＣＥＮＡＳＥＫＪ．Ｂａｙｅｓｉａｎｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｆｏｒ

ｍｕｌｔｉ唱ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃｏｆｔｈｅ７ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎ唱ｆｅｒｅｎｃｅｏｎＰａｒａｌｌｅｌＰｒｏｂｌｅｍＳｏｌｖｉｎｇｆｒｏｍＮａｔｕｒｅ．Ｌｏｎｄｏｎ：Ｓｐｒｉｎｇｅｒ，２００２：２９８唱３０７．

［１４］ＺＨＯＵＡｉ唱ｍｉｎｇ，ＺＨＡＮＧＱｉｎｇ唱ｆｕ，ＪＩＮＹａｏ唱ｃｈｕ，ｅｔａｌ．Ｇｌｏｂａｌｍｕｌｔｉ唱

ｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｖｉａｅｓｔｉｍａｔｉｏｎｏｆｄｉｓｔｒｉｂｕｔｉｏｎａｌｇｏｒｉｔｈｍｗｉｔｈ

ｂｉａｓｅｄｉｎｉｔｉａｌｉｚａｔｉｏｎａｎｄｃｒｏｓｓｏｖｅｒ［Ｃ］／／ＰｒｏｃｏｆＧｅｎｅｔｉｃａｎｄＥｖｏｌｕ唱

ｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎＣｏｎｆｅｒｅｎｃｅ．ＮｅｗＹｏｒｋ：ＡＣＭＰｒｅｓｓ，２００７：６１７唱

６２２．

（下转第３６８６页）

表１三种算法在测试函数中的数据统计对比（１００次）函数

算法最优值收敛到全局最优解的平均迭代次数收敛到局部极值点的次数平均计算时间／ｓ１ＧＡ０

２３１２３２１．１１ＱＧＡ０１５６１３１２．５４ＣＱＧＡ０９９０９．８７２ＧＡ

０．４５４９３４１

２６２４．３３ＱＧＡ０．７１３３２３８

１０１４．３４ＣＱＧＡ０．９３２１

１２３０

１０．１１３

ＧＡ０．２６８２４５３

３３３４．７６ＱＧＡ０．５９３２２１３８１５．３４ＣＱＧＡ０．９５４１１４５０

１１．１３４ＧＡ

０．９７２１５４１

３１４５．２１

ＱＧＡ０．９７３９２