当前位置:首页 >> 电力/水利 >>

粒子群算法实例


粒子群算法解决函数优化问题

学院:信息科学与工程学院

目 录

引言............................................................................................................................

.... 1 一、问题描述................................................................................................................ 2 1.1 连续函数求最优值问题................................................................................. 2 1.2 粒子群算法..................................................................................................... 2 二、算法设计................................................................................................................ 3
2.1 流程框图............................................................................................................................3 2.2 算法实现............................................................................................................................3 2.3 参数选择............................................................................................................................4

三、程序设计................................................................................................................ 5 3.1 编写程序......................................................................................................... 5 四、 结果与分析.......................................................................................................... 6 4.1 实验结果:..................................................................................................... 6 4.2 分析:............................................................................................................. 7 五、 总结...................................................................................................................... 7

引言 本文主要利用粒子群算法解决连续函数的最小值问题, 粒子群优化是一种新 兴的基于群体智能的启发式全局 搜索算法, 粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间 中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点,倍受科学 与工程领域的广泛关注, 已经成为发展最快的智能优化算法之一。本文介绍了粒 子群优化算法的基本原理,分析了其特点,并将其应用于函数优化问题求解。 求函数最优值问题,对此问题,传统的优化技术很容易陷入局部最优解,求 得全局优化解的概率不高,可靠性低;为此,建立尽可能大概率的求解全局优化 解算法是求解函数优化的一个重要问题。本文采用粒子群算法来解决这类问题。

1

一、问题描述 1.1 连续函数求最大值问题 本文主要选取一个三维函数,利用matlab编写粒子群算法程序来求解它们 以验证遗传算法在解决函数优化问题中的有效性。本文选取的函数为: f=x(1).^2+x(2).^2+x(3).^2,求它的最小值。 1.2 粒子群算法 PSO 从这种模型中得到启示并用于解决优化问题。PSO 中,每个优化问题 的潜在解都是搜索空间中的一只鸟,称之为粒子。所有的粒子都有一个由被优化 的函数决定的适值( fitness value) ,每个粒子还有一个速度决定它们飞翔的方向 和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次 迭代中, 粒子通过跟踪两个极值来更新自己;第一个就是粒子本身所找到的最优 解,这个解称为个体极值;另一个极值是整个种群目前找到的最优解,这个极值 是全局极值。 另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那 么在所有邻居中的极值就是局部极值。 假设在一个 D 维的目标搜索空间中,有 N 个粒子组成一个群落,其中第 i 个 粒子表示为一个 D 维的向量
X
i

? ( x i 1 , x i 2 , ? , x iD )

,i

? 1, 2 , ? , N



第 i 个粒子的“飞行 ”速度也是一个 D 维的向量,记为
V i ? v i 1 , v i 2 , , v iD ) ( ?

,i

? 1, 2 , ? 3



第 i 个粒子迄今为止搜索到的最优位置称为个体极值,记为
p best ? ( p i 1 , p i 2 , ? , p iD )

,i

? 1, 2 , ? , N



整个粒子群迄今为止搜索到的最优位置为全局极值,记为
g best ? ( p g 1 , p g 2 , ? , p gD )

在找到这两个最优值时, 粒子根据如下的公式(1.1)和( 1.2)来更新自己的速度和位 置:
v id ? w ? v id ? c 1 r1 ? p id ? x id ? ? c 2 r2 ( p gd ? x id )
2

(1.1)

x id ? x id ? v id

(1. 2)

其中:c 1 和 c 2 为学习因子, 也称加速常数(acceleration constant),r1 和 r2 为[0, 1]范围内的均匀随机数。式(1.1)右边由三部分组成,第一部分为“惯性(inertia)” 或“动量(momentum)”部分,反映了粒子的运动“习惯(habit)”,代表粒子有维持自 己先前速度的趋势;第二部分为“认知(cognition)”部分,反映了粒子对自身历史 经验的记忆(memory)或回忆(remembrance), 代表粒子有向自身历史最佳位置逼近 的趋势;第三部分为“社会(social)”部分,反映了粒子间协同合作与知识共享的群 体历史经验。 二、算法设计 这部分内容主要是针对本文主要研究问题的类型确定粒子群算法具体实现 过程和一些参数的选择。 2.1 算法流程框图

图 1 粒子群算法流程图 2.2 算法实现 算法的流程如下: ① 初始化粒子群,包括群体规模 N ,每个粒子的位置 x i 和速度 V i

3

② 计算每个粒子的适应度值 F it [i ] ;
( ③ 对每个粒子,用它的适应度值 F it [i ] 和个体极值 p best i )比较,如果
F it [ i ] ? p best ( i )

( ,则用 Fit [i ] 替换掉 p best i );
Fit [i ]

④ 对每个粒子,用它的适应度值
F it [ i ] ? p b e s t( i ) 则用 F it [i ] 替 g best

和全局极值

g b e s t比 较 , 如 果



⑤ 根据公式(1.1),(1.2)更新粒子的速度 v i 和位置 x i ; ⑥ 如果满足结束条件(误差足够好或到达最大循环次数)退出,否则返回②。 2.3 参数选择 本算法中主要的参数变量为 w (惯性权值) c 1 , c 2 (加速因子) , ,N (种 群数) ,M (迭代次数) ,D (粒子维数) 。 (1)种群规模 通常,种群太小则不能提供足够的采样点,以致算法性能很差;种群太大尽 管可以增加优化信息,阻止早熟收敛的发生,但无疑会增加计算量,造成收敛时 间太长,表现为收敛速度缓慢。种群规模一般设为100~1000。本文选择种群规模 为100。 (2)最大迭代次数 迭代次数越多能保证解的收敛性,但是影响运算速度,本文选1000次。 (3)惯性权值 惯性权重 w 表示在多大程度上保留原来的速度。 w 较大,全局收敛能力强, 局部收敛能力弱; w 较小,局部收敛能力强,全局收敛能力弱。本文选0.6。 (4)加速因子 加速常数 c 2 和 c 2 分别用于控制粒子指向自身或邻域最佳位置的运动。文献 [20]建议 ?
? c1 ? c 2 ? 4 .0

,并通常取 c 1

? c2 ? 2

。本文也取 c 1

? c2 ? 2



(5)粒子维数 本文中粒子维数取决于待优化函数的维数,例如本文取3。 需要说明的是,本文的程序允许改变这些参数,因为本文编写的程序参照 matlab工具箱,留给用户解决这类问题一个接口函数,上述的各个参数正是接口
4

函数的参数,因此允许改变。另外对于 w 和c也可采用变参数法,即随迭代次数 增加,利用经验公式使它们动态调整,本文采用固定值。 三、程序设计 3.1 编写程序 程序主要有两个m文件组成,pso.m是遗传算法接口文件,fitness.m是待求解 的问题函数,只需要修改fitness.m里的目标函数就可实现不同问题的解。 (1)pso.m文件 function [xm,fv] = PSO(fitness,N,c1,c2,w,M,D) %fitness-是要优化的目标函数,N-种群数,c1,c2-学习因子,w-惯性权重, M-迭代次数,D-粒子维数。 format long; %初始化种群 for i=1:N for j=1:D x(i,j)=randn; v(i,j)=randn; end end %先计算各个粒子的适应度,并初始化pi-粒子个体极值和pg-全局极值 for i=1:N p(i)=fitness(x(i,:)); y(i,:)=x(i,:); end pg = x(N,:); for i=1:(N-1) if fitness(x(i,:))<fitness(pg) pg=x(i,:); end end %pg为全局极值 %随机初始化位子 %随机初始化速度

5

%进入粒子群算法主要循环 for t=1:M for i=1:N v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)); x(i,:)=x(i,:)+v(i,:); if fitness(x(i,:))<p(i) p(i)=fitness(x(i,:)); y(i,:)=x(i,:); end if p(i)<fitness(pg) pg=y(i,:); end end Pbest(t)=fitness(pg); end xm = pg'; fv = fitness(pg); (2)目标函数fitness.m文件 function f=fitness(x) f=x(1).^2+x(2).^2+x(3).^2 ; end 需要说明的是,针对不同的函数优化,只需要改变目标函数就可以。 (3)在命令行输入或建立调用m文件 在命令行先后输入[xm,fv] = PSO(@fitness,100,2,2,0.6,1000,3),或建立包涵 该语句的m文件,运行即可得到结果。 四、 结果与分析 4.1 实验结果 (1)对于目标函数f=x(1).^2+x(2).^2+x(3).^2 优化结果如下: xm =1.0e-162 *
6

0.556163077454623 0.937292023592359 0.146573921409127 fv =0 , fv是最优值,xm为最优值对应的自变量值。 4.2 分析 通过对实验结果和已知最小值比较可知,该算法能有效解决这类问题,需要 特别指出的是xm的取值只是近似值,另外,本文的粒子群算法程序只是实现粒 子群算法的基本功能,该算法还有待进一步改进。 五、总结 本文利用粒子群算法思想,通过编写 matlab 程序,对一个三维连续函数进 行优化得到了较好的仿真结果, 证明粒子群算法在解决这类问题的可行性。 另外, 在编写本文的工作过程中, 提高了自己对粒子群算法的理解和应用能力。为今后 利用智能算法撰写论文或进行科学研究打下了很好地基础。

7


相关文章:
粒子群算法实例
7 引言 本文主要利用粒子群算法解决连续函数的最小值问题, 粒子群优化是一种新 兴的基于群体智能的启发式全局 搜索算法, 粒子群优化算法通过粒子间的竞争和协作以...
一个很好的学习粒子群算法的例子
一个很好的学习粒子群算法例子_数学_自然科学_专业资料。目标优化函数程序中已经内定了,f6 ={0.5-[sin(sqrt(x2+y2)2-0.5]}/(1+0.001*(x2+y2))...
matlab粒子群优化算法举例分析
1.2 。 a)%主函数源程序(main.m) %---基本粒子群算法 (particle swarm optimization) %---名称: 基本粒子群算法 %---初始格式化 clear all; %清除所有变...
粒子群算法学习报告
(4) 机器人控制 在机器人控制中, 粒子群算法被用于机器人震动抑制轨迹规划以及动态规 划问题。 三 粒子群算法 Matlab 实例例子为计算一个 40 个十维的粒子...
粒子群算法matlab代码 吐血推荐
粒子群算法(1)---粒子群算法简介二、粒子群算法的具体表述 上面罗嗦了半天,那些...7,8;...,以此类推,一直到邻域为 4,这 个时候,邻域扩展到整个例子群体。据...
用MATLAB编写PSO算法及实例
用MATLAB编写PSO算法及实例_计算机软件及应用_IT/计算机_专业资料。pso粒子群算法 高斯函数, 用MATLAB 编写 PSO 算法及实例 1.1 粒子群算法 PSO 从这种模型中...
粒子群算法解最短路径
本文最后用实例验证了算法确实在执行了若干次迭代 后收敛。程序的编程环境为Microsoft Visual Studio 2008,编程语言为C#。 关键词: 粒子群算法 最短路径 约束优化 ...
粒子群算法详解matlab代码
粒子群算法详解matlab代码_计算机软件及应用_IT/计算机_专业资料。粒子群算法(1)---粒子群算法简介一、粒子群算法的历史 粒子群算法源于复杂适应系统(Complex Adaptiv...
基本粒子群算法的原理和matlab程序
基本粒子群算法的原理和matlab程序_计算机软件及应用_IT/计算机_专业资料。自己整理的粒子群算法的方法,并且将现有的程序整理简化后上传,比较有参考价值。基本...
粒子群算法原理及在函数优化中的应用(附程序)
(Author:xiao5) 2012-5-5 下面以测试函数ackley为例,给出基本粒子群算法的程序实现代码: A、 主程序(可运行的程序) drawPSO.m: %基于PSO算法的函数寻优收敛...
更多相关标签:
粒子群算法 | 粒子群优化算法实例 | 粒子群算法matlab程序 | 粒子群算法及应用 | 粒子群算法matlab实例 | 粒子群优化算法 | 粒子群算法应用实例 | 粒子群算法流程图 |