PSO
第２７卷第４期２０１０年４月
计算机应用研究
ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ
Ｖ０１．２７Ｎｏ．４Ａｐｒ．２０１０
基于ＧＡ—ＰＳＯ算法的路径测试数据自动生成
周红，张胜，刘琳岚，蔡虹
（南昌航空大学信息工程学院，南昌３３００６３）
摘要：为了实现测试数据自动生成，许多遗传算法及其改进算法应用到了测试领域。针对遗传算法具有较强的全局搜索能力，但局部搜索能力较弱，且收敛速度慢的特点。将遗传算法与粒子群算法结合起来形成新的混合算法（ＧＡ．ＰＳＯ），并成功应用到软件测试数据自动生成过程中。实验结果表明，该算法结舍了遗传算法和粒子群算法的优点，在保证软件测试数据正确生成的情况下，极大地提高了数据生成的效率。关键词：测试数据自动生成；ＧＡ－ＰＳＯ算法；软件测试中图分类号：ＴＰ３１１．５６
文献标志码：Ａ
文章编号：１００１—３６９５（２０１０）０４．１３６６．０４
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－３６９５．加１０．０４．０４３
Ａｕｔｏｍａｔｉｃｇｅｎｅｒａｔｉｏｎｏｆｐａｔｈ
ｔｅｓｔ
ｄａｔａｂａｓｅｄ
Ｏｉｌ
ＧＡ—ＰＳＯ
ＺＨＯＵＨｏｎｇ，ＺＨＡＮＧＳｈｅｎｇ，ＬＩＵＬｉｎ－ｌａｎ，ＣＡＩＨｏｎｇ
（＆ｈｏｄｏｆＩｎｆｏｒｍａｔｉｏｎ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ＮａｎｃｈａｎｇｌｔａｎｇｋｏｎｇＵｍｖｅｒｓ酊，Ｎａｎｅｈａｎｇ３３００６３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎｏｒｄｅｒｉｎｔｏ
ｔｅｓｔ
ｔｏ
ａｃｈｉｅｖｅ
ｔｏ
ｔｅｓｔ
ｄａｔａａｕｔｏｍａｔｉｃｇｅｎｅｒａｔｉｏｎ，ｍｕｃｈｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ
ｏｒ
ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｈａｄｂｅｅｎｂｍｕｇＩｌｔ
ｆｉｅｌｄ．Ａｃｃｏｒｄｉｎｇ
ｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｓｔｒｏｎｇｇｌｏｂａｌｓｅａｒｃｈ，ｂｕｔｗｅａｋｌｏｃａｌｓｅａｒｃｈａｎｄｓｌｏｗｃｏｎｖｅｒｇｅｎｃｅｏｆｇｅｎｅｔｉｃ
ａｎｅｗ
ａｌｇｏｒｉｔｈｍ，ｔｈｉｓｐａｐｅｒｐｍｐｏｓｅｄａｕｔｏｍａｔｉｃｓｏｆｔｗａｒｅ
ｔｅｓｔ
ａｌｇｏｒｉｔｈｍ（ＧＡ－ＰＳＯ）ｗｈｉｃｈｃｏｍｂｉｎｅｄＧＡａｎｄＰＳＯ，ａｎｄａｐｐｌｉｅｄｉｔｓｕｃｃｅｓｓｆｕｌｌｙｔｏ
ｄａｔａｇｅｎｅｒａｔｉｏｎ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｈａｓｃｏｍｂｉｎｅｄｔｈｅａｄｖａｎｔａｇｅｓｏｆ
ｈｙｂｒｉｄ
ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄｐａｒｔｉｃｌｅｓｗａｒｌｎｏｐｔｉｍｉｚａｔｉｏｎ，ａｎｄｉｔｇｅｎｅｒａｔｉｏｎｏｆｃｏｒｒｅｃｔｔｅｓｔｄａｔａ．
ｈａｓｇｒｅａｔｌｙｅｎｈａｎｃｅｄｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｄａｔａｇｅｎｅｒａｔｉｏｎｉｎｅｎｓｕｒｉｎｇｔｈｅ
ｔｅｓｔ
Ｋｅｙｗｏｒｄｓ：ｔｅｓｔｄａｔａａｕｔｏｍａｔｉｃｇｅｎｅｒａｔｉｏｎ；ＧＡ－ＰＳＯａｌｇｏｒｉｔｈｍ：ｓｏｆｔｗａｒｅ
软件测试是一项昂贵而又耗费劳力的工作，往往占软件开发总工作量的５０％左右…。测试的自动化是降低工作量和成本的有效途径。测试数据的自动生成则是软件自动测试的前提，因此如何自动生成测试数据就成为解决软件自动测试问题的关键。最初的测试数据自动生成领域比较常见的是随机法、符号执行法、程序插装法和迭代松弛法等，但它们对大型项目的实用性比较差，且执行效率低下。
将人工智能技术应用到软件测试数据自动生成过程中，可以极大地提高测试数据自动生成的效率。这种情况下，测试数据生成问题转换成对测试数据的搜索优化问题。不少文献介绍了相关研究成果，文献［２］将遗传算法应用于测试数据自动生成中；文献［３］将禁忌算法应用于结构测试数据自动生成中；文献［４］提出模拟退火遗传算法，在遗传算法操作之后利用退火算法进一步优化，取得了一定成果；文献［５］提出自适应遗传算法，通过自适应改变交叉率和变异率，提高了算法的覆盖率；文献［６］对遗传算法进行改进，提出了一种基于ＩＧＡ（免疫遗传算法）的测试数据自动生成方法，有效改善了遗传算法的未成熟收敛缺陷；文献［７］提出一种ＨＣＧＡ（自适应遗传算法和爬山算法相结合的改进算法），加强算法前期的全局搜索和后期的局部搜索能力。
综上所述，测试数据自动生成大部分是基于遗传算法以及其改进算法。遗传算法具有全局搜索性，但遗传算法的局部搜
收稿日期：２００９．０８．２７；修回日期：２００９—０９．２５
索性不强，其变异具有随机性，当粒子在最优解附近时，收敛速度仍然很慢，且遗传算法的选择操作会丢失一些适应度小的粒子，而这些粒子身上可能也有好的经验可以学习。为此，本文
将粒子群算法与遗传算法结合起来构成新的混合算法——
ＧＡ ＰＳＯ算法。因为粒子群算法具有很强的局部搜索能力且收敛速度快，能够有效改进遗传算法的不足。同时，由于粒子群算法中所有的粒子都单向朝自身最好粒子和种群最好粒子移动，这种单向信息流动导致其有陷入局部最优的可能性。粒子群的这种不足之处正好可由遗传算法来弥补。本文将ＧＡ．ＰＳＯ算法有效地应用到路径测试数据自动生成中，并通过实验来验证其有效性。１
相关算法
１．１遗传算法
遗传算法（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ＧＡ）是由美国Ｍｉｃｈｉｇａｎ大学的Ｈｏｕａｎｄ教授于１９７５年受生物进化论的启发而提出来的，是基于自然选择原理和遗传机制的通用搜索寻优算法。它可以定义为一个八元组：
ＳＧＡ＝（ｅＭｅ，Ｅ，Ｐｏ，Ｎ，Ｓ，Ｃ，Ｍ，ｒ）
（１）
其中：ｃｏｄｅ表示个体的编码方法；Ｅ表示个体适应度评价；Ｐｏ表示初始群体；』ｖ表示群体规模；．ｓ表示选择算子；Ｃ表示交叉算子；肘表示变异算子；Ｔ表示运行中止代数。
基金项目：江西省教育厅科技计划资助项目（ＧＪＪ０８２２３）
作者简介：周红（１９８６一），女。江西九江人，硕士研究生，主要研究方向为软件测试（ｎｕ＇ｋｘａｕｗｌ＠１２６．ｃｏｍ）；张胜（１９６８－），男，湖北罗田人，副教
授，博士。主要研究方向为人工智能、Ｗｅｂ信息抽取、无线传感嚣网络；刘琳岚（１９６８．），女，湖南东安人，教授，主要研究方向为软件工程、嵌入式系
统；蕖虹（１９８１－），女，江西南昌人，硕士，主要研究方向为数据挖掘、嵌入式系统．
万方数据