基于模糊遗传算法的嵌入式软件测试数据生成方法

摘要

基于模糊遗传算法的嵌入式软件测试数据生成方法，涉及一种测试数据生成方法。为了解决现有的测试数据生成方法生成的测试数据集规模较大导致的生成时间较长的问题。本发明对遗传算法进行改进，利用模糊控制方法，通过种群熵和离散度自适应地控制遗传过程中遗传算子的选取，在种群多样性变差时增大交叉概率和变异概率，使得种群朝全局最优的方向进化，以缩小测试数据的规模；然后利用蚁群算法对生成的组合测试数据按照较大的离散度进行排序，以增大测试参数相邻测试数据取值间的“距离”，从全部组合测试数据的最优路径排序中选出大离散度的测试数据排序作为最后的嵌入式软件测试数据输出。本发明适用于嵌入式软件测试数据生成。

说明书

技术领域

本发明涉及一种测试数据生成方法。

背景技术

软件的错误通常是由少数几个参数的相互作用导致的，与某些输入参数取值的先后顺 序有关，尤其是当参数取值发生跳变时，更易引起软件错误。研究发现，单个参数引发的 软件错误只占总体的20％-40％，而由两个参数相互作用引发的软件错误可达到总体的 70％，由三个参数引起的软件错误可达到总体的90％左右。随着参数个数的增大，测试数 据的规模及算法复杂程度呈指数增长，因此，两两组合测试技术一直组合测试领域中的研 究热点。

作为一种特殊形式的软件，嵌入式软件具有实时性强、可靠性要求高等特点，因此， 对其进行深入测试尤为必要。将组合软件测试方法应用于嵌入式软件测试，可通过硬件接 口自动注入测试数据、自动获取测试结果，实现嵌入式软件的自动化高覆盖率测试。测试 数据生成是嵌入式软件测试中的重要环节，也是组合测试研究的热点。目前的数据生成方 法主要分为代数构造法、贪心算法和启发式智能算法等。在代数构造法中主要的方法是正 交设计法和TCconfig法；贪心算法主要包括AETG、TCG和IPO等方法；而蚁群算法(Ant  Colony Algorithm)、粒子群群算法(Particle Swarm Optimization)和遗传算法(Genetic  Algorithm)等则属于智能算法。相对于贪心算法，启发式搜索算法能够给出较优的结果， 但是大多数启发式算法需要进行多次矩阵搜索，运行时间较长。

遗传算法在组合测试数据的生成中被广泛应用，但是遗传算法容易陷入局部最优，从 而导致生成的测试数据集规模较大，时间较长。

发明内容

本发明为了解决现有的测试数据生成方法生成的测试数据集规模较大导致的生成时 间较长的问题。

1、基于模糊遗传算法的嵌入式软件测试数据生成方法，包括以下步骤：

嵌入式软件中的一条测试数据T＝(a₁,a₂,...,a_k)即可认为是一条染色体， a_ip∈[0,v_ip-1],(ip＝1,2,...,k)，测试数据T中第ip个参数的取值a_ip认为是染色体上的第ip 个基因，集合v_ip为该基因所属的基因库，k为一条染色体上的基因个数；

设当前已有的测试数据集合为A，未被A覆盖的全部t维交互所组成的集合为Q，即 I是t维交互，H_t嵌入式软件的测试系统全部t维交 互，测试数据T_in中的全部交互，T_in是A中的一条测试数据，其适应值计算函数定义 为：$f\left(T_{\mathrm{in}}\right)=\left|\right\{H_{T_{\mathrm{in}},t}\cap Q\left\}\right|;$

步骤1.1：输入交互维度t，染色体进化代数M_g，染色体组规模N_g；第ip个参数的 取值区间为[0,v_ip-1],1≤ip≤k，k为一条染色体上的基因个数；令当前进化代数m＝0，测 试数据集A＝Φ，未被覆盖t维组合集Q为全部k个参数的t维取值集合；

步骤1.2：初始化染色体组，随机为每一条染色体的基因赋初始值；

步骤1.3：计算每条染色体的适应值，然后按照适应值从小到大进行排序，记为 第i_x条染色体的适应值，i_x∈N_g，生成随机数p∈[0,1]，如果则认为第n条染色体为自然选择的结果，循环N_g次，选择出新的N_g条染色体，作为新的 染色体组；

步骤1.4：对种群N_g的染色体进行随机配对，每一对染色体生成随机数q∈[1,k]，对 q位置的基因按照概率p_c进行交叉，生成新的染色体组；

步骤1.5：对步骤1.4生成新的染色体组中每一条染色体生成随机数q∈[1,k]，对q位 置的基因按照概率p_m进行变异；

步骤1.6：为每一条染色体计算适应值，判断种群最大适应值是否为如果是，进 入步骤1.7；如果不是，则判读m是否等于M_g，如果相等则跳到步骤1.7，否则令m＝m+1， 跳到步骤1.3；

步骤1.7：将适应值最大的染色体放入A，移除Q中已被适应值最大的染色体覆盖的 t维组合，判断Q是否为空，如果为空，则输出A结束，否则跳到步骤1.2；

步骤2.1：输入测试数据集A，蚁群规模M_a，迭代次数N_a；为每一只蚂蚁Ant_H， H∈[1,M_a]，随机设定初始城市的位置，即A中的某条数据；

步骤2.2：依次为每一只蚂蚁选择下一个城市，按照第W只蚂蚁的J_w(i)依次计算转 移概率，按照转移概率由小到大对城市进行排序，随机生成p_a∈[0,1]，计算 当C_R>P_a时，蚂蚁H将选取城市C_R作为所要去的城市；

步骤2.3：判断全部蚂蚁是否已经走完全部城市，如果没有完成，则跳到步骤2.2继 续完成；若完成，则记录最优路径的城市排序，更新信息素τ_ij；判断蚁群遍历全部城市 的次数是否达到N_a，若满足跳到步骤2.4，否则跳到步骤2.1；

步骤2.4：从全部的最优路径城市排序中选出最大距离，即最大离散度，的城市排序 作为最后的排序结果A'输出。

本发明具有以下有益效果：

本发明对遗传算法进行改进，利用模糊控制方法，通过种群熵和离散度自适应地控制 遗传过程中遗传算子的选取，在种群多样性变差时增大交叉概率和变异概率，使得种群朝 全局最优的方向进化，以缩小测试数据的规模，减少测试数据的生成时间。相比传统的方 法，本发明可以减少测试数据的生成时间3.53-91.12％。而且本发明为了能够尽可能有效 地发现软件错误，利用蚁群算法对生成的组合测试数据按照较大的离散度进行排序，以增 大测试参数相邻测试数据取值间的“距离”，进一步提高嵌入式软件的故障发现概率。

附图说明

图1为本发明流程图；

图2为熵隶属度函数曲线图；

图3为离散度隶属度函数曲线图。

具体实施方式

具体实施方式一：基于模糊遗传算法的嵌入式软件测试数据生成方法，相关概念如 下：

(一)遗传算法的相关概念如下：

(1)染色体

嵌入式软件中的一条测试数据T＝(a₁,a₂,...,a_k)即可认为是一条染色体， a_ip∈[0,v_ip-1],(ip＝1,2,...,k)，测试数据T中第ip个参数的取值a_ip认为是染色体上的第ip 个基因，集合v_ip为该基因所属的基因库，k为一条染色体上的基因个数；染色体在变异的 过程中处于某个位置的基因将从基因库中选择新的基因进行变异；

(2)适应值函数

设当前已有的测试数据集合为A，未被A覆盖的全部t维交互所组成的集合为Q，即 I是t维交互，H_t嵌入式软件的测试系统全部t维交 互，测试数据T_in中的全部交互，T_in是A中的一条测试数据，其适应值计算函数定义 为：当Q＝Φ时认为当前测试数据集合A中包含了全部t维交互，A 成为t维覆盖数组，至此遗传算法执行完毕；

(3)优秀种群

当一个进化周期结束后，按照one-test-at-one-time策略从测试数据集中选择一条适应 值最大的测试数据T添加到已有测试数据集A中，然后从集合Q中移除被A覆盖的全部 t维交互，即$\forall I=\{(v_1,a_{v_1}),(v_2,a_{v_2}),...,(v_t,a_{v_t})\}\in T$如果$\exists I\in Q,$v₁,...,v_t表示k个参数中的t 个，a_v1,...,a_vt表示对应参数v₁,...,v_t的取值，则从Q中移除I；

重新计算除T之外的全部测试数据集的适应值，选择适应值最大的测试数据y保留 至下一代；这样y被认为是除了T之外的最优测试数据，将y保留至下一代有助于种群 的快速成熟，这样在其余种群进化M_g次时，y已经进化了2M_g次，有助于y向全局最优 进化；

(4)种群熵

若第m代种群中有R个子集，各个子集所包含的个体数目分别为 且${\exists r}_r\in \{\mathrm{1,2},...,R\},\underset{r=1}{\overset{R}{U}}{A}_{i{r}_r}=B_m,$B_m为第m代种群的集合，则种群熵定 义为：

$S_N=(-\underset{r=1}{\overset{R}{\Sigma }}{P}_{{\mathrm{ir}}_r}\log \left(P_{{\mathrm{ir}}_r}\right))/\log N---\left(1.1\right)$

式中：ir_r∈[1,R]；N为种群的规模；当R＝1时，S_N＝0；当R＝N时， S_N＝1；熵体现的是种群集合中不同类型个体的分布情况，种群中不同类型的个体越 多，种群的熵就越大，种群的多样性就越好；

(5)种群离散度

根据测试数据T₁和T₂间的离散度定义种群的离散度为：

$D_N=\frac{\left|A_{{\mathrm{ir}}_1}\right|\left|A_{{\mathrm{ir}}_2}\right|D_{A_{i{r}_1}{A}_{{\mathrm{ir}}_2}}+...+\left|A_{{\mathrm{ir}}_{R-1}}\right|\left|A_{{\mathrm{ir}}_R}\right|D_{A_{{\mathrm{ir}}_{R-1}}{A}_{{\mathrm{ir}}_R}}}{\left|A_{{\mathrm{ir}}_1}\right|\left|A_{{\mathrm{ir}}_2}\right|+...+\left|A_{{\mathrm{ir}}_{R-1}}\right|\left|A_{{\mathrm{ir}}_R}\right|}---(1.2)$

式中：${\mathrm{ir}}_{d1},{\mathrm{ir}}_{d2}\in [1,R]$且ir_d1≠ir_d2为子集和离散度的权重， 当R＝1时，D_N＝0；当R＝N时，D_N＝1；种群的离散度同样可以对种群的多样性进行描 述，当种群中的不同类型个体越多时，种群的离散度就越大，种群的多样性就越好；

(6)熵隶属度函数

熵隶属度函数采用如下规则：

根据熵值S_N和熵的模糊标记确定熵的模糊标记的小、中、大；

分别根据和绘制四条熵隶属度 函数图像；

熵的模糊标记为小对应函数图像的熵隶属度函数值；

熵的模糊标记为中对应和函数图像的熵隶属度函数值；

熵的模糊标记为大对应函数图像的熵隶属度函数值；

(7)离散度隶属度函数

离散度隶属度函数采用如下规则：

根据离散度值D_N和离散度的模糊标记确定离散度的模糊标记的 小、中、大；

分别根据和绘制四条离散度隶 属度函数图像；

离散度的模糊标记为小对应函数图像的离散度隶属度函数值；

离散度的模糊标记为中对应和函数图像的离散度隶属度函数值；

离散度的模糊标记为大对应函数图像的离散度隶属度函数值；

(8)模糊规则

表1 遗传算子模糊规则

离散度模糊标记为小且熵模糊标记为小，模糊规则差；离散度模糊标记为中且熵模糊 标记为小，模糊规则差；离散度模糊标记为小且熵模糊标记为中，模糊规则差；

离散度模糊标记为大且熵模糊标记为小，模糊规则良；离散度模糊标记为中且熵模糊 标记为中，模糊规则良；离散度模糊标记为小且熵模糊标记为大，模糊规则良；

离散度模糊标记为大且熵模糊标记为中，模糊规则优；离散度模糊标记为大且熵模糊 标记为大，模糊规则有；离散度模糊标记为中且熵模糊标记为大，模糊规则优；

(9)模糊推理

种群的多样性为优时，即模糊规则为优时，交叉和变异应以小概率进行；种群的多样 性为差时，即模糊规则为差时，种群应以较大的交叉和变异概率进行进化；其它情况认为 种群的多样性良好，即模糊规则为良时，以较为合适的概率进行进化；

分别取熵隶属度函数图像和离散度隶属度函数图像上的值，进行组合按照最小值法推 理隶属度；即：选取熵的模糊标记为小、中、大对应的不为零的熵隶属度函数值，记为选取离散度的模糊标记为小、中、大对应的不为零的离散度隶属度函数值，记为分 别进行组合，按照得到最小值隶属度作为模糊规则的隶属度；模糊规则差、 良、优中的结果存在一个或者多个，对应存在的模糊规则的隶属度记为μ_C(z_l)，z_l为模糊 规则差、良、优的隶属度的权值。

(二)蚁群算法相关概念如下：

蚁群算法广泛应用于路径寻优的问题中，每一条测试数据就相当于一个将要去的城 市，对全部的测试数据的排序就相当于将所要去的全部城市进行排序一样，对城市的排序 是按照路径最小原则，而对于测试数据集的排序则依赖离散度最大原则；

设经过遗传算法生成的测试数据集为A，且T₁≠T₂，则T₁和T₂之间的距 离就是它们的离散度在蚁群算法中每一条测试数据(T₁或T₂)即为蚂蚁所在的城市；

按照蚁群算法的转移概率计算蚂蚁的下一个城市，第H只蚂蚁由城市C_f到C_b的转移 概率为：

$p_{C_f{C}_b}^H=\frac{{\left({\tau }_{C_f{C}_b}\right)}^{\alpha }{\left({\eta }_{C_f{C}_b}\right)}^{\beta }}{\underset{s\in J_H\left(C_f\right)}{\Sigma }{\left({\tau }_{C_{f}s}\right)}^{\alpha }{\left({\eta }_{C_{f}s}\right)}^{\beta }}---\left(2.1\right)$

式中，J_H(C_f)表示蚂蚁H在第C_f个城市允许转移到的城市的集合 J_H(C_f)＝A-tabu_H，tabu_H表示蚂蚁H已经到过的城市；表示启发因子，此处为C_f到C_b之间路径的距离；α表示信息素相对重要的程度，β表示启发因子相对重要的程度； 表示路径C_f到C_b的信息素大小，其更新公式为：

${\tau }_{C_f{C}_b}=(1-\rho ){\tau }_{C_f{C}_b}+\underset{H=1}{\overset{C_m}{\Sigma }}\Delta {\tau }_{C_f{C}_b}^H---\left(2.2\right)$

式中，ρ为信息素挥发系数，1-ρ为信息素残留因子，表示信息素的更新值， C_m表示蚂蚁个数，其计算公式为：

${\mathrm{\Delta \tau }}_{C_f{C}_b}^H=\left(\begin{array}{cc}\frac{Q_m}{L_H},& C_f{C}_b\in l_H\\ 0,& C_f{C}_b\notin l_H\end{array}\right)---\left(2.3\right)$

式中，Q_m为常数，L_H为表示第H只蚂蚁在本次周游过程中走过的长度的倒数，l_H表 示第H只蚂蚁在本次迭代中走过的路线；若第H只蚂蚁在其走过的路线中存在C_f→C_b， 则在信息素更新时

基于模糊遗传算法的嵌入式软件测试数据生成方法，包括以下步骤：

嵌入式软件中的一条测试数据T＝(a₁,a₂,...,a_k)即可认为是一条染色体， a_ip∈[0,v_ip-1],(ip＝1,2,...,k)，测试数据T中第ip个参数的取值a_ip认为是染色体上的第ip 个基因，集合v_ip为该基因所属的基因库，k为一条染色体上的基因个数；

设当前已有的测试数据集合为A，未被A覆盖的全部t维交互所组成的集合为Q，即 I是t维交互，H_t嵌入式软件的测试系统全部t维交 互，测试数据T_in中的全部交互，T_in是A中的一条测试数据，其适应值计算函数定义 为：$f\left(T_{\mathrm{in}}\right)=\left|\right\{H_{T_{\mathrm{in}},t}\cap Q\left\}\right|;$

步骤1.1：输入交互维度t，染色体进化代数M_g，染色体组规模N_g；第ip个参数的 取值区间为[0,v_ip-1],1≤ip≤k，k为一条染色体上的基因个数；令当前进化代数m＝0，测 试数据集A＝Φ，未被覆盖t维组合集Q为全部k个参数的t维取值集合；

步骤1.2：初始化染色体组，随机为每一条染色体的基因赋初始值；

步骤1.3：计算每条染色体的适应值，然后按照适应值从小到大进行排序，记为 第i_x条染色体的适应值，i_x∈N_g，生成随机数p∈[0,1]，如果则认为第n条染色体为自然选择的结果，循环N_g次，选择出新的N_g条染色体，作为新的 染色体组；

步骤1.4：对种群N_g的染色体进行随机配对，每一对染色体生成随机数q∈[1,k]，对 q位置的基因按照概率p_c进行交叉，生成新的染色体组；

步骤1.5：对步骤1.4生成新的染色体组中每一条染色体生成随机数q∈[1,k]，对q位 置的基因按照概率p_m进行变异；

步骤1.6：为每一条染色体计算适应值，判断种群最大适应值是否为如果是，进 入步骤1.7；如果不是，则判读m是否等于M_g，如果相等则跳到步骤1.7，否则令m＝m+1， 跳到步骤1.3；

步骤1.7：将适应值最大的染色体放入A，移除Q中已被适应值最大的染色体覆盖的 t维组合，判断Q是否为空，如果为空，则输出A结束，否则跳到步骤1.2；

步骤2.1：输入测试数据集A，蚁群规模M_a，迭代次数N_a；为每一只蚂蚁Ant_H， H∈[1,M_a]，随机设定初始城市的位置，即A中的某条数据；

步骤2.2：依次为每一只蚂蚁选择下一个城市，按照第W只蚂蚁的J_w(i)依次计算转 移概率，按照转移概率由小到大对城市进行排序，随机生成p_a∈[0,1]，计算 当C_R>P_a时，蚂蚁H将选取城市C_R作为所要去的城市；

步骤2.3：判断全部蚂蚁是否已经走完全部城市，如果没有完成，则跳到步骤2.2继 续完成；若完成，则记录最优路径的城市排序，更新信息素τ_ij；判断蚁群遍历全部城市 的次数是否达到N_a，若满足跳到步骤2.4，否则跳到步骤2.1；

步骤2.4：从全部的最优路径城市排序中选出最大距离，即最大离散度，的城市排序 作为最后的排序结果A'输出。

具体实施方式二：本实施方式所述的步骤1.4中采用模糊推理的方法求解p_c，包括以 下步骤：

1.4.1：模糊化：根据种群集合按照隶属度函数计算种群的熵和离散度隶属度，并根据 熵和离散度隶属度值激活模糊规则；

1.4.2：模糊推理：根据种群的熵和离散度隶属度值，按照最小值法推理被激活的模糊 规则的隶属度；

1.4.3：去模糊化：根据不同模糊规则的隶属度，采用加权平均法 $z_0=\underset{l=1}{\overset{s}{\Sigma }}{z}_l{\mu }_C\left(z_l\right)/\underset{l=1}{\overset{s}{\Sigma }}{\mu }_C\left(z_l\right)$精确计算交叉概率。

其他步骤和具体参数与具体实施方式一相同。

具体实施方式三：本实施方式所述的步骤1.4.1中计算种群的熵和离散度隶属度的过 程为：

若第m代种群中有R个子集，各个子集所包含的个体数目分别为 且${\exists r}_r\in \{\mathrm{1,2},...,R\},\underset{r=1}{\overset{R}{U}}{A}_{i{r}_r}=B_m,$B_m为第m代种群的集合，则种群熵定 义为：

$S_N=(-\underset{r=1}{\overset{R}{\Sigma }}{P}_{{\mathrm{ir}}_r}\log \left(P_{{\mathrm{ir}}_r}\right))/\log N---\left(1.1\right)$

式中：ir_r∈[1,R]；N为种群的规模；当R＝1时，S_N＝0；当R＝N时， S_N＝1；

根据测试数据T₁和T₂间的离散度定义种群的离散度为：

$D_N=\frac{\left|A_{{\mathrm{ir}}_1}\right|\left|A_{{\mathrm{ir}}_2}\right|D_{A_{i{r}_1}{A}_{{\mathrm{ir}}_2}}+...+\left|A_{{\mathrm{ir}}_{R-1}}\right|\left|A_{{\mathrm{ir}}_R}\right|D_{A_{{\mathrm{ir}}_{R-1}}{A}_{{\mathrm{ir}}_R}}}{\left|A_{{\mathrm{ir}}_1}\right|\left|A_{{\mathrm{ir}}_2}\right|+...+\left|A_{{\mathrm{ir}}_{R-1}}\right|\left|A_{{\mathrm{ir}}_R}\right|}---(1.2)$

式中：${\mathrm{ir}}_{d1},{\mathrm{ir}}_{d2}\in [1,R]$且ir_d1≠ir_d2为子集和离散度的权重， 当R＝1时，D_N＝0；当R＝N时，D_N＝1；

其他步骤和具体参数与具体实施方式一或二相同。

具体实施方式四：本实施方式所述的步骤1.4.1中熵隶属度函数值、离散度隶属度函 数值以及模糊规则确定的步骤如下：

熵隶属度函数采用如下规则：

根据熵值S_N和熵的模糊标记确定熵的模糊标记的小、中、大；

分别根据和绘制四条熵隶属度 函数图像，如图2所示；

熵的模糊标记为小对应函数图像的熵隶属度函数值；

熵的模糊标记为中对应和函数图像的熵隶属度函数值；

熵的模糊标记为大对应函数图像的熵隶属度函数值；

离散度隶属度函数采用如下规则：

根据离散度值D_N和离散度的模糊标记确定离散度的模糊标记的 小、中、大；

分别根据和绘制四条离散度隶 属度函数图像，如图3所示；

离散度的模糊标记为小对应函数图像的离散度隶属度函数值；

离散度的模糊标记为中对应和函数图像的离散度隶属度函数值；

离散度的模糊标记为大对应函数图像的离散度隶属度函数值；

模糊规则采用如下：

离散度模糊标记为小且熵模糊标记为小，模糊规则差；离散度模糊标记为中且熵模糊 标记为小，模糊规则差；离散度模糊标记为小且熵模糊标记为中，模糊规则差；

离散度模糊标记为大且熵模糊标记为小，模糊规则良；离散度模糊标记为中且熵模糊 标记为中，模糊规则良；离散度模糊标记为小且熵模糊标记为大，模糊规则良；

离散度模糊标记为大且熵模糊标记为中，模糊规则优；离散度模糊标记为大且熵模糊 标记为大，模糊规则有；离散度模糊标记为中且熵模糊标记为大，模糊规则优。

其他步骤和具体参数与具体实施方式一至三之一相同。

具体实施方式五：本实施方式所述的步骤1.4.2的步骤为：

种群的多样性为优时，即模糊规则为优时，交叉和变异应以小概率进行；种群的多样 性为差时，即模糊规则为差时，种群应以较大的交叉和变异概率进行进化；其它情况认为 种群的多样性良好，即模糊规则为良时，以较为合适的概率进行进化；

分别取熵隶属度函数图像和离散度隶属度函数图像上的值，进行组合按照最小值法推 理隶属度；即：选取熵的模糊标记为小、中、大对应的不为零的熵隶属度函数值，记为选取离散度的模糊标记为小、中、大对应的不为零的离散度隶属度函数值，记为分 别进行组合，按照得到最小值隶属度作为模糊规则的隶属度；模糊规则差、 良、优中的结果存在一个或者多个，对应存在的模糊规则的隶属度记为μ_C(z_l)，z_l为模糊 规则差、良、优的隶属度的权值。

其他步骤和具体参数与具体实施方式一至四之一相同。

具体实施方式六：本实施方式所述的步骤1.4.2所述的模糊规则差、良、优的隶属度 的权值中概率的论域是[0，1]，模糊规则差、良、优对应的权值为1、0.5、0。

其他步骤和具体参数与具体实施方式一至五之一相同。

具体实施方式七：本实施方式所述的步骤1.5中p_m的求解过程与p_c一样。

其他步骤和具体参数与具体实施方式一至六之一相同。

具体实施方式八：本实施方式所述的步骤2.2中的的求解过程为：

按照蚁群算法的转移概率计算蚂蚁的下一个城市，第H只蚂蚁由城市C_f到C_b的转移 概率为：

$p_{C_f{C}_b}^H=\frac{{\left({\tau }_{C_f{C}_b}\right)}^{\alpha }{\left({\eta }_{C_f{C}_b}\right)}^{\beta }}{\underset{s\in J_H\left(C_f\right)}{\Sigma }{\left({\tau }_{C_{f}s}\right)}^{\alpha }{\left({\eta }_{C_{f}s}\right)}^{\beta }}---\left(2.1\right)$

式中，J_H(C_f)表示蚂蚁H在第C_f个城市允许转移到的城市的集合 J_H(C_f)＝A-tabu_H，tabu_H表示蚂蚁H已经到过的城市；表示启发因子，此处为C_f到C_b之间路径的距离；α表示信息素相对重要的程度，β表示启发因子相对重要的程度； 表示路径C_f到C_b的信息素大小，其更新公式为：

${\tau }_{C_f{C}_b}=(1-\rho ){\tau }_{C_f{C}_b}+\underset{H=1}{\overset{C_m}{\Sigma }}\Delta {\tau }_{C_f{C}_b}^H---\left(2.2\right)$

式中，ρ为信息素挥发系数，1-ρ为信息素残留因子，表示信息素的更新值， C_m表示蚂蚁个数，其计算公式为：

${\mathrm{\Delta \tau }}_{C_f{C}_b}^H=\left(\begin{array}{cc}\frac{Q_m}{L_H},& C_f{C}_b\in l_H\\ 0,& C_f{C}_b\notin l_H\end{array}\right)---\left(2.3\right)$

式中，Q_m为常数，L_H为表示第H只蚂蚁在本次周游过程中走过的长度的倒数，l_H表 示第H只蚂蚁在本次迭代中走过的路线；若第H只蚂蚁在其走过的路线中存在C_f→C_b， 则在信息素更新时

其他步骤和具体参数与具体实施方式一至七之一相同。

实施例

通过仿真实验将本发明与其它多种启发式算法进行比较，选择几种典型的待测系统， 利用本发明成测试数据集，并对测试数据集规模和算法效率与其它算法进行比较。比较结 果如表2和表3所示。本发明用FGA(Fuzzy Genetic Algorithm)表示，比较的对象有SA (模拟退火)方法、GA(遗传算法)方法、ACA(蚁群算法)方法、CE(交叉熵算法) 方法，AETG测试工具及PSO算法；

表2 对于典型测试系统测试数据集规模比较

表3 对于典型测试系统算法执行时间比较

注：实验环境和编程方法：①C++,Linux,INTEL Pentium IV 1.8GHz；②C,Windows XP, INTEL Pentium IV 2.26GHz；③Matlab,Windows XP,INTEL Core(TM)₂2.66GHz；④.C++, Windows XP,INTEL Core(TM)₂2.5GHz.

由表2和表3可以看出，对于上述几种典型的测试系统，本发明主要优势是在算法执 行效率方面，所需运算时间上明显较其它算法少。在软件系统规模较小时，本发明所生成 测试数据集规模与其他的测试工具相差不大，在规模较大的系统下，会产生更优的结果，

为消除实验环境和编程方法对结果的影响，在与本发明相同实验环境下，实现了基于 PSO的测试数据生成算法，并对生成测试数据集规模和算法执行时间进行分析。本发明 中，取群体规模N_g＝500，迭代次数M_g＝20。实验结果如表4和表5所示，其中，试验 环境为C++,Windows XP,INTEL Core(TM)22.5GHz。

表4 对于大规模系统测试数据集规模比较

表5 对于大规模系统算法执行时间比较

由表4和表5可见，对于较大规模系统，与PSO算法相比，本发明在生成测试数据 规模和算法效率方面均具有优势。因为随着系统规模的增大，PSO算法容易陷入局部最 优的特点对实验结果的影响较大，如需得到较好结果，则需要大幅增加迭代次数。本发明 中，采用了全局寻优效果较好的FGA算法，能够有效的保证测试数据的生成质量，同时 具有较高的算法执行效率，由表4和表5中数据可以看出，在保证测试数据质量略有提高 的前提下，本发明的执行速度与PSO算法相比，提了10％到30％。

在利用蚁群算法对测试数据集进行排序时，算法参数对测试数据集的排序结果及算法 效率影响，本发明利用相同的测试数据集对蚁群算法参数的选取进行了实验，分析了各参 数对数据排序结果及算法运行时间的影响，给出了实际应用时各参数的选取方法。下面以 规模为20的测试数据集为例，给出了不同的蚂蚁数量和迭代次数对排序后测试数据集离 散度及计算时间的影响情况。下述α表示信息素相对重要的程度，β表示启发因子相对重 要的程度，ρ为信息素挥发系数。

表6 在不同蚂蚁数量下的排序离散度

注：迭代次数30，α＝1，β＝5，ρ＝0.5

表7 在不同迭代次数下的排序离散度

注：蚂蚁数量30，α＝1，β＝5，ρ＝0.5

由表6和表7可知，迭代次数与蚂蚁的数量直接导致算法搜索路径增加。蚂蚁数量越 大，每次迭代走过的路径越多，越容易找到全局最优的路径。迭代次数越多，每个蚂蚁走 过的路径越长，越容易得到最优结果，但是如果增加蚂蚁数量及迭代次数，就会增加算法 的复杂度，使得计算的时间相应增加。由表6可知，当蚂蚁数量由10增加到100时，最 大排序离散度提升了9％，计算时间约增加了1倍；而当蚂蚁数量由100增加到500时， 最大排序离散度只提升了1％，计算时间却增加了5倍。以上结论同样适用于迭代次数与 最大排序离散度之间。因此，当系统规模较大、需要考虑排序时间时，建议蚂蚁数量和迭 代次数都不大于100。

表8～4.9分别给出了信息素重要程度、启发因子和挥发因子与排序后测试数据集的离 散度之间的关系。

表8 在不同信息素重要程度下测试数据集的离散度

注：迭代次数30，蚂蚁数量30，β＝5，ρ＝0.5

表9 在不同启发因子下测试数据集的离散度

注：迭代次数30，蚂蚁数量30，α＝1，ρ＝0.5

表10 在不同挥发因子下测试数据集的离散度

注：迭代次数30，蚂蚁数量30，α＝1，β＝5

由表8至表10可知，信息素重要程度和挥发因子的变化对测试数据集的离散度影响 不大，启发因子越大，测试数据集的离散度越大。对不同规模的测试数据集进行排序时， 在信息素重要程度、启发因子和挥发因子的取值上会有不同，鉴于以上参数在一定范围内 存在最优值，可以通过相关试验确定。

结论：本发明在利用遗传算法生成组合测试数据的基础上，引入模糊控制方法，设计 了隶属度函数和模糊规则，对遗传算法的交叉概率和变异概率按照种群的多样性进行自适 应改变，有效的减少了种群早熟的问题，使得种群朝全局最优的方向进化。实验验证，本 算法在测试数据生成时间上优于其他算法，而且测试数据集的规模较小，可有效地应用于 组合软件测试数据生成中。针对嵌入式软件输入参数值跳变易引起软件错误的特点，在生 成的测试数据集的基础上，采用蚁群算法对测试数据进行离散度排序，以提高测试数据的 质量，进而提高嵌入式软件错误的发现概率。