目前，自然语言处理（NLP）作为一项理论驱动的计算智能技术，在自动网页推荐、社交情感分析和聊天机器人等科技领域有着重要的应用前景。如图一所示，NLP程序广泛应用在社会的各个领域，其主要以一种智能与高效的方式，实现对文本数据的系统化分析、理解与信息提取。然而，为了确保NLP程序的准确运行，以及避免其在测试时产生大量的时间开销和费用成本，有必要研制一款高效率的软件测试工具来保证NLP程序的可靠性。

图一  NLP的应用场景示例

为了最小化算法的测试用例开销，此项研究将NLP程序单元测试路径覆盖测试用例生成ATCG-PC问题建模成单目标优化问题。但在求解ATCG-PC问题时存在两个难点：第一，NLP程序中存在大量字符串输入变量，而一些路径仅当输入特定值的字符串时才能被覆盖，这样导致传统的优化算法在求解路径测试用例时收效甚微；第二，在ATCG-PC问题中，可能存在大量测试用例覆盖到同一条路径的情况，从而导致优化算法处理时会产生大量冗余的开销。

针对上述问题，华南理工大学软件学院智能算法实验室提出了一种基于随机启发式算法的动态多点搜索策略（SA-SS）[1]，该策略主要在结合如差分进化算法DE[2][3]、粒子群算法PSO[4]等随机启发式算法搜索后，使用动态多点搜索策略优化种群并重复进行迭代更新，从而求解NLP程序的路径覆盖测试用例生成问题。目前该研究成果已成功发表在计算智能权威期刊IEEE Transactions on Emerging Topics of Computational Intelligence上。下面我们对本研究工作的相关成果展开介绍。

图二 SA-SS的流程示意图

 SA-SS的流程如图二所示，该策略首先初始化种群，并评估种群个体和更新路径覆盖情况，在此基础上采用DE，PSO等算法的更新策略来更新种群，进一步评估种群个体和更新路径覆盖情况，最后通过动态多点搜索策略更新整个种群。其中，通过动态多点搜索策略来覆盖目标路径主要分为以下两步：第一步先优化个体生成目标路径和初始化撒点的步长，第二步开始顺序搜索所有变量维度，每次撒点以原最优值为中心，搜索时留下最优个体并更新撒点步长，最后按照该步骤持续动态多点搜索，直至达到最小搜索的撒点步长并遍历完所有变量。图三是一个基于SA-SS求解问题的用例示例图。

图三 基于SA-SS求解问题的用例示例图

考虑到随机启发式算法如差分进化算法DE、改进遗传算法IGA、蜂群算法ABC、粒子群算法PSO、竞争优化算法CSO等在求解ATCG-PC问题时效率难以满足要求，该研究工作将上述算法结合所提出的策略进行了以下四组仿真实验，从而验证该搜索策略SA-SS的有效性，其中实验分别为：SA-SS中参数s的对比实验、DE-SS与DE的对比实验、DE-SS与其它算法（包括IGA、ABC、PSO、CSO等）结合动态多点搜索策略SS的算法对比实验、DE-SS与其它算法（包括IGA、ABC、PSO、CSO等）结合变量局部搜索策略VNS的新算法对比实验。

其中，实验的基准测试函数均采用NLP工具包StandFordCoreNLP[5]，如图四所示。Stanford CoreNLP是一个用于处理自然语言的工具集合，它可以根据不同词语得到其基本的形式——词性，并依据短语和语法依赖来标记句子的结构，从而发现实体之间的关系、情感色彩以及人们所说的话等。不仅如此，Stanford CoreNLP提供了众多语法分析工具，支持大部分主要（人类）语言并适用于大多数主流编程语言的API，广泛应用在各类自然语言的文本分析中，具有整体最高水平的文本分析效果。此外，CoreNLP针对自然语言的分析也为更高级别和特定领域的文本理解应用程序提供了基础构建模块，在涉及自然语言处理的研究和应用领域中具有极高的地位以及深厚的意义。

图四 基准测试函数

实验一主要对SA-SS中参数s的性能作分析，算法以DE为例，实验对比结果如图五所示。当参数s取2时，DE-SS算法表现最优，而随着设定值增大算法性能呈现逐步下降的趋势。

图五 以DE算法为例的SA-SS参数性能分析结果

实验二给出了DE与DE-SS的对比分析，实验结果如图六所示。结果表明，该研究工作所提出的动态多点搜索策略SA-SS显著提升了DE算法求解ATCG-PC问题时的测试用例开销，并且在相同测试用例开销的情况下，DE-SS相比DE能够更快地实现路径覆盖。

图六 DE与DE-SS的对比结果

实验三给出了DE-SS与其它相关算法（包括IGA、ABC、PSO、CSO等）的对比分析，实验结果如图七所示。结果表明，该研究工作所提出的动态多点搜索策略SS能够显著提升IGA、ABC、PSO、CSO等算法自动生成NLP程序路径覆盖测试用例的效率，主要包括减少测试用例的数量以及实际运行时间的开销等方面。

图七 DE-SS与其他相关算法对比实验结果图

实验四给出了DE-SS与VNS领域搜索策略的对比分析，实验结果如图八所示。结果表明，该研究工作所提出的动态多点搜索策略SS相对于VNS这类传统的邻域搜索策略，在求解ATCG-PC问题时拥有显著的优势。

图八 DE-SS与VNS领域搜索策略对比实验结果图

在此项研究中，我们研究的是如何解决NLP程序路径覆盖测试用例的自动生成问题。针对一个复杂约束优化的NP-难问题，使用随机启发式算法如差分进化算法DE、粒子群算法PSO等来求解是一种常见、可行的思路。然而NLP程序的路径覆盖测试用例生成问题存在其独特的难点，如大量路径需要输入字符串为特定值才能被覆盖的难点，这使得传统的算法在求解该问题时效率难以满足要求。因此，此项研究针对一个应用广泛的NLP工具包CoreNLP进行单元测试，根据NLP单元程序中经常使用字符串作为输入变量的特点，设计了一种基于随机启发式算法的动态多点搜索策略SA-SS，从而实现了CoreNLP程序的单元测试路径覆盖测试用例的自动生成。该工作为同类型NLP程序自动生成路径来覆盖测试用例的算法提供了设计思路，使研究人员能够在此基础上设计更加优秀和高效的算法来测试NLP程序。

除此，在自动生成NLP程序（或其它需要特定输入值才能覆盖具体路径的程序）路径覆盖测试用例时，此项研究所提出的动态多点搜索策略可以显著减少算法的测试用例开销，并提升算法性能。该技术通过在跟目标路径等价的局部流形空间上搜索，使得算法搜索范围缩小且求解效果明显提高，这种将寻找目标等价于局部流形的思路有望为机器学习、数据挖掘等研究领域提供更多的应用实例与理论基础。

研究团队介绍：

智能算法实验室（原智能算法与智能软件实验室，2018年更名）依托华南理工大学软件学院而建，坐落于国家级人才培养模式创新实验区内。实验室主要承担国内外重要智能算法类的研究课题，以算法与软件工具包的形式，根据国内外企业、科研与教育机构等单位在智能信息处理方面的需求，解决相关技术难点问题，并从中培养国际化算法研究型人才与算法工程化人才。

本课题组隶属算法学术研究室的智能化软件工程研究组和算法工程研究室的大数据与自然语言处理研究组，主要研究数值型、文本型、混合型以及多元异构的数据挖掘、分析与预测，特别是针对海量数据处理效率与分析准确性的算法技术与架构设计等，如:降水集合预报预测、客户投诉记录智能分析、O2O智能导购、论坛舆情智能监控、绩效智能汇总和英语作文自动评分等。

参考文献：

1. Fangqing Liu, Han Huang, Zhongming Yang, Zhifeng Hao and Jiangping Wang. Search-based Algorithm with Scatter Search Strategy for Automated Test Case Generation of NLP Toolkit[J]. IEEE Transactions on Emerging Topics of Computational Intelligence, (Accept). DOI: 10.1109/TETCI.2019.2914280.

2. Han Huang, Fangqing Liu, Zhongming Yang and Zhifeng Hao.Automated Test Case Generation Based on Differential Evolution With Relationship Matrix for iFogSim Toolkit[J]. IEEE Transactions on Industrial Informatics, 2018,14(11):5005-5016.

3. Han Huang, Fangqing Liu, Xiaoyan Zhuo, and Zhifeng Hao.Differential evolution based on self-adaptive fitness function for automated test case generation[J]. IEEE Computational Intelligence Magazine,2017,12(2):46–55.

4. Fangqing Liu, Han Huang, Xueqiang Li and Zhifeng Hao. Automated Test Data Generation Based on Particle Swarm Optimization with Convergence Speed Controller[J].CAAI Transactions on Intelligence Technology,2017,2(2):73-79.

5. C. D. Manning, M. Surdeanu, J. Bauer, J. Finkel, S. J. Bethard, and D. Mcclosky. The Stanford CoreNLP Natural Language Processing Toolkit[C]//Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations. 2014:55-60.

文字： 刘方青、刘子钊

校稿： 冯夫健

图：   刘方青

实验室负责人： 黄翰教授

联系邮箱： hhan@scut.edu.cn

时间： 2019年7月25日