《基于文化粒子群算法的软件缺陷定位方法》-工学论文，计算机论文-论文范文参考-科学狗论文网

标题

基于文化粒子群算法的软件缺陷定位方法

范文

王宪勇石建树

摘要：自动化软件缺陷定位方法能够在无人工干预下快速定位软件中缺陷位置，但是不少缺陷定位方法存在定位准确性低的问题。为了提升软件缺陷定位的准确性，提出一种基于文化粒子群算法的软件缺陷定位方法CAPSOFaL，该方法使用缺陷程序实体构建算法种群，通过两个进化空间的协作得到最优解，并通过分析最优解得到测试程序内的真实缺陷位置。该方法能够减少冗余信息对实体怀疑值计算的干扰，并显著提升真实缺陷位置在缺陷报告中的排名，进而提升缺陷定位的准确性。

关键词：软件测试;缺陷定位;文化算法;粒子群算法

中图分类号：TP311.5 文献标识码：A

文章编号：1009-3044（2019）31-0271-02

1概述

随着软件规模的不断扩大，软件中包含的缺陷也越来越多，这些缺陷影响软件的可靠性，甚至阻碍软件的正常运行，如何快速准确地找到软件中的缺陷位置，成为开发维护人员关注的重点。传统的人工调试消耗大量的时间和人力资源，而且随着软件规模的扩大已经力不从心。自动化软件缺陷定位方法的出现就是为了将开发人员从繁重的调试中解放出来。在已有的自动化软件缺陷定位方法中，基于频谱的缺陷定位方法（program Spectrum based Fault Localization，简称sFL）定位效果表现优秀。该方法收集程序中每个实体的测试用例的执行覆盖情况，并与执行结果一起构成该程序的频谱信息，通过统计计算频谱信息得出实体的怀疑值，最后生成缺陷分析报告从而辅助开发人员进行缺陷定位和修复。图1给出了SFL方法缺陷定位的流程。

在SFL方法中，Tarantula、Ochiai、Jaccard等方法因为实现简单，定位效果较好而受到广泛关注。这些方法可以计算并生成一个实体怀疑值的降序序列，该序列中位置越靠前的实体，越有可能是程序中的真实缺陷位置。但是在生成的序列中，排在序列前端的具有较高怀疑值的实体，往往是缺陷程序中被失败测试用例和成功测试用例同时较多覆盖的非缺陷实体。因此，提出一种基于文化粒子群算法的缺陷定位方法CAPSOFaL，该方法将缺陷程序中的每个实体作为一个怀疑元素，通过怀疑元素的不同组合来构建个体，并在粒子群算法的基础上增加信度空间，采用大小种群差速进化、互相影响的方式，进一步强化最优个体对种群进化的引导，从而减少冗余信息对实体怀疑序列构建的干扰，提升真实缺陷位置在实体怀疑序列中的排名，并最终提升缺陷定位效果。

2文化粒子群算法

文化粒子群算法由两部分构成，一部分是粒子群算法，另一部分是根据文化算法的思想构建的信度空间，下面将给出这两种算法以及文化粒子群算法的具体描述。

2.1文化算法

文化算法（Cultural Algorithm，简称CA）是1994年Reynolds受到文化的进化对人类文明进化的影响而提出的一种双层进化机制。该机制的创新之处在于，除了传统的种群进化空间之外，新添加了信度空间，将知识的概念融人种群的进化中，从而加快了整个种群的进化速度。文化算法的基本结构将在图2中给出。

信度空间由种群知识构成，是文化算法的核心。种群知识是指种群中个体的进化经验与信息，这些知识可以分为五大类：状态知识、规范知识、地势知识、领域知识和历史知识。其中，状态知识和规范知识较为重要，状态知识反映了种群进化的线性过程，规范知识反映了种群随着进化的加深其搜索空间的不断变化。信度空间的构建主要通过接受函数从原始种群进行选拔，满足条件的个体才会被允许进入信度空间。而信度空间产生的知识将通过影响函数对原始种群的进化进行引导。接受函数和影响函数的形式将在下面给出。

2.2粒子群算法

粒子群算法（Particle Swarm Optimization，简称PSO），也称为粒子群优化算法，是一种模拟鸟群觅食行为的群体智能优化算法。该方法通过模拟庞大的鸟群在一定范围内搜索未知位置的食物的行为，来得到待解决问题的最优解。在粒子群算法中，鸟群对应算法的种群，鸟群的搜索范围对应问题的解空间，也就是算法的搜索空间，鸟群的搜索行为对应种群的进化，未知食物位置搜索对应搜索问题的最优解。算法的搜索过程可以描述为：将问题的解空间作为算法的搜索空间，将问题的每个可能解映射为一个粒子位置，通过适应度函数的控制，使得种群中的個体向最优个体的位置靠近，算法进化终止后种群内适应度函数值最高的粒子位置，即为当前问题的最优解。粒子群算法中最重要的步骤就是个体的速度及位置更新，下面将在公式（3）（4）（5）中给出具体形态。

2.3文化粒子群算法

文化粒子群算法结合粒子群算法和文化算法的优势，在原始种群进化空间的基础上，增加信度空间，在接受函数的控制下形成小规模的最优种群，通过加速进化的方式，获得原始种群下一步的进化方向，并通过影响函数引导原始种群的进化，并最终提升整体进化速度。在种群的构建上，给缺陷程序中的每个实体赋上唯一的编号并作为一个怀疑元素，将固定长度的随机怀疑元素的组合作为粒子，算法结束时产生的最优粒子位置即为缺陷程序的实体怀疑序列。粒子的形态为：

{9，5，6，8，7，4，1，3，2}

示例中假设缺陷程序内包含9个实体，每一个数字唯一标识一个实体，红色标识的数字表示假设的缺陷位置。为了正确评价这种特殊形态的粒子，适应度函数设计为两种相似性的比值，其中一种相似性为失败相似性，它表示一个粒子中包含失败执行轨迹中元素的数量，同理，成功相似性为粒子中包含成功轨迹中元素的数量。适应度函数的形态将在公式4中给出。

通过新生成的粒子位置{9，5，6，8，6，7，3，4，}可以看到，假设的缺陷位置已经挪动到了序列的前端。在序列中元素6出现了两次，原因是示例中粒子位置的移动只受到gtest的影响而缺少pbest的影响，在实际的进化情况，粒子位置的移动不会只受一种最优位置的影响，所以怀疑元素重复出现的情况不会发生。最终，进化完成的算法将产生一个最优粒子位置，假设最优粒子位置为：{5，8，9，6，7，3，4，1，2}，则生成的缺陷位置报告为：

3结论

本文提出的基于文化粒子群算法的软件缺陷定位方法CAPSOFaL，能够提升真实缺陷位置在缺陷报告中的排名，提高了缺陷定位的准确性，减少了开发人员搜寻缺陷位置的工作量。下一步将在缩减方法时间复杂度的情况下进一步提升缺陷定位的精确度。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。