数学建模之智能计算(2).doc

数学建模之智能计算（2）

一、 蚁群算法
蚁群优化算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法.它由意大利学者Marco Dorigo于上世纪九十年大初期最早提出的一种源于大自然的新的仿生类算法，其灵感来源于上述所描述的蚂蚁在寻找食物过程中发现路径的行为.蚁群算法主要是借鉴蚂蚁群体之间的信息传递方法达到寻优的目的，最初有称之为蚁群优化方法，在计算机模拟仿真中由于采用了人工“蚂蚁”的概念，因此，也称蚂蚁系统（Ant System.AS）。
主要讨论内容
蚁群算法基本原理
蚁群算法模型的建立
蚁群算法研究进展
基于蚁群算法的TSP求解
一个实例
蚁群算法的收敛性讨论
一、基本原理
1、 从真实蚂蚁到人工蚂蚁
蚁群算法是一种受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。其基本原理如下图：

图1 蚁群觅食路线
上图表示蚂蚁觅食的线路，为蚁穴 , 为食源，从到有两条线路可走，是长路径，是短路径。蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向。图表示起始情况，假定蚁穴中有只蚂蚁，分别用表示，Ｂ为食源。开始时蚁穴中蚂蚁向食源移动，由于路线和上均没有蚂蚁通过，在这两条路线上都没有信息素气味，因此蚂蚁选择这两条线路的机会均等。令蚁选择线路，蚁选择线路，假定蚂蚁移动的速度相同，当蚁到达食源时，蚁还在途中，如图。蚁到达食源以后就返回，这时从返回也有两条线路选择，哪一条线路上信息素的气味重就选择哪一条。因为蚁还在途中，没有到达终点，这时在线路上靠近端处，蚁还没有留下信息素气味，所以蚁返回蚁穴的线路只有一个选择，就是由原路返回。当蚁返回时，蚁开始出发，蚁的线路选择必定是，因为这时上气味浓度比上重 (上已有蚂蚁两次通过 ) ，如图所示。当蚁到达食源时 ,蚁返回线路必然选择，如图所示。如此继续下去 ，沿线路上移动的蚂蚁越来越多，这就是巢穴到食源的最短路线，蚂蚁根据线路上留下信息素浓度的大小，确定在路线上移动的方向，蚁群向信息素浓度重的线路集聚的现象称为正反馈。蚂蚁算法正是基于正反馈原理的启发式算法。
蚁群觅食过程中的简单规则
每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：
　　1、范围：
　　蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
　　2、环境：
　　蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
　　3、觅食规则：
　　在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
　　4、移动规则：
　　每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
　　5、避障规则：
　　如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
　　7、播撒信息素规则：
　　每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。
　　根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于上述所描述的蚂蚁在寻找食物过程中发现路径的行为。其中“信息素”在蚁群算法中期到非常重要的启示作用。
[1] Colorni A, Dorigo M, Maniezzo V, etal. Distributed optimization by ant colonies . Proceedings of the 1st European Conference on Artifical Life, 1991,134-142
[2] Dorigo M. Optimzation,learning and natural algorithms.Ph.D.Thesis, Department of Electronics, Politenico diMilano,Italy,1992
在蚁群算法中，需要定义人工蚂蚁的概念，人工蚂蚁具有双重特性，首先，它们是真实马一行维特征的一种抽象，通过对真实蚂蚁行为的观察，将蚁群行为中的智能化因素赋予人工蚂蚁；另一方面，为了解决实际问题，人工蚂蚁必须具备真实蚂蚁一些所不具备的特性。归纳起来看，它与真实蚂蚁之间主要存在下列异同

二、人工蚁与真实蚁的共同特征比较
1、 人工蚁与真实蚁一样，都是一个需要合作的群体
问题的解决需要通过人工蚁的合作来完成，人工蚁群通过相
互协调与合作从而有可能找到全局最优方案，而每只人工蚁的单独行动只可能找到局部最优解
2、 人工蚁和真实蚁一样，都要完成一个共同的任务
人工蚁与真实蚁一样，都要完成一个共同的任务，即需寻找
一个从源节点（巢穴）到目的节点（食物源）之间的最短路经（或最小代价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻节点之间移动，直至遍历所有可能路径，为了减少计算复杂度并寻找出最短路径，需要记录当前路径
3、 人工蚁与真实蚁一样都通过使用信息素进行间接通信
人工蚁与真实蚁一样都存在一种改变当前所处环境的机制：
真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改更新在其所经过的路径上存储的信息，是一种模拟自然界中的信息素轨迹更新的过程
4、 人工蚁利用真实蚁觅食行为中的自催化机制—正反馈
当一些路径上通过的蚂蚁越来越多时，路径上留下的信息素
轨迹也越来越多，使得信息素强度变大，根据蚂蚁清倾向于选择信息强度大的特点，后来的蚂蚁选择该路经的概率也越高，从而增加了该路经的信息素强度，这称之为自催化过程
自催化机制利用信息素作为反馈，通过对系统演化过程中较优解的增强作用，使得问题的解向着全局最优的方向逐步接近
5、 信息素的挥发机制
在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，
这种机制需要蚂蚁忘记过去，不受过去经验的过分约束，有利于指引蚂蚁朝着新的方向搜索，避免早熟收敛
6、 利用当前信息进行路径选择的随机选择策略
人工蚁于真实蚁都是利用概率选择策略实现一个节点到相
邻节点的移动，选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，因此，人工蚁与真实蚁所使用的选择策略在时间和空间上都具有局部特性
人工蚁具备一些真实蚁所不具备的特征，主要体现在下列五个方面
1、 人工蚁存在于离散空间中，它们的移动实质上是有一个离散状态到另一个离散状态的转移；
2、 人工蚁具有一个记录其过去自身行为的内在状态；
3、 人工蚁存在于与时间无关联的环境之中
4、 人工蚁并非完全盲从，它受到问题特征的启发，例如，
有的问题中人工蚂蚁产生一个解后改变信息量，而在有的问题中人工蚂蚁每做一次选择便改变信息量
5、为了提升人工蚁系统的性能，改进算法效率，人工蚁可增加一些性能，如预测未来、局部优化、回溯等。在很多具体应用中，人工蚁可以在局部优化的过程中交换信息以及实行简单预测等。
三、基本蚁群算法模型的建立
1、蚂蚁个体的抽象
抽象出能够为建立模型起作用的真实蚁群的机理，摒弃与建立模型算法无关的因素.
2、问题空间的描述
蚂蚁轨迹可以看成为二维平面上的活动，其活动过程为一个状态到另一个状态的迁移，因此，利用蚁群算法求解的问题其数学模型采用图论语言来描述就显得非常自然，另一方面，在实际问题中的许多应用问题可以通过图的语言来描述，这就使得蚁群算法的广泛应用成为可能.
3、寻找路径的抽象
把真实蚂蚁的觅食过程抽象成算法中解的构造过程，将信息素抽象成存在于图边上的轨迹，信息素的大小可以通过设置权重来体现，并根据权重的值决定走向下一个节点的概率.用任何两个节点分别表示蚂蚁的巢穴（初始节点）和食物源（终止节点），人工蚂蚁按照一定的状态转移概率从初始节点移动到邻近的节点，以此类推，最终选择行走到目标节点，从而得到问题的一个可行解.
4、信息素挥发的抽象
自然界中真实蚂蚁在所经过的路径上会连续不断的留下信息素，而信息素也会随着时间的推移连续不断的挥发，在人工蚁群算法中，蚂蚁完成从某一节点到相邻节点的一次移动后（相应于经过一个时间单位），进行一次信息素挥发，这有利于避免陷入局部最优的陷阱.
5、启发因子的引入
为了设计有效的蚁群算法，在决定蚂蚁行走方向的状态转移概率时，引入一个随机搜索的过程，即引入一个启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，从而极大的增加算法的有效性，从而使蚁群算法的有效应用成为可能.
为了说明蚂蚁系统模型，下面讨论基于蚁群算法的旅行商问题的解.
在模型建立与求解过程中，我们需要首先引入下列符号：
用表示时刻位于城市的蚂蚁数目，为蚁群中蚂蚁的总数目，为TSP问题的规模，即城市的个数.显然， ，表示t时刻路径上的信息量，是t时刻集合中元素（城市）两两连接上残留信息量的集合，在初始时刻各路经上的信息量都相等，即设（常数），基本蚁群算法的寻优是通过有向图来实现的.
蚂蚁在运动过程中，根据各条路经上留下的信息量决定其转移方向.此处采用禁忌表来记录蚂蚁k当前所走过的城市.集合随着进化过程作动态调整，而用来表示蚂蚁k下一步允许访问的城市位置，显然.若用表示城市和城市之间的距离，则t时刻，图中边反映由城市转移到城市的启发程度，即能见度，可以取为，是一个与时间无关的常数.在搜索过程中，蚂蚁根据各条路经上的信息量以及路径的启发信息（主要是路径长度）来计算状态转移概率，如用表示蚂蚁k在 t时刻由城市转移到城市的状态转移概率，则可以定义
(1)
在上式中，与分别反映了路径轨迹与路径能见度的相对重要性. 作为信息启发式因子，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强，作为启发式因子，反映了蚂蚁在运动过程中启发因素在选择路径时的受重视程度，其值越大，则该状态转移越接近贪心规则.在两种极端情形：与下，则分别退化为传统的贪心算法与纯粹的正反馈启发式方法.
上述状态转移概率的计算用到t时刻各条路经上信息量的计算，下面我们讨论的计算方法.在初始时刻，，可以选择（常数），蚂蚁完成一次循环后各路经上的信息量更新方程设为
(2)
其中，表示信息素的持久系数（即信息的挥发度），而则表示信息素的衰减系数，因此一般选择比较合适.从上式可以看出，在已知的情况下，为了计算，需要计算出全体蚂蚁在时刻t到时刻内留在路径上信息素量的增量，因此，需要计算出每只蚂蚁k 在时刻t到时刻内留在路径上信息素量的增量.根据更新策略的不同，Dorigo M提出了三种计算不同的方法，从而得到三种不同的蚁群算法模型，分别称之为Ant-Quantity（蚁量）模型、Ant-Density（蚁密）模型以及Ant-Cycle（蚁周）模型.
在蚁量模型中
(3)
其中，Q 表示信息素强度，为蚂蚁循环一周释放的总信息量.
在蚁密模型中
(4)
从上面的定义不难看到，在蚁密模型中，一只蚂蚁从城市转移到城市的过程中路径上信息素的增量与边的长度无关，而在蚁量模型中，它与成反比，就是说，在蚁量模型终端路径对蚂蚁更具有吸引力，因此，更一步加强了状态转移概率方程中能见度因子的值.
在上述两种基本蚁群算法模型中，蚂蚁完成一步后即更新路径上的信息素，即在建立方案的同时释放信息素，采用的是局部信息，为了充分利用整体信息从而得到全局最优算法，下面介绍一种蚁周模型.
蚁周模型与上述两种模型的主要区别在于的不同，在蚁周模型中，表示蚂蚁经过n步完成一次循环后后更新蚂蚁k所走过的路径，具体更新值满足 （5）
其中，表示蚂蚁k在本次循环中所走路径的长度.
由于蚁周系统中，要求蚂蚁已经建立了完整的轨迹后再释放信息，信息素轨迹根据如下公式进行更新
（6）
四、 基本蚁群算法的实现
以TSP为例，基本蚁群算法的具体实现步骤描述如下：
（1）参数初始化 令时间，循环次数计数器初值，轨迹强度增量的初值设为0，即，初始阶段禁忌表设为空集，即，由某种启发式算法规则确定，在TSP中一般取为，将m只蚂蚁随机置于n个元素（城市）上，并令有向图上每条边的初始信息量为常数，即；
（2） 循环次数蚂蚁禁忌表索引号，蚂蚁数目；
（3） 蚂蚁个体根据状态转移概率公式(1)计算的概率原则元素（城市）j并前进，；
（4）修改禁忌指针表，即将选择好之后的蚂蚁移动到新的元素（城市），并将该元素（城市）移到该蚂蚁个体的禁忌表中；
（5）信息素更新的计算
在蚁密模型中， ；
在蚁量模型中，；
对于每一个路径，设置持久因子，并按照（2）计算.
在蚁周模型中，对于，根据禁忌表的记录计算，对于，设，即为蚂蚁k的禁忌表中连接城市的路径，计算，对于每一条路经，按照（6）计算.
（6）纪录到目前为止的最短路经，如果，则计算终止，循环结束并输出计算结果，否则，清空禁忌表并返回步骤（2）.
一系列仿真试验表明，在求解TSP 问题时，蚁周算法的性能优于其它两种算法，因此，人们更多地关注于一周算法的研究.
下面我们讨论基本蚁群算法的计算复杂度问题.
算法计算复杂度由时间复杂度和空间复杂度构成.根据蚁群算法所列参数，以及每一步算法描述，其算法每一步运算量主要包括：初始化参数，含赋值运算量为，设置禁忌表赋值运算量为，每只蚂蚁单独求解需要算术元算量为，而信息素轨迹浓度的更新需要次算术运算，因此，算法总的运算量为.基本蚁群算法的求解通过有向图来描述，因此需要一个n阶二维距离矩阵来描述问题本身的特征；为了表示有向图上的信息量，需要用另外一个n阶二维距离来表示图上的信息素浓度；同时，在求解TSP问题的过程中，为了保证TSP城市不出现重复的现象，需要为每只蚂蚁设置一个n阶一维数组的禁忌表；为了保存蚂蚁寻找到的解，还需为每只蚂蚁设置一个数组；为了便于更新轨迹，需要利用二维数组保存每条边上的信息素更新量，等等.整个计算过程所耗的空间复杂度为.
由于蚁群算法是一种比较新的模拟进化智能算法，目前还没有形成非常严格的系统理论，包括算法中的许多参数设置、信息素量的更新策略等都仍然有许多值得研究的地方.另外，蚁群算法可以用来有效求解较小规模的TSP问题，但是，对较大规模的TSP问题，蚁群算法存在需要循环次数偏大等问题.针对这些问题，近年来研究者进行了大量深入的研究，提出了许多改进的蚁群优化算法，这些改进算法主要集中在性能的改进等方面.例如，精英策略，其思想是在算法开始后便对到目前为止所发现的最佳路径给以记录，并将随之得到的行程标记为全局最优行程，一旦对信息进行搜索更新，则对所得到的行程加权处理，而经过上述行程的蚂蚁记为“精英”，这样做的目的可以增加选择较好行程的机会，从而可能以更快的速度收敛到更好的解.在精英策略中，需要注意的是：若选择的精英过多，则算法可能因为陷入举步最优解的陷阱而过早出现搜索停滞现象，
极大—极小系统（MAX—MIN System）是另一种有代表性的改进算法，该算法要求每次迭代后授权一只蚂蚁对蚂蚁系统的信息素进行更新修改以获取更好的解.为了增强算法初始阶段的搜索能力，信息素的初始值被设置为取值上限MAX，为了避免搜索停滞，路径上的信息素浓度被限制在区间内.另外，基于秩权限（Rank—based Version）的改进AS 算法也是一种有效算法，与精英算法相似，在该算法中总是更新更好路径上的信息素.以求解大型TSP（最多包含132座城市）为例，研究表明，基于AS的算法性能均优于前面两章描述的模拟退伙算法（SA）和遗传算法(GA)，而基于秩权限的改进AS 算法可以得到比精英策略AS 算法更优的解.
蚁群算法进化计算过程，实际上是计算机通过程序不断迭代来实现的，由于蚁群算法在构造解的过程中.利用了随机选择策略，因此，算法是否收敛就成为人们关心的问题.1999年，Gutjahr W J最早从有向图的角度对一种改进的蚁群算法—图搜索蚁群系统（GBAS）的收敛性进行了证明. 此后，改进的蚁群算法及其收敛分析的工作一直是研究的重点和难点问题.
五、改进的蚁群算法
蚁群算法作为一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群体进化过程来寻求最优解，该过程包含适应阶段与协作两个阶段.在适应阶段，各候选解根据积累的信息不断的调整自身结构；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解.但是，基本蚁群算法存在搜索时间过长的问题，虽然计算机速度的提高以及蚁群算法的本质并行性在一定程度上可以缓解这一问题，但是，随着问题规模变大，计算实时性会成为一大难题.为了克服基本蚁群算法的缺陷，人们提出了许多改进的蚁群算法.下面介绍三种改进方案.
一、具有变异特征的蚁群算法
这是1999年吴庆洪等人针对TSP问题的基本蚁群算法提出的一种改进方案.对于路径的选择采取逆转变异方式，设某个体所走路径：

如果距离满足

其中表示对进行取整运算.则进行操作：inversion(),函数inversion()的功能是把个体solution的和这一段颠倒过来，如：

其中，变异的次数是随机的，这一过程涉及到的运算比蚁群算法中的循环过程要简单得多，因此只需较短的时间内便可完成相同次数的运算.另一方面，经过这种变异算子作用后，这一代解的性能产生明显的改善，从而也能改善整个群体的性能，减少计算时间.试验表明，上述具有变异特征的蚁群算法可以有效加快搜索速度.
2、基于蚁群算法与遗传算法融合(GAAA)的改进方法
上述GAAA算法是由丁建立等在2003年提出了的，其基本思想是吸取两种算法的优点，克服各自的缺陷，优势互补.在时间效率上优于遗传算法，在求解精度效率上优于遗传算法，是时间效率和求精解效率都比较好的启发式算法.
其基本思路是算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，其结果是产生有关问题的初始信息素分布. 算法后过程采用蚁群算法，在一定初始信息素分布的情况下，充分利用蚁群算法的并行性、正反馈性、求精解效率高登
特点.
下面讨论GAAA算法中遗传算法的定义与设置.
在编码与适应值函数的涉及中，结合解决问题，采用十进制编码，适应值函数结合目标函数而定，如TSP问题，以遍历城市次序作为遗传算法的编码，适应值函数取为哈密顿圈的长度的倒数.
种群生成与染色体选择则利用rand函数随机生成一定数量的十进制实数编码种群，根据适应值函数选择准备进行交配的一对染色体父串.
交叉算子采用Davis提出的顺序交叉法，先进行常规的双点交叉，再进行维持原有相对访问顺序的巡回路线修改，具体交叉如下：
·随机在父串上选择一个交配区域，如两父串选定为

将的交配区域加到前面，将的交配区域加到的前面：

·依次删除中与交配区域相同的数码，最后得到两字串：

变异算子采用逆转变异方法，所谓逆转，如染色体在区间和处发生断裂，断裂片断又以顺序插入，于是逆转后的染色体变为，其中，“进化”是指逆转算子的单方向性，只有经逆转后适应值有提高的才能接受下来，否则逆转无效.
为了实现遗传算法和蚁群算法的有效结合，需要讨论GAAA算法的改进与衔接问题.
首先通过遗传算法得到一定的路径信息素，并把信息素的初值设置为，其中，是根据具体求解问题规模给定的一个信息素常数，是遗传算法求解结果转换得信息素值.
信息素更新模型采用蚁群圈模型进行信息素更新，即一圈中只有最短路径的蚁群才进行信息素修改增加，而所有路径的轨迹更新方程均采用：

为了验证算法性能，采用典型的含遍历30个城市的TSP问题进行仿真实验，GAAA算法中迭代次数固定为30代，蚁群算法中各路径的信息素初始值设为60，遗传算法求解结果转换的信息素值为经过路径加2，轨迹更新表1反映GAAA算法优化求解数据逼近过程，图8直观地说明了GAAA算法中经过遗传算法求解结果在信息素初值设置的表现，不难看出GAAA 算法是一个逐步收敛的过程，从均值与分布的角度来看，具有非常高的求解精度，图9 是应用GAAA 算法得到的最优解，与采用其他方法得到的最优解结果一致.图10～图11找到的解与最优解非常接近，是其它算法容易陷入举步最优的几个值，由于在遗传阶段采用随机产生种群，因而有效避免了陷入举步最优.

表1 GAAA 算法优化解数据逼近过程

图8 GAAA算法一次随机遗传变异后产生的信息素分布

图9 GAAA算法找到的最优路径（423.74）

图10 GAAA算法一次随机迭代找到的最优路径(424.46)

图11 GAAA算法一次随机迭代找到的最优路径(424.67)
下面的三个表则给出了GAAA算法与基本蚁群算法以及遗传算法与模拟退火算法结合方法的实验结果比较.

表2 GAAA算法实验结果

表3 基本蚁群算法实验结果

表4 遗传算法与模拟退火算法结合方法实验结果

通过仿真实验可以看出，GAAA算法无论在优化性能还是时间性能上都能够取得好的效果，由于在遗传算法中使用随机生成种群，不仅加快了蚁群算法的速度还避免了求精解阶段陷入局部最优，另外，由于采用遗传算法与蚁群算法结合，对于蚁群算法中的参数调整有较大的减少，从而减少了盲目的实验次数.
在蚁群算法的设计过程中，为了避免过小导致收敛速度慢的缺陷，还可以通过设置自适应变化的以提高收敛速度，例如，取初始值，当算法求得的最优值在规定的次循环后还没有明显改进时，取

其中为调解因子，一般取，而为的最小值.
仿真结果表明，与基本蚁群算法相比，最优解以及收敛性能等方面均有一定的提高.

二、 粒子群算法
动物学家Reynoldsf对鸟群的飞翔和群舞行为很感兴趣，而动物学家Heppner则对于大数目的鸟群为什么能如此一致的朝一个方向飞行、突然同时转向、分散、再聚集很感兴趣，这些研究者通过对每个个体的行为建立简单的数学模型，然后在计算机上模拟和再现这些群体行为.
基于鸟类的导航成为人们研究的课题。
在其他动物群体中，比如畜群、鱼群以至于人类群体，社会生物学家Wilson认为“至少从理论上说，群体中的单个成员在搜寻食物的过程中能够利用其它成员曾经勘测和发现的关于食物位置的信息，当事先不确定食物位于什么地方时，这种信息的利用是至关重要的，这种信息分享的机制远远超过了由于群体成员之间的竞争而导致的不利之处”以上对于动物群体的观察说明了群体成员之间的信息分享是非常重要的，这一点也是粒子群优化算法赖以建立的基本原理之一.
研究者的另一个动机是希望模拟人的社会行为，即单个的人是怎样通过调节个人的行为以便与其它社会成员和谐一致，并取得最有利于自己的位置.单个的人为了避免与其它社会成员发生冲突，通常利用自己以前的经验和其它社会成员的经验来调整自己的行为，这是PSO设计思想的另一个源泉.
若把在某个区域范围内寻找某个函数最优值的问题看作鸟群觅食行为，区域中的每个点看作一只鸟，现把它叫粒子，每个粒子之间是协作的，相互之间是互通信息的.同时每个粒子都利用自己以前的经验和其它社会成员的经验来调整自己的行为.
粒子群算法是一种演化计算技术，是一种基于迭代的优化工具，系统初始化为一组随机解，通过迭代搜寻最优值，将鸟群运动模型中栖息地类比为所求问题空间中可能解的位置，利用个体间的传递，导致整个群体向可能解的方向移动，逐步发现较好解.
一、基本粒子群算法
粒子群算法，其核心思想是对生物社会性行为的模拟.最初粒子群算法是用来模拟鸟群捕食的过程，假设一群鸟在捕食，其中的一只发现了食物，则其他一些鸟会跟随这只鸟飞向食物处，而另一些会去寻找更好的食物源.在捕食的整个过程中，鸟会利用自身的经验和群体的信息来寻找食物.粒子群算法从鸟群的这种行为得到启示，并将其用于优化问题的求解.若把在某个区域范围内寻找某个函数最优值的问题看作鸟群觅食行为，区域中的每个点看作一只鸟，现把它叫粒子（particle).每个粒子都有自己的位置和速度，还有一个由目标函数决定的适应度值.但每次迭代也并不是完全随机的，如果找到了新的更好的解，将会以此为依据来寻找下一个解.图1 给出了粒子运动的思路图.

图2.4.1粒子运动的路线图
下面给出粒子群算法的数学描述.
假设搜索空间是D维的，群中的第i个粒子能用如下D维矢量所表示：
(1)
每个粒子代表一个潜在的解，这个解有D个维度.每个粒子对应着D维搜索空间上的一个点.粒子群优化算法的目的是按照预定目标函数找到使得目标函数达到极值的最优点.第i个粒子的速度或位置的变化能用如下的D维向量表示：
(2)
为了更准确地模拟鸟群，在粒子群优化中引入了两个重要的参量.一个是第i个粒子曾经发现过的自身历史最优点(Personal best，pbest)，可以表示为：
(3)
另一个是整个种群所找到的最优点(Global best，gbest)，可以表示为：
(4)
PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解.在每一次的迭代中，粒子通过跟踪两个“极值”(和)来更新自己.在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置：

(速度更新公式) (5)

(位置更新公式) (6)
其中称之为惯性因子，在一般情况下，取，代表迭代序号，G是预先给出的最大迭代数；, ，N是群的大小； 和是正的常数，分别称为自身认知因子和社会认知因子，用来调整和的影响强度.和是区间[0，1]内的随机数.由(5)和(6)构成的粒子群优化称为原始型粒子群优化.
从社会学的角度来看
公式(5)的第一部分称为记忆项，表示上次优化中的速度的影响；公式第二部分称为自身认知项，可以认为是当前位置与粒子自身最优位置之间的偏差，表示粒子的下一次运动中来源于自己经验的部分；公式的第三部分称为社会认知项，是一个从当前位置指向种群最佳位置的矢量，反映了群内粒子的协作和知识共享.可见，粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动.随着迭代进化的不断进行，粒子群逐渐聚集到最优点处，图2 给出了某个优化过程中粒子逐渐聚集的示意图.

图2 粒子群在优化过程聚集示意图
综上所述，我们得到如下基本粒子群算法流程：
(1) 设定参数，初始化粒子群，包括随机位置和速度；
(2) 评价每个粒子的适应度；
(3) 对每个粒子，将其当前适应值与其曾经访问过的最好位置pbest作比较，如果当前值更好，则用当前位置更新pbest；
(4) 对每个粒子，将其当前适应值与种群最佳位置gbest作比较，如果当前值更好，则用当前位置更新gbest；
(5) 根据速度和位置更新公式更新粒子；
(6)若未满足结束条件则转第二步；否则停止迭代.
迭代终止条件根据具体问题一般选为迭代至最大迭代次数或粒子群搜索到的最优位置满足预定的精度阈值.
3 粒子群算法的轨迹分析
4 改进的粒子群算法
作为一种模拟鸟类迁徙觅食过程建立起来的智能算法，与其他智能算法相比具有非常鲜明的特色，同时也存在一定的缺陷。
优点：（1）粒子群算法没有遗传算法所需要的交叉和变异运算，仅依靠通过确定粒子的方向和速度完成搜索，并且在迭代进化过程中只有最优的粒子将信息传递给其它粒子，因此，搜索速度快；
（2）粒子群算法具有记忆特性，可以记忆粒子群的历史最佳位置并传递给其它粒子；
（3）结构简单，需要调整的参数少，从而易于工程实现；（4）采用实数编码，问题解的变量数直接作为粒子维数，求解过程直观。
缺陷：（1）容易陷入局部最优，收敛早熟以及求解精度低；（2）不能有效解决离散与组合问题以及很难求解非直角
坐标系下表示的实际问题等。
针对上述基本粒子群算法的缺陷，人们提出了许多改进方案。
（1）将各种先进的理论引入到粒子群算法中，得到改进的粒子群算法；
（2）将粒子群算法和其它智能优化算法相结合，研究各种混合优化算法，达到取长补短、改善算法某方面性能的效果；
（3）另外，基本粒子群算法主要针对连续函数进行搜索运算，但许多的实际问题都呈现为离散的组合优化形式，因此，粒子群算法的离散化就成为第三类改进方法，粒子群算法的离散化又存在两条不同的途径：第一种途径是以标准的连续粒子群算法为基础，将所研究的离散问题映射到连续的粒子运动空间，仍然采用标准的粒子群算法速度以及位置更新策略，适当修改标准PSO算法从而得到问题的解；另一种途径是针对离散优化问题，在保持标准粒子群算法基本思想、算法框架以及信息更新本质机理不变的前提下，重新定义合适的粒子群离散表示方式与操作算子以求得问题的解。这两种方法存在一定的区别，首先，第一种途径将实际离散问题映射到粒子连续运动空间后，在连续空间中计算求解；第二种途径则将PSO算法映射到离散空间，在离散空间中求解，因此上述两种方法经常被称之为基于连续空间的DPSO与基于离散空间的DPSO。下面分别有代表性的集中算法对上述三类改进粒子群算法作简单描述。
一、加速粒子群算法
为了提高粒子群算法的效能并扩展其应用范围，第一种改进措施就是将先进的理论溶入到粒子群算法中，例如：
1、带惯性权重(inertia weight)粒子群算法及其改进
探测是指粒子在较大程度上离开原先的寻优轨程，偏到新的方向进行搜索；开发则指粒子在较大程度上继续原先的寻优轨程进行细部搜索.为了更好的控制算法的探测和开发能力，引入惯性权重w，使得 (5)式改变为：
（18）
大量的实验表明，惯性权重的方法求解优化问题时具有下列特点：第一，较大惯性权重可以加强PSO算法的全局搜索能力，即探索较大的区域，较快地定位最优解的大致位置；较小的惯性权重能加强PSO算法局部搜索能力，即粒子速度减慢，开始精细的局部搜索；第二，惯性权重都是由大到小地变化.
算法流程图：
(1) 算法参数设定其中有一组s参数，共h个；
(2) 对粒子群的随机位置与速度进行初始化设置：
(3) 将整个粒子群均分为h个子群；
(4)对所有子群分别按典型粒子群算法开始运行，其中第一个子群按s1 参数的惯性权重曲线运行，第i子群按si参数的惯性权重曲线运行；
(5)判断算法收敛准则是否满足，如果满足转向第八步；否则执行第六步；
(6)每间隔一定的迭代步数测出每个子群独立的全局极值比较，把有最差全局极值的子
群用有最好全局极值的子群替代，整个粒子群变为h-1个子群，h-1个子群继续按h-1个参数的惯性权重曲线运行；
(7)判断算法收敛准则是否满足，如果满足执行第八步；否则转向第六步；
(8)输出si及相应的全局极值，算法运行结束.
其中，初始化粒子群中的位置与速度用均匀分布随机数在函数的定义域范围产生.
根据上述算法步骤，通过仿真算例来对算法性能进行测试。
2、带收缩因子(constriction factor)的粒子群算法
Clerc建议采用收缩因子的方法，通过正确选择控制参数保证PSO算法收敛.其速度更新方程为：
(28)
其中“收缩因子”为：
(29)
在使用Clerc的收缩因子方法时，通常取为4．1，从而使收缩因子等于0．729.
二、混合智能粒子群算法
1、一种模拟退火和粒子群混合优化算法
目前，人们已得到多种模拟退火和粒子群混合优化算法，但其算法原理基本相似。
混合算法在各种不同温度下串行地依次进行PSO和SA(模拟退火)搜索，使一种两层的串行结构。PSO的一次优化结果作为SA 的初始解，在SA算法中经过Metropolis抽样过程得到的解又成为PSO下一次进化的初始种群，依次对问题进行优化，在优化质量得到充分保证的前提下提高优化效率。
在混合优化算法中，需要根据粒子群算法的特点对SA的操作进行设计，SA状态函数采用，其中为随机扰动变量，一般可取为高斯分布，为扰动幅度；退温操作中的温度更新函数取为且其大小可以不断变化；新状态接受准则为；SA的抽样稳定准则采用固定步数的方法，即L为固定值，再混合算法中可取，混合优化算法流程图如图10所示。

图10 模拟退火和粒子群混合优化算法

2、遗传粒子群混合算法
将遗传算法的思想与粒子群算法结合以提高算法的性能一直是智能计算领域的一项重要内容。一种混合粒子群算法方案模仿自然界的个体成熟过程，对遗传算法中的每一代群体中的优秀个体，采用粒子群算法获得进一步提高，使算法获得比遗传算法和粒子群算法更好的优化效果。
GAPSO算法分为三部分：提高、选择交叉、变异 。在GAPSO算法中，采用浮点编码，并考虑初始条件、种群数为、速度更新公式（5）中参数以及交叉率和变异率的确定方法，经过条件初始化后，经过新的算法运算以获得新的种群。
算法的实现过程。
第一步：生成初始种群，初始化种群，对种群众参数进行赋值；
第二步：计算种群中个体的适应度，按照适应度值得大小进行排序，将排序靠前个个体保留，后各个体去除；
第三步：对前个个体按照标准PSO算法进行提高和成熟，直接进入下一代；
第四步：对下一代剩下的个个体从已经提高的个个体中按竞争选择方法，首先随机选择两个优秀个体，比较两个个体的适应度函数值，选择其中适应度函数值高的座位父体，以同样的方法再选择一个母体，以概率进行交叉，生成两个新的个体，直接获得各个体；
第五步：对于选择交叉获得的个个体以概率进行变异，变异操作完成后，把个个体进入到下一代种群中；
第六步：达到迭代次数或者检验当前种群是否满足预设的条件，若满足则停止迭代；否则转第二步。

离散粒子群算法及其改进
标准粒子群算法是一种主要针对连续优化问题而设计的搜索运算，由于许多的实际问题都以离散的组合优化问题形式出现，为了将粒子群算法应用于离散优化问题的求解，
人们从两个角度建立了离散粒子群算法：
第一种是以标准粒子群算法为基础，根据相关的离散优化问题，将离散问题空间映射到连续的粒子运动空间，并对标准