Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2021, Vol. 48 Issue (3): 331-337    DOI: 10.3785/j.issn.1008-9497.2021.03.009
数学与计算机科学     
基于Memetic算法的仿真用例集约简技术
杨祎巍1, 匡晓云1, 黄开天1, 洪超1, 郑昌立2, 蒋小文2
1.广东省电力系统网络安全企业重点实验室（南方电网科学研究院有限责任公司），广东 广州 510080
2.浙江大学 信息与电子工程学院，浙江 杭州 310027
Simulation test case suite reduction based on Memetic algorithm
YANG Yiwei1, KUANG Xiaoyun1, HUANG Kaitian1, HONG Chao1, ZHENG Changli2, JIANG Xiaowen2
1.Guangdong Provincial Key Laboratory of Power System Network Security, Electric Power Research Institute, China Southern Power Grid, Guangzhou 510080, China
2.College of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1375 KB)   HTML  
摘要： 在芯片项目中，回归测试是一项重复进行的工作，需耗费大量资源，用例集的反复执行可确保设计的正确性，但会产生较大的测试运行代价。将遗传算法的特点与局部搜索策略的优点有机结合，对约简问题进行数学建模，设计了Memetic算法，对其中的全局策略和各算子、局部策略进行了改进，以功能覆盖率为衡量标准，在完全覆盖的情况下，Memetic算法较标准遗传算法的收敛速度更快，用例集更精简，并较大程度地降低了回归测试的运行代价。
关键词： 用例集约简;  Memetic算法;  测试运行代价;  回归测试    
Abstract: In the entire chip project,regression testing is a work that require lots of resources.The test case suite will be repeatedly executed to ensure the correctness of the design,which will incur large test operation cost. To reduce the use case study, this paper propose Memetic algorithm which organically combines the characteristics of similar genetic algorithms with the advantages of local search strategies.The algorithm is designed by mathematically modeling the reduction problem,and the global strategy,each operator,and the local strategy are improved. Under the condition of complete functional coverage,the convergence speed of Memetic algorithm is faster than that of the standard genetic algorithm,the use case set is more streamlined,and the running cost of regression testing is reduced to a greater extent.
Key words: test case suite reduction    test run cost    regression testing    Memetic algorithm
收稿日期: 2020-04-19 出版日期: 2021-05-20
CLC:  TP 391  
基金资助: 南方电网公司科技项目“密码芯片嵌入式安全平台方案设计与关键技术研究”（ZBKJXM20190065/SEPRI-K195049）；广东省电力系统网络安全企业重点实验室项目(2018B030323022).
通讯作者: ORCID:https://orcid.org/0000-0002-6283-2262，E-mail：xiaowen_jiang@zju.edu.cn.     E-mail: xiaowen_jiang@zju.edu.cn
作者简介: 杨祎巍(1982—)，ORCID:https://orcid.org/0000-0002-6184-7251，男，博士，高级工程师，主要从事电力系统网络安全研；
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
杨祎巍
匡晓云
黄开天
洪超
郑昌立
蒋小文

引用本文:

杨祎巍, 匡晓云, 黄开天, 洪超, 郑昌立, 蒋小文. 基于Memetic算法的仿真用例集约简技术[J]. 浙江大学学报（理学版）, 2021, 48(3): 331-337.

YANG Yiwei, KUANG Xiaoyun, HUANG Kaitian, HONG Chao, ZHENG Changli, JIANG Xiaowen. Simulation test case suite reduction based on Memetic algorithm. Journal of Zhejiang University (Science Edition), 2021, 48(3): 331-337.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2021.03.009    或    https://www.zjujournals.com/sci/CN/Y2021/V48/I3/331

1 李忍，黄树成，祁云嵩.用于测试用例最小化的遗传算法［J］. 信息技术，2015（9）：6-9. DOI：10.13274/j.cnki.hdzj.2015.09.002 LI R，HUANG S C，QI Y S. Genetic algorithm for minimizing test cases［J］. Information Technology，2015（9）：6-9. DOI：10.13274/j.cnki.hdzj.2015.09.002
2 邓秋辉，罗小华.基于混合遗传算法的回归测试用例集最小化研究［J］. 传感器与微系统，2018，37（7）：11-14. DOI：10.13873/J.1000-9787（2018）07-0011-04 DENG Q H，LUO X H. Research on minimization of regression test case set based on hybrid genetic algorithm［J］. Sensors and Microsystems，2018，37（7）：11-14. DOI：10.13873/J.1000-9787（2018）07-0011-04
3 陈阳梅，丁晓明. 测试用例集约简方法综述［J］. 重庆工商大学学报（自然科学版），2012 （3）：70-74. DOI：10.3969/j.issn.1672-058X.2012.03.016 CHEN Y M，DING X M.Review of test suite reduction method［J］.Journal of Chongqing Technology and Business University（Natural Science Edition），2012（3）：70-74. DOI：10.3969/j.issn.1672-058X.2012.03.016
4 李玉燕. 基于不变量的回归测试用例集约简方法研究［D］. 衡阳：南华大学，2017. LI Y Y.Research on Regression Test Case Suite Reduction Based on Invariant［D］.Hengyang：University of South China，2017.
5 田小梅，龚静.实数编码遗传算法的评述［J］.湖南环境生物职业技术学院学报，2005，11（1）：25-31. DOI：10.3969/j.issn.1671-6361.2005.01.007 TIAN X M，GONG J. On overview of real-coded genetic algorithm［J］.Journal of Hunan Environment-Biological Polytechnic，2005，11（1）：25-31. DOI：10.3969/j.issn.1671-6361.2005.01.007
6 李书全，孙雪，孙德辉，等.遗传算法中的交叉算子的述评［J］.计算机工程与应用，2012，48（1）：36-39. DOI：10.3778/j.issn.1002-8331.2012.01.011 LI S Q，SUN X，SUN D H，et al. Summary of crossover operator of genetic algorithm［J］. Computer Engineering and Applications，2012，48（1）：36-39. DOI：10.3778/j.issn.1002-8331.2012.01.011
7 徐芳. 适应性Memetic算法及其在求解离散约束优化问题中的研究［D］. 合肥：中国科学技术大学，2018. XU F.Adaptive Memetic Algorithm and Its Research in Solving Discrete Constrained Optimization Problems［D］.Hefei：University of Science and Technology of China，2018.
8 王树朋，黄凯，严晓浪.基于遗传算法的覆盖率驱动测试产生器［J］. 浙江大学学报（工学版），2016，50（3）：580-588. DOI：10.3785/j.issn.1008-973X.2016.03.024 WANG S P，HUANG K，YAN X L.Coverage directed test generation based on genetic algorithm［J］.Journal of Zhejiang University（Engineering Science Edition），2016，50（3）：580-588. DOI：10.3785/j.issn.1008-973X.2016.03.024
9 ZHANG J，SANDERSON A C.JADE：Adaptive differential evolution with optional external archive［J］.IEEE Transactions on Evolutionary Computation，2009，13（5）：945-958.
10 孟波. 基于改进遗传-禁忌搜索算法的无功优化分析［D］. 郑州：华北水利水电大学，2015. MENG B. Analysis of Reactive Power Optimization Improved Genetic Tabu Search Algorithm［D］.Zhengzhou：North China University of Water Resources and Electric Power，2015.
11 WU X Y，YAN S F，WAN X，et al. Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem［J］. Journal of Combinatorial Optimization，2015，10：1-24.
12 邱萌，符卓. 需求可离散拆分车辆路径问题及其禁忌搜索算法［J］. 哈尔滨工程大学学报，2019，40（3）：525-533. DOI：10.11990/jheu.201801010 QIU M，FU Z. Tabu search algorithm for the discrete split delivery vehicle routing problem［J］. Journal of Harbin Engineering University，2019，40（3）：525-533. DOI：10.11990/jheu.201801010
[1] 林耿, 关健. 自适应memetic算法求解集合覆盖问题[J]. 浙江大学学报（理学版）, 2016, 43(2): 168-174.