7.4.4 多目标蝙蝠免疫算法
免疫蝙蝠算法是把生物免疫系统中的多样性和免疫记忆等特性引入蝙蝠算法中,一方面弥补了蝙蝠算法多样性较差的缺点,能够解决传统BAT算法“早熟收敛”的问题;另一方面对人工免疫算法收敛较慢的缺点进行了改善,该算法结合了两种算法的优点,使寻优结果能较好地满足实际要求。
图7-6 人工免疫算法
由于在多目标优化问题中求得的解是一个Pareto最优解集,而不是唯一解,所以要对传统的进化算法进行改进,主要考虑以下两点。
(1)全局最优值的选择
在式(7-28)中,蝙蝠需要通过全局最优值更新速度,但是多目标优化问题的解是解集,因此本书采用小生境技术和轮盘选择法来选择全局最优值,可以保证全局的蝙蝠向Pareto最优解集中密度较小的解收敛,保证了解集的分布。
(2)解集构造方法
每次迭代后,对蝙蝠进行分类,分为支配解集和非支配解集,分别将非支配集中的解依次加入Pareto最优解集中,并在加入过程与Pareto最优解集进行比较判断。如果非支配集中的解支配Pareto最优解集中的解,则将后者从Pareto最优解集删去;如果Pareto最优解集中的解支配非支配集中的解,则不将该解加入Pareto最优解集中;若两个互不支配,则加入Pareto最优解集中。另外由于随着迭代过程,Pareto最优解集不断增加,会对算法的性能产生影响,所以一般会提前设置好Pareto最优解集的容量,当Pareto最优解集超过容量时,就采用小生境技术计算Pareto最优解集中解的适应值,删除最小的部分解,这样可以有效地保证解的分布。
1.蝙蝠编码及更新
(1)蝙蝠的编码方式
每个粒子表示一个测试用例排序序列,采用的编码方式为序列编码,即对于一个包含L个测试用例的测试用例集,每个粒子可以编码为一个长度为L的整数数组,数组中第i项的值表示序列中第i个执行的测试用例序号。
(2)蝙蝠更新策略
在测试用例优先级排序问题中,针对粒子按照测试用例编号序列进行编码,标准蝙蝠算法中的速度和位置更新公式(7-33)不再适用。为此将遗传算法中的交叉操作引入粒子群算法的粒子速度和位置更新操作中,采用单点交叉操作对粒子的速度和位置进行更新[14]。针对本书测试用例排序采用的蝙蝠编码方式,设父蝙蝠为F 1和F 2,要得到子个体B 1和B 2,单点交叉操作的基本流程如下。
步骤1:选取染色体上的一个位置k作为交叉位置,其中k∈{1,…,L},L为蝙蝠个体的编码长度,即测试用例的个数。
步骤2:父蝙蝠F 1的前k个基因遗传作为B 1的第一个基因片段B 1,1。
步骤3:遍历父蝙蝠F 2的基因序列,若该基因存在于子蝙蝠B 1的第一个基因片段中,则删除该基因,遍历完成后得到长度为L-k的第二个基因片段B 1,2。
步骤4:将两个基因片段进行整合得到子蝙蝠B 1。
步骤5:子蝙蝠B 2的基因构造过程同子蝙蝠B 1,算法结束。
这里给出一个蝙蝠更新交叉操作的例子。
假设存在父蝙蝠F 1和F 2,蝙蝠的编码长度L=5,其表现形式如图7-7所示。
图7-7 父蝙蝠的编码
第一步:假设生成交叉位置为k=2,则根据步骤2,得到基因片段B 1,1,如图7-8所示。
图7-8 得到的基因片段
第二步:根据步骤3,依次遍历F 2的基因序列,由于1和3两个基因片段在B 1,1中出现,将其删除,遍历完成后得到基因片段B 1,2,如图7-9所示。
图7-9 删除后得到的基因片段(https://www.daowen.com)
第三步:对基因片段B 1,1和B 1,2进行整合,得到子蝙蝠B 1,如图7-10所示。
图7-10 得到的子蝙蝠B 1
第四步:生成子蝙蝠B 2的操作与B 1类似,得到的B 2如图7-11所示,算法至此结束。
图7-11 得到的子蝙蝠B 2
根据上述的分析研究,得到了蝙蝠速度和位置更新的表达式,所以对式(7-31)~式(7-33)进行更新,具体表现形式如式(7-49)~式(7-51)所示。
其中,randi(x,y)代表随机生成[x,y]区间内一个正整数,cross k(x,y)代表对x和y两个染色体以k为交叉点进行交叉操作。
(3)蝙蝠变异策略
蝙蝠免疫算法包含变异机制,常规的变异方法已经不适用于测试用例优先级排序的问题,所以本书提出基因优化置换操作,其思想是从基因中随机选择一定数目的基因,在后面的基因中随机选择该位置最优的基因进行替换,基因优化置换操作的步骤如下。
步骤1:随机选取一个变异数目k,k∈{0,…,L},L为粒子个体的编码长度,即测试用例的个数。
步骤2:随机选择一个基因,计算该基因前所有基因对测试点的覆盖。
步骤3:根据指定规则选择该基因后面的基因,与该基因进行对比,选择其中对未覆盖的测试点覆盖率/时间消耗最小的基因与选择的基因进行置换。
步骤4:判断迭代次数是否达到变异数目,如果没有,则跳回步骤2;否则输出变异后的基因。
2.算法流程
基于以上分析,可以得出蝙蝠免疫算法的步骤如下。
步骤1:初始化参数,包括蝙蝠种群规模m、迭代次数maxGEN、蝙蝠位置x i(i=1,2,…,m)和速度v i、声波频率f i、声波响度Ai以及频度r i,输入目标函数f(x),设置Pareto最优解集NDSet,初始为空。
步骤2:将蝙蝠分为支配解集和非支配解集,非支配解集中的集加入NDSet,同时设置复制蝙蝠群体得到一个新蝙蝠群体。
步骤3:根据轮盘选择法找出当前种群中的最优蝙蝠位置x*,并根据式(7-49)~式(7-51)对蝙蝠的速度和位置进行更新。
步骤4:开始对蝙蝠进行更新操作,在区间[0,1]上生成随机数rand1,如果rand1＞ri,根据式(7-34)在被选择的全局最优解周围随机生成局部解,否则使用式(7-33)对蝙蝠的位置进行更新。
步骤5:在区间[0,1]上生成随机数rand2,如果rand2＜Ai,这个时候有以下3种可能。
·步骤4中的新解支配原蝙蝠,则更新为新解位置,并使用式(7-36)和式(7-37)减小A i和增大r i。
·原蝙蝠支配步骤4中的新解,则不做任何操作。
·若两者无支配关系,则将新解加入复制的新蝙蝠群体中,更新为新解位置,并使用式(7-36)和式(7-37)减小Ai和增大r i。
步骤6:判断所有蝙蝠的更新操作是否完成,没有则返回步骤4,否则对新蝙蝠群体进行克隆免疫选择操作。
步骤7:判断是否满足最大迭代次数,没有的话跳到步骤4,否则输出NDSet。
