含被动聚集因子的微粒群优化算法A particle swarm optimizer with passive congregation翻译.doc

含被动聚集因子的微粒群优化算法 本文给出了含被动聚集因子的微粒群算法来提高标准PSO（SPSO）的性能，被动聚集因子是一个重要的生物力量以保存种群的完整性。通过将被动聚集因子引入PSO算法中，信息能够从群体中的个体中转变。含被动集聚集因子的微粒群优化算法（PSOPC）已经通过了10种30维的基准函数的测试，并且分别与全局版本的SPSO、本地版本的SPSO（LSPSO）、和含有收缩因子的PSO（CPSO）做了比较。实验结果显示出含被动聚集因子的PSO明显地提高了基准函数的搜索表现。1介绍 微粒群算法（PSO）是一种群算法，首先是由Kennedy与Eberhart（1995）提出的，它是由动物的社会行为而受到启发的，比如鱼群和鸟群。与其他群算法相似，比如进化算法，PSO能够解决很多种不同的优化问题，同时在某些方面PSO也显示出了比其他算法更快的收敛速率（Kennedy和Eberhart，2001）。PSO的另一个优点是它具有更少的参数去调节，这使得PSO非常容易执行。 Angeline(1998)指出虽然PSO能够比其他进化算法在早期的迭代中表现得更出色，但是当迭代次数增加时它的竞争力就没有那么大了。目前，有多个关于提高标准PSO（SPSO）的性能的研究已经开始做。Lobjerg etal.(2001)提出了一个包含子代和亚种群的混合的PSO模型.Kennedy和Mendes（2002）提出了这种压缩种群数量结构来研究SPSO的搜索性能。其他的关于提高PSO的性能的研究有运用类聚分析（Kennedy，2000）和模糊自适应惰性权重（shi 和 Eberhart）。图1，微粒群与最好位置微粒gbest的相互作用PSO 是基于假设同类中各元素提供一种最优进化信息的群体分享（Kennedy和Eberhart，1995）。SPSO模型是基于以下两种因素：（Kennedy和Eberhart，1995）； （1） 自我记忆，它能够记得在群体中每个个体（）以前的最好的位置;（2） 公认的认知，它是这个群体中目前所能得到的最优解（）。因此，在同一种类种分享信息是在采用公共的可见信息过程之中完成的，如图1。并且在单独的个体之中没有信息分享，除非向其他个体传播了信息。因此，种群也许会丢掉多样性，并且如果到目前为止，相对于全局最优解的搜索种群收敛的太早，很可能限制在本地最小值周围的搜索能力。生物学家已经提出了允许动物聚集成群体四种生物学上的机制：被动的增长（passive aggregation），主动的增长（active aggregation），被动的聚集(passive congregation)，社会性的聚集（social congregation）（Parrish和Hamner，1997）。在这些力量之中有不同的信息分享机制。我们发现被动聚合模型对于SPSO模型的组合来说只相当匹配的，由于被这个发现所激发，我们提出了一种含有被动聚集因子的混合PSO模型。第二部分介绍了SPSO。含有被动聚集因子的PSO算法将在第三部分呈现。第四部分，我们给出了测试函数，实验设置参数，与实验的结果。在第五部分。给出了一些讨论。第六部分给出了结论。2，标准微粒群优化算法。PSO是以群体为基础的优化算法。PSO算法的整体被称为微粒群，并且PSO群体中的每个个体被称为微粒，第个微粒在第次的迭代中具有以下两个性质：（1） 在一个N维德搜索空间中微粒的当前位置，其中与分别是维空间数的上限和下限。（2） 当前速率，它由最大速率与最小速率所限定。在PSO的每一次迭代中，这些微粒由以下的方程来更新（Kennedy与Eberhart，1995）： (1) (2)上式中，表示第个微粒所经过的最好位置（也称作pbest）。根据的不同定义，由两种不同的PSO版本.如果 表示所有微粒经过的最好位置（也称作gbest），这个版本称作全局版本。如果来自一些更小数量的临近微粒（也被称作lbest），这样的版本称为局部版本。与由分别由下列方程决定： （3） （4）这里是目标函数，并且表示整个微粒群的数量，为均匀分布的随机数 即；。表示惯性权重（Shi与Eberhart，1997），通常初始化为之间的随机数。一个较大的惯性权重能够促进全局的收敛，而一个较小的惯性权重能够微调当前搜索区域，促进局部收敛（Shi与Eberhart，1998），为加速常数（Eberhart与Shi），用来控制一个微粒进入一个单循环中所走的距离。 标准PSO的另一个重要的变体是含有收缩因子途径的PSO（CPSO），由Clerc与Kennedy（2002）提出。CPSO的速率由下列方程给出： （5）这里称为收缩因子，并给出： 其中 （6）CPSO保证搜索过程的收敛，并且在一些研究问题上，能够产生比含有惯性权重的标准PSO更加有效的解决方法（Eberhart与Shi，2000）。3，含被动集聚集因子的微粒群优化算法。PSO算法是由一些社会群体的行为发展而来的，比如鸟群，鱼群和昆虫群体的特殊的空间秩序。每一个这些事件都有一个稳定的有机群体的时空完整性：这些群体不会失去任何一点形态和密度，犹如一个整体一般地坚持自己的发展。对于这些群体的每一个来说。不同的生物力是保存群体完整性的必要因素。Parrish与Hammer（1997）提出了一个数学模型：动物群体的空间结构，该模型显示了动物是怎样组织他们自己的。在这些模型中，聚合有时候代表有机群体的无社会性的外部的物理力量。这里我们有两种聚集:被动聚合与主动聚合。被动聚合指得是通过自然的物理过程形成的被动群体。举一个被动聚集的例子，在开放水域的浮游生物的大规模的聚集，这里这些浮游生物不是由于聚集的群体吸引过去的，而是通过物理力量（比如水流）被动的传送过去的。主动聚集指的是群体依靠一些具有吸引力的东西（比如食物或者空间）使得群体中的每一个成员都主动地聚集到一个特殊的位置。集合与聚集不同，是由整体力量推动群聚的，就是说吸引聚合的源头是这个群体本身。集合可分为被动集合与社会性的集合。被动集合是指，群体中某个个体对其他群成员的吸引，但是这里没有任何社会行为的显现。社会性的集合常常发生在各成员相关（ 有时候高度相关）的群体中。许多的个体间的行为是在社会集合，需要主动信息转移中显示出来的 (Parrish and Hammer,1997) .举个例子说明,蚂蚁用触角接触传递个体身份或者位置的信息（Gorgon等,1993）。由以上的定义，方程（1）的第三部分可以被分类成要么是主动聚合因子要么是被动集合因子。但是由于是目前为止群体的最好位置，这里可以看成是食物最多的地方。我们认为作为主动聚合因子更好。 已经发现，在空间上定义明确的聚合，比如鱼群，单个的鱼对整个群体有较低的保真度因为集合的整体是由微弱甚至没有关系的各个个体组成的（Hilborn,1991）。鱼群整体上称为“自私的牧群”（Hqmilton,1971）,在群体中每个个体试图从群体中吸取整体的优势，而不是他们邻居的命运（Pitcher andParrish,1993）。在这些集合中，信息能够被动的转移而不是主动的（Magurran and Higham,1998）。这种反社会的集合类型能够被认为是被动的集合。因为PSO是由鱼群的启发而出现的，因此自然的会问如果一个被动的集合模型能够被应用以提高SPSO的性能。这里，我们不考虑其他模式比如被动聚合，因为PSO不是通过物理过程而被动聚合的。因为社会性的集合常常在群体的高保真度时发生，比如每个个体相互间有很高的联系时（Alexander,1974）。社会集合通常会出现劳动分工。在一个社会性的昆虫领域，比如蚂蚁的群体，大多数工作是由专门的个体所组成的群体共同完成的。这比由非专业的个体按顺序工作要有效率的多（Bonabeau et al.,1999）。劳动分类的概念是建立在数据聚类排序，排序和数据分析的基础上的（Lumber and Faieta，1994）。一个聚集中的组成员可以作出反应，并且无需直接检测坏境中的输入信号，因为他们可以从他们邻居那得到足够的信息（Parrish and Hammer，1997）。个体需要监视周围环境与他们直接相关的邻居，比如邻居的方位与速度（Parrish and Hamner，1997）。因此，集合中的每一个个体都有从其他组成员那得到的多种潜在信息，这样可以最大限度的减少漏检与不正确解释的几率（Parrish and Hamner,1997）。这样的信息传递能够应用在被动集会模式里。由于这个结果的启发，也是为了保持模型的简单与和SPSO保持一致，我们提出了一个含有被动因子的混合的PSO模型： （7） （8）这里表示从群中随机选择的一个粒子，表示被动集会系数，表示一个统一的随机序列，范围是（0,1）：。PSOPC里的个体之间的交互在图2中所示，PSOPC的伪代码如表1所示。图2.含有被动聚集因子的微粒的交互作用表1，PSOPC算法的伪代码4.实验研究4.1. 测试函数 在我们的实验研究中，10个基准函数集被用来评价PSOPC算法与其他算法的优劣。 Sphere model： Schwefels Problem 1.2: Schwefels Problem2.21: Generalized Rosenbrocks function: Generalized Schwefels Problem 2.26: Generalized Rastrigins function: Ackleys Function: Generalized Griewank function: Generalized Penalized functions: 和这里我们有： 以上这些基准函数都已经由Yao等人（1999），Chellapilla（1998），Fogel(1991)深度的测试过了。他们可以分成单峰函数（），和多峰函数（），这里，局部最小值随着问题维数的增加以指数方式增长。表2列出了每个函数的维度，可行的解空间和。表2 测试函数的基本特征4.2 实验设置为了测试所提出的PSOPC的表现，三个标准PSO的变种被用来比较，标准PSO的全局版本（GSPSO），标准PSO的局部版本（LSPSO），与收缩因子版本的PSO（CPSO）。用在这三个标准PSO的参数来自Kennedy and Eberhart(2001),Clerc and Kennedy(2002),Eberhart and Shi(2001),Shi and Eberhart(1998),Kenndy and Mendes(2002),或者是由首选出来的。在我们的实验中所有算法的规模数量都设定为100。GSPSO，LSPSO和CPSO的粒子速度的最大值与最小值被分别设定为上限值与下限值的一半。GSPSO与LSPSO的加速度常数与都设为2.0（Kennedy and Eberhart，2001）。而对于CPSO，则采用（Clerc and Kennedy，2002）.PSOPC中的加速常数设为。惯性权重对于GSPSO和LSPSO的收敛来说至关重要。一个合适的惯性权重的值常常能够平衡全局和局部探究能力，并且因此能够找到一个最适宜的解。起初，这个惯性权重是个常数。然而，实验结果反应出，最好在初始阶段把惯性权重设置为一个大的值，这样是为了促进搜索空间的全局探索并且通过降低它能够得到更加精确的解（Eberhart and Shi，2001）。因此，一个衰减的惯性权重值从0.9开始，以0.4结束，由Shi和Eberhart（1998）提出来并应用在GSPSO与LSPSO。PSOPC的惯性权重从0.9开始以0.7结束。，对于CPSO，收缩因子由方程（6）给出，即。LSPSO的临近大小设定为2(Kennedy and Mendes,2002)。这个新引进的被动集聚系数对于PSOPC的搜索性能是至关重要的。实验的执行用来选择一个合适的。四个基准函数（Sphere function），（Rosenbrock function），（Rastrigin function），（Griewank function）已经用不同的值测试过了。从25次的运行结果中得到的平均测试结果列举在表4中，当时，PSOPC在函数与上产生了好值。对于函数和，最好结果产生在处，当时，PSOPC的搜索表现在函数、和中是不尽人意的（表3）。对于函数，应该小于等于0.6，要不然PSOPC在2000次的迭代后不能收敛。因此所有函数通用的值应该小于等于0.6。 表4 在线性增加情况下Rastrigin（）函数的平均适应值 我们所感兴趣的是调查含有一个线性增加的的PSOPC是否相比于固定值的能够在测试函数中能够产生一个更好的结果，因此（Rastrigin函数）在线性增加的的情况下（不同的范围）被挑选用来测试。结果在表4中列出。含有线性增加的被动集聚系数的PSOPC产生了最好的结果，的以0.4开始0.6结束。所有算法参数的设定由表5总结出。所有试验重复了50次，所有算法的固定的最大迭代次数为2000。4.3 实验结果与比较每个算法在每个测试函数上的实验结果（即运行50次函数值的平均值与标准差）在表6中列出。为了测量在PSOPC与其他三种标准PSO变体实验结果的统计差异性，我们采取了一系列的正反测试。结果在表7中列出。在处的具有自由度为49的关键值为2.0，那就意味着如果时，两者的平均值在统计上是有显著差异的。从表6中可以看出，在大多数测试函数上PSOPC的表现明显优于其他三种标准算法。唯有的两个例外是与。对于，由PSOPC产生的PSOPC优于由GSPSO与LSPSO产生的结果，但是稍微差与CPSO产生的结果。对于，GSPSO的表现微微好于PSOPC，然而PSOPC的结果远远好于LSPSO与CPSO。然而，从表7中我们可以看出，对于与，由CPSO与GSPSO分别产生的结果不明显优于PSOPC。对于，从PSOPC中得到的结果与GSPSO中得到的结果没有显著的差异。对于与，由PSOPC与CPSO产生的结果也没有显著的统计差异。可以下个结论，PSOPC在所有测试基准函数的表现上都优于LSPSO。表5 参数设置表6 PSOPC，GSPSO，LSPSO与CPSO的比较表7 PSOPC，GSPSO，LSPSO与CPSO的正反测试在处自由度为49的t分布的值对于正反测试很重要，在所有的单峰基准函数（）的表现上，CPSO的好于GSPSO。但是GSPSO的结果在多峰函数（）的表现上较好。虽然我们认为LSPSO能够如同水流“环顾流动”一样实现局部最优（Kennedy 与 Mendes，2002），但是我们的实验结果显示GSPSO与CPSO具有全局收敛特性。四个算法的搜索性能排序为（由大到小）：。 图3到12显示了搜索进展的平均值与由四种算法在函数上每种分别运行50次所得到的最优解。从这些图片中得到：对于大多数的基准函数，PSOPC在搜索的早期能够很快的找到最优解。 对于单峰函数（），收敛速率比最终优化的解更加重要，因为有许多其他方法比如基于梯度的搜索方法，专门设计用来优化单峰函数（Yao 等，1999）。从图3-6，可以看出PSOPC有比其他三个算法更快的收敛速度。 函数是多峰函数因此很难优化，因为局部极小值随着函数维数增长而以指数形式增长（Trn and Zilinskas (1989), Schwefel(1995)），函数的四种算法搜索进程由图7-12表述。根据这些图，我们知道对于大部分函数（，和），当其他三种算法被局部极小值所困住并且停滞不前时，PSOPC能够在全局极小值处收敛。唯一的例外是函数，当最大迭代次数到时GSPSO与CPSO不能完全的收敛。图3 ，Sphere function图4 ,Schwefels Problem1.2.图5 ，Schwefels Problem 2.21.图6 ，Generalized RosenBrock function图7 ，Generalized Schwefels Problem 2.26图8 , Generalized Rstrigins function图9 , Ackleys function图10 ， Generalized Griewank function 图11 ，Penalized function P8图12 ,Penalized function P165.讨论 数学上，这个被动集聚器可以被看成一个在搜索过程中加入扰动的随机变量。Fieldsend和Singh（2002）也引入了一个随机变量到标准PSO算法中，在他们论文中他们成为动荡（turbulence）。速度增加方程由下式给出： （11）这里是一个随机变量，是模型参数的绝对范围。 根据我们的经验，一个大的能够帮助微粒逃出局部极小值，但是也能够引起搜索过程的偏离。一个太小的对搜索性能没有太大的改善。的值也是一个专门的问题，例如对于某些基准函数来说这个值合适，然而对于其它函数，可能会恶化算法的搜索性能。因此，找到一个合适的值对于算法的最优解问题是必须的。 比较振荡因子，被动集聚器对于不同的优化问题有更强的适应性。对于每个个体，这个振荡是与它自己到其随机选择的邻居的距离成正比的，而不是到它外部的一个随机数。在搜索的早期阶段，个体之间的距离是很大的，因此，相应的振荡也是很大的，这样群粒子可以避免收敛到一个局部极小值。随着迭代次数的增加，个体之间的距离越来越小，因次，振荡也随之变小