群智能学习笔记

群智能

【复习所用笔记，内容来自老师的PPT】

定义概述

群，已知有蚁群、鱼群、鸟群。它们是互相影响的个体，行为简单。没有一个集中控制中心。作为群体协作工作时，能够突显出非常复杂的行为特征——智能行为，群体智能。

任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布
式解决问题的策略均属于群智能。

群智能（Swarm Intelligence）已经成为有别于传统人工智能中符号主义和链接主义的一种新的关于人工智能的研究路线。示例：有蚁群算法、粒子群算法等。

群智能为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已取得成功的基于SI的优化算法有蚁群算法、粒子群算法、鱼群算法、猴群算法等。

目前，已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法，更重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析,群智能理论及应用研究都是具有重要学术意义和现实价值的。

 无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。
 基于分散的群体行为的自组织系统，通过一定数量的简单个体之间以及和环境之间的相互交互从而实现群体表现一定的智能行为。
这里关心的不是个体之间的竞争，而是它们之间的协同（获取并共享信息）

SI与GA

目前，已有的基于SI的优化算法都是源于对动物社会通过协作解决问题行为的模拟，它主要强调对社会系统中个体之间相互协同作用的模拟。这一点与遗传算法 Genetic Algorithms- -GA不同，GA是对生物演化中适者生存的模拟。与GA一样的是，SI的目的并不是为了忠实地模拟自然现象，而是利用它们的某些特点去解决实际问题。另一个与GA的相同点是,基于SI的优化算法也是概率搜索算法。

典型算法

在计算智能领域已取得成功的基于SI的优化算法有蚁群算法、粒子群算法、鱼群算法、猴群算法等。

蚁群算法（蚂蚁觅食）
粒子群算法（蜂群或鸟群觅食）
鱼群算法（鱼群的移动与觅食）
猴群算法（猴群的移动与觅食）
 优点
灵活性稳健性自组织潜在的并行和分布

蚁群算法

蚁群算法是模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为而设计的，蚂蚁在遇到食物返回的路上会分泌（信息素），信息素会随着时间慢慢挥发，且关键路径上的信息素相对浓度（较高），蚁群算法已被广泛应用于许多优化问题中，其中有（聚类问题）（路由算法设计）（图着色）（车辆调度）（机器人路径规划）。

各种行为因子：

（1 ）范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径，那么它能观察到的范围以及能够移动的范围都会发生在这样的一个范围之内。
（2 ）环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有其他的蚂蚁，还有信息素，信息素可以设计为单一种类也可以多种类（如两种），一种是找到食物的蚂蚁撒下的食物信息素，另外一种是找到食物的蚂蚁洒下的蚁窝的信息素，或者其它目的的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。同时环境也以一定的速率让信息素消失。
（3 ）觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则通过比较在能感知的范围内的信息素的多少，然后它会向信息素最多的方向移动。同时每只蚂蚁还以小概率来进行“犯错”。从而并不总是向信息素最多的方向移动。蚂蚁找到蚁巢的规则可以和觅食规则相同，只不过它只对蚁巢的信息素进行反应，而对食物信息素没有任何反应。
（4 ）移动规则：每只蚂蚁都向信息素最多的方向前进，并且在运动方向上有一个随机的小扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了那些点，如果发现要走的下一个点已经走过了，它就会尽量避开。
（5 ）避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则或返回蚁巢规则进行移动。
（6）信息素规则：每只蚂蚁在刚找到食物或者蚁巢的时候散发的信息素最多，并随着它走远的距离，散播的信息素越来越少。
根据需要还可以定义其它规则。

粒子群算法（PSO)

模拟鸟群或蜂群的觅食行为。基本思想：通过群体中个体之间的协作和信息共享来寻找最优解。

每个粒子有一个适应度（评估）函数以模拟每只小鸟与食物的距离
 每个粒子有一个速度决定它的飞行方向和距离，初始值可以随机确定
 每一次单位时间的飞行后，所有粒子分享信息，下一步将飞向自身最佳位置（个体极值（pbest）和全局最优位置（全局极值(gbest)）的加权中心

初始化为一群随机粒子，通过迭代找到最优。
每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来更新自己的位置。

粒子速度和位置的更新

假设在D维搜索空间中，有m个粒子：

其中第i个粒子的位置为矢量 $\vec{X_i}=(X_{i1},X_{i2},\dots,X_{iD})$

其飞行速度也为一个矢量，记作 $\vec{v_i}=(v_{i1},v_{i2},\dots v_{iD})$

第i个粒子搜索到的最优位置为 $\vec{p_i}=(p_{i1},p_{i2},\dots p_{iD})$

整个粒子群搜索到的最优位置为 $\vec{p_{gbest}}=(p_{gbest1},p_{gbest2},\dots p_{gbestD})$

k+1时刻第i个粒子的位置和速度更新为：

$v^{k+1}_{id}=w\cdot v^k_{id}+c_1\cdot rand()\cdot (p_{id}-x_{id}^k)+c_2\cdot rand()(p_{gbest}-x^k_{id})$

$，，x^{k+1}_{id}=x^k_{id}+v_{id}^{k+1} i=1,2,…，m; d=1,2…，D$

其中，w称为惯性权重， $c_1,c_2$ 为两个正常系数，称为加速因子。将 $v_{id}^k$ 限制在一个最大速度 $v_{max}$ 内。

$v^{k+1}_{id}=w\cdot v^k_{id}+c_1\cdot rand()\cdot (p_{id}-x_{id}^k)+c_2\cdot rand()(p_{gbest}-x^k_{id})$

$，，x^{k+1}_{id}=x^k_{id}+v_{id}^{k+1} i=1,2,…，m; d=1,2…，D$

$w\cdot v^k_{id}$ ：“惯性部分”，对自身运动状态的信任

$c_1\cdot rand()\cdot (p_{id}-x_{id}^k)$ ：“认知部分”，对粒子本身的思考，即来源于自己经验的部分

$c_2\cdot rand()(p_{gbest}-x^k_{id})$ ：“社会部分”，粒间子的信息共享，来源于群体中的其它优秀微粒的经验。

w的作用惯性权重w

（1）使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。
（2 ）表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动。
（3 ）较大的w 有利于跳出局部极值，而较小的w有利于算法收敛。

加速常数 $c_1$ 和 $c_2$

（1)代表将粒子推向pbest 和gbest 位置的统计加速项的权重。
（ 2 ）表示粒子的动作来源于自己经验的部分和其它粒子经验的部分。
（ 3 ）较小的值允许粒子在被拉回之前可以在目标区域外徘徊，而较大的值则导致粒子突然冲向或越过目标区域。

将c 1 和c 2 统一为一个控制参数，φ= c 1 +c 2

如果φ 很小，粒子群运动轨迹将非常缓慢；
如果φ 很大，则粒子的位置变化非常快；
实验表明，当φ=4.1 （通常c 1 =2.0 ，c 2 =2.0 ）时，具有很好的收敛效果

粒子数
一般取20 ～40 ，对较难或特定类别的问题可以取100 ～200。。
 最大速度v max
决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度。
 终止条件
最大循环数以及最小错误要求。

与遗传算法的比较

 共性
（ 1 ）都属于仿生算法；（ 2 ）都属于全局优化方法；
（ 3 ）都属于随机搜索算法；（ 4 ）都隐含并行性；
（ 5 ）根据个体的适应信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等；
（ 6 ）对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。

差异
（ 1 ）PSO 有记忆，所有粒子都保存较优解的知识，而GA ，以前的知识随着种群的改变被改变；
（ 2 ）PSO 中的粒子是一种单向共享信息机制。而GA 中的染色体之间相互共享信息，使得整个种群都向最优区域移动；
（ 3 ）GA 需要编码和遗传操作，而PSO 没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。

粒子群优化算法流程

1 、初始化一群粒子（群体规模），包括随机的位置和速度
2 、评价每个粒子的适应度
3 、对每个粒子更新个体最优位置 $p_{id}$
4 、更新全局最优位置 $p_{gbest}$
5 、根据速度和位置方程更新每个粒子的速度和位置( $v_{id}$ 和 $p_{id}$ )
6 、如未满足结束条件（通常为满足足够好的适应值或达到设定的最大迭代次数），返回2

鱼群算法

模拟鱼群的觅食行为、集群行为、跟随行为和随机游动行为。
大多时间，鱼会向有更多食物的方向游动，
同时它们会尽量的聚集在一起来（在某个区域不是太密集的前提下）并保持和鱼群的中心位置的鱼的游动方向一致

rand()可以产生从0到1之间的随机数

聚集行为觅食行为跟随行为移动行为都有公式

群智能优化算法与进化计算

相同点：
均为概率搜索算法
目的都是为了模拟自然现象，利用它们的某些特点去解决实际问题
区别：
智能优化算法的灵感来源于群居动物的社会行为，强调对社会系统中个体之间相互协作的模拟。

基于群智能优化算法的不足

数学理论基础相对薄弱，涉及的各种参数
设置没有确切的理论依据
带有随机性，每次的求解不一定一样，当处理突发事件时，系统的反映可能是不可预测的，这在一定程度上增加了其应用风险。