文章编号：１００７—１４２３（２０１４）１４—０００８—０４ ＤＯＩ：１０．３９６９６．ｉｓｓｎ．１００７—１４２３．２０１４．１４．００２ 一种改进的粒子群算法稳定性证明及其应用 焦国辉 （太原师范学院计算机中心，太原０３０１２） 摘要： 针对改进的粒子群算法缺乏理论上稳定性证明及其相应的参数选择问题．利用李雅普诺夫稳定性理论对个体决策粒 子群算法给予稳定性证明，并给出相应的参数选择方式，改变传统粒子群算法只能从仿真角度说明该算法的稳定性。 采用几个常用的测试函数进行仿真实验，与其他改进的粒子群算法相比，结果表明该算法具有更好的性能。 关键词： 粒子群算法：个体决策；李雅普诺夫函数；稳定性 基金项目： 国家自然科学基金（Ｎｏ．６０９７５７４）、国家青年科学基金（Ｎｏ．６１０３０５３） ０ 引言 粒子群算法是一种基于群体智能的随机优化算 法川．由于其结构简单．运算速度快，且不需要领域知 法某一特性 本文通过李雅普诺夫稳定性理论对个体 决策粒子群算法给予了稳定性证明．并给出了相应的 参数选择方式．为以后其他改进粒子群算法稳定性证 识．一经提出便引起许多学者广泛的研究兴趣。现在已 经广泛应用于神经网络训练［２１、模式识别网、多目标优化［４３ 等方面。粒子群算法提出以后，许多学者从收敛性、稳 定性等方面对标准粒子群算法进行了研究。Ｏｚｅａｎ和 Ｍ０ｈａｎ首次对标准粒子群算法从理论方面进行了分 析［５１．Ｔｒｅ１ｅａ对标准粒子群算法的收敛性进行了分析嘲． 明和参数选择提供一种思路。 １ 个体决策粒子群算法 设Ｐ（ｍ）＝（ｐｊ（ｔ－ｓ），ｐｉ（ｔ—ｓ—１），…，ｐｊ（ｔ））为粒子 从 ｓ到ｔ代的个体历史位置．把它对应的适应值按照大小 （Ｐ（ｍ））＝ａ唱ｍａｘ （ （ｍ） ＝１，２，…，ｎ）｝ 进行排序 为对应的最差粒子适应值。 （Ｐ（ｍ））＝ａｒｇ ｍｉｎ［ｆ（Ｐｉ（ｍ）， ＝并在此基础上提出了该算法收敛性和稳定性较好时的 参数选择方式。Ｍ．１ｉａｎｇ对标准粒子群算法进行了随机 １，２…ｎ）｝为对应的最优粒子适应值。则粒子／在第ｔ 代的性能评价指标为： 收敛性分析【７Ｊ．证明了算法收敛的条件及参数选择范 围 Ｊ．Ｌ．Ｆｅｍ等证明粒子运动状态和停滞状态的稳定区 域是一样的恻 针对粒子群算法容易陷入局部最优这一 缺点．研究者提出了许多改进的算法，但是很少有人针 对改进的粒子群算法从理论上给出稳定性证明及参数 ｆ１，ｉｆ（ｆ￣ （Ｐ（ ）） （Ｐ（ ）））， 。 ｛＼ 急 （Ｐ（ｆ）） （Ｐ（ｔ））’……… ｅ 由式（１）可以看出在第ｔ代中，历史适应值越优的 粒子，它的性能评价指标ｓｃ０ （ｆ）越大，而历史适应值 越差的粒子，它的性能评价指标ｓｃｏｒｅｊ（ｔ）］ｇｇ．：ｂ。性能评 价指标ｓｃｏ （￡）主要由粒子自身的个体适应值来确定， 这就等于给各个粒子在ｔ代的个体适应值进行了排序， 选择方式．只能从仿真实验中分析算法稳定性较好．从 经验中给出参数选择方式．即使有些学者针对标准粒 子群算法的收敛性及参数选择给予证明．也是针对算 ＠ 现代计算机２０１４．０５中 使个体历史适应值越好的粒子性能越好，反之亦然。 下面步骤就是根据性能评价指标来确定权重。由于 决策个体的能力、经验、水平等方面的差异，隐藏他们 在决策过程中的作用是不同的，这种差异可以用决策 者的权重来表示： ｓｃｏｒｅ（ｔ） ＝ ．．．．．．．．．．．．．．．． — ——．．．！ ！．．．．．． ．．．．． —． ．．．．．．．．．．．．．．一 ｓｃｏｒｅ１（ｆ）￥ｃｏｒ￣２（ｔ）．．．￥ＣＯＦｅ （ （２） ｅ ＋ｅ ＋…＋ｅ 决策后的个体历史最优位置为： Ｐ，ｇｔ）：∑Ｕｊ￣ｐｊ（ｔ） （３） ｌ 对照标准粒子群算法．个体决策粒子群算法的进 化方程可表示为： ｖｊｋ（ｔ＋１）＝ ｗｖ，ｋ（ｔ）＋ｃ１ｒｌ（ｐｍ（ｔ）－ｘｊ￣（ｔ））＋ｃ２ｒ２（ｐ （ｆ）一ｘｊｋ（ｔ））（４） ｘｉｋ（ｔ＋１） （￡） ｍ（￡＋１） （５） 其中ｘｉｋ为粒子 的当前位置；ｖｊｋ为粒子的当前速 度；Ｐｊｋ为粒子 的最优位置，称为个体历史最优位置。 Ｐ 为全局历史最优位置。其中 ＝１，２，…，ｍ，ｍ为粒子 的个数， ＝１，２，…，ｎ，凡为解空间的维数，ｔ为粒子的当 前进化代数．ｗ为惯性权重．具有平衡全局和局部搜索能 力的作用，介于『０，１］之间。ｃ。与ｃ：为学习因子，通常在 ［０，２１之间取值，ｃ 具有调节粒子向自身最优位置靠近的 作用，Ｃ 具有调节粒子向群体历史最优位置靠近的作用， ｒ广ｕ（ｏ，１），ｒ￣－Ｕ（Ｏ，１）为两个相互的随机数。 ２ 稳定性证明 由Ｌｖａｐｕｎｏｖ第二方法稳定性定义和定理 把个体 决策粒子群算法（４）与（５）从理论上进行了稳定性证明 及参数选择。若设： １＝ｃ ｌｒｌ， ２＝ｃ２ｒ２， ＝ １＋ ２ ！ ‘ （ ） （ｔ）－ｘ （ｆ—１）］十 ［纽 监 。（ ）］ 下面，将利用Ｌｖ印ｕｎｏｖ第二方法推导个体决策群 子算法的稳定性：取误差变量ｅｉ（ ） （ｆ）一ＰＱ，并假设 保持不变，即 ０。取Ｌｙａｐｕｎｏｖ函数（能量函数）。￣３ｉ（ ） Ｔ： ｅ （ｆ）ｅｉ（ ）对其求导，则有： Ｖｉ（ ）＝［ｅ （ｔ）］ｒｅ （ｔ） ＝ＩＸ （ｔ）－Ｐｑ］ （ｔ）－ＰＱ］ ＝Ｉｘ （ｔ）兀 （ ）一ＰＱ］ ＝｛ｗ［ｘ （ｔ）－ｘ （ｔ－１）］＋ ［尸： （ｔ）］ （ｔ）－Ｐｑ］ ＝ （ｔ）－－Ｘ （ｔ－１）兀 （ｔ）－ＰＱ３－￣１１ （ｔ）ｌｌ 由范数定义： ≤Ｉｌｘｌｌ Ｉｌｙｌｌ，因此有： ［筏（￡） ；（￡一１）］ｒｅ （￡）≤ＩＩｘ （￡） （￡～１）ｌｌｑｌｅ （ｔ）ｌｌ 所以∞≤ 由此可以得出个体决策粒子群算法的稳定性条件 为： ，ｆｉ（Ｉｌｘｉ㈤ （ｔ－ｉ）Ｉ１＞０） Ｉ【（ｔＪ∈［０，１］，ｏｔｈｅｒｗｉｓｅ ３ 仿真实验 为了验证本文提出的个体决策历史适应值粒子群 算法（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ Ｉｎｄｉｖｉｄｕａｌ Ｄｅ． ｃｉｓｉｏｎ Ｈｉｓｔｏｒｙ Ｆｉｔｎｅｓｓ．ＰＳＯ—ＩＤＨＦ）在稳定性条件下对函 数优化的性能，我们利用标准粒子群算法（Ｓｔａｎｄａｒｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ．ｓＰｓｏ）及带时间加速常数 的粒子群算法（Ｍｏｄｉｆｉｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ｗｉｔｈ Ｔｉｍｅ—ｖａｒｙｉｎｇ Ａｃｃｅｌｅｒａｔｏｒ Ｃｏｅｆｉｆｃｉｅｎｔｓ，ＭＰＳＯ—ＴＶＡＣ）进 行比较 为了测试ＰＳＯ—ＩＤＨＦ在函数优化方面的性能．本 文选取了两个经典的测试函数进行测试 Ｒａｓｔｒｉｇｉｎ函数： ｆｇ ）：∑ 一１０ ｃ。ｓ（２￣ｒｘ ）＋１０］， 一５．１２≤ ≤５．１２，ｍｉｎ ） （０，…，０）＝０ Ａｃｋｌｅｙ函数： （ ）＝２０＋ｅ－２Ｏｅｘｐ（一０．２、／ ） －３２￣＜ｘ ≤３２，ｍｉｎ ） （０，…，０）＝Ｏ 现代计算机 ２０１４．０５中ｏ 【４】吕艳萍，李绍兹．自适应扩散混合变异机制微粒群算［Ｊ］．软件学报，２００７，１８（１７）：２７４０－２７５１ ［５］ＭＣｌｅｒｃ．ＪＫｅｎｎｅｄｙ．Ｔｈｅ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｅｘｐｌｏｓｉｏｎ Ｓｔａｂｉｌｉｔｙ，ａｎｄ Ｃｏｎｖｅｒｇｅｎｃｅ ｉｎ ａ Ｍｕｔｉｄｉｍｅｎｓｉｏｎａｌ Ｃｏｍｐｌｅｘ Ｓｐａｃｅ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃ— ｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（１）：５８～７３ 【６］Ｃｒｉｓｔｉａｎ Ｔｒｅｌｅａ．Ｔｈｅ Ｐａｒｔｉｃｌｅ Ｓｗａｍ Ｏｐｔｒｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ：Ｃｏｎｖｅｒｇｅｎｃｅ Ａｎａｌｙｓｉｓ ａｎｄ Ｐａｒａｍｅｔｅｒ Ｓｅｌｅｃｔｉｏｎ［Ｊ］．Ｉｎｆｏｍａｔｒｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｌｅｔｔｅｒｓ，２００３，８５（６）：３１７－３２５ 【７】李宁，孙德宝等．基于差分方程的ＰＳＯ算法粒子运动轨迹分析【ＪＪ．计算机学报，２００６，２９（１１）：２０５２￣２０６１ 『８］Ｆｅｒｎ ａｎｄ Ｍａｒｔ Ｔｈｅ Ｇｅｎｅｒａｌｉｚｅｄ ＰＳＯ：Ａ Ｎｅｗ Ｄｏｏｒ ｔｏ ＰＳＯ Ｅｖｏｌｕｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ａｒｔｉｉｆｃｉａｌ Ｅｖｏｌｕｔｉｏｎ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，１５（３）： １ １７～１２５． 【９】王高雄，周之铭，朱思铭，王寿松编．常微分方程【Ｍ】．高等教育出版社，２００４ 作者简介： 焦国辉（１９８４一），男，河南新乡人，硕士，研究方向为计算智能、剩余寿命预测 收稿Ｅｌ期：２０１４—０４—０８ 修稿日期：２０１４—０５—０５ Ｐｒｏｖｅｍｅｎｔ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｔｈｅ Ｓｔａｂｉｌｉｔｙ ｏｆ ａｎ Ｉ ｍｐｒｏｖｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ＪＩＡ０ Ｇｕｏ—ｈｕｉ （Ｃｏｍｐｕｔｅｒ Ｃｅｎｔｒｅ，Ｔａｉｙｕａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｔａｉｙｕａｎ ０３００１２） Ａｂｓｔｒａｃｔ： Ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｉｎｓｕｆｆｉｃｉｅｎｔ ｔｈｅｏｒｅｔｉｃａｌ ｓｔａｂｉｌｉｔｙ ｐｒｏｏｆ ａｎｄ ｐａｒａｍｅｔｅｒ ｓｅｌｅｃｔｉｏｎ ｏｎ ｉｍｐｒｏｖｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ｕｓｅｓ Ｌｙａｐｕｎｏｖ ｓｔａ— ｂｉｌｉｔｙ ｔｈｅｏｒｙ ｔｏ ｉｍｐｒｏｖｅ ｉｎｄｉｖｉｄｕａｌ ｄｅｃｉｓｉｏｎ ＰＳＯ ｓｔａｂｉｌｉｔｙ ａｎｄ ｇｉｖｅｓ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｐａｒａｍｅｔｅｒｓ ｓｅｌｅｃｔｅｄ ｍｅｔｈｏｄｓ，ｗｈｉｃｈ ｃｈａｎｇｅｓ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＰＳＯ ｏｎｌｙ．Ｕｓｅｓ ｓｅｖｅｒａｌ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ ｔｏ ｓｉｍｕｌａｔｉｏｎ，ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅ ｔｈａｎ ｔｈｅ ｏｔｈｅｒ ｉｍ— ｐｒｏｖｅｄ ＰＳＯ． Ｋｅｙｗｏｒｄｓ： ＰＳＯ（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ）；Ｉｎｄｉｖｉｄｕａｌ Ｄｅｃｉｓｉｏｎ；Ｌｙａｐｕｎｏｖ Ｆｕｎｃｔｉｏｎ；Ｓｔａｂｉｌｉｔｙ 曰 计笪木几 ，ｎ１ａｎ 由ｔＤ
