流形（Manifold）是局部具有欧几里得空间性质的空间，其概念是几何和现代数学物理中许多模型和方法的核心，广泛应用于计算和应用数学、机器学习、物理、化学等领域。

图1  有趣的流形近年来，哈佛大学研究团队尝试应用几何方法研究深度学习[4]近期，他们提出了流形分布定律，即根据计算共形几何中的数据分布假设和流形假设，同一类别的高维数据往往集中在低维流形附近[5]受到流形分布定律的启发，智能算法研究中心提出了一种

基于流形搜索的测试用例自动生成算法（Manifold-Inspired Search-based Algorithm,MISA）[1]，为基于路径覆盖的测试用例自动生成（Automated 次元羊Test Case Generation Based on Path Coverage,ATCG-PC

）问题提供了优化方案，现已成功在智能优化领域的国际学术期刊IEEE Transactions on Emerging Topics in Computing（JCR一区，影响因子7.691）上发表研究成果论文。

下面重点介绍MISA算法的主要思路在许多领域中，利用流形学习，可将非欧氏空间转化为低维欧氏空间，从而降低问题的求解难度而MISA算法运用流形学习的思想，定义了等价映射子空间有效决策子集（Effective decision space, EDS。

）。MISA算法的主要思路是使用测试用例与次元羊路径之间的关系矩阵来找到等价映射子空间，并通过在子空间中搜索来生成涵盖所有可能路径的测试用例。

图2  流形思想在启发式优化算法的应用下面介绍MISA算法的两大策略（1）定义等价映射子空间EMS通过计算找到等价映射子空间EMS在预设的子空间内进行搜索，减少搜索空间，以减少路径与测试用例一对多关系造成的函数评估次数（。

Function Evaluations, FEs）冗余，同时定位有效决策子集（2）自适应地分配FEs消耗在子空间不是EMS的情况下，根据测试用例路径关系矩阵自适应地分配FEs，确保算法的有效性流形启发式优化算法（。

MISA）的流程如图3所示。该算法实现了以上两种策略，力求将ATCG次元羊-PC求解过程中产生的FEs降到最少。

图3  流形启发式优化算法流程图MISA为基于路径的测试用例自动生成问题提供了优化方法测试用例自动生成是软件工程中一类最基本的NP-Complete黑盒问题该问题的求解可有效减少软件测试的资源开销其中基于路径覆盖的测试用例自动生成算法最为关键。

目前，ATCG-PC问题求解有两个难点：一、从测试用例到路径的映射是一个黑盒，关系的未知性使得许多生成的测试用例重复覆盖相同路径，大大增加了FEs的消耗二、测试用例搜索空间的表面是一个非欧氏的特殊空间，使得在大规模范围内找到覆盖目标路径的测试用例十分困难。

而MISA通过在ATCG-PC的等价映射子空间中查询和搜索，节次元羊省了大量的冗余FEs消耗，有效解决了ATCG-PC求解的难点为了验证MISA算法的有效性，智能算法研究中心搜集整理出一个全面的测试集（下载地址：。

https://github.com/peerfog/ATCG-PC-testing-benchmarks）。该测试集的详细信息如图4所示。

图4  测试集详细信息表该测试集可分为三种类型：第一类为数据包，对应图4中的iFogSim与CoreNLP两个数据包iFogSim[2]是雾计算领域常用的工具包，通过模拟物联网和雾环境，测量资源管理技术在延迟、网络拥塞、能耗和成本方面的影响。

CoreNLP[3]是自然语言处理领域常用的工具包，集成了非常多实用的功次元羊能，包括分词、词性标注和句法分析等第二类为开源工程中的函数，分别从gimp-2.2.4（图像处理与合成工具）、bibclean-2.08。

（清理bibtex文件工具）和tiff-3.8.2（图像处理工具）三个开源工程中共选取了六个函数添加进测试集第三类为基础函数，从众多函数中挑选了十个基础函数补充到测试集中，以完善测试集的功能该测试集共选取了两个广泛使用的数据包和。

16个开源基准函数，测试用例的数量庞大另外，测试集覆盖的领域甚广，涉及雾计算、自然语言处理等最重要的是，该测试集是面向路径覆盖的相比于分支覆盖、语句覆盖等，面向路径覆盖的测试用例生成具有难度更高、覆盖逻辑路径更多等优势。

利用该测试集次元羊，将MISA算法与其他相关算法进行实验评估与对比，测试MISA算法的性能图5给出MISA与ATCG-PC两种最新算法的实验结果对比，在大多数基准程序中，MISA的平均FEs消耗明显少于其他算法。

红色方框突出显示MISA优于其他比较算法的结果。

图5  MISA与部分最新算法的实验结果对比为了验证EMS搜索策略（算法1）的有效性，我们将MISA预设子空间与整个搜索空间的大小进行比较如图6所示，预设子空间的大小远小于整个搜索空间的大小，这将节省大量。

FEs消耗。

图6  MISA预设子空间和整个搜索空间的大小比较实验结果表明，MISA算法的FEs消耗明显低于现有算法，其路径覆盖率是目前流行的算法中最高次元羊的MISA算法在ATCG求解上具有显著的优势，将来可应用到具有函数嵌套和循环的大型软件中。

智能算法研究中心长期致力于将人工智能算法应用于解决智能化软件工程领域的前沿难题，并已取得一些初步成效未来，我们将继续在这个领域进行探索，以期为软件工程的学科建设和发展作出积极贡献参考文献[1] F. Liu, H. Huang, J. Su, S. D. Semujju, Z. Yang and Z. Hao,"Manifold-inspired search-based algorithm for automated test case generation," 。

IEEE Transactions o次元羊n Emerging Topics in Computing, vol. 99, pp. 1-15,2021.[2] H. Gupta, A.Vahid Dastjerdi, S. K. Ghosh, and R. Buyya, "iFogSim: A toolkit for modelingand simulation of resource management techniques in internet of things, edgeand fog computing environments,"

Software: Practice and Experience, vol. 47, n次元羊o. 9, pp. 1275-1296, 2017.[3] C. D. Manning,M. Surdeanu, J. Bauer, J. Finkel, S. J. Bethard, and D. Mcclosky, "The stanfordcoreNLP natural language processing toolkit," in

Proceedings of 52ndAnnual Meeting of the Association for Computational Linguistics: SystemDemonstrations

, pp. 55-60, 2014.[4] X. 次元羊Gu, F. Luo,J. Sun, and S. Yau."Variationalprinciples for minkowski type problems, discrete optimal transport, and discretemonge-ampere equations,"

 AsianJournal of Mathematics (AJM), vol. 20, no. 2, pp.383-398, 2016.[5] N. Lei, Z. Luo, S. Yau, and X. Gu, "Ageometric understanding of deep learning," 

Eng次元羊ineering, vol. 6,no. 3, pp. 361-374, 2020.研究团队介绍

      智能算法研究中心（原智能算法实验室，成立于2009年，2018年与2020年更名）是由算法研究科学家黄翰教授创办和牵头的人工智能研究团队研究中心主要承担国内外重要智能算法类的研究课题，以算法与软件工具包的形式，根据国内外企业、科研与教育机构等单位在智能信息处理方面的需求，解决相关技术难点问题，并从中培养国际化算法研究型人才与算法工程化人才。

实验室必修课

实验室精神

-END-

总编：黄翰责任编辑：袁中锦文字：梁靖欣图片：梁靖欣校稿：何莉怡时间：2021年07月26日

想了解更多智能算法最新研究进展、学术活动次元羊与经验交流等长按二维码关注我们吧

如果有需要咨询的地方可以联系我们实验室的负责人实验室负责人：黄翰教授联系邮箱：hhan@scut.edu.cn