2.3 群体智能
二十世纪五十年代中期出现了仿生学，人们从生物进化机理中受到启发，提出许多用于解决复杂优化问题的新方法，如遗传算法、进化规划和进化策略等。这些以生物特性为基础的进化算法的发展，以及对生物群落行为的发现，引导研究人员进一步开展了对生物社会性的研究，从而出现了基于群智能理论的优化算法，目前，群智能理论研究领域有两种主要的算法，即粒子群优化算法（Particle Swarm Optimization，PSO）和蚁群算法（Ant Colony Optimization，ACO）。粒子群算法起源于对简单社会系统的模拟，最初是模拟鸟群飞行的过程，主要用于处理连续空间中的函数优化问题；蚁群算法是对蚂蚁群落觅食过程的模拟，已成功应用于许多离散优化问题的研究。
2.3.1 粒子群优化算法
借助于生物觅食运动的启迪，Kennedy和Eberhart于1995年提出了基于群体优化技术的粒子群优化算法（PSO算法）。PSO算法是智能优化算法领域中的一个新的分支，其来源于对鸟群和鱼群群体运动行为的研究，即一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这个模型中得到启发而产生的，并用于解决连续空间中的函数优化问题。它与基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法不同的是，粒子群优化算法是通过个体之间的协作来寻找最优解的。生物社会学家E.O.Wilson关于生物群体有一段话，“至少在理论上，一个生物群体中的任何一员可以从这个群体中其他成员以往在寻找食物过程中积累的经验和发现中获得好处。只要食物源分布于不同地方，这种协作带来的优势就可能变成决定性的，超过群体中个体之间对食物竞争所带来的劣势”，这段话的意思是说生物群体中信息共享会产生进化优势，这也正是粒子群优化算法的基本思想。
在粒子群算法中，问题的解对应于搜索空间中鸟的位置，这些鸟被称为粒子。每个粒子都有自己的位置和速度（决定飞行的方向和距离），粒子在飞行过程中，参照自身的最优飞行经验和整个群体的最优经验来不断更新自己的飞行状态（速度和位置），从而来完成寻优的任务。
假设在一个n维的搜索空间中，有m个粒子组成一个群落，其中第i个粒子的位置向量表示为Xi=（xi1，xi2，…，xin）（i=1，2，…，m），飞行速度表示为Vi=（vi1，vi2，…，vin）（i=1，2，…，m）。粒子i迄今为止搜索到的最优位置为Pbesti=（pi1，pi2，…，pin）（i=1，2，…，m），整个粒子群迄今为止搜索到的最优位置为Pbestg=（pg1，pg2，…，pgn）（i=1，2，…，m），粒子i的飞行状态可根据以下公式进行更新：
式中，η1和η2称为加速系数（或称学习因子），使粒子向自身最优和群体最优的方向飞行。r1()，r2()是[0，1]之间的随机数。此外，粒子的速度Vi受到最大速度Vmax的限制。如果当前对粒子的加速将导致它在某维的速度Vid超过该维的最大速度Vmaxd，则其在该维的速度被限制为该维的最大速度。
ω为非负数，称为惯性因子（Inertia weight），用于平衡全局搜索能力和局部搜索能力。在最初的基本PSO算法中，没有惯性因子ω，Vmax对算法性能的影响非常大，与优化问题相关性非常强，且不存在经验值，不合适的Vmax将导致系统发散。
Shi和Eberhart于1998年提出了惯性因子ω的概念，通过惯性因子ω可以很好地控制粒子的搜索范围，大大削弱了Vmax的重要性。显然，较大的ω适于对解空间进行大范围探查，而较小的ω适于进行小范围开掘。他们随后又提出了自适应PSO算法、模糊自适应PSO，前者ω由0.9到0.4逐步递减，粒子进行广泛搜索，逐步求精；后者则提出了9条模糊规则，根据Gbest适应度的变化和当前ω值对惯性因子做适当调整。
式（2-9）中的第一部分为微粒先前的速度乘一个权值进行加速，表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动；第二部分为认知部分，表示粒子自身的思考；第三部分为社会部分，表示粒子间的信息共享与相互合作。
基本PSO的流程可以描述为以下内容。
（1）设置参数，初始化搜索点的位置及其速度值，通常是在允许的范围内随机产生的，每个粒子的Pbest坐标设置为其当前位置，且计算出相应的个体极值（即个体极值点的适应度值），而全局极值（即全局极值点的适应度值）就是个体极值中最好的，记录该最好值的粒子序号，并将Gbest设置为最好粒子的当前位置。
（2）判断是否满足算法收敛准则。若满足，则输出优化结果，否则重复下述操作。
1）对粒子群中的每个粒子，重复下述操作：
对每个粒子，用式（2-9）和式（2-10）对每个粒子的速度和位置进行更新；
2）对粒子群中的每个粒子，重复下述操作：
对每个粒子，计算粒子的适应度值，如果该值好于该粒子当前的个体极值，则将Pbest设置为该粒子的位置，且更新个体极值。如果某个粒子的个体极值中最好的值好于当前的全局极值，则将Gbest设置为该粒子的位置，记录该粒子的序号，且更新全局极值。
粒子群算法的基本框架如图2.2所示。
图2.2 粒子群算法的基本框架
粒子群优化算法与GA算法有些相似，如它们都是基于群体的优化技术，有较强的并行性；无须梯度信息，只需利用目标的取值信息，具有很强的通用性。但是，PSO算法比GA算法更简单，操作更方便。因而，PSO算法从诞生起一直受到数值优化领域的广泛关注，吸引了大量研究者。为改善PSO算法的收敛性和总体性能，该领域的研究者开发了很多变形算法。其中，如何加快算法的收敛速度和避免早熟收敛问题一直是大多数研究者研究的重点，也是所有随机搜索算法研究者共同面临的两个主要难题。这两个问题之间就存在很复杂的关系，在很多情况下是互相冲突的。在避免早熟收敛方面，现有的大量研究涉及如何让算法跳出局部最优点；在加快收敛速度方面，主要的研究集中在如何选择最优的算法参数，以及从其他智能优化算法中借鉴一些思想对PSO算法的主要框架加以修正上。从可得的文献中，看到一些研究者给出了非常鼓舞人心的改善结果。目前，除了理论研究之外，PSO算法已被成功应用于系统设计、多目标优化、分类、模式识别、系统建模、调度、计划、信号处理、机器人应用、决策支持、仿真和识别等领域，其优化结果非常具有竞争力。
2.3.2 蚁群优化算法
蚁群优化算法是由意大利学者Dorigo等人于二十世纪九十年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化系统，蚁群优化算法包含两个基本阶段——适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构；在协作阶段，候选解之间通过信息交流，以期望获得性能更好的解，这类似于学习自动机的学习机制。蚁群优化算法最早成功应用于解决著名的旅行商问题，该算法采用了分布式正反馈并行计算机制，易于与其他方法结合，而且具有较强的鲁棒性。
Dorigo指出：蚁群中的蚂蚁以外激素为媒介的、间接的、异步的联系方式是蚁群算法最大的特点。蚂蚁在行动（寻找食物或者寻找回巢的路径）中，会在它们经过的地方留下一些挥发性的化学物质，这些化学物质被称为外激素或信息素。这些物质能够被蚁群中其他的蚂蚁感受到，并作为一种信号来影响后到者的行为。蚂蚁在行进时会根据前边的蚂蚁所留下的信息素的浓度来选择其要走的路径，路径上信息素的浓度越大，蚂蚁选择该路径的概率越大。后到者留下的信息素会对路径上原有的信息素进行加强。这样，经过蚂蚁越多的路径，后到的蚂蚁选择该路径的概率也越大。因此，对越短的路径，由于在一定时间内走过的蚂蚁越多，其信息素的浓度越大。蚂蚁个体就是通过这样的信息交流来达到寻找食物的目的。
Dorigo对蚁群算法的论述为：在图2.3（a）中，设A为巢穴，E为食物源，H、C为一障碍物。蚂蚁要由A到达E或由E返回A，必须要经过H或C来绕开障碍物。各条路径上的长度如图2.3（a）所示。
图2.3 蚁群算法原理
设每个时间单位有30只蚂蚁由A达到B，有30只蚂蚁由E到达D。每只蚂蚁过后留下的信息素的量为1，信息素停留的时间也为1。在初始时刻，由于路径BC、BH、DC和DH上均无信息素存在，因此，位于B点和D点的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BH、BC、DH和DC，如图2.3（b）所示。经过一个时间单位后，由于BCD路径的长度是BHD路径的一半，因此，选择BCD路径的蚂蚁已经由B点到达D点，或由D点到达B点，而选择BHD路径的蚂蚁只能到达H点，BCD路径的信息素浓度是BHD路径的二倍。在下一个时刻，将有20只蚂蚁选择BCD路径，有10只蚂蚁选择BHD路径，如图2.3（c）所示。随着时间的推移，将有越来越多的蚂蚁选择BCD路径，从而找到由蚁穴到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正反馈过程。
通过上例可知，蚂蚁觅食协作方式的本质是：（1）信息素踪迹越浓的路径，被选中的概率越大，即路径概率选择机制；（2）路径越短，在上面的信息素踪迹增长得越快，即信息素更新机制。蚂蚁之间通过信息素进行通信，即协同工作机制。
作为分布智能体的蚂蚁，除了能根据信息素轨迹的指引进行寻优外，还能充分利用基于问题的启发式信息。另外，蚁群优化算法还有两个重要的机制，信息素挥发（Pheromone Trail Evaporation）和后台行为（Daemon Actions）。遗忘（Forgeting）是一种高级的智能行为，作为遗忘的一种形式，路径上的信息素随着时间不断变化，将驱使蚂蚁探索解空间中新的领域，从而避免求解过程过早地收敛于局部最优解。后台行为包括邻域（局部）搜索（Local Search）过程及问题全局信息的收集。蚁群优化是一种基于种群的构造型自然启发式优化方法，这种构造性（Constructive）方法如果与改进型（Improvement）迭代方法，如邻域搜索、禁忌搜索等相结合，能得到更好的优化结果。此外，通过在解构造过程中动态收集基于问题本身的启发式信息，将引导蚁群在高质量的问题空间中进行精细的搜索，从而获得更好的解。
算法的主要步骤可描述如下。
1）设置参数，初始化信息素踪迹和启发式信息。
2）判断算法收敛准则是否满足，若满足则输出优化结果，否则重复下述操作。
（1）对蚁群中的每只蚂蚁，重复下述操作。
对每个解构造步，重复下述操作：① 按照信息素和启发式信息的指引构造一步问题的解；② 进行信息素局部更新（可选）。
（2）进行后台操作，如近邻搜索、禁忌搜索（可选）。
（3）根据已获取的解的质量进行全局信息素更新。
自从Dorigo等人提出第一个ACO算法，即AS（Ant System）算法后，许多学者对就如何改进基本ACO算法进行了大量的研究，如基于蚂蚁等级的ASrank，引入了Q-学习机制的Ant-Q，采用伪随机比例规则的ACS，将信息限制在一定的范围内并使用了信息素平滑机制的最大最小蚁群算法MMAS等。国内的学者针对提高ACO算法的性能也展开了大量有益的工作，如吴庆洪等人从遗传算法中变异算子的作用得到启发，在蚁群算法中采用了逆转变异机制，进而提出了一种具有变异特征的蚁群算法，这是国内学者对蚁群算法所做的最早改进。张纪会等人提出了自适应的蚁群算法，采用确定性选择和随机选择相结合的策略，在搜索的过程中动态地调整选择的概率，实现了选择概率的自适应，提高了算法的收敛速度和性能。吴斌和史忠植首先在蚁群算法的基础上提出了相遇算法，提高了蚁群算法蚂蚁一次周游的解的质量。陈峻、沈洁和秦岭等人提出基于分布均匀度的自适应群算法，该算法根据优化过程中解的分布均匀度，自适应地调整路径选择概率的确定策略和信息量更新策略。朱庆保和杨志军提出基于变异和动态信息素更新的蚁群优化算法，该算法针对TSP问题提出了三种策略，即最近节点选择策略、信息素动态更新策略和最优个体变异策略，大大提高了ACO算法求解TSP问题的能力。