自适应速度的粒子群优化算法求解约束优化问题翻译.doc

自适应速度的粒子群优化算法求解约束优化问题鲁海燕 陈玮琪摘要：粒子群优化(PSO)最初是作为一个无约束最优化开发的技术，因此缺乏一个明确处理约束的机制。当用PSO解决约束优化问题（COPs）时，现有的研究主要集中在如何处理约束和约束在固有的粒子群搜索机制上的影响几乎已经没有了的问题上。出于这一事实，在本文中,我们主要研究如何利用约束的影响（或者关于可行域的知识）来改善粒子的优化能力。根据这些研究,我们提出一个修改算法,称为自适应速度粒子群优化(SAVPSO)来解决COPs。为了解决约束问题，在SAVPSO中，我们采用了最近提出来的动态目标约束处理法（DOCHM），这实质上是集成SAVPSO固有的搜索机制的组成部分，即DOCHM+SAVPSO。综合SAVPSO的性能在一个著名的基准测试套件，实验结果表明，适当地利用对可行域的知识可以大大提高解决COP底层算法的性能。 关键词：约束优化，粒子群优化算法，随机算法，进化算法，非线性规划，约束处理机制1、介绍许多现实世界的应用，如工程设计，超大规模集成电路设计，结构优化，经济，位置和分配问题1，包括那些必须有效解决、带有难度的约束优化问题。由于这些问题的复杂性，确定性优化方法，如：可行方向和广义梯度下降方法，即使这些方法的连续性和可微性做出了强有力的假设目标函数1,2，却往往都无法提供可行的解决方案。这为进化算法提供了一个机会，如遗传算法，进化策略，进化规划和粒子群优化（PSO），这些已在过去几年中成功地应用并解决了COPs。PSO算法是基于种群的、全局性的，随机优化算法由Kennedy和Eberhart于1995年开发8,9。由于在执行难优化任务时体现出来的简单性和有效性，它已经越来越普及。然而，就像前面提到的其他随机算法，PSO缺乏明确的约束处理机制。进化算法已经提出了一些约束处理机制3,10。近年来，一些研究一直致力于把一些约束处理机制合并到PSO算法中去解决COPs4,6,11-14。 然而，大部分的研究都集中在COPs的“处理约束”问题上，很少的注意力被花在研究约束对粒子的飞行模式的影响。通过这一事实的启发，在这项工作中，我们不仅引入适当的约束处理技术到所提出的算法中，同时也探讨在约束的影响下，如何提高其固有的算法机制。PSO算法模拟的是粒子在没有约束（除了绑定的约束）的搜索空间的飞行模式（或者搜索机制），因此，它不能直接适用于COPs。由于PSO算法没有考虑到账户约束对搜索机制的影响，它通常难以把集中粒子在可行区域的大致区域（特别是当可行域很小时），所以损害了该算法的优化能力。因此，我们想象一下，如果我们能适当地把约束的影响融入到PSO算法的搜索机制，那么粒子群算法的优化能力将得到改善。为此，在本文中，我们主要研究的是限制对粒子飞行模式（或搜索机制）的潜在影响，探索方法来把这一影响合并到PSO的内在算法机制中，并由此提出一个简单的合并策略，就像我们提到的自适应速度粒子群优化(SAVPSO)一样。这个名字是从属性派生的，我们的算法中，每个粒子都有能力根据可行域的一些特性自适应地调整它的速度。另外，为解决直接约束，当把SAVPSO 加入到COPs时，一些适当的约束处理机制是必须的。就像之前提到的，已经有过一些方法用于处理PSO约束。一种常用且简单的方法就是通过罚函数，它将约束优化问题转换成无约束优化问题15。这个方法能很好的解决一些问题，但是它需要罚参数仔细的调优，这对它原问题来说本来就是一个困难的优化问题16。另一种用于约束处理方法就是保留可行办法，它改编自17Huand Eberhart12。这种方法需要对可行区域内的颗粒初始化，初始化处理可能需要很长的时间，并可能对一些问题难以实现。最近，一些研究人员提出了一些混合粒子群算法，它们是一些约束处理机制的组合13,18。在本文中，我们采纳我们最近提出来的动态目标约束处理法(DOCHM)19。DOCHM在SAVPSO固有的搜索机制上运行，在某些方面体现出对约束的影响。DOCHM主要的目的就是迫使粒子去搜索可行域，这是通过最小化被视为第一目标进行优化的距离函数，并优化了原始目标（原问题），这被视为DOCHM的第二目标。本文的其余部分安排如下：第2节介绍我们感兴趣的问题；第3节描述了标准粒子群算法，并分析其在COPs中的不适用性方面 ；在第4节中，我们呈现我们所提出的SAVPSO，包括DOCHM的简要说明；在第5节中，实验是用13个众所周知的长凳标记功能来评估我们提出的SAVPSO的性能，并与其他算法提供的结果进行了比较；最后，我们的结论和未来的工作中在第6节中给出。 2、 问题陈述约束优化问题（COPs）或者一般的非线性规划问题(NLPs) 明确的表示如下： minimize （1）使得： （2） （3）其中是解的向量,就如，q是不等式约束的数目。通过限制范围内的参数，搜索空间S被定义为一个n维空间 （4）并且，可行域是域中满足不等式和等式的区域。当不等式约束满足时，我们说它是活跃的。所有的等式约束（无论所使用的的值）都被说成是中的所有活跃点。由于在专业文献上进化算法的普遍做法，等式约束转化为不等式约束的形式 （5）是一个允许公差（一个非常小的正值）。当 时，解被认为是可行的。3、 POS和它的不适应性对于COPs的作用 自从19958,9年的介绍之后，PSO算法经历了很多变体，其中一些已被证明的算法使得性能方面有了真正的改善20。在这一节，我们用下面PSO典型的变体作为一个例子，它被我们作为标准的PSO（SPSO是它的缩写） 来分析SPSO算法对于COPs不适应性的方面。在一个维的搜索空间，假设粒子群是由个粒子组成。第个粒子实际上是一个维矢量，粒子的速率也是一个维矢量。访问第个粒子的最有位置是中的点，表示为。设为整个粒子群中粒子达到最优位置的标志，为迭代计数器。然后，在SOPSO中，粒子群根据下面的更新方程式来操作21-23： （6） （7）在这里，是粒子的标志，表示粒子的第个分量，是一个被称为惯性权重的参数，都是正的常数，分别被称为认知参数和社会参数，均匀分布于0,1之间的随机参数，表示为。把第维作为搜索空间，右手侧（6）由三部分组成24，第一部分是动力部分，第二部分是认知部分，代表了自己个人的想法，即从自己的飞行经验中学习。第三部分是社会部分，代表了粒子之间的协作，即从群体中学习飞行经验。事实上，最后两部分的和，即，能够被认为，当时，对位于周围有前途的区域，一个潜在的位置最新获得的速度项。当第一部分能够被视为具有可信初速度的粒子，或者最新获得速度的修改项时，这些都将促使粒子偏离潜在位置。于是，在当前的速度下，求出这两项的和。然而，这两项不考虑可行域的影响。比如，这两部分中的其中一个或者两者可能太大以至于相应的粒子会远离可行域。这是提出的PSO在求解COPs的巨大困难之一。因此 ，我们预计，如果约束的影响得到妥善利用，则算法的优化能力可能会大大改善。4、 我们的方法 在这部分，我们将详细介绍我们的方法，把约束影响引入到PSO的固有搜索机制中。4.1 PSO搜索机制上约束的影响 回想一下第三部分，我们把速度表达式（6）拆分为两项，并分别解释了它们的隐含意义。我们的讨论表明，PSO的搜索机制没有考虑约束条件的影响或者关于可行域的知识。在本文中，我们将研究如何适当地利用这种撞击或者知识来提高解决COPs问题而由此产生的算法的性能。为此，我们首先分析了可能影响粒子搜索方式的知识（关于可行域）。我们推测下面可行域的三个特点，它们被认为是一些关于可行域的知识，对粒子搜索方式的影响负责。（1） 可行域的位置与搜索空间有关；（2） 可行域的连通性和形状；（3） 可行域与搜索空间的比值。特点（1）意味着颗粒应该首先搜索可行域，从而找出可行区域内的最优解。因此，可行的区域可以被看作是粒子躺在可行区域之外的目标。在我们算法的稍后讨论中，这种影响是通过DOCHM（看4.4）来反映和实现的，一种在19中最近被我们提出来的约束处理法。特性（2）表明，颗粒应该有比较强的开拓能力，从而提高他们的跳出局部最优的能力。正如我们将在后面的4.2，4.3和4.5看到的一样，我们可能会通过选择适当的参数值，实现这一目标。特征描述（3）中的比率| F |/| S|反映了可行区域的相对大小。我们猜想，如果我们能有效地利用这种知识到我们的算法中，来适当地修改每个粒子的速度，那么我们算法的优化能力可能会得到改善。4.2 自适应速度的粒子群算法基于以上的分析，基于上面的分析，我们修改速度的更新方程以如下方式，我们设，因此，最新获得的速度项能够使得粒子飞向位于之间的一个位置。因此，粒子不会冲离可行域太远。同时，我们用标记为代替动力项，标志代表标志，它表示在维中的飞行方向。换句话而言，粒子以前的速度经验只限于飞行方向，而它的幅度由下式决定，它是根据可行域的影响而来，是参数，是在1,N范围内均匀分布的随机整数，表示为。请注意，从上面的假设看，两者接近或者在可行域中，因此，大致反映了可行区域的大小。因此，从可知，粒子不会从可行域偏离太远；此外，的值可以自适应地随群搜索范围的变化而变化。根据以上的讨论，我们得出改进的PSO算法，我们称之为自适应速度PSO（SAVPSO的简称）。在SAVPSO，该群是根据下面的公式进行更新操作： （8） （9），是缩放参数，标志代表标志4.3 参数分析 在本小节中，我们做了参数的直观分析。 比较式子（6）和（8），我们看到在（8）的右边，一项被设计成类似可以在之间的近似区域集中搜索的粒子，而一项被设计成类似相应的速度反映约束的影响，或利用有关可行域的知识。请注意，在搜索过程的某些阶段中，在DOCHM的影响下，粒子的最优位置将位于可行地区内或周围，然后从统计的观点，可以大致地反映可行域的尺寸，而是一个缩放参数。因此，我们假设，那么，速度粗略地与可行域的大小匹配。假设，那么，速度是增大的，因此群的搜索范围被放大，因此群的探索能力得到提高，但收敛速度降低。假如，那么，速度是减小的，因此群的搜索范围缩小，该群的开发能力得到提高，并且算法收敛速度快，而且很容易得到陷入局部最优。为了获得全局最优解，粒子不仅需要较强的开拓能力，以跳出局部最优的，还需要不错开采能力，从而在可行区域内找出全局最优。因此，根据意义上面的分析，我们认为在SAVPSO的开采和探索能力之间的找出一个平衡是合理的。要做到这一点，我们可以简单地取。或者，我们可以设置，是一个参数，。注意，假如，则，的平均值是1。假如，的平均值小于1。就如我们所看到的第五部分，当时，我们的算法可以为比值大的那些问题获得显着的好结果。然而，这是不适合比值小情况下的问题。因此，根据参数的分析，我们建议，如果取一个较小的值，例如，那么，对于那些比值小的问题，算法的性能会有比较大的提高。事实上，另外的实验结果（见第五部分的表4）表明，（在这种情况下的平均值）确实改善了算法对于这些问题的性能，这与我们的参数分析是一致。4.4 约束处理法DOCHM是最近在19中，我们提出的一个基于PSO的约束处理技术。通过定义一个距离函数，DOCHM将原问题转化为一个双目标优化问题，被视为第一目标，为第二目标。对于可行域，有几种方法来构造距离函数，一种简单的方法如下： （10）可知，是违反约束的总和，因此，当时，。此外，的所有最优解构成了原问题的可行区域。显然，飞行颗粒朝可行区域相当于优化，并且因此上述的特性（1）可以通过DOCHM反映。值得注意的是，尽管需要惩罚函数的形式，但是，由于它是在传统的惩罚函数法上定义，所以它不被使用。它仅仅是用来决定粒子是否在可行域内和粒子有多接近可行域。它可以从（10）中看出，没有额外的参数涉及DOCHM。具体而言，动态目标约束的处理方法适用于以下方式。对辅助目标函数的和实际的目标函数构成的两个函数来进行优化。假如粒子在可行域外，粒子将把作为优化目标。否则，该颗粒将不是最优化的实际目标函数。在优化过程中，假如粒子离开可行域，它将再一次优化。因此，该粒子具有独立地动态调整他们彼此之间优化目标的能力。此外，尽管DOCHM的主要目的是推动粒子进入可行域，但是在可行区域内，它没有严格的限制粒子。这是有利于改善粒子的探索能力。 DOCHM的方法在表1中有描述。DOCHM是在这个意义上的一般约束处理技术，它可以结合到各种基于PSO的算法中。DOCHM主要集中在有效反射粒子的飞行模式在可行域上的特性（1）的影响，而SAVPSO目的是提高在可行区域内的优化行为。这可以从实验第五部分中可以看出。4.5解决COP的集成SAVPSO在某些情况下，可行区域的边界可位于搜索空间中非常接近的参数边界和/或.因此，在解决过程中，可行域边界附近的一些粒子会有违反参数化约束的事情发生。为了克服这个问题，我们采用在19中用到的技术，重新随机评估，使得在分量上的大小介于所有粒子在第分量上的均值和参数范围之间，即 （11），是在0,1中的一个常数。为了使该技术适用于一般的问题，我们在本文中所进行的实验设置为a =1。 总之，表2描述了SAVPSO集成算法的伪代码，是迭代的最大数目。注意，集成的SAVPSO结合DOCHM作为其搜索机制的组成部分。5、 实验与讨论为了评估该算法的性能，我们在由Runarsson和yao16扩展的著名的Michalewicz测试函数10进上行了一系列的实验。这些选定的测试功能包括具有在进化算法中代表“难”的全局优化问题的特点。此外，我们比较结果发现，一些最近提出的基于PSO算法增强了一些额外的运营商和约束处理机制4,12,13,18,25。这些测试函数的主要特征总结在表3中，详细功能信息，请参阅在本文的末尾附录。在表3中，在所指示的第三列中的每个值是可行区域与搜索空间的整个之间的比例的估计值，是可行的解的数目，是随机生成的解决方案的总数量。在这项工作中，=1,000,000。问题，和是最大化问题。它们被转化成的最小化问题。所有等式约束已转化成不等式约束，使用违规的程度。用50个粒子，最大的迭代数量设置为1000每运行，算法中30个独立运行的粒子在每个问题中都被执行。表3中的参数是常数在动态选择策略中挑选的常数，可见式子8。的值是根据在第四部分中的讨论挑选出来的，和是两个例外。由于这两个函数趋于找到算法中的局部极小，我们设。所有实验用MATLAB执行。表4总结了在上述实验的设置情况下，我们的SAVPSO算法的实验结果，其中“选项”代表每个已知问题的“最优”解，“标准”代表所获得的30个独立运行的统计数据“标准偏差”。但应指出，所得到的解决方案是完全可行的解决方案，这实际上是由我们算法的固有搜索机制来保证的。从表4可以看出，SAVPSO算法的大部分问题会产生相当精确的解决方案和标准偏差是非常小。请注意，通过一定程度的违反，所有等式约束都被转换成不等式约束。由于这种近似，一些解决方案可能比已知的最优解更好。比如 ，在SAVPSO中给出的最好的目标值是5126.484153，它比最优值5126.4981好。其他例子包括，和。问题有两个最小局部：-13.000和-12.453125，30个独立运行中只有3个被困到两个局部极小。问题包含于那些难以解决问题的进化算法中。具体而言，是一个困难的惩罚函数法的问题，而涉及等式约束。上述实验表明，我们的算法可以为具有相当大的比值的问题获得大幅度地良好的结果。但是它不适合具有相对小的比值的问题（例子）。因此，根据之前对参数的分析，用（的平均值是1/2），我们这些实验进行额外的分析，相应的结果在表4中举出。从表4中可以看出，这个参数设置确实提高了我们的算法对这些问题的性能，这与我们前面的参数分析相一致。请注意，从表3中可以看出，可行区域的大小非常小（几乎为零），这将使得基于PSO算法的性能恶化。为了克服这个困难，我们进行了和其他实验设置保持不变额外的实验，产生显著地更好的结果，这都包含在表4中由符号*所示的行。这个结果表明，假如可行域很小，一个用常数的搜索机制可能比用随机数的结果好。这是因为随机加大了粒子移动的随机性，这使得粒子很难在可行域中进行集中搜索，因此，损害了所使用算法的优化能力。我们的比较结果不同如于之前的基于PSO算法，结果呈现在表5和6中。就如表5中所示，与Toscano 和 Coello算法13比较，在本文的其余部分记为CHMPSO，我们的结果中的所有都是最好的，除了两个问题（）的最好方面，平均值和最坏的结果。即使是这两个例外，我们的算法发现一个问题的最优解（）和另一个（）的最好结果比由CHMPSO获得的更好。关于成本计算用适应度函数评价的数量来衡量，对于每一个问题，我们最多只有FFE，然而，在CHMPSO中被执行了（40个粒子进行了8500次迭代）。对于问题，我们的算法找到所有30次最佳的解决方案，CHMPSO没有找到任何关于问题，最优方案始终只是问题g08和g12。对于问题g05,g10和g13，我们的算法明显优于CHMPSO。对于在基准上所有涉及等式约束（g03，g05，g11和g13）的所有问题，我们的算法已经找到比最优解更好的结果。这是由不平等近似等式，匿名提到的。表6总结出了我们的算法与四个其他最近提出的基于PSO算法比较得到的最好结果。这四种算法,Hu和Eberhartd的 PSO需要一个初始化的粒子在可行域内部,这在某些情况12下可能需要非常高计算成本,导致其被禁止在真实的应用程序中。张和谢的DEPSO18是一种混合粒子群优化算法，它使用类似于差分进化26的复制操作。在18中DEPSO的FFE最大数量为1,400,000。由 Zavala等人提出的PESO25也是一种混合粒子群优化算法，它集成了两个扰动运营商，在25中每个问题花费350,000 FFE在实验中。由Dong4等人提出的CPSO，它嵌入了基于优先级的合适的约束排序方法和动态邻域到标准的PSO算法中，与CPSO相关的实验费用最多为50,000FFE。从表6可以看出，我们的算法在测试函数的最优结果上优于或者与上述PSO，DEPSO和CPSO算法匹配。比较PESO，我的最好结果对于问题g02和g13要更好，对问题g07，g09和g10稍微差一点，其他问题都是差不多的。上述实验结果显示，DOCHM和SAVPSO的综合效应有助于综合SAVPSO的性能，即：DOCHM+ SAVPSO。文献19中的发展表明，DOCHM确实有助于良好的底层算法的良好性能。为了揭示SAVPSO对于DOCHM+ SAVPSO更好的性能的独立贡献，我们把DOCHM+