智能算法---粒子群算法
智能算法—粒子群算法
1 粒子群算法是一种群智能算法，那么什么是群智能？ 群智能由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略。生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。这些个体有两个特点（1）个体行为受到群体行为的影响，趋利避害。就是说个体之间是存在信息交流的；（2）群体有着很强的生存能力，但是这种能力不是单纯个体行为的叠加。
2 群智能的基本原则：
- 邻近原则（Proximity Principle）：群体能够进行简单的空间和时间计算
- 质量原则（Quality Principle）：群体不仅能够对时间和空间因素作出反应，而且能够响应环境中的质量因子（如事物的质量或位置的安全性）
- 多样性反应原则（Principle of Diverse Response）：群体不应将自己获取资源的途径限制在过分狭窄的范围内
- 稳定性原则（Stability Principle）：即群体不应随着环境的每一次变化而改变自己的行为模式
- 适应性原则（Adaptability Principle）：当改变行为模式带来的回报与能量投资相比是值得的时，群体应该改变其行为模式
3 群智能的特点
- 控制是分布式的，不存在中心控制
- 群体中的每个个体都能够改变环境，这是个体之间间接通信的一种方式，这种方式被称为“激发工作”（Stigmergy）
- 群体中每个个体的能力或遵循的行为规则非常简单，因而群智能的实现比较方便，具有简单性的特点
- 群体表现出来的复杂行为是通过简单个体的交互过程突现出来的智能（Emergent Intelligence），因此，群体具有自组织性
典型的群智能算法有粒子群优化算法（PSO）；蚁群算法(ACO）；鱼群算法
下面我们来详细介绍粒子群优化算法，并结合具体的实例来说明。
1 什么是粒子群优化算法
该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。
2 PSO算法的基本思想
- 每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。
- 所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
- PSO初始化为一群随机粒子，然后通过迭代找到最优解。
PSO模型分为全局PSO模型和局部的PSO模型，全局PSO模型是局部PSO模型的一种特殊的方式。
3 全局PSO模型。
3.1 基本原理和数据抽象表示如下
每个粒子给定一个初始的位置，粒子历史最佳位置就是粒子到最优点向量。全局最佳位置，就是对整个粒子群而言，有一个最佳的粒子指向最佳点的方向就是全局最佳的位置。此外粒子还有一个飞行的速度，这个速度促进每个粒子朝着最佳前进，没有速度，粒子就无法收敛。
3.2那么有关的数据之间的关系如下
速度由三个部分组成，（1）粒子本身有的动能，w为事先定义的参数。（2）粒子自我认知学习部分。是指粒子现在所在的位置指向最佳粒子的向量。自我认知部分包含随机函数是为了保证随机性，不然确定的数据很快就能达到收敛。（3）粒子社会认知部分。粒子群最佳位置减去现在所在的位置的向量。这三种共同定义速度
位置由现在位置加上一个时间间隔内粒子走的距离，注意速度存在约束条件。
结果更新，根据条件选择最优解。
3.3 PSO算法的流程图
3.4全局PSO举例
到达最佳位置，得到最优解
4 局部PSO模型
4.1数据的抽象表示
注意和全局PSO模型，粒子群的最佳位置改成了邻居最佳位置，这样局部PSO就可以形成多个比较好的解。在后面速度的更新公式也只是第三部分改成邻居最佳位置减去现有的位置向量。其他都不变。
4.2 流程图
4.3常见的局部PSO的邻居拓扑结构
全互连的形式就是上面所说的全局PSO模型；幻想结构就是相邻的节点收敛，是一种典型的局部邻居拓扑结构，收敛速度比较慢。二冯诺依曼结构中，每个节点都有四个和其相邻的点，因此收敛速度比全互连慢，比环形结构快。
5 全局和局部PSO算法实例比较
5.1 优化问题
分单模和多模。如上左图所示，单模整体而言就只有一个最优解，对应于全局的PSO问题。二右上图所示，多模问题中存在多个极值点，对应于局部的PSO算法。
比较结果如下
在相同的实验环境下，由上左图可以知道局部的PSO算法收敛速度比较快。但是局部PSO如果得到结果，就如上右图所示，虽然开始的时候局部PSO算法的收敛速度比较快，但是如果得到收敛结果了，结果就不会再变化了。
6 二进制粒子群优化算法(BPSO）
上面提到的粒子群优化算法适合连续型的粒子群优化问题求解。但是不能用于离散型的数据。
7 求解集合组合问题的离散粒子群优化模型(SDPSO)
7.1 SDPSO是一种适合集合关系的最优化问题求解的模型。
速度和位置的及算法是如下
7.2 SDPSO算法流程如下
8 PSO实例应用求解
下面采用PSO方法解决背包问题
8.1 问题描述
8.2 评价方式
- 背包问题的评价函数 ：采用贪心算法思想
- 在评价解时，首先按pi/ωi的降序对解中放入背包的物品进行排序；
- 优先计算pi/ωi大的物品的价值，直到满足最大容量的限度；
- 所形成的新解及该解的总价值为评价结果。
8.3 求解过程
测试实例：有两个测试实例
比较算法：二进制PSO（BPSO）和SDPSO
参数设置：粒子数 N＝20、最大循环次数100、算法测试50遍。BPSO参数设置：参数c1=c2=2。BPSO中Vmax=6
9 PSO的优缺点
PSO的优点
- 强的通用性，不依赖于问题信息；
- 群体搜索，具有记忆能力；
- 原理简单，容易实现；
- 协同搜索，同时利用个体信息和群体信息指导搜索。
PSO的缺点
- 局部搜索能力较差，搜索精度不够高；
- 易陷入局部最优；
- 搜索性能对参数具有一定的依赖性；
- 算法理论不完善。
版权声明：本文为tao-alex原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。