1. 蚁狮算法简介
（以下描述，均不是学术用语，仅供大家快乐的阅读）
蚁狮是一种昆虫，城里长大的我没有见过这玩意儿，请教了农村长大小的伙伴，依然没见过，这玩意儿可能在我们生活的地方分布较少。
（图片及介绍来自百度百科）
蚁狮算法(Ant Lion Optimization)是根据蚁狮挖制漏斗状陷阱进行捕食蚂蚁的过程提出的优化算法。算法提出于2015年（2014年末），也是一个比较新的算法，不过好像相关的论文也比较多了。算法的过程和操作步骤比较简单，算法的效果却出乎意料的好，不过算法的实现与蚁狮的行为不是很匹配，但这也不会影响我们的理解。
蚁狮算法中，每个蚁狮以及蚂蚁的位置表示解空间中的一个可行解。蚂蚁在选择一个蚁狮，在其陷阱范围内进行随机游走（random walk）。蚁狮会吃掉陷阱范围内位置最优的个体（取代其位置）。
可以看出算法的主要步骤很简单，不过其具体实现与捕食过程还是有些许不同，当然蚂蚁也不可能会自愿的围绕蚁狮的陷阱为中心进行随机游走。具体的算法将在下一节中详细描述。
2. 算法流程
蚁狮算法中有两种角色，蚁狮和蚂蚁，其数量均为N, 其位置为 ，其适应度值为F(x) 。为了方便描述，下面使用X_AL表示蚁狮的位置，X_A表示蚂蚁的位置。
初始化时，会在解空间内随机初始化N个蚁狮以及N个蚂蚁，下面是其迭代步骤。
整个算法的流程大致可以分为四步：
1. 蚂蚁选择目标蚁狮陷阱。（自投罗网，说吧，你是选择清蒸还是红烧）
2. 计算陷阱的放缩比例。
3. 蚂蚁随机游走。
4. 蚁狮移动到指定蚂蚁的位置。
2.1蚂蚁选择目标蚁狮
每一只蚂蚁都要选择一个目标蚁狮来进行后续的随机游走，选择过程可以随机选择也可以使用轮盘赌的方式进行选择，具体的实现比较简单，不在赘述。（轮盘赌参见遗传算法）。
2.2计算陷阱的比例
该步骤计算陷阱（相对搜索空间）的大小，用于下一步中确定蚂蚁随机游走后的位置。
论文中，陷阱的大小与个体无关，只与当前迭代次数有关，其计算公式如下：
其中t为当前迭代次数，T为最大迭代次数。可以看出这是一个分段函数，我们看看它的图像。
从图像可以看出，在迭代的末期，比例会变得很大，但是该值是用作分母，所以随着迭代次数增加，陷阱范围越来越小。
2.3蚂蚁随机游走
蚂蚁的随机游走是蚁狮算法的核心，在介绍之前先看看random walk的定义及图像。
2.3.1随机游走
定义函数rw如下：
其中r为0-1内的均匀随机数。
随机游走函数RW定义如下：
即t个rw随机数之和。明显可知-t<=RW(t)<=t。
看看RW(100)的图像，
从图像可以看出，虽然函数的期望为0，但其曲线还是比较曲折的，有偏向正数的曲线，有偏向负数的曲线，也有在0值上下波动的曲线。总而言之，随机游走的曲线的随机性还是比较大的，这也为算法提供了随机搜索能力。
2.3.2计算蚂蚁随机游走相对值
下面要将随机游走转换为蚂蚁的随机游走。
第i个蚂蚁的在第t代时随机游走的值为RW_i(t),则RW_i(t+1)=RW_i(t)+rw。
第t代群体中随机游走的最大值为Max(RW(t)),最小值为Min(RW(T))。
定义ARW_i(t)为第i个蚂蚁在第t代随机游走过程的相对位置，其计算公式如下：
可以看出ARW是一个取值范围为0-1的数，即将这N个蚂蚁的随机游走值归一化到0-1范围内，再做进一步计算。
2.3.3计算蚁狮陷阱范围
该蚂蚁选定第k个蚁狮作为自己的目标蚁狮，由上一步计算出的比例ratio可以计算出该蚁狮所在陷阱的范围trap。
其中
2.3.4计算蚂蚁的位置
蚂蚁会围绕自己所选择的蚁狮做随机游走，最终，蚂蚁会停留在该蚁狮的陷阱范围内。蚂蚁位置的计算公式如下：
可以看出第i个蚂蚁位置在它所选择的蚁狮的陷阱内，具体的位置由它随机游走结果在群体中的相对位置决定。
除此之外，该蚂蚁还会向着全局最优的蚁狮个体进行随机游走，最后会停留在这两个位置的中点处。
以上，蚁狮算法中随机游走部分就结束了。看上去很复杂，但是理解之后还是很简单的，大致分为两步：
1. 蚂蚁选择蚁狮，通过陷阱确定自己的大致位置。
2. 蚂蚁根据随机游走在种群中的相对位置，确定自己在陷阱中的精确位置。
2.4蚁狮移动到指定蚂蚁的位置
该步骤也是较为简单的步骤，其实现与描述相差较大。具体实现为在这N个蚁狮以及N个蚂蚁一共2N个个体中，选择较好的N个个体作为蚁狮。注意，只是选择了N个蚁狮，原蚁狮若未被选中则不复存在，但原蚂蚁依然存在，只是新蚁狮和原蚂蚁位置重叠了。该实现方式是原文代码的实现，其实大家想怎么实现都可以，算法的鲁棒性很强，不会因为这些细微的改动而变差。
2.5算法步骤
可以看出蚁狮算法的整体流程还是比较简单的，虽然随机游走部分公式较多，但是只要知道其含义还是比较容易理解的。
3.实验
适应度函数。
实验一：
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| 选择蚁狮方式 | 轮盘赌 |
| 值 | |
|---|---|
| 最优值 | 3.8900618299208255E-10 |
| 最差值 | 3.105985890779366E-7 |
| 平均值 | 6.142564495109296E-8 |
从结果可以看出，蚁狮算法的效果非常好。从图像可以看出，算法的收敛速度也是非常之快，在3-4代之后群体就收敛到了一个相对集中的位置。不过我们可以看到算法的ratio的实现，应该是在最后的10%代才进行小范围搜索，而图像可以看出3-4代就收敛了，可能与轮盘赌选择有关。虽然结果很，收敛过快容易陷入局部最优，但这也可能是该适应度函数太简单的缘故。
实验二：
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| 选择蚁狮方式 | 随机选择 |
| 值 | |
|---|---|
| 最优值 | 5.652087288375292E-10 |
| 最差值 | 5.641551352947513E-7 |
| 平均值 | 7.520606013312168E-8 |
图像和结果与实验一并没有太大的差别，收敛的依然很快。蚂蚁选择蚁狮方式对结果的影响不太大。看来应该是蚁狮选择蚂蚁的方式对种群造成的影响，步骤2.4中可以看出，算法没有使用贪心算法，而是选择在2N个个体中选择前N个个体。这种方式向着最优个体收敛的速度应该快于普通的贪心算法。（普通的贪心算法，如果蚂蚁随机游走到的位置由于蚁狮，则蚁狮移动到该位置）。
实验三： 使用贪心算法移动蚁狮
| 值 | |
|---|---|
| 问题维度(维度) | 2 |
| 总群数量(种群数) | 20 |
| 最大迭代次数 | 50 |
| 取值范围 | （-100，100） |
| 实验次数 | 10 |
| 选择蚁狮方式 | 随机选择 |
| 值 | |
|---|---|
| 最优值 | 3.1748247992028467E-9 |
| 最差值 | 5.054159478342528E-7 |
| 平均值 | 6.544495515254065E-8 |
从图像看可知，种群的收敛速度没有之前那么快了，结果也与实验一和实验二相差不大。故可知，算法的快速收敛主要由其蚁狮移动的方式决定。改为贪心算法后，收敛速度慢了一点，总体而言差别不大。
4.总结
蚁狮算法是根据蚁狮使用陷阱捕食随机游走的蚂蚁而提出的算法。不过其核心确实蚂蚁的随机游走。原文的描述时将所有的流程融合为了一个公式，理解不易，本文中将其分步分解后可以明显的看出其公式的含义。算法的性能不错，鲁棒性也较强，对其操作步骤的简单修改对其效果的影响不太大。
算法中随机游走过程为算法提供了不错的搜索能力，而陷阱的比例则决定了其搜索范围，是局部搜索还是全局搜索，蚁狮的移动方式决定了种群的收敛速度。总体来看，对于平滑的局部最优较少的函数，算法能得到非常好的效果，在其他问题上也有不错的结果。
参考文献
Mirjalili, Seyedali. The Ant Lion Optimizer[J]. Advances in Engineering Software, 2015, 83:80-98. 提取码：lyrw
官网(有代码)http://www.alimirjalili.com/ALO.html
官网代码备份，防wall防丢 提取码：fg1j
以下指标纯属个人yy,仅供参考
| 指标 | 星数 |
|---|---|
| 复杂度 | ★★★☆☆☆☆☆☆☆ |
| 收敛速度 | ★★★★★★★★★☆ |
| 全局搜索 | ★★★★★★★☆☆☆ |
| 局部搜索 | ★★★★★★☆☆☆ |
| 优化性能 | ★★★★★★☆☆☆☆ |
| 跳出局部最优 | ★☆☆☆☆☆☆☆☆☆ |
| 改进点 | ★★★★☆☆☆☆☆☆ |
网友评论