收稿日期： ２０１１唱０９唱１５； 修回日期： ２０１１唱１０唱２６　　基金项目： 国家自然科学基金资助项目（６０９７３１１８） 作者简介： 聂鹏（１９７７唱），男，陕西汉中人，博士研究生，主要研究方向为软件确保、软件测试、软件可靠性（ ｚｅａｎｅｔ ＠１６３． ｃｏｍ ）；耿技（１９６３唱）， 男，安徽合肥人，教授，博士研究生，主要研究方向为系统软件、软件确保、软件可靠性；秦志光（１９５６唱），男，四川隆昌人，教授，博导，主要研究方向 为计算机开放系统与网络安全性、信息系统安全． 软件 测试 用 例自 动生 成算 法综 述 倡 聂　鹏１，２ ， 耿　技１ ， 秦志光１ （１．电子科技大学 计算机科学与工程学院， 成都 ６１１７３１； ２．江西财经大学， 南昌 ３３００１３） 摘　要： 按照测试用例自动生成技术的不同，将测试用例自动生成算法分为随机、遗传、蚁群、粒子群四类，对上述 各类算法的现状和进展进行介绍、分析和探讨。 最后，对软件测试用例自动生成的研究进行了总结。 关键词： 软件测试； 测试用例生成； 随机测试； 启发性测试 中图分类号： ＴＰ ３１１　　　文献标志码： Ａ 　　　文章编号： １００１唱３６９５（２０１２）０２唱０４０１唱０５ ｄｏｉ ：１０．３９６９ ／ ｊ ． ｉｓｓｎ ．１００１唱３６９５．２０１２．０２．００１ Ｓｕｒｖｅｙ ｏｎ ａｕｔｏｍａｔｉｃ ｔｅｓｔ ｃａｓｅ ｇｅｎｅｒａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｏｆｔｗａｒｅ ｔｅｓｔｉｎｇ ＮＩＥＰｅｎｇ １，２ ， ＧＥＮＧＪｉ １ ， ＱＩＮＺｈｉ 唱 ｇｕａｎｇ １ （１．School of Computer Science ＆Engineering，University of Electronic Science ＆Technology of China，Chengdu ６１１７３１，China； ２．Jiangxi University of Finance ＆Economics，Nanchang ３３００１３，China） Abstract： Ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｔｈｅ ａｕｔｏｍａｔｉｃ ｔｅｓｔ ｃａｓｅ ｇｅｎｅｒａｔｉｏｎｓ ， ｔｈｅｒｅ ｗｅｒｅ ｆｏｕｒ ｃａｔｅｇｏｒｉｅｓ ， ｉｎｃｌｕｄｉｎｇ ｒａｎ 唱 ｄｏｍ ｔｅｓｔ ａｌｇｏｒｉｔｈｍｓ ， ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ， ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ， ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ． Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｄ ， ａｎａｌｙｚｅｄ ， ａｎｄ ｄｉｓｃｕｓｓｅｄ ｔｈｅ ｓｔａｔｕｓ ａｎｄ ｏｖｅｒｖｉｅｗ ｏｆ ｔｈｅ ｆｏｕｒ ｃａｔｅｇｏｒｉｅｓ ． Ｆｉｎａｌｌｙ ， ｉｔ ｄｒｅｗ ｔｈｅ ｃｏｎｃｌｕｓｉｏｎｓ ｆｏｒ ｔｈｅ ａｕｔｏｍａｔｉｃ ｔｅｓｔ ｃａｓｅ ｇｅｎｅｒａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ． Key words： ｓｏｆｔｗａｒｅ ｔｅｓｔｉｎｇ ； ｔｅｓｔ ｃａｓｅ ｇｅｎｅｒａｔｉｏｎ ； ｒａｎｄｏｍ ｔｅｓｔ ； ｈｅｕｒｉｓｔｉｃ ｔｅｓｔ 0 　引言 ＩＥＥＥ 计算机协会在 ＩＥＥＥＳｔｄ ８２９—１９８３［１］ 中对软件测试 给出了定义：通过人工测试或自动测试的手段对软件的质量进 行度量，用于检验被测软件实际运行结果是否与设计软件时的 初衷相一致。 ＩＥＥＥＳｔｄ ８２９—１９９８［２］ 进一步明确软件测试是用 于检测当前软件与实际设计需求间的差异的过程，具体包括了 测试用例（ ｔｅｓｔ ｃａｓｅ ， ＴＣ ） 集、测试过程集以及两者的组合。 ＩＥＥＥＳｔｄ ８２９—２００８［３］ 将软件测试延伸到整个软件开发生命周 期中，指出软件测试是给定条件下对系统或组件的执行，以及 对结果进行观察或记录的行为。 软件测试中的 ＴＣ 是用于特 定目的的数据集合，如输入数据、执行条件、程序路径、测试需 求等。 总体而言，软件测试技术是依据软件规约或者程序结构 设计一组 ＴＣ ，将 ＴＣ 作为输入来执行待测程序，判断被测程序 的动态行为和运行结果，以发现程序错误或功能缺陷。 从测试过程是否需要执行待测程序的角度，软件测试方法 可分为静态和动态两类［４］。 静态测试方法是指无须动态执行 待测程序代码，仅对软件进行静态检查和审阅来评测测试对象 是否符合编程标准，可用于发现待测软件的不足之处。 静态测 试方法包括规范测试、软件模型测试、符号执行、空间约简、文 档测试等。 静态测试的主要不足在于： ａ ） 难以发现由软件运 行环境导致的错误和故障； ｂ ） 可能因测试目标的复杂性而导 致符号执行状态空间爆炸，致使静态分析无法继续。 动态测试 方法是通过运行待测程序来检查软件的动态行为，验证运行结 果的正确性，可以发现测试对象在运行环境中形成的错误和故 障。 动态测试包括两个基本要素： ａ ）待测程序； ｂ ）运行待测程 序的数据，即 ＴＣ 。 ＴＣ 自动生成算法是一种依照 ＴＣ 规格需求和测试目标要 求自动生成 ＴＣ 的方法。 长期以来， ＴＣ 生成主要依靠手工完 成，这意味着软件测试人员需要具备丰富的经验和较高的专业 水平。 这导致实际工程中 ＴＣ 生成往往带有很大的盲目性， ＴＣ 数量多、测试效果差、测试成本高。 据统计，在软件测试的全部 开销中，约 ４０％花费消耗在设计 ＴＣ 阶段。 因此，如何科学有 效地通过 ＴＣ 自动生成算法，依据软件规格或程序结构自动构 造 ＴＣ 成为软件测试的研究重点之一。 多年来，许多研究者对 ＴＣ 自动生成进行了广泛而深入的研究，并取得了大量的研究 成果，本文主要针对软件 ＴＣ 自动生成算法进行了研究。 ＴＣ 自 动生成算法，尤其是启发性 ＴＣ 生成算法具备算法实现简单、 鲁棒性好的特点。 启发性 ＴＣ 生成算法是指通过对 ＴＣ 进行评 价进而自动更新 ＴＣ ，寻找可以覆盖测试目标的最优 ＴＣ 集的算 法。 该类算法通过待测程序的信息反馈，智能、动态地产生 ＴＣ ，具有良好的方向性和目的性，是 ＴＣ 自动生成算法研究的 主要内容。 1 　 TC 自动生成算法框架 动态测试的核心是 ＴＣ 自动生成算法，用于快速生成 ＴＣ并覆盖测试目标。 ＴＣ 自动生成算法框架如图 １ 所示。 ａ ） ＴＣ 自动生成算法对需要测试的程序进行结构性分析， 目的在于生成测试目标 O 和 ＴＣ 规格需求。 测试目标 O 是 ＴＣ 生成算法需要覆盖的对象，根据具体测试需求的差异而变化， 第 ２９ 卷第 ２ 期 ２０１２ 年 ２ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ 畅２９ Ｎｏ 畅２ Ｆｅｂ 畅２０１２ 主要包括语句、分支（判定）、条件、路径等。 ＴＣ 规格需求是对 ＴＣ 合法性的约束条件，主要包括 ＴＣ 结构说明、 ＴＣ 属性说明。 ｂ ） ＴＣ 自动生成算法对需要测试的程序进行插桩。 插桩是 向待测程序中插入特殊的程序片段（探针），用于跟踪动态测 试中 ＴＣ 的行为，采集程序语句的执行、变量变化等信息。 这 些信息称之为测试反馈信息，是 ＴＣ 自动生成算法产生、选择 和修正 ＴＣ 数据的基础，也是构造用于对 ＴＣ 质量进行评估的 适应度函数的依据。 ｃ ） ＴＣ 自动生成算法根据适应度函数判断测试目标是否已 经覆盖，如果覆盖则获得可用测试用例，算法结束；否则对 ＴＣ 进行选择与修正 ＴＣ ，产生新的 ＴＣ 数据。 如何对 ＴＣ 进行选 择、修正或补充新的 ＴＣ ，是 ＴＣ 自动生成算法框架的核心部分。 现有的主要研究包括基于随机算法的 ＴＣ 自动生成算法、基于 遗传的 ＴＣ 自动生成算法、基于蚁群的 ＴＣ 自动生成算法和基 于粒子群的 ＴＣ 自动生成算法。 2 　 TC 自动生成算法 2 畅 1 　 TC 自动生成算法评价指标 ＴＣ 自动生成算法的主要评价指标有首次失效发现平均 ＴＣ 数（ Ｆ 唱 ｍｅａｓｕｒｅ ）、测试覆盖率、迭代次数、复杂度、执行时间、 累计 ＴＣ 产生数量。 其中，算法迭代次数与算法复杂度为主要 评价指标；而算法执行时间容易受到待测程序的复杂度以及测 试环境的干扰，因此为参考指标。 Ｆ 唱 ｍｅａｓｕｒｅ 是对发现待测程 序中首个失效数据所需要的平均 ＴＣ 数。 常见的测试覆盖率 包括语句覆盖率、判定（分支）覆盖率、条件覆盖率、路径覆盖 率、 ｄｅｆ 唱 ｕｓｅ 覆盖率、函数覆盖率、状态覆盖率等。 复杂度是指 ＴＣ 自动生成算法的时间复杂度，反映了算法执行时间随 ＴＣ 数 量增加而增长的量级，在很大程度上可以反映出算法的优劣程 度。 执行时间是指 ＴＣ 自动生成算法从开始运行到完成测试 目标覆盖或退出算法时经历的运行时间。 累计 ＴＣ 产生数量 是指 ＴＣ 在算法整个执行期内产生的 ＴＣ 数量的总和。 2 畅 2 　基于随机算法的 TC 自动生成算法 基于随机算法的 ＴＣ 自动生成算法，简称随机测试（ ｒａｎ 唱 ｄｏｍ ｔｅｓｔ ， ＲＴ ）由 Ｈａｍｌｅｔ 于 １９９４ 年提出［５］，是一种基本的软件 自动化测试技术［６］，它通过在程序输入域上随机产生测试输 入来测试程序。 ＲＴ 的基本思想是使用 ＴＣ 规格需求随机生成 ＴＣ ，然后使 用生成的 ＴＣ 运行待测程序，最后检测测试目标是否被覆盖， 该方法不要求 ＴＣ 生成算法返回测试反馈信息。 ２００４ 年， Ｃｈｅｎ 等人对基本的 ＲＴ 算法进行了改进，提出适 应性随机测试（ ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓｔ ， ＡＲＴ ）［７］，并使用 Ｆ 唱 ｍｅａ 唱 ｓｕｒｅ对算法性能进行比较；他们还进一步提出 ＭＲＲＴ ［８］ 对基本 的 ＲＴ 算法计算性能进行改进。 同年， Ｃｈｅｎ 等人在 ＡＲＴ 中引 入输入域分区的概念，提出新的 ＤＰ ［９］ 算法以减少 ＡＲＴ 算法开 销。 ＡＲＴ 通过最大化 ＴＣ 在输入空间上的距离避免其对测试 目标中同一错误过度覆盖。 ２００５ 年， Ｍａｙｅｒ ［１０］ 进一步对此方法 进行改进，提出基于格的适应性 ＲＴ ，优化了距离比较次数，同 时在输入域采用递归格构建的方式给出 ＴＣ 的最大距离。 ２００６—２００７ 年， Ｃｈｅｎ 等人提出基于区域分割的 ＡＲＴ 算法［１１］ 和 Ｂａｌａｎｃｉｎｇ ［１２］ 算法，在执行时间和 Ｆ 唱 ｍｅａｓｕｒｅ 两个指标上降低 了 ＡＲＴ 的算法开销，但仍然存在 ＡＲＴ 多维问题。 ２００７ 年， Ｃｈｅｎ 等人对 ＡＲＴ 算法中出现的分区边界 ＴＣ 优先问题进行了 改进［１３］，通过对 Ｆ 唱 ｍｅａｓｕｒｅ 指标的测量证明了改进的有效性。 总体来说， ＲＴ 算法可以划分为四类： ａ ）基本随机算法； ｂ ） 基于距离的 ＲＴ 算法（ ＤＡＲＴ ），如 ＦＳＣＳ ［７］、 ＥＣＰ 唱 ＦＳＣＳ ［１３］； ｃ ）基 于排斥区域的 ＲＴ 算法（ ＲＲＴ ），如 ＭＲＲＴ ［８］； ｄ ）基于区域划分 的 ＲＴ （ ＰＡＲＴ ）算法，如 ＤＰ ［９］、 ＩＰ ［１１］、 ｂａｌａｎｃｉｎｇ ［１２］。 ＲＴ 的优点突出表现在： ａ ）算法简单、易于执行； ｂ ）生成 ＴＣ 效率高； ｃ ） ＲＴ 能够避免测试人员的主观偏见。 同时， ＲＴ 的缺 点也非常明显： ａ ） ＲＴ 的代码覆盖率低，测试覆盖率是衡量测试 充分度的重要指标，由于测试输入随机产生，很多情况下 ＲＴ 难以保证对程序代码的高覆盖率； ｂ ） ＲＴ 会生成大量的非法或 无用测试数据，一般而言待测程序对输入数据有一定约束或限 制，而 ＲＴ 会忽略这些约束，从而生成大量的非法或无用测试 数据； ｃ ） ＲＴ 表现出明显的盲目性，尽管 ＡＲＴ 算法较纯 ＲＴ 有所 改进，但由于 ＲＴ 算法本身缺乏待测目标的内部信息［５］，同时 ＴＣ 间缺乏知识共享与协同（特别在输入域存在非均匀分布、非 连续分布的情况下），这导致 ＲＴ 表现出明显的盲目性。 尽管 ＲＴ 有其固有的缺陷，但依然是其他优化算法，特别 是近些年来迅速发展的启发性 ＴＣ 生成算法的数据来源与对 比基准。 2 畅 3 　基于遗传的 TC 自动生成算法 基于遗传的 ＴＣ 自动生成算法简称遗传算法（ ｇｅｎｅｔｉｃ ａｌｇｏ 唱 ｒｉｔｈｍ ， ＧＡ ），是一种启发性算法，它将自然界遗传基因的遗传过 程与达尔文适者生存原则相结合，不断进化（选择、交叉、变 异）与淘汰 ＴＣ ，最终得到可用 ＴＣ 的过程。 １９９５ 年， Ｊｏｎｅｓ 在软 件结构性测试中将生物学的 ＧＡ ［１４］ 引入到 ＴＣ 自动生成中 来［１５，１６］，其基本算法如图 ２ 所示。 ·２０４· 计 算 机 应 用 研 究 　 第 ２９ 卷 ＧＡ 形式化描述如下： ＧＡ ＝｛π， ＴＣ ，P，R，M，F，τ｝。 ＴＣ 种 群即 ＴＣ 的集合，π是 ＴＣ 种群的规模； ＴＣ 是初始种群， ＴＣ ＝ ｛ ＴＣ１ ， ＴＣ２ ，⋯， ＴＣn ｝，其中 ＴＣi （１≤i≤π｝是种群中的个体；P、 R、M 分别为 ＧＡ 的三个基本操作，即基因选择、基因交叉和基 因变异， ＧＡ 中的基因一般为 ＴＣ 的二进制位串；F 是评价个体 适应度的适应度函数，即 ＴＣi 的适应度可以表示为 fi ＝F （ ＴＣi ）；τ为遗传算法的终止条件，通常为算法最大允许迭代次 数或适应度收敛值。 ＧＡ 的基本步骤如下： ａ ）随机产生 ＴＣ ，作为 ＴＣ 初代种群，规模为 n。 ｂ ）判断算法是否满足覆盖测试目标，若覆盖，则执行步骤 ｈ ）；否则执行步骤 ｃ ）。 ｃ ）判断算法是否满足达到最大迭代次数，若达到最大迭 代次数，则执行步骤 ｈ ）；否则执行步骤 ｄ ）。 ｄ ）对 ＴＣ 群体的个体计算 fi ＝F（ ＴＣi ）。 ｅ ）依据 fi 对 ＴＣ 种群进行选择产生亲代种群。 ｆ ）对亲代种群执行交叉／变异产生新 ＴＣ 。 ｇ ）形成下一代 ＴＣ 种群，并执行步骤 ｂ ）。 ｈ ）算法结束，输出可用 ＴＣ 。 ＧＡ 本质上是将 ＴＣ 生成过程转换为寻找最适合测试环境 的最优 ＴＣ 的过程。 其核心过程包括： ａ ） 生存环境的定义； ｂ ） 根据测试任务设计适应度函数，量化 ＴＣ 对环境的适应性； ｃ ） 亲代选择策略； ｄ ）交叉／变异策略。 Ｊｏｎｅｓ 等人［１５，１６］ 在 ＧＡ 的研究中使用 ＴＣ 和实际可覆盖目 标间的汉明距离构造评价 ＴＣ 的适应度函数，并使用单一数据 位变异和单点交叉作为 ＴＣ 种群更新方式对待测程序进行判 断覆盖。 实验证明 ＧＡ 在迭代次数上较 ＲＴ 算法有显著降低。 １９９７ 年， ＭｃＧｒａｗ 等人［１７］ 使用条件表达式操作数和测试目标的 距离作为适应度函数构造 ＧＡ ，实验证明新 ＧＡ 在测试目标覆 盖效率上有所改善。 １９９９ 年， Ｐａｒｇａｓ 等人［１８］ 使用控制依赖图 （ ｃｏｎｔｒｏｌ ｄｅｐｅｎｄｅｎｃｅ ｇｒａｐｈｓ ， ＣＤＧ ）对适应度函数进行构造，指出 一般情况下 ＣＤＧ 产生的谓词路径较少，验证了新算法 ＴＧｅｎ 在 迭代次数上优于 ＲＴ 算法。 ２０００ 年， Ｌｉｎ 等人［１９］ 在控制流图 （ ｃｏｎｔｒｏｌ 唱 ｆｌｏｗ ｄｉａｇｒａｍ ， ＣＦＤ ）上根据 ＴＣ 执行的路径与目标实际 路径相似度定义适应度函数，对待测程序进行了路径覆盖测 试。 ２００１ 年， Ｂｏｔｔａｃｉ ［２０］ 将适应度定义为 ＴＣ 的非负变异成本。 ２００５ 年， Ｇｉｒｇｉｓ ［２１］ 对数据流进行分析，根据变量定义与使用之 间的关系构造 ｄｅｆ 唱 ｕｓｅ 路径，并进行 ｄｅｆ 唱 ｕｓｅ 路径覆盖测试，该 算法在迭代次数、 ｄｅｆ 唱 ｕｓｅ 路径覆盖率、累计 ＴＣ 产生数量三个 指标上均优于 ＲＴ 算法。 ２００７ 年， Ｇｈｉｄｕｋ 等人［２２］ 在 ＤＴ （ ｄｏｍｉ 唱 ｎａｔｏｒ ｔｒｅｅ ）上构建适应度方程，提出 ＴＧＧＡ 算法，指出 Ｇｉｒｇｉｓ 给 出的适应度方程会丢失 ＴＣ 的差异信息，从而忽略了 ＴＣ 之间 潜在的优劣性，这将导致 ＴＣ 丧失择优进化的机会； ＴＧＧＡ 算法 在测试覆盖率、迭代次数、执行时间、累计 ＴＣ 产生数量四个指 标上优于 ＲＴ 算法。 ２００９ 年， Ｓｈｅｎ 等人［２３］ 在 ＧＡ 中使用禁忌 搜索作为 ＴＣ 种群的变异方式，使得 ＴＣ 种群中的个体 ＴＣ 在进 入繁殖前能够得到预先的独立优化，较 Ｊｏｎｅｓ 提出的 ＧＡ ，新的 算法在函数覆盖率指标上有一定提高。 ２０１０ 年， Ｐｉｎｔｏ 等人［２４］ 提出多目标适应度函数，可实现针对覆盖率、测试时间、失效数 据发现能力的综合优化，实验证明该算法较 ＲＴ 在目标覆盖率 和执行时间两个指标上均有所改善。 ＧＡ 在 ＴＣ 自动生成算法中的引入，减少了 ＴＣ 自动生成 的盲目性，提高了软件测试的效率；但 ＧＡ 的早期迭代阶段， ＴＣ 种群中存在大量次优解。 这些次优解在交叉算子的作用 下进化为最优解的概率较大，即算法初期 ＴＣ 种群的质量改 善速度比较快；随着 ＴＣ 群体多样性的逐渐降低， ＴＣ 种群进 化出最优解的速度下降，即 ＧＡ 的宏观探索能力大于局部求 精能力。 2 畅 4 　基于蚁群的 TC 自动生成算法 基于蚁群的 ＴＣ 自动生成算法简称蚁群优化（ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ， ＡＣＯ ）算法，是 ＭｃＭｉｎｎ 等人［２５］ 将 Ｄｏｒｉｇｏ 等人［２６］ 提出的仿生寻优启发性算法引入到 ＴＣ 自动生成中而形成的 新算法。 ＡＣＯ 算法基本思想是将待测程序结构信息表达为某种知 识，然后应用蚁群算法完成知识推理，在推理过程中生成所需 要的 ＴＣ 。 其基本原理是将蚁群智能体放在路径有向图 G 上 （蚂蚁指形成 ＴＣ 编码的数据元）， 通过蚂蚁移动、释放信息素 （覆盖图 G 中边形成的标记）等行动搜索最优路径 P，从而寻 找可覆盖测试目标 O 的输入变量。 蚂蚁在图 G 上的移动路径 经过解码形成 ＴＣ 。 ＡＣＯ 算法的核心过程包括： ａ ）将测试问题转换成有向图 G； ｂ ） 构造基于图 G 的评估函数 F，用于量化被信息素覆盖的 路径优劣； ｃ ） 可能解生成算法与停止准则； ｄ ） 信息素更新策 略； ｅ ）蚁群个体从图 G 的节点 A 移动到节点 B 的策略。 ＡＣＯ 基本原理和 ＡＣＯ 算法路径网络构造基本原理如图 ３、４ 所示。 ＡＣＯ 算法首先要解决的问题是知识表达， 即如何将待测 程序的输入空间映射为蚁群算法的路径［２７］。 为了适应输入空 间中不同数据结构的变量， 通常使用输入变量的二进制形式 来构建映射模型。 首先，将待测程序输入空间 D 的某一 ＴＣ 通 过编码规则转换为位串 b；b 与路径有向图 G 的一条路径 P 相 ·３０４·第 ２ 期 聂　鹏，等：软件测试用例自动生成算法综述 　　　 对应；经过蚁群算法将产生新的路径 P′；P′经解码得到对应的 位串 b′，b′经转换形成新的 ＴＣ 。 ＡＣＯ 算法路径有向图记为 G ＝（V，E）， 节点集记为 V ＝｛v１ ，v２ ，⋯，v２N｝。 ＡＣＯ 算法基本步骤如下： ａ ）初始化，初始化蚁群和控制参数。 ｂ ）将规模为 m 的蚁群随机分配到图 G 的路径节点上，并 为路径上的每个有向边分配一个极小常数作为初始信息素。 ｃ ）蚁群中的个体按照算法给定的状态移动规则在节点间 移动。 ｄ ）对蚁群中的个体进行信息素的局部更新。 ｅ ）蚁群中的个体顺次选择多个节点完成信息素局部更 新，并进行路径构造。 ｆ ）对构造好的路径进行解码，生成 ＴＣ ；使用 ＴＣ 运行待测 程序，并通过适应度函数 F 对 ＴＣ 进行适应度评估，最终保留 最优路径。 ｇ ）若算法满足终止条件，则输出 ＴＣ ，结束算法；否则转入 步骤 ｃ ）。 ２００３ 年， ＭｃＭｉｎｎ 等人［２５］ 将 ＡＣＯ 算法引入到 ＴＣ 自动生成 中，用于寻找待测程序的状态迁移序列，对演化算法进行补充 优化。 同年， Ｄｏｅｒｎｅｒ 等人［２８］ 使用 ＡＣＯ 算法提取可用测试路 径，用于优化测试覆盖率和测试成本。 ２００５ 年， Ｌｉ 等人［２９］ 使 用 ＡＣＯ 算法基于 ＵＭＬ 对待测程序进行状态覆盖测试。 ２００７ 年，傅博［２７］ 在 ＡＣＯ 算法中引入路径变异算子和自适应挥发系 数， 提高了蚂蚁路径的多样性，在迭代次数上优于 ＧＡ 。 ２００９ 年， Ｌｉ 等人［３０］ 将待测程序的输入域划分为不同的子域，基于子 域构建搜索路径图，并基于该路径图使用 ＡＣＯ 算法生成 ＴＣ ， 该算法在迭代次数上优于 ＧＡ 。 ２００９ 年，陈明师等人［３１］ 对标 准 ＡＣＯ 算进行改进，提出多态蚁群 ＴＣ 自动生成算法（ ｐｏｌｙｍｏｒ 唱 ｐｈｉｃ ａｎｔ ｃｏｌｏｎｉｅｓ ａｌｇｏｒｉｔｈｍ ， ＰＡＣＡ ）。 ＰＡＣＡ 将蚁群划分为侦察 蚁、搜索蚁和工蚁，从而缩小了算法搜索空间，增强了蚁群间的 协作，提高了搜索效率。 陈明师等人的实验证明了 ＰＡＣＡ 在 ＴＣ 生成的执行时间上优于 ＡＣＯ 算法。 ２０１０ 年， Ｘｕ 等人［３２］ 在 ＡＣＯ 算法寻径中引入遗传算法，提出 ＧＡＡＣＯ 算法，克服了遗 传算法局部搜索能力差、易早熟现象，同时弥补了蚁群算法费 时、易停滞现象，增强了 ＴＣ 生成的随机性、快速性和全局收敛 性。 Ｘｕ 等人实验证明了 ＧＡＡＣＯ 在迭代次数上优于 ＧＡ 、 ＡＣＯ 和 ＲＴ 算法。 ＡＣＯ 算法是一个增强型学习系统， 具有分布式计算、易于 与其他算法相融合、鲁棒性强等优点，但由于搜索初期信息素 相对匮乏， 导致算法的搜索效率降低， 正反馈机制容易产生 停滞早熟现象。 2 畅 5 　基于粒子群的 TC 自动生成算法 基于粒子群的 ＴＣ 自动生成算法简称粒子群优化（ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ， ＰＳＯ ）算法，是 Ｗｉｎｄｉｓｃｈ 等人［３３］ 基于 Ｋｅｎｎｅ 唱 ｄｙ 和 Ｅｈｅｒｈａｒｔ 通过对动物社会行为的研究成果［３４］ 而提出的一 种新的 ＴＣ 自动生成算法。 ＰＳＯ 具备算法简单、鲁棒性好的特 点，通过 ＴＣ 的个体认知与群体智能的相互影响和作用动态地 产生用例数据，具有很好的导向性和收敛性。 ＰＳＯ 算法将 ＴＣ 规格需求作为算法的解空间；可能覆盖测 试目标的潜在 ＴＣ 集合称之为粒子群，每个潜在可达测试目标 的 ＴＣ 称之为粒子；每个粒子都以一定速度在 D 维解空间中运 动，并由一个量化评估函数产生适应值（ ｆｉｔｎｅｓｓ ｖａｌｕｅ ）；粒子群 追随当前最优粒子并在解空间中持续搜索，直至满足算法结束 条件。 在每一次算法迭代中，粒子通过跟踪两个极值进行自我 更新，第一个极值为粒子本身所找到的最优解，称之为个体最 优（pｂｅｓｔ ）；另一个极值是整个粒子群当前找到的最优解，称之 为全局最优（gｂｅｓｔ ）。 ＰＳＯ 算法基本原理如图 ５ 所示。 ＰＳＯ 算法基本步骤如下： ａ ）随机初始化粒子的位置和速度。 ｂ ）计算每个粒子的适应值。 ｃ ）对于每个粒子，将其适应值与所经历过的最好位置的 适应值进行比较，若较好，则将其作为当前的最好位置。 ｄ ）对每个粒子，将其适应值与全局所经历的最好位置的 适应值进行比较，若较好，则将其作为当前的全局最好位置。 ｅ ）如未达到结束条件（通常为足够好的适应值或达到一 个预设的最大代数）则执行步骤 ｆ ），否则算法结束。 ｆ ）对粒子的速度和位置进行更新，产生新粒子群并返回步 骤 ｂ ）。 ２００７ 年， Ｗｉｎｄｉｓｃｈ 等人［３３］ 将 ＰＳＯ 算法引入到 ＴＣ 自动生 成算法中，并通过分支覆盖测试与 ＧＡ 进行了分析和比较，指 出 ＰＳＯ 在对复杂对象的测试中优于 ＧＡ 。 ２００８ 年，李爱国等 人［３５］ 采用分支函数叠加法构造 ＰＳＯ 适应值函数，对测单元 的执行路径进行覆盖测试，并与 ＧＡ 进行了分析和比较工作， 证明 ＰＳＯ 算法在迭代次数和执行时间两个指标上优于 ＧＡ 。 同年， Ｈｌａ 等人［３６］ 在 ＰＳＯ 算法中，提出一种基于综合覆盖率 的适应度测量方法，并与随机算法进行了性能对比，分析了 ＰＳＯ 算法在复杂度上优于 ＧＡ 。 ２０１０ 年， Ｃｕｉ 等人［３７］ 在 ＰＳＯ 算法中构建 ＥＦＡＵ 路径度量函数， ＰＳＯ 适应值为目标路径与 ＥＦＡＵ 度量值间的相似度， Ｃｕｉ 等人实验性地比较了 ＧＡ 、 ＰＳＯ 和 ＥＦＡＵ 唱 ＰＳＯ 的迭代性能，证明 ＥＦＡＵ 唱 ＰＳＯ 在迭代次数上优 于其他两种算法。 周红等人［３８］ 在 ＰＳＯ 算法中引入 ＧＡ ，增强 ＰＳＯ 中 ＴＣ 种群的多样性，降低 ＰＳＯ 算法的早熟特性，在迭代 次数和执行时间两个指标上优于 ＧＡ 。 Ｎａｙａｋ 等人［３９］ 基于数 据流图建立 ＰＳＯ 测试用例生成算法，对 ＰＳＯ 和 ＧＡ 两种算法 的复杂度进行了分析。 在 ｄｅｆ 唱 ｕｓｅ 覆盖测试实验中，验证了 ＰＳＯ 算法较 ＧＡ 需要的迭代次数更少。 ＰＳＯ 以其计算迅速和易用性优于传统算法，但是 ＰＳＯ 如 同其他智能算法一样存在早熟。 通常认为， ＰＳＯ 的早熟是由粒 子群丧失多样性，从而导致群体中大部分个体聚集在一个很小 的搜索范围，当该搜索范围不含最优解时，算法将受困于局部 最优。 ·４０４· 计 算 机 应 用 研 究 　 第 ２９ 卷 3 　结束语 ＴＣ 自动生成算法的研究大大提高了软件测试的自动化水 平，为软件失效数据采集提供了一种自动化方法。 ＴＣ 自动生成 算法的研究成果得到越来越广泛的应用，并在学术界和工业界 均得到了重视。 ＴＣ 自动生成是建立在对软件结构抽象描述的 基础上，通过对部分人工软件测试行为进行替代，有效提高了测 试效率和测试失效辨识，有利于软件可靠性的评估和预测。 在现有的自动化方法中仍存在一些缺陷或不足，需在以下 几个方面进行深入研究： ａ ）测试失效发现和测试自动化密不可分。 一方面，失效 发现是测试自动化不可缺少的内容；另一方面，自动化又使得 测试失效发现更加困难。 目前对测试失效发现的研究比较少， 实践中经常通过对比不同软件版本的输出结果进行测试失效 发现，因此测试失效发现是未来研究的内容之一。 ｂ ）在现有的 ＴＣ 自动生成算法中， ＲＴ ／ ＡＲＴ 算法由于无须 跟踪 ＴＣ 在待测程序中的运行状态而表现出较大的盲目性； ＧＡ 通过对 ＴＣ 运行状态的跟踪，加强了 ＴＣ 对测试目标的针对 性，但算法较为复杂、收敛性较差是 ＧＡ 的主要问题； ＡＣＯ 具有 分布式计算、与其他算法易于融合、鲁棒性强等优点；但由于搜 索初期信息相对匮乏， 导致算法的收敛性降低， 算法中的正 反馈机制也容易产生早熟现象； ＰＳＯ 算法简单、鲁棒性好，通过 粒子群的个体认知与群体智能间的知识传递，动态地产生用例 数据，对测试目标的导向性和收敛性均较好，但是 ＰＳＯ 如同其 他智能算法一样存在早熟，如何抑制早熟是该算法的重要研究 内容。 ｃ ） ＴＣ 自动生成算法中仍需不断引入新的理论和方法，通 过对新理论和方法的研究，尽可能地扩展测试覆盖，提升测试 效果，使软件测试在智能性和高效性两个方面有更进一步的 提高。 参考文献： ［１］ Ｓｏｆｔｗａｒｅ ＆Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｍｍｉｔｔｅｅ ． ＩＥＥＥ ８２９—１９８３， ＩＥＥＥ ｓｔａｎｄａｒｄ ｆｏｒ ｓｏｆｔｗａｒｅ ａｎｄ ｓｙｓｔｅｍ ｔｅｓｔ ｄｏｃｕｍｅｎｔａｔｉｏｎ ［ Ｓ ］．［ Ｓ ． ｌ ．］： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， １９８３． ［２］ Ｓｏｆｔｗａｒｅ ＆Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｍｍｉｔｔｅｅ ． ＩＥＥＥ ８２９—１９９８， ＩＥＥＥ ｓｔａｎｄａｒｄ ｆｏｒ ｓｏｆｔｗａｒｅ ａｎｄ ｓｙｓｔｅｍ ｔｅｓｔ ｄｏｃｕｍｅｎｔａｔｉｏｎ ［ Ｓ ］．［ Ｓ ． ｌ ．］： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， １９９８． ［３］ Ｓｏｆｔｗａｒｅ ＆Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｍｍｉｔｔｅｅ ． ＩＥＥＥ ８２９—２００８， ＩＥＥＥ ｓｔａｎｄａｒｄ ｆｏｒ ｓｏｆｔｗａｒｅ ａｎｄ ｓｙｓｔｅｍ ｔｅｓｔ ｄｏｃｕｍｅｎｔａｔｉｏｎ ［ Ｓ ］．［ Ｓ ． ｌ ．］： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， ２００８． ［４］ 单锦辉， 姜瑛， 孙萍．软件测试研究进展［ Ｊ ］．北京大学学报， ２００５，41（１）： １３４唱１４５． ［５］ ＨＡＭＬＥＴＲ ． Ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ［ Ｍ ］／／ Ｅｎｃｙｃｌｏｐｅｄｉａ ｏｆ Ｓｏｆｔｗａｒｅ Ｅｎｇｉ 唱 ｎｅｅｒｉｎｇ ． Ｎｅｗ Ｙｏｒｋ ： Ｗｉｌｅｙ ，１９９４． ［６］ ＧＥＲＬＩＣＨＲ ， ＧＥＲＬＩＣＨＲ ， ＢＯＬＬＴ ． Ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ： ｆｒｏｍ ｔｈｅ ｃｌａｓｓｉｃａｌ ａｐｐｒｏａｃｈ ｔｏ ａ ｇｌｏｂａｌ ｖｉｅｗ ａｎｄ ｆｕｌｌ ｔｅｓｔ ａｕｔｏｍａｔｉｏｎ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ２ ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｒａｎｄｏｍ Ｔｅｓｔｉｎｇ ． Ｎｅｗ Ｙｏｒｋ ： ＡＣＭＰｒｅｓｓ ，２００７：３０唱３７． ［７］ ＣＨＥＮＴＹ ， ＬＥＵＮＧＨ ， ＭＡＫＩＫ ． Ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ９ ｔｈ Ａｓｉａｎ Ｃｏｍｐｕｔｉｎｇ Ｓｃｉｅｎｃｅ Ｃｏｎｆｅｒｅｎｃｅ ． Ｂｅｒｌｉｎ ： Ｓｐｒｉｎ 唱 ｇｅｒ ， ２００４：３２０唱３２９． ［８］ ＣＨＥＮＴＹ ， ＫＵＯＦｅｉ 唱 ｃｈｉｎｇ ， ＭＥＲＫＥＬＲＧ ， et al． Ｍｉｒｒｏｒ ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ３ ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｑｕａｌｉ 唱 ｔｙ Ｓｏｆｔｗａｒｅ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， ２００３：４唱１１． ［９］ ＣＨＥＮＴＹ ， ＭＥＲＫＥＬＲＧ ， ＥＤＤＹＧ ， et al． Ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓ 唱 ｔｉｎｇ ｔｈｒｏｕｇｈ ｄｙｎａｍｉｃ ｐａｒｔｉｔｉｏｎｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ４ ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｑｕａｌｉｔｙ Ｓｏｆｔｗａｒｅ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏ 唱 ｃｉｅｔｙ ， ２００４：７９唱８６． ［１０］ ＭＡＹＥＲＪ ． Ｌａｔｔｉｃｅ 唱 ｂａｓｅｄ ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ２０ ｔｈ ＩＥＥＥ ／ ＡＣＭＩｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｍａｔｅｄ Ｓｏｆｔｗａｒｅ Ｅｎ 唱 ｇｉｎｅｅｒｉｎｇ ． Ｎｅｗ Ｙｏｒｋ ： ＡＣＭＰｒｅｓｓ ， ２００５：３３３唱３３６． ［１１］ ＣＨＥＮＴＹ ， ＨＵＡＮＧＤｅ 唱 ｈａｏ ， ＺＨＯＵＺｈｉ 唱 ｑｕａｎ ． Ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ｔｈｒｏｕｇｈ ｉｔｅｒａｔｉｖｅ ｐａｒｔｉｔｉｏｎｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ １１ ｔｈ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｏｌｏｇｉｃｓ ． Ｂｅｒｌｉｎ ： Ｓｐｒｉｎｇｅｒ ，２００６：１５５唱１６６． ［１２］ ＣＨＥＮＴＹ ， ＨＡＯＤｅ 唱 ｈｕａｎｇ ， ＫＵＯＦｅｉ 唱 ｃｈｉｎｇ ． Ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓ 唱 ｔｉｎｇ ｂｙ ｂａｌａｎｃｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ２ ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｒａｎｄｏｍ Ｔｅｓｔｉｎｇ ， Ｃｏｌｏｃａｔｅｄ ｗｉｔｈ ｔｈｅ ２２ ｎｄ ＩＥＥＥ ／ ＡＣＭＩｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｍａｔｅｄ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ ． Ｎｅｗ Ｙｏｒｋ ： ＡＣＭ Ｐｒｅｓｓ ，２００７：２唱９． ［１３］ ＣＨＥＮＴＹ ， ＫＵＯＦｅｉ 唱 ｃｈｉｎｇ ， ＬＩＵＨｕａｉ ． Ｅｎｈａｎｃｉｎｇ ａｄａｐｔｉｖｅ ｒａｎｄｏｍ ｔｅｓｔｉｎｇ ｔｈｒｏｕｇｈ ｐａｒｔｉｔｉｏｎｉｎｇ ｂｙ ｅｄｇｅ ａｎｄ ｃｅｎｔｒｅ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ａｕｓｔｒａ 唱 ｌｉａｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ，２００７：２６５唱２７３． ［１４］ ＨＯＬＬＡＮＤＪＨ ． Ａｄａｐｔａｔｉｏｎ ｉｎ ｎａｔｕｒａｌ ａｎｄ ａｒｔｉｆｉｃｉａｌ ｓｙｓｔｅｍｓ ： ａｎ ｉｎ 唱 ｔｒｏｄｕｃｔｏｒｙ ａｎａｌｙｓｉｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｂｉｏｌｏｇｙ ， ｃｏｎｔｒｏｌ ， ａｎｄ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ［ Ｍ ］． Ｃａｍｂｒｉｄｇｅ ： ＭＩＴＰｒｅｓｓ ，１９７５： ２２８． ［１５］ ＪＯＮＥＳＢＦ ， ＳＴＨＡＭＥＲＨ ， ＥＹＲＥＳＤＥ ． Ａｕｔｏｍａｔｉｃ ｓｔｒｕｃｔｕｒａｌ ｔｅｓ 唱 ｔｉｎｇ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］．Software Engineering Journal， １９９６，11（５）： ２９９唱３０６． ［１６］ ＪＯＮＥＳＢＦ ， ＳＴＨＡＭＥＲＨ ， ＥＹＲＥＳＤＥ ． Ｇｅｎｅｒａｔｉｎｇ ｔｅｓｔ ｄａｔａ ｆｏｒ ＡＤＡ ｐｒｏｃｅｄｕｒｅｓ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ １ ｓｔ Ｉｎｔｅｒ 唱 ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｙｓｔｅｍｓ ： Ｉｎｎｏｖａｔｉｏｎｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ ．１９９５：６５唱７０． ［１７］ ＭｃＧＲＡＷＧ ， ＭＩＣＨＡＥＬＣ ， ＳＣＨＡＴＺＭ ． Ｇｅｎｅｒａｔｉｎｇ ｓｏｆｔｗａｒｅ ｔｅｓｔ ｄａｔａ ｂｙ ｅｖｏｌｕｔｉｏｎ ［ Ｊ ］．IEEETrans on Software Engineering， １９９７，27（１２）： １０８５唱１１１０． ［１８］ ＰＡＲＧＡＳＲＰ ， ＨＡＲＲＯＬＤＭＪ ， ＰＥＣＫＲＲ ． Ｔｅｓｔ 唱 ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］．Software Testing，Verification and Reliability，１９９９，9（４）： ２６３唱２８２． ［１９］ ＬＩＮＪ ， ＹＥＨＰ ． Ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｅｓｔ ｃａｓｅ ｇｅｎｅｒａｔｉｏｎ ｉｎ ｐａｔｈ ｔｅｓｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ９ ｔｈ Ａｓｉａｎ Ｔｅｓｔ Ｓｙｍｐｏｓｉｕｍ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， ２０００：２４１唱２４６． ［２０］ ＢＯＴＴＡＣＩＬ ． Ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ ｆｏｒ ｍｕｔａｔｉｏｎ ｔｅｓｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｓｉｎｇ Ｍｅｔａｈｅｕｒｉｓｔｉｃ Ｉｎ ｎｏｖａｔｉｖｅ Ａｌｇｏｒｉｔｈｍｓ Ｗｏｒｋｓｈｏｐ ａｔ ｔｈｅ ２３ ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ ．２００１：３唱７． ［２１］ ＧＩＲＧＩＳＭＲ ． Ａｕｔｏｍａｔｉｃ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｆｏｒ ｄａｔａ ｆｌｏｗ ｔｅｓｔｉｎｇ ｕｓｉｎｇ ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ［ Ｊ ］．Journal of Universal Computer Science，２００５，11（６）： ８９８唱９１５． ［２２］ ＧＨＩＤＵＫＡＳ ， ＨＡＲＲＯＬＤＭＪ ， ＧＩＲＧＩＳＭＲ ． Ｕｓｉｎｇ ｇｅｎｅｔｉｃ ａｌｇｏ 唱 ｒｉｔｈｍｓ ｔｏ ａｉｄ ｔｅｓｔ 唱 ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｆｏｒ ｄａｔａ 唱 ｆｌｏｗ ｃｏｖｅｒａｇｅ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ １４ ｔｈ Ａｓｉａ 唱 Ｐａｃｉｆｉｃ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ ．［ Ｓ ． ｌ ．］： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， ２００７：４１唱４８． ［２３］ ＳＨＥＮＸｉａ 唱 ｊｉｏｎｇ ， ＷＡＮＧＱｉａｎ ， ＷＡＮＧＰｅｉ 唱 ｐｅｉ ， et al． Ａｕｔｏｍａｔｉｃ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｔｅｓｔ ｃａｓｅ ｂａｓｅｄ ｏｎ ｇａｔｓ ａｌｇｏｒｉｔｈｍ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ＩＥＥＥＩｎ 唱 ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒａｎｕｌａｒ Ｃｏｍｐｕｔｉｎｇ ．２００９：４９６唱５００． （下转第 ４１３ 页） ·５０４·第 ２ 期 聂　鹏，等：软件测试用例自动生成算法综述 　　　 仪器仪表学报，２００９，30（９）：１８８６唱１８９０． ［４２］ ＶＩＤＡＫＯＶＩＣＢ ， ＬＯＺＯＹＡＣＢ ． Ｏｎ ｔｉｍｅ 唱 ｄｅｐｅｎｄｅｎｔ ｗａｖｅｌｅｔ ｄｅｎｏｉ 唱 ｓｉｎｇ ［ Ｊ ］．IEEETrans on Signal Processing，１９９８，46（９）：２５４９唱 ２５５１． ［４３］ ＣＡＮＤＥＳＥＪ ． Ｒｉｄｇｅｌｅｔｓ ： ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ ［ Ｄ ］． Ｓｔａｎｆｏｒｄ ： Ｓｔａｎｆｏｒｄ Ｕｎｉｖｅｒｓｉｔｙ ，１９９８． ［４４］ ＤＯＮＯＨＯＤＬ ， ＤＵＮＣＡＮＭＲ ． Ｄｉｇｉｔａｌ ｃｕｒｖｅｌｅｔ ｔｒａｎｓｆｏｒｍ ： ｓｔｒａｔｅｇｙ ， ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｎｄ ｅｘｐｅｒｍｅｎｔｓ ［ Ｄ ］． Ｓｔａｎｆｏｒｄ ： Ｓｔａｎｆｏｒｄ Ｕｎｉｖｅｒｓｉｔｙ ， １９９９． ［４５］ ＣＡＮＤＥＳＥＪ ， ＤＯＮＯＨＯＤＬ ． Ｃｕｒｖｅｌｅｔｓ ： ａ ｓｕｒｐｒｉｓｉｎｇｌｙ ｅｆｆｅｃｔｉｖｅ ｎｏｎａｄａｐｔｉｖｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｏｂｊｅｃｔｓ ｗｉｔｈ ｅｄｇｅｓ ［ Ｒ ］． Ｓｔａｎｆｏｒｄ ： Ｓｔａｎｆｏｒｄ Ｕｎｉｖｅｒｓｉｔｙ ，１９９９． ［４６］ ＤＯＭＮ ， ＶＥＴＴＥＲＬＩＭ ． Ｔｈｅ Ｃｏｎｔｏｕｒｌｅｔ ｔｒａｎｓｆｏｒｍ ： ａｎ ｅｆｆｉｃｉｅｎｔ ｄｉ 唱 ｒｅｃｔｉｏｎａｌ ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ ｉｍａｇｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ［ Ｊ ］．IEEETrans on Image Processing，２００５，14（１２）：２０９１唱２１０６． ［４７］ ＰＥＮＮＥＣＥＬ ， ＭＡＬＬＡＴＳ ． Ｓｐａｒｓｅ ｇｅｏｍｅｔｒｉｃ ｉｍａｇｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ ｗｉｔｈ ｂａｎｄｅｌｅｔｓ ［ Ｊ ］．IEEETrans on Image Processing，２００５，14 （４）： ４２３唱４３８． ［４８］ ＣＡＮＤＥＳＥＪ ． Ｒｉｄｇｅｌｅｔ ： ｔｈｅｏｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ ［ Ｄ ］． Ｓｔａｎｆｏｒｄ ： Ｓｔａｎｆｏｒｄ Ｕｎｉｖｅｒｓｉｔｙ ， １９９８． ［４９］ ＳＴＡＲＣＫＪＬ ， ＣＡＮＤＥＳＥＪ ， ＤＯＮＯＨＯＤＬ ． Ｔｈｅ Ｃｕｒｖｅｌｅｔ ｔｒａｎｓｆｏｒｍ ｆｏｒ ｉｍａｇｅ ｄｅｎｏｉｓｉｎｇ ［ Ｊ ］．IEEETrans on Image Processing，２００２， 11（６）：６７０唱６８４． ［５０］ 肖小奎，黎绍发．加强边缘保护的 Ｃｕｒｖｅｌｅｔ 图像去噪方法［ Ｊ ］．通 信学报，２００４，25（２）：９唱１５． ［５１］ 刘盛鹏，方勇．基于数学形态学的 Ｃｏｎｔｏｕｒｌｅｔ 变换域图像降噪方法 ［ Ｊ ］．光子学报，２００８，37（１）：１９７唱２０１． ［５２］ 王军华，方勇．基于 Ｃｕｒｖｅｌｅｔ 稀疏表示的图像盲分离初始化［ Ｊ ］． 应用科学学报，２００９，27（２）：１６２唱１６６． ［５３］ 练秋生，陈书贞．基于解析轮廓波变换的图像稀疏表示及其在压 缩传感中的应用［ Ｊ ］．电子学报，２０１０，38（６）：１２９３唱１２９８． ［５４］ 张文革，刘芳，焦李成，等．基于 Ｂａｎｄｅｌｅｔｓ 域逐子块阈值的图像去 噪［ Ｊ ］．电子学报，２０１０，38（２）：２９０唱２９４． ［５５］ ＤＯＮＯＨＯＤＬ ． Ｗｅｄｇｅｌｅｔｓ ： ｎｅａｒｌｙ ｍｉｎｉｍａｘ ｅｓｔｉｍａｔｉｏｎ ｏｆ ｅｄｇｅｓ ［ Ｊ ］． Annals Statistics，１９９９，27（３）：８５９唱８９７． ［５６］ 郭武，王润生，张鹏，等．基于独立分量分析的图像去噪研究［ Ｊ ］． 信号处理，２００８，24（３）：３８１唱３８５． ［５７］ ＨＹＶＡＲＩＮＥＮＡ ， ＨＯＹＥＲＰ ， ＯＪＡＥ ． Ｓｐａｒｓｅ ｃｏｄｅ ｓｈｒｉｎｋａｇｅ ｆｏｒ ｄｅ 唱 ｎｏｉｓｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ．１９９８：８５９唱８６４． ［５８］ ＯＬＳＨＡＵＳＥＮＡＢ ， ＦＩＥＬＤＤＪ ． Ｓｐａｒｓｅ ｃｏｄｉｎｇ ｗｉｔｈ ａｎ ｏｖｅｒｃｏｍｐｌｅｔｅ ｂａｓｉｓ ｓｅｔ ： ａ ｓｔｒａｔｅｇｙ ｅｍｐｌｏｙｅｄ ｂｙ Ｖ １［ Ｊ ］．Vision Research，１９９７， 37（２３）：３３１１唱３３２５． ［５９］ ＨＡＲＩＴＯＰＯＵＬＯＳＭ ， ＹＩＮＨｕ 唱 ｊｕｎ ， ＡＬＬＩＮＳＯＮＮＭ ． Ｉｍａｇｅ ｄｅｎｏｉｓ 唱 ｉｎｇ ｕｓｉｎｇ ｓｅｌｆ 唱 ｏｒｇｎｉｚｉｎｇ ｍａｐ 唱 ｂａｓｅｄ ｎｏｎｌｉｎｅａｒ ｉｎｄｅｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ ［ Ｊ ］．Neural Network，２００２，15（８唱９）：１０８５唱１０９８． ［６０］ ＨＡＮＸｉａｎ 唱 ｈｕａ ， ＣＨＥＮＹＷ ， ＮＡＫＡＯＺ ， et al． ＩＣＡ 唱 ｄｏｍａｉｎ ｆｉｌｔｅｒｉｎｇ ｏｆ Ｐｏｉｓｓｏｎ ｎｏｉｓｅ ｉｍａｇｅｓ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ３ ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍｕｌｔｉｓｐｅｃｔｒａｌ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ ．２００３：８１１唱 ８１４． ［６１］ ＡＮＪＡＬＩＰ ， ＡＪＡＹＳ ， ＳＡＰＲＥＳＤ ． Ａ ｒｅｖｉｅｗ ｏｎ ｎａｔｕｒａｌ ｉｍａｇｅ ｄｅｎｏｉ 唱 ｓｉｎｇ ｕｓｉｎｇ ｉｎｄｅｐｅｎｄｅｎｔ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ （ ＩＣＡ ） ｔｅｃｈｎｉｑｕｅ ［ Ｊ ］． Advances in Computational Research，２０１０， 2（１）：６唱１４． ［６２］ 蔡泽民，赖剑煌．一种基于超完备字典学习的图像去噪方法［ Ｊ ］． 电子学报，２００９，37（２）： ３４７唱３５０． ［６３］ 李恒建 尹忠科，王建英．基于量子遗传优化算法的图像稀疏分解 ［ Ｊ ］．西南交通大学学报，２００７，42（１）：１９唱２３． （上接第 ４０５ 页） ［２４］ ＰＩＮＴＯＧＨＬ ， ＶＥＲＧＩＬＩＯＳＲ ． Ａ ｍｕｌｔｉ 唱 ｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ２２ ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅ 唱 ｒｅｎｃｅ ｏｎ Ｔｏｏｌｓ ｗｉｔｈ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ．２０１０：１２９唱１３４． ［２５］ ＭｃＭＩＮＮＰ ， ＨＯＬＣＯＭＢＥＭ ． Ｔｈｅ ｓｔａｔｅ ｐｒｏｂｌｅｍ ｆｏｒ ｅｖｏｌｕｔｉｏｎａｒｙ ｔｅｓ 唱 ｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏ 唱 ｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ ． Ｂｅｒｌｉｎ ： Ｓｐｒｉｎｇｅｒ 唱 Ｖｅｒｌａｇ ， ２００３：２４８８唱２４９８． ［２６］ ＤＯＲＩＧＯＭ ， ＧＡＭＢＡＲＤＥＬＬＡＬＭ ． Ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ ： ａ ｃｏｏｐｅｒａ 唱 ｔｉｖｅ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ ［ Ｊ ］．IEEE Trans on Evolutionary Computation，１９７７，1（１）： ５３唱６６． ［２７］ 傅博．基于蚁群算法的软件测试数据自动生成［ Ｊ ］．计算机工程 与应用， ２００７，43（１２）： ９７唱９９． ［２８］ ＤＯＥＲＮＥＲＫ ， ＧＵＴＪＡＨＲＷＪ ． Ｅｘｔｒａｃｔｉｎｇ ｔｅｓｔ ｓｅｑｕｅｎｃｅｓ ｆｒｏｍ ａ Ｍａｒｋｏｖ ｓｏｆｔｗａｒｅ ｕｓａｇｅ ｍｏｄｅｌ ｂｙ ＡＣＯ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ 唱 ｆｅｒｅｎｃｅ ｏｎ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ ． Ｂｅｒｌｉｎ ： Ｓｐｒｉｎｇｅｒ 唱 Ｖｅｒｌａｇ ， ２００３：２４６５唱２４７６． ［２９］ ＬＩＨｕａｉ 唱 ｚｈｏｎｇ ， ＬＡＭＣＰ ． Ｓｏｆｔｗａｒｅ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｕｓｉｎｇ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ｗｏｒｌｄ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅ ， Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ．２００５：１唱４． ［３０］ ＬＩＫｅ 唱 ｗｅｎ ， ＺＨＡＮＧＺｉ 唱 ｌｕ ， ＬＩＵＷｅｎ 唱 ｙｉｎｇ ． Ａｕｔｏｍａｔｉｃ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｂａｓｅｄ ｏｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ５ ｔｈ Ｉｎ 唱 ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎａｔｕｒａｌ Ｃｏｍｐｕｔａｔｉｏｎ ．２００９：２１６唱２２０． ［３１］ 陈明师， 刘晓洁， 李涛．基于多态蚁群算法的测试用例自动生成 ［ Ｊ ］．计算机应用研究， ２００９， 26（６）：２３４７唱２３４８． ［３２］ ＸＵＤｕｏ 唱 ｙｏｎｇ ， ＬＩＺｈｉ 唱 ｓｈｕ ． Ｓｔｕｄｙ ｏｎ ｔｅｓｔ ｃａｓｅ ａｕｔｏｍａｔｅｄ ｇｅｎｅｒａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｙ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌ 唱 ｇｏｒｉｔｈｍ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｃｏｎ 唱 ｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， ２０１０： ５６５５唱５６５８． ［３３］ ＷＩＮＤＩＳＣＨＡ ， ＷＡＰＰＬＥＲＳ ， ＷＥＧＥＮＥＲＪ ． Ａｐｐｌｙｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｏ ｓｏｆｔｗａｒｅ ｔｅｓｔｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ９ ｔｈ Ｇｅｎｅｔｉｃ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ ． Ｎｅｗ Ｙｏｒｋ ： ＡＣＭＰｒｅｓｓ ， ２００７：１１２１唱１１２８． ［３４］ ＫＥＮＮＥＤＹＪ ， ＥＢＥＲＨＡＲＴＲ ． Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｔｒａｌ Ｎｅｔｗｏｒｋｓ ． Ｐｉｓ 唱 ｃａｔａｗａｙ ： ＩＥＥＥＰｒｅｓｓ ， １９９５：１９４２唱１９４８． ［３５］ 李爱国， 张艳丽．基于 ＰＳＯ 的软件结构测试数据自动生成方法 ［ Ｊ ］．计算机工程， ２００８，34（６）： ９３唱９７． ［３６］ ＨＬＡＫＨＳ ， ＣＨＯＩＹＳ ， ＰＡＲＫＪＳ ． Ａｐｐｌｙｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉ 唱 ｚａｔｉｏｎ ｔｏ ｐｒｉｏｒｉｔｉｚｉｎｇ ｔｅｓｔ ｃａｓｅｓ ｆｏｒ ｅｍｂｅｄｄｅｄ ｒｅａｌ ｔｉｍｅ ｓｏｆｔｗａｒｅ ｒｅｔｅｓｔ 唱 ｉｎｇ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ８ ｔｈ ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ Ｗｏｒｋｓｈｏｐｓ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥＣｏｍ 唱 ｐｕｔｅｒ Ｓｏｃｉｅｔｙ ，２００８：５２７唱５３２． ［３７］ ＣＵＩＨｕａｎ 唱 ｈｕａｎ ， ＣＨＥＮＬｉ ， ＺＨＵＢｉａｎ ， et al． Ａｎ ｅｆｆｉｃｉｅｎｔ ａｕｔｏｍａｔｅｄ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｍｅｔｈｏｄ ［ Ｃ ］／／ Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅａｓｕｒｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｍｅｃｈａｔｒｏｎｉｃｓ Ａｕｔｏｍａｔｉｏｎ ． Ｗａｓｈｉｎｇｔｏｎ ＤＣ ： ＩＥＥＥＣｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ ， ２０１０：４５３唱４５６． ［３８］ 周红， 张胜， 刘琳岚， 等．基于 ＧＡ 唱 ＰＳＯ 算法的路径测试数据自 动生成［ Ｊ ］．计算机应用研究， ２０１０，27（４）：１３６６唱１３６９． ［３９］ ＮＡＹＡＫＮ ， ＭＯＨＡＰＡＴＲＡＤＰ ． Ａｕｔｏｍａｔｉｃ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｆｏｒ ｄａｔａ ｆｌｏｗ ｔｅｓｔｉｎｇ ｕｓｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ ］．Contempora唱 ry Computing，２０１０，95（２）： １唱１２． ·３１４·第 ２ 期 郭德全，等：基于稀疏性的图像去噪综述