1999年，Bonabeau 、Dorigo 和Theraulaz 在他们的著作《Swarm Intelligence: From Natural to Artificial Systems 中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制粒子群优化算法
任何种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。
Swarm 可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm 的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。蚂蚁成群则有利于寻找食物，因为任一只蚂蚁发现食物都可带领蚁群来共同搬运和进食只蜜蜂或蚂蚁的行为能力非常有限它几乎进食。一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm 则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。
信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是种智能以被认为是一种智能
, 也就是说动物个体通过聚集成群而涌现出了智能。因此，Bonabeau 将SI 的定义进一步推广为：无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。这里我们关心的不是个体之间的竞争，而是它们之间的协同。
蚁群算法
蚁群算法（Ant Colony Optimization, ACO ）由
Colorni ，Dorigo 和Maniezzo 在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”
（pheromone ）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。
蚁群算法(续)
ACO 算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。
目前目前，
ACO 算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO 算法应用于连续问题的优化中。由于ACO 算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。
粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能(Swarm intelligence SI)的一种粒子群算法(particle PSO 算法简介
(Swarm intelligence, SI) 的一种。粒子群算法(particle swarm optimization ，PSO)由Kennedy 和Eberhart 在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence 的优化方法。
PSO 模拟鸟群的捕食行为
PSO 模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远那么找到食道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适每个粒子还有一个速度应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO 初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫B t 另个极值是整个种群目做个体极值pBest ，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest 。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。
James Kennedy received the Ph.D. degree from theUniversity of North Carolina, Chapel Hill, in 1992. He is a Social Psychologist who has been working with the particle swarm algorithm since 1994. He has published dozens of articles and chapters on particle swarms and related topics, in computer science and social
science journals and proceedings. He is a coauthor of Swarm Intelligence (San Mateo, CA: Morgan Kaufmann, 2001), with R.C. Eberhart and Y . Shi, now in its third printing.
Rusll C. Eberhart (M’88–SM’89–F’01) received the Ph.D. degree in electrical engineering from Ka
nsas State University, Manhattan.He is the Chair and Professor of Electrical and Computer Engineering, Purdue School of Engineering and Technology, Indiana University–Purdue University
Indianapolis (IUPUI),Indianapolis, IN. He is coeditor of Neural Network PC Tools (1990),coauthor of Computational Intelligence PC Tools (1996), coauthor of Swarm Intelligence (2001),
Computational Intelligence: Concepts to Implementations (2004). He has
published over 120 technical papers.Dr. Eberhart was awarded the IEEE Third Millenium Medal. In 2002, he became a Fellow of the American Institute for Medical and Biological Engineering.
同遗传算法类似，PSO 也是一种基于群体叠代的算法，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO 的优势在于简单容易实现同时又有深刻的智能背景既适合科实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。
近年PSO 方面文献的数量
106
100
10012022
4
12
16
18
49
20
4060801995
1996
1997
1998
1999
2000
2001
2002
2003
基本PSO 算法
PSO 中，每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子(Particle)”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索.
PSO 初始化为一群随机粒子。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest . 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest 。另外，也可以不用整个种群而只是用其中一部分的邻居。
基本PSO 算法(续)
PSO 算法数学表示如下：
设搜索空间为D 维，总粒子数为n 。第i 个粒子位置表示为向量X i =( x i1, x i2,…, x iD )；第i 个粒“飞行”历史中的过去最优位置（即该位子飞行历史中的过去最优位置（即该位置对应解最优）为P i =(p i1,p i2,…,p iD )，其中第g 个粒子的过去最优位置P g 为所有P i
(i=1, …,n )中的最优；第i 个粒子的位置变化率（速度）为向量V i =(v i1, v i2,…, v iD )。每个粒子的位置按如下公式进行变化（“飞行”）：
基本PSO 算法(续)
(1)()
()[()()]()[()()]
v t w v t c rand p t x t c rand p t x t +=×+××−+××−（1）
（2）
(1)()(1)
11x t x t v t i n
d D
+=++≤≤≤≤其中，C 1,C 2为正常数，称为加速因子；rand ( )为[0，1]之间的随机数；w 称惯性因子，w 较大适于对解空间进行大范围探查(exploration)，w 较小适于进行小范围开挖(exploitation)。第d （1≤d ≤D ）维的位置变化范围为[-XMAXd , XMAXd]，速度变化范围为[-VMAXd , VMAXd]，迭代中若位置和速度超过边界范围则取边界值。
基本PSO 算法(续)
粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优P l 调整位置，即公式(2)中P gd 换为P ld 。
PSO 和遗传算法的比较
共同点
①种群随机初始化。
②对种群内的每一个个体计算适应值(fitness value)。适应值与最优解的距离直接有关。③种群根据适应值进行复制。④②④如果终止条件满足的话，就停止，否则转步骤②。
从以上步骤，我们可以看到PSO 和遗传算法有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO 没有遗传操作如交叉(crossover)和变异(mutation)，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。
不同点
与遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中, 只有gBest (orlBest) 给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解。算例：Schwefel's function
where
)
sin(
)
(
)
(⋅
−
=∑x读书绘画作品
x
x
f
n
:
1
=
i
420.9687,
=
418.9829;
=
)
(
minimum
global
500
500
−
⋅
≤
≤
−
x
n
x
f
x
搜寻过程-最初状态
搜寻过程-经过5代搜寻过程-经过10代搜寻过程-经过15代搜寻过程-经过20代搜寻过程-经过25代搜寻过程-经过100代
搜寻过程-经过500代搜寻结果
移动次数搜寻结果
0416.245599
5515.748796
10759.404006
15793.732019
20834.813763
100837.911535
5000837.965771
最佳解837.9658绥芬河怎么读
带时间窗车辆路径问题
车辆路径问题(Vehicle Routing Problem，
VRP)由Dantzig和Ramr于1959年首次提出的，它是指对一系列发货点，组成的它是指对系列发货点(或收货点)成适当的行车路径，使车辆有序地通过它们，
在满足一定约束条件的情况下，达到一定的目标(诸如路程最短、费用最小，耗费时间尽量少等)，属于完全NP问题，在运筹、计算机、物流、管理等学科均有重要意义。
带时间窗车辆路径问题（续）
带时间窗的车辆路径问题(Vehicle Routing Problem With Time Windows, VRPTW)是在VRP问题上加了客户要求访问的时间窗口。由于在现实生活中许多
如邮政投递问题都可以归结为VRPTW问题来处理(如邮政投递、火车及公共汽车的调度等)，其处理的
好坏将直接影响到企业的服务质量，所以对它的研究越来越受到人们的重视。先后出现了一般启发式算法和神经网络、遗传算法、禁忌搜索和模拟退火等智能化启发式算法，也取得了一些较好的效果。带时间窗车辆路径问题（续）
时间窗车辆路径问题一般描述为：有一个中心仓
库，拥有车K辆，容量分别为q
k
(k=1,..,K)；现有L
个发货点运输任务需要完成，以1,…,L表示。第i
个发货点的货运量为g
i
(i=1,…,L)，( max g i ≤max
)q i) ，完成发货点i任务需要的时间(装货或卸货)表
示为Ti，且任务i必须在时间窗口[ET
典故成语故事i
, LT i]完成，
其中ET
i
为任务i的允许最早开始时间，LT
i
为任务i
的允许最迟开始时间。如果车辆到达发货点i的时
间早于ET
i
，
则车辆需在i处等待；如果车辆到达时
间晚于LT
i
，任务i将被延迟进行。求满足货运要求
的运行费用最少的车辆行驶线路。
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎧
=
=
∀
≤
−
+
−
+
=
∑
∑
∑∑∑∑∑
)3(
,
,1
1
)2(
..
)1(
)0,
max(
)0,
max(
min
L
i
y
k
q
y
g
t s
LT
s
p
s
ET
p
x
c
z
L
时间窗车辆路径问题的数学描述：
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎨
∀
=
=
∀
=
=
∈
=
∀
=
=
∀
=
=
∑
∑
)8(
,轮胎销售
,1,0
1
)7(
,
,1,0
,
1
)6(
)
(
)5(
,
,
1,0
)4(
,
,1,0
；
或
；
或
；
；
k
L
i
y
k
L
j
i
x
S
x
X
电容式位移传感器
k
桥的教学反思L
i
y
x
k
L
j
y
x
L
L
L
L
带时间窗车辆路径问题（续）
这个模型通用性很强，经过参数的不同设定，可以将其转换为其他组合优化问题的数学模型。若(1)ET=0,LT→∞，则VRPTW
型若()中i,i则模型就变成了普通的VRP模型；若仅有一个车辆被利用，则该问题就变成了TSP问题。
带时间窗车辆路径问题（续）
如何找到一个合适的表达方法，使粒子与解对
应，是实现算法的关键问题之一。构造一个
2L维的空间对应有L VRP
维的间对应有个发货点任务的问
题，每个发货点任务对应两维：完成该任务
车辆的编号k，该任务在k车行驶路径中的次
序r。为表达和计算方便，将每个粒子对应的
2L维向量X分成两个L维向量：Xv (表示各任
务对应的车辆)和Xr(表示各任务在对应的车辆
路径中的执行次序)。
例如，设VRP问题中发货点任务数为7，车辆数
为3，若某粒子的位置向量X为：
发货点任务号: 1 2 3 4 5 6 7
Xv ： 1 2 2 2 2 3 3
Xr ： 1 4 3 1 2 2 1
则该粒子对应解路径为：
车1：0 Æ1 Æ0
车2：0 Æ4 Æ5 Æ3Æ2Æ0
车3：0 Æ7Æ6Æ0
粒子速度向量V与之对应表示为Vv和Vr。
该表示方法的最大优点是使每个发货点都得到车辆的配送服务，并限制每个发货点的需求仅能由某一车辆来完成，使解的可行化过求仅能由某车辆来完成，使解的可行化过程计算大大减少。虽然该表示方法的维数较
高，但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在实验结果中可以看到。VRP问题为整数规划问题，因此在算法实现过程中要作
相应修改。具体实现步骤如下：
Step1：初始化粒子群。
1.1 粒子群划分成若干个两两相互重叠的相邻子群；
1.2 每个粒子位置向量Xv的每一维随机取1～K（车辆
数）之间的整数，Xr的每一维随机取1～L(发货点任务
数)之间的实数；
1.3 每个速度向量Vv的每一维随机取-(K-1)～(K-1)（车
辆数）之间的整数，Vr的每一维随机取-(L-1)～(L-1)之
间的实数；
1.4 用评价函数Eval评价所有粒子；
1.5 将初始评价值作为个体历史最优解Pi，并寻找各子
群内的最优解Pl和总群体内最优解Pg。
Step2：重复执行以下步骤，直到满足终止条件或达
到最大迭代次数。
2.1 对每一个粒子，按式(1)计算Ｖv、Ｖr；按照式
(2)计算Xv、Xr，其中Xv向上取整；当Ｖ、X超过其
范围时按边界取值；
2.2 用评价函数Eval评价所有粒子；
2.3 若某个粒子的当前评价值优于其历史最优评价
值，则记当前评价值为该历史最优评价值，同时将
当前位置向量记为该粒子历史最优位置P
i
;
2.4 寻找当前各相邻子群内最优和总群体内最优解，
若优于历史最优解则更新P
l
、Pg。对于子群内有
多个体同为最优值的情况，则随机取其中一个为子
群内当前最优解。
其中，评价函数Eval完成以下任务:
1、根据公式计算该粒子所代表路径方案的行驶成本Z，在计算中发货点任务的执行次序要根据对应Xr值的大小顺序，由小到大执行。
2、将Xr按执行顺序进行重新整数序规范。例如某粒子迭代一次后结果如下
教导有方是什么意思啊
如，某粒子迭代一次后结果如下：
Xv ： 1 2 2 2 2 3 3
Xr ： 5 3.2 6.2 1.2 2.5 0.5 4.2则评价后重新规范的Xr是：1 3 4 1 2 1 2 实验１：采用了无时间窗VRP的例子，问题为一
个有7个发货点任务的车辆路径问题，各任务点
的坐标及货运量见下表：
表1 各发货点坐标及货运量
序号01234567
坐标(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)
货运量
(g)
0.890.140.280.330.210.410.57
注：序号0表示中心仓库，设车辆容量皆为q=1.0，
由3辆车完成所有任务。(最优路径距离为217.81)
GA参数：群体规模n=40；交叉概率Pc=0.6；变异概率
Pm=0.2；轮盘赌法选择子代，最大代数200。
PSO参数：粒子数n=40；分为2个子群，子群规模为
22，子群间重叠的粒子数为2个（子群规模的1/10）；
w=0.729；c1=c2=1.49445；最大代数200。
两种方法各运行50次，结果如下表2所示。
实验1 GA、PSO方法结果对比
方法
达到最优
脚气病缺什么路径次
数
未达最优
路径次
数
达到最优路
径平均代
数
达到最优路
径的平均
时间(s)
GA321853.932.3
PSO50028.36 3.04
实验2，采用VRPTW的例子，该问题有8项货物运输任务，货物点位置及时间窗略。实验结果如下：
实验2 GA、PSO方法结果对比
搜索成功率平均行驶成本平均成功搜索时间
GA24%993.618.41s
PSO46%940.58.53s
