第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. 了算法的全局搜索能力和局部搜索能力，提高了算
第 １２ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．４ ２０１７ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６１０００４ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１７０４０７．１７４４．００８．ｈｔｍｌ 依概率收敛的改进粒子群优化算法 钱伟懿，李明 （渤海大学 数理学院，辽宁 锦州 １２１０１３） 摘 要：粒子群优化算法是一种随机优化算法，但它不依概率 １ 收敛到全局最优解。 因此提出一种新的依概率收敛 的粒子群优化算法。 在该算法中，首先引入了具有探索和开发能力的两个变异算子，并依一定概率对粒子当前最好 位置应用这两个算子，然后证明了该算法是依概率 １ 收敛到 ε⁃最优解。 最后，把该算法应用到 １３ 个典型的测试函数 中，并与其他粒子群优化算法比较，数值结果表明所给出的算法能够提高求解精度和收敛速度。 关键词：粒子群优化算法；随机优化算法；变异算子；依概率收敛；全局优化；进化计算；启发式算法；高斯分布 中图分类号：ＴＰ３０１．６ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０４－０５１１－０８ 中文引用格式：钱伟懿，李明．依概率收敛的改进粒子群优化算法［Ｊ］． 智能系统学报， ２０１７， １２（４）： ５１１－５１８． 英文引用格式：ＱＩＡＮ Ｗｅｉｙｉ，ＬＩ Ｍｉｎｇ． Ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｗｉｔｈ ｐｒｏｂａｂｉｌｉｔｙ ｃｏｎｖｅｒｇｅｎｃｅ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（４）： ５１１－５１８． Ｉｍｐｒｏｖｅｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｐｒｏｂａｂｉｌｉｔｙ ｃｏｎｖｅｒｇｅｎｃｅ ＱＩＡＮ Ｗｅｉｙｉ， ＬＩ Ｍｉｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｐｈｙｓｉｃｓ， Ｂｏｈａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｊｉｎｚｈｏｕ １２１０１３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ ＰＳＯ） ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｓｔｏｃｈａｓｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ｄｏｅｓ ｎｏｔ ｃｏｎｖｅｒｇｅ ｔｏ ａ ｇｌｏｂａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｐｒｏｂａｂｉｌｉｔｙ １． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗ ｐｒｏｂａｂｉｌｉｔｙ⁃ｂａｓｅｄ ｃｏｎｖｅｒｇｅｎｔ ＰＳＯ ａｌｇｏｒｉｔｈｍ ｔｈａｔ ｉｎｔｒｏｄｕｃｅｓ ｔｗｏ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒｓ ｗｉｔｈ ｅｘｐｌｏｒａｔｉｏｎ ａｎｄ ｅｘｐｌｏｉｔａｔｉｏｎ ａｂｉｌｉｔｉｅｓ， ｗｈｉｃｈ ａｒｅ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｐｒｅｖｉｏｕｓ ｂｅｓｔ ｐｏｓｉｔｉｏｎ ｏｆ ａ ｐａｒｔｉｃｌｅ ｗｉｔｈ ａ ｃｅｒｔａｉｎ ｐｒｏｂａｂｉｌｉｔｙ． Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｃｏｎｖｅｒｇｅｓ ｔｏ ｔｈｅ⁃ ｏｐｔｉｍｕｍ ｓｏｌｕｔｉｏｎ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｐｒｏｂａｂｉｌｉｔｙ １．Ｗｅ ａｐｐｌｉｅｄ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｎ １３ ｔｙｐｉｃａｌ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ ａｎｄ ｃｏｍｐａｒｅｄ ｉｔｓ ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈ ｔｈａｔ ｏｆ ｏｔｈｅｒ ＰＳＯ ａｌｇｏｒｉｔｈｍｓ． Ｏｕｒ ｎｕｍｅｒｉｃａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｓｏｌｕｔｉｏｎ ｐｒｅｃｉｓｉｏｎ ａｎｄ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ． Ｋｅｙｗｏｒｄｓ： ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ； ｓｔｏｃｈａｓｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ； ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ； ｐｒｏｂａｂｉｌｉｔｙ ｃｏｎｖｅｒｇｅｎｃｅ； ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ； ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ； ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ； Ｇａｕｓｓｉａｎ ｄｉｓｔｒｉｂｕｔｉｏｎ 收稿日期：２０１６－１０－０５． 网络出版日期：２０１７－０４－０７． 基金项目：国家自然科学基金项目（１１３７１０７１）；辽宁省教育厅科学研究 项目（Ｌ２０１３４２６）． 通信作者：钱伟懿． Ｅ⁃ｍａｉｌ：ｑｉａｎｗｅｉｙｉ２００８＠ １６３．ｃｏｍ． 粒子群优化算法是 Ｋｅｎｎｅｄｙ 等［１］ 在 １９９５ 年提 出的一种群体搜索的随机优化算法。 由于 ＰＳＯ 算 法的参数少而且易操作，所以在实际问题中得到了 广泛的应用。 对 ＰＳＯ 算法的研究主要有以下几个 方面：１）对 ＰＳＯ 算法自身参数的改进，这方面的工 作主要关于惯性权重的自适应改进［２－９］ 和对学习因 子的改进［９－１１］ ；２）将其他进化算法与 ＰＳＯ 相结合， 比如，遗传算法与 ＰＳＯ 算法结合［１２－１３］ ，差分进化算 法与 ＰＳＯ 算法结合［１４］ ，模拟退火算法与 ＰＳＯ 算法 结合［１５］ ；３）在 ＰＳＯ 算法引入一些改进 ＰＳＯ 算法性 能的其他算子，比如，把高斯扰动策略加入粒子群 优化算法中［１６］ ，把均匀设计方法引入到粒子群优化 算法中［１７］ ，把变异策略［１８］ 、精英策略［１９］ 、局部搜索 策略［２０］及邻域搜索策略［２１］ 引入到粒子群优化算法 中；４）ＰＳＯ 算法的理论分析，比如，基于线性系统理 论研究 ＰＳＯ 收敛性［２２－２５］ ，基于随机过程研究 ＰＳＯ 收敛性［２６］ ，但是粒子群算法不依概率收敛［２６］ 。 本 文给出了一种依概率 １ 收敛的 ＰＳＯ 算法，该算法在 标准粒子群优化算法实施位置更新后按一定概率 对较好的粒子实施具有开发能力的变异操作，对较 差的粒子实施具有探索能力的变异操作，从而平衡 了算法的全局搜索能力和局部搜索能力，提高了算
.512. 智能系统学报 第12卷 法的效率，另外，证明了该算法依概率1收敛到ε- P实施式(4)或式(5)的变异操作，即当f(P)≤∫ 最优解。实验结果表明，提出的算法能够提高全局 时，对P按概率μ实施式(5)的变异操作，当f(P)> 搜索能力，算法的收敛速度明显加快。 f时，对P按概率u实施式(4)的变异操作，其中 Ne 1标准PS0算法 ), (7) 标准粒子群算法中，粒子群由N。个粒子组成， [(-(P)) 在时刻k,第i个粒子在d维空间中速度和位置的更 fs-f(P) f(P)≤fe 新公式为 u= (8) a(f(Pi)-fv) v=ovi cir(pi -xia)+car2(pa -x) fu -fave f(P)>fv (1) 城=x始+城 式中：f=max{f(P)},a是一个自适应参数，它 (2) 1iN 式中：i=1,2,…,N。,d=1,2,…,D,D为决策变量的 被定义为 维数，ω为惯性权重，x=(x始，x点，…，x0)表示粒子i a=1-0.8 (9) 的当前的位置；=(，哈，…，)是粒子i的当前 由式(8)知，对适应值较好的粒子实施局部搜 的速度；P=(p哈，p哈，…，P)是粒子i当前最优位 索的概率较大，而对适应值较差的粒子实施全局搜 置，P=(p,P点，…，P)是全局最优位置；c1、2是 索的概率较大。由于当算法迭代到后期，粒子比较 加速度因子，12是0~1之间的随机数。第k次迭 代的惯性权重表示为 集中，从而导致-或)-接近1，若a -可或 fef(p)fa-fe =(@stan -@end (3) 大，那么实施式(4)或式(5)的变异操作的粒子较 多，从而导致算法运算时间长，因此按式(9)实行单 式中：wat、w分别为最初和最终的惯性权重，K 调递减策略。 是最大迭代步。 位置与速度越界处理： 2 改进的PSO算法 , 儿≤站≤山 la+rand()·(u4-la), 其他 提高PS0算法性能的有效方法之一就是平衡 (10) 算法的探索能力和开发能力。我们的目的是对粒 子所经历的最好位置进行操作，一方面能够使其跳 站，n≤话≤ 出局部最优；另一方面使其具有一定的局部搜索能 =min' 姑1<an (11) 力。为此，给出两个变异算子： P=P·p,N(0,c2) (4) 式中：=0.5l4,8"=0.5u4o 改进PSO0算法的流程如下： P=P+p,N(0,2) (5) 1)设置参数，随机初始化粒子的位置和速度， 式中：P1>1和P2>1是常数，N(0,o2)是具有时变标 计算各粒子的适应度，确定每个粒子的经历过的最 准差σ的高斯分布的随机变量，σ表示为 优位置及全局最优位置，令k=1: 00--小 2)按式(3)计算惯性权重，并按式(1)和式(2) (6) 进行速度与位置更新： 式中：0m和σ是标准差σ的最终和初始值，k是 3)按式(10)和式(11)进行越界处理： 当前迭代步，K是最大迭代步。因为P,N(0,σ2) 4)对粒子i(i=1,2,…,N)计算其适应值，更 的值比1大或比1小，又因为P·P1N(0,σ2)是一 新其经历过的最优位置P和全局最优位置P, 个随机值，所以它比P大或小，这样P可能远离 并按式(7)计算fe: P,因此说式(4)具有一定的全局搜索能力。另一 5)若f(P)≤f,按式(9)计算a,按式(8)计 算u,在[0，l]选取一个随机数and,若rand<u,则 方面，式(5)表明在P附近搜索，因此式(5)具有一 按式(6)计算σ，按式(5)更新粒子经历过的最优位 定的局部搜索能力。 如果每次都对P实施式(4)或式(5)的变异操 置，得到P,转7)： 作，那么导致算法运行时间长，因此按一定概率μ对 6)若fP)>f,按式(9)计算a,按式(8)计
法的效率，另外，证明了该算法依概率 １ 收敛到 ε⁃ 最优解。 实验结果表明，提出的算法能够提高全局 搜索能力，算法的收敛速度明显加快。 １ 标准 ＰＳＯ 算法 标准粒子群算法中，粒子群由 Ｎｐ 个粒子组成， 在时刻 ｋ，第 ｉ 个粒子在 ｄ 维空间中速度和位置的更 新公式为 ｖ ｋ＋１ ｉｄ ＝ ωｖ ｋ ｉｄ ＋ ｃ１ ｒ１（ｐ ｋ ｉｄ － ｘ ｋ ｉｄ ） ＋ ｃ２ ｒ２（ｐ ｋ ｇｄ － ｘ ｋ ｉｄ ） （１） ｘ ｋ＋１ ｉｄ ＝ ｘ ｋ ｉｄ ＋ ｖ ｋ＋１ ｉｄ （２） 式中：ｉ ＝ １，２，…，Ｎｐ，ｄ ＝ １，２，…，Ｄ，Ｄ 为决策变量的 维数，ω 为惯性权重，ｘ ｋ ｉ ＝ （ｘ ｋ ｉ１ ，ｘ ｋ ｉ２ ，…，ｘ ｋ ｉＤ）表示粒子 ｉ 的当前的位置；ｖ ｋ ｉ ＝ （ｖ ｋ ｉ１ ，ｖ ｋ ｉ２ ，…，ｖ ｋ ｉＤ ）是粒子 ｉ 的当前 的速度；Ｐ ｋ ｉ ＝ （ ｐ ｋ ｉ１ ，ｐ ｋ ｉ２ ，…，ｐ ｋ ｉＤ ） 是粒子 ｉ 当前最优位 置，Ｐ ｋ ｇ ＝ （ ｐ ｋ ｇ１ ，ｐ ｋ ｇ２ ，…，ｐ ｋ ｇＤ ）是全局最优位置；ｃ１ 、ｃ２ 是 加速度因子，ｒ１ 、ｒ２ 是 ０～１ 之间的随机数。 第 ｋ 次迭 代的惯性权重表示为 ωｋ ＝ （ωｓｔａｒｔ － ωｅｎｄ ） Ｋｍａｘ － ｋ Ｋｍａｘ æ è ç ö ø ÷ ＋ ωｅｎｄ （３） 式中：ωｓｔａｒｔ、ωｅｎｄ分别为最初和最终的惯性权重，Ｋｍａｘ 是最大迭代步。 ２ 改进的 ＰＳＯ 算法 提高 ＰＳＯ 算法性能的有效方法之一就是平衡 算法的探索能力和开发能力。 我们的目的是对粒 子所经历的最好位置进行操作，一方面能够使其跳 出局部最优；另一方面使其具有一定的局部搜索能 力。 为此，给出两个变异算子： Ｐ －ｋ ｉｄ ＝ Ｐ ｋ ｉｄ·ρ１Ｎ（０，σ ２ ） （４） Ｐ －ｋ ｉｄ ＝ Ｐ ｋ ｉｄ ＋ ρ２Ｎ（０，σ ２ ） （５） 式中：ρ１＞１ 和 ρ２＞１ 是常数，Ｎ（０，σ ２ ）是具有时变标 准差 σ 的高斯分布的随机变量，σ 表示为 σ ＝ σｍａｘ － （σｍａｘ － σｍｉｎ ） ｋ Ｋｍａｘ （６） 式中：σｍａｘ和 σｍｉｎ是标准差 σ 的最终和初始值，ｋ 是 当前迭代步，Ｋｍａｘ是最大迭代步。 因为 ρ１Ｎ（０，σ ２ ） 的值比 １ 大或比 １ 小，又因为 Ｐ ｋ ｉｄ·ρ１Ｎ（０，σ ２ ）是一 个随机值，所以它比 Ｐ ｋ ｉｄ 大或小，这样 Ｐ －ｋ ｉｄ 可能远离 Ｐ ｋ ｉｄ ，因此说式（４）具有一定的全局搜索能力。 另一 方面，式（５）表明在 Ｐ ｋ ｉｄ附近搜索，因此式（５）具有一 定的局部搜索能力。 如果每次都对Ｐ ｋ ｉ 实施式（４）或式（５）的变异操 作，那么导致算法运行时间长，因此按一定概率 μ 对 Ｐ ｋ ｉ 实施式（４）或式（５）的变异操作，即当 ｆ（Ｐ ｋ ｉ ）≤ｆ ａｖｅ 时，对Ｐ ｋ ｉ 按概率 μ 实施式（５）的变异操作，当ｆ（Ｐ ｋ ｉ ）＞ ｆ ａｖｅ时，对Ｐ ｋ ｉ 按概率 μ 实施式（４）的变异操作，其中 ｆ ａｖｅ ＝ １ Ｎｐ ∑ Ｎｐ ｊ ＝ １ ｆ（Ｐ ｋ ｊ ）， （７） μ ＝ α（ｆ ａｖｅ － ｆ（Ｐ ｋ ｉ ）） ｆ ａｖｅ － ｆ（Ｐ ｋ ｇ ） ， ｆ（Ｐ ｋ ｉ ） ≤ ｆ ａｖｅ α（ｆ（Ｐ ｋ ｉ ） － ｆ ａｖｅ） ｆｍａｘ － ｆ ａｖｅ ， ｆ（Ｐ ｋ ｉ ） ＞ ｆ ａｖｅ ì î í ï ïï ï ïï （８） 式中：ｆｍａｘ ＝ ｍａｘ １≤ｉ≤Ｎｐ ｛ ｆ（Ｐ ｋ ｉ ）｝，α 是一个自适应参数，它 被定义为 α ＝ １ － ０．８ ｋ Ｋｍａｘ （９） 由式（８）知，对适应值较好的粒子实施局部搜 索的概率较大，而对适应值较差的粒子实施全局搜 索的概率较大。 由于当算法迭代到后期，粒子比较 集中，从而导致 ｆ ａｖｅ －ｆ（Ｐ ｋ ｉ ） ｆ ａｖｅ －ｆ（Ｐ ｋ ｇ ） 或 ｆ（Ｐ ｋ ｉ ）－ｆ ａｖｅ ｆｍａｘ －ｆ ａｖｅ 接近 １，若 α 大，那么实施式（４） 或式（５） 的变异操作的粒子较 多，从而导致算法运算时间长，因此按式（９）实行单 调递减策略。 位置与速度越界处理： ｘ ｋ＋１ ｉｄ ＝ ｘ ｋ＋１ ｉｄ ， ｌ ｄ ≤ ｘ ｋ＋１ ｉｄ ≤ ｕｄ ｌ ｄ ＋ ｒａｎｄ（）·（ｕｄ － ｌ { ｄ ）， 其他 （１０） ｖ ｋ＋１ ｉｄ ＝ ｖ ｋ＋１ ｉｄ ， ｖｍｉｎ ≤ ｖ ｋ＋１ ｉｄ ≤ ｖｍａｘ ｖｍｉｎ ， ｖ ｋ＋１ ｉｄ ＜ ｖｍｉｎ ｖｍａｘ， ｖ ｋ＋１ ｉｄ ＞ ｖｍａｘ ì î í ï ï ï ï （１１） 式中：ｖ ｍｉｎ ｄ ＝ ０．５ｌ ｄ ，ｖ ｍａｘ ｄ ＝ ０．５ｕｄ 。 改进 ＰＳＯ 算法的流程如下： １）设置参数，随机初始化粒子的位置和速度， 计算各粒子的适应度，确定每个粒子的经历过的最 优位置及全局最优位置，令 ｋ ＝ １； ２）按式（３）计算惯性权重，并按式（１）和式（２） 进行速度与位置更新； ３） 按式（１０）和式（１１）进行越界处理； ４） 对粒子 ｉ（ｉ ＝ １，２，…，Ｎｐ ）计算其适应值，更 新其经历过的最优位置Ｐ ｋ＋１ ｉ 和全局最优位置Ｐ ｋ＋１ ｇ ， 并按式（７）计算 ｆ ａｖｅ； ５） 若 ｆ（Ｐ ｋ＋１ ｉ ）≤ｆ ａｖｅ，按式（９）计算 α，按式（８）计 算 μ，在［０，１］选取一个随机数 ｒａｎｄ，若 ｒａｎｄ＜ μ，则 按式（６）计算 σ，按式（５）更新粒子经历过的最优位 置，得到Ｐ －ｋ＋１ ｉ ，转 ７）； ６）若 ｆ（Ｐ ｋ＋１ ｉ ）＞ｆ ａｖｅ，按式（９）计算 α，按式（８）计 ·５１２· 智 能 系 统 学 报 第 １２ 卷
第4期 钱伟懿，等：依概率收敛的改进粒子群优化算法 ·513· 算u,在[0,1]选取一个随机数rand,若rand<u,则 B。;如果P(new)=P,则结论是显然的。 按(6)式计算σ，按(4)式更新粒子经历过的最优位 引理3H重E④，P由算法生成的，则存在 置，得到P; p>0,使得 7)令 pr(P1∈BI重=)≥p p,fp)<fP) 式中pr表示概率测度。 p+(new)= p1,fp)≥fp) 证明如果P实施变异算子(4)或(5)操作， 8)令P'=P'(new),更新P'; 则令X(P)=1,否则令X(P)=0,由算法步骤5)和 9)判断是否满足终止条件（本文采用最大迭代 步骤6)及式(8)有 步)，若满足则输出结果，否则令k=k+1,转2)。 pr(K(P')=1)=a,pr(X(P1)=0)=1-a 3 收敛性分析 于是 本文考虑如下全局优化问题： pr(P1∈BI=D)≥pr(X(P)=1)· minimize f(x) pr(P1∈B.1电=D)1X(P)=1)= subject to x∈S 式中：f:S→R是实值函数，S={xmm≤x≤xm}, a·pr(P1eB.I重=D)1X(P')=1)= a·pr(p'(new)∈B.I中=Φ) xm=(l1,l2,…,ln）,xmm=(1,42,…,4o）。 由引理2有 定义1设f(x)是实值函数，x”∈S,若对任意 x∈S, pr(P∈BI=)≥a·pr(P∈B|=) f(x·)≤f(x) 由于P的每个分量是独立的，再由式(5)知， 则称x·为S的全局最优解。 随机变量P+1的密度函数为 定义2对任意ε>0，设 1 D B.={x∈Sllf(x)-f(x·)|<el} g(1,x2,“,xD）= exp(- 则称B。为e最优解集，x∈B。被称为6-最优解。 2Top2 本文假设u(B)>0,其中μ为勒贝格测度。 于是 由定义1和2得： pr(p'∈B|电=)= x结=点+ω点+c(p点-xa)+cr2(p-x) ng(x1,x2,…,xo)dxd2…dxo≥ (12) 由式(12)可看出，在第k+1代粒子群中第i个 √22 exp(-D 2m2 D 粒子的状态由x、、P、P决定，所以令9：=(x,”, u(B.) P:,P）∈T,其中T=SxVxSXSER"。 式中m=m,,lu,}。 定义3设中，=1重|重=(9，…，P,）,9:∈ 1 D a加(B.),则 2m2 令p= exp(-D- T,i=1,…,N},则称中为状态空间，中∈中称为 mP2) 状态。 pr(P∈BI重=Φ)≥p>0。 定义4设2={ω1ω=（中，中2，中，…）， 定理1设（中，中2，少，…）∈2是由算法任意 重∈中p,Hk,则称n为样本空间，w∈2称为状 生成的状态序列，则序列{p}依概率1收敛到c-最 态序列，其中重=(，，…，吹)，=(，，P, 优解，即 P)。 lim pr{pg∈Be}=1 由改进算法可知，f(P)≤f(P),所以有如下 证明由算法可知，中+1只与Φ。有关，所以Φ， 引理。 ④2，中，…是马尔可夫过程，由马尔可夫过程性质及 引理1对Hk≥1，若P∈B,则P∈Bo 引理1可知 pr(PI生B)=pr(PEB) 引理2对Vi,k,若PeB。,那么P(new)∈B。 Πpr(PI年BIP华B)≤ 证明如果P(new)=p,由算法7)知f(p)≥ f(P),再由P∈B。有P∈B.,从而P'(new)∈ Πpr(P生B.lP生B)
算 μ，在［０，１］选取一个随机数 ｒａｎｄ，若 ｒａｎｄ＜ μ，则 按（６）式计算 σ，按（４）式更新粒子经历过的最优位 置，得到Ｐ －ｋ＋１ ｉ ； ７）令 Ｐ ｋ＋１ ｉ （ｎｅｗ） ＝ Ｐ － ｋ＋１ ｉ ， ｆ（Ｐ － ｋ＋１ ｉ ） ＜ ｆ（Ｐ ｋ＋１ ｉ ） Ｐ ｋ＋１ ｉ ， ｆ（Ｐ － ｋ＋１ ｉ ） ≥ ｆ（Ｐ ｋ＋１ { ｉ ） ； ８） 令Ｐ ｋ＋１ ｉ ＝Ｐ ｋ＋１ ｉ （ｎｅｗ），更新Ｐ ｋ＋１ ｇ ； ９） 判断是否满足终止条件（本文采用最大迭代 步），若满足则输出结果，否则令 ｋ ＝ ｋ＋１，转 ２）。 ３ 收敛性分析 本文考虑如下全局优化问题： ｍｉｎｉｍｉｚｅ ｆ（ｘ） ｓｕｂｊｅｃｔ ｔｏ ｘ ∈ Ｓ 式中：ｆ：Ｓ →Ｒ 是实值函数， Ｓ ＝ ｛ ｘｍｉｎ ≤ｘ ≤ｘｍａｘ ｝， ｘｍｉｎ ＝ （ｌ １ ，ｌ ２ ，…，ｌＤ），ｘｍａｘ ＝ （ｕ１ ，ｕ２ ，…，ｕＤ）。 定义 １ 设 ｆ（ｘ）是实值函数，ｘ ∗ ∈Ｓ，若对任意 ｘ∈Ｓ， ｆ（ｘ ∗ ） ≤ ｆ（ｘ） 则称 ｘ ∗为 Ｓ 的全局最优解。 定义 ２ 对任意 ε＞０，设 Ｂε ＝ ｘ ∈ Ｓ ｆ（ｘ） － ｆ（ｘ ∗ { ） ＜ ε } 则称 Ｂε 为 ε 最优解集，ｘ∈Ｂε 被称为 ε⁃最优解。 本文假设 μ（Ｂε ）＞０， 其中 μ 为勒贝格测度。 由定义 １ 和 ２ 得： ｘ ｋ＋１ ｉｄ ＝ ｘ ｋ ｉｄ ＋ ωｋ ｖ ｋ ｉｄ ＋ ｃ１ ｒ１（ｐ ｋ ｉｄ － ｘ ｋ ｉｄ ） ＋ ｃ２ ｒ２（ｐ ｋ ｇｄ － ｘ ｋ ｉｄ ） （１２） 由式（１２）可看出，在第 ｋ＋１ 代粒子群中第 ｉ 个 粒子的状态由ｘ ｋ ｉ 、ｖ ｋ ｉ 、Ｐ ｋ ｉ 、Ｐ ｋ ｇ 决定，所以令 φｉ ＝ （ｘｉ，ｖｉ， Ｐｉ，Ｐｇ ）∈Γ，其中 Γ ＝ Ｓ×Ｖ×Ｓ×Ｓ∈Ｒ ４Ｄ 。 定义 ３ 设 ΦＮｐ ＝ ｛Φ 丨Φ ＝ （φ１，…，φＮｐ ），φｉ ∈ Γ，ｉ ＝ １，…，Ｎｐ｝， 则称 ΦＮｐ为状态空间，Φ∈ΦＮｐ称为 状态。 定义 ４ 设 Ω ＝ ｛ω ｜ ω ＝ （ Φ１ ， Φ２ ， Φ３ ，…）， Φｋ ∈ΦＮｐ，∀ｋ｝， 则称 Ω 为样本空间，ω∈Ω 称为状 态序列，其中Φｋ ＝ （φ ｋ １ ，φ ｋ ２ ，…，φ ｋ Ｎｐ ），φ ｋ ｉ ＝ （ ｘ ｋ ｉ ，ｖ ｋ ｉ ，Ｐ ｋ ｉ ， Ｐ ｋ ｇ ）。 由改进算法可知，ｆ（Ｐ ｋ＋１ ｇ ）≤ｆ（Ｐ ｋ ｇ ），所以有如下 引理。 引理 １ 对∀ｋ≥１，若 Ｐ ｋ ｇ∈Ｂε ，则Ｐ ｋ＋１ ｇ ∈Ｂε 。 引理 ２ 对∀ｉ，ｋ，若Ｐ －ｋ ｉ ∈Ｂε，那么Ｐ ｋ＋１ ｉ （ｎｅｗ） ∈Ｂε 。 证明 如果Ｐ ｋ ｉ（ｎｅｗ）＝ Ｐ ｋ ｉ ，由算法 ７）知 ｆ（Ｐ －ｋ ｉ ）≥ ｆ（Ｐ ｋ ｉ ），再由Ｐ －ｋ ｉ ∈Ｂε 有 Ｐ ｋ ｉ ∈Ｂε ，从而 Ｐ ｋ＋１ ｉ （ ｎｅｗ） ∈ Ｂε ；如果Ｐ ｋ ｉ（ｎｅｗ）＝ Ｐ －ｋ ｉ ，则结论是显然的。 引理 ３ ∀Φ∈ΦＮｐ ，Ｐ ｋ＋１ ｇ 由算法生成的，则存在 ρ＞０，使得 ｐｒ（Ｐ ｋ＋１ ｇ ∈ Ｂε ｜ Φｋ ＝ Φ） ≥ ρ 式中 ｐｒ 表示概率测度。 证明 如果Ｐ ｋ ｉ 实施变异算子（４） 或（５） 操作， 则令 χ（Ｐ －ｋ ｉ ）＝ １，否则令 χ（Ｐ －ｋ ｉ ）＝ ０，由算法步骤 ５）和 步骤 ６）及式（８）有 ｐｒ（χ（ Ｐ －ｋ＋１ ｇ ） ＝ １） ＝ α，ｐｒ（χ（ Ｐ －ｋ＋１ ｇ ） ＝ ０） ＝ １ － α 于是 ｐｒ（Ｐ ｋ＋１ ｇ ∈ Ｂε ｜ Φｋ ＝ Φ） ≥ ｐｒ（χ（ Ｐ －ｋ＋１ ｇ ） ＝ １）· ｐｒ（（Ｐ ｋ＋１ ｇ ∈ Ｂε ｜ Φｋ ＝ Φ） ｜ χ（ Ｐ －ｋ＋１ ｇ ） ＝ １） ＝ α·ｐｒ（（Ｐ ｋ＋１ ｇ ∈ Ｂε ｜ Φｋ ＝ Φ） ｜ χ（ Ｐ －ｋ＋１ ｇ ） ＝ １） ＝ α·ｐｒ（Ｐ ｋ＋１ ｇ （ｎｅｗ） ∈ Ｂε ｜ Φｋ ＝ Φ） 由引理 ２ 有 ｐｒ（Ｐ ｋ＋１ ｇ ∈Ｂε ｜ Φｋ ＝ Φ） ≥α·ｐｒ（Ｐ －ｋ＋１ ｇ ∈Ｂε ｜ Φｋ ＝ Φ） 由于Ｐ －ｋ＋１ ｇ 的每个分量是独立的，再由式（５）知， 随机变量Ｐ －ｋ＋１ ｇ 的密度函数为 ｇ（ｘ１，ｘ２，…，ｘＤ） ＝ １ ２πσρ２ æ è ç ö ø ÷ Ｄ ｅｘｐ（ － ∑ Ｄ ｄ ＝ １ （ｘｄ － ｐ ｋ＋１ ｇｄ ） ２ ２σ ２ ρ ２ ２ ） 于是 ｐｒ（ ｐ －ｋ＋１ ｇ ∈ Ｂε Φｋ ＝ Φ） ＝ ∫ Ｂε ｇ（ｘ１ ，ｘ２ ，…，ｘＤ）ｄｘ１ ｄｘ２…ｄｘＤ ≥ １ ２πσｍａｘ ρ２ æ è ç ö ø ÷ Ｄ ｅｘｐ（ － Ｄ ２ｍ ２ σｍｉｎ ２ ρ ２ ２ ）μ（Ｂε ） 式中 ｍ ＝ ｍａｘ １≤ｉ≤Ｄ ｛ ｜ ｌ ｉ ｜ ， ｜ ｕｉ ｜ ｝。 令 ρ ＝ １ ２πσｍａｘ ρ２ æ è ç ö ø ÷ Ｄ ｅｘｐ（－Ｄ ２ｍ ２ σｍｉｎ ２ ρ ２ ２ ）μ（Ｂε ），则 ｐｒ（Ｐ ｋ＋１ ｇ ∈ Ｂε ｜ Φｋ ＝ Φ） ≥ ρ ＞ ０。 定理 １ 设（Φ１ ，Φ２ ，Φ３ ，…）∈Ω 是由算法任意 生成的状态序列，则序列 ｐ ｋ ｇ { } 依概率 １ 收敛到 ε⁃最 优解，即 ｌｉｍ ｋ→¥ ｐｒ｛ｐ ｋ ｇ ∈ Ｂε ｝ ＝ １ 证明 由算法可知，Φｋ＋１只与Φｋ 有关，所以Φ１ ， Φ２ ，Φ３ ，…是马尔可夫过程，由马尔可夫过程性质及 引理 １ 可知 ｐｒ（Ｐ ｋ＋１ ｇ ∉ Ｂε ） ＝ ｐｒ（Ｐ １ ｇ ∉ Ｂε ）· ∏ ｋ ｔ ＝ １ ｐｒ（Ｐ ｔ＋１ ｇ ∉ Ｂε Ｐ ｔ ｇ ∉ Ｂε ） ≤ ∏ ｋ ｔ ＝ １ ｐｒ（Ｐ ｔ＋１ ｇ ∉ Ｂε Ｐ ｔ ｇ ∉ Ｂε ） 第 ４ 期 钱伟懿，等：依概率收敛的改进粒子群优化算法 ·５１３·
,514 智能系统学报 第12卷 令 选取文献[24]中的13个测试函数进行实验研究。 △={ΦP.EB}CΦy 前7个函数为高维单峰函数，后6个函数是高维多 则HΦ∈中，由引理3有 峰函数。在本文中13个问题的维数都取30。PS0 pr(P”生BlP生B）≤ 算法的实验结果与LDIWPSO2]、CDIWPSO) pr(P生B|④，=D)=1-p DAPSO[4、和SSRDIWPSOL]实验结果进行比较。 所有算法的共同参数设置如下：oam=0.9,ωmd= 于是pr(PeB)≤1-(1-p),故 0.4,p=30,G1=c2=2,"n=0.5xin,"m.=0.5x, lim pripB=1 Km=3000,PS0算法的其他参数设置如下：P,=2, 数值实验 P2=0.1,0mx=1,0mm=0.2。所有算法的程序都是 由MATLAB2007实现，且每个实验独立运行30次， 为了评价改进算法（简称，PS0)的性能，我们 实验结果见表1和表2。 表1 高维单峰函数的实验结果 Table 1 Experimental results for unimodal functions 测试函数 LDIWPSO CDIWPSO DAPSO SSRDIWPSO IPSO 最好收敛值 1.8024×1018 8.0553×10~39 1.4906x10-20 6.8915x10-8 2.9978×1048 最差收敛值 1.9980x105 7.1317×102 4.7508×1014 6.3577×108 4.9490×10~37 平均收敛值 2.5759×10-16 2.3817×10-2 2.1494×10-15 3.3532×104 1.0262×10~8 方差 1.7596x1031 1.6952×104 7.5669x10-2 2.0137×10-6 2.3843×105 最好收敛值 1.1885×1012 6.5151×109 7.2893×1014 1.7545×1024 4.9281×1032 最差收敛值 7.2170×109 1.1902×10~0 7.8997×10 3.3250×1018 1.1493×10 平均收敛值 3.1295×100 6.8920x102 4.6966×109 2.3788×1019 1.2719x1029 方差 1.7210×10~ 6.0557x102 2.4803×10~16 5.7642×107 1.0997×10~56 最好收敛值 68.4539 1.1843 58.2694 0.0929 2.3526×1025 最差收敛值 668.4762 55.9227 577.0090 4.0948 7.4470×10 平均收敛值 255.7415 13.9276 230.0843 0.8589 7.8654×10-2 方差 2.4053×10 0.6244 1.4937×10 0.8771 2.0584×10 最好收敛值 2.0365 0.5392 1.8241 0.1273 1.8101×1024 最差收敛值 8.2982 3.8830 8.7478 0.9779 1.0096×10-9 平均收敛值 4.8073 2.2561 5.1848 0.4659 2.7701×1020 方差 3.3552 0.6244 2.6767 0.0702 3.6932×100 最好收敛值 0.3308 0.0069 6.6552 0.0083 23.5679 最差收敛值 147.1466 96.3554 119.8775 91.9750 24.6369 平均收敛值 50.7752 35.5231 44.3036 39.8869 24.1214 方差 1.4967×103 877.0478 1.1164×103 906.3516 0.0269 最好收敛值 0 0 0 0 0 最差收敛值 0 0 0 0 0 平均收敛值 0 0 0 0 0 方差 0 0 0 0 0 最好收敛值 0.0064 0.0077 0.0131 0.0047 1.9271×106 最差收敛值 0.0496 0.0355 0.0441 0.0218 5.2760×104 平均收敛值 0.0248 0.0171 0.0277 0.0115 1.4020×10-3 方差 1.0811×10 4.3125×10 8.5989x10 1.5079×10 1.1127×108
令 Δ ＝ ｛Φ Ｐｇ ∉ Ｂε ｝ ⊂ ΦＮｐ 则∀Φ∈ΦＮｐ ，由引理 ３ 有 ｐｒ（Ｐ ｔ＋１ ｇ ∉ Ｂε Ｐ ｔ ｇ ∉ Ｂε ） ≤ ｐｒ（Ｐ ｔ＋１ ｇ ∉ Ｂε Φｔ ＝ Φ） ＝ １ － ρ 于是 ｐｒ（Ｐ ｋ＋１ ｇ ∈Ｂε ）≤１－（１－ρ） ｋ ，故 ｌｉｍ ｋ→¥ ｐｒ｛ｐ ｋ ｇ∈Ｂε ｝ ＝ １ ４ 数值实验 为了评价改进算法（简称，ＩＰＳＯ） 的性能，我们 选取文献［２４］中的 １３ 个测试函数进行实验研究。 前 ７ 个函数为高维单峰函数，后 ６ 个函数是高维多 峰函数。 在本文中 １３ 个问题的维数都取 ３０。 ＩＰＳＯ 算 法 的 实 验 结 果 与 ＬＤＩＷＰＳＯ ［２］ 、 ＣＤＩＷＰＳＯ ［３］ 、 ＤＡＰＳＯ ［４］ 、和 ＳＳＲＤＩＷＰＳＯ ［５］ 实验结果进行比较。 所有算法的共同参数设置如下：ωｓｔａｒｔ ＝ ０． ９，ωｅｎｄ ＝ ０．４，Ｎｐ ＝ ３０，ｃ１ ＝ ｃ２ ＝ ２，ｖｍｉｎ ＝ ０．５ ｘｍｉｎ ，ｖｍａｘ ＝ ０．５ ｘｍａｘ， Ｋｍａｘ ＝ ３ ０００，ＩＰＳＯ 算法的其他参数设置如下：ρ１ ＝ ２， ρ２ ＝ ０．１， σｍａｘ ＝ １， σｍｉｎ ＝ ０．２。 所有算法的程序都是 由 ＭＡＴＬＡＢ２００７ 实现，且每个实验独立运行 ３０ 次， 实验结果见表 １ 和表 ２。 表 １ 高维单峰函数的实验结果 Ｔａｂｌｅ １ Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｆｏｒ ｕｎｉｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ 测试函数 ＬＤＩＷＰＳＯ ＣＤＩＷＰＳＯ ＤＡＰＳＯ ＳＳＲＤＩＷＰＳＯ ＩＰＳＯ Ｆ１ 最好收敛值 １．８０２ ４×１０ －１８ ８．０５５ ３×１０ －３９ １．４９０ ６×１０ －２０ ６．８９１ ５×１０ －５３ ２．９９７ ８×１０ －４３ 最差收敛值 １．９９８ ０×１０ －１５ ７．１３１ ７×１０ －２２ ４．７５０ ８×１０ －１４ ６．３５７ ７×１０ －４３ ４．９４９ ０×１０ －３７ 平均收敛值 ２．５７５ ９×１０ －１６ ２．３８１ ７×１０ －２３ ２．１４９ ４×１０ －１５ ３．３５３ ２×１０ －４４ １．０２６ ２×１０ －３８ 方差 １．７５９ ６×１０ －３１ １．６９５ ２×１０ －４４ ７．５６６ ９×１０ －２６ ２．０１３ ７×１０ －８６ ２．３８４ ３×１０ －７５ Ｆ２ 最好收敛值 １．１８８ ５×１０ －１２ ６．５１５ １×１０ －１９ ７．２８９ ３×１０ －１４ １．７５４ ５×１０ －２４ ４．９２８ １×１０ －３２ 最差收敛值 ７．２１７ ０×１０ －９ １．１９０ ２×１０ －１０ ７．８９９ ７×１０ －８ ３．３２５ ０×１０ －１８ １．１４９ ３×１０ －２７ 平均收敛值 ３．１２９ ５×１０ －１０ ６．８９２ ０×１０ －１２ ４．６９６ ６×１０ －９ ２．３７８ ８×１０ －１９ １．２７１ ９×１０ －２９ 方差 １．７２１ ０×１０ －１８ ６．０５５ ７×１０ －２２ ２．４８０ ３×１０ －１６ ５．７６４ ２×１０ －３７ １．０９９ ７×１０ －５６ Ｆ３ 最好收敛值 ６８．４５３ ９ １．１８４ ３ ５８．２６９ ４ ０．０９２ ９ ２．３５２ ６×１０ －２５ 最差收敛值 ６６８．４７６ ２ ５５．９２２ ７ ５７７．００９ ０ ４．０９４ ８ ７．４４７ ０×１０ －２１ 平均收敛值 ２５５．７４１ ５ １３．９２７ ６ ２３０．０８４ ３ ０．８５８ ９ ７．８６５ ４×１０ －２２ 方差 ２．４０５ ３×１０ ４ ０．６２４ ４ １．４９３ ７×１０ ４ ０．８７７ １ ２．０５８ ４×１０ －４２ Ｆ４ 最好收敛值 ２．０３６ ５ ０．５３９ ２ １．８２４ １ ０．１２７ ３ １．８１０ １×１０ －２１ 最差收敛值 ８．２９８ ２ ３．８８３ ０ ８．７４７ ８ ０．９７７ ９ １．００９ ６×１０ －１９ 平均收敛值 ４．８０７ ３ ２．２５６ １ ５．１８４ ８ ０．４６５ ９ ２．７７０ １×１０ －２０ 方差 ３．３５５ ２ ０．６２４ ４ ２．６７６ ７ ０．０７０ ２ ３．６９３ ２×１０ －４０ Ｆ５ 最好收敛值 ０．３３０ ８ ０．００６ ９ ６．６５５ ２ ０．００８ ３ ２３．５６７ ９ 最差收敛值 １４７．１４６６ ９６．３５５ ４ １１９．８７７ ５ ９１．９７５ ０ ２４．６３６ ９ 平均收敛值 ５０．７７５ ２ ３５．５２３ １ ４４．３０３ ６ ３９．８８６ ９ ２４．１２１ ４ 方差 １．４９６ ７×１０ ３ ８７７．０４７ ８ １．１１６ ４×１０ ３ ９０６．３５１ ６ ０．０２６ ９ Ｆ６ 最好收敛值 ０ ０ ０ ０ ０ 最差收敛值 ０ ０ ０ ０ ０ 平均收敛值 ０ ０ ０ ０ ０ 方差 ０ ０ ０ ０ ０ Ｆ７ 最好收敛值 ０．００６ ４ ０．００７ ７ ０．０１３ １ ０．００４ ７ １．９２７ １×１０ －６ 最差收敛值 ０．０４９ ６ ０．０３５ ５ ０．０４４ １ ０．０２１ ８ ５．２７６ ０×１０ －４ 平均收敛值 ０．０２４ ８ ０．０１７ １ ０．０２７ ７ ０．０１１ ５ １．４０２ ０×１０ －３ 方差 １．０８１ １×１０ －４ ４．３１２ ５×１０ －５ ８．５９８ ９×１０ －５ １．５０７ ９×１０ －５ １．１１２ ７×１０ －８ ·５１４· 智 能 系 统 学 报 第 １２ 卷
第4期 钱伟懿，等：依概率收敛的改进粒子群优化算法 ·515 表2高维多峰函数的实验结果 Table 2 Experimental results for multimodal functions 测试函数 LDIWPSO CDIWPSO DAPSO SSRDIWPSO IPSO 最好收敛值 -1.0319×10 -1.0536×10 -1.0497×104 -9.3124×103 -1.1622×10 最差收敛值 -8.5820×103 -8.9175×103 -8.1674×103 -7.3383×10 -9.4506×10 平均收敛值 -9.2970×10 -9.6920x10 -9.3788×103 -8.0845×103 -1.0301×10 方差 2.2238×10 1.7414×105 2.2818×105 1.9323×10 1.5892×10 最好收敛值 16.9143 16.9143 21.8891 20.8941 0 最差收敛值 45.7681 45.7681 50.7428 65.6672 0 平均收敛值 30.4703 28.6216 34.1975 41.9872 0 方差 50.4865 49.7484 55.3084 135.8404 0 最好收敛值 4.4714×100 7.9936×10-5 5.3995×10-11 7.9936×105 8.8816×10-6 最差收敛值 5.3020×10 2.4369×10" 1.8997 1.3404 4.4409×105 平均收敛值 8.5364×10-9 8.3057×10B 0.3301 0.0670 9.1778×10-16 方差 104575×10-16 1.9764×10-23 0.4323 0.0898 1.0518×10-31 最好收敛值 0 0 0 0 最差收敛值 0.0296 0.0442 0.0731 0.0566 0 平均收敛值 0.0103 0.0135 0.0142 0.0139 0 方差 7.749×105 1.864×10 2.981×10 2.413×10 0 最好收敛值 4.188×10-7 1.925×10-2 1.812×10 1.780×102 5.124×10-24 最差收敛值 0.4147 0.3110 0.8300 0.6219 3.3658×10-20 平均收敛值 0.0587 0.0276 0.0864 0.0726 2.4129×10-21 方差 0.0087 0.0051 0.0342 0.0250 3.0290×104 最好收敛值 1.4840×10-6 1.3676×10- 2.4086x10-7 3.4452×10-2 8.0767×10~9 最差收敛值 0.0110 0.0110 0.0439 0.0439 0.0210 平均收敛值 0.0033 0.0037 0.0060 0.0027 0.0027 方差 2.6226×10 2.7752×10 1.0769x10+ 1.0007×104 3.4655×10 从表1可以看出，除了测试函数F,、F,和F 法优于其他4种算法。对于测试函数F。,PS0算法 外，PS0算法与其他4种算法相比，在寻优能力和 与其他4种算法获得相同的结果。总之，对于高维 稳定性方面明显优于其他4种算法，特别是测试函 单峰函数来说PSO算法有一定优势，其原因如下： 数F,和F4,其他4种算法不能获得到最优解，而 函数F,~F,都单峰函数，由于PS0算法有较好的 PSO算法能够得到较理想的最优解，且稳定性也非 局部搜索能力，所以PS0算法对于单峰函数具有 常好。对于测试函数F,来说，PS0算法不如 一定优势。函数F,是非线性简单的单峰函数，所以 SSRDIWPS0算法，但是优于其他3种算法。对于测 大多数算法都能够找到最优解：函数F,是很难极小 试函数F,来说，IPS0算法的最好收敛值不如其他4 化的典型病态二次函数，由于其全局最优解与可达 种算法，但是对于平均收敛值和方差来说，PS0算 到的局部最优之间有一道狭窄的山谷，所以算法很
表 ２ 高维多峰函数的实验结果 Ｔａｂｌｅ ２ Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｆｏｒ ｍｕｌｔｉｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ 测试函数 ＬＤＩＷＰＳＯ ＣＤＩＷＰＳＯ ＤＡＰＳＯ ＳＳＲＤＩＷＰＳＯ ＩＰＳＯ Ｆ８ 最好收敛值 －１．０３１ ９×１０ ４ －１．０５３ ６×１０ ４ －１．０４９ ７×１０ ４ －９．３１２ ４×１０ ３ －１．１６２ ２×１０ ４ 最差收敛值 －８．５８２ ０×１０ ３ －８．９１７ ５×１０ ３ －８．１６７ ４×１０ ３ －７．３３８ ３×１０ ３ －９．４５０ ６×１０ ３ 平均收敛值 －９．２９７ ０×１０ ３ －９．６９２ ０×１０ ３ －９．３７８ ８×１０ ３ －８．０８４ ５×１０ ３ －１．０３０ １×１０ ４ 方差 ２．２２３ ８×１０ ５ １．７４１ ４×１０ ５ ２．２８１ ８×１０ ５ １．９３２ ３×１０ ５ １．５８９ ２×１０ ５ Ｆ９ 最好收敛值 １６．９１４ ３ １６．９１４ ３ ２１．８８９ １ ２０．８９４ １ ０ 最差收敛值 ４５．７６８ １ ４５．７６８ １ ５０．７４２ ８ ６５．６６７ ２ ０ 平均收敛值 ３０．４７０ ３ ２８．６２１ ６ ３４．１９７ ５ ４１．９８７ ２ ０ 方差 ５０．４８６ ５ ４９．７４８ ４ ５５．３０８ ４ １３５．８４０ ４ ０ Ｆ１０ 最好收敛值 ４．４７１ ４×１０ －１０ ７．９９３ ６×１０ －１５ ５．３９９ ５×１０ －１１ ７．９９３ ６×１０ －１５ ８．８８１ ６×１０ －１６ 最差收敛值 ５．３０２ ０×１０ －８ ２．４３６ ９×１０ －１１ １．８９９ ７ １．３４０ ４ ４．４４０ ９×１０ －１５ 平均收敛值 ８．５３６ ４×１０ －９ ８．３０５ ７×１０ －１３ ０．３３０ １ ０．０６７ ０ ９．１７７ ８×１０ －１６ 方差 １０４ ５７５×１０ －１６ １．９７６ ４×１０ －２３ ０．４３２ ３ ０．０８９ ８ １．０５１ ８×１０ －３１ Ｆ１１ 最好收敛值 ０ ０ ０ ０ ０ 最差收敛值 ０．０２９ ６ ０．０４４ ２ ０．０７３ １ ０．０５６ ６ ０ 平均收敛值 ０．０１０ ３ ０．０１３ ５ ０．０１４ ２ ０．０１３ ９ ０ 方差 ７．７４９ ×１０ －５ １．８６４ ×１０ －４ ２．９８１ ×１０ －４ ２．４１３ ×１０ －４ ０ Ｆ１２ 最好收敛值 ４．１８８ ×１０ －７ １．９２５ ×１０ －３２ １．８１２ ×１０ －８ １．７８０ ×１０ －３２ ５．１２４ ×１０ －２４ 最差收敛值 ０．４１４ ７ ０．３１１ ０ ０．８３０ ０ ０．６２１ ９ ３．３６５ ８×１０ －２０ 平均收敛值 ０．０５８ ７ ０．０２７ ６ ０．０８６ ４ ０．０７２ ６ ２．４１２ ９×１０ －２１ 方差 ０．００８ ７ ０．００５ １ ０．０３４ ２ ０．０２５ ０ ３．０２９ ０×１０ －４１ Ｆ１３ 最好收敛值 １．４８４ ０×１０ －１６ １．３６７ ６×１０ －３１ ２．４０８ ６×１０ －１７ ３．４４５ ２×１０ －３２ ８．０７６ ７×１０ －１９ 最差收敛值 ０．０１１ ０ ０．０１１ ０ ０．０４３ ９ ０．０４３ ９ ０．０２１ ０ 平均收敛值 ０．００３ ３ ０．００３ ７ ０．００６ ０ ０．００２ ７ ０．００２ ７ 方差 ２．６２２ ６×１０ －５ ２．７７５ ２×１０ －５ １．０７６ ９×１０ －４ １．０００ ７×１０ －４ ３．４６５ ５×１０ －５ 从表 １ 可以看出，除了测试函数 Ｆ１ 、Ｆ５ 和 Ｆ６ 外，ＩＰＳＯ 算法与其他 ４ 种算法相比，在寻优能力和 稳定性方面明显优于其他 ４ 种算法，特别是测试函 数 Ｆ３ 和 Ｆ４ ，其他 ４ 种算法不能获得到最优解，而 ＩＰＳＯ 算法能够得到较理想的最优解，且稳定性也非 常好。 对 于 测 试 函 数 Ｆ１ 来 说， ＩＰＳＯ 算 法 不 如 ＳＳＲＤＩＷＰＳＯ 算法，但是优于其他 ３ 种算法。 对于测 试函数 Ｆ５ 来说，ＩＰＳＯ 算法的最好收敛值不如其他 ４ 种算法，但是对于平均收敛值和方差来说，ＩＰＳＯ 算 法优于其他 ４ 种算法。 对于测试函数 Ｆ６ ，ＩＰＳＯ 算法 与其他 ４ 种算法获得相同的结果。 总之，对于高维 单峰函数来说 ＩＰＳＯ 算法有一定优势，其原因如下： 函数 Ｆ１ ～ Ｆ７ 都单峰函数，由于 ＩＰＳＯ 算法有较好的 局部搜索能力，所以 ＩＰＳＯ 算法对于单峰函数具有 一定优势。 函数 Ｆ１ 是非线性简单的单峰函数，所以 大多数算法都能够找到最优解；函数 Ｆ５ 是很难极小 化的典型病态二次函数，由于其全局最优解与可达 到的局部最优之间有一道狭窄的山谷，所以算法很 第 ４ 期 钱伟懿，等：依概率收敛的改进粒子群优化算法 ·５１５·