A.7 粒子群与蚁群优化

1.一群笨个体，凑出聪明集体

前面几章讲的遗传算法、模拟退火，思路都是模仿自然。这一章再讲一类模仿自然的算法，叫群智能。它的核心想法很有意思：一群里头的每个个体其实都很笨，规则简单得很，可一旦它们互相影响起来，整个群体却能表现出找最优的本事。鸟群觅食、蚁群找路，都是现成的例子。

说来也巧，我之前看过一本讲复杂系统的科普书，里面提到，生物学家一开始以为鸟群里有个头鸟在指挥，后来建模才发现，每只鸟无非是跟着身边几只邻居飞、再稍稍靠拢食物多的方向，根本没有什么总指挥，可整群鸟的动作却整齐得像排练过。粒子群和蚁群算法，就是把这种简单规则涌现出集体智慧的现象，拿来解优化问题。

2.粒子群优化PSO：一边记着自己的好去处，一边跟着大部队

粒子群优化（Particle Swarm Optimization，简称PSO）模仿的是鸟群觅食。设想一群鸟在一片区域里找食物，每只鸟就是一个粒子，它在空间里有一个位置，也有一个飞行速度。

每个粒子会记住两样东西。一是自己飞到现在为止去过的最好位置，记作 $p_i$（自身历史最优，下标 $i$ 表示第几个粒子）。二是整个群体目前找到的最好位置，记作 $g$（全局最优）。粒子每一步更新自己的速度时，会同时受这两处吸引，往它们的方向偏。设第 $i$ 个粒子当前的位置是 $x_i$、速度是 $v_i$，速度更新的式子大致是：

$$v_i \leftarrow v_i + c_1 r_1 (p_i - x_i) + c_2 r_2 (g - x_i)$$

这里头 $c_1$ 和 $c_2$ 是两个权重，决定粒子更听自己的经验还是更听群体的经验。$r_1$ 和 $r_2$ 是两个0到1之间的随机数，给运动添一点随机性，免得所有粒子死板地朝一个方向冲。括号里的 $(p_i - x_i)$ 是朝自己最好位置走的那一份，$(g - x_i)$ 是朝群体最好位置走的那一份。更新完速度，再用 $x_i \leftarrow x_i + v_i$ 把位置挪一步，如此反复，整个群体就会慢慢聚拢到比较好的区域。

实际用的时候，常常还往式子最前面加一个惯性权重 $w$，写成 $wv_i$，控制粒子保留多少原来的速度。$w$ 大一点，粒子飞得远、爱往新区域探索。$w$ 小一点，粒子收敛得快、爱在好区域附近细细地抠。常见的做法是让 $w$ 随着迭代慢慢减小，前期多探索、后期多开发，这和模拟退火里慢慢降温是一个心思。这里还有个要留意的现象，叫早熟收敛，就是所有粒子过早地挤到同一个不怎么样的位置上出不来了，通常靠保留较大的惯性、或者周期性地给粒子来一记扰动来解决，思路是别让群体丢掉多样性。

小明第一次接触这个算法时，觉得它特别像他参加过的那种大型寻宝活动：每个人一边记着自己刚才在哪儿找到过线索，一边又忍不住凑到全场呼声最高的地方去，两边一拉扯，大伙儿就渐渐围住了真正的目标。PSO适合连续优化问题，实现起来也比遗传算法简单，不用设计交叉变异，调几个权重就行。

3.蚁群算法ACO：用信息素把好路越走越宽

蚁群算法（Ant Colony Optimization，简称ACO）模仿的是蚂蚁找食。蚂蚁有个天性，走过的地方会留下一点点气味，学名叫信息素，后面的蚂蚁倾向于往信息素浓的路走。妙就妙在，到食物源更短的路上，蚂蚁往返得更快，单位时间里经过的次数更多，信息素积累得也就更浓，于是更多蚂蚁被吸引过去，形成正反馈，最后整群蚂蚁基本都集中在最短的那条路上。

把这个现象写成算法，关键就是信息素的更新。设某条边上的信息素量是 $\tau$，蚂蚁选路时，倾向于信息素浓、而且本身距离短（代价小）的边。具体某只蚂蚁从一点选下一条边的概率，大致正比于：

$$P \propto \tau^{\alpha} \eta^{\beta}$$

这里头 $\eta$ 是启发式信息，通常取距离的倒数，距离越短 $\eta$ 越大。$\alpha$ 和 $\beta$ 是两个权重，调节信息素和距离各自的影响。等一批蚂蚁都走完一趟，再更新信息素：先让所有信息素挥发一点，公式是 $\tau \leftarrow (1-\rho)\tau$，其中 $\rho$ 是挥发率（0到1之间），再加上这趟蚂蚁在自己走过的边上释放的新信息素。挥发是为了让旧的、未必好的路径慢慢被遗忘，避免一开始碰巧走过的烂路把大家一直拴住。

拿旅行商问题（TSP，要找一条走遍所有城市又最短的环线）来说，每只蚂蚁从某座城市出发，按上面那个概率挑下一座城市，一座座走遍所有城市，算出自己这条环线的总长度。一批蚂蚁各走出一条环线，走完一起更新信息素，环线越短的，沿路释放的信息素越多。这样一轮轮跑下去，信息素会越来越集中到短的环线上，最终收敛到一个相当不错的解。

我之前读过一篇讲算法史的随笔，提到早期有人真的拿真实蚂蚁做过实验，在巢穴和食物之间架两根长短不同的桥，结果没多久蚂蚁就全涌到短桥上去了，这个实验后来启发了一整套蚁群算法。

4.PSO和ACO，怎么选

这两种算法各有脾气。PSO偏连续优化，每个粒子就在实数空间里飞，代码简单、调参也少，工程里上手很快。ACO偏离散组合优化，靠信息素积累群体经验，在TSP、排班、路由这类问题上很能打，但跑起来要放出一批批蚂蚁，开销不小，调 $\alpha$、$\beta$、$\rho$ 也需要点经验。

它们的共同点是，都不靠梯度。还记得3.9 节讲的那些优化器吧，它们能奏效，前提是目标函数光滑、能求导。可现实里很多问题，目标要么根本没法求导，要么解空间是离散的、到处是坑，梯度下降派不上用场，这时候就要请这些元启发式出马了。它们靠的是随机加上经验的慢慢积累，虽然不保证找到全局最优，但往往能给一个相当不错的解。

也要提一句，元启发式不是万能钥匙。它们普遍跑得慢、结果有随机性，所以工程上通常会先用简单的办法（比如随机搜索、坐标下降）探个底，确认问题确实需要这类算法，再上群智能。一上来就放蚁群，有时只是徒增开销。

5.收个尾

说到底，梯度下降和这一章讲的元启发式，是在解两类不一样的问题。目标光滑可导的，梯度下降又快又稳，自然是首选。目标棘手、解空间复杂的，就轮到遗传、模拟退火、粒子群、蚁群这些随机搜索的办法上场。小张之前优化一个连解析式都写不出来的黑箱指标，梯度没法算，最后就是靠粒子群一点点试出来的，虽然慢，好歹把指标磨下来了。会按问题的脾气挑工具，这才算把优化这件事摸透了。其实优化这一门，没有哪把钥匙能开所有的锁，多掌握几种思路，遇事才不慌。

练习

Q1. 粒子群优化（PSO）的速度更新 $v_i\leftarrow v_i+c_1r_1(p_i-x_i)+c_2r_2(g-x_i)$ 里，$(p_i-x_i)$ 和 $(g-x_i)$ 分别代表粒子受什么吸引？

$(p_i-x_i)$ 是朝"自身历史最优位置"走的分量，$p_i$ 是这个粒子飞到现在去过的最好位置，体现个体经验；$(g-x_i)$ 是朝"全局最优位置"走的分量，$g$ 是整个群体目前找到的最好位置，体现群体经验。$c_1$、$c_2$ 是两个权重（决定更听自己还是更听群体），$r_1$、$r_2$ 是0到1的随机数添点随机性。粒子同时受这两处吸引，一边记着自己的好去处、一边跟着大部队，慢慢聚拢到比较好的区域。

Q2. 蚁群算法（ACO）里信息素更新为什么要有"挥发"这一步（$\tau\leftarrow(1-\rho)\tau$）？如果没有挥发会怎样？

挥发是为了让旧的、未必好的路径慢慢被遗忘，避免一开始碰巧走过的烂路把大家一直拴住。如果没有挥发，早期某条路径即使不好，只要信息素积累过就永远在那儿，蚂蚁会被一直拴死在上面，没法收敛到更优的路径。挥发率 $\rho$（0到1之间）控制遗忘速度，配合新信息素释放（环线越短释放越多）形成正反馈：短路上往返快、单位时间经过次数多、信息素积累浓，越走越宽；长路信息素挥发多于积累，慢慢被遗忘。

Q3. 易错点：粒子群（PSO）和蚁群（ACO）都是群智能算法，它们能随便互换使用吗？

不能随便换，两者各有擅长的场子。PSO偏连续优化，每个粒子在实数空间里飞，代码简单、调参少（主要调 $c_1$、$c_2$、惯性权重 $w$），工程里上手快，适合连续变量的问题。ACO偏离散组合优化，靠信息素积累群体经验，在TSP、排班、路由这类问题上很能打，但要放出一批批蚂蚁、开销不小，调 $\alpha$、$\beta$、$\rho$ 也需要经验。两者的共同点是不靠梯度（目标函数不可导也能用），但具体选哪个要看问题是连续还是离散、规模多大、对解质量的要求。一上来就放蚁群未必合适，常常先用简单办法探底确认需要这类算法再上。