本文是一篇计算机论文，本文通过生成部分随机样本，训练RBF神经网络模型为个体与适应度值建立关系，以降低计算适应度值的时间消耗。
1绪论
1.1研究背景与意义
随着近些年软件规模的不断扩大，若软件在测试时不够充分而投入市场使用，未被检测到的漏洞被触发时会造成不可预测的后果，用户也因此承担该风险。因此，软件的可靠性[2]受到重视，软件测试也随之愈发受到人们的关注[1-3]。在软件运行出现漏洞时，大多数输入情况下系统表现正常，而当输入一些特定的数据时才会使系统进入未知状态，导致不可估量的损失[4-7]。
任何软件均可视为函数的一种表达形式，即人们在设计软件功能时，均希望指定数据输入至软件中，输出为期望的数据，也就是为输入数据和输出数据建立一一映射关系。因此，要验证软件的可靠性即意味着需要大量验证测试数据与对应输出数据是否匹配，而由于时间成本关系，仅能从海量的测试数据中选取一小部分高质量的输入数据进行测试，故测试数据生成是软件测试中至关重要的步骤[8-11]。
输入的测试数据与输出数据的映射关系表现形式常以路径的形式表现出来，为检测所有映射关系的可靠性，因此一组高质量的测试数据需尽可能多地覆盖目标路径[12-15]。在选择一组测试用例时，所覆盖的路径数常作为其是否优秀的一个依据，针对路径覆盖问题的研究也随之受到重视。路径覆盖问题常定义为[16]：寻找程序输入空间中的某一组测试数据，其覆盖指定的目标路径集中的所有路径。路径覆盖问题可根据一次生成的路径数量分为单路径覆盖问题和多路径覆盖问题。其中后者可一次生成多条路径，效率高于前者，但也远比前者复杂，因此有较多学者系统地研究多路径覆盖生成测试用例[17-22]。
......................
1.2研究现状
近些年，较多国内外学者研究生成测试数据的问题时采取自动化方式[32-35]，且常使用启发式搜索算法尝试解决路径覆盖问题。下面介绍启发式搜索算法以及遗传算法在测试用例生成问题上的研究现状。
1)基于启发式搜索算法生成测试数据
为生成高质量的测试数据，众多学者将该问题转化成了路径覆盖问题，以避免忽视出现错误且未被检测的路径。由于搜索的状态空间过大，无法使用算法精确定位到覆盖指定路径的测试数据，因此常使用启发式搜索算法解决该问题，其中常见的算法为：蚁群算法，遗传算法，模拟退火算法，萤火虫算法等。且均通过实验证明了其在生成测试用例时的高效。
Pandey等[36]在萤火虫算法中融入Levy Flight方法，通过实验证明其提高了局部搜索能力，进而降低测试用例生成时间。Jatana等[37]将粒子群优化算法与变异测试相结合，其选择优秀个体的方式使用突变检测，提高了测试用例生成效率。Sharifipour等[38]设计新的信息素以改变蚁群在局部移动中的搜索方式，实验结果表明其优化了搜索能力，且分支覆盖和收敛速度得到提高。廖伟志等[39]优化评价蚂蚁优劣的方法，根据该评价方法决定路径变异及蚂蚁状态转移，使得难覆盖节点有更多的蚂蚁穿越，提高测试用例生成效率。Skocelas等[40]验证依赖于前向网络的上下文单元功能，并基于此，使用循环神经网络生成测试用例。高凤娟等[41]在深度学习的基础上结合符号执行测试与模糊测试方法，在测试开始前筛选出适合模糊测试的路径集，制导模糊测试至适当区域，提升整体效率。
.......................
2相关理论与技术
2.1优秀个体迁移策略
为阐述清楚优秀个体迁移的概念，首先描述所处理的问题，然后借鉴文献[23]的方法对问题进行建模，接着针对模型的不足之处提出优秀个体迁移策略进行优化，最后说明所提方案的优势。其中在多路径覆盖测试数据时，若不预先处理不可达路径，则可能导致在所有的可达路径都生成后，由于目标路径集中存在不可达路径却又继续尝试覆盖，降低生成效率。故在选取目标路径前，本文通过不可达路径检测模型筛选出不可达路径，并将其从目标路径集中删除。
第一步，问题描述
设个体ind所对应的路径l=(i1,i2,...,ik,...,im)，其中ik(1≤k≤m)的取值根据是否经过路径节点k而定，若经过节点k则ik=1，反之ik=0。本文策略意在通过搜索算法获取测试用例集R=(r1,r2,...,rj,...,rn)，其中测试用例rj覆盖路径pj，即生成一组测试用例覆盖所有目标路径。
第二步，模型构建
设目标路径集P包含n条路径，当输入lj尝试覆盖路径pj(j=1,2,…,n)时，若对应适应度函数yj=F(lj)达到最大值，则个体ind覆盖了路径pj，因此，覆盖目标路径问题转化为求解适应度函数y1,y2,...,yn的最大值问题，如式(2.1)所示。
ybest(j)=max(F(l1),...,F(lj),...,F(ln)),1≤j≤n(2.1)
计算机论文怎么写
.......................
2.2路径相似性迁移策略
在优秀个体迁移策略中，首先提出使用基于路径相似度的迁移策略，以路径相似度作为判断个体是否迁移的方式，并提出路径相似表以降低计算路径相似度的时间复杂度。接下来介绍所使用的相关定义与技术。
2.2.1路径相似表
定义2.1路径相似表。设目标路径集为P={p1,p2,...,pn}，可达路径集Q={q1,q2,...,qn}，其中qj与路径集P的子集Psim的相似度为α时，则Psim为qj的路径相似表。
设可达路径数为m，目标路径数为n，测试数据进化生成过程中的所有个体数为t。本文采用的策略在文献[23]搜索其它子种群解的基础上，融入个体迁移思想，在搜索解时需让种群中每个个体的路径与目标路径集作比较，判断个体是否为目标路径集中某些路径的解，而个体迁移也需计算路径与目标路径集间的相似度，故可同步进行，不会增加时间复杂度。易知可达路径数m远小于种群进化过程中所生成的个体数t，故会出现多个个体经过相同的可达路径p，进而在搜索是否为目标路径的解或优秀个体时，导致大量重复计算同一路径与目标路径集的相似度，重复次数γrep的计算如式(2.3)所示。γrep=(t-m)*n(2.3)
种群尝试覆盖目标路径集中的路径时，往往会覆盖非目标路径集中的路径，而当所有目标路径都被覆盖时，种群中进化出的所有个体会覆盖全部可达路径，故路径相似表的总数等于可达路径集的总数，因此当需搜索某条路径的路径相似表时就需在数量为可达路径数的表中搜索。
.........................
3基于路径相似性迁移策略的多路径覆盖测试..............................15
3.1问题定义....................................15
3.2融合路径相似性与个体迁移的多路径覆盖...............................16
4基于RBF神经网络迁移策略的多路径覆盖测试...........................34
4.1问题定义........................................34
4.2融合RBF神经网络与个体迁移的多路径覆盖.........................35
5总结与展望.........................................49
5.1总结.............................................49
5.2展望..........................................50
4基于RBF神经网络迁移策略的多路径覆盖测试
4.1问题定义
为避免运行插桩程序计算分支距离和层接近度的时间复杂度，同时降低获得个体适应度值的资源消耗，提出使用RBF神经网络预测适应度值的方法。RBF神经网络预测模块见4.2.1节，模型拟合的适应度函数见4.2.2节。在多种群遗传算法生成测试数据，种群迭代更新时，旧种群中会出现其它种群的优秀个体。若仅使用路径相似度作为评判个体的优劣会忽略某些优秀基因，同时可能引入某些劣质的基因，影响种群中优秀基因的迁移准确性，其对算法的优化难以稳定预测；若使用适应度值作为评判标准，则每个个体需计算多个适应度值，会极大地增加时间复杂度。但使用RBF神经网络预测适应度值，并以此作为判断个体是否优秀的依据，是解决优秀个体迁移准确性与时间复杂度较高的一种可行方案。遗传算法进化生成模块见4.2.2节。算法的总体框架如图4.1所示。
计算机论文参考
..........................
5总结与展望
5.1总结
本文以遗传算法为总体框架，并基于不同的优秀个体筛选方式选择迁移对象以提高个体信息共享程度，实验证明了所提出的两种方法提升了测试数据的生成效率。其在路径覆盖测试中的工作主要包括以下4点：
1)增加个体信息共享方式
在传统个体信息共享中，共享的信息仅包括种群中的个体是否覆盖了其它目标路径。但种群中会出现其它种群的优秀个体，这部分个体在进化过程中被舍弃，无法得到充分利用。为利用这部分个体信息，本文方法引入个体迁移策略，将这部分优秀个体迁移至对应的新种群中，参与该种群的进化操作，从而将搜索解或近似解的范围从单种群扩大到多种群中。由3.3节和4.3节的实验设计与结果分析可知，使用优秀个体迁移可有效地提升个体信息共享程度，提高种群中的优秀个体占比，在遗传过程中可有更大的概率将优秀基因遗传给后代，进而降低平均进化代数，达到提高测试数据生成的效率。
2)基于路径相似性迁移优秀个体
为提高种群间的个体共享程度，先提出将路径相似度作为个体是否优秀的判断依据，并且将满足条件的个体视为优秀个体，将其迁移至其它子种群中。但该方案在执行时，需计算大量路径相似度，且由于在进化过程中个体数量远大于可达路径数量，会出现多个个体经过同一条可达路径，故在计算个体路径与目标路径集的相似度时，会有多次重复的路径相似度计算，从而导致时间复杂度上升。为解决这一问题，提出使用路径相似表存储已经计算过的路径相似度，当再次经过该路径时，只需根据个体路径查表即可知个体是哪些子种群的优秀个体，进而降低计算相似度的时间复杂度。
3)使用RBF神经网络降低适应度函数模块的时间复杂度
在遗传算法中，适应度函数作为决策哪些个体的基因有较大概率遗传给后代的模块，有着至关重要的作用。但其需运行插桩程序以获得个体的部分信息，用于计算个体于目标路径的优劣程度。该过程的复杂度视程序规模而定，在程序规模逐渐增大的现在，其消耗的资源过多。而随着机器学习的快速发展，其挖掘数据之间关系的能力得到充分发展。本文通过生成部分随机样本，训练RBF神经网络模型为个体与适应度值建立关系，以降低计算适应度值的时间消耗。
参考文献（略）