优化教育软件的自动化测试：以一门在线STEM科目为例

鲁宾·冈萨雷斯·克雷斯波 普拉波哈特·库马 曼珠·卡里 丹尼尔·布尔戈斯

【摘 要】 教育软件和教育ICT软件应用程序测试的自动化能减少测试维护失败的风险，选择最优化的测试套件能提高效率，因此能降低成本和耗时。本文介绍一种自动化测试工具的研发，这种工具包含教育软件测试的两个主要自动化部分：测试套件生成和测试套件优化。本文通过控制流图表示被试教育软件的控制流。该工具提供五种测试套件生成方法，即边界值测试、稳健性测试、最坏情况测试、稳健最坏情况测试和随机测试，并采用人工蜂群算法或布谷鸟搜索算法对所生成的测试套件进行优化，直至达到预期的适应值水平。与其他算法相比，这种方法能够以最少的一组测试用例达成最大的路径覆盖率。最后，我们对所产生的优化测试套件进行自动故障检测。本文还以一所在线开放大学的一门STEM科目为案例，介绍这个工具的使用情况。

【关键词】 教育软件；教育ICT软件应用程序；测试套件生成；测试套件优化；STEM；控制流图；自动化测试

【中图分类号】 G420 【文献标识码】 B 【文章编号】 1009-458x（2018）6-0028-12

导读：长期以来，信息技术与教育的深度融合是一个热点问题。然而，从目前的情况看，这种融合似乎仍然缺乏应有的深度，也还没有达成预期目标。2017年12月13日，《中国教育报》刊登该报记者张贵勇撰写的一篇题为“新技术进课堂不等于媒介教育”的文章，文中提到有些课堂“教师利用令人眼花缭乱的电子课件上课，课堂看似热闹”，甚至是“课堂上学生全部使用平板电脑等新媒介设备来上课”，他认为“尽管电子教材也好，多媒体课件也好，其以数字化、交互化、多媒化的形式，将教学内容以科学直观的视频、音频、图形、文本等展现出来，对学生的知识学习有帮助，但没有改变传统的灌输式学习方式，没有真正提升学生对各种媒介的解读、运用能力”。在我看来，这就是典型的“伪融合”。

本期“国际论坛”四位作者分别来自西班牙和印度的远程在线教学大学和普通高校（研究院），均在技术与教育的融合领域颇有建树，其中通信作者丹尼尔·布尔戈斯教授是西班牙拉里奥哈国际大学主管研究和技术的副校长，也是联合国教科文组织e-learning教席和国际远程开放教育理事会开放教育资源（OER）教席，一个真正具有跨学科学术背景的学者。他曾经在我们的通信中阐述他的教育科研理念。他认为作为在线教学机构的一员，自己的研究责无旁贷应该扎根具体教育实践，以解决实际教育教学问题为首要目的。他说学术研究应该接地气，应该能够赋权于教师，就技术的教育用途而言，研究成果应该能为并非技术行家的教师所用，而且能提高教学效果、达成预期学习目标，否则谈不上“融合”。他本人一直身体力行，比如有关适合大规模招生的e-learning推荐模型的研究①，也许正因为他有这样的理念而且又取得了丰硕成果，所以才被联合国教科文组织和国际远程开放教育理事会委以要职。

本文介绍他们的一项新研究成果，即教育软件的自动化测试。在今天这个信息时代，教育软件无处不在，从某种意义上讲已经成为当今教育教学不可或缺的组成部分，甚至可以说很多学科的教学离不开教育软件的应用。比如在生物、医学和护理等专业的学习中，教育软件能给学习者提供虚拟现实或增强现实，大大提高学习活动的真实性，完成很多在传统教学环境下很难开展的学习任务；而在机械、工程和建筑等专业的学习中，学习者使用这些软件开展设计、运算、建模、试验等活动，即使失败了也不会造成任何经济损失或伤害。对于远程在线学习来讲，教育软件的用途更是非常广泛，其对提高学习效果、保证教学质量的重要性更是自不待言。

随着用途越来越广泛，教育软件也越来越大、越来越复杂，因此，“改进教育软件开发技术，加快开发过程，提高开发效率，这些都势在必行。高效的软件开发过程应该是快捷、容易操作、稳健和低成本的”。这其中便涉及软件测试，这是“教育软件开发最具挑战性的阶段”。“教育软件测试在软件开发生命周期的早期进行，越是往后才发现的错误，修复的成本越高”，但是这也是一项非常复杂的工作，手工操作费时耗力、成本高昂，且不说可行性的问题。因此，本研究在系统回顾（教育）软件测试研究成果的基础上，研发一种自动化测试工具，即测试套件生成和测试套件优化。

本研究提出的自动化测试工具自身配备四种黑盒技术（即边界值测试、稳健性测试、最坏情况测试和稳健最坏情况测试）以及随机测试技术。可以用其中任何一种技术生成测试对象教育软件的测试数据，然后用人工蜂群算法和布谷鸟搜索算法优化这些数据，再把优化的测试套件应用于测试对象软件上以生成实际输出，而测试对象软件的控制流图则会产生预期输出，如果实际输出和预期输出不一致，则说明这个软件有错误。在阐明这种自动化测试工具的工作原理之后，文章还介绍了人工蜂群算法和布谷鸟搜索算法。

本研究用这个自动化测试工具对20个教育软件应用程序进行测试。软件测试是在西班牙拉里奥哈国际大学工程與技术学院的e-learning和社交网络硕士学位课程中进行的，有44名学生参加。限于篇幅，本文以三角形分类问题的软件应用程序为例，介绍自动化测试工具的运作和实际效果。测试结果表明，这个自动化测试工具在人工蜂群算法和布谷鸟搜索算法的帮助下能以最少的测试用例覆盖最多的路径，减少测试时间，降低测试费用，换言之，大大提高测试效率。研究还发现，两种算法有各自的优点，布谷鸟搜索算法的结果更加稳定但路径覆盖率较低，而人工蜂群算法的路径覆盖率更好，但结果不如布谷鸟搜索算法稳定。考虑到路径覆盖率是选择测试套件算法更加可靠的决定因素，因此，在本研究中，与布谷鸟搜索算法相比，人工蜂群算法是一个更好的选择。文章最后还指出本研究的局限和今后研究方向。

这篇文章的意义不仅体现在研发一种教育软件自动化测试工具上，也是技术与教育融合的一个很好的例子。对远程（在线）教育工作者而言，它更是布尔戈斯教授的教育科研观的具体体现。我认为这也是值得远程（在线）教育机构和实践者认真谋划和努力的一个科研方向——把技术与教育的融合扎根于远程（在线）教育实践中，旨在解决实际教学问题，达成具体教学目标。

最后，衷心感谢四位国际同行对本刊的支持！（肖俊洪）

引言

过去五十年，教育软件无所不在，对教育的影响越来越大，因此，人们对可靠教育软件的需求与日俱增。教育软件的用途广泛，几乎涉及我们生活的每一个方面，因此软件越来越复杂、越来越大。在这种背景下，改进教育软件开发技术，加快开发过程，提高开发效率，这些都势在必行。高效的软件开发过程应该是快捷、容易操作、稳健和低成本的。

教育软件的质量通过在软件开发生命周期（Software Development Lifecycle）的每一个层面对该软件进行严格测试得以保证（Bertolino， 2007； Burnstein， 2006）。经常升级导致软件修改的次数增加，软件的整体可靠性会随着降低。一种应对措施是增加测试量（Marciniak， 1994）。教育软件测试是软件开发生命周期一个不可或缺的阶段。没有经过严格测试的软件和错误代码每年给教育软件开发组织造成数十亿美元的损失，很多缺陷是用户发现的（Burnstein， 2006）。测试不仅是保证教育软件系统质量的有效措施（Miller， 1981），也是教育软件工程最复杂和较不为人所了解的领域之一（Whittaker， 2000）。

一些研究阐述了为什么要开展教育软件测试（Alba & Chicano， 2008； Alshraideh & Bottaci， 2006； Bertolino， 2007； Harman， Mansouri， & Zhang， 2009； Korel & Al-Yami， 1998； Markman， McMullen， & Elizaga， 2008； Pressman， 2005； Ricca & Tonella， 2001； Sommerville， 2001； Sthamer， 1995），原因包括检测故障、最大限度降低与教育软件残余错误相关的风险（Askarunisa， Prameela， & Ramraj， 2009）和对软件进行全面彻底测试（Huang & Kuo， 2002）等。在测试阶段发现的系统错误多数产生自软件开发生命周期的早期（Beizer， 1990），因此，教育软件测试应在软件开发生命周期的早期进行，越是往后才发现的错误，修复的成本越高。测试被认为是教育软件开发最具挑战性的阶段，占用全部开发时间和费用的50%～60%（Bertolino， 2007）。

教育软件测试可以手工进行，也可以通过自动化方式进行，目的是验证该软件是否符合工作或客户要求，也用于检查实际结果与预期输出是否一致（Radatz， Geraci， & Katki， 1990）。这种测试通过使用合适的测试用例（test case）检验软件是否符合要求，以此评估其质量。有些错误是在设计阶段因疏忽而引起的，这些错误应该立即得到修复。教育软件测试的目标是生成包含精确测试用例并能达成最大覆盖率和尽可能发现更多错误的最小测试套件（test suite）（Sthamer， 1995）。在此过程中，每一个测试用例都是不同的；每一个测试用例都配上一组输入和一系列预期输出。测试的另一个任务是生成合适的测试套件，以满足测试标准，比如代码覆盖（code coverage）（Sakti， Pesant， & Guéhéneuc， 2015）、路径覆盖（path coverage）、分支覆盖（branch coverage）（Sthamer， 1995）和语句覆盖（statement coverage）（Clarke， 1976）。这方面已经有一些测试标准，必须满足相关标准才能保证所测试的教育软件的质量（Ghiduk & Girgis， 2010）。教育软件的全面测试很难手工进行，有些方面必须实现自动化。

手工生成测试套件更加耗时耗力，这是一个劳动密集型而又昂贵的过程，因此必须减少人工测试量（Poon， Tse， Tang， & Kuo， 2011）。自动化测试能加快测试过程，节省时间和成本，达成最大覆盖率。此外，测试过程的自动化还能显著降低软件开发维护费用，提高其可靠性。

美国国家标准与技术研究院（National Institute of Standards and Technology）的研究表明，软件测试基础设施不完善所造成的损失每年估计在222亿到595亿美元之间（Tassey， 2002）。由此可见，必须优化测试过程，才能既减少对资源的要求（时间、经费和人力等）又保证质量。早期的教育软件技术开发采用爬山（hill climbing）算法（属于梯度下降算法[gradient descent algorithms]一族）生成测试用例和测试套件（Korel， 1990）。这些方法很耗时且无法避免搜索空间的局部最优解（local optima）。后来，人们使用元启发式搜索算法（metaheuristic search algorithms）解决这个问题（Edvardsson， 1999；Wegener， Baresel， & Sthamer， 2001），比如禁忌搜索算法（Tabu Search）（Díaz， Tuya， Blanco， & Dolado， 2008； Glover， 1997； Zamli， Alkazemi， & Kendall， 2016）、模拟退火算法（Simulated Annealing）（Lim， Rodrigues， & Zhang， 2006）、遗传算法（Genetic Algorithm，GA）（Alander， Mantere， & Turunen， 1998； Hermadi， Lokan， & Sarker， 2010； Mala， Mohan， & Kamalapriya， 2010）、粒子群优化算法（Particle Swarm Optimization，PSO）（Ahmed & Zamli， 2011； Jiang， Shi， Zhang， & Han， 2015）和蚁群优化算法（Ant Colony Optimization，ACO）（Li & Lam， 2004； Markman， McMullen， & Elizaga， 2008）。每一种算法都有自己的优缺点。工程界不同领域对基于搜索的算法已經开展了广泛研究、实验和应用（Afzal， Torkar， & Feldt， 2009； Harman， Mansouri， & Zhang， 2009）。

测试边界值不足以确保教育软件的准确，因为所有可能的值都必须测试和验证，但这是行不通的。要对一种教育ICT软件应用程序进行全面测试，只增加两个32-bits整数输入就要求测试[264]个不同测试用例，即使每秒钟完成数千次测试，这个量的测试也需要数百年时间才能做完。因此，必须实现测试套件优化（Test Suite Optimization，TSO）。TSO是去除不必要、多余的测试用例，把优质测试用例纳入测试套件中的过程，在这里，优质指的是在路径覆盖率、错误检测和代码覆盖率方面表现好。TSO从其测试用例母集中发现最好的子集。本研究采用人工蜂群算法（Artificial Bee Colony Algorithm，ABC）和布谷鸟搜索算法（Cuckoo Search Algorithm，CSA）实现TSO。这两种算法都是受到大自然启发的算法（Karaboga， 2005； Yang & Deb， 2009）。

研究背景

符号和术语

被测试的教育软件（Educational Software Under Test，SUT）的控制流或逻辑可以通过控制流图（flow graph）表示。控制流图由节点（N）和边（E）组成，即G（N， E）。用控制流图表示SUT逻辑，节点代表语句块，边代表从一个节点转移到另一个节点的流向，形成一条路径。基于控制流图有限的节点，可以发现独立路径（independent path）。控制流图与SUT的实际逻輯相似。因此，对一个控制流图的测试数据进行的运算被看作对教育ICT软件应用程序的运算。这个软件应用程序的特点应该体现在其控制流图中。

路径测试标准

一般而言，路径测试包括挑选一组合适的路径并用测试数据检测这些路径。这是一个迭代过程，直至完成对所有路径的测试。但是，一个控制流图的所有路径并非都能通过遍历，这些路径被称为“不可行路径”。路径覆盖率即被成功遍历的路径除以全部路径所得之百分比，如方程式（1）所示：

[路径覆盖率%=被成功遍历的独立路径数独立路径总数×100%] eq.（1）

文献回顾

科瑞尔（Korel， 1990）根据路径覆盖测试标准，采用包含各种可能的测试数据的动态路径测试技术生成教育软件测试数据，目的是获取执行期望路径的测试用例值。迪森等（Deason， Brown， Chang， & Cross， 1991）提出基于规则的测试数据生成方法，采用路径/谓词分析或随机测试数据生成法。他们认为因为测试用例可能无法覆盖所有路径，应该对测试套件进行优化。卡拉博加（Karaboga， 2005）根据蜜蜂群智能觅食行为，提出一种新的人工蜂群算法解决多维度和多模态问题。卡拉博加和巴斯图尔克（Karaboga & Basturk， 2007）后来又提出ABC算法解决约束优化问题。罗等（Luo， Liu， Yang， Li， Chen， & Cao， 2016）提出一种称为ABC覆盖阵列生成器（covering array generator）的新算法，生成覆盖阵列和结对测试的混合覆盖阵列。测试用例优先级排序（Test case prioritization）指的是重新排列测试用例执行顺序，以在某一特定时间段尽可能发现更多错误。作者们还进一步提出一种高效的多目标蚁群优化方法（multi-objective ant colony optimization）解决多目标和高维多目标问题（multi-objective and many-objective problems）。这种技术基于帕累托占优和偏好指标（Pareto dominance and preference indicators），使外部包（external archives）在每一次生成中产生一种有效的解。

杨和戴布（Yang & Deb， 2015）提出CSA算法解决包括NP-hard问题的优化问题，而甘多米等（Gandomi， Yang， & Alavi， 2013）则用CSA在没有调整测试参数的情况下解决结构问题，使CSA成为像PSO一样的稳健且更加通用的应用程序（Meza， Espitia， Montenegro， Giménez， & González-Crespo， 2016）。库玛和查克拉瓦蒂（Kumar & Chakarverty， 2011）使用GA和CSA设计嵌入式系统空间探索问题。CSA无需对参数调整进行过多试验便能够在更短时间内产生更好的种群。在对SUT更长时间运算之后通过GA获得最佳解。因此，CSA能在更短运算时间内高效生成某一个问题的多种解，而GA则在求最佳解方面效果最好。拉姆邹恩等（Ramchoun， Amine， Idrissi， Ghanou， & Ettaouil， 2016）采用GA，用反向传播算法（back-propagation algorithm）训练网络以优化网络问题。

马拉等（Mala， Mohan， & Kamalapriya， 2010）提出一种新的教育软件测试优化范式，采用基于混合智能的搜索方法达成教育软件测试最优化。这个框架的优点是自动生成测试用例，发现最优测试顺序，减少测试用例数量和把测试次数降到最低。

迈克尔等（Michael， McGraw， Schatz， & Walton， 1997）提出基于启发式搜索技术的方法解决教育软件测试的各种问题，他们通过在各种软件应用程序中使用GA和随机测试技术生成测试数据，比较这两种技术，发现GA生成更有效的测试数据。

卡里和库玛（Khari & Kumar， 2016）提出基于TSO搜索的方法，把局部搜索和全局搜索结合起来，在更短时间、迭代次数更少而空间复杂性的增加可以忽略不计的情况下获得最优结果。辛格（Singh， 2015）的结论肯定自动化生成预期输出的重要性，因为与人工操作相比，这样能够大大降低费用和时间。但是，目前还没有合适、完整和稳健的技术。

巴朗等（Barón， Crespo， Espada， & Martínez， 2015）提出一个学习考核框架，该框架包括结构方程模型和模糊认知图，旨在促进智慧环境下的学习评价。森沃尔等（Semwal， Singha， Sharma， Chauhan， & Behera， 2016）使用不同机器学习技术（如支持向量机、人工神经网络、KNN分类算法和分类器融合等）发现机器学习的原理和分类步态数据。梅扎等（Meza， Espitia， Montenegro， & Crespo， 2015）提出像旋转和直线运动这样的多目标优化（multi-objective optimization）策略，该策略建立在PSO和探索与利用（E & E）结果的基础上。查克里等（Chakri， Khelif， Benouaret， & Yang， 2017）提出一种修改的蝙蝠算法（bat algorithm）解决某些情况下基础蝙蝠算法探索能力低所引起的优化问题，提高该算法在探索和利用方面的效率。

本文尝试从不同角度研发一种自动化测试工具，即测试套件生成（Test Suite Generation，TSG）和测试套件优化（Test Suite Optimization，TSO）。

自动化测试工具的框架

自动化测试模型

本模型的测试套件生成包含四种黑盒技术，即边界值测试（boundary value testing）、稳健性测试（robustness testing）、最坏情况测试（worst case testing）和稳健最坏情况测试（robustness worst case testing），以及随机测试（random testing）。图1是其完整框架。我们可以用其中任何一种技术生成SUT的测试数据，然后用ABC或CSA对这些数据进行优化，将优化的测试套件应用于SUT上会生成实际输出，而SUT的控制流图则会产生预期输出，通过比较实际输出和预期输出发现SUT的错误。这个框架的组成部分如下：

·输入：控制流图和SUT。

·处理模块：采用上述测试技术完成TSG，由于所生成的测试套件可能会也可能不会对SUT有100%的路径覆盖，因此将其输入第二阶段，即TSO。这个阶段是在ABC和CSA帮助下完成的，最终获得优化测试套件。

·错误检测：将生成的测试套件与控制流图和SUT一起使用，分別获得预期输出和实际输出。如果两种输出不一致，则说明SUT有错误。

[ith]测试用例的方程式如下：

[xi=ti1，ti2，ti3，……tik……，tiN]

where [i=1，2，…SN] eq.（2）

在方程式（2）中，每一个测试用例xi有N个值，N等于包含教育ICT软件应用程序代码的源文件的变量数目，tik代表每一个变量的独立值集（individual set of values），SN 表示每个变量的每一个独立tik集（each individual set of tik for each variable）包含的值的数目。

已存在的测试用例发生位变异（mutation of bits）时产生新的随机测试用例。变异函数从这些位中选择一个并加以扰动。在方程式（3）中，xi是输入的测试用例，yi是变异测试用例：

yi= mutate （xi） eq.（3）

如果已存在和变异测试用例的独立路径相同，那么根据马提亚斯（Matyas）目标函数的值选择其中一个测试用例（Jamil & Yang， 2013），如方程式（4）和（5）所示：

For xi， p = （0.26 * [i=1Nt2ij]-0.48 * [j=1Ntij]） eq.（4）

For yi， q = （0.26 * [i=1Nt2ij]-0.48 * [j=1Ntij]） eq.（5）

如果 p > q， 那么

xi是比yi更好的测试用例

否则，

yi是比 xi更好的测试用例

结束分支。

ABC算法

ABC算法基于蜜蜂群的智能行为，包括三种平行工作的蜂：雇佣蜂、观察蜂和侦察蜂。雇佣蜂的数量与观察蜂的数量相同，等于SN。我们必须界定该算法的终止条件，通过重复以下步骤寻找每一个食物源ai：

1. 随机确定食物源[ai]以外的邻居食物源[a'i]。

2. 用目标函数评估邻居食物源[a'i]，如果[a'i]优于ai，则用其代替ai。否则，把尝试次数增加一次。

在侦察蜂时期，放弃尝试次数多于终止条件值的食物源，改用另一个随机食物源。ABC算法提供全局搜索，最终把有最佳目标函数值的食物源储存在记忆中。

ABC算法用于测试的完整伪代码如下：

第1步：初始化ABC控制参数。

第2步：用本测试工具的任何测试技术初始化初始种群。

第3步：评估这个种群并把通过新独立路径的测试用例添加到结果集。

第4步：cycle=1

第5步：Do

【雇佣蜂和观察蜂时期】

a. 用方程式（3）随机确定[ai]以外的邻居测试用例[a'i]。

b. 用方程式（4）和（5）评估食物源[a'i]；如果[a'i]优于ai，则用其代替ai。如果没有更好的解，则增加尝试次数。

【侦察蜂时期】

c. 确定尝试次数多于终止条件值的测试用例并通过方程式（3）用新的随机测试用例取代它们。

d. cycle = cycle + 1

第6步：While cycle！=终止条件

CSA算法

CSA算法基于布谷鸟下蛋的方法。布谷鸟是在其他鸟的巢下蛋的（Yang & Deb， 2015）。在教育软件测试中使用CSA，布谷鸟的蛋代表测试用例，巢代表教育软件的独立路径，蛋的适应值（fitness）代表测试用例的目标函数值。每一只布谷鸟随机选择其他鸟的一個巢，判断已经存放在里面的蛋的适应值。在这里，适应值代表布谷鸟的蛋与巢里原来的蛋的差别。如果布谷鸟的蛋的适应值优于原来的蛋，布谷鸟就会把那个蛋扔掉，用自己的蛋取而代之。否则，它会继续寻找另一个巢。

CSA算法用于测试的完整伪代码如下：

第1步：初始化终止条件的控制参数。

第2步：用本测试工具的任何测试技术初始化初始种群。

第3步：评估这个种群并把通过新独立路径的测试用例添加到结果集。

第4步：cycle=1

第5步：Do

【布谷鸟时期】

e. 用方程式（3）随机确定一只准备下蛋的布谷鸟（测试用例）[c'i]。

f. 随机找一个巢，即检查测试用例通过哪条独立路径。

【换/扔蛋时期】

g. 用方程式（4）和（5）评估[c'i] ；如果[c'i] 优于原来的蛋（测试用例）[ci ]，则用其代替[ci ]。如果没有更好的解，则寻找另一个巢。

h. cycle = cycle + 1

第6步：While cycle！=终止条件

STEM案例：三角形分类问题

虽然我们对研发的20个教育ICT软件应用程序都进行了测试，限于篇幅，本文以其中一个作为案例，介绍自动化测试工具的运作。

三角形分类问题

这是STEM中数学科目的基础问题，涉及辨识三角形的性质，即是直角三角形、钝角三角形、锐角三角形或不是三角形。2017年初，我们在西班牙拉里奥哈国际大学（Universidad Internacional de La Rioja）工程与技术学院的e-learning和社交网络硕士学位课程中进行软件测试，共有48名学生参加，4名后来退出，实际有44人参加本研究。拉里奥哈国际大学是一所在线大学，工程与技术学院有3，000多名学生，因此能否用合适的教育软件开展STEM科目的教学对学习结果会有重要影响。另一方面，这也与欧洲委员会①和经济合作与发展组织②有关这个问题的指导原则相一致。

我们用三角形分类问题展示ABC和CSA算法的使用。我们首先将这个问题的控制流图和SUT输入测试工具，据此生成测试套件并对所生成的测试套件进行优化。如上所述，这个工具有四种黑盒技术和随机测试技术，这些技术用于生成测试套件。TSO则是用ABC或CSA进行运算。优化的测试套件分别与控制流图和SUT一起生成预期输出和实际输出，通过对这两种输出的比较发现SUT的错误。整个过程如图1所示。

控制流图

控制流图以图形表示SUT的预期输出。本案例的控制流图是手工制作的，然后输入测试工具（见图2）。C0， C1， C2， C3， C4， C5是这个软件应用程序的条件，这些条件导致不同路径的出现。N0， N1， N2， N3， N4， N5， N6， N7， N8， N9， N10和N11代表代码的节点。图2是手工制作的控制流图，图3则是自动化测试工具显示的控制流图。

独立路径：独立路径指的是在控制流图中至少遍历一条没有被其他任何路径遍历过的边的路径。根据图2的控制流图，三角形分类问题的所有独立路径如表1所示。

ABC运算

初始种群

可以用上述任何一种黑盒技术或随机测试生成初始种群。本案例用的是随机技术，规定测试用例数目等于10（随机选择），测试用例和它们的目标值见表2。表中测试用例的三个值a、b和c表示三角形三条边的值，目标值表示的是函数最小化的值。

雇佣蜂第一次迭代

雇佣蜂第一次迭代之后，每一条独立路径只剩下一个测试用例，这是对所有通过相同路径的测试用例的目标值进行比较的结果。目标值最小的测试用例被认为是这条路径最佳的测试用例。

以通过路径N0-N1-N2的两个测试用例为例，它们分别是测试用例1（目标值-189175.5）和测试用例8（目标值-226215.86）（见表2），测试用例8的目标值比测试用例1小，它三边的值分别是a=235，b=65，c=33，被认为比测试用例1更好，因此被储存在记忆中。表3是第一次迭代的结果。

雇佣蜂第二次迭代

在雇佣蜂的第二次迭代中，对第一次迭代保留下来的优化测试用例进行变异。这些测试用例的变异导致新测试用例的产生，雇佣蜂对新测试用例做进一步运算。如果任何测试用例拦截到还没有被其他测试用例遍历过的路径，那么这个测试用例就被保存在与之相应的记忆中。如果发现任何测试用例遍历已经有测试用例通过的路径，那么比较这两个测试用例的目标值，把目标值较小的测试用例储存在记忆中。测试用例的变异和比较用方程式（4）和（5）进行。

以表3通过路径N0-N1-N2的测试用例（a=235， b=65， c=33）为例。用XOR运算对该测试用例的一个值进行变异：

（235）10 = （11101011）2

11101011 XOR 10000000 = 01101011

（01101011）2 = （107）10

产生变异测试用例a=107， b=65， c=33。这个测试用例通过路径N0-N1-N3-N5-N7-N8-N11，因此相应路径的记忆中就增加了这个变异测试用例。表4是第二次迭代的结果。

以此类推，更多的迭代会增强其记忆。图4是用ABC优化测试套件的截图。

CSA运算

初始种群

可以用上述任何一种黑盒技术或随机测试生成初始种群。本案例用的是随机技术，规定测试用例数目等于10，测试用例和它们的目标值见表5。

CSA第一次循环

CSA 第一次循环之后，每一条独立路径只剩下一个测試用例，这是对所有通过相同路径的测试用例的目标值进行比较的结果。目标值最小的测试用例被认为是这条路径最佳的测试用例。

以通过路径N0-N1-N2的三个测试用例为例，它们分别是测试用例2（目标值-838870.2）、4（目标值-798429.0）和6（目标值-1499877.56）（见表5）。这三个测试用例中，测试用例6的目标值最小，它三边的值分别是a=912，b=5，c=857。这个测试用例被认为比其他两个测试用例更好，因此被储存在记忆中。表6是第一次循环的结果。

CSA第二次循环

CSA第二次循环中，测试工具随机从搜索空间选取一个新测试用例。如果发现这个测试用例遍历已经有测试用例通过的路径，那么比较这两个测试用例的目标值，把目标值较小的测试用例储存在记忆中。否则，这个测试用例便保存在与这条路径相应的记忆中。表7是第二次循环的更新数据。

在第二次循环中，随机生成的一个新测试用例遍历路径2。新的循环又发现新测试用例，一旦发现更

好的测试用例，表格会随着持续更新。更多的循环会增强其记忆。图5是用CSA优化测试套件的截图。

实验结果

表8和表9是用ABC和CSA测试20种教育ICT软件应用程序所获得的路径覆盖率和适应值（20种软件应用程序的名单见附录）。

表8和表9是用ABC和CSA对20种教育ICT软件应用程序的测试套件进行优化测试的结果。测试结果显示，用ABC的平均路径覆盖率是90.3%，而CSA的平均覆盖率是75.4%。在优化数据的适应值方面，ABC也优于CSA。这说明在路径覆盖方面ABC的表现优于CSA。另外，研究发现，除了教育ICT软件应用程序3外，总体而言，适应值越高，路径覆盖率越高。应用程序3的适应值更高，但路径覆盖率却更低。这可能是由于CSA的各种限制条件所引起的，它们以较低路径覆盖率换取优质的数据优化。

我们的这个工具在这两种算法的帮助下能以最少的测试用例覆盖最多的路径，这有助于减少测试时间，大大降低测试费用。

用ABC得出这些软件应用程序适应值的标准差是2.69E-5单位，而CSA的标准差是1.14E-7单位。换言之，CSA的结果更加一致但路径覆盖率较低，而ABC的路径覆盖率更好，但结果不如CSA一致。因为在为测试套件选择算法上路径覆盖率是更加可靠的决定因素，因此，在本研究中ABC证明是更好的选择。

结束语

研究局限

虽然我们已经采取一切措施保证研究结果的真实性，但是有些因素可能会影响研究结果的外部和内部效度等。为此，我们在多种教育ICT软件应用程序上测试ABC和CSA方法，减少上述风险。为了避免结果偏差，我们一共测试了20种软件程序。为了使测试工具认为代码没有错误，控制流图必须正确无误，哪怕代码包括一些错误。虽然我们采用随机方法，但是所得到的测试数据是最优化的。有时，路径覆盖率难以达到100%，这是因为可能有些路径生成测试用例的可能性较低。本研究的SUT可能比较大，但测试人员应该使用它的控制流图才能进行测试。本测试工具只能用于用Java技术研发的教育ICT软件应用程序，目前尚未用于其他软件应用程序的测试。其运算速度和表现可能会因平台而异。本测试工具需要Java运行环境。

结论和下一步计划

研究发现，在执行自动化TSO以达成所生成的测试套件最小化却有最大路径覆盖率的目标方面，ABC方法优于CSA方法。案例研究显示，采用这两种算法在本研究的自动化测试工具上测试20种教育ICT软件应用程序，ABC的路径覆盖率平均值为90.3%，而CSA则是75.4%。由此可见，ABC在路径覆盖率上优于CSA，是TSO更可靠的选择。

在今后的研究中，可以运用其他自然启发算法改进我们所提出的这个模型。另外，也可以在各方面混合使用ABC和CSA以获得更好结果。上述算法的TSG输入可以通过其他方法实现自动化，比如决策盒（decision box）或因果法（cause-effect），这些方法提供更少的测试套件输入。

【鸣谢】本研究得到拉里奥哈国际大学通过工程与技术学院（School for Engineering & Technology）（http：//esit.unir.net）和教育创新和技术研究院（Research Institute for Innovation & Technology in Education，简称iTED， http：//research.unir.net/ited）提供的部分资助。

[参考文献]

Afzal， W.， Torkar， R.， & Feldt， R. （2009）. A systematic review of search-based testing for non-functional system properties. Information and Educational software Technology， 51 （6）， 957-976.

Ahmed， B. S.， & Zamli， K. Z. （2011）. A variable strength interaction test suites generation strategy using Particle Swarm Optimization. Journal of Systems and Educational software， 84 （12）， 2171-2185.

Alander， J. T.， Mantere， T.， & Turunen， P. （1998）. Genetic algorithm based educational software testing. In G. D. Smith， N. C. Steele， & R. F. Albrecht （Eds.）， Artificial Neural Nets and Genetic Algorithms， Proceedings of International Conference （ICANNGA97） （pp. 325–328）. Norwich， UK： Springer-Verlag， Wien.

Alshraideh， M.， & Bottaci， L. （2006）. Search-based software test data generation for string data using progtam-specific search operators. Educational software Testing， Verification and Reliability， 16 （3）， 175-203.

Alba， E.， & Chicano， F. （2008）. Observations in using parallel and sequential evolutionary algorithms for automatic educational software testing. Computers and Operations Research， 35 （10）， 3161-3183.

Askarunisa， A.， Prameela， P.， & Ramraj， N. （2009）. DBGEN-Database （Test） GENerator-An Automated Framework for Database Application Testing. International Journal of Database Theory and Application， 2（3）， 27-54.

Barón， H. B.， Crespo， R. G.， Espada， J. P.， & Martínez， O. S. （2015）， Assessment of learning in environments interactive through fuzzy cognitive maps. Soft Computing， 19（4）， pp. 1037-1050.

Beizer， B. （1990）. Educational software Testing Techniques （2nd edition）. New York： Van Nostrand Reinhold.

Bertolino， A. （2007）. Educational software testing research： Achievements， challenges， dreams. In Future of Software Engineering， 2007. FOSE '07 （pp. 85-103）. Minneapolis， MN.

Burnstein， I. （2006）. Practical educational software testing： a process-oriented approach. Springer New York： Springer Science and Business Media.

Chakri， A.， Khelif， R.， Benouaret， M.， & Yang， X. S. （2017）， New directional bat algorithm for continuous optimization problems. Expert Systems with Applications， 69， 159-175.

Clarke， L. A.， （1976）. A system to generate test data and symbolically execute programs. IEEE Transactions on educational software engineering， 3， 215-222.

Deason， W. H.， Brown， D. B.， Chang， K. H.， & Cross， J. H. （1991）. A rule-based educational software test data generator. IEEE Transactions on Knowledge and Data Engineering， 3（1）， 108-117.

Díaz， E.， Tuya， J.， Blanco， R.， & Dolado， J. J. （2008）. A tabu search algorithm for structural educational software testing. Computers and Operations Research， 35 （10）， 3052-3072.

Edvardsson， J. （1999）. A survey on automatic test data generation. In Proceedings of the 2nd Conference on Computer Science and Engineering （pp.21-28）. Linkoping， ECSEL.

Gandomi， A. H.， Yang， X. S.， & Alavi， A. H. （2013）. Cuckoo search algorithm： a metaheuristic approach to solve structural optimization problems. Engineering with computers， 29（1）， 17-35.

Ghiduk， A. S.， & Girgis， M. R. （2010）. Using genetic algorithms and dominance concepts for generating reduced test data. Informatica （Slovenia）， 34（3）， 377-385.

Glover， F. （1997）. Tabu search and adaptive memory educational ICT applications—advances， applications and challenges. In R.S. Barr， R.V. Helgason， & J.L. Kennington （Eds.）， Interfaces in computer science and operations research （pp.1-75）. Norwell， MA： Kluwer Academic Publishers.

Harman， M.， Mansouri， S. A.， & Zhang， Y. （2009）. Search based educational software engineering： A comprehensive analysis and review of trends techniques and applications. Department of Computer Science， Kings College London， Tech. Rep. TR-09-03.

Hermadi， I.， Lokan， C.， & Sarker， R. （2010）. Genetic algorithm based path testing： challenges and key parameters. In Educational software Engineering （WCSE）， 2010 Second World Congress on IEEE Vol. 2 （pp. 241-244）. Wuhan， China.

Huang， C. Y.， & Kuo， S. Y. （2002）. Analysis of incorporating logistic testing-effort function into educational software reliability modeling. IEEE Transactions on Reliability， 51（3）， 261-270.

Jamil， M.， & Yang， X. S. （2013）. A literature survey of benchmark functions for global optimisation problems. International Journal of Mathematical Modelling and Numerical Optimisation， 4（2）， 150-194.

Jiang， S.， Shi， J.， Zhang， Y.， & Han， H. （2015）. Automatic test data optimization based on reduced adaptive particle swarm optimization algorithm. Neuro computing， 158， 109-116.

Karaboga， D. （2005）. An idea based on honey bee swarm for numerical optimization （Vol. 200）. Technical report-tr06， Erciyes University， engineering faculty， computer engineering department.

Karaboga， D.， & Basturk， B. （2007）. Artificial bee colony （ABC） optimization algorithm for solving constrained optimization problems. In P. Melin， O. Castillo， L. T. Aguilar， & W. Pedrycz （Eds.）， Foundations of Fuzzy Logic and Soft Computing （pp.789-798）. Berlin Heidelberg： Springer.

Khari， M.， & Kumar， P. （2016）. A novel approach for educational software test data generation using cuckoo algorithm. In Proceedings of the Second International Conference on Information and Communication Technology for Competitive Strategies （p. 98）. ACM.

Korel， B. （1990）. Automated educational software test data generation. Educational software Engineering， IEEE Transactions on， 16（8）， 870-879.

Korel， B.， & Al-Yami， A. M. （1998）. Automated regression test optimization. ACM SIGSOFT Educational software Engineering Notes， 23 （2）， 143-152.

Kumar， A.， & Chakarverty， S. （2011， May）. Design optimization using genetic algorithm and cuckoo search. In 2011 IEEE International Conference on Electro/Information Technology （EIT） （pp. 1-5）. IEEE.

Li， H.， & Lam， C. P. （2004）. Educational software Test Data Optimization using Ant Colony Optimization. In International Conference on Computational Intelligence （1-4）.

Lim， A.， Rodrigues， B.， & Zhang， X. （2006）. A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research， 174 （3）， 1459-1478.

Luo， J.， Liu， Q.， Yang， Y.， Li， X.， Chen， M. R.， & Cao， W. （2017）. An artificial bee colony algorithm for multiobjective optimisation. Applied Soft Computing， 50， 235-251.

Mala， D. J.， Mohan， V.， & Kamalapriya， M. （2010）. Automated educational software test optimisation framework-an artificial bee colony optimisation-based approach. IET educational software， 4（5）， 334-348.

Mann， M. （2015）. Generating and prioritizing optimal paths using ant colony optimization. Computational Ecology and Educational software， 5 （1）， 1.

Marciniak， J. J. （1994）. Encyclopedia of educational software engineering. New York： Wiley-Interscience.

Markman， K. D.， McMullen， M. N.， & Elizaga， R. A. （2008）. Counterfactual thinking， persistence， and performance： A test of the reflection and evaluation model. Journal of Experimental Social Psychology， 44 （2）， 421-428.

Miller， E. F. （1981）. Introduction to educational software testing technology. Tutorial： Educational software Testing and Validation Techniques. Second Edition， IEEE Catalog No. EHO， （pp. 180-200）.

Meza， J.， Espitia， H.， Montenegro， C.， & Crespo， R. G. （2015）， Statistical analysis of a multi-objective optimization algorithm based on a model of particles with vorticity behaviour. Soft Computing. Retrieved from https：//www.springerprofessional.de/statistical-analysis-of-a-multi- objective-optimization-algorithm/7001512

Meza， J.， Espitia， H.， Montenegro， C.， Giménez， E.， & González-Crespo， R.， （2017）. MOVPSO： Vortex Multi-Objective Particle Swarm Optimization. Applied Soft Computing， 52， 1042-1057.

Michael， C. C.， McGraw， G. E.， Schatz， M. A.， & Walton， C. C. （1997）. Genetic algorithms for dynamic test data optimization. In Automated Educational software Engineering， 1997. Proceedings in 12th IEEE International Conference IEEE （pp. 307-308）.

Poon， P. L.， Tse， T. H.， Tang， S. F.， & Kuo， F. C. （2011）. Contributions of tester experience and a checklist guideline to the identification of categories and choices for educational software testing. Educational software Quality Journal， 19 （1）， 141-163.

Pressman， R. S. （2005）. Educational software engineering： a practitioner's approach. McGraw Hill， New York： Palgrave Macmillan.

Radatz， J.， Geraci， A.， & Katki， F. （1990）. IEEE standard glossary of educational software engineering terminology. IEEE Std， 610121990（121990）， 3.

Ramchoun， H.， Amine， M.， Idrissi， J.， Ghanou， Y.， & Ettaouil， M.， （2016）. Multilayer Perceptron： Architecture Optimization and Training. International Journal of Interactive Multimedia and Artificial Intelligence， 4（1）， 26-30.

Ricca， F.， & Tonella， P. （2001）. Analysis and testing of web applications. In Proceedings of the 23rd international conference on Educational software engineering， IEEE Computer Society （pp. 25-34）.

Sakti， A.， Pesant， G.， & Guéhéneuc， Y.G.， （2015）. Instance generator and problem representation to improve object oriented code coverage. IEEE Transactions on Educational software Engineering， 41 （3）， 294-313.

Semwal， V. B.， Singha， J.， Sharma， P. K.， Chauhan， A.， & Behera， B. （2017）. An optimized feature selection technique based on incremental feature analysis for bio-metric gait data classification Multimedia Tools and Applications， 76 （22）， 24457-24475.

Singh， Y. （2015）. Automated Expected Output Generation： Is this a Problem that has been solved？. ACM SIGSOFT Educational software Engineering Notes， 40（6）， 1-5.

Sommerville， I.， （2001）. Educational software Engineering （6th ed.）. Boston， USA. Addison-Wesley.

Sthamer， H. H. （1995）. The automatic optimization of educational software test data using genetic algorithms. Doctoral dissertation， University of Glamorgan.

Tassey， G. （2002）. The economic impacts of inadequate infrastructure for educational software testing. National Institute of Standards and Technology， RTI Project， 7007 （011）. Retrieved from https：//www.nist.gov/sites/default/files/documents/director/planning/report02-3.pdf

Wegener， J.， Baresel， A.， & Sthamer， H. （2001）. Evolutionary test environment for automatic structural testing. Information and Educational software Technology， 43 （14）， 841-854.

Whittaker， J. A. （2000）. What is educational software testing？ And why is it so hard？. IEEE educational software， 17 （1）， 70-79.

Yang， X. S.， & Deb， S. （2009）. Cuckoo search via Lévy flights. In. World Congress on Nature & Biologically Inspired Computing （pp. 210-214）. IEEE.

Yang， X. S.， & Deb， S. （2015）. Cuckoo Search for Optimization and Computational Intelligence. IGI Global.

Zamli， K.Z.， Alkazemi， B.Y.， & Kendall， G.， （2016）. A Tabu Search hyper-heuristic strategy for t-way test suite optimization. Applied Soft Computing， 44， 57-74.

附录：本研究测试的20种教育ICT软件应用程序

Triangle classification： right angled， acute angled or obtuse angled

Maximum number among 3 numbers

Division of students based on marks

Valid triangle or not

Triangle classification： equilateral， scalene， isosceles

Class of the given network address

Leap year or not

Type of radiations by frequency

PHRASO-MATIC Game

Day of the date （Mon， Tues， etc.）

Find the types of roots of a quadratic equation （real/imaginary/equal）

Linear Search

Binary Search

Find if three numbers form a Pythagorean triplet or not

Find if a string is a part of a given input string

Find the quadrant of the points entered by the user

Find if the number entered by the user is perfect or not

Find the input given by a user is alphabet， special character or a character

Convert a number to binary or hexadecimal or octal depending upon the choice entered by the user

Find if a number entered by the user is Armstrong or not.

收稿日期：2018-01-15

定稿日期：2018-02-05

作者简介：鲁宾·冈萨雷斯·克雷斯波（Rubén González Crespo）博士，西班牙拉里奥哈国际大学（Universidad Internacional de La Rioja）高等工程学院院长，西班牙标准化和认证协会（Spanish Association for Standardization and Certification）会长，认证、质量和技术标准讲席，哥伦比亚教育部顾问委员会委员，西班牙国家质量评估与鉴定署（National Agency for Quality Evaluation and Accreditation of Spain）評估专家，国际标准组织（ISO）多个委员会的委员，《交互多媒体和人工智能国际期刊（International Journal of Interactive Multimedia and Artificial Intelligence）》主编，主持多个欧洲委员会和西班牙教育部资助的课题，发表150多篇论文。

普拉波哈特·库马（Prabhat Kumar）博士，印度巴特那国家技术学院（National Institute of Technology， Patna）助理教授，学院IT服务部主管教授，多家国际期刊编委和审稿人，曾在多家著名大学和机构工作，在国内外期刊发表35篇同行评审的论文，研究兴趣包括：无线传感网络、物联网、操作系统、软件工程、电子政务等。

曼珠·卡里（Manju Khari）博士，印度安贝德卡高级通信技术与研究研究院（Ambedkar Institute of Advanced Communication Technologies and Research）助理教授，多家国际期刊编委和审稿人，在国内外期刊发表近百篇同行评审的论文，出版合著两部，研究兴趣包括：软件测试、软件质量、软件度量、信息安全和自然启发算法。

丹尼尔·布尔戈斯（Daniel Burgos）博士，西班牙拉里奥哈国际大学副校长（知识、转移和技术）、教授、教育创新和技术研究院院长，联合国教科文组织e-learning教席，国际远程开放教育理事会开放教育资源（OER）教席；曾任拉里奥哈国际大学工程学院院长，源讯研究与创新部教育处总监和用户体验实验室主任，荷兰开放大学副教授；参与40多个欧盟资助课题，发表120多篇论文；拥有四个博士学位，分别是传播学博士、计算机科学博士、教育博士和人类学博士。

译者简介：肖俊洪，汕头广播电视大学教授，Distance Education （Taylor & Francis）期刊副主编，System： An International Journal of Educational Technology and Applied Linguistics （Elsevier）期刊编委（515041）。https：//orcid.org/0000- 0002- 5316-2957

责任编辑 郝 丹 单 玲

编 校 韩世梅