改进PSO算法在软件测试数据生成中的应用.pdf

ＣＮ４３－１２５８／ＴＰ计算机工程与科学２０１２年第３４卷第１期
ＩＳＳＮ１００７－１３０ＸＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥＶｏｌ．３４，Ｎｏ．１，２０１２

文章编号：１００７－１３０Ｘ（２０１２）０１－００８６－０４

＊
改进ＰＳＯ算法在软件测试数据生成中的应用
ＡｐｐｌｉｃａｔｉｏｎｏｆａｎＩｍｐｒｏｖｅｄＰａｒｔｉｃｌｅＳｗａｒｍ
ＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍｉｎＳｏｆｔｗａｒｅ
ＴｅｓｔＤａｔａＧｅｎｅｒａｔｉｏｎ

时贵英

ＳＨＩＧｕｉ－ｙｉｎｇ
（东北石油大学计算机与信息技术学院，黑龙江大庆１６３３１８）
（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＮｏｒｔｈｅａｓｔＰｅｔｒｏｌｅｕｍＵｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ１６３３１８，Ｃｈｉｎａ）

摘要：软件测试是软件质量保证的重要手段，测试用例自动生成一直是被广泛研究的问题。本文在
分析了遗传算法、粒子群算法和蚁群算法的优缺点后，在软件测试用例的自动生成过程中采用一种新改进
的粒子群算法。该算法将蚁群算法的信息素机制引入到粒子群算法中，加大了粒子间的多样性，有效地克
服了粒子群算法容易发生早熟停滞的缺陷。最后通过仿真实验证明了算法应用于软件测试的可行性和高
效性。
Ａｂｓｔｒａｃｔ：Ｓｏｆｔｗａｒｅｔｅｓｔｉｎｇｉｓａｎｉｍｐｏｒｔａｎｔｍｅａｎｓｏｆｓｏｆｔｗａｒｅｑｕａｌｉｔｙａｓｓｕｒａｎｃｅ，ｔｈｅａｕｔｏｍａｔｉｃｇｅｎｅｒ－
ａｔｉｏｎｏｆｔｅｓｔｃａｓｅｓｈａｓｂｅｅｎｗｉｄｅｌｙｓｔｕｄｉｅｄ．Ｂｙａｎａｌｙｚｉｎｇｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｇｅｎｅｔｉｃ
ａｌｇｏｒｉｔｈｍ，ｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｓａ
ｎｅｗｉｍｐｒｏｖｅｄｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍｉｎｔｈｅａｕｔｏｍａｔｉｃｇｅｎｅｒａｔｉｏｎｏｆｔｅｓｔｃａｓｅｓ．Ｔｈｅｐｈｅｒｏｍｏｎｅｍｅｃｈ－
ａｎｉｓｍｏｆｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｉｎｔｒｏｄｕｃｅｄｉｎｔｏｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｃａｎｉｎｃｒｅａｓｅｔｈｅ
ｄｉｖｅｒｓｉｔｙｏｆｐａｒｔｉｃｌｅｓａｎｄｏｖｅｒｃｏｍｅｔｈｅｄｅｆｅｃｔｔｈａｔＰＳＯｉｓｅａｓｙｔｏｐｒｅｍａｔｕｒｅａｎｄｓｔａｇｎａｔｉｏｎ．Ｆｉｎａｌｌｙｔｈｅ
ｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｐｒｏｖｅｓｔｈｅｆｅａｓｉｂｉｌｉｔｙａｎｄｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｎｓｏｆｔｗａｒｅｔｅｓｔｉｎｇ．
关键词：粒子群算法；蚁群算法；信息素机制；软件测试
Ｋｅｙｗｏｒｄｓ：ＰＳＯ；ＡＣＯ；ｐｅｒｏｍｏｎｅｍｅｃｈａｎｉｓｍ；ｓｏｆｔｗａｒｅｔｅｓｔｉｎｇ
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７－１３０Ｘ．２０１２．０１．０１５
中图分类号：ＴＰ３１１文献标识码：Ａ

算法［１～３］、粒子群算法［４］、蚁群算法［５］用于面向路
１引言径的测试用例自动生成研究中来，取得了一定的效
果。但是，任何方法都有其缺陷或不足，比如遗传
软件测试是软件质量保证的重要手段。好的算法虽然具有良好的全局搜索能力，但实现复杂，
测试用例，能发现程序中至今未发现的错误，然而且局部搜索能力差，容易发生早熟现象；同遗传算
软件测试人员通过人工构造测试用例是一项非常法比较，粒子群算法容易实现并且没有太多参数需
繁重而且开销很高的劳动，因此测试用例自动生成要调整，但在算法后期局部搜索能力较差，反馈信
一直是被广泛研究的问题。它不仅可以减少软件息利用不充分，容易陷入局部最优，导致算法出现
开发的费用，而且还可以大大提高软件的可靠性，停滞，破坏了粒子间的多样性，导致算法不再继续
缩短软件的开发周期。近年来有一些学者将遗传搜索解空间，从而发生早熟现象；蚁群算法具有正

＊收稿日期：２０１０－１２－１３；修订日期：２０１１－０３－１１
通讯地址：１６３３１８黑龙江省大庆市东北石油大学计算机与信息技术学院
Ａｄｄｒｅｓｓ：ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＮｏｒｔｈｅａｓｔＰｅｔｒｏｌｅｕｍＵｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ，Ｈｅｉｌｏｎｇｊｉａｎｇ１６３３１８，Ｐ．Ｒ．Ｃｈｉｎａ
时贵英：改进ＰＳＯ算法在软件测试数据生成中的应用７８

反馈性、并行性、强收敛性以及鲁棒性，但由于搜索
初期信息素相对匮乏，导致算法的搜索效率降低，３改进的ＰＳＯ算法
容易产生停滞早熟现象。一种有效的方法是将粒