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

摘要

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

主权项

基于模糊遗传算法的嵌入式软件测试数据生成方法，其特征在于包括以下步骤：嵌入式软件中的一条测试数据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，即Q＝{I|I∈H_t,且}，I是t维交互，H_t嵌入式软件的测试系统全部t维交互，测试数据T_in中的全部交互，T_in是A中的一条测试数据，其适应值计算函数定义为：$f\left(T_{\mathrm{in}}\right)=\left|\right\{H_{Y_{\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'输出。