一种基于灾变的演化测试的动态优化方法

摘要

本发明提出了一种基于灾变的演化测试的动态优化方法，主要用于解决演化测试在演化过程中出现的种群早熟退化现象，本发明涉及到的关键操作包括：(1)生成初始种群时，需要度量初始种群的多样性，如果初始种群的多样性高于第一阀值，则表示种群中的个体过于分散，搜索过程较难收敛，此时需要重新生成初始种群直到初始种群多样性低于第一阀值；(2)演化过程中周期性的度量种群的多样性，一旦发现种群多样性低于第二阀值且未找到全局最优解则判定种群早熟退化，此时采取灾变操作以帮助种群恢复多样性。

主权项

一种基于灾变的演化测试的动态优化方法，其特征在于如下步骤：步骤1).分析指定的作为测试对象的程序并构造对应的控制流图，在测试对象中指定测试目标并根据指定的测试目标构造适应值函数，所述的测试目标是公知的语句覆盖、分支覆盖及路径覆盖，步骤2).随机生成k个数，这k个数组成一个测试用例即每个测试用例包含k个数，然后每个测试用例编码成种群中的一个个体，重复上述过程直至初始种群有n个个体，其中k和n都是正整数，所述的编码方法是公知的二进制编码和格雷码编码方法，步骤3).将种群中的个体解码为测试用例并将该测试用例作为测试对象的输入，运行测试对象并根据步骤1)构造的适应值函数计算适应值，适应值的值域为(0，1.0]，当某个体的适应值为1.0时，该个体就是所需的全局最优解，该个体对应的是满足测试目标的测试用例，所述的解码是将二进制编码或者格雷码编码的个体转换为十进制数值的测试用例，步骤4).将种群中个体的适应值按照设定的划分标准进行划分，统计每个划分区域中的个体数，根据DCP＝-∑Pi*log10Pi度量初始种群的多样性，所述的DCP为种群的多样性，Pi表示种群中适应值在第i个划分区域的个体数占个体总数的比例，且Pi∈[0，1.0]，i为正整数且为划分区域的编号，如果初始种群的多样性DCP高于设定的第一阀值，就重新生成初始种群直到初始种群的多样性DCP低于第一阀值，第一阀值的值域为(0，1.0]，步骤5).如果种群中的个体包含所需的全局最优解或者种群演化满足预设终止条件，则转至步骤11)，否则，进入步骤6)，所述的全局最优解是种群中适应值为1.0的个体，且该个体对应的是满足测试目标的测试用例，所述的预设终止条件是种群演化迭代次数达到预设的种群最大迭代次数max，所述的max是正整数，步骤6).如果种群的多样性DCP低于设定的第二阀值，则进行灾变操作，产生一个新种群，并转入步骤9)，否则，将当前种群作为旧种群，进入步骤7)，第二阀值的值域为(0，1.0]，步骤7).对旧种群进行演化操作，并生成临时种群，步骤8).按照设定的存活概率Ps对旧种群和临时种群进行存活操作，形成一个新种群，新种群中的个体为二进制编码或者格雷码编码的个体，所述的存活概率Ps∈(0，1.0)；步骤9).将新种群作为当前种群，并将当前种群中的个体解码为测试用例并将该测试用例作为测试对象的输入，运行测试对象并根据步骤1)构造的适应值函数计算适应值，步骤10).转至步骤5)，步骤11).结束测试。