基于智能优化算法的测试数据生成研究综述

摘要：软件测试数据的自动生成是提高测试效率和降低测试成本的关键策略之一。近年来，基于智能优化算法的测试数据生成方法逐渐成为学术界关注的热点问题。文章对该领域的研究成果进行了系统梳理与综合评述。文章分析了进化算法、群智能算法及模拟单个事物运行的智能算法在软件测试数据生成中的应用效果及优化能力，展望了软件测试数据自动生成技术未来可能的发展方向，提出了进一步的研究建议与思考。

关键词：智能优化算法；软件测试；测试数据生成；遗传算法；粒子群算法；蚁群算法；模拟退火算法

中图分类号：TP18 文献标识码：A

文章编号：1009-3044（2025）06-0049-04开放科学（资源服务）标识码（OSID）：

0 引言

软件测试在软件开发过程中扮演着不可或缺的角色。据统计，在软件开发的整个生命周期中，软件测试的成本通常占据了开发总成本的一半甚至更高[1]。传统的人工测试数据生成方法已显现出耗时费力且效率低下的局限性。因此，自动化生成测试数据的方法因其高效性的特点成为了解决该问题的重要途径之一。

在软件测试领域，基于智能优化算法的测试数据生成方法因提升效率而被广泛研究与应用，从而为软件测试工作提供了有力支持。

1 智能优化算法概述

智能优化算法是一类基于仿生学原理和数学模型的优化方法，被广泛应用于工程设计、机器学习、数据挖掘等领域，用于解决复杂的优化问题。这些算法通过模拟生物进化、群体行为或其他智能策略来搜索问题的最优解或近似最优解，具有全局搜索能力强、通用性高、参数敏感性高等特点，在生成软件测试数据方面也发挥着重要作用。以遗传算法（Genetic Al⁃gorithm， GA）为代表的进化类算法，以及优化粒子群（Particle Swarm Optimization， PSO）、蚁群算法（AntColony Optimization， ACO）等群体智能算法，结合模拟退火算法（Simulated  Annealing）、差分进化算法（Dif⁃ferential Evolution，DE）、灰狼优化算法（Grey Wolf Op⁃timizer， GWO）、蝙蝠算法（Bat Algorithm， BA）、多目标优化算法（Multi-objective Optimization Algorithm，MOA）、协同进化算法（Co-evolutionary Algorithm，CEA）、强化学习优化（Reinforcement Learning Optimi⁃zation）、元学习优化（Meta-learning Optimization）等其他优化方法，常用于生成软件测试数据。本文将探讨这些算法及其改进算法在自动生成测试数据中的实践，并对智能优化算法的未来研究趋势进行归纳与预测。

2 基于进化类算法的测试数据生成

进化类算法是一种源自自然进化过程的智能优化方法，借助遗传变异和“适者生存”的自然规则逐步优化的智能算法。这些算法模仿了生物进化的机制[2]，最具代表性的有学者Holland[3]在1975年基于自然选择理论提出的遗传算法（Genetic Algorithm，GA）和美国学者Storn 等[4]1995 年创立的差分进化算法（Differential Evolution，DE）。它们在求解复杂优化问题时展现出了强大的搜索能力和适应性。最常见的遗传算法的流程图如图1所示。

遗传算法生成测试数据的核心原理在于，设计并定义适应度函数，将其函数值作为衡量标准，借助算法反复对编码后的参数进行迭代优化，直至获取最优解或达到最大进化代数。相较于人工生成，能以更高效率生成更高质量的测试数据。但劣势十分显著，如出现过早收敛陷入局部最优和生成的测试数据路径覆盖率低的问题。为此，许多学者提出了各自的改进方案。

为应对遗传算法容易陷入局部最优的状况，程孟飞[5]所提出的多路径覆盖测试用例使用改进的佳点集遗传算法，通过混沌学习初始化，优化交叉算子，综合路径相似性与分支距离，该文章所提出的改进算法在迭代次数方面的波动相对较小，有效减缓了过早收敛的现象；杨现玮[6]提出的算法能够基于个体适应度的分布情况，决定交叉操作与变异操作的执行顺序，以提升种群中个体的多样性，为后续的遗传操作奠定基础，通过迁移子种群的个体，使得交叉和变异后的种群个体更加丰富，利于全局寻优，该算法在运行效率和生成覆盖所有路径的测试用例数量方面表现出显著的优势；黄陈辉[7]提出了基于反向学习的初始种群生成策略，以优化初始种群，使其更接近最优解，设计适应度函数，考虑算法的并行能力，采用了针对所有目标路径的个体评价函数，在交叉和变异过程中使用了混沌序列操作，增强全局寻优能力，避免“早熟”，提高了算法的性能，使遗传算法的效率提升了10.8%，自适应遗传算法提升了8.49%；文献[8]结合鲸鱼算法提出混合算法，采用精英保留策略，在交叉、变异操作中分别采用自适应的交叉、变异概率，增强了其全局搜索能力。这些方法的核心理念是通过打破种群的局部收敛状态，增强对解空间的探索能力，从而提高遗传算法找到全局最优解的可能性。

针对遗传算法生成测试数据效率不高和路径覆盖率低的问题，黄川沂[9]优化了算法流程，在每次生成子代时，会根据覆盖情况更新目标集和存档集，新设计的适应度函数综合考虑层相似度、分支偏差和个性化因子，能够自定义个性化因子并设置其影响权重，针对初代种群生成设计了自定义用例集，将随机生成的种群与自定义用例集结合，提升了初代种群的多样性，有助于算法更快收敛，并设计了多组对照实验，结果表明在测试用例生成问题上有更加优异的表现；文献[10]构建了适应度函数，扩大不匹配路径之间的差异，迅速生成满足条件的测试数据，降低冗余测试数据的产生，并提升覆盖率；虞飞等人[11]融合退火算法到遗传算法中，在交叉和变异产生新一代种群时，以退火算法的概率接受比父辈差的个体，能覆盖更多的路径，实验证明此算法的最优迭代次数为标准遗传算法的42.1%，是自适应遗传算法的85.4%；林亚娜[12]改进的算法通过路径构建方法生成目标路径矩阵集合和实际路径矩阵，设计适应度函数，比较目标路径矩阵和实际路径矩阵的差异，经归一化处理得到适应度值，根据适应度值调节遗传算子，得到问题的最优解集合和全部测试数据；文献[13]提出了一种基于佳点集的遗传算法，该算法根据问题特征采用不同种类的编码方式。对于基于二进制进行编码的个体，生成子代个体时利用了佳点集交叉算子；对于基于实数进行编码的个体，生成子代个体时则利用混沌交叉方法。此外，设计适应度函数时对分支距离和个体穿越路径与目标路径矩阵相似度的结合进行了尝试，该方法在覆盖率以及测试时间方面均具有优势；姚婷[14]提出基于多路径覆盖的遗传算法，计算个体针对每一条目标路径的适应值，保存符合条件的测试用例及其覆盖的目标路径，若无期望的测试用例，则评价进化个体性能，然后，进行选择、交叉、变异操作，构成新一代种群，迭代至生成覆盖所有目标路径的测试用例，效率明显提高；Suresh Y等[15]提出一种基于基路径集的遗传算法自动生成测试数据的软计算方法，将遗传算法的特征与测试数据相结合，充分利用测试数据生成能力的全局和局部优化能力的优点。这些方法的核心理念是提升搜索效率、增强全局探索能力并优化局部精度，从而更有效地解决遗传算法生成测试数据时效率低和路径覆盖率低的问题。

差分进化算法因其结构简洁、收敛速度快、鲁棒性强且实现便捷等特点，广泛应用于软件测试数据生成。韦婧[16]提出了一种基于多因素排序的参数自适应差分进化算法，该算法由两大部分组成，分别为参数存储和分配机制，参数存储通过加权排名择优存储，为下一代提供参考；分层分配依据适应度差值分类优化，增强局部搜索。实验表明，该机制有效提升差分进化算法性能，自适应策略池进一步优化。此外，自适应选择策略池差分进化算法结合了改进的DE/current-to-rand/1变异策略，并设计了两种不同类型的策略池。这些策略能够增强种群的局部搜索能力，平衡探索与开发的能力。实验结果显示，所提算法具有竞争力。

3 基于群智能算法的测试数据生成

自20世纪90年代以来，自然界生物和物理现象进入专家学者的视线，影响其提出了一系列群体智能算法，旨在通过模拟这些现象来解决复杂的优化问题。蚁群觅食启发了Colorni A[17]等人提出蚁群算法（Ant Colony Optimization，ACO），鸟群捕食启发Kenne⁃dy J[18]等人提出了粒子群优化算法（Particle Swarm Op⁃timization，PSO）。此外，对自然界物理现象的观察也是部分群体智能算法的起点。Reynolds R G[19]模拟人类社会发展提出文化算法，烟花爆炸启发Zhu Y等[20]提出了演化算法等。在软件测试数据生成领域，粒子群优化算法已成为学者们研究的重点，其流程图如图2所示。

与大多数优化算法一样，粒子群优化算法同样有着后期容易陷入局部最优和生成测试数据效率不高的问题。文献[21]通过引入自适应随机测试，提出了一种基于自适应随机测试的粒子群优化算法，当种群陷入局部最优解时，通过生成跳出局部最优的粒子提升全局搜索概率，实验显示算法精度与探索能力优异。提出代理模型优化，通过样本训练、适应度预测、筛选与更新降低计算成本，动态调整代理模型，显著提升了测试用例生成效率，同时有效降低了时间和计算成本。孙毅刚等人[22]为了应对测试用例冗余的问题提出一种由天牛须算法改进的粒子群算法，将粒子群算法与改进后的天牛须搜索算法结合来生成测试用例，有效减少测试用例集的大小，提高生成的效率；王杰等人[23]提出了基于实例群优化算法的软件测试数据生成方法，优化了各个环节的参数；滕赛娜[24]提出了两种方法改进陷入局部最优问题，其一采用梯度下降法对最优解与次优解进行再次搜索，并设定禁忌区域以保证快速找到最优解并提高收敛精度，其二引入混沌搜索进行优化，对当前种群中的最优粒子进行混沌优化以跳出局部最优，并对部分较差粒子进行混沌优化以改善种群多样性；王曙燕等人[25]利用大数据平台Spark将所有需要被覆盖的两两组合分组并下发到集群中各个节点上进行寻优操作，采用一次只测试一个用例的策略，并结合自适应粒子群算法进行寻优，当各个节点完成寻优后，利用Spark进行结果收集，并对收集后的用例集进行约简操作；李晨晨[26]采用约简粒子群优化算法（RAPSO）生成组合测试用例集，对进化方程中的速度项进行约简，仅依靠位置的更新来实现算法的迭代，避免了粒子速度带来的误差，提高了粒子群优化算法的收敛速度，在RAPSO算法的进化过程中，采用根据粒子当前适应度值与聚集度动态调整惯性权重的策略，有效避免算法过早收敛于局部最值，该算法相比其他3种算法分别提高了61.71%、46.82%、48.09%的执行效率。其核心理念与解决方法的关键在于平衡全局探索与局部开发，确保搜索多样性与效率。

群智能算法中其他受启发于鸟群、虫群和兽群的算法在软件测试数据生成上也被广泛应用。李清霞[27]提出了一种采用柯西变异算子来自动生成具有较高变异的测试数据集的改进乌鸦搜索算法，利用相对误差作为适应度函数来选择较好的测试用例，引入柯西变异算子以防止陷入局部最优；刘汀[28]引进改进蚁群算法控制测试用例集合的冗余数据量，建立测试用例集覆盖模型，掌握测试用例集数据信息的覆盖情况，根据事件发生概率模型，以测试用例集的用例个数最小为优化目标，建立用例集优化目标函数，在保证用例集满足要求的条件下，逐步缩小用例集信息的覆盖度；Lakshminarayana P等人[29]提出了一种混合了杜鹃搜索算法和蜂群算法的算法，将算法与现有的粒子群优化、布谷鸟搜索、蜂群算法和萤火虫算法进行了性能比较，所提算法生成的测试数据中有65%达到了较高的适应度函数值。

4 基于模拟单个事物运行的智能算法测试数据生成

有别于进化类算法和群智能算法的模拟群体行为，模拟退火算法、神经网络和禁忌搜索算法等倾向于模拟单个事物的运行逻辑来进行优化。刘思凝[30]提出一种改进的模拟退火遗传算法生成测试数据，提出新的路径相似度计算，并纳入适应度函数中，提高个体评价精度；围绕多点交叉算法和自适应变异，采用精英保留策略，保护最优个体，再结合模拟退火算法，应用Boltzmann机制，加速收敛并避免早熟和局部最优；文献[6]使用RBF神经网络模拟适应度函数，代替插值法计算个体适应度值，大幅提高了分支覆盖测试用例生成算法的效率，缩短了生成时间；刘本和[31]以禁忌搜索算法作为主要工具，结合遗传算法辅助提出改进的禁忌搜索算法，通过优化初始解的选择，解决了禁忌搜索算法对初始解的依赖问题，并对返回值进行了调整，从而在效率和解质量方面取得了显著改善；仲晓敏等人[32]对禁忌搜索算法的评价函数、邻域移动和禁忌表进行改进，并设计了合理的赦免准则和终止准则。在此基础上构建了测试用例生成模型，利用禁忌搜索算法产生测试用例来驱动插桩程序运行并求取其评价值，通过实验验证了该方法的准确性和有效性。

5 结论与展望

在软件测试领域，自动生成测试数据已成为解决测试效率和成本问题的重要途径之一。本文综述了基于智能优化算法的软件测试数据自动生成方法。首先阐述了软件测试的重要性以及传统方法的局限性，从而引发了自动生成测试数据的需求。随后，概述了智能优化算法，涵盖了进化类算法和群体智能算法等。最后针对这些算法，详细介绍了它们在测试数据生成领域的应用以及改进成果。未来，基于智能优化算法的测试数据生成方法仍具有广阔的研究前景，在跨领域测试数据生成、动态适应性优化算法、多目标优化与约束处理和大规模软件系统测试数据生成方面，可以进一步提高测试数据生成的效率和质量，结合多种算法和技术以提高智能化水平，追求人机协同化、软硬件协同测试数据生成、自动化与持续集成中的测试数据生成，并设计定制化方案以满足不同应用需求。