双链量子遗传算法的收敛性分析及改进方法研究

量子遗传算法是将量子计算与遗传算法相结合形成的一种混合遗传算法，它弥补了传统遗传算法的某些缺陷，特别适用于复杂工程问题的最优化求解。该算法采用量子比特编码量子染色体的基因位，采用量子旋转门更新种群，使量子染色体的量子比特基因位向当前最优染色体的量子比特基因位靠近，产生最优个体，加快算法的收敛速度。量子遗传算法存在的问题有：（1）传统的量子编码操作使概率幅值更趋近于0或1，容易导致算法陷入局部极值，产生早熟收敛现象。（2）传统的量子旋转门旋转角的大小和方向是根据事先设计好的调整策略确定的，并且直接影响着算法的收敛速度和解的收敛精度。（3）对算法复杂性和收敛性的理论研究很薄弱。 针对量子遗传算法存在的缺陷，本论文的主要研究内容有： (1)现有的双链量子遗传算法最明显的缺点就是容易陷入局部极值、收敛速度慢。收敛精度低等问题，已有许多算法对它进行了改进，但很难有本质上的突破，并且大部分文献通常用实验结果验证算法的有效性，稳定性和收敛性，对算法收敛性的理论证明尚未见诸报道。本论文从理论上研究了双链量子遗传算法的收敛性问题，依据马尔科夫链理论证明该算法的收敛性，通过仿真研究，对算法收敛性和优化效率的影响进行了分析讨论。 (2)双链量子遗传算法具有种群多样性、全局搜索能力、计算并行性等良好的性能，但在求解组合优化问题时并未完全解决早熟收敛现象，同时也没有保证双链量子遗传算法的全局收敛。为此，本论文提出一种改进旋转门的双链量子遗传算法，该算法采用一种改进的量子旋转门对种群中的染色体进行更新，有效提高算法的收敛速度，同时避免算法陷入局部最优解，使算法更适合解决多个局部最优解的问题，实现了算法的全局收敛。