.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)计法的效率，另外，证明了该算法依概率 １ 收敛到 ε⁃ 最优解。 实验结果表明，提出的算法能够提高全局 搜索能力，算法的收敛速度明显加快。 １ 标准 ＰＳＯ 算法 标准粒子群算法中，粒子群由 Ｎｐ 个粒子组成， 在时刻 ｋ，第 ｉ 个粒子在 ｄ 维空间中速度和位置的更 新公式为 ｖ ｋ＋１ ｉｄ ＝ ωｖ ｋ ｉｄ ＋ ｃ１ ｒ１（ｐ ｋ ｉｄ － ｘ ｋ ｉｄ ） ＋ ｃ２ ｒ２（ｐ ｋ ｇｄ － ｘ ｋ ｉｄ ） （１） ｘ ｋ＋１ ｉｄ ＝ ｘ ｋ ｉｄ ＋ ｖ ｋ＋１ ｉｄ （２） 式中：ｉ ＝ １，２，…，Ｎｐ，ｄ ＝ １，２，…，Ｄ，Ｄ 为决策变量的 维数，ω 为惯性权重，ｘ ｋ ｉ ＝ （ｘ ｋ ｉ１ ，ｘ ｋ ｉ２ ，…，ｘ ｋ ｉＤ）表示粒子 ｉ 的当前的位置；ｖ ｋ ｉ ＝ （ｖ ｋ ｉ１ ，ｖ ｋ ｉ２ ，…，ｖ ｋ ｉＤ ）是粒子 ｉ 的当前 的速度；Ｐ ｋ ｉ ＝ （ ｐ ｋ ｉ１ ，ｐ ｋ ｉ２ ，…，ｐ ｋ ｉＤ ） 是粒子 ｉ 当前最优位 置，Ｐ ｋ ｇ ＝ （ ｐ ｋ ｇ１ ，ｐ ｋ ｇ２ ，…，ｐ ｋ ｇＤ ）是全局最优位置；ｃ１ 、ｃ２ 是 加速度因子，ｒ１ 、ｒ２ 是 ０～１ 之间的随机数。 第 ｋ 次迭 代的惯性权重表示为 ωｋ ＝ （ωｓｔａｒｔ － ωｅｎｄ ） Ｋｍａｘ － ｋ Ｋｍａｘ æ è ç ö ø ÷ ＋ ωｅｎｄ （３） 式中：ωｓｔａｒｔ、ωｅｎｄ分别为最初和最终的惯性权重，Ｋｍａｘ 是最大迭代步。 ２ 改进的 ＰＳＯ 算法 提高 ＰＳＯ 算法性能的有效方法之一就是平衡 算法的探索能力和开发能力。 我们的目的是对粒 子所经历的最好位置进行操作，一方面能够使其跳 出局部最优；另一方面使其具有一定的局部搜索能 力。 为此，给出两个变异算子： Ｐ －ｋ ｉｄ ＝ Ｐ ｋ ｉｄ·ρ１Ｎ（０，σ ２ ） （４） Ｐ －ｋ ｉｄ ＝ Ｐ ｋ ｉｄ ＋ ρ２Ｎ（０，σ ２ ） （５） 式中：ρ１＞１ 和 ρ２＞１ 是常数，Ｎ（０，σ ２ ）是具有时变标 准差 σ 的高斯分布的随机变量，σ 表示为 σ ＝ σｍａｘ － （σｍａｘ － σｍｉｎ ） ｋ Ｋｍａｘ （６） 式中：σｍａｘ和 σｍｉｎ是标准差 σ 的最终和初始值，ｋ 是 当前迭代步，Ｋｍａｘ是最大迭代步。 因为 ρ１Ｎ（０，σ ２ ） 的值比 １ 大或比 １ 小，又因为 Ｐ ｋ ｉｄ·ρ１Ｎ（０，σ ２ ）是一 个随机值，所以它比 Ｐ ｋ ｉｄ 大或小，这样 Ｐ －ｋ ｉｄ 可能远离 Ｐ ｋ ｉｄ ，因此说式（４）具有一定的全局搜索能力。 另一 方面，式（５）表明在 Ｐ ｋ ｉｄ附近搜索，因此式（５）具有一 定的局部搜索能力。 如果每次都对Ｐ ｋ ｉ 实施式（４）或式（５）的变异操 作，那么导致算法运行时间长，因此按一定概率 μ 对 Ｐ ｋ ｉ 实施式（４）或式（５）的变异操作，即当 ｆ（Ｐ ｋ ｉ ）≤ｆ ａｖｅ 时，对Ｐ ｋ ｉ 按概率 μ 实施式（５）的变异操作，当ｆ（Ｐ ｋ ｉ ）＞ ｆ ａｖｅ时，对Ｐ ｋ ｉ 按概率 μ 实施式（４）的变异操作，其中 ｆ ａｖｅ ＝ １ Ｎｐ ∑ Ｎｐ ｊ ＝ １ ｆ（Ｐ ｋ ｊ ）， （７） μ ＝ α（ｆ ａｖｅ － ｆ（Ｐ ｋ ｉ ）） ｆ ａｖｅ － ｆ（Ｐ ｋ ｇ ） ， ｆ（Ｐ ｋ ｉ ） ≤ ｆ ａｖｅ α（ｆ（Ｐ ｋ ｉ ） － ｆ ａｖｅ） ｆｍａｘ － ｆ ａｖｅ ， ｆ（Ｐ ｋ ｉ ） ＞ ｆ ａｖｅ ì î í ï ïï ï ïï （８） 式中：ｆｍａｘ ＝ ｍａｘ １≤ｉ≤Ｎｐ ｛ ｆ（Ｐ ｋ ｉ ）｝，α 是一个自适应参数，它 被定义为 α ＝ １ － ０．８ ｋ Ｋｍａｘ （９） 由式（８）知，对适应值较好的粒子实施局部搜 索的概率较大，而对适应值较差的粒子实施全局搜 索的概率较大。 由于当算法迭代到后期，粒子比较 集中，从而导致 ｆ ａｖｅ －ｆ（Ｐ ｋ ｉ ） ｆ ａｖｅ －ｆ（Ｐ ｋ ｇ ） 或 ｆ（Ｐ ｋ ｉ ）－ｆ ａｖｅ ｆｍａｘ －ｆ ａｖｅ 接近 １，若 α 大，那么实施式（４） 或式（５） 的变异操作的粒子较 多，从而导致算法运算时间长，因此按式（９）实行单 调递减策略。 位置与速度越界处理： ｘ ｋ＋１ ｉｄ ＝ ｘ ｋ＋１ ｉｄ ， ｌ ｄ ≤ ｘ ｋ＋１ ｉｄ ≤ ｕｄ ｌ ｄ ＋ ｒａｎｄ（）·（ｕｄ － ｌ { ｄ ）， 其他 （１０） ｖ ｋ＋１ ｉｄ ＝ ｖ ｋ＋１ ｉｄ ， ｖｍｉｎ ≤ ｖ ｋ＋１ ｉｄ ≤ ｖｍａｘ ｖｍｉｎ ， ｖ ｋ＋１ ｉｄ ＜ ｖｍｉｎ ｖｍａｘ， ｖ ｋ＋１ ｉｄ ＞ ｖｍａｘ ì î í ï ï ï ï （１１） 式中：ｖ ｍｉｎ ｄ ＝ ０．５ｌ ｄ ，ｖ ｍａｘ ｄ ＝ ０．５ｕｄ 。 改进 ＰＳＯ 算法的流程如下： １）设置参数，随机初始化粒子的位置和速度， 计算各粒子的适应度，确定每个粒子的经历过的最 优位置及全局最优位置，令 ｋ ＝ １； ２）按式（３）计算惯性权重，并按式（１）和式（２） 进行速度与位置更新； ３） 按式（１０）和式（１１）进行越界处理； ４） 对粒子 ｉ（ｉ ＝ １，２，…，Ｎｐ ）计算其适应值，更 新其经历过的最优位置Ｐ ｋ＋１ ｉ 和全局最优位置Ｐ ｋ＋１ ｇ ， 并按式（７）计算 ｆ ａｖｅ； ５） 若 ｆ（Ｐ ｋ＋１ ｉ ）≤ｆ ａｖｅ，按式（９）计算 α，按式（８）计 算 μ，在［０，１］选取一个随机数 ｒａｎｄ，若 ｒａｎｄ＜ μ，则 按式（６）计算 σ，按式（５）更新粒子经历过的最优位 置，得到Ｐ －ｋ＋１ ｉ ，转 ７）； ６）若 ｆ（Ｐ ｋ＋１ ｉ ）＞ｆ ａｖｅ，按式（９）计算 α，按式（８）计 ·５１２· 智 能 系 统 学 报 第 １２ 卷