基于GA-PSO算法的路径测试数据自动生成(2)

PSO

第４期

周红，等：基于ＧＡ－ＰＳＯ算法的路径测试数据自动生成

１３６７

遗传算法的基本步骤如下：

ａ）初始化产生问题解的初始种群；

ｂ）计算种群适应度，如果找到最优解或迭代次数达到最大，则转到ｆ）；

ｃ）选择操作；ｄ）交叉操作；

ｅ）变异操作，转向ｂ）；ｆ）算法结束。

选择操作的方法有轮盘赌法、随机遍历抽样法、锦标赛选择法等，其中最常用的是轮盘赌法；交叉操作有单点交叉、多点交叉、均匀交叉等不同的交叉方法；变异操作随机选取符号串中的一个基因，并将其改变，以产生一个新的符号串。该操作将可变性引入群体，从而为逃离局部最优提供手段。１．２粒子群算法

粒子群算法（ｐａｒｔｉｃｌ阜ｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）是由Ｅｂｅｒ－ｈａｒｔ和Ｋｅｎｎｅｄｙ于１９９５年提出的一种源于对鸟类捕食行为的高效并行搜索寻优算法。ＰＳＯ的基本算法流程如下：

ａ）在整个搜索空间上随机初始化整个粒子群的位置和速度，并计算每个粒子在当前位置处的适应度函数值兀，相应地初始化ｐｏ诅＝厶，ｐｏ州＝ｍａ】【Ｕ，…Ｚ，…Ｚ），ｉ＝ｌ，２，…，ｎ。

ｂ）在每次迭代过程中，每个粒子根据以下准则来更新自己的位置和速度。

出１＝硝＋ｃｎ（吨一＊乞）＋ｃ２ｒ２（出一吨）

（２）缸｛蔓。芝：蔓

（３）ｚ岔１＝ｚ乞＋如

（４）并磊＝｛

。

ｒ玩一＃乞＞‰一

Ｌ—ｘ抽ｚ厶＜一工缸

。

（５）

ｃ）更新ｐ：和ｐ：。

ｄ）如果满足中止准则，算法结束；否则，转向ｂ）。

上述算法中以表示ｄ维搜索空间中第ｉ个粒子适应度函数值；丑表示第一次迭代前第ｉ个粒子适应度函数值；ｐｏｄ表示

第一次迭代前整个种群ｄ维搜索空间中的最佳位置。

式（２）为粒子速度更新准则，其中屹“表示ｄ维搜索空间

中第ｉ个粒子的第ｋ＋１代迭代速度；甜是惯性因子，一般采用

公式∞＝∞一一Ｉ鼍急盖产获得，ｔ表示当前代数，ｍａｘＤＴ表示

最大迭代次数；ｃ。、ｃ：表示加速系数（或称学习因子），ｃ。称为认知参数（ｃｏｇｎｉｔｉｖｅ），Ｃ：称为社会参数（ｓｏｃｉａｌ），分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长；ｒ。、ｒ２为［Ｏ，１］之间的随机数。

式（４）为粒子位置更新准则，其中髫乞为所搜索的ｄ维空间

中粒子ｉ在第后次迭代中的当前位置；式（３）限制粒子的最大飞行速度；式（５）控制粒子的飞行范围。

２应用于测试数据自动生成的混合算法

软件测试数据自动生成方法一般可以分成功能测试数据自动生成方法和结构测试数据自动生成方法。本文结合遗传算法和粒子群算法的思想和各自的特性，将两者进行有机结合形成两者的混合算法ＧＡ－Ｐｓｏ算法，并将该算法应用于结构测试数据自动生成过程中。相应的流程如图ｌ所示。

万　

方数据算法生成测试数据的步骤如下：

ａ）初始化种群。随机产生一定数目的初始种群，设为只，遗传算法作用于该种群。初始化种群Ｐ２＝｛咖｝，用于粒子群算法运算，初始值为空。

ｂ）计算种群Ｐ，适应度函数值。根据构造的适应度函数，分别计算每个粒子的适应度函数值。适应度值反映的是粒子实际经过路径与目标路径的距离。若实际路径满足条件，完全覆盖目标路径或者迭代次数达到最大，则转ｇ）。

ｃ）划分种群。按照适应度大小对Ｐ，中的粒子进行排序，筛选出种群Ｐ，中粒子基因较好的个体，即适应度值大的粒子，以中比例选取部分粒子加入到种群Ｐ２。

ｄ）改进种群Ｐ２个体。对种群Ｐ２采用粒子群算法，根据自身和全局最优粒子更新种群Ｐ２，得到新的种群Ｐ２。计算更新后的种群Ｐ２所有粒子的适应度函数，判断是否找到最优解或迭代次数达到最大，若找到则转ｇ）。

ｅ）重构种群Ｐ。。除去迁移到Ｐ２中参加粒子群算法的粒子，随机产生函比例的粒子补充进入Ｐ，。补充币比例的粒子是为了保持参加遗传算法粒子的个数固定。

ｆ）改进种群Ｐ。个体。种群Ｐ。采用遗传算法寻优，按照选择、交叉、变异方式得到新一代种群Ｐ。，转到ｂ）。

ｇ）输出最优解，算法结束。

３实验结果与分析

３．１

测试数据自动生成模型

ＧＡ—ＰＳＯ算法测试数据生成的模型主要包括两个模块，即

测试环境构造模块和ＧＡ．ＰＳＯ算法运行模块。模型结构如图２所示。

右侧ＧＡ－ＰＳＯ算法包是系统的核心部分，它随机地产生第一代种群，按照输入参数的编码方式将种群中的粒子映射成实际参数值，并传递给左侧的驱动程序，驱动被测单元运行。被测单元运行时计算出当前测试数据的适应函数值返回给右侧的ＧＡ．ＰＳＯ算法包，算法包据此来评价种群中每个粒子的优劣，评估每个粒子的适应度，若有满足要求的粒子则输出最优解，否则通过ＧＡ—ＰＳＯ算法形成新一代种群，如此往复，直至找到覆盖选定路径的测试数据。左侧的测试环境构造模块利用程序插装技术，在被测程序源代码级插入用于评估当前输入参数值的适应度函数，并将适应度值返回ＧＡ—ＰＳＯ算法包。本文中适应度函数采用分支函数叠加法构造，相关内容在３．３节介绍。

３．２测试实例

首先采用常用测试函数Ｒａｓｔｒｉｇｉｎ作为测试对象，ｆ（ｘ）＝

＾一ｌ

三茗；一ｌＯｃｏｓ（２１ｖｘｌ）＋ｌｏ（一１０≤聋‘≤１０），这是一个多峰函数，

最优值接近原点，基本遗传算法的寻优值为４９．４６６４，基本粒子群算法的寻优值为４９．３２１２，混合算法的寻优值为Ｏ，说明

混合算法的寻优能力更强。

其次本文选择具有代表性的三角形类型判别程序作为测试实例。因为该实例包含了清晰而又复杂的逻辑，是很多测试问题的首选程序。三角形判别程序总共包含三个输入变量（聋，Ｙ，ｚ），这个简单例子的程序如下：

ｐｕｂｌｉｃ

ｖｏｉｄ砸ａｎｇＩｅ（ｈａｔ

ｘ，ｉｎｔｙ。ｉｎｔ

ｚ）

｛

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库基于GA-PSO算法的路径测试数据自动生成(2)在线全文阅读。