严 英，郭 剑，孙力娟

（1.南京邮电大学计算机学院 南京 210046；2.南京邮电大学计算机技术研究所 南京 210003）

1 引言

遗传算法 （genetic algorithm，GA）是进化计算的一个分支，也是软计算的关键技术之一。它本质上是一种随机搜索算法，在数据挖掘、机器学习、图像处理、网络优化等领域获得了广泛的应用[1～2]。但是应用GA算法来解决实际问题时，人们也遇到了不少困难。最常见的问题就是遗传算法的收敛速度缓慢，且常常收敛于局部最优解。为了解决这个问题，研究者也提出了不少改进[3～4]。Han等人[5]首次将量子计算的相关概念引入到遗传算法的框架中，提出了量子遗传算法（quantum genetic algorithm，QGA）[6，7]。QGA算法对GA算法的编码方式与演化操作都进行了改进，使得算法的收敛速度大大加快，但算法收敛到局部最优解的问题仍然没有很好地解决。

本文对QGA算法进行了研究，针对QGA算法早熟的问题，从算法机制的角度进行了分析。QGA算法每次迭代时，以一个最优染色体来指导群体的进化，破坏了染色体的多样性，使得算法很容易收敛到局部最优解。本文分析了这种方法的不足，改进了QGA的信息交流方式，进而提出了一种基于精英组的量子遗传算法 （elite group based quantum genetic algorithm，EQGA）。最后，本文将 EQGA 用于无线多媒体传感器网络 （wireless multimedia sensor network，WMSN）的覆盖优化问题，通过对比实验验证了EQGA的性能。

2 量子遗传算法

QGA是在GA基础上发展起来的一种随机搜索算法。为了进行区别，本文将传统的QGA算法称为标准量子遗传算 法 （standard quantum genetic algorithm，SQGA）。在SQGA中，染色体的编码和演化操作需要借助于量子计算的相关工具，下面分别进行介绍。……