覆盖表生成蚁群算法

南京大学我们毕业啦其实是答辩的标题地方聂长海覆盖表生成蚁群算法：探索与挖掘searchbasedsoftwaretesting,SBST[McMinn2011]functionaltesting,mutationtesting,stresstesting,regressiontesting,…morethan600papers01SBSTabout340paperssearchbasedsoftwaretesting,SBST[McMinn2011]functionaltesting,mutationtesting,stresstesting,regressiontesting,…morethan600paperscombinatorialtesting,CT[Nie2011]02SBST&CTsearchbasedsoftwaretesting,SBST[McMinn2011]functionaltesting,mutationtesting,stresstesting,regressiontesting,…searchbasedcombinatorialtesting,SBCTabout30paperscombinatorialtesting,CT[Nie2011]03SBST&CTsearchbasedcombinatorialtesting,SBCTmodeltestexecutionfaultdiagnosisevaluationthemostpopularresearchfieldtestsuitegeneration04SBCTComputationalMethod(SearchMethod)evolvetestcaseevolvetestsetrandomsearchgreedysearchlocalsearch(HC,SA,TS,…)globalsearch(GA,ACO,PSO,…)05CoveringArrayGeneration06ShibaToshiaki等人对遗传算法和蚁群算法在覆盖表生成问题中的应用进行了研究，并与其他算法如AETG进行了对比；XiangChen等人对蚁群算法在组合测试变强度覆盖表生成中以及生成排序问题中的应用进行了研究；ChanghaiNie等人提出了基于搜索的组合测试，其中包括对蚁群算法覆盖表生成覆盖表的研究；研究现状（覆盖表）覆盖表生成蚁群算法变种研究覆盖表生成蚁群算法参数调优整表演化覆盖表生成蚁群算法07研究内容基于Hadoop的分布式实验过程08研究问题•Q1蚁群算法变种在求解覆盖表生成问题上是否存在差异，何种算法变种更加适合求解覆盖表生成问题？•Q2算法参数配置对实验结果又怎样的影响，是否存在一个最优参数配置？•Q3能否通过解结构调整的方式提升算法的性能？•Q4如何通过分布式技术节约实验部分的时间开销？9算法变种研究Step1：设置算法参数，初始化未被覆盖组合对队列UncoverList；Step2：当UncoverList不为空，继续，否则，算法终止；Step3：计算启发值（A），设置全局最优解，设置迭代计数器NC；Step4：设置迭代最优解，令每只蚂蚁从F1移动到Fe（B）；Step5：更新迭代最优解，更新全局最优解；Step6：局部信息素更新（C）；Step7：全局信息素更新（D）；Step8：选择最好的结果作为一条测试用例加入到CA_Set；10算法变种研究启发值计算(A)路径选择(B)局部信息素更新(C)全局信息素更新(D)方式1方式2ASISBSASACSMMAS11参数类型范围ASACSMMAS信息素指数α浮点型0α≤5启发值指数β浮点型0β≤5信息素残留系数ρ浮点型0ρ≤1蚂蚁数量m整形0迭代次数NC整形0信息素初值τinit浮点型0≤τinit≤10ACS路径选择概率q0浮点型0q01局部更新系数φ浮点型0φ≤1信息素上界τmax浮点型τminτmax≤5信息素下界τmin浮点型0τminτmax对单个参数进行研究参数组合pair-wise实验局部优化算法参数配置调优参数较多，参数配置空间庞大需要对多个覆盖表进行验证每次验证至少需要进行30次重复实验12算法参数配置调优：单参数影响实验1单参数影响实验（以α为例）010203040506070800.10.40.711.31.61.92.22.52.83.13.43.744.34.64.930次实验覆盖表平均规模(Δ)MCA1(90)CA2(64)CA3(36)MCA4(64)MCA5(81)参数α对AS算法性能的影响01020304050600.10.40.711.31.61.92.22.52.83.13.43.744.34.64.930次实验覆盖表平均规模(Δ)MCA1(90)CA2(64)CA3(36)MCA4(64)MCA5(81)参数α对ACS算法性能的影响01020304050600.10.40.711.31.61.92.22.52.83.13.43.744.34.64.930次实验覆盖表平均规模(Δ)MCA1(90)CA2(64)CA3(36)MCA4(64)MCA5(81)参数α对MMAAS算法性能的影响13算法参数配置调优：pair-wise实验2参数配置pair-wise实验——以AS为例MCA1CA2CA3MCA4MCA5CA6CA7CA8MCA9MCA10总和总均值C11001107210110233431851118748780.6667C29410066939431411848113698724.8333C39810365959731421850115714739.4C49610368949431421848111705734.6333C5959568969332411848112698730.6C69610368969432421848113710738.2667C710010870999933441850118739765.0667C89310570979531421848112711739.6333C99710267949632421849113710735.6667C109910868989932431850118733761.6667C119710670989532421849110717744.1667C129510467969632411848112709735.7C139610668979532421849112715740.6667C149810567959631421850113715743.8333C159810467969630431850113715745.6333C169910768979732431850117728754.6C179710367969432421848111708734C189610669969532411949112715744C19981097010110032431851117739771.9C209510366969631421850115712739.133314算法参数配置调优：局部调优实验3参数配置局部优化——对参数α与β的局部调优编号αβρmNCCAS-10.50.10.620200CAS-20.60.10.620200CAS-30.80.10.620200CAS-40.90.10.620200CAS-50.70.20.620200CAS-60.70.30.620200MCA1CA2CA3MCA4MCA5CA6CA7CA8MCA9MCA10总和总均值CAS-19410467969531431850112710737.5667CAS-29610367979432421849115713738.2333CAS-39510668979631411849113714739.2333CAS-49710568969532401848111710739.3333CAS-59710468969431411849113711739.4CAS-69710568979432411849113714738.7667C29410066939431411848113698724.833315算法参数配置调优：局部调优实验3参数配置局部优化——参数m与NC的调优MCA1CA2CA3MCA4MCA5CA6CA7CA8MCA9MCA10总和总均值CASbest9410066939431411848113698724.8333CASmnc19510066929331421949111698724.5667CASmnc2959965919431421849111695719.9CASmnc3939764929331421848109687718.5333CASmnc4959563909431421848111687713.7667CASmnc5949764919330421848109686716020406080100120140160180编号αβρmNCCASmnc10.70.10.640200CASmnc20.70.10.680200CASmnc30.70.10.620400CASmnc40.70.10.620800CASmnc50.70.10.64040016算法研究：参数配置调优推荐配置参数类型范围ASACSMMAS信息素指数α浮点型0α≤50.71.52.0启发值指数β浮点型0β≤50.10.80.5信息素残留系数ρ浮点型0ρ≤10.60.70.99蚂蚁数量m整形0408020迭代次数NC整形0400200200信息素初值τinit浮点型0≤τinit≤100.40.41.0ACS路径选择概率q0浮点型0q010.01局部更新系数φ浮点型0φ≤10.9信息素上界τmax浮点型τminτmax≤55.0信息素下界τmin浮点型0τminτmax1.0AnswertoQ2:参数配置对算法性能有较为明显的影响，通过参数配置调优可以为覆盖表生成蚁群算法提供一组推荐参数配置。17实验1：在不同m与NC的组合下对比实验结果AnswertoQ1:算法变种的性能有一定的差异，在最优配置下对比三种算法，MMAS的结果更好，且从计算开销来看，其耗时更少，因此MMAS是一个更适合求解覆盖表生成问题的变种。MCA1CA2CA3MCA4MCA5CA6CA7CA8MCA9MCA10总和总均值CASbest9410066939431411848113698724.8333CAS19510066929331421949111698724.5667CAS2959965919431421849111695719.9CAS3939764929331421848109687718.5333CAS4959563909431421848111687713.7667CAS5949764919330421848109686716CACSbest9510165929230421848113696730.92CACS1949963909131411849112688718.6343CACS2949763909131421847113686714.3667CACS39610165939431421848116704731.5628CACS49510366929431421849115705731.6788CACS5949862909430421847113688715.5229CMMASbest939461869030411848112673702.6333CMMAS1939361859230421848112674701.5333CMMAS2939261859030431848111671699.2CMMAS3959361859131421846111673701.6667CMMAS49392