没有合适的资源?快使用搜索试试~ 我知道了~
1. [Machine Learning] 深度学习中消失 2. [Machine Learning] logistic函数和s 3. [Machine Lea
资源详情
资源评论
资源推荐
2017/6/30 [Algorithm] 群体智能优化算法之粒子群优化算法 - Poll的笔记 - 博客园
http://www.cnblogs.com/maybe2030/p/5043356.html#top 1/11
Poll的笔记
昵称:Poll的笔记
园龄:2年
粉丝:506
关注:14
+加关注
< 2017年6月 >
日 一 二 三 四 五 六
28 29 30 31 1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 1
2 3 4 5 6 7 8
最新随笔
1. [Machine Learning] 深度学习中消失
的梯度
2. [Machine Learning] logistic函数和s
oftmax函数
3. [Machine Learning & Algorithm] 神
经网络基础
4. [Machine Learning] Active Learnin
g
5. [Machine Learning & Algorithm]CA
ML机器学习系列2:深入浅出ML之Ent
ropy-Based家族
6. [Machine Learning & Algorithm]CA
ML机器学习系列1:深入浅出ML之Reg
ression家族
7. [Data Structure] LCSs——最长公
共子序列和最长公共子串
8. [Algorithm & NLP] 文本深度表示模
型——word2vec&doc2vec词向量模型
9. [Algorithm] 机器学习算法常用指标
总结
10. [Linux] Linux常用文本操作命令整
理
- [三叶草精神] what hurts more,the
pain of hard work or the pain of
regret?
首页 联系
管理 博客园
随笔 - 63 文章 - 1 评论 - 257
阅读目录
1. 常见的群体智能优化算法分类
2. 粒子群优化算法思想
3. 粒子群优化算法的基本框架
4. 对粒子群优化算法中惯性权重的认识
5. 粒子群优化算法举例——求解旅行商问题
6. 参考文献
同进化算法(见博客《[Evolutionary Algorithm] 进化算法简介》,进
化算法是受生物进化机制启发而产生的一系列算法)和人工神经网络算法
(Neural Networks,简称NN,神经网络是从信息处理角度对人脑的神经
元网络系统进行了模拟的相关算法)一样,群体智能优化算法也属于一种生
物启发式方法,它们三者可以称为是人工智能领域的三驾马车(PS:实际上
除了上述三种算法还有一些智能算法应用也很广泛,比如模拟金属物质热力
学退火过程的模拟退火算法(Simulated Algorithm,简称SA),模拟人体
免疫系统在抗原刺激下产生抗体过程的人工免疫系统算法(Artificial
Immune System,简称AIS)等,但是相对三者而言,模拟退火和人工免
疫系统算法已逐渐处于低潮期)。群体智能优化算法主要模拟了昆虫、兽
群、鸟群和鱼群的群集行为,这些群体按照一种合作的方式寻找食物,群体
中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的
方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜
索,从而在解空间内找到最优解。
回到顶部
1. 常见的群体智能优化算法分类
常见的群体智能优化算法主要有如下几类:
(1)蚁群算法(Ant Colony Optimization,简称ACO)[1992年提
出];
(2)粒子群优化算法(Particle Swarm Optimization,简称PSO)
[Algorithm] 群体智能优化算法之粒子群优化算法
11 0
2017/6/30 [Algorithm] 群体智能优化算法之粒子群优化算法 - Poll的笔记 - 博客园
http://www.cnblogs.com/maybe2030/p/5043356.html#top 2/11
随笔分类
Algorithm(23)
Bash(1)
C/C++(6)
Computational Advertising(1)
Data Structure(6)
Database(3)
Evolutionary Algorithm(2)
Hadoop(4)
Linux(6)
Machine Learning(15)
Math(2)
Network(2)
Operate System
Python(11)
Recommendation System(1)
Search Engine(3)
Social Network Analysis(1)
Web Development(2)
生活杂谈(1)
随笔档案
2017年1月 (1)
2016年7月 (1)
2016年6月 (1)
2016年5月 (4)
2016年4月 (2)
2016年3月 (2)
2016年2月 (2)
2016年1月 (1)
2015年12月 (5)
2015年11月 (3)
2015年10月 (1)
2015年9月 (5)
2015年8月 (8)
2015年7月 (8)
2015年6月 (19)
My Team
OMEGA team
(2)粒子群优化算法(Particle Swarm Optimization,简称PSO)
[1995年提出](简单易于实现,也是目前应用最为广泛的群体智能优化算
法);
(3)菌群优化算法(Bacterial Foraging Optimization,简称BFO)
[2002年提出];
(4)蛙跳算法(Shuffled Frog Leading Algorithm,简称SFLA)
[2003年提出];
(5)人工蜂群算法(Artificial Bee Colony Algorithm,简称ABC)
[2005年提出];
除了上述几种常见的群体智能算法以外,还有一些并不是广泛应用的群
体智能算法,比如萤火虫算法、布谷鸟算法、蝙蝠算法以及磷虾群算法等
等。
回到顶部
2. 粒子群优化算法思想
由于博主对粒子群优化算法比较熟悉,在硕士期间也进行了比较系统的
学习,所以利用本博文系统的介绍一下应用最为广泛的PSO算法。
粒子群优化算法是在1995年由Eberhart博士和Kennedy博士一起提出
的,它源于对鸟群捕食行为的研究。它的基本核心是利用群体中的个体对信
息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演
化过程,从而获得问题的最优解。我们可以利用一个有关PSO的经典描述来
对PSO算法进行一个直观的描述。设想这么一个场景:一群鸟进行觅食,而
远处有一片玉米地,所有的鸟都不知道玉米地到底在哪里,但是它们知道自
己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略,也是最简单
有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。PSO就是从
这种群体觅食的行为中得到了启示,从而构建的一种优化模型。
在PSO中,每个优化问题的解都是搜索空间中的一只鸟,称之为“粒
子”,而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一
个位置向量(粒子在解空间的位置)和速度向量(决定下次飞行的方向和速
度),并可以根据目标函数来计算当前的所在位置的适应值(fitness
value),可以将其理解为距离“玉米地”的距离。在每次的迭代中,种群中的
粒子除了根据自身的“经验”(历史位置)进行学习以外,还可以根据种群中
最优粒子的“经验”来学习,从而确定下一次迭代时需要如何调整和改变飞行
的方向和速度。就这样逐步迭代,最终整个种群的粒子就会逐步趋于最优
解。
回到顶部
3. 粒子群优化算法的基本框架
在介绍PSO的算法流程之前,我们写给出PSO中常用的迭代算子的形
式。令 代表粒子 的位置向量,
代表粒子 的速度向量(其中 为优化问题的维度
大小),最早版本的粒子群优化算法的迭代算子形式如下:
速度向量迭代公式:
(1)
位置向量迭代公式:
(2)
其中在公式(1)中, 和 分别代表粒子 的历史最佳位置向量
和种群历史最佳位置向量。根据公式(1)(2)可以看出,种群中的粒子通
过不断地向自身和种群的历史信息进行学习,从而可以找出问题的最优解。
但是,在后续的研究中表明,上述原始的公式中存在一个问题:公式
(1)中 的更新太具有随机性,从而使得整个PSO算法的全局优化能力很
强,但是局部搜索能力较差。而实际上,我们需要在算法迭代初期PSO有着
= ( , , ..., )
X
i
x
i
1
x
i
2
x
in
i
= ( , ,.. ., )
V
i
v
i
1
v
i
2
v
in
i
n
= + (
Pbes
− ) + (
Gbest
− )
V
i
V
i
c
1
r
1
t
i
X
i
c
2
r
2
X
i
= +
X
i
X
i
V
i
Pbes
t
i
Gbest
i
V
i
11 0
2017/6/30 [Algorithm] 群体智能优化算法之粒子群优化算法 - Poll的笔记 - 博客园
http://www.cnblogs.com/maybe2030/p/5043356.html#top 3/11
常用链接
[Andrew Moore] Statistical Data Min
ing Tutorials
[Online Terminals] tutorialspoint
ACM之家
机器学习周报
开源中国
漫谈机器学习算法
鸟哥的Linux私房菜
统计之都
推酷
我爱公开课
我爱机器学习
我爱自然语言处理
推荐博友
CAML
计算广告与机器学习-技术共享平台
Dustinsea
百度关键词搜索推荐系统maker
JasonDing
机器学习、算法、Spark
July的博客
结构之法,算法之道。
uc技术博客
UC企业技术博客
Vamei
文艺地讲解编程、数学和设计
阿哈磊
图文并茂的阿哈磊算法讲解,简单易懂
董的博客
关注大规模数据处理
寒江独钓
详细的数据结构和算法讲解
火光摇曳
机器学习、分布式计算、计算广告学
静觅
python爬虫系列教程
静逸
专注于wed前端
酷壳
程序员必看,涉及面很广,也很有深度
牛吧大数据
大数据、机器学习、R语言
强,但是局部搜索能力较差。而实际上,我们需要在算法迭代初期PSO有着
较强的全局优化能力,而在算法的后期,整个种群应该具有更强的局部搜索
能力。所以根据上述的弊端,Shi和Eberhart通过引入惯性权重修改了公式
(1),从而提出了PSO的惯性权重模型:
速度向量迭代公式:
(3)
其中参数 称为是PSO的惯性权重(inertia weight),它的取值介于[0,1]
区间,一般应用中均采取自适应的取值方法,即一开始令 ,使得
PSO全局优化能力较强,随着迭代的深入,参数 进行递减,从而使得PSO
具有较强的局部优化能力,当迭代结束时, 。参数 和 称为是
学习因子(learn factor),一般设置为1.4961;而 和 为介于[0,1]之间
的随机概率值。
整个粒子群优化算法的算法框架如下:
Step 1种群初始化:可以进行随机初始化或者根据被优化的问题设计
特定的初始化方法,然后计算个体的适应值,从而选择出个体的局部最优位
置向量 和种群的全局最优位置向量 。
Step 2迭代设置:设置迭代次数 ,并令当前迭代次数 ;
Step 3速度更新:根据公式(3)更新每个个体的速度向量;
Step 4位置更新:根据公式(2)更新每个个体的位置向量;
Step 5局部位置向量和全局位置向量更新:更新每个个体的 和
种群的 ;
Step 6终止条件判断:判断迭代次数时都达到 ,如果满足,输出
;否则继续进行迭代,跳转至Step 3。
对于粒子群优化算法的运用,主要是对速度和位置向量迭代算子的设
计。迭代算子是否有效将决定整个PSO算法性能的优劣,所以如何设计PSO
的迭代算子是PSO算法应用的研究重点和难点。
回到顶部
4. 对粒子群优化算法中惯性权重的认识
参数 被称之为是惯性权重,顾名思义 实际反映了粒子过去的运动状
态对当前行为的影响,就像是我们物理中提到的惯性。如果 ,从前
的运动状态很少能影响当前的行为,粒子的速度会很快的改变;相反, 较
大,虽然会有很大的搜索空间,但是粒子很难改变其运动方向,很难向较优
位置收敛,由于算法速度的因素,在实际运用中很少这样设置。也就是说,
较高的 设置促进全局搜索,较低的 设置促进快速的局部搜索。
回到顶部
5. 粒子群优化算法举例——求解旅行商问题
旅行商问题(Traveling Salesman Problem,TSP)又译为旅行推销员
问题、货郎担问题,简称为TSP问题,是最基本的路线问题和最典型的NP难
问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之
后,最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由
Dantzig等人于1959年提出的。
下面为一个TSP问题的数据集,城市个数为50:
1 37 52
2 49 49
3 52 64
4 20 26
5 40 30
=
w
+ (
Pbes
− ) + (
Gbest
− )
V
i
V
i
c
1
r
1
t
i
X
i
c
2
r
2
X
i
w
w
= 0.9
w
w
= 0.1
c
1
c
2
r
1
r
2
Pbes
t
i
Gbest
g
max
g
= 1
Pbes
t
i
Gbest
g
max
Gbest
w w
w
<< 1
w
w w
11 0
剩余10页未读,继续阅读
大头蚊香蛙
- 粉丝: 16
- 资源: 317
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0