粒子群算法解决函数优化问题
粒子群算法解决函数优化问题 1 1、群智能算法研究背景 粒子群优化算法(Particle Swarm Optimization, PSO是由Kennedy和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995年提出的一种群智能算法,其思想 来源于人 工生命和演化计算理论,模仿鸟群飞行觅食行为,通过鸟集体协作使群 体达到优。 PSO算法作为一种新的群智能算法,可用于解决大量非线性、不可微和多峰 值的复 杂函数优化问题,并已广泛应用于科学和工程领域,如函数优化、神经网 络训练、经济调 度、模式识别与分类、结构设计、电磁场和任务调度等工程优化 问题等。 PSO算法从提出到进一步发展,仅仅经历了十几年的时间,算法的理论基础 还很薄 弱,自身也存在着收敛速度慢和早熟的缺陷。 如何加快粒子群算法的收敛 速度和避免出 现早熟收敛,一直是大多数研究者关注的重点。 因此,对粒子群算 法的分析改进不仅具 有理论意义,而且具有一定的实际应用价值。 2 2、国内外研究现状 对PSO算法中惯性权重的改进:Poli等人在速度更新公式中引入惯性权重来 更好的 控制收敛和探索,形成了当前的标准PSO算法。 研究人员进行了大量的研究工作,先后提出了线性递减权值(LDIW)策略、 模糊惯性权值(FIW)策略和随机惯性权值(RIW)策略。其中,FIW策略需要专家 知识建立 模糊规则,实现难度较大,RIW策略被用于求解动态系统,LDIW策略 相对简单且收敛速 度快, 任子晖,王坚于2009年,又提出了基于聚焦距离变化率的自适应惯性权重 PSO算法。 郑春颖和郑全弟等人,提出了基于试探的变步长自适应粒子群算法。 进的PSO算法既保持了搜索速度快的特点,又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析:1999年采用代数方法对几种典型PSO算法的 运行轨迹进行了分析,给出了保证收敛的参数选择范围。在收敛性方面 这些改 Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则,证明了标准PSO 算法不能收敛于全局优解,甚至于局部优解;证明了保证收敛的PSO算法能 够收敛于局 部优解,而不能保证收敛于全局优解。 国内的学者:2006年,刘洪波和王秀坤等人对粒子群优化算法的收敛性进 行分析, 指出它在满足收敛性的前提下种群多样性趋于减小, 低而失去继续搜索可行解的能力,提出混沌粒子群优化算法。 粒子将会因速度降 2008年,黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所 带来的影响,对粒子群算法进行了改进。2009年,高浩和冷文浩等人,分析了 速度因子 对微粒群算法影响,提出了一种基于 算法。并证明了它能以概率1收敛到全局优解。 Gaussian变异全局收敛的粒子群 2010年,为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论, 对惯性 权重粒子群模型的收敛性进行了分析,提出了使得在算法模型群模型收敛 条件下的惯性权重和加速系数的参数约束关系,使算法在收敛性方面具有显著优 越性。在 PSO算法中嵌入别的算法的思想和技术。 1997年,李兵和蒋慰孙提出混沌优化方法; 1998年,An gel ine在PSO算法中引入遗传算法中的选择算子,该算法虽然 加快 了算法的收敛速度,但同时也使算法陷入局部优的概率大增, 特别是在优化Griewa nk 基准函数的优值时得到的结果不理想; 2004年,高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中,首先对 当前群体 中的优粒子进行混沌寻优,再用混沌寻优的结果随机替换群体中的一 个粒子,这样提出另 一种混沌粒子群优化算法。 2005年,YuLiu和ZhengQin提出了中心粒子群算法; 2010年,提出基于区域收缩搜索的混合粒子群算法。和别的智能算法的融 合。 国外学者:1998年,Angeline提出了结合遗传算法中选择算子的PSO算法, 主要 应用粒子群算法的基本机制以及自然选择机制所采用的演化计算方法,使PSO的局部搜 索能力得到了提高,但同时削弱了全局搜索能力; 2001年,Lovbierg等人,将繁殖和子群组的概念引入PSO算法中,防止了 基于适应值的选择对那些多局部极值函数带来的潜在问题; 2003年,Zhang和Xie在PSO中加入差分进化算子,Higasb、Iba和Stacey 等人试图在PSO中加入变异算子,同年,Hendtlass提出了一个研究,即扩大粒 子有记 忆的地方,它是通过对比蚁群算法信息素在路径上的分布情况得出的。 3 3、PSOPSO 算法介绍 N 匹配领 域个体速 避免与领 进个体冲撞 3飞向鸟 群中心 度 基本思想:通过群体中个体之间的协作和信息共享来寻找最优解 优点:概念简单、容易实现、搜索速度快和搜索范围大 缺点:易陷入局部极小 基本粒子群算法流程: 1.初始化粒子群,随机初始化粒子(D维上的位置和速度) 2.根据适应度函数计算各粒子的适应度值 3.对每个粒子,将其与本身历史最好位置比较,若较好,则将其替换为当前 最好位 置 4.对每个粒子,将其与全局最好位置比较,若较好,则将其替换为全局最好 位置 5.根据公式(1)更新粒子的速度和位置 6.若未达到约束条件,则返回步骤2 vj = wVjd +c1 rand 1 ( pbest^ - x^ ) c2rand ; (gbest: -xid) 公式(1) 流程图 1+ 开始 计算各粒子目标函数,找出计算各粒子目标函数,找出 当前个体的概值和全局极值当前个体的概值和全局极值 计算更新的速度和更新的位置 输出最优解 4 4、算法改进 原始的PSO算法易陷入局部最优解,而采用增加扰动的方法可以消除此现 象。当粒 子群体最有位置有一定代数没有进化时,选其中的粒子 优值一样),用当前的粒子对其进行更新操作 (位置和全局最 PSO算法中的w是惯性权重,使粒子保持空间的运动惯性,其有扩展全局搜 索的趋势,有能力搜索新的区域 目前常用的有固定权值、线性递减权值等方法,固定权值不利于迭代最后阶 段的收 敛,线性递减权值方法需要用小步长才能出现较好的收敛效果。 采用随机权重方法,每次使w随机分布在0.4-0.6之间,实践证明,要优于 线性递 减的算法。 5 5、实验结果及分析 SphereSphere 函数: f (x )= Error PSO IPSO RPSO Average 3936 2783 530 Max_Exc 2657 2109 407 7% 0 0 n RastrigrinRastrigrin 函数:f(X)八 (X: - 10COS 二(2二Xi) 10) i =1 广义 SuccessAversge_TMin_T PSO IPSO RPSO 3% 40% 86% 8033 9195 4971 5664 4971 981 GriewankGriewank 函数:f (x) 2 4000 i =1 X i丨丨 cos( Fail_pro PSO IPSO RPSO Sta nd_proAverage 0 4% 54% 0.725 0.443 0.162 2% 0 0 程序运行截图 6、总结与期望 标准PSO算法具有收敛速度快,但易陷入局部最优,因此我们