ＣＮ４３－１２５８／ＴＰ计算机工程与科学２０１２年第３４卷第１期ＩＳＳＮ１００７－１３０ＸＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥＶｏｌ．３４，Ｎｏ．１，２０１２文章编号：１００７－１３０Ｘ（２０１２）０１－００８６－０４＊改进ＰＳＯ算法在软件测试数据生成中的应用ＡｐｐｌｉｃａｔｉｏｎｏｆａｎＩｍｐｒｏｖｅｄＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍｉｎＳｏｆｔｗａｒｅＴｅｓｔＤａｔａＧｅｎｅｒａｔｉｏｎ时贵英ＳＨＩＧｕｉ－ｙｉｎｇ（东北石油大学计算机与信息技术学院，黑龙江大庆１６３３１８）（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＮｏｒｔｈｅａｓｔＰｅｔｒｏｌｅｕｍＵｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ１６３３１８，Ｃｈｉｎａ）摘要：软件测试是软件质量保证的重要手段，测试用例自动生成一直是被广泛研究的问题。本文在分析了遗传算法、粒子群算法和蚁群算法的优缺点后，在软件测试用例的自动生成过程中采用一种新改进的粒子群算法。该算法将蚁群算法的信息素机制引入到粒子群算法中，加大了粒子间的多样性，有效地克服了粒子群算法容易发生早熟停滞的缺陷。最后通过仿真实验证明了算法应用于软件测试的可行性和高效性。Ａｂｓｔｒａｃｔ：Ｓｏｆｔｗａｒｅｔｅｓｔｉｎｇｉｓａｎｉｍｐｏｒｔａｎｔｍｅａｎｓｏｆｓｏｆｔｗａｒｅｑｕａｌｉｔｙａｓｓｕｒａｎｃｅ，ｔｈｅａｕｔｏｍａｔｉｃｇｅｎｅｒ－ａｔｉｏｎｏｆｔｅｓｔｃａｓｅｓｈａｓｂｅｅｎｗｉｄｅｌｙｓｔｕｄｉｅｄ．Ｂｙａｎａｌｙｚｉｎｇｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ｔｈｅｐａｐｅｒｐｒｏｐｏｓｅｓａｎｅｗｉｍｐｒｏｖｅｄｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍｉｎｔｈｅａｕｔｏｍａｔｉｃｇｅｎｅｒａｔｉｏｎｏｆｔｅｓｔｃａｓｅｓ．Ｔｈｅｐｈｅｒｏｍｏｎｅｍｅｃｈ－ａｎｉｓｍｏｆｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｉｎｔｒｏｄｕｃｅｄｉｎｔｏｔｈｅｐａｒｔｉｃｌｅｓｗａｒｍａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｃａｎｉｎｃｒｅａｓｅｔｈｅｄｉｖｅｒｓｉｔｙｏｆｐａｒｔｉｃｌｅｓａｎｄｏｖｅｒｃｏｍｅｔｈｅｄｅｆｅｃｔｔｈａｔＰＳＯｉｓｅａｓｙｔｏｐｒｅｍａｔｕｒｅａｎｄｓｔａｇｎａｔｉｏｎ．Ｆｉｎａｌｌｙｔｈｅｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｐｒｏｖｅｓｔｈｅｆｅａｓｉｂｉｌｉｔｙａｎｄｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｎｓｏｆｔｗａｒｅｔｅｓｔｉｎｇ．关键词：粒子群算法；蚁群算法；信息素机制；软件测试Ｋｅｙｗｏｒｄｓ：ＰＳＯ；ＡＣＯ；ｐｅｒｏｍｏｎｅｍｅｃｈａｎｉｓｍ；ｓｏｆｔｗａｒｅｔｅｓｔｉｎｇｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７－１３０Ｘ．２０１２．０１．０１５中图分类号：ＴＰ３１１文献标识码：Ａ算法［１～３］、粒子群算法［４］、蚁群算法［５］用于面向路１引言径的测试用例自动生成研究中来，取得了一定的效果。但是，任何方法都有其缺陷或不足，比如遗传软件测试是软件质量保证的重要手段。好的算法虽然具有良好的全局搜索能力，但实现复杂，测试用例，能发现程序中至今未发现的错误，然而且局部搜索能力差，容易发生早熟现象；同遗传算软件测试人员通过人工构造测试用例是一项非常法比较，粒子群算法容易实现并且没有太多参数需繁重而且开销很高的劳动，因此测试用例自动生成要调整，但在算法后期局部搜索能力较差，反馈信一直是被广泛研究的问题。它不仅可以减少软件息利用不充分，容易陷入局部最优，导致算法出现开发的费用，而且还可以大大提高软件的可靠性，停滞，破坏了粒子间的多样性，导致算法不再继续缩短软件的开发周期。近年来有一些学者将遗传搜索解空间，从而发生早熟现象；蚁群算法具有正＊收稿日期：２０１０－１２－１３；修订日期：２０１１－０３－１１通讯地址：１６３３１８黑龙江省大庆市东北石油大学计算机与信息技术学院Ａｄｄｒｅｓｓ：ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＮｏｒｔｈｅａｓｔＰｅｔｒｏｌｅｕｍＵｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ，Ｈｅｉｌｏｎｇｊｉａｎｇ１６３３１８，Ｐ．Ｒ．Ｃｈｉｎａ时贵英：改进ＰＳＯ算法在软件测试数据生成中的应用７８反馈性、并行性、强收敛性以及鲁棒性，但由于搜索初期信息素相对匮乏，导致算法的搜索效率降低，３改进的ＰＳＯ算法容易产生停滞早熟现象。一种有效的方法是将粒