CW-PSO及其在古建筑传感器优化配置中的应用研究.pdf

Computer Engineering and Applications计算机工程与应用2013， 49 （5） 1引言 近几年来， 在文物保护方面， 木构古建筑本体及其环 境的监测显得越来越重要。通过对木构古建筑进行监测， 可以为文物建筑的维护方案提供可靠和必要的数据。环 境监测是建筑结构健康监测的重要部分， 传感器优化配置 是健康监测的基础。如何将有限数量的传感器布置在合 适的节点上并获得较为全面的信息是目前健康监测领域 研究的热点之一。 粒子群优化算法 （PSO） 是一种基于群智能的全局优化 方法[1-2]， 它源于对鸟群觅食运动行为的模拟。目前已广泛 应用于函数优化[3-4]、 神经网络训练[5]、 组合优化[6-7]、 模式分 类和模糊控制以及工程应用[8-9]等领域。但是它存在局部 搜索能力较差， 搜索精度不高并且容易早熟等问题。为了 提高算法的性能， 研究者在PSO算法的参数以及与其他算 法相结合方面做了很多研究[10-11]。 2标准粒子群算法描述 粒子群优化算法 （Particle Swarm Optimization， PSO） 是Kennedy和Eberhart于1995年提出的一种基于种群搜索 策略的全局优化进化算法， 它模拟鸟类的觅食行为， 通过 个体间的协作和竞争实现最优解的搜索。在求解优化问 题时， 算法首先初始化产生一群随机粒子， 在解决实际问 题中粒子代表问题的一个可能解。粒子群优化算法是基 于群体和适应度的， 在迭代过程中， 通过粒子的适应度函 数值来评价粒子的优劣。每个粒子具有位置和速度两个 特征， 假设粒子在D维的目标搜索空间中飞行， 那么第i个 粒子的位置表示为 Xit{xi1txi2txiDt} 第i个粒子的速度表示为 Vit{vi1tvi2tviDt} 粒子当前搜索到的最优值称为个体极值， 当前群体最 CW-PSO及其在古建筑传感器优化配置中的应用研究 路杨 1， 张晓丽2 LU Yang1, ZHANG Xiaoli2 1.河南大学 计算中心， 河南 开封 475000 2.河南大学 计算机与信息工程学院， 河南 开封 475000 1.Computing Center, Henan University, Kaifeng, Henan 475000, China 2.School of Computer and Ination Engineering, Henan University, Kaifeng, Henan 475000, China LU Yang, ZHANG Xiaoli. Particle swarm optimization based on cosine adaptive adjusting inertia weight and its applica- tion research in optimal sensor placement of historic architecture. Computer Engineering and Applications, 2013, 49 （5） 268-270. Abstract Aiming at the premature convergence problem and unbalance of global search and local search in particle swarm opti- mization algorithm, this paper proposes a particle swarm optimization algorithm based on cosine adaptive adjusting inertia weight. The improved particle swarm optimization is applied in optimal sensor placement of wooden historic architecture. Simu- lation results show that it can avoid premature convergence to an extent, improve the global search ability and obtain accurate results of optimization by simulation experiment. Key words particle swarm optimization algorithm; inertia weight; wooden historic architecture; optimal sensor placement 摘要 针对粒子群优化算法容易陷入早熟收敛以及全局搜索和局部搜索平衡能力差等缺点， 提出了基于余弦自适应调 整惯性权重的粒子群优化算法 （CW-PSO） ， 并将其应用在木构古建筑传感器优化配置中。仿真结果表明， 该算法在一定程 度上避免了早熟收敛， 提高了全局和局部搜索性能， 又能得到较为精确的寻优结果。 关键词 粒子群优化算法； 惯性权重； 木构古建筑； 传感器优化配置 文献标志码 A中图分类号 TP39doi 10.3778/j.issn.1002-8331.1209-0029 基金项目 国家青年基金 （No.61203094） ； 河南省科技攻关 （No.122102210052） 。 作者简介 路杨 （1972） ， 女， 博士， 副教授， 主要研究方向 模式识别、 数据挖掘； 张晓丽 （1987） ， 女， 硕士生， 主要研究方向 模式识别、 数据挖掘。E-mail kangkangxiao2006 收稿日期 2012-09-10修回日期 2012-12-06文章编号 1002-8331 （2013） 05-0268-03 268 2013， 49 （5） 优称为全局极值。在每次迭代过程中， 粒子通过跟踪个体 极值和当前粒子群找到的最优解即全局极值来更新自己 的速度和位置， 从而搜寻到问题的最优解。粒子的速度与 位置更新公式如下 vijt 1 wvijt c1r1pij- xijt c2r2pgj- xijt（1） xijt 1 xijt vijt 1（2） 在式 （1） 和式 （2） 中，1 j D，w为惯性权重， 学习因 子c1、 c2是非负常数， 通常取值为2；vijt[-vmaxvmax]；r1和 r2是介于[0， 1]之间的随机数；vmax是常数， 由用户设定。 3基于余弦自适应调整惯性权重的粒子群优化 算法 （CW-PSO） 3.1种群聚集度 种群聚集度反映了所有粒子当前的聚集程度[12]， 聚集 度s如式 （3） 所示。 s minfavgtfgt maxfavgtfgt （3） 其中favgt是第t代中所有粒子的平均适应度值，fgt是 第t代粒子群中最优粒子的适应度值。其中0 s 1， 反映 了所有粒子当前的聚集程度，s越小， 说明粒子群中所有的 粒子越分散，s越大， 粒子越聚集。 3.2余弦自适应调整惯性权重策略 惯性权重w在粒子群优化算法中起着至关重要的作 用， 控制着 PSO的全局与局部搜索能力。w值越大， 全局 搜索能力越强， 有利于跳出局部极值； 反之， 局部开发能力 越强， 越容易收敛[13]。在标准粒子群算法中， Shi Y等人[14] 采取线性递减惯性权重策略 （LDW） ， 即 w wminwmax- wmin.Tmax - t Tmax w从0.9到0.4线性下降， 使得PSO在搜索初期快速寻找到 全局最优解， 随着w逐渐减小， 粒子速度变慢， 开始精细的 局部搜索。研究者又相继提出了模糊调整惯性权重策略、 随机调整惯性权重策略等， 研究表明这些调整策略能有效 避免粒子群的早熟收敛， 优化结果精度较高。 文献[15]提出基于步长较小的惯性权重线性递减策略 （SL-PSO） ， 步长较小， w的变化幅度较小， 粒子群不易陷入 局部最优。但是由于线性递减惯性权重策略普遍存在不 能很好地平衡全局和局部搜索能力的缺点。为了弥补线 性递减惯性权重策略的不足， 本文对文献[15]中的惯性权 重进行修正， 在其基础上提出了基于余弦自适应调整惯性 权重的粒子群优化算法 （CW-PSO） ， 并引入种群聚集度的 概念。w的修正策略如下 （1） 当0 s 1 2 时， 粒子的位置分布比较分散， 以步长 1/T 2 max非线性递减。由式 （4） 可以看出， 步长较小，w的减 小速度缓慢， 维护了群体的多样性， 有利于全局搜索， 从而 避免了算法的早熟收敛。 w wminwmax- wmincosπ 2 t T 2 max （4） （2） 当 1 2 s 1时， 此时粒子的位置相对比较集中， 以 步长1/Tmax非线性递减， 相比式 （4） ， 步长增大，w的减小 趋势加快。由于余弦函数的特点， 避免了粒子群体的多样 性迅速降低。与SL-PSO算法相比， CW-PSO算法更易进行 精细的局部搜索， 提高了算法的精度。 w wminwmax- wmincosπ 2 t Tmax （5） 在式 （4） 、 式 （5） 中wmax为最大惯性权重，wmin为最小 惯性权重，Tmax为终止迭代次数，t为当前进化代数。 4基于CW-PSO的传感器优化配置 设 n个温度传感器所在节点的位置为x1x2xn并 按从 1到 n编码， 在某时刻每个温度传感器测得的温度观 测值为T1T2Tn。在建筑物结构上布置传感器， 为了 减少传感器的数量， 在保证能获得较为全面的温度信息的 前提下， 尽可能选择在温差较大的节点上布置传感器。假 设共有n个节点， 传感器的预算个数为p， 则S表示为粒子 位置对应的p个传感器节点的集合， 这p个整数均介于 1 到n之间且互不相等。在本文中， 问题解的优化目标函数 如式 （6） 所示， 粒子群优化的目的是为了使f最大化。其 中k i，i S， 由于温度传感器是实时监测的， 为了简化适 应度函数， 本文设定Ti是在一个节点i上某月的平均温度。 f 1 p k S i 1 n Ti- Tk n- p （6） 5仿真实验 选取建筑物结构的 20个节点， 按从 1到 20进行编码。 经测量统计， 每个节点在 2007年 11月份测得的平均温度 如表1所示。 按照粒子群算法的流程， 用MATLAB仿真工具编制了 程序。取粒子数 M10， 传感器预算数目 P，wmax 0.9， wmin 0.4。本文用式 （6） 的适应度函数测试CW-PSO算法 的性能， 并与线性递减惯性权重粒子群算法 （LDW） 、 基于 步长的线性递减策略粒子群优化算法 （SL-PSO） 进行比 较。三种粒子群算法所取参数均和上述参数相同。为了 节点ID 1 2 3 4 5 6 7 8 9 10 平均温度/℃ 9.412 0 11.236 4 10.367 0 15.464 4 10.661 6 13.668 4 11.494 1 16.917 8 13.033 2 11.150 1 节点ID 11 12 13 14 15 16 17 18 19 20 平均温度/℃ 12.253 6 13.054 4 12.446 4 10.465 3 10.216 8 14.618 7 14.781 0 11.147 6 9.366 2 15.315 1 表1节点与平均温度 路杨， 张晓丽 CW-PSO及其在古建筑传感器优化配置中的应用研究 269 Computer Engineering and Applications计算机工程与应用2013， 49 （5） 使结果更加精确， 分别设置Tmax为200、 300， 每个算法独立 运行20次。测试结果如表2和表3所示。 当Tmax为300时， 由图1可以看出， 随着传感器数量的 增加， 粒子的适应度函数值也在增加， 但传感器数量从 9 以后， 适应值递增梯度非常小， 故传感器数量可选9。程序 运行后CW-PSO算法输出的粒子全局最优位置为 （1， 2， 4， 5， 7， 8， 12， 17， 20） ， 最优值为5.659 8。由图2可以看出线性 递减惯性权重算法 （LDW） 收敛速度过慢； SL-PSO 算法采 用基于步长较小的线性递减惯性权重策略， 提高了搜索速 度和收敛精度； CW-PSO 算法迭代速度稍慢于 SL-PSO 算 法， 由于群体的多样性高， 避免了算法过早地收敛以及陷 入局部最优， 并且能够很好地平衡全局搜索和局部搜索能力。 6结束语 针对粒子群优化算法存在早熟收敛以及不能较好地 控制其在全局和局部搜索的平衡性等缺点， 在分析惯性权 重对算法性能影响的基础上提出了基于余弦自适应调整 惯性权重的粒子群优化算法， 并引入种群聚集度概念， 然 后采用该算法对木构古建筑传感器配置进行优化。在粒 子群分布比较分散时， 粒子群收敛速度快， 迭代曲线平稳， 全局搜索能力强； 当粒子的位置比较集中时， 粒子的速度 相对比较缓慢， 在局部范围内寻优能力强。经仿真分析， 算法的性能有了明显的提高， 并且验证了用粒子群优化算 法求解传感器优化配置问题的可行性。 参考文献 [1] Eberhart R C， Kennedy J.A new optimizer using particle swarm theory[C]//Proceedings of the 6th International Sym- posium on Micro Machine and Human Science.Piscataway NJ IEEE Service Center， 1995 39-43. [2] Kennedy J， Eberhart R C.Particle swarm optimization[C]// Proc IEEE International Conference on Neural Networks. Piscataway NJ IEEE Service Center， 1995 1942-1948. [3] He Q， Wang L.An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J]. Engineering Applications of Artificial Intelligence， 2007， 120 （4） 89-99. [4] Wang Y J， Yang Y P.Particle swarm optimization with pref- erenceorderrankingulti-objectiveoptimization[J]. Ination Sciences， 2009， 179 （12） . [5] 高海兵， 高亮， 周驰， 等.基于粒子群优化的神经网络训练算法 研究[J].电子学报， 2004， 32 （9） 1572-1574. [6] 沈显君， 王伟斌， 郑波尽， 等.基于改进的微粒群优化算法的0-1 背包问题求解[J].计算机工程， 2006， 32 （18） 23-24. [7] Tchomte S K.Particle swarm optimization a study of parti- cle displacement for solving continuous and combinatorial- optimization problems[J].Int J Production Economics， 2009， 12 （9） 108-110. [8] 王旸， 刘晓东， 徐小慧， 等.基于粒子群优化的数据分类算法[J]. 系统仿真学报， 2008， 20 （22） 6158-6162. [9] 王晓敏， 刘希玉， 戴芬.基于PSO的关联规则挖掘方法及应用[J]. 信息技术与信息化， 2009 （3） 85-87. [10] 徐刚， 杨玉群， 黄先玖.一种非线性权重的自适应粒子群优化 算法[J].计算机工程与应用， 2010， 46 （35） 49-51. [11] Chatterjeea A， Siarry P.Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J]. Computers and Operations Research， 2006， 34 （4） 859-871. [12] 王润芳， 张耀军， 裴志松.新型的动态粒子群优化算法[J].计算 机工程与应用， 2011， 47 （16） 32-34. [13] 田野.粒子群优化算法及其应用研究[D].长春 吉林大学， 2010. [14] Shi Y， Eberhart R C.A modified particle swarm optimizer[C]// Proceedings of the IEEE International Conference on Evo- lutionary Computation.Piscataway NJ IEEE Service Center， 1998 69-73. [15] 胡建秀， 曾建潮.微粒群算法中惯性权重的调整策略[J].计算 机工程， 2007， 33 （11） 193-195. 算法 CW-PSO LDW SL-PSO 最优适应值 5.659 8 4.891 5 5.412 5 平均适应值 5.597 6 4.905 4 5.244 7 适应值方差 0.010 9 0.118 2 0.057 1 表2算法的测试性能仿真 （Tmax300） 算法 CW-PSO LDW SL-PSO 最优适应值 5.415 7 4.624 8 5.059 8 平均适应值 5.343 5 4.107 7 5.001 3 适应值方差 0.014 2 0.137 6 0.075 4 表3算法的测试性能仿真 （Tmax200） 2468101214161820 6 5 4 3 2 1 0 传感器数量 适应度值 图1适应度函数值随传感器数量变化曲线图 50100150200250300 6 5 4 3 2 1 0 迭代次数 平均适应度值 LDW SL-PSO CW-PSO 图2三种算法的适应度迭代曲线图 270