混合变异算子的自适应粒子群优化算法

维普资讯 http://www.cqvip.com 第２８卷　计算机应用　Ｖｏ１．２８　２００８年６月　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｊｕｎｅ　２００８　文章编号：１００１—９０８１（２００８）Ｓ１—００２８—０３　混合变异算子的自适应粒子群优化算法　安晓会　，高岳林　（１．宁夏大学数学计算机学院，银川７５００２１；２．北方民族大学信息与系统科学研究所，银川７５００２１）　（ａｎｘｉａｏｈｕｉ＿２００７＠１６３．ｃｏｎ）　摘要：针对惯性权重线性递减粒子群算法（ＬＤＷ）不能适应复杂的非线性优化搜索过程的问题，提出了一种非　线性递减的惯性权重策略，使算法很快地进入局部搜索，并在算法中引入混合变异算子，克服算法易早熟收敛的缺　陷。对几种典型函数的测试结果表明，本文算法的收敛速度和收敛精度都明显优于ＬＤＷ算法。　关键词：粒子群算法；自适应惯性权重；变异算子；全局优化　中图分类号：ＴＰ１８２　文献标志码：Ａ　Ａｄａｐｔｉｖｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｈｙｂｒｉｄ　ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ　ＡＮ　Ｘｉａｏ　ｈｕｉ　．ＧＡ０　Ｙｕｅ　１ｉｎ　（１．Ｓｈｏｏｌ　ｏｆＭａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ，Ｎｉｎｇｘｉａ　Ｕｎｉｖｅｒｓｉｔｙ，ＹｉｎｃｈｕａｎＮｉｎｇｘｉａ　７５００２１，Ｃｈｉｎａ；　２．Ｒｅｓｅａｒｃｈ　ＩｎｓＫｔｕｔｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｓｙｓｔｅｍ　Ｃｏｍｐｕｔａｔｏｉｎ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈ　Ｎａｔｏｉｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙｉｃｎｈｕａｎ　Ｎｉｎｇｘｉａ　７５００２１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ　ｉｎｅｒｔｉａ　ｗｅｉｇｈｔ　ｗｉｔｈ　ｎｏｎｌｉｎｅａｒｌｙ　ｄｅｓｃｅｎｄｉｎｇ　ｓｔｒａｔｅｇｙ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｔｈａｔ　ｔｈｅ　Ｌｉｎｅａｒｌｙ　Ｄｅｃｒｅａｓｉｎｇ　Ｗｅｉｇｈｔ（ＬＤＷ）ｏｆ　ｐａｒｔｉｃｌｅ　ｓｗａｒｌｎ　ａｌｇｏｒｉｔｈｍ　ｃｏｕｌｄ　ｎｏｔ　ａｄａｐｔ　ｔｏ　ｔｈｅ　ｃｏｍｐｌｅｘ　ａｎｄ　ｎｏｎｌｉｎｅａｒ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｃｅｓｓ，　ｗｈｉｃｈ　ｃｏｕｌｄ　ｑｕｉｅｌｄｙ　ｐｕｔ　ｔｈｅ　ａｌｇｏｒｔｔｈｍ　ｉｎｔｏ　ｌｏｃａｌ　ｓｅａｒｃｈｉｎｇ．Ｆｕｒｔｈｅｒ　ｍｏｒｅ，ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ　ｗａｓ　ｉｎｔｒｏｄｕｃｅｄ　ｔｏ　ｏｖｅｒｃｏｍｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｔｈｅ　ｐｒｅｍａｔｕｒｅ　ａｎｄ　ｌｏｗ　ｐｒｅｃｉｓｉｏｎ　ｏｆ　ｔｈｅ　ｓｔａｎｄａｒｄ　ＰＳＯ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ＬＤＷ—ＰＳＯ　ａｎｄ　ｏｕｒ　ｍｅｔｈｏｄ　ｗｅｒｅ　ｔｅｓｔｅｄ　ｗｉｔｈ　ｉｆｖｅ　ｗｅｌｌ—ｋｎｏｗｎ　ｂｅｎｃｈｍａｒｋ　ｆｕｎｃｔｉｏｎｓ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｓｐｅｅｄ　ａｎｄ　ａｃｃｕｒａｃｙ　ｏｆ　ＯＵｒ　ｍｅｔｈｏｄ　ａｒｅ　ｓｉｇｎｉｆｌｅａｎｄｙ　ｓｕｐｅｒｉｏｒ　ｔｏ　ｔｈａｔ　ｏｆ　ＬＤＷ—ＰＳＯ．　Ｋｅｙ　ｗｏｒｄｓ：Ｓｔｎａｄａｒｄ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ（ＳＰＳＯ）；ａｄａｐｔｉｖｅ　ｉｎｅｒｔｉａ　ｗｅｉｇｈｔ；ｍｕｔａｔｉｏｎ　ｏｐｅｒａｔｏｒ；ｇｌｏｂａｌ　ｏｐｔｉｉｍｚａｔｉｏｎ　０　引言　（ｔ＋１）＝　（ｔ）＋　（ｔ＋１）　（２）　其中加速常数Ｃ　，Ｃ　是两个非负值，ｒ。，ｒ２为均匀分布于［０，１］　粒子群优化（ＰＳＯ）算法是由Ｋｅｎｎｅｄｙ和Ｅｂｅｒｈａｒｔ于１９９５　之间的随机数。为使粒子速度不致过大，可设定速度上限　年提出的一类基于群智能的随机优化算法　Ｊ，其思想来源于　，即当式（１）的１％ｌ＞　时，取｝　ｌ＝　。　为惯性　对鸟群捕食行为的研究，同遗传算法和蚁群算法相比，ＰＳＯ算　权重，它决定了粒子先前速度对当前速度的影响程度，从而　法有着算法简单、容易实现，并且可调参数少等特点，使用于　起到平衡算法全局搜索和局部搜索能力的作用。为了进一步　求解大量非线性、不可微和多峰值的复杂优化问题。由于　提高算法的性能，文献［１］提出自适应调整的策略，即：　ＰＳＯ算法的程序实现起来异常简洁，需要调整的参数也少，因　（ｔ）＝（　一　）（　ｌ眦一ｔ）／　＋　＇山　（３）　此有许多学者研究它，发现粒子群优化算法的可调参数中惯　其中，ｔ为当前进化迭代次数，　为最大进化迭代次数，　～　性权重是最重要的参数，较大的惯性权重有利于提高算法的　为初始惯性权重，　为进化至最大代数时的惯性权重。随着　全局搜索能力，而较小的惯性权重会增强算法的局部搜索能　迭代的进行，可以线性减少　的值，这使得算法在迭代初期探　力。为了找到一种能在全局搜索和局部搜索之间取得最佳平　索能力较强，可以不断搜索新的区域，然后收敛能力逐渐增　衡的惯性权重选取方法，近年来国内外的研究者作了大量的　强，使算法在可能的最优解周围精细搜索。这是目前使用最广　工作，并提出了各种改进的ＰＳＯ算法　Ｊ，并且应用于许多　泛的ＳＰＳＯ算法形式。　管理和工程领域　Ｊ。　２　混合变异算子的自适应粒子群优化算法　１　标准粒子群算法与线性权重策略　２．１　指数自适应惯性权重　假设搜索空间是ｎ维的，粒子群中第ｉ个粒子的位置用　前人实验发现粒子群优化算法的可调参数中惯性权重是　最重要的参数，较大的惯性权重有利于提高算法的全局搜索　（　，…，　）表示，第ｉ个粒子的速度表示为　＝（　能力，而较小的惯性权重会增强算法的局部搜索能力。受文献　，…，％），第　粒子迄今为止搜索的最好位置记为Ｐ　＝（Ｐ　［８］的启示本文提出以下指数递减惯性权重，以实现ＰＳＯ算　Ｐ　，…，Ｐ　），整个粒子迄今为止搜索到的最好位置记为Ｐ　＝　法增强全局搜索和局部搜索之间的平衡能力：　（Ｐｓｌ，Ｐ　，…，Ｐ　），下一代粒子的位置和速度，其第ｄ（１≤ｄ≤　＝（　～一　ｌｎｉ　）×ｅｘｐ（一４０×（∥　ｌ巾　）　）　（４）　ｎ）维根据如下方程变化：　其中ｓ为一常数，这里取２。　（ｔ＋１）＝例　（ｔ）＋Ｃｌｒｌ（Ｐ　（ｔ）一　（ｔ））＋　２．２　算法未成熟收敛的预测和处理　ｃ２ｒ２（Ｐ　（￡）一　（￡））　（１）　经分析知，如果粒子群优化算法陷入早熟收敛或者达到　收稿日期：２００７—１０—０８；修回日期：２００７—１２一ｏ４。　基金项目：中国博士后基金资助项目（２００６０６０１００１）；国家教育部社科规划项目（０６ＪＡ６３００５６）。　作者简介：安晓会（１９８１一），女，陕西渭南人，硕士研究生，主要研究方向：最优化理论、经济金融数学；　高岳林（１９６３一），男，陕西榆林人，　教授，博士，主要研究方向：优化理论、智能计算、经济金融数学、金融工程。　维普资讯 http://www.cqvip.com

６月　安晓会等：混合变异算子的自适应粒子群优化算法　２９　全局收敛，粒子群中的粒子将聚集在搜索空间的一个或几个　粒子群中的部分粒子采用２个非自然规则遗传操作算子‘　ｌｏ｜　特定位置，此时群体适应度方差　等于零。但是，仅借助适应　进行变异，这样通过提高局部精确搜索能力和破坏群体个体　度方差等于零不能区别早熟收敛与全局收敛，还需进一步判　的单一性两种策略可改进算法中的未成熟收敛现象。具体如　断算法此时得到的最优解是否为理论全局最优解或期望最优　下：　解，如果此时已经得到全局最优，则可认为算法达到全局收　１）当前最优个体的微变异算子。本文对当前最优个体　敛，否则，这表明算法陷入局部最优。　ｇ　采用增加随机扰动的方法进行变异，记变异概率为Ｐ　，　本节采用群体适应度方差和粒子聚集距离来预测非成熟　Ｐ　∈［０．１，０．３］，对ｇ　进行微变异，即对个体只选取一位基　收敛的产生，现在分别给出它们的定义。　因进行变异：ｇ　。＝ｇ　。　Ｘ（１＋０．５　田），田是服从Ｇａｕｓｓ（０，　定义１【７１　设粒子群的粒子数目为ｎ　为第ｉ个粒子的　１）分布的随机变量。　适应度　为粒子群目前的平均适应度，　为粒子群的群体　２）低适应度个体高变异算子。选取当前种群中的若干个　适应度方差，则　可以定义为：　最差个体，以大大高于Ｐ　的变异概率进行变异，在定义域内　２＝骞［＝ｔ　毕ｄ］。　（５）　且在一定的范围内随机扰动取值，高变异概率可选择在　０．７—０．８。　其中／是归一化定标因子，起作用是限制ｃｒ２的大小　可以任　２．３算法的具体步骤　意取值，只需注意两个条件：１）归一化后，整个粒子群Ｉ　一　１）随机初始化粒子群中粒子的位置和速度；　Ｉ的最大值不大于１；２）随算法的进化而改变，在本文的算　２）将粒子的Ｐ　设置为当前位置，Ｐ　设置为群体中最佳粒　法中　的取值采用如下公式：　ｒ：』ｍａｘ｛Ｉ　一　ｖｓ　Ｉ｝，ｍａｘ｛Ｉ　一　Ｉ｝＞１　ｆ６　子的位置；　【１３）判断算法收敛准则是否满足，若满足，转５）；否则，执　，　其他　定义１表明，群体适应度方差　反映的是粒子群中所有　行４）；　粒子的“收敛”程度。　越小，则粒子群趋于收敛；反之，粒子　４）对粒子群中的所有粒子执行如下操作：　群则处于随机搜索阶段。　①根据式（１）、（２）更新粒子的位置与速度；②根据式　定义２　粒子平均聚集距离和最大聚集距离的定义分　（５）一（８）计算适应度方差与平均聚集距离及最大聚集距　别为：　离，判断算法是否陷入局部收敛。若是，则对群体中的部分粒　子执行上述变异规则。转２）；　Ｍ　ｅ０ｎＤｉｓｔ＝上　√　（ｐ　一　）２５）输出Ｐ　，算法运行结束。　生—————一　（７）　３　数值试验和结果分析　／二　ＭａｘＤｉｓｔ＝ｍａｘ＾／　（　一　）　；ｉ＝１，２，…，ｍ（８）　为了叙述方便，将本文的算法记为ＡＰＳＯ，本节采用表１　其中ｍ为群体的粒子数，ｎ为粒子的维数，Ｐ　为粒子群目前搜　中的函数来测试ＳＰＳＯ和ＡＰＳＯ算法，在试验中，我们取ｃ．＝　索到的最优位置，　为每个粒子目前搜索到的最优位置。　ｃ２＝１．７，埘一＝０．９，Ｗｍｌｎ＝０．４，粒子数为３Ｏ。每个函数在　在粒子群优化运算过程中，当适应度方差趋于零而且平　ＳＰＳＯ算法和ＡＰＳＯ算法下各运行２Ｏ次，取最佳适应度函数值　均聚集距离大于最大聚集距离时，此时认为粒子达到全局收　均值，迭代次数ｎ不同时的具体结果比较见表２—４。　敛，当适应度方差趋于零而且平均聚集距离小于最大聚集距　为了进一步比较两算法的性能，图３—５给出每个函数的　离时认为粒子陷入局部收敛。当粒子陷入局部收敛时，我们对　平均最佳适应度进化曲线。　表１　５个标准测试函数　表２　Ｓｐｈｅｒｅ和Ｒａｓｔｒｉｇｒｉｎ函数　表３　Ｇｒｉｅｗ￣＇ｌｋ和Ｓｈｏ．ｆｅｒ＇ｓｆ＇｝函数　Ｓｐｈｅｒｅ　ＳＰＳＯ　ＡＰＳＯ　Ｒａｓｔｒｉｇｒｉｎ　ＳＰＳＯ　ＡＰＳＯ　９ｒｉｅｗａｎｋ　ＳＰＳ０　ＡＰＳ０　Ｓｈａｆｆｅｒ＇ｓｆ７　ＳＰＳ０　ＡＰＳ０　＝１００　１．６１４４ｅ—Ｄ４　６．７８４０ｅ－５５　ｎ＝１Ｏ　９１．１６６７　０．０７９０　ｎ＝２Ｏ　Ｏ．Ｏ２６２　５．４９１　１ｅ一１Ｏ　ｎ＝１ｏｏ　Ｏ．ｏｏ５Ｏ　４．２５８９ｅ一１２　＝２ｏｏ　１．ｏｏ２５ｅ－０９　２．４９７９ｅ一１ｏｏ　ｎ＝３Ｏ　５Ｏ．１１１　１　９．２３３２ｅ．１１　ｎ＝３Ｏ　Ｏ．９ｏｏ８　５．１９７６ｅ—ｌ１　ｎ＝２００　３．５７２６ｅ－０－６　５．１７９９ｅ－２３　ｎ＝４００　３．９１６３ｅ－２０　２．３９３５ｅ一１６６　ｎ＝５Ｏ　３７．８９０４　３．９０８０ｅ．１５　ｎ＝５０　０．５２３４　２．２５９３ｅ一１５　ｎ＝３００　４．１０１４ｅ－９　８．３１４０ｅ－２７　ｎ＝５００　５．９７４１ｅ－２５　１．７７７５ｅ一１７４　ｎ＝８０　１７．４４９５　０　ｎ＝１ｏｏ　０．１４１　６　０　ｎ＝５００　７．２０３３ｅ一１５　１．１７２　１ｅ－５５　ｎ＝８ｏｏ　２．１３８Ｏｅ－３９　０　ｎ＝１ｏｏ　１４．５１２７　Ｏ　ｎ＝２ｏｏ　Ｏ．Ｏ９１　６　Ｏ　ｎ＝８００　５．５４４６ｅ－２３　０　维普资讯 http://www.cqvip.com 计算机应用　２００８盎　表４　Ｓｈａｆｆｅｒ＇ｓ函数　口　≥　器　詈　Ｉｍｒａｆｉｏｎ　图１　Ｓｐｈｅｒｅ函数平均最佳适应度进化曲线　Ｉｔｅｒａｔｉｏｎ　图２　Ｒａｓｔｒｉｇｒｉｎ函数平均最佳适应度进化曲线　懿　鲁　詈　＞　器　詈　图３　Ｓｈａｆｆｅｒ＇ｓ　ｆ７函数平均最佳适应度进化曲线　从图表数据可以看出：对于给定测试函数，ＳＰＳＯ算法很　快出现了早熟收敛情况，而且收敛速度缓慢；ＡＰＳＯ算法全局　收敛速度远快于ＳＰＳＯ算法，在收敛精度方面也远高于ＳＰＳＯ　算法。本文算法在所有函数优化问题中，都具有较快的全局　收敛速度和强大的全局搜索能力，能有效地避免粒子群优化　算法的早熟收敛问题。　４　结语　本文在线性递减惯性权重的基础上，提出了一种非线性　递减自适应惯性权重，在算法的早期通过加速惯性权值的递　减速度让算法较快地进入局部搜索，根据群体的适应度方差　及平均聚集距离来判断算法是否陷入局部最优解。若陷入局　部最优解，我们对群体中的部分粒子按不同的概率进行变异，　提出了一种改进的粒子群算法（ＡＰＳＯ），从而不仅使算法摆脱　后期陷入局部最优点的束缚，又保持了前期搜索速度快的特　性，通过五个例子的测试，表明这种改进的ＰＳＯ算法效果是　很好的。　主　詈　＞　器　墨　Ｉｍｍｆｉｏｎ　图４　Ｇｆｉｅｗａｎｋ函数平均最佳适应度进化曲线　警　器　主　詈　＞　器　罟　Ｉ￣ｍｆｉｏｎ　图５　Ｓｃｈａｆｆｃｒ＇ｓ函数平均最佳适应度进化曲线　参考文献：　【１］ＥＢＥＲＨＡＲＴ　Ｒ　Ｃ，ＳＨＩ　Ｙ　Ｈ．Ｐａｒｔｉｃｌｅ　８ＷａｌＴｎ　ｏｐｔｉｍｉｚａｔｉｏｎ：ｄｅｖｅｌｏｐ—　ｍｅｎｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　ｒｅｓｏｕｒｃｅ８【Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ．Ｐｉｓｃａｔａｗａｙ，ＵＳＡ：ＩＥＥＥ　Ｓｅｒｖｉｃｅ　Ｃｅｎｔｅｒ，２００１：８１—８６．　【２］　陈君波，叶庆卫，周宇，等．一种新的混合变异粒子群算法【Ｊ］．　计算机工程与应用，２００７，４３（７）：５９—６１．　【３］　张世勇．一种新的混合粒子群优化算法【Ｊ］．重庆工商大学学　报：自然科学版，２００７，２４（３）：２４１—２４５．　【４］　刘建华，樊晓平，瞿志华．一种惯性权重动态调整的新型粒子群　算法【Ｊ］．计算机工程与应用，２００７，４３（７）：６８—７０．　【５］　陈贵敏，贾建援，韩琪．粒子群优化算法的惯性权重递减策略　研究【Ｊ］．西安交通大学学报，２００６，４０（１）：５３—５７．　【６］　夏桂梅，曾建湖．粒子群算法的研究现状及发展趋势【Ｊ］．山西　师范大学学报，２００５，１９（１）：２３—２５．　【７］　吕振萧，候志荣．自适应变异的粒子群优化算法【Ｊ］．电子学　报，２００４，３２（３）：４１６—４２０．　【８］　雷开友．粒子群算法及其应用研究【Ｄ］．重庆：西南大学，２００６．　【９］　ＦＡＬＫ　Ｊ　Ｅ，ＳＯＬＡＮＤ　Ｒ　Ｍ．Ａｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｅｐａｒａｂｌｅ　ｎｏｎｅｏｎｖｅｘ　ｐｒｏｇｒａｍｍｉｎｇ　ｐｒｏｂｌｅｍｓ【Ｊ］．Ｍａｎａｇｅｍｅｎｔ　Ｓｃｉｅｎｃｅ，１９６９，１５（９）：５５０　—５６９．　【１Ｏ］李旭东，涂车生．遗传算法中引入非自然规则的研究【Ｊ］．计算　机工程与应用，２００３，３（４）：８７—８９．