计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 557-560.DOI: 10.3724/SP.J.1087.2012.00557

• 计算机软件技术 • 上一篇    下一篇

改进的量子遗传算法及其在测试数据生成中的应用

周绮,姜淑娟,赵雪峰   

  1. 中国矿业大学 计算机科学与技术学院,江苏 徐州 221116
  • 收稿日期:2011-07-27 修回日期:2011-09-23 发布日期:2012-02-23 出版日期:2012-02-01
  • 通讯作者: 周绮
  • 作者简介:周绮(1987-),女,湖南望城人,硕士研究生,主要研究方向:软件测试;
    姜淑娟(1966-),女,山东莱阳人,教授,博士生导师,博士,主要研究方向:软件分析与测试、程序设计语言、编译技术;
    赵雪峰(1986-),男,江西九江人,硕士研究生,主要研究方向:软件工程、软件测试。
  • 基金资助:
    国家自然科学基金资助项目(10926072);江苏省自然科学基金资助项目(BK2010599);江苏省“青蓝工程”资助项目

Improved quantum genetic algorithm and its application in test data generation

ZHOU Qi,JIANG Shu-juan,ZHAO Xue-feng   

  1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China
  • Received:2011-07-27 Revised:2011-09-23 Online:2012-02-23 Published:2012-02-01
  • Contact: ZHOU Qi

摘要: 针对测试数据自动生成中收敛速度不够快的缺点,提出一种改进的量子遗传算法(IQGA),其对量子遗传算法的主要改进是:1)在个体更新时,对个体的某一位取反,将取反后的个体用于指导下一代个体的进化;2)对测量后的二进制个体进行变异,而不是传统的互换量子比特的概率幅。将IQGA用于测试数据生成,通过对三个基础程序进行实验,结果表明IQGA在覆盖率和迭代次数两个方面都优于传统量子遗传算法。IQGA不仅能保证种群朝着正确的方向进化,同时有效地避免了早熟现象,能以更快的速度搜索到目标解。

关键词: 量子遗传算法, 测试数据生成, 取反指导更新, 二进制变异, 快速收敛

Abstract: This paper proposed an Improved Quantum Genetic Algorithm (IQGA) for the problem of slow convergence in test data generation. There are two main improvements. First, every bit of every individual was reversed to conduct the evolution; second, the binary individuals were mutated after measurement, instead of the traditional exchange of the probability amplitude of quantum bits. IQGA was applied into test data generation. The experiments on three basic programs prove that IQGA is better than QGA in terms of coverage rate and the number of iterations. IQGA can not only ensure the right direction of the evolution of populations, but also avoid premature phenomenon, and it can get the solution at a faster convergence speed.

Key words: Quantum Genetic Algorithm (QGA), test data generation, updating conducted by reversing, binary mutation, rapid convergence

中图分类号: