第12卷第4期 智能系统学报 Vol.12 No.4 2017年8月 CAAI Transactions on Intelligent Systems Aug.2017 D0I:10.11992/is.201610004 网s络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20170407.1744.008.html 依概率收敛的改进粒子群优化算法 钱伟懿，李明 (渤海大学数理学院，辽宁锦州121013) 摘要：粒子群优化算法是一种随机优化算法，但它不依概率1收敛到全局最优解。因此提出一种新的依概率收敛 的粒子群优化算法。在该算法中，首先引入了具有探索和开发能力的两个变异算子，并依一定概率对粒子当前最好 位置应用这两个算子，然后证明了该算法是依概率1收敛到ε最优解。最后，把该算法应用到13个典型的测试函数 中，并与其他粒子群优化算法比较，数值结果表明所给出的算法能够提高求解精度和收敛速度。 关键词：粒子群优化算法：随机优化算法：变异算子：依概率收敛：全局优化：进化计算：启发式算法：高斯分布 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2017)04-0511-08 中文引用格式：钱伟懿，李明.依概率收敛的改进粒子群优化算法[J].智能系统学报，2017,12(4)：511-518. 英文引用格式：QIAN Weiyi,LI Ming..mproved particle swarm optimization algorithmwith probability convergence[J].CAAI transactions on intelligent systems,2017,12(4):511-518. Improved particle swarm optimization algorithm with probability convergence QIAN Weiyi,LI Ming (College of Mathematics and Physics,Bohai University,Jinzhou 121013,China) Abstract:The particle swarm optimization (PSO)algorithm is a stochastic optimization algorithm that does not converge to a global optimal solution on the basis of probability 1.In this paper,we present a new probability-based convergent PSO algorithm that introduces two mutation operators with exploration and exploitation abilities,which are applied to the previous best position of a particle with a certain probability.This algorithm converges to the- optimum solution on the basis of probability 1.We applied the proposed algorithm in 13 typical test functions and compared its performance with that of other PSO algorithms.Our numerical results show that the proposed algorithm can improve solution precision and convergence speed. Keywords:particle swarm optimization;stochastic optimization algorithm;mutation operator;probability convergence;global optimization;evolutionary computation;heuristic algorithm;Gaussian distribution 粒子群优化算法是Kennedy等)在1995年提 结合1)：3)在PS0算法引入一些改进PS0算法性 出的一种群体搜索的随机优化算法。由于PSO算 能的其他算子，比如，把高斯扰动策略加入粒子群 法的参数少而且易操作，所以在实际问题中得到了 优化算法中[，把均匀设计方法引入到粒子群优化 广泛的应用。对PSO算法的研究主要有以下几个 算法中)，把变异策略)、精英策略1)、局部搜索 方面：1)对PS0算法自身参数的改进，这方面的工 策略[20]及邻域搜索策略[21]引入到粒子群优化算法 作主要关于惯性权重的自适应改进2-)和对学习因 中：4)PS0算法的理论分析，比如，基于线性系统理 子的改进9-川；2)将其他进化算法与PS0相结合， 论研究PS0收敛性2-2]，基于随机过程研究PS0 比如，遗传算法与PS0算法结合2-)，差分进化算 收敛性[2)，但是粒子群算法不依概率收敛[2。本 法与PS0算法结合[14，模拟退火算法与PS0算法 文给出了一种依概率1收敛的PS0算法，该算法在 标准粒子群优化算法实施位置更新后按一定概率 收稿日期：2016-10-05.网络出版日期：2017-04-07. 对较好的粒子实施具有开发能力的变异操作，对较 基金项目：国家自然科学基金项目(11371071)：辽宁省数育厅科学研究 差的粒子实施具有探索能力的变异操作，从而平衡 项目(L2013426). 通信作者：钱伟懿.E-mail:qianweiyi2008@163.com. 了算法的全局搜索能力和局部搜索能力，提高了算第 １２ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．４ ２０１７ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６１０００４ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１７０４０７．１７４４．００８．ｈｔｍｌ 依概率收敛的改进粒子群优化算法 钱伟懿，李明 （渤海大学 数理学院，辽宁 锦州 １２１０１３） 摘 要：粒子群优化算法是一种随机优化算法，但它不依概率 １ 收敛到全局最优解。 因此提出一种新的依概率收敛 的粒子群优化算法。 在该算法中，首先引入了具有探索和开发能力的两个变异算子，并依一定概率对粒子当前最好 位置应用这两个算子，然后证明了该算法是依概率 １ 收敛到 ε⁃最优解。 最后，把该算法应用到 １３ 个典型的测试函数 中，并与其他粒子群优化算法比较，数值结果表明所给出的算法能够提高求解精度和收敛速度。 关键词：粒子群优化算法；随机优化算法；变异算子；依概率收敛；全局优化；进化计算；启发式算法；高斯分布 中图分类号：ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０４－０５１１－０８ 中文引用格式：钱伟懿，李明．依概率收敛的改进粒子群优化算法［Ｊ］． 智能系统学报， ２０１７， １２（４）： ５１１－５１８． 英文引用格式：ＱＩＡＮ Ｗｅｉｙｉ，ＬＩ Ｍｉｎｇ． Ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｗｉｔｈ ｐｒｏｂａｂｉｌｉｔｙ ｃｏｎｖｅｒｇｅｎｃｅ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（４）： ５１１－５１８． Ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｐｒｏｂａｂｉｌｉｔｙ ｃｏｎｖｅｒｇｅｎｃｅ ＱＩＡＮ Ｗｅｉｙｉ， ＬＩ Ｍｉｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｐｈｙｓｉｃｓ， Ｂｏｈａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｊｉｎｚｈｏｕ １２１０１３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ ＰＳＯ） ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｓｔｏｃｈａｓｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ｄｏｅｓ ｎｏｔ ｃｏｎｖｅｒｇｅ ｔｏ ａ ｇｌｏｂａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｐｒｏｂａｂｉｌｉｔｙ １． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗ ｐｒｏｂａｂｉｌｉｔｙ⁃ｂａｓｅｄ ｃｏｎｖｅｒｇｅｎｔ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ｉｎｔｒｏｄｕｃｅｓ ｔｗｏ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒｓ ｗｉｔｈ ｅｘｐｌｏｒａｔｉｏｎ ａｎｄ ｅｘｐｌｏｉｔａｔｉｏｎ ａｂｉｌｉｔｉｅｓ， ｗｈｉｃｈ ａｒｅ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｐｒｅｖｉｏｕｓ ｂｅｓｔ ｐｏｓｉｔｉｏｎ ｏｆ ａ ｐａｒｔｉｃｌｅ ｗｉｔｈ ａ ｃｅｒｔａｉｎ ｐｒｏｂａｂｉｌｉｔｙ． Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｃｏｎｖｅｒｇｅｓ ｔｏ ｔｈｅ⁃ ｏｐｔｉｍｕｍ ｓｏｌｕｔｉｏｎ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｐｒｏｂａｂｉｌｉｔｙ １．Ｗｅ ａｐｐｌｉｅｄ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｎ １３ ｔｙｐｉｃａｌ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ ａｎｄ ｃｏｍｐａｒｅｄ ｉｔｓ ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈ ｔｈａｔ ｏｆ ｏｔｈｅｒ ＰＳＯ ａｌｇｏｒｉｔｈｍｓ． Ｏｕｒ ｎｕｍｅｒｉｃａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｓｏｌｕｔｉｏｎ ｐｒｅｃｉｓｉｏｎ ａｎｄ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ． Ｋｅｙｗｏｒｄｓ： ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ； ｓｔｏｃｈａｓｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ； ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ； ｐｒｏｂａｂｉｌｉｔｙ ｃｏｎｖｅｒｇｅｎｃｅ； ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ； ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ； ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ； Ｇａｕｓｓｉａｎ ｄｉｓｔｒｉｂｕｔｉｏｎ 收稿日期：２０１６－１０－０５． 网络出版日期：２０１７－０４－０７． 基金项目：国家自然科学基金项目（１１３７１０７１）；辽宁省教育厅科学研究 项目（Ｌ２０１３４２６）． 通信作者：钱伟懿． Ｅ⁃ｍａｉｌ：ｑｉａｎｗｅｉｙｉ２００８＠ １６３．ｃｏｍ． 粒子群优化算法是 Ｋｅｎｎｅｄｙ 等［１］ 在 １９９５ 年提 出的一种群体搜索的随机优化算法。 由于 ＰＳＯ 算 法的参数少而且易操作，所以在实际问题中得到了 广泛的应用。 对 ＰＳＯ 算法的研究主要有以下几个 方面：１）对 ＰＳＯ 算法自身参数的改进，这方面的工 作主要关于惯性权重的自适应改进［２－９］ 和对学习因 子的改进［９－１１］ ；２）将其他进化算法与 ＰＳＯ 相结合， 比如，遗传算法与 ＰＳＯ 算法结合［１２－１３］ ，差分进化算 法与 ＰＳＯ 算法结合［１４］ ，模拟退火算法与 ＰＳＯ 算法 结合［１５］ ；３）在 ＰＳＯ 算法引入一些改进 ＰＳＯ 算法性 能的其他算子，比如，把高斯扰动策略加入粒子群 优化算法中［１６］ ，把均匀设计方法引入到粒子群优化 算法中［１７］ ，把变异策略［１８］ 、精英策略［１９］ 、局部搜索 策略［２０］及邻域搜索策略［２１］ 引入到粒子群优化算法 中；４）ＰＳＯ 算法的理论分析，比如，基于线性系统理 论研究 ＰＳＯ 收敛性［２２－２５］ ，基于随机过程研究 ＰＳＯ 收敛性［２６］ ，但是粒子群算法不依概率收敛［２６］ 。 本 文给出了一种依概率 １ 收敛的 ＰＳＯ 算法，该算法在 标准粒子群优化算法实施位置更新后按一定概率 对较好的粒子实施具有开发能力的变异操作，对较 差的粒子实施具有探索能力的变异操作，从而平衡 了算法的全局搜索能力和局部搜索能力，提高了算