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