今天我们接续昨天的话题，继续来聊聊AI领域里面比较有趣的一些演算法。

蚂蚁演算法 (Ant Colony Optimization, ACO）

如同我们昨天所聊到的，AI里面有许多演算法都是模拟自然界的生物特性所发展出来的，蚂蚁演算法顾名思义，就是模拟自然界里蚂蚁的习性所衍生出来的演算法。如果要讲的比较精确一点的话，
蚂蚁系统 (Ant System, AS)
是最早被提出来的模型，而蚂蚁系统的理论也是现在其他蚂蚁演算法的基础。
而
蚂蚁演算法 (Ant Colony Optimization, ACO）
则是目前应用较为广泛的演算法。

那麽蚂蚁演算法模拟的部份是什麽呢?
自然界中的蚂蚁在外出找寻食物的时候，会在走过得路径上留下一种叫做 费洛蒙(Pheromone) 的物质，而费洛蒙可以帮助後面的蚂蚁来决定是否要依循着前面蚂蚁留下的费洛蒙继续前进。
想像一群蚂蚁出门寻找食物的时候，先遣的蚂蚁们是漫无目的且随机的选择移动的路径并且沿路留下费落蒙，而後续出发的蚂蚁遇到前蚁留下来的费落蒙时，会选择：

1. 对哇造！ 蚂蚁选择跟着走，并且也留下自己的费洛蒙。
   这麽一来这条路径的费洛蒙的浓度就会因此增加。
   

2. 蚂蚁一定要靠自己！ 蚂蚁选择自己找寻没有费洛蒙的路径，并留下新的费洛蒙。
   如此一来原本有前蚁费洛蒙的路径上，费洛蒙浓度将随着时间而挥发减少。
   

而这些找寻食物的路径上，越短的路径能够让蚂蚁越快的往返於巢穴与食物之间，因此这些较短(通常也意味着较好)的路径上自然而然的会留下浓度越高的费洛蒙，并吸引更多的蚂蚁照着这条路径去搬运食物。

图源: 动物星球频道(台湾)
不懂梗的请参考这里

因此这样的特性，让蚂蚁演算法可以很好的运用在寻找问题最佳解的应用上，特别是在於寻找最短路径上的一些问题。

爬山法 (Hill Climbing)

爬山法是一种区域性搜寻的演算法，他的优点是简单快速且容易实作，然而缺点也很明显，就是它很容易卡在相对高点的解而非全域的最佳解。

不太好理解的话没有关系，我们来看下面的说明：
爬山法的概念为，
每次都以"当下的位子状态"，并且去估算"所有邻居的状态"後，往最佳的方向移动。
例如今天我们有一个5乘5的区域，每一个区域里为1~25的任一数字(不重复出现)，而每次移动的规则为附近九宫格的一格，目标是找到最大的数字。

假设我们的初始位子从最右下方的 11开始，此时他的邻居为九宫格内可以到达的数字，分别为12、15以及8，此时依照目标我们选择最大的15来移动。
接下来我们的位子改成从15开始来做搜寻，在这个时候邻居改成周围九宫格里的13、21、2、7、12、19、8以及11，那麽我们一样依照目标选择最大的21来移动成为新的起始点。
而接着我们从21做搜寻的时候，附近的邻居为25、4、18、13、2、7、15以及12，到此我们选择最大的25成为新的起点。
接着在25开始，我们可以看到周围的邻居已经没有比自己还要大的数字了，则演算法结束，25为我们找到的解 (同时也是最佳解)。

爬山法虽然快又有效，但就如同前面所提到的缺点，爬山法很容易卡在相对高点的解而非全域的最佳解。.
上面举的例子可以想像成是最佳情况，假设今天我们选的起点为左中下的3，那麽在经过第一次搜寻并且移动後，就会来到相对於附近已经是最佳解的22并停止搜寻，也就是只有找到相对於自己邻居中最佳的解而非整个25宫格里面的全域的最佳解 25。
甚至更惨一点的情况，我们从正下方的19开始当作起点，此时由於已经在相对高点了，因此搜寻结束并且回报19为最佳解。

我们从这张图来看的话：

图源

如果想要找到全域最佳解 (Global maximum)，那麽你起始搜寻的位置必须得在最高点位左方shoulder到右边最低点位之间才有机会，否则的话根据爬山法的机制，只要移动到任何一个平坦处 (如图右边的flat local maximum)或是相对高点 (如图中间的Local maximum)，则结束搜寻并且只能得到局部最佳解。

当然後续也有许多对於爬山法所作的改良，例如：
在爬山的过程中加入一些随机性、改变爬山搜寻时的策略、更多元化且多次的重新设定起始点来做搜寻等等，这些细节在这边我们就不多谈了。

不小心又打了三千五百多个字...
我们明天继续 (或是停刊放弃)