认真聊AI | 群智能算法

原创内容

No.711

认真聊AI | 群智能算法

人类最有意思的一点就在于总能从自然界找到各种各样的参考并应用。

图片由海艺AI绘制

受自然界生物界各种各样的规律启迪，人们根据其原理设计了很多求解问题的算法。比如蚂蚁搬家、鸟群觅食、蜜蜂筑巢等等，这些现象不止是生物学家沉迷其中，计算机学家也相当痴迷。

群智能的工作原理基于自然界中生物群体的自组织行为。在没有中央指挥的情况下，个体通过遵循简单的规则和局部信息交流，相互协作以实现复杂任务的解决。例如，蚂蚁寻找食物时会释放信息素，其他蚂蚁通过感知这些信息素的浓度来选择路径，随着更多蚂蚁选择较短的路径，信息素的正反馈效应使得最优路径得到加强。

我们把由简单个体组成的群落与环境以及个体之间的互动行为称作群智能，而这种受动物群体智能启发的算法则称为群智能算法。

在计算机领域，群智能算法包括粒子群优化算法，蚁群算法、人工免疫算法等。遗传算法等进化算法本质上也是一种群智能算法，都是受自然现象的启发，基于抽取出的简单自然规则而发展出的计算模型。

遗传算法的起源可以追溯到20世纪60年代初期，20世纪80年代后，遗传算法进入兴盛发展时期，被广泛应用于自动控制、生产计划、图像处理、机器人等研究领域。

遗传算法总的来说理解起来有点困难，我还是研究了一段时间的。总的来说遗传算法就是人们在解决一些问题的时候参考了自然界生物遗传与进化的机理，对这些机理进行模仿的算法。比如自动控制、生产计划、图像处理等等领域，人们参考自然界生物进化的模式做出了解答。

既然是参考了自然界的生物进化，那我们先来说说自然界的生物进化，也就是适者生存，优胜劣汰：一个种群作为起点，经过竞争后，一部分个体被淘汰而无法再次进入循环圈，而另一部分则进入种群，适应度高的个体只是进入种群的概率大，而不是一段会进入种群，而适应度低的个体进入种群的概率低而不是不会进入种群。此外，在繁衍的过程中，基因还有一定的概率发生变异，使得种群有了进化的可能。

虽然人们针对不同问题设计了许多不同的编码方法来表示问题的可行解，产生了不同的遗传算子构成了各种不同的遗传算法。但这些遗传算法还是有一些共同点的，Goldberg总结出了基本遗传算法（simple genetic algorithms，SGA），该算法只使用选择算子、交叉算子、变异算子三种基本的遗传算子，给各种遗传算法提供了一个基本框架。

遗传算法包含五个基本要素，即参数编码、初始群体设定、适应度函数的设计、遗传操作设计和控制参数设计。

比如我们在解决流水车间调度问题的最短的最优解(推荐大家看B站UP主lvqaq的数学建模的视频，我自己看书是一点都没看懂，但是看UP的视频我看懂了)的时候，就可以参考自然界生物进化的规律，把一个可行的工序作为初代全体，然后把总耗时作为进化的目标，做模型让工序繁衍子代（用算法模拟），然后就能在一代代的进化中拿到最优解（至少是比较好的解）。

总的来说，遗传算法就是这么个过程：

总而言之，遗传算法在理解上还是有一点难度的，难度主要在于把显示的问题当作生物种群的时候，一开始想明白有点困难，需要多看几个案例才能完全理解。

粒子群优化算法是另一种受自然界启发的算法，这里主要是参考了鸟群在飞行的过程中总能保持惊人的排列和同步的特性。我们把飞行的鸟群假设成一堆在移动的粒子，那么鸟群飞行就可以抽象出一个粒子移动的模型。

在这个模型中，需要的参数就比遗传算法多很多，比如群体规模m，惯性权重w，加速度V1\V2，最大速度Vmax、最大代数Gmax。

类似遗传算法，粒子群算法也是先初始化每个粒子，然后对粒子做出适应度评价，计算每个粒子的适应度，然后选定每个粒子的最好位置，设置一个最终只检查条件，如果不符合就继续迭代。

粒子群优化算法在解决车辆路径问题（配送中心有K辆车L客户，求运输成本最小这种）上有比较多的应用。计算结果和遗传算法类似，可能得不到最优解，但是能得到一个比较好的解。

蚁群算法是一种基于蚂蚁在觅食时总能找到洞穴和食物之间最佳路径的生物本能而来的一种算法。

蚁群在觅食的时候存在着信息素追踪和信息素遗留两种行为，也就是说蚂蚁在选择路线的时候有一定概率沿着信息素密集度比较高的路径觅食，并在走过的范围内继续释放信息素。当一条路上的信息素越多时，后来的蚂蚁选择这条路的概率也就越大。这种过程我们称为蚂蚁的自催化过程，因为这个原理是一种正向反馈机制，所以蚂蚁系统也被称为增强学习系统。

蚁群算法的经典应用就是旅行商人问题，假设有一个旅行商人要拜访n个城市，他必须选择一条经过每个城市恰好一次并最终返回出发城市的路线。目标是使这条路线的总长度（或总成本，如时间、费用等）最小。

模型的公式在微信上敲出来比较费劲，直接放个图出来：

对蚁群算法而言，有两个比较关键的因子，一个是信息素启发因子，另一个是期望值启发因子。当信息素启发因子偏大时，蚂蚁选择走以前的路的概率更大，算法会过早陷入局部最优；当期望值启发因子越大时，蚂蚁在某个局部点上选择局部最优解的概率越大，也是容易陷入局部最优的，也就是说，对蚁群算法而言，设置参数还是很重要的。

虽然遗传算法、群粒子算法和蚁群算法看起来公式完全不一样，但是核心思路还是比较类似的，除了都是模仿了自然界的生物本能之外，在逻辑上也有类似的地方。

这三种算法都有一点穷举的意味在里面：我们先给一个可行解或者随机点，然后计算一下目标值，接下来对一些参数进行调整（比如交叉变异），再算一下目标值，将每一次计算中的一些我们倾向的结果作为下一次计算的输入，这样反复迭代很多次之后就能得到一个我们比较想要的结果了。

也就是说，对于群智能算法，不一定能得到最优解，但是一定可以得到一个比较好的解。对于群智能算法而言，关键的地方在于如何保证算法的收敛效率和避免陷入局部最优，这大概就是算法工程师们常说的玄学调参吧。