花朵授粉算法的研究及在测试数据自动生成中的应用_董跃华

第37卷第5期

江西理工大学学报

ＪｏｕｒｎａｌｏｆＪｉａｎｇｘｉＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ

DOI:10.13265/j.cnki.jxlgdxxb.2016.05.012

Vol.37, No.5Oct. 2016

2016年10月

文章编号：2095-3046（2016）05-0072-07

花朵授粉算法的研究及在测试数据

自动生成中的应用

董跃华，

摘

谭星成

（江西理工大学信息工程学院，江西赣州341000）

要：为了提高测试数据自动生成的效率, 通过分析基本花朵授粉算法（FPA ）的寻优性能，提出

一种基于禁忌搜索的自适应步长花朵授粉算法（TS-ASFPA ）并将其应用于测试数据的自动生成中. 首先针对花朵授粉算法收敛速度慢、寻优精度低的问题，根据当前解的位置状态，提出一个步长因子来实时地对步长的大小进行适应调整，使搜索范围更靠近最优解所在的区域；其次，引入禁忌搜索算法以克服花朵授粉算法易陷入局部极值的缺陷；最后将该算法与其他几种典型的智能算法作比较，通过对公开的测试程序集进行实验对比，表明该算法在测试用例自动生成上的可行性和高效性.

关键词：花朵授粉算法；禁忌搜索算法；测试数据自动生成；步长因子中图分类号：TP301.6

文献标志码：A

Research on flower pollination algorithm and its application in

automatic generation of test data

DONG Yuehua, TAN Xingcheng

(Schoolof Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China)

Abstract ：In order to improve the efficiency of test data automatic generation, through the analysis of optimization ability of the basic flower pollination algorithm, an adaptive step flower pollination algorithm based on tabu search algorithm is put forward and applied in the automatic generation of test data. Firstly, with the focus on the issue of low accuracy computation, slow speed convergence, according to the position of the current solution, a step length factor is proposed to adjust the length of step in real time to make the search range closer to the region where the optimal solution is located. Secondly, a tabu search algorithm is introduced to overcome the defect that the basic flower pollination algorithm is easily caught in local extremal. Finally, the algorithm is compared with several other typical intelligence algorithms, and the open -test assembly comparative test confirms the feasibility and efficiency of the algorithm in software testing.

Key words ：flower pollination algorithm; tabu search algorithm; automatic generation of test data; step length factor

作为测试过程中的基础和核心部分，其作用是测试

0引言程序的某一项功能，其生成问题影响着测试的效率. 目前有专家学者将蚁群算法[1]、遗传算法[2]、粒子群算法[3]等智能算法应用于测试数据的自动生成

软件测试伴随着整个软件生存周期，测试数据

收稿日期：２０１6-05-18

基金项目：国家自然科学基金资助项目（６１５６１０２４）

：董跃华（），女，副教授，主要从事数据挖掘、软件工程、，E-mail ：

第３７卷第５期

中，并取得一定的成果.

董跃华，等：花朵授粉算法的研究及在测试数据自动生成中的应用

现的，其中根据授粉对象的不同可以分为异花授粉和自花授粉两种形式. 异花授粉主要通过动物来传播花粉，能够进行长距离的授粉，故异花授粉又称为全局授粉；自花授粉是花朵之间的短距离授粉过程，故又成为局部授粉. FPA 是根据花朵全局授粉和局部授粉过程的一种群体智能优化算法，FPA 通过全局授粉和局部授粉两个操作算子来对复杂问题进行优化求解[12]. 首先，设定以下4个理想条件[13]：

花朵授粉算法[4]是一种通过模拟自然界中花朵授粉过程的新型智能优化算法，已经将其用于解决多目标优化问题[5]，并取得了不错的成果. 该算法和粒子群算法一样具有参数少、易实现的优点，具有较强的全局寻优能力，并且FPA 根据转换概率参数ρ的大小来判断是进行全局授粉操作还是局部授粉操作，从而有利于更快更好地找到最优解的所在的位置. 但FPA 也有着在迭代中后期寻优精度低、收敛速度慢及易陷入局部极值的缺陷，针对

FPA 的缺陷，提出一种改进的FPA 并将其应用于测试数据的自动生成中.

通过对FPA 的不足之处进行分析，Abdel -

1）异花授粉过程主要是自然界中的昆虫或者风力采取Levy 飞行机制对花粉进行传播；

2）自花授粉过程是在局部小范围内进行的授粉

过程；

Raouf 等[6]为了加强算法的寻优性能，在算法的初

期利用粒子群算法来生成初始解以提高解的质量；

3）类似昆虫这样的传粉者被认为是花朵植物的

一种恒常性，相当于一个与两朵花的相似度成比例的繁衍概率；

Wang 等[7]认为解的不同维数之间会妨碍算法的搜

索速度和寻优精度，因此提出对解进行逐维改进并对局部进行深度搜索以提高搜索速度和寻优精度；

4）转换概率P ∈[0，1]控制着全局授粉和局部授粉之间的转换，其中更倾向于局部授粉.

在自然界中，显花植物不止会开出一朵花朵，并且每朵花又可以产生上亿个花粉配子，为了把问题简单化，假设每株显花植物都只能开出一朵花，且每朵花只能对应地生成一个花粉配子.

算法的具体实现步骤如下：

K.Lenin 等[8]将和声算法融入到FPA 中，并在和声

算法中加入混沌策略以提高种群多样性，为了进一步提高解的质量和寻优的精度，再将和声算法得到的最优解作为FPA 的初始解继续进行寻优操作；肖辉辉等[9]提出了一种基于复合形法的FPA ，利用复合形法来引导种群进化，先确定当前最差的解，并计算出当前种群的形心位置，再利用当前形心对当前最差的解进行映射操作以使最差的解得到改善，按照此方法进行迭代操作，不断地向最优解逼近，改进算法在收敛速度和寻优精度上得到了一定的改善.

文章首先提出一个步长因子对全局搜索和局部搜索的搜索范围大小作出进一步调整，使得每次更新迭代的范围更贴近全局最优解所在的区域，从而改善FPA 收敛速度慢、寻优精度低的问题；其次，引入TS 算法以克服FPA 易陷入局部极值的缺陷，先定义一个群体平均适应度，计算当前迭代的群体平均适应度与更新后的群体平均适应度的差值，当差值小于给定的阈值β时，开始启用TS 算法进行局部搜索；最后采用3种典型的测试程序，通过对比实验比较TS-ASFPA 算法与AMPSO 算法[10]、

Step1初始化，设定花朵种群为n ，转换概率为P ，在定义的搜索空间内随机产生n 个初始解，并计算每个解的适应度值，求出当前的最优解.

Step2花朵授粉算法通过将转换概率P 与一个0到1之间的随机数rand 相比较，来判定是选用局部授粉操作还是全局授粉操作.

当P

X i =X i +坠（X j -X k ）

t +1

（1）

其中X i 、X i 分别表示第t +1代和第t 代的第i 个花朵的花粉，坠表示[0，1]上服从均匀分布的随机数，X j 和X k 表示相同植物种类的不同花朵的花粉.

当P >rand时，进行全局授粉操作，按照式（2）对解进行更新，并对解进行越界处理.

AGA 算法[11]在自动生成数据方面的效果，以表明TS-ASFPA 算法在测试数据生成上的优越性.

X i =X i +L （X best -X i ）

t +1t t

（2）

其中L 代表的是搜索的步长大小，采用莱维飞机机制，具有一定的全局寻优性，X best 代表的是全局最优解.

1.1

相关概念

基本花朵授粉算法

，花朵授粉是依靠花粉的传播来实

Step3计算式（1）或者式（2）得到的最新解，若新解的适应度值优于当前解，则用新解代替当前解.

Step4在Step3，

新解替代当前的全局最优解.

江西理工大学学报2016年10月

当中有适应度值比当前全局最优解更好的，则用该差处理来确定步长大小，因为事先不清楚花粉之间的距离大小，因此该局部授粉过程也同样具有不确定性，不能根据当前解的实际位置来进行搜索.

针对FPA 存在的问题，需要对当前解的实际情况作出自适应步长调整，以处理好寻优精度和搜索速度之间的平衡关系，为此提出一个步长因子（step factor ，SF ）：

Step5判断是否达到算法的终止条件，若达到，

则结束迭代操作，输出最后的全局最优解，否则，返回Step2继续进行迭代更新.

1.2禁忌搜索算法

禁忌搜索算法最先由Glover [14]提出，是对人类

智力的一种模拟，其包括禁忌表、禁忌长度和藐视法则3个部分，对初始值的要求较高，通过引入禁忌表来存储最近被搜索到的解并设定一个禁忌准则来避免迂回搜索，为了不错过那些优良解，同时引入藐视法则，使得被禁忌的优良解重新回到搜索空间，从而让局部搜索领域得到扩展.

算法的具体实现步骤如下：

1exp md -md 2，P >rand

md max （3）SF ＝

md -md +1

·ε，P

max min 其中，P 是上文提到的转换概率，rand 和ε都是0到1之间的随机数，m 表示一个正整数，d i 表示当

前最优解的位置与当前解的距离大小，d max 、d min 分别表示当前最优解的位置与其余所有解位置中距离的最大值和最小值. 由于d min 表示的是距离当前最优解位置的最小值，而每次迭代的当前最优解与最终的全局最优解还有一定的空间，d min 所对应的解很可能距离最终的全局最优解更近，因此d i 与

Step1设定好禁忌长度、藐视准则和终止条件，

选取一个初始解，将禁忌表置为空；

Step2从当前解的领域中选取若干个目标值较

优的解作为算法的候选解集合；

Step3从Step2得到的一组候选解中进行藐视

准则判断，若发现满足藐视准则的解，则用该解代替当前解，将禁忌表之前的禁忌对象删除，并添加当前最佳状态所对应的对象作为新的禁忌对象；否则，进入下一个步骤；

d min 的差值很大程度上表现了当前解与最终的全局

最优解的接近程度. 当P >rand 时，对应地采取全局

搜索策略，当d i 与d min 的差值越大，说明当前解离全局最优解越远，步长要加大；当d i 与d min 的差值越小，说明当前解离最终的全局最优解越近，步长要减小. 同理，当P

·（4）S i =S max -（S max -S min ）SF

式（4）中，S max 、S min 分别代表步长的最大值和最小值，S max -S min 表示步长的波动幅度范围.

根据公式（3）和公式（4）来实现搜索步长的自适应调整，从上代解的位置状态来动态更新本次迭代的步长大小，从而具有更好的适应性，算法的寻优精度和搜索速度得到改善.

Step4从所有的非禁忌对象中选取其中最优的

解替代当前解，并用该解所对应的禁忌对象来替换原来的禁忌对象；

Step5判断算法是否达到终止条件，若达到，则结束迭代操作并输出最优化结果；否则返回Step2

继续进行迭代搜索.

2基于禁忌搜索的自适应步长花朵授粉算法（TS-ASFPA ）

2.1

自适应步长花朵授粉算法(ASFPA）

在FPA 中，生物异花授粉指的是通过莱维飞行进行的全局授粉过程，采用莱维飞行机制虽然能够扩大搜索范围，增加种群的多样性，但是其具有随机性，步长时大时小，步长越大，搜索的范围就越大，但同时降低了搜索的精度，甚至可能出现震荡现象；步长越小，搜索的精度越高，但因此减慢了搜索的速度. 因此这种寻优机制缺乏自适应性，不能根据当前解的实际情况来分配解的搜索范围大小，因此不能很好地解决寻优精度低和收敛速度慢的缺陷. 非生物自花授粉指的是局部授粉过程，该过2.2禁忌搜索算法的引用

但是算法还存在着易陷入局部极值的缺陷，这

里引入上文提到的TS 算法来克服这一缺陷，使算法快速收敛到全局最优解. 在进行TS 算法前先判断是否满足TS 算法开始的条件，文章以群体的平均适应度作为判断标准，如果更新后的的的群体平均适应度与当前的群体平均适应度的变化小于预先设定的阈值，即满足f avg －f avg ≤β时，此时表示搜索到最优解可能出现的区域，其中f avg 、f avg 表示t

t ′

第３７卷第５期董跃华，等：花朵授粉算法的研究及在测试数据自动生成中的应用

度，β表示阈值，则开始采用TS 算法进行局部搜索，由于TS 算法对初始解的要求较高，这里将当前的全局最优解放入禁忌表中，在它的邻域范围内产生一定数目的领域解，并从中选取一组候选解进行搜索，若达到算法的终止条件，则退出算法并输出最终结果作为新的全局最优解，否则，返回ASFPA 部分对解继续进行更新.

Step12根据是否满足藐视法则从Step11得到

的候选解中选取新解，若满足，则用满足藐视法则的最优解替代当前解，更新禁忌表；若不满足，则选取候选解中非禁忌对象对应的最优解替代当前解，更新禁忌表.

2.3

TS-ASFPA 算法的运行步骤

根据第2.1节和2.2节的分析，TS-ASFPA 算

Step13判断算法是否达到结束条件，若达到，则结束迭代操作并输出最终的最优解X bext ；否则更新迭代次数t =t +1，转Step5继续进行循环操作.

法的具体运行流程如下：

3TS-ASFPA 算法的测试数据生成

3.1

测试数据生成模型

Step1对算法所涉及的参数进行设置，其中花朵的种群数设为n 、转换概率设为P 、群体平均适应度值变化阈值β、当前迭代次数t =0、最大迭代次数为t max 等参数.

Step2初始化花朵种群中每朵花朵的状态，分别计算它们所对应的适应度函数值.

Step3找出最优适应度函数值所对应的解X bext .

t f

计算群体平均适应度函数值Step4f avg ＝ΣX .

i =1Step5根据转换概率P 的大小来选择对解更新的方式，若P

md -md 2将其带入公式

（4）计算步长大小，，

md max

并用此步长对解进行更新.

Step6若P

ε，将其带入公式（4）计算步长大

max min 小，并用此步长对解进行更新.

Step7对Step5或者Step6产生的新解的适应

t i

TS-ASFPA 算法的测试数据自动生成模型可分为3大部分：测试环境的构建模块，TS-ASFPA 算法模块和测试运行模块. 测试环境的构建是建

立模型的基础，该模块对被测程序进行静态分析，然后根据选择的目标路径进行参数选择及分支函数插桩；TS-ASFPA 算法是核心部分，首先对TS-

ASFPA 进行参数设置以及初始化一组解，然后利用TS-ASFPA 算法对初始解进行迭代操作，以此来

对解进行更新，直到寻得足够优的位置或算法达到结束条件. 测试运行模块在测试数据生成模型中起到实时调用并运行的作用，它主要完成对插桩后的被测测序的实时调用和运行，再将得到的适应度值传递给TS-ASFPA 算法模块使用. TS-ASFPA 算法的测试数据生成模型如图1所示.

ΣΣΣ

3.2适应度函数的构造

适应度函数值能够反映所对应个体的优劣性，

其构造的质量好坏对求解的效率有着直接影响，这里采用对每条分支路径进行覆盖的策略来生成测试数据，借鉴Korel [15]的理论成果，采取分支函数叠加的方法来构造适应度函数，采取表1所示的方式来计算分支谓词的分支距离.

对被测程序的适应度函数的定义如下：假设被测程序的选定路径上有m 个分支，每个分支n 有个参数. 首先对被测程序进行插桩操作，即在选定路径上的每个分支点前插入相应的分支函数

度函数值进行计算，将新解的适应度函数值与当前解的适应度函数值作比较，若新解更优，则用新解代替当前解，否则，保留当前解.

Step8再用新解对应的适应度函数值与当前全

局最优解的适应度函数值作比较，若新解优于当前全局最优解，则用该新解代替当前全局最优解，否则保留当前全局最优解.

Step9根据Step7计算新的群体适应度值f avg =f X

. Σi =1n

t i

t ′

F i =f i （x 1，x 2，…，x n ），其中i =1，2，…，m . 每个分支函

数返回一个实值μi =μ（F i ）来衡量实际执行路径与

逻辑执行路径的偏差程度，则被测程序的适应度函数表达式如下：

Step10若f avg －f avg ≤β，启用TS 算法，设定好

禁忌长度、藐视准则和终止条件，将禁忌表置空，否则转Step13.

t ′t

F =Σg （μi ）

i =1

（5）

这样的一个映射

Step11将Step8得到的全局最优解X bext 作为TS 算法的初始解，在初始解的邻域范围内产生若

其中μi 和g （μi ）满足g （μi ）=关系.

≤0μ≤0

μ，μi >0

，

静态分析测试环境构造参数提取

江西理工大学学报

分支函数插桩驱动程序生成

2016年10月

1/O处理

外部变量处理

测试环境构造模块

初始化种群n 个个体

调用返回适

驱动模块被测单元

TS-ASFPA 算法

应度值

进行评估选择

更新迭代次数，对每个个体进行更新

桩模块

测试运行模块

是否满足停止条件

TS-ASFPA 运算模块

测试数据输出

结束

图1

表1

分支谓词branch i

TS-ASFPA 算法的测试数据生成模型

分支谓词的距离构造函数

分支距离函数f （branch i ）

动生成实验，3个测试程序分别为[16]：三角形类型判定程序、计算两日期之间天数差程序、直线与矩形之间的位置关系程序. 3个测试程序结构如表2.

表2

测试程序名称三角形类型判定计算两日期之间天数差

Boole n

~aa=ba!=baba>=ba&&ba ||b

if true then 0else d

-f （a ）

if |a-b|=0then0else |a-b|+dif |a-b|!=0then0else d if a-b0then 0else （b-a ）+dif a-b>=0then 0else （b-a ）+d

f （a ）+f（b ）Min （f （a ）,f （b ））

基准测试程序

变量个数分支路径数

语句数

358

51836

315392

直线与矩形之间的位置关系

其中，三角形类型判定程序是根据边长的大小对三角形的形状进行判定；计算两日期之间天数差程序是计算一年中给出的两个日期之间距离的天数；直线与矩形之间的位置关系程序是对于给定的直线与矩形来判定它们之间的相对位置关系.

4.1

实验分析

实验方案

2）参与对比实验的算法参数设置

本实验将TS-ASFPA 算法与另外两种已经应用于测试数据自动生成邻域的两种较优秀的算法（AMPSO 算法和AGA 算法）通过实验进行对比分析3.

1）实验设置

3个典型测试程序进行测试数据自

第３７卷第５期

表3

算法名称

董跃华，等：花朵授粉算法的研究及在测试数据自动生成中的应用

算法的参数设置

参数名称学习因子c 1、c 2

参数取值

平均迭代次数

[**************]0

6065

7580

8590

95100

TS-ASFPA AMPSO AGA

c 1、c 2=1.49w =0.729k 1=0.1、k 2=0.01p m 1=0.1、p m 2=0.01p c 1=0.9、p c 2=0.6

p =0.8T =10N =10

AMPSO 惯性权重w 变异概率

AGA

变异概率p m 交叉概率p c 转换概率p

TS-ASFPA 禁忌表T

种群大小

TS 邻域解个数

图3计算两日期之间天数差程序

4.2实验对比分析

4.2.1平均迭代次数的对比试验

对3种测试程序分别进行测试，记录当粒子群

的规模范围为50~100时，AMPSO 、AGA 、TS-ASFPA

由图4可知：在直线与矩形之间的位置关系程序中，TS-ASFPA 算法较AMPSO 算法在生成最优解所需的平均迭代次数上减少了大约30%；TS-

3种算法生成最优解所需的平均迭代次数，每次试验

均运行100次，实验结果如图2、图3和图4所示，其中图2说明的是以上3种算法分别对三角形分类程序进行测试生成最优解所需的平均迭代次数；图3说明的是以上3种算法分别对两天相隔日期程序进行测试生成最优解所需的平均迭代次数；图4说明的是以上3种算法分别对判断直线与矩形关系程序进行测试生成最优解所需的平均迭代次数.

403530平均迭代次数

ASFPA 算法较AGA 算法在生成最优解所需的平均迭代次数上减少了大约48%.

504540平均迭代次数

TS-ASFPA AMPSO AGA

[1**********]05

5055

TS-ASFPA AMPSO AGA

6065707580种群大小

859095100

2520151050

5055

6065

7580

8590

95100

图4直线与矩形之间的位置关系程序

4.2.2生成最优解平均耗费时间的对比试验对3种测试程序分别进行测试，记录当粒子群

的规模范围为50、75、100时，TS-ASFPA 、AMPSO 、

种群大小

AGA3种算法生成最优解所需的平均耗费时间，每次试验均运行100次，实验结果如表4.

由表4可知，在不同粒子规模的情况下：

图2三角形类型判定程序

由图2可知：在三角形类型判定程序中，TS-

1）在三角形类型判定程序中，就平均耗费时间而言，TS-ASFPA 算法较AGA 算减少了约70%，

较AMPSO 算法不相上下.

ASFPA 算法较AMPSO 算法在生成最优解所需的平均迭代次数上大约减少了39%；TS-ASFPA 算法较AGA 算法在生成最优解所需的平均迭代次数上减少了大约70%.

由图3可知：在计算两日期之间天数差程序中，TS-ASFPA 算法较AMPSO 算法在生成最优解所需的平均迭代次数上减少了大约14%；TS -

2）在计算两日期之间天数差程序中，就平均耗费时间而言，TS-ASFPA 算法较AGA 算法减少了约26%，较AMPSO 算法不相上下.

3）在直线与矩形之间的位置关系程序中，就平均耗费时间而言，TS-ASFPA 算法较AGA 算法减

少了约34%，较AMPSO 算法不相上下.

ASFPA 算法较AGA 算法在生成最优解所需的平%.

4.2.3实验结果对比分析

结合图2、图3、图4、表4，在

表4

江西理工大学学报

3种算法在生成最优解所需的

平均耗费时间上的对比

2016年10月

ASFPA 搜索后再进一步判断是否进行TS 搜索，利

用TS 优秀的局部寻优能力来弥补FPA 可能会陷入局部最优解的不足，算法的搜索速度也得到了一定程度的提高. 实验结果表明，在使用3种不同的标准测试程序的条件下，在平均迭代次数和平均耗费时间这两项指标上，TS-ASFPA 算法在自动生成测试数据的效率上有较大的改进. 然而与AMPSO 算法相比，本文提出的TS-ASFPA 算法在平均耗费时间指标上没有明显的优化，因此如何进一步缩短

粒子规模

生成最优解平均耗费时间/ms

程序类型

AMPSO AGA

三角形类型判定

TS-ASFPA 168.6169.7280.3165.5172.4286.3192.4174.6303.7

167.2560.6170.5565.3273.8986.2166.2583.4168.6590.3298.6995.7192.7630.5167.6690.7312.81020.4

50计算两日期之间天数差直线与矩形之间的位置关系

三角形类型判定

75计算两日期之间天数差直线与矩形之间的位置关系

三角形类型判定

TS-ASFPA 算法的运行时间是下一步的研究方向.

参考文献：

[1]傅博. 基于蚁群算法的软件测试数据自动生成[J].计算机工程与

应用,2007,43(12):97-99.

100计算两日期之间天数差直线与矩形之间的位置关系

[2]律亚楠. 基于遗传算法的测试数据生成研究[D].汕头：汕头大学, 2008.

[3]Kennedy J, Eberhart R. Particle swarm optimization [C]//IEEE

International Conference on Neural Networks, 1995:1942-1948.

同的测试程序下：

[4]Yang X S. Flower pollination algorithm for global optimization[C]//International Conference on Unconventional Computing and Natural Computation. Springer Berlin Heidelberg, 2012:240-249. [5]Yang X S, Karamanoglu M, He X. Multi-objective flower algorithm for optimization[J].Procedia Computer Science, 2013, 18:861-868. [6]Abdel-Raouf O, Abdel-Baset M. A new hybrid flower pollination algorithm for solving constrained global optimization problems [J].International Journal of Applied Operational Research -An Open Access Journal, 2014, 4(2):1-13.

[7]Wang R, Zhou Y. Flower pollination algorithm with dimension by

dimension improvement[J].Mathematical Problems in Engineering, 2014:81791.

[8]Lenin K. Shrinkage of active power loss by hybridization of flower pollination algorithm with chaotic harmony search algorithm [J].Control Theory Inform, 2014(4):31-38.

[9]肖辉辉, 万常选, 段艳明. 一种基于复合形法的花朵授粉算法[J].小型微型计算机系统,2015,6(6):1373-1378.

1）在生成最优解所需的平均迭代次数方面，TS-ASFPA 算法较AMPSO 算法减少了大约30%，较AGA 算法减少了大约50%.

2）在生成最优解所需的平均耗费时间方面，TS-A SFPA 算法较AGA 算法减少了约30%，较AMPSO 算法而言不相上下.

综上所述，文章提出的TS-ASFPA 算法把一种自适应步长FPA 和TS 算法进行融合，首先采用自适应FPA 进行搜索，再根据是否满足TS 算法开始的条件来启用TS 算法进一步进行搜索，有效地解

决了容易陷入局部极值的问题，寻优能力得到明显提高. 就生成最优解所需的平均迭代次数而言，

TS-ASFPA 算法明显优于AMPSO 算法和AGA 算

法；就生成最优解所需的平均耗费时间而言，相比较AGA 算法，算法的执行速度得到了较大的提高，与AMPSO 算法的平均耗时相当. 因此与AMPSO 、

[10]邵楠, 周雁舟, 惠文涛, 等. 基于自适应变异粒子群优化算法的测

试数据生成[J].计算机应用研究,2015,32(3):786-789.

[11]李军, 李艳辉, 彭存银. 基于自适应遗传算法的路径测试数据生

成[J].计算机工程,2009,35(2):203-205.

AGA 两种算法相比，TS-ASFPA 算法在测试数据自动生成方面具有更高的效率.

[12]井福荣, 郭肇禄, 罗会兰. 一种使用反向学习策略的改进花粉授

粉算法[J].江西理工大学学报,2015，36(3):101-106.

5结语

[13]肖辉辉, 万常选, 段艳明. 一种改进的新型元启发式花朵授粉算

法[J].计算机应用研究,2016,33(1):126-131.

[14]Glover F. Tabu search-part I[J].ORSA Journal on computing, 1989,

寻找好的测试用例自动生成方案是软件测试中需解决的问题，文章提出了TS-ASFPA 算法并将其应用于测试数据生成领域. 该算法通过结合两种算法得到了TS -ASFPA 混合优化算法，TS -

1(3):190-206.

[15]Korel B. Automated software test data generation[J].IEEE Transactions

on Software Engineering, 1990, 16(8):870-879.

[16]Chatterjee A, Siarry P. Nonlinear inertia weight variation for

dynamic adaptation in particle swarm optimization[J].Computers and Operations Research, 2006, 33(3):859-871.

ASFPA 继承了ASFPA 和TS 各自的优点，在进行

第37卷第5期

江西理工大学学报

ＪｏｕｒｎａｌｏｆＪｉａｎｇｘｉＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ

DOI:10.13265/j.cnki.jxlgdxxb.2016.05.012

Vol.37, No.5Oct. 2016

2016年10月

文章编号：2095-3046（2016）05-0072-07

花朵授粉算法的研究及在测试数据

自动生成中的应用

董跃华，

摘

谭星成

（江西理工大学信息工程学院，江西赣州341000）

要：为了提高测试数据自动生成的效率, 通过分析基本花朵授粉算法（FPA ）的寻优性能，提出

关键词：花朵授粉算法；禁忌搜索算法；测试数据自动生成；步长因子中图分类号：TP301.6

文献标志码：A

Research on flower pollination algorithm and its application in

automatic generation of test data

DONG Yuehua, TAN Xingcheng

(Schoolof Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China)

Key words ：flower pollination algorithm; tabu search algorithm; automatic generation of test data; step length factor

作为测试过程中的基础和核心部分，其作用是测试

软件测试伴随着整个软件生存周期，测试数据

收稿日期：２０１6-05-18

基金项目：国家自然科学基金资助项目（６１５６１０２４）

：董跃华（），女，副教授，主要从事数据挖掘、软件工程、，E-mail ：

第３７卷第５期

中，并取得一定的成果.

董跃华，等：花朵授粉算法的研究及在测试数据自动生成中的应用

FPA 的缺陷，提出一种改进的FPA 并将其应用于测试数据的自动生成中.

通过对FPA 的不足之处进行分析，Abdel -

1）异花授粉过程主要是自然界中的昆虫或者风力采取Levy 飞行机制对花粉进行传播；

2）自花授粉过程是在局部小范围内进行的授粉

过程；

Raouf 等[6]为了加强算法的寻优性能，在算法的初

期利用粒子群算法来生成初始解以提高解的质量；

3）类似昆虫这样的传粉者被认为是花朵植物的

一种恒常性，相当于一个与两朵花的相似度成比例的繁衍概率；

Wang 等[7]认为解的不同维数之间会妨碍算法的搜

索速度和寻优精度，因此提出对解进行逐维改进并对局部进行深度搜索以提高搜索速度和寻优精度；

4）转换概率P ∈[0，1]控制着全局授粉和局部授粉之间的转换，其中更倾向于局部授粉.

算法的具体实现步骤如下：

K.Lenin 等[8]将和声算法融入到FPA 中，并在和声

Step1初始化，设定花朵种群为n ，转换概率为P ，在定义的搜索空间内随机产生n 个初始解，并计算每个解的适应度值，求出当前的最优解.

Step2花朵授粉算法通过将转换概率P 与一个0到1之间的随机数rand 相比较，来判定是选用局部授粉操作还是全局授粉操作.

当P

X i =X i +坠（X j -X k ）

t +1

（1）

其中X i 、X i 分别表示第t +1代和第t 代的第i 个花朵的花粉，坠表示[0，1]上服从均匀分布的随机数，X j 和X k 表示相同植物种类的不同花朵的花粉.

当P >rand时，进行全局授粉操作，按照式（2）对解进行更新，并对解进行越界处理.

AGA 算法[11]在自动生成数据方面的效果，以表明TS-ASFPA 算法在测试数据生成上的优越性.

X i =X i +L （X best -X i ）

t +1t t

（2）

其中L 代表的是搜索的步长大小，采用莱维飞机机制，具有一定的全局寻优性，X best 代表的是全局最优解.

1.1

花朵授粉算法的研究及在测试数据自动生成中的应用_董跃华

相关内容

热门内容

标签