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

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

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

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

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

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

３实验结果与分析

３．１

测试数据自动生成模型

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

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

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

３．２测试实例

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

＾一ｌ

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

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

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

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

ｐｕｂｌｉｃ

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

ｘ，ｉｎｔｙ。ｉｎｔ

ｚ）

｛

PSO

．１３６８

ｉｆ（ｘ＜＝０

计算机应用研究

０Ｘ＞１００）

第２７卷

由图可看出程序总共包含九条路径：路径ｌ为正（膏不满足条件）；路径２为疋瓦（Ｙ不满足条件）；路径３为咒五瓦（＝不满足条件）；路径４为瓦瓦瓦乃（不构成三角形）；路径５为疋Ｌ瓦瓦马五．（等腰直角三角形）；路径６为疋Ｌ瓦瓦ＢＬ：（直角三角形）；路径７为疋Ｌ咒瓦马正，％（等边三角形）；路径８

ｅｌｓｅ

Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｆｌｎ（”ｘ不符合条件”）；

ｉｆ（Ｙ＜＝Ｏ０Ｙ＞ｌｏｏ）Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｔｌｎ（”Ｙ不符合条件”）；ｅｌｓｅｉｆ（Ｚ＜＝０｜ｆＺ＞１００）

ｅｌｓｅ

Ｓｙｓｔｅｍ．ＯＵｔ．ｐｆｉｎｆｌｎ（”ｚ不符合条件”）；１

ｉｆ（ｘ＋Ｙ＜ｚ０ｘ＋ｚ＜Ｙ０Ｙ＋ｚ＜ｘ）

Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｔｌｎ（”不构成三角形”）；

ｅｌｓｅ

为孔ｔ乃孔巧瓦，瓦（等腰三角形）；路径９为疋瓦Ｌ瓦‰Ｔ１４

（一般三角形）。３．３构造适应度函数

｛

ｉｆ（ｘ謇ｘ＋ｙ事Ｙ＝＝ｚ ｚ８

ｘ ｘ）

ｘ＋ｘ＋ｚ事ｚ＝＝Ｙ

４

Ｙ

０

Ｙ。Ｙ＋ｚ ｚ＝＝

适应度函数是ＧＡ，ＰＳＯ算法与实际问题的惟一接口，是种群中个体优劣的一种量化反映，它的构造直接影响问题求解的效率。本文采用Ｋｏｒｅｌ【８１提出的分支函数叠加法构造适应度函数。首先将程序中各个分支谓词用分支函数，来量化，分支函数是一个分支谓词到实际值的映射，在选定路径上各分支点前插入相应的分支函数表达式（假设有ｍ个分支），Ｆ。＝＾（髫．，茗２，…，茗。），见＝．疋（菇ｌ，茗２，…，髫。），…．，Ｆｍ＝厶（茹ｌ，名２，…，髫。）ｏ由分支函数叠加得到的目标函数表达式为Ｆ＝ｍｆｌ．ｘ一（‘＋

｛０

Ｙ

４

ｉｆ（ｘ ｘ＋Ｙ Ｙ＝＝ｇ ｚ＆６Ⅸ＝＝ｙ０ｘ｝ｘ＋ｚ奉ｚ＝＝Ｙ木ｙ＆占Ⅸ＝＝ｚＹ＋ｚ ｚ＝＝ｘ ｘ＆＆ｙ２＝ｚ）

Ｓｙｓｔｅｍ．Ｏｕｔ．ｐｆｉｎｆｌｎ（”这是一个等腰直角三角形”）；

ｅｌｓｅ

Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｆｌｎ（”这是一个直角三角形”）；｝

ｅｌｓｅ

ｉｆ（ｘ＝＝ｙ＆＆ｙ＝＝ｚ）

Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｔｌｎ（”这是一个等边三角形”）；

ｅｌｓｅｉｆ（（ｘ＝＝ｙ）＆＆（ｙ！＝ｚ）０（ｘ：＝ｚ）＆＆（ｘ！＝ｙ）０（Ｙ＝＝ｚ）＆＆（Ｙ！＝ｘ））

Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｔｌｎ（“这是一个等腰三角形”）；

ｅｌｓｅ

Ｒ＋…＋Ｆ。），Ｉｌ瞰为一个较大整数。这样评价函数Ｆ归结为

被测单元的参变量茗。，茗：，石，，…，菇。的函数，其值便是评价测试数据优劣程度的尺度。３．４结果评价与分析

实验中选取其中四条路径（编号为６、７、８、９）作为测试目标。为了评价算法的优劣，分别使用简单遗传算法、粒子群算法以及ＧＡ．ＰＳＯ算法对所测试的路径进行１００次试验，记录下各种方法正确产生测试数据所需要的代数和所需ＣＰＵ时间。实验结果如表１所示。

表Ｉ

三种不同算法执行性能对比表

Ｓｙｓｔｅｍ．ｏｕｔ．ｐｆｉｎｆｌｎ（”这是一个普通三角形”）；｝｝

为了后续的表述方便，将三角形类别判别程序的流程采用如图３所示的二叉树表示。树中叶子节点表示程序运行到某一状态（即输出某一结果）；父节点和分支节点表示程序的一个分支判断，ｔ（ｉ＝１，２，…，１６）表示对应分支的判断结果（ＴＲＵＥ或ＦＡＬＳＥ）。

ｌ初始化产生种群Ｐ。，只（只为宅）Ｉ

●

ｒ－ｏ（豫示代敷）Ｉ

＜囊多是。皴；｜絮料

计算种群Ｐ．粒子适应度

●

７Ｉ

构孽黔；—ＧＡ—ＰＳＯ

Ｉ古

爿骨种群（接适应度大小捧序，

ｌ

加入种群只（适戍度人的币比倒粒子）

ｌ

改进种群Ｐ１个体（根据自身和奄局量优粒子更新）

Ｉ

得到新一代粒子群种群ｐ’

０

计算种群＾粒于适应度

嚼｛莉

ｔ

ｌ｜十

霹谜申嘲｛《刻｛遄

实验中的参数选择如下：三条边的输入变量为０～２００，种群大小为１００，最大迭代次数为５００。遗传算法采用２２位二进制数对三个输入变量编码，交叉率为０．８５，变异率为０．０５。粒子群算法采用实值编码，粒子从遗传算法中迁移过来后，先换算成相应的整型，再利用粒子群算法进行更新。其中：ｃ。＝Ｃ２－－－２，∞。。＝０．８，ｔＯ曲＝０．０７０２。适应度函数中的ｍａｘ＝

１０００．妒＝０．２。

《套芦

【随机产生咖 …… 此处隐藏：1683字，全部文档内容请下载后查看。喜欢就下载吧 ……