解决数学问题必须用脑子？蚂蚁第一个不服！
正文共2594字，预计阅读时间约为8分钟
也可点击本篇推文音频，用耳朵聆听知识~
你小时候观察过蚂蚁搬运食物吗？吃饭时手里留一点米饭，吃完跑下楼撒在草丛旁，过一阵子，就有一排来来回回搬运食物的蚂蚁。好奇的你看着它们，经常一蹲就是半天。
但你有没有想过，蚂蚁是怎么走过石头和草丛的“千山万水”，找到你撒的米粒？它们又是如何找到蚁穴和米饭之间最近的路的？科学家正是受到蚁群觅食的启发，为货运路线、网络路由等问题找到了更好的解决方案。让我们跟着一只蚂蚁的脚步，一起了解一下吧！
想找到路？喷点“香水”
今天，蚂蚁“大强”的工作是出门找食物，可它没有手机导航APP，只能随便逛。为了能找到回家的路，它一路走一路喷香水。
今天蚂蚁大强的运气真好，发现了几颗白米粒，貌似还是熟的。可大强遇到一个难题，米粒对它而言太大了，它背不动，需要回家搬外援。于是，大强沿着有香水的路线回到蚁穴，把这个好消息告诉自己的兄弟姐妹。
一群蚂蚁浩浩荡荡地出发了，可有少部分蚂蚁“不走寻常路”，就不走大强喷过香水的路，非要自己找更近的路。当然，无论走什么路，每只蚂蚁都会喷香水，以便记住自己走过的路。
香水会挥发，味道会逐渐变淡，但是后续的蚂蚁会补充香水。不难想象，距离米饭越近，路程越短，蚂蚁补充香水的频率也就越高，那么这条路上香水味就会越浓。
于是乎，越来越多的蚂蚁走在距离米饭更近的路上，蚁群速度也更快。当然，还是有少量蚂蚁“不走寻常路”，但如果它们发现了一条更近的路，那么重复上面的步骤，蚁群会逐渐向这条新的路上聚集。
越近的路上，蚂蚁越多
在上述过程中，蚂蚁没有人类世界的“香水”，但它会释放一种叫做“信息素”的物质。这种物质只有蚂蚁能够闻到，且易挥发，蚂蚁完全按照信息素的指引回巢。
当你用樟脑丸（不知道00后读者见过吗？）画一个圆，将蚂蚁圈进去，那么蚂蚁会绕那个圆运动，直到樟脑的味道挥发得差不多。这是因为樟脑覆盖了信息素，蚂蚁就找不到回巢的路了。
信息素被“中断”
由“干饭”衍生出的蚁群算法
意大利学者Marco Dorigo将上述蚁群觅食行为归纳为：
（1）随机感知
蚂蚁在最初寻找食物时，是随机移动的，而且它的感知范围是有限的。一般来说，一只蚂蚁只能感知到一个方格世界，它自己是方格的中心。另外，最初不止一个蚂蚁寻找食物，每一个蚂蚁觅食的方向是互不影响的。
（2）环境留痕
蚂蚁会在走过的路径上留下信息素，后续会按照信息素的指向回巢。所有的蚂蚁释放的信息素是相同的，这意味着一个蚂蚁可以识别出另一个蚂蚁的信息素。
（3）觅食移动
一只蚂蚁在移动的过程中，如果感知不到任何食物或信息素，那它就完全随机地选择前进方向；如果感知到食物，那它就会直接走向食物；如果感知到信息素，那它会以一定的概率选择以此作为前进方向，信息素越浓的方向，概率越大。但即使完全没有信息素的方向，概率也不为0。
（4）随机避障
当蚂蚁遇到障碍物（草丛、石头等）时，它会随机选择一个方向绕路。如果某个方向的信息素更浓，那它选择这条路的概率更大。
（5）信息素挥发
信息素会随时间挥发，味道会随着变淡。但是，如果有蚂蚁路过，那它会加深信息素的浓度。相同时间内，路过的蚂蚁越多，那信息素就会越浓。
然后，Marco Dorigo用计算机模拟了蚁群行为，实现了蚁群算法（Ant Colony Optimization, ACO），其流程如下：
步骤1：在空间的起点处随机产生若干“个体”，令它们在空间上随机移动，且它们之间互不影响；
步骤2：若某“个体”找到目标，则选择某个方向返回起点，而各方向信息素越浓，概率也越大。另外，没有信息素的方向概率也不为0。这里，信息素=信息素×挥发系数（小于1）。一旦它返回到起点，就令其余的个体开始随机运动；
步骤3：一旦“个体”遇到障碍物，随机选择一个方向绕路。信息素越浓的路径，概率越大；
步骤4：对每一个“个体”走过的方格（空间的最小单位），信息素+1；
步骤5：当经历的时间达到一定数值时，或者满足一定条件时，停止算法。
最后，信息素最浓，因此拥有最多“个体”的路径，就被认为是空间里从“起点”到“目标”最短的路径。
蚁群算法的流程图
旅行、快递、上网…都能用到
蚂蚁也没想到，自己只是想找点吃的，就被科学家研究出了个算法。那么，蚁群算法具体能做什么呢？最初，它被用于解决旅行社问题：如果一个旅客，想要走遍一系列的城市，什么路线才是最近的呢？这个问题分为两种情况：
（1）不返回原点：只考虑起点到终点的路径，无需从终点再返回起点
例如，如果你想坐高铁从西安到西双版纳，高铁必须从一个城市到另一个城市，铁道系统如何判断什么路线用时最短呢？
最“笨拙”的方法是“枚举法”，即列举从西安到西双版纳所有可能的路线，甚至包括西安-…-乌鲁木齐-…-西双版纳，然后选出用时最短的线路。
枚举法包括大量明显不合理的选项
不难看出，这种方法面临着组合爆炸问题，即可能的路径过多，因此带来了巨大的计算负担。且如果旅客要求必须到昆明中转（想尝尝昆明的鲜花饼），那么可能的路径会更多，计算负担更重。
另一种“聪明”的方法是“动态规划法”，依旧以从“西安到西双版纳”的高铁线路为例，但我们要求一定要途径昆明。
先说结论：“西安-昆明-西双版纳”的最短路线，一定是“西安-昆明”的最短路径（路径1）+“昆明-西双版纳”的最短路径（路径1）。为什么呢？因为（反证法）：
如果路径1+路径2不是“西安-西双版纳”（必须途径昆明）的最短路径
（可证）
路径1和路径2中至少有一条不是最短的
（可证）
假设错误，因此路径1+路径2一定是“西安-西双版纳”（必须途径昆明）的最短路径
应用相同的原理，可得：如果我们得到“西安-西双版纳”必须途径的城市，例如达州、成都、昆明，那么我们就能把问题变为“西安-达州”+“达州-成都”+“成都-昆明”+“昆明-西双版纳”的最短路径，而每一段路径又可以继续细分…
这样，就解决了“西安到西双版纳”的最短高铁线路问题。假如路径上有15个必经的城市，“枚举法”的计算量差不多是“动态规划法”的一万亿倍！
（2）返回原点：从起点到终点，还要由终点返回起点
还有一种更具代表性的旅行商问题，那就是计划要走遍多个城市，每个城市必须拜访且只能拜访一次，而最终要回到起点，那么什么路线才是最短的？
若用“枚举法”解决这个问题，那计算量过大，计算机难以承受；而这个问题又无法应用“动态规划法”。这时，就可以求助于蚁群算法：
规定每只“蚂蚁”必须拜访每个城市，且只能拜访一次，最终要回到起点。算法执行若干次后，信息素浓度最高，也就是“蚂蚁”最多的路径，就是最短的路径。
举例来讲，若上述旅行商问题中存在31个城市，我们创造100只“蚂蚁”，蚁群算法执行200次，最终输出的最短路线为
第1-第200次执行算法时，所有蚁群路径的最短距离和平均距离分别为
可以看出，蚁群逐渐“聚集到”我们想要的最短路径。而计算机得到这个答案只花费了2.6秒。
如果将这些城市替换为快递车辆的节点，例如仓库、中转站、配送中心等，那么就得到了货运车辆的最优路线，使你的快递能最快到达你手里。
如果将这些城市替换为无线网络的节点，例如服务器、路由器、网关等，那么就得到了网络路由的最优路线，使你看科普文、刷抖音不卡顿。
给我们的启发是……
单个蚂蚁的行为规则比较简单，能力也极其有限。但是，通过某种信息传递机制，蚁群整体就可以表现出智能的行为，这种现象被称为群智能（Swarm Intelligence）。
因此，若想让我们的社会变得更加智能，一方面是提升自己，但更重要的是，我们应传递质量更高的信息。看到这里，你还不打算转发这篇有质量的科普文么？
作者：望墨溢
作者单位：西北工业大学航海学院
版权说明：未经授权严禁任何形式的媒体转载和摘编，并且严禁转载至微信以外的平台！
文章首发于科学大院，仅代表作者观点，不代表科学大院立场。转载请联系cas@cnic.cn
推荐阅读
大西洋上的天然高速，飞机的... >>
科学大院是中科院官方科普微平台，由中科院科学传播局主办、中国科普博览团队运营，致力于最新科研成果的深度解读、社会热点事件的科学发声。
转载授权、合作、投稿事宜请联系cas@cnic.cn
大院er拍了拍你：不要忘记
点亮这里的 赞 和 在看 噢~