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

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

2、助， 但没有改变传统的灌输式学习方式， 没有真 正提升学生对各种媒介的解读、运用能力”。在我看来，这就是 典型的“伪融合”。本期“国际论坛”四位作者分别来自西班牙和印度的远程 在线教学大学和普通高校（研究院），均在技术与教育的融合领 域颇有建树，其中通信作者丹尼尔 ?布尔戈斯教授是西班牙拉里 奥哈国际大学主管研究和技术的副校长， 也是联合国教科文组织 e-learning 教席和国际远程开放教育理事会开放教育资源 （OER） 教席， 一个真正具有跨学科学术背景的学者。 他曾经在我们的通 信中阐述他的教育科研理念。他认为作为在线教学机构的一员， 自己的研究责无旁贷应该扎根具体教育实践， 以解决实

3、际教育教 学问题为首要目的。 他说学术研究应该接地气， 应该能够赋权于 教师， 就技术的教育用途而言， 研究成果应该能为并非技术行家 的教师所用，而且能提高教学效果、达成预期学习目标，否则谈 不上“融合”。 他本人一直身体力行， 比如有关适合大规模招生 的e-learning 推荐模型的研究，也许正因为他有这样的理念 而且又取得了丰硕成果， 所以才被联合国教科文组织和国际远程 开放教育理事会委以要职。本文介绍他们的一项新研究成果，即教育软件的自动化测 试。在今天这个信息时代，教育软件无处不在，从某种意义上讲 已经成为当今教育教学不可或缺的组成部分， 甚至可以说很多学 科的教学离不开教育软件的应

4、用。 比如在生物、 医学和护理等专 业的学习中， 教育软件能给学习者提供虚拟现实或增强现实， 大 大提高学习活动的真实性， 完成很多在传统教学环境下很难开展 的学习任务；而在机械、工程和建筑等专业的学习中，学习者使 用这些软件开展设计、运算、建模、试验等活动，即使失败了也 不会造成任何经济损失或伤害。 对于远程在线学习来讲， 教育软 件的用途更是非常广泛， 其对提高学习效果、 保证教学质量的重 要性更是自不待言。随着用途越来越广泛，教育软件也越来越大、越来越复杂， 因此，“改进教育软件开发技术， 加快开发过程， 提高开发效率， 这些都势在必行。高效的软件开发过程应该是快捷、容易操作、 稳健和低

5、成本的”。 这其中便涉及软件测试， 这是“教育软件开 发最具挑战性的阶段”。 “教育软件测试在软件开发生命周期的 早期进行，越是往后才发现的错误，修复的成本越高”，但是这 也是一项非常复杂的工作，手工操作费时耗力、成本高昂，且不 说可行性的问题。因此，本研究在系统回顾（教育）软件测试研 究成果的基础上， 研发一种自动化测试工具， 即测试套件生成和 测试套件优化。本研究提出的自动化测试工具自身配备四种黑盒技术 （即边 界值测试、稳健性测试、最坏情况测试和稳健最坏情况测试）以 及随机测试技术。 可以用其中任何一种技术生成测试对象教育软 件的测试数据， 然后用人工蜂群算法和布谷鸟搜索算法优化这些 数

6、据，再把优化的测试套件应用于测试对象软件上以生成实际输 出，而测试对象软件的控制流图则会产生预期输出， 如果实际输 出和预期输出不一致， 则说明这个软件有错误。 在阐明这种自动 化测试工具的工作原理之后， 文章还介绍了人工蜂群算法和布谷 鸟搜索算法。本研究用这个自动化测试工具对 20 个教育软件应用程序进 行测试。软件测试是在西班牙拉里奥哈国际大学工程 ?c 技术学 院的 e-learning 和社交网络硕士学位课程中进行的， 有 44 名学 生参加。限于篇幅，本文以三角形分类问题的软件应用程序为例， 介绍自动化测试工具的运作和实际效果。 测试结果表明， 这个自 动化测试工具在人工蜂群算法和布

7、谷鸟搜索算法的帮助下能以 最少的测试用例覆盖最多的路径， 减少测试时间， 降低测试费用， 换言之，大大提高测试效率。研究还发现，两种算法有各自的优 点，布谷鸟搜索算法的结果更加稳定但路径覆盖率较低， 而人工 蜂群算法的路径覆盖率更好，但结果不如布谷鸟搜索算法稳定。 考虑到路径覆盖率是选择测试套件算法更加可靠的决定因素， 因 此，在本研究中，与布谷鸟搜索算法相比，人工蜂群算法是一个 更好的选择。文章最后还指出本研究的局限和今后研究方向。这篇文章的意义不仅体现在研发一种教育软件自动化测试 工具上，也是技术与教育融合的一个很好的例子。 对远程（在线） 教育工作者而言，它更是布尔戈斯教授的教育科研观的

8、具体体 现。我认为这也是值得远程（在线）教育机构和实践者认真谋划 和努力的一个科研方向把技术与教育的融合扎根于远程 （在 线）教育实践中，旨在解决实际教学问题，达成具体教学目标。 最后，衷心感谢四位国际同行对本刊的支持！（肖俊洪）引言 过去五十年，教育软件无所不在，对教育的影响越来越大， 因此，人们对可靠教育软件的需求与日俱增。 教育软件的用途广 泛，几乎涉及我们生活的每一个方面，因此软件越来越复杂、越 来越大。在这种背景下， 改进教育软件开发技术， 加快开发过程， 提高开发效率， 这些都势在必行。 高效的软件开发过程应该是快 捷、容易操作、稳健和低成本的。教育软件的质量通过在软件开发生命周期

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

10、是教 育软件工程最复杂和较不为人所了解的领域之一（ 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 ， 199

11、5），原因包括检测故障、最大限度降低与教育软件残余错误 相关的风险（ Askarunisa ， Prameela ， & Ramraj ， 2009 ）和 对软件进行全面彻底测试（ Huang & Kuo， 2002 ）等。在测试阶 段发现的系统错误多数产生自软件开发生命周期的早期 （ Beizer ， 1990 ），因此，教育软件测试应在软件开发生命周 期的早期进行，越是往后才发现的错误，修复的成本越高。测试 被认为是教育软件开发最具挑战性的阶段， 占用全部开发时间和费用的 50%- 60% (Bertoli no , 2007 )。教育软件测试可以手工进行，也可以通过自动化方式进行， 目的

12、是验证该软件是否符合工作或客户要求， 也用于检查实际结 果与预期输出是否一致( Radatz ， Geraci ， & Katki ， 1990 )。 这种测试通过使用合适的测试用例( test case )检验软件是否 符合要求， 以此评估其质量。 有些错误是在设计阶段因疏忽而引 起的，这些错误应该立即得到修复。 教育软件测试的目标是生成 包含精确测试用例并能达成最大覆盖率和尽可能发现更多错误 的最小测试套件( test suite )( Sthamer ， 1995 )。在此过程 中，每一个测试用例都是不同的； 每一个测试用例都配上一组输 入和一系列预期输出。测试的另一个任务是生成合适的测

13、试套 件，以满足测试标准，比如代码覆盖( code coverage )( Sakti ， Pesant,& Gue he neuc,2015 )、路径覆盖(path coverage )、分支覆盖( branch coverage )( Sthamer， 1995 )和语句覆盖( statement coverage )( Clarke ， 1976 )。这方面已经有一 些测试标准， 必须满足相关标准才能保证所测试的教育软件的质 量( Ghiduk & Girgis ， 2010)。教育软件的全面测试很难手工 进行，有些方面必须实现自动化。手工生成测试套件更加耗时耗力， 这是一个劳动密集型而

14、又 昂贵的过程， 因此必须减少人工测试量 (Poon， Tse， Tang， & Kuo， 2011 )。自动化测试能加快测试过程，节省时间和成本， 达成最大覆盖率。 此外， 测试过程的自动化还能显著降低软件开发维护费用，提高其可靠性。美国国家标准与技术研究院( National Institute of Standards and Technology )的研究表明，软件测试基础设施不 完善所造成的损失每年估计在 222亿到 595亿美元之间( Tassey， 2002)。由此可见，必须优化测试过程，才能既减少对资源的要 求(时间、经费和人力等)又保证质量。早期的教育软件技术开 发采用爬山(

15、 hill climbing )算法(属于梯度下降算法 gradient descent algorithms 一族)生成测试用例和测试套件( Korel ， 1990)。这些方法很耗时且无法避免搜索空间的局部最优解 ( local optima )。后来，人们使用元启发式搜索算法 ( metaheuristic search algorithms)解决这个问题( Edvardsson ，1999 ；Wegener，Baresel ，& Sthamer ，2001 )， 比如禁忌搜索算法(Tabu Search) (Di az, Tuya , Bia neo , & Dolado， 2008

16、；Glover ， 1997 ；Zamli ， Alkazemi ， & Kendall ， 2016)、模拟退火算法 ( Simuiated Anneaiing )( Lim， Rodrigues ， & Zhang， 2006 )、遗传算法( Genetic Aigorithm ， GA( Aiander ， Mantere ， & Turunen ， 1998 ； Hermadi ， Lokan ， & Sarker ， 2010； Maia ， Mohan， & Kamaiapriya ， 2010 )、粒子群优化 算法( Particie Swarm Optimization ， P

17、SO)( Ahmed & Zamii， 2011； Jiang ， Shi ， Zhang ， & Han ， 2015 )和蚁群优化算 法(Ant Colony Optimization , ACO (Li & Lam, 2004 ； Markman, McMuiien， & Eiizaga ， 2008)。每一种算法都有自己的优缺点。工程界不同领域对基于搜索的算法已 ?开展了广泛研究、实 验和应用（ Afzal ， Torkar ， & Feldt ， 2009 ； Harman， Mansouri ， & Zhang， 2009 ）。测试边界值不足以确保教育软件的准确， 因为所有可能的值

18、都必须测试和验证， 但这是 行不通的。要对一种教育 ICT 软件应用程序进行全面测试， 只增 加两个 32-bits 整数输入就要求测试 264 个不同测试用例，即 使每秒钟完成数千次测试， 这个量的测试也需要数百年时间才能 做完。因此，必须实现测试套件优化 （ Test Suite Optimization ， TSO。TSO是去除不必要、多余的测试用例，把优质测试用例 纳入测试套件中的过程，在这里，优质指的是在路径覆盖率、错 误检测和代码覆盖率方面表现好。TSO从其测试用例母集中发现最好的子集。 本研究采用人工蜂群算法 （ArtificialBee ColonyAlgorithm , AB

19、C 和布谷鸟搜索算法（Cuckoo Search Algorithm ， CSA实现TSO这两种算法都是受到大自然启发的算法（Karaboga， 2005； Yang & Deb ， 2009 ） 。研究背景符号和术语 被测试的教育软件（ Educational Software Under Test ， SUT的控制流或逻辑可以通过控制流图（flow graph ）表示。 控制流图由节点（N和边（E）组成，即G （N, E ）。用控制 流图表示SUT逻辑，节点代表语句块，边代表从一个节点转移到 另一个节点的流向，形成一条路径。基于控制流图有限的节点， 可以发现独立路径(independent

20、 path )。控制流图与SUT的实 际逻 ?相似。因此，对一个控制流图的测试数据进行的运算被看 作对教育 ICT 软件应用程序的运算。 这个软件应用程序的特点应 该体现在其控制流图中。路径测试标准 一般而言，路径测试包括挑选一组合适的路径并用测试数据 检测这些路径。 这是一个迭代过程， 直至完成对所有路径的测试。 但是，一个控制流图的所有路径并非都能通过遍历， 这些路径被 称为“不可行路径”。 路径覆盖率即被成功遍历的路径除以全部 路径所得之百分比，如方程式( 1)所示： 路径覆盖率 %=被成功遍历的独立路径数独立路径总数x 100% eq. ( 1)文献回顾科瑞尔( Korel ， 199

21、0 )根据路径覆盖测试标准，采用包含 各种可能的测试数据的动态路径测试技术生成教育软件测试数 据，目的是获取执行期望路径的测试用例值。迪森等(Deason，Brown， Chang， & Cross ， 1991 )提出基于规则的测试数据生 成方法，采用路径 / 谓词分析或随机测试数据生成法。他们认为 因为测试用例可能无法覆盖所有路径，应该对测试套件进行优 化。卡拉博加( Karaboga， 2005 )根据蜜蜂群智能觅食行为， 提出一种新的人工蜂群算法解决多维度和多模态问题。 卡拉博加 和巴斯图尔克( Karaboga & Basturk ， 2007 )后来又提出 ABC算法解决约束优化问

22、题。罗等(Luo, Liu , Yang , Li , Chen, & Cao, 2016 )提出一种称为ABCS盖阵列生成器(covering array generator )的新算法，生成覆盖阵列和结对测试的混合 覆盖阵列。测试用例优先级排序( Test case prioritization ) 指的是重新排列测试用例执行顺序, 以在某一特定时间段尽可能 发现更多错误。 作者们还进一步提出一种高效的多目标蚁群优化 方法( multi-objective ant colony optimization)解决多目标和高维多目标问题( multi-objective and many-obj

23、ective problems )。这种技术基于帕累托占优和偏好指标( Pareto dominance and preference indicators ),使外部包( external archives )在每一次生成中产生一种有效的解。杨和戴布(Yang & Deb，2015 )提出CSA算法解决包括 NP-hard 问题的优化问题,而甘多米等( Gandomi, Yang, & Alavi，2013)则用CSA在没有调整测试参数的情况下解决结构 问题，使CSA成为像PSO-样的稳健且更加通用的应用程序(Meza, Espitia , Montenegro , Gime nez, &G

24、onzd lez-Crespo , 2016 )。库玛和查克拉瓦蒂(Kumar & Chakarverty , 2011 )使用GA和 CSA设计嵌入式系统空间探索 问题。CSA无需对参数调整进行过多试验便能够在更短时间内产 生更好的种群。在对SUT更长时间运算之后通过 GA获得最佳解。 因此，CSA能在更短运算时间内高效生成某一个问题的多种解， 而GA则在求最佳解方面效果最好。拉姆邹恩等( RamchounAmine， Idrissi ， Ghanou， & Ettaouil ， 2016 )采用 GA， 用反向传播算法( back-propagation algorithm )训练网络以优

25、 化网络问题。马拉等( Mala， Mohan， & Kamalapriya ， 2010 )提出一 种新的教育软件测试优化范式， 采用基于混合智能的搜索方法达 成教育软件测试最优化。这个框架的优点是自动生成测试用例， 发现最优测试顺序，减少测试用例数量和把测试次数降到最低。迈克尔等(Michael , McGraw, Schatz , & Walton, 1997) 提出基于启发式搜索技术的方法解决教育软件测试的各种问题， 他们通过在各种软件应用程序中使用GA和随机测试技术生成测试数据，比较这两种技术，发现 GA 生成更有效的测试数据。卡里和库玛(Khari & Kumar，2016 )提出

26、基于TSO搜索的 方法，把局部搜索和全局搜索结合起来，在更短时间、迭代次数 更少而空间复杂性的增加可以忽略不计的情况下获得最优结果。 辛格(Singh，2015)的结论肯定自动化生成预期输出的重要性， 因为与人工操作相比，这样能够大大降低费用和时间。但是，目 前还没有合适、完整和稳健的技术。巴朗等(Bar o n,Crespo, Espada ,& Mart i nez, 2015 )提出一个学习考核框架,该框架包括结构方程模型和模糊认知图,旨在促进智慧环境下的学习评价。森沃尔等(Semwal, Singha , Sharma, Chauhan , & Behera ， 2016 )使用不同机

27、器学习技术(如支持向量机、人 工神经网络、KNN分类算法和分类器融合等)发现机器学习的原 理和分类步态数据。 梅扎等( Meza， Espitia ， Montenegro ， & Crespo， 2015 )提出像旋转和直线运动这样的多目标优化(multi-objective optimizatio n )策略，该策略建立在 PSO和 探索与利用(E &E)结果的基础上。查克里等(Chakri , Khelif , Benouaret ， & Yang ， 2017 )提出一种修改的蝙蝠算法( bat algorithm )解决某些情况下基础蝙蝠算法探索能力低所引起的 优化问题，提高该算法在

28、探索和利用方面的效率。本文尝试从不同角度研发一种自动化测试工具， 即测试套件 生成(Test Suite Generation ,TSG 和测试套件优化(Test Suite Optimization ， TSO)。自动化测试工具的框架 自动化测试模型 本模型的测试套件生成包含四种黑盒技术，即边界值测试( boundary value testing )、稳健性测试( robustness testing )、最坏情况测试( worst case testing )和稳健最坏 情况测试( robustness worst case testing )，以及随机测试( random testin

29、g )。图 1 是其完整框架。我们可以用其中任何 一种技术生成SUT的测试数据，然后用ABC或CSA寸这些数据进 行优化，将优化的测试套件应用于SUT上会生成实际输出，而SUT的控制流图则会产生预期输出，通过比较实际输出和预期输 出发现SUT的错误。这个框架的组成部分如下：?输入：控制流图和 SUT。?处理模块：采用上述测试技术完成TSG由于所生成的测试套件可能会也可能不会对 SUT有 100%勺路径覆盖，因此将其 输入第二阶段，即TSQ这个阶段是在ABC和CSA帮助下完成的， 最终获得优化测试套件。?错误检测：将生成的测试套件与控制流图和SUT一起使用，分?e获得预期输出和实际输出。如果两种

30、输出不一致，则说明 SUT有错误。ith 测试用例的方程式如下：xi=ti1 , ti2 , ti3 ,tik ,tiNwhere 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 )时产生 新的随

31、机测试用例。变异函数从这些位中选择一个并加以扰动。 在方程式( 3)中， xi 是输入的测试用例， yi 是变异测试用例：yi= mutate ( xi ) eq. ( 3)如果已存在和变异测试用例的独立路径相同， 那么根据马提 亚斯( Matyas )目标函数的值选择其中一个测试用例( Jamil & Yang， 2013 )，如方程式( 4)和( 5)所示：* j=1Ntij ) eq.For xi ， p = ( 0.26 * i=1Nt2ij-0.48 （4）For yi ， q = （0.26 * i=1Nt2ij-0.48 * j=1Ntij ） eq.（5）如果 p q ， 那么

32、xi 是比 yi 更好的测试用例否则，yi 是比 xi 更好的测试用例结束分支。ABC算 法ABC算法基于蜜蜂群的智能行为，包括三种平行工作的蜂： 雇佣蜂、观察蜂和侦察蜂。雇佣蜂的数量与观察蜂的数量相同， 等于SM我们必须界定该算法的终止条件，通过重复以下步骤 寻找每一个食物源 ai ：1. 随机确定食物源 ai 以外的邻居食物源 ai。2用目标函数评估邻居食物源ai，如果ai优于ai， 则用其代替 ai 。否则，把尝试次数增加一次。在侦察蜂时期， 放弃尝试次数多于终止条件值的食物源， 改 用另一个随机食物源。ABC算法提供全局搜索，最终把有最佳目 标函数值的食物源储存在记忆中。ABC算法用于

33、测试的完整伪代码如下：第1步：初始化ABC空制参数。第 2 步：用本测试工具的任何测试技术初始化初始种群。第 3 步：评估这个种群并把通过新独立路径的测试用例添加 到结果集。第 4 步： cycle=1第 5 步： Do【雇佣蜂和观察蜂时期】a. 用方程式 （3）随机确定 ai 以外的邻居测试用例 aib. 用方程式（ 4）和（ 5）评估食物源 ai ；如果 ai 优 于 ai ，则用其代替 ai 。如果没有更好的解，则增加尝试次数。【侦察蜂时期】c. 确定尝试次数多于终止条件值的测试用例并通过方程式 （3）用新的随机测试用例取代它们。d. cycle = cycle + 1第6步：While

34、 cycle !=终止条件CSA算法CSA算法基于布谷鸟下蛋的方法。布谷鸟是在其他鸟的巢下 蛋的（Yang & Deb，2015 ）。在教育软件测试中使用 CSA布 谷鸟的蛋代表测试用例， 巢代表教育软件的独立路径， 蛋的适应 值（ fitness ）代表测试用例的目标函数值。每一只布谷鸟随机 选择其他鸟的一巢， 判断已经存放在里面的蛋的适应值。 在这里， 适应值代表布谷鸟的蛋与巢里原来的蛋的差别。 如果布谷鸟的蛋 的适应值优于原来的蛋， 布谷鸟就会把那个蛋扔掉， 用自己的蛋 取而代之。否则，它会继续寻找另一个巢。CSA算法用于测试的完整伪代码如下：第 1 步：初始化终止条件的控制参数。第 2

35、 步：用本测试工具的任何测试技术初始化初始种群。第 3 步：评估这个种群并把通过新独立路径的测试用例添加 到结果集。第 4 步： cycle=1第 5 步： Do【布谷鸟时期】e. 用方程式（ 3）随机确定一只准备下蛋的布谷鸟（测试用 例） ci 。f. 随机找一个巢，即检查测试用例通过哪条独立路径。【换/ 扔蛋时期】g. 用方程式（ 4）和（ 5）评估 ci ；如果 ci 优于原 来的蛋（测试用例） ci ，则用其代替 ci 。如果没有更好的 解，则寻找另一个巢。h. cycle = cycle + 1第 6 步： While cycle ！ =终止条件STEM案例：三角形分类问题虽然我们对

36、研发的 20个教育 ICT 软件应用程序都进行了测 试，限于篇幅，本文以其中一个作为案例，介绍自动化测试工具 的运作。三角形分类问题这是STEM中数学科目的基础问题，涉及辨识三角形的性质，即是直角三角形、钝角三角形、锐角三角形或不是三角形。 2017 年初，我们在西班牙拉里奥哈国际大学( Universidad Internacional de La Rioja)工程与技术学院的 e-learning 和社交网络硕士学位课程中进行软件测试， 共有 48 名学生参加， 4 名后来退出，实际有 44 人参加本研究。拉里奥哈国际大学是一 所在线大学，工程与技术学院有 3， 000 多名学生，因此能否

37、用 合适的教育软件开展 STEM科目的教学对学习结果会有重要影 响。另一方面， 这也与欧洲委员会和经济合作与发展组织有 关这个问题的指导原则相一致。我们用三角形分类问题展示 ABC和CSA算法的使用。我们首 先将这个问题的控制流图和 SUT俞入测试工具，据此生成测试套 件并对所生成的测试套件进行优化。 如上所述， 这个工具有四种 黑盒技术和随机测试技术，这些技术用于生成测试套件。TSO则是用ABC或CSA进行运算。优化的测试套件分别与控制流图和 SUT一起生成预期输出和实际输出，通过对这两种输出的比较发 现SUT的错误。整个过程如图1所示。控制流图控制流图以图形表示 SUT的预期输出。本案例的

38、控制流图是 手工制作的， 然后输入测试工具 (见图 2)。 C0， C1 ， C2， C3， C4， C5 是这个软件应用程序的条件，这些条件导致不同路径的 出现。 N0， N1， N2， N3， N4， N5， N6， N7， N8， N9， N10 和N11代表代码的节点。图2是手工制作的控制流图， 图3则是 自动化测试工具显示的控制流图。独立路径：独立路径指的是在控制流图中至少遍历一条没有 被其他任何路径遍历过的边的路径。 根据图 2的控制流图， 三角 形分类问题的所有独立路径如表 1 所示。ABC运算初始种群 可以用上述任何一种黑盒技术或随机测试生成初始种群。 本 案例用的是随机技术，

39、规定测试用例数目等于10（随机选择），测试用例和它们的目标值见表 2。表中测试用例的三个值 a、b 和 c 表示三角形三条边的值，目标值表示的是函数最小化的值。雇佣蜂第一次迭代 雇佣蜂第一次迭代之后， 每一条独立路径只剩下一个测试用 例，这是对所有通过相同路径的测试用例的目标值进行比较的结 果。目标值最小的测试用例被认为是这条路径最佳的测试用例。以通过路径NO-N1-N2的两个测试用例为例，它们分别是测试用例 1（目标值 -189175.5 ）和测试用例 8（目标值 -226215.86 ） （见表 2），测试用例 8 的目标值比测试用例 1 小，它三边的值 分别是a=235, b=65, c

40、=33，被认为比测试用例1更好，因此被 储存在记忆中。表 3 是第一次迭代的结果。雇佣蜂第二次迭代 在雇佣蜂的第二次迭代中， 对第一次迭代保留下来的优化测 试用例进行变异。这些测试用例的变异导致新测试用例的产生， 雇佣蜂对新测试用例做进一步运算。 如果任何测试用例拦截到还 没有被其他测试用例遍历过的路径， 那么这个测试用例就被保存 在与之相应的记忆中。 如果发现任何测试用例遍历已经有测试用 例通过的路径， 那么比较这两个测试用例的目标值， 把目标值较 小的测试用例储存在记忆中。测试用例的变异和比较用方程式 （4）和（ 5）进行。以表3通过路径N0-N1-N2的测试用例（a=235, b=65

41、, c=33 ）为例。用XOR运算对该测试用例的一个值进行变异：（235） 10 =（11101011） 211101011 XOR 10000000 = 01101011（01101011） 2 = （107） 10产生变异测试用例 a=107， b=65， c=33 。这个测试用例通过路径NO-N1-N3-N5-N7-N8-N11，因此相应路径的记忆中就增加 了这个变异测试用例。表 4 是第二次迭代的结果。以此类推，更多的迭代会增强其记忆。 图4是用ABC优化测 试套件的截图。CSA运算初始种群 可以用上述任何一种黑盒技术或随机测试生成初始种群。 本 案例用的是随机技术，规定测试用例数目等

42、于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。新的循环又发现新测试用例，一旦发现更好的测试用例， 表格会随着持续更新。 更多的循环会增强