·374. 智能系统学报 第8卷 2.2惯性权重的调整 开始 在粒子群优化算法中，搜索陷入局部极值，往往 初始化种群☐ 表现为算法重复进行无效的搜索，而粒子的位置几 初始化状态标志1ag=1 乎静止不变.为了充分发挥自适应群体结构的效能， 本文根据适应函数值的不同采用不同的惯性权重， 计算每个粒子的适应值 以求全局最小值为例，群体中的粒子按适应值f的 计算个体历史最好位置和全局最好位置 变化情况分为以下3种情况： 1)群体中满足f∫的粒子已经比较接近全局 flag=0Ediversity(S.)<d 最优，此时应赋予较小的惯性权重，以促进快速收敛 Y 将粒子与全局最优粒子建立新连接 于全局最优.因此将此集合中的粒子的惯性权重调 整为 依据适应值重新计算的值。 =w-（w-w (4) 根据速度和位置方程更新粒子的速度和位置 取ωm=0.5,由式(4)可以看出，粒子的适应值越 满足终止条件 好，其对应的惯性权重就越小，进而加强了局部寻优 Y 的能力. 结束☐ 2)如果粒子满足∫寸f,则说明这些粒子具 图1SPS-PS0算法流程 有较好的局部和全局的寻优能力，此时应保证在前期 Fig.1 Flow chart of SPS-PSO algorithm 粒子进行“开发”性搜索，获得较多候选解，后期进行 3 “勘探”性搜索，探索出全局最优因此考虑这部分粒 仿真实验 子采用经典的惯性权重线性递减的调整方法 3.1测试函数和参数设置 3)对于群体中较差的粒子，即f>f时，借鉴吴 为了测试新算法对复杂问题寻优的有效性，本 浩扬等]提出的变异方法来调整惯性权重： 文选取了3个Benchmark测试函数进行仿真实验. 1 实验环境为Intel CPU2.1GB,Windows XP操作系 =1.5-1+kxexp( 统、1.0GB内存，Visual C++6.0环境下进行编程.为 当群体搜索到的最优位置长时间未发生变化 确保实验结果的可信度，每个算法运行20次实验， 时，群体根据粒子的分布特点来调整惯性权重.若粒 初始化种群个数为100，问题维数30维，最大进化 子分布较为分散，则△取较大的值来降低粒子的惯 代数为1000.算法中，加速因子c1、2均取1.5，w的 性权重，加强局部寻优，使群体趋于收敛：若粒子分 初始值取0.9，d取5×10-6. 布较为聚集，算法陷入局部最优，则△取较小的值 I)Sphere函数. 增加粒子的惯性权重，促使粒子有效地跳出局部最 Sphere函数为可分离的单峰函数，用于测试算 优.其中参数k主要用来调整惯性权重的上限，文中 法的收敛精度，函数在x,=0处到达全局极小值0 取k=1.5. 2.3算法流程 ()=2,-100≤≤10 根据以上分析，基于SPS-PSO(particle swarm 2)Rastrigrin函数. optimization based on self-adaptive population struc- Rastrigrin函数是不可分离的多峰函数，较难优 ture,SPS-PSO)的基本步骤为：先初始化种群：设置 化，全局最小值在变量为0时到达，该函数有10n个 初始化的状态标志lag=1:计算每个粒子的适应值， 局部极小点 并且评估个体的历史最好位置和全局最好位置：果 当前位置优于前一次搜索，则lag=l,否则设置lag= f5(x)=∑[x-10c0s(2mx:+10)], 0:若连续t次f1ag的值始终为0，此时检测该粒子邻 -5.12≤x:≤5.12. 域的群体多样性，与最优粒子建立新的连接，并依据 3)Griwank函数. 适应值重新计算ω的值，然后更新粒子的速度和位 Griwank函数也是不可分离的多峰优化函数， 置，进行下一步的搜索 函数在x:=0时到达全局最小值，该函数有2n个局 SPS-PS0算法的流程图如图1. 部极小值.２．２ 惯性权重的调整 在粒子群优化算法中，搜索陷入局部极值，往往 表现为算法重复进行无效的搜索，而粒子的位置几 乎静止不变．为了充分发挥自适应群体结构的效能， 本文根据适应函数值的不同采用不同的惯性权重， 以求全局最小值为例，群体中的粒子按适应值 ｆ ｉ 的 变化情况分为以下 ３ 种情况： １）群体中满足 ｆ ｉ＜ｆ′ａｒｇ的粒子已经比较接近全局 最优，此时应赋予较小的惯性权重，以促进快速收敛 于全局最优．因此将此集合中的粒子的惯性权重调 整为 ω ＝ ω － （ω － ωｍｉｎ ） ｆ ｉ － ｆ′ａｒｇ ｆ ｇ － ｆ′ａｒｇ ． （４） 取 ωｍｉｎ ＝ ０．５，由式（４） 可以看出，粒子的适应值越 好，其对应的惯性权重就越小，进而加强了局部寻优 的能力． ２）如果粒子满足 ｆ′ａｒｇ ＜ｆ ｉ ＜ｆ ａｒｇ，则说明这些粒子具 有较好的局部和全局的寻优能力，此时应保证在前期 粒子进行“开发”性搜索，获得较多候选解，后期进行 “勘探”性搜索，探索出全局最优．因此考虑这部分粒 子采用经典的惯性权重线性递减的调整方法． ３）对于群体中较差的粒子，即 ｆ ｉ ＞ｆ ａｒｇ时，借鉴吴 浩扬等［１２］提出的变异方法来调整惯性权重： ω ＝ １．５ － １ １ ＋ ｋ × ｅｘｐ（ － Δ） ，Δ ＝｜ ｆ ｇ － ｆ′ａｒｇ ｜ ． 当群体搜索到的最优位置长时间未发生变化 时，群体根据粒子的分布特点来调整惯性权重．若粒 子分布较为分散，则 Δ 取较大的值来降低粒子的惯 性权重，加强局部寻优，使群体趋于收敛；若粒子分 布较为聚集，算法陷入局部最优，则 Δ 取较小的值 增加粒子的惯性权重，促使粒子有效地跳出局部最 优．其中参数 ｋ 主要用来调整惯性权重的上限，文中 取 ｋ ＝ １．５． ２．３ 算法流程 根据以上分析，基于 ＳＰＳ⁃ＰＳＯ （ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ ｏｎ ｓｅｌｆ⁃ａｄａｐｔｉｖｅ ｐｏｐｕｌａｔｉｏｎ ｓｔｒｕｃ⁃ ｔｕｒｅ， ＳＰＳ⁃ＰＳＯ）的基本步骤为：先初始化种群；设置 初始化的状态标志 ｆｌａｇ ＝ １；计算每个粒子的适应值， 并且评估个体的历史最好位置和全局最好位置；果 当前位置优于前一次搜索，则 ｆｌａｇ ＝ ｌ，否则设置ｆｌａｇ ＝ ０；若连续 ｔ 次 ｆｌａｇ 的值始终为 ０，此时检测该粒子邻 域的群体多样性，与最优粒子建立新的连接，并依据 适应值重新计算 ω 的值，然后更新粒子的速度和位 置，进行下一步的搜索． ＳＰＳ⁃ＰＳＯ 算法的流程图如图 １． 图 １ ＳＰＳ⁃ＰＳＯ 算法流程 Ｆｉｇ．１ Ｆｌｏｗ ｃｈａｒｔ ｏｆ ＳＰＳ⁃ＰＳＯ ａｌｇｏｒｉｔｈｍ ３ 仿真实验 ３．１ 测试函数和参数设置 为了测试新算法对复杂问题寻优的有效性，本 文选取了 ３ 个 Ｂｅｎｃｈｍａｒｋ 测试函数进行仿真实验． 实验环境为 Ｉｎｔｅｌ ＣＰＵ ２．１ ＧＢ，Ｗｉｎｄｏｗｓ ＸＰ 操作系 统、１．０ ＧＢ 内存，Ｖｉｓｕａｌ Ｃ＋＋６．０ 环境下进行编程．为 确保实验结果的可信度，每个算法运行 ２０ 次实验， 初始化种群个数为 １００，问题维数 ３０ 维，最大进化 代数为１ ０００．算法中，加速因子 ｃ１ 、ｃ２ 均取 １．５，ω 的 初始值取 ０．９，ｄＬｏｗ取 ５×１０ －６ ． １）Ｓｐｈｅｒｅ 函数． Ｓｐｈｅｒｅ 函数为可分离的单峰函数，用于测试算 法的收敛精度，函数在 ｘｉ ＝ ０ 处到达全局极小值 ０． ｆ １（ｘ） ＝ ∑ Ｄ ｉ ＝ １ ｘｉ， － １００ ≤ ｘｉ ≤ １００． ２）Ｒａｓｔｒｉｇｒｉｎ 函数． Ｒａｓｔｒｉｇｒｉｎ 函数是不可分离的多峰函数，较难优 化，全局最小值在变量为 ０ 时到达，该函数有 １０ｎ 个 局部极小点． ｆ ２（ｘ） ＝ ∑ Ｄ ｉ ＝ １ ［ｘ ２ ｉ － １０ｃｏｓ（２πｘｉ ＋ １０）］， － ５．１２ ≤ ｘｉ ≤ ５．１２． ３）Ｇｒｉｗａｎｋ 函数． Ｇｒｉｗａｎｋ 函数也是不可分离的多峰优化函数， 函数在 ｘｉ ＝ ０ 时到达全局最小值，该函数有 ２ｎ 个局 部极小值． ·３７４· 智 能 系 统 学 报 第 ８ 卷