7.2.2　人工免疫算法

7.2.2　人工免疫算法

人工免疫算法(Artificial Immune Algorithm,AIA)是模仿生物免疫机制,结合基因的进化机理,人工构造出的一种新型智能优化算法。它具有一般免疫系统的特征,采用群体搜索策略,通过迭代计算,最终以较大的概率得到问题的最优解。相较于其他算法,免疫算法利用自身产生多样性和维持机制的特点,保证了种群的多样性,克服了一般寻优过程(特别是多峰值的寻优过程)中不可避免的“早熟”问题,可以求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。

1.编码策略设计

在测试用例优先排序问题中,输入为测试用例集T,抗体个体为一个测试用例序列。本书将测试用例集的不同序列作为抗体的编码,放入免疫算法中,即为每一个测试用例编一个序号,不同顺序组成的序列作为一个抗体的编码。假设测试用例集为T={t 1,t 2,…,tn},则其中一个抗体个体的编码如图7-1所示。

图7-1　抗体个体编码示意图

2.亲和度函数设计

亲和度表征免疫细胞与抗原的结合强度,与遗传算法中的适应度类似。亲和度的评价与问题具体相关,针对不同的优化问题,应该在理解问题实质的前提下,根据问题的特点定义亲和度评价函数。通常函数优化问题可以用函数值或对函数值的简单处理(如取倒数、相反数等)作为亲和度评价,而对于组合优化问题或应用中更为复杂的优化问题,则需要具体问题具体分析[1]。

在本书中亲和力则可以评价抗体个体与最优解之间的相似度,这在免疫系统中是用来衡量抗原和抗体之间的匹配程度的函数。本书将每个测试用例序列对应的APSC作为生物的亲和度指标,APSC越接近1,说明生物亲和度越高,该测试用例序列越接近最优解。

3.抗体浓度设计

抗体浓度(den(x):S-＞[0,1])表征抗体种群的多样性好坏,抗体浓度过高意味着种群中非常类似的个体大量存在,则寻优搜索会集中于可行解区间的一个区域,不利于全局优化。因此,优化算法中应对浓度过高的个体进行抑制,保证个体的多样性[1]。

本书中抗体个体为测试用例集序列编码,所以采用抗体之间的海明距离作为抗体-抗体之间亲和度的判定方式,海明距离的计算公式为

其中,在本书中,将两个抗体之间编码的相似程度作为海明距离的计算方式,∂k的定义为(https://www.daowen.com)

在抗体种群中,两个抗体个体的编码相似度越高,海明距离越大,抗体浓度越高。

4.抗体激励度设计

抗体激励度是指抗体种群中抗体应答抗原和被其他抗体激活的综合能力,主要受亲和度和浓度影响,与亲和度成正比,与浓度成反比[1]。本书中利用抗体亲和度和抗体浓度评价结果进行简单的数学运算得到抗体激励度,如式(7-22)所示:

其中,act(ab i)为抗体ab i的激励度,a和b是常量。

5.基于AIA的测试用例优先级排序优化算法流程

本书基于人工免疫算法提出的测试用例优先级排序优化算法如算法7-1所示。

在上述算法中,第1行代表输入;第2、3行代表初始化算法参数和抗体种群;第4行代表对种群中的每一个可行解进行亲和度评价,得到当前种群中亲和度的最大值aff_max及其对应的抗体个体best;第5~28行代表进行抗体种群迭代寻优,其中的免疫处理方法有免疫选择、克隆、变异和克隆抑制等;第29行代表进行结果后处理及可视化。

本书的免疫处理部分针对智能终端测试用例优先级排序问题做了相应的改变,具体如算法7-2所示。

在上述算法中,第1~3行代表算法的输入、输出;第4~9行代表对当前抗体种群进行免疫选择;第10~26行代表对抗体种群进行免疫克隆选择。