6.3.1 蚁狮优化算法
1.蚁狮优化算法描述
蚁狮优化(Ant Lion Optimizer,ALO)算法简称蚁狮算法,模拟了蚁狮和陷阱中的蚂蚁之间的交互,为了模拟这种交互作用,蚂蚁需要在搜索空间中移动,而蚁狮则可以捕猎它们。由于蚂蚁在自然界中寻找食物时是随机移动的,因此选择一个随机行走来模拟蚂蚁的运动:
式中:cumsum计算了累积和;n为最大迭代次数;t表示随机游走的步数(即迭代),r(t)的定义为
式中,rand为[0,1]内服从均匀分布的随机数。
蚂蚁在每一步的优化中都通过随机游走来更新它们的位置。但是,由于每个搜索空间都有一个边界(变量范围),式(6-19)不能直接用于蚂蚁位置的更新。为了使随机游走保持在搜索空间内,使用式(6-19)对其进行归一化:
式中,ai为第i个变量随机游走的最小值,bi是第i个变量随机游走的最大值,
是第t次迭代中第i个变量的最小值,
是第t次迭代中第i个变量的最大值。每次迭代都需要式(6-21),以保证搜索空间内出现随机游走。
蚂蚁的随机游走会受到蚁狮陷阱的影响,如式(6-22)、式(6-23)所示:
式中,ct为第t次迭代中所有变量的最小值,d t为第t次迭代中所有变量的最小值,Antlio
为被选定的第j只蚁狮在第t次迭代中的位置。
通过轮盘赌策略选择某只蚂蚁具体被哪只蚁狮捕食,每只蚂蚁只能被一只蚁狮捕食,而适应度越高的蚁狮捕获蚂蚁的概率越大。通过式(6-24)、式(6-25)模拟这种现象:(https://www.daowen.com)
式中,I为比率。
当蚂蚁的适应度值比蚁狮小时,则认为蚁狮将其捕获,此时蚁狮会根据蚂蚁的位置来更新位置,如式(6-26)所示:
式中,Ant
为第i只蚂蚁在第t次迭代的位置,f为适应度函数。
每次迭代后,选择适应度最好的蚁狮作为精英蚁狮。第t只蚂蚁在第t+1次迭代的位置由式(6-27)确定。
式中,
(l)为蚂蚁在一只由轮盘赌在第t次迭代选择到的蚁狮周围随机游走第l步产生的值,
(l)为蚂蚁在第t代的精英蚁狮周围随机游走第l步产生的值,l为蚂蚁随机游走步数内的任何值。
2.基于ALO算法的测试用例约简算法描述
本书提出的基于ALO算法的测试用例集约简算法如下所示。
在上述算法中,第1~4行为输入;第5、6行为蚁狮算法的基本参数和蚁狮及蚂蚁的初始化位置;第7行为计算蚁狮种群中每一只蚁狮所对应的适应度;第8行为根据适应度对蚁狮种群进行排序;第9行为获取到精英蚁狮及其对应的适应度;第10~20行为对蚁狮种群和蚂蚁种群进行遍历,分别更新蚂蚁种群和蚁狮种群,并进行不断迭代,直到达到最大迭代次数;第21行为对算法后结果进行处理和可视化。
