第5期 王超，等：参数自适应粒子群算法的给水管网优化研究 ·725· 示粒子与期望粒子的相似程度，并自适应调整惯性 就是对原有粒子位置产生一个服从Gaussian分布的 权重和2个加速系数，同时实现变异的自适应性，有 随机扰动项，其中δ为Gaussian分布的标准差，4为 效平衡了粒子群算法的全局搜索能力和收敛速度。 期望，δ越小分布会越集中在x=μ的位置，反之会越 PS0算法搜索前期选择较大权重值，加强粒子 分散。 探索能力，后期选择较小权重值，保持算法收敛速 变异的位置为x物，公式为 度，这种思想被广泛采用。但所有粒子的权重被统 xn（t)=xin+入（x加s一xmin） (28) 一调整，忽略了粒子之间的差异性，若早期就有粒子 变异后粒子的新位置为该粒子上一代位置与变 找到全局最优点，却因其权重过大而跳出，则会降低 异位置连线的中点，公式为 算法搜索效率。为此，本文设计出一种根据各粒子 x'(t)=0.5(xg(t)+xm(t)) (29) 与期望粒子相似度不同而动态调整权重的PS0算 分期变异机制的主要特点：通过评估整个种群 法，公式为 的分布情况，通过该粒子与期望粒子相似程度大小 w*1=wx-(ωmx-wmn）×s(i,e）(21) 来决定是否对其变异：2种变异方法分期交叉进行， 与期望粒子相似度较小的粒子，权重应较大，加 很好地平衡了种群多样性和算法的收敛能力，在前 快粒子探索整个解空间：反之，其权重应较小，这样 期避免算法陷入局优，后期可以使算法快速找到全 可使该粒子在期望最优位置领域内进行微小探索， 局最优值。 加强粒子的开发能力。 2.4算法流程及性能测试 加速系数c,是个体认知，c,是社会认知，算法搜 设微粒数为N,问题的维数为D,最大迭代步数 索初期，c1应较大，增加种群多样性，2应较小，避免 为Tm,本文算法描述如下： 种群陷入局部最优：搜索后期，逐渐找到最优区域， 1)初始化，包括各参数：N、x、v、T,随机产生 c,应较小，加快收敛速度，c2应较大，领导种群趋向 N个粒子及其初始速度，并计算适应度； 全局最优位置。结合以上c1,c,的调整思想，提出其 2)更新粒子的位置和速度： 迭代公式如下： 3)评价种群中各粒子的适应度； c=c1as-(c1s-c1mn）×s'(i,e） (22)》 4)根据适应度值更新粒子的个体极值Y:; c1=c1mim+(c2mx-c2min）×s'(i,e）（23) 5)根据适应度更新种群的全局极值Y; 2.3 分期变异机制 6)计算粒子之间的相似度s(i,e),并根据式 PS0算法在迭代过程中会因种群多样性的缺失 (21)更新惯性权重； 而陷入局部最优，为增加种群多样性，对种群粒子进 7)根据式(24)计算变异概率，并判断是否满足 行变异，当粒子与期望粒子相似度越大时，对应粒子 变异条件，若满足变异条件，则根据式(26)~(29) 变异的概率应越小，反之亦然。定义变异概率p和 进行分期交叉变异，重新计算粒子适应度，并更新 变异条件分别如下： Y、Y.; T p.=cos(2(i,e)） (24) 8)判断算法的终止条件，若满足则停止，输出 相关结果：否则转2)。 rand()<Pim (25) 为了验证算法的有效性，将PAPS0算法用于优 为有效平衡算法的全局搜索能力和收敛速度， 化汉诺塔管网和纽约管网，2个经典管网的布局图、 将混沌变异和Gaussian变异分期交叉进行，整个迭 节点水压和管段长度等详细数据参照文献[18]。 代过程分为4个阶段，每个阶段的前20%的迭代步 根据汉诺塔管网实际问题，进行参数敏感性分 数进行混沌变异，后5%的迭代步数进行Gaussian 析后，PAPSO算法在整个搜索过程中，各参数设置 变异。利用混沌的遍历性，充分增大种群多样性，如 如下：wm=0.9,wmm=0.4,C1=2.05,c2=1.45,V= 式(26)所示；利用Gaussian变异的局部搜索能力， 300,T=100。图1为汉诺塔管网造价收敛曲线， 加快算法的收敛速度，如式(27)所示。 改进的PAPSO算法在第31步就找到了全局最优 Ag=u×A写'(1-A) (26) 值，具有较快的收敛速度。 x expl-(-u) A(x)=1 (27) 对于汉诺塔问题，通过EPANET2.0(w= 282 10.667)水力模拟计算验证，目前最优的解决方案造 式(26)中：A)表示第t步混合演变后的值，当u= 价是6.081×10美元。表1列出了遗传算法、混合 4,A∈(0,1)，且0{0.25,0.5,0.75}时，将产 粒子群差分算法、自适应粒子群算法、差分算法和本 生混沌现象，A,(t)在(0,1)内遍历。Gaussian变异 文提出的PAPSO算法优化汉诺塔问题的结果对比，示粒子与期望粒子的相似程度，并自适应调整惯性 权重和 ２ 个加速系数，同时实现变异的自适应性，有 效平衡了粒子群算法的全局搜索能力和收敛速度。 ＰＳＯ 算法搜索前期选择较大权重值，加强粒子 探索能力，后期选择较小权重值，保持算法收敛速 度，这种思想被广泛采用。 但所有粒子的权重被统 一调整，忽略了粒子之间的差异性，若早期就有粒子 找到全局最优点，却因其权重过大而跳出，则会降低 算法搜索效率。 为此，本文设计出一种根据各粒子 与期望粒子相似度不同而动态调整权重的 ＰＳＯ 算 法，公式为 ω ｔ＋１ ｉ ＝ ωｍａｘ － （ωｍａｘ － ωｍｉｎ ） × ｓ ｔ （ｉ，ｅ） （２１） 与期望粒子相似度较小的粒子，权重应较大，加 快粒子探索整个解空间；反之，其权重应较小，这样 可使该粒子在期望最优位置领域内进行微小探索， 加强粒子的开发能力。 加速系数ｃ１是个体认知，ｃ２是社会认知，算法搜 索初期，ｃ１应较大，增加种群多样性，ｃ２应较小，避免 种群陷入局部最优；搜索后期，逐渐找到最优区域， ｃ１应较小，加快收敛速度，ｃ２应较大，领导种群趋向 全局最优位置。 结合以上ｃ１ ，ｃ２的调整思想，提出其 迭代公式如下： ｃ ｔ＋１ １ｉ ＝ ｃ１ｍａｘ － （ｃ１ｍａｘ － ｃ１ｍｉｎ ） × ｓ ｔ （ｉ，ｅ） （２２） ｃ ｔ＋１ ２ｉ ＝ ｃ１ｍｉｎ ＋ （ｃ２ｍａｘ － ｃ２ｍｉｎ ） × ｓ ｔ （ｉ，ｅ） （２３） ２．３ 分期变异机制 ＰＳＯ 算法在迭代过程中会因种群多样性的缺失 而陷入局部最优，为增加种群多样性，对种群粒子进 行变异，当粒子与期望粒子相似度越大时，对应粒子 变异的概率应越小，反之亦然。 定义变异概率ｐｉｍ和 变异条件分别如下： ｐｉｍ ＝ ｃｏｓ （ π ２ ｓ（ｉ，ｅ）） （２４） ｒａｎｄ（） ＜ ｐｉｍ （２５） 为有效平衡算法的全局搜索能力和收敛速度， 将混沌变异和 Ｇａｕｓｓｉａｎ 变异分期交叉进行，整个迭 代过程分为 ４ 个阶段，每个阶段的前 ２０％的迭代步 数进行混沌变异，后 ５％的迭代步数进行 Ｇａｕｓｓｉａｎ 变异。 利用混沌的遍历性，充分增大种群多样性，如 式（２６） 所示；利用 Ｇａｕｓｓｉａｎ 变异的局部搜索能力， 加快算法的收敛速度，如式（２７）所示。 λ ｔ ｉｊ ＝ ｕ × λ ｔ－１ ｉｊ （１ － λ ｔ－１ ｉｊ ） （２６） λ ｔ ｉｊ（ｘ） ＝ １ δ ２π × ｅｘｐ［ － （ｘ － μ） ２ ２δ ２ ］ （２７） 式（２６）中：λ (ｔ) ｉｊ 表示第 ｔ 步混合演变后的值，当 ｕ ＝ ４，λ （ｔ） ｉｊ ∈（ ０，１），且 λ （ｔ） ｉｊ ∉{０．２５，０．５，０．７５} 时，将产 生混沌现象，λｉｊ（ｔ）在（０， １）内遍历。 Ｇａｕｓｓｉａｎ 变异 就是对原有粒子位置产生一个服从 Ｇａｕｓｓｉａｎ 分布的 随机扰动项，其中 δ 为 Ｇａｕｓｓｉａｎ 分布的标准差，μ 为 期望，δ 越小分布会越集中在 ｘ ＝ μ 的位置，反之会越 分散。 变异的位置为ｘｉｊｍ ，公式为 ｘｉｊｍ（ｔ） ＝ ｘｉｊｍｉｎ ＋ λ ｔ ｉｊ（ｘｉｊｍａｘ － ｘｉｊｍｉｎ ） （２８） 变异后粒子的新位置为该粒子上一代位置与变 异位置连线的中点，公式为 ｘ′ｉｊ（ｔ） ＝ ０．５（ｘｉｊ（ｔ） ＋ ｘｉｊｍ（ｔ）） （２９） 分期变异机制的主要特点：通过评估整个种群 的分布情况，通过该粒子与期望粒子相似程度大小 来决定是否对其变异；２ 种变异方法分期交叉进行， 很好地平衡了种群多样性和算法的收敛能力，在前 期避免算法陷入局优，后期可以使算法快速找到全 局最优值。 ２．４ 算法流程及性能测试 设微粒数为 Ｎ，问题的维数为 Ｄ，最大迭代步数 为Ｔｍａｘ，本文算法描述如下： １）初始化，包括各参数：Ｎ、ｘ、ｖ、Ｔｍａｘ，随机产生 Ｎ 个粒子及其初始速度，并计算适应度； ２）更新粒子的位置和速度； ３）评价种群中各粒子的适应度； ４）根据适应度值更新粒子的个体极值Ｙｉ； ５）根据适应度更新种群的全局极值Ｙｇ ； ６）计算粒子之间的相似度 ｓ （ ｉ，ｅ），并根据式 （２１）更新惯性权重； ７）根据式（２４）计算变异概率，并判断是否满足 变异条件，若满足变异条件，则根据式（２６） ～ （２９） 进行分期交叉变异，重新计算粒子适应度，并更新 Ｙｉ、Ｙｇ ； ８）判断算法的终止条件，若满足则停止，输出 相关结果；否则转 ２）。 为了验证算法的有效性，将 ＰＡＰＳＯ 算法用于优 化汉诺塔管网和纽约管网，２ 个经典管网的布局图、 节点水压和管段长度等详细数据参照文献［１８］。 根据汉诺塔管网实际问题，进行参数敏感性分 析后，ＰＡＰＳＯ 算法在整个搜索过程中，各参数设置 如下：ωｍａｘ ＝ ０． ９，ωｍｉｎ ＝ ０． ４，ｃ１ ＝ ２． ０５，ｃ２ ＝ １． ４５，Ｎ ＝ ３００，Ｔｍａｘ ＝ １００。 图 １ 为汉诺塔管网造价收敛曲线， 改进的 ＰＡＰＳＯ 算法在第 ３１ 步就找到了全局最优 值，具有较快的收敛速度。 对 于 汉 诺 塔 问 题， 通 过 ＥＰＡＮＥＴ２． ０ （ ω ＝ １０．６６７）水力模拟计算验证，目前最优的解决方案造 价是 ６．０８１×１０ ６ 美元。 表 １ 列出了遗传算法、混合 粒子群差分算法、自适应粒子群算法、差分算法和本 文提出的 ＰＡＰＳＯ 算法优化汉诺塔问题的结果对比， 第 ５ 期 王超，等：参数自适应粒子群算法的给水管网优化研究 ·７２５·