改进量子遗传算法在多峰值函数寻优中的应用

米兰　鱼佳欣　李东涛　谢瑞莎

摘 要：针对标准量子遗传算法（QGA）在寻找多峰值最优时存在局部寻优能力较差和易早熟的缺陷，提出一种改进量子遗传算法（QQGA），运用基于概率划分的小生境协同进化策略初始化量子种群，并采用动态量子旋转角调整策略来加快收敛速度；加入量子移民和保优选择策略，提高规划效率，避免陷入局部最优。利用复杂二元函数测试改进量子遗传算法，结果比标准量子遗传算法效率高。

关键词：量子遗传算法；多峰值函数；优化

中图分类号：TP301 文献标识码：A

Abstract：According to has the poor local searching ability and precocity in search of multi peak optimization，so this paper proposed an improved quantum genetic algorithm （QQGA），which uses the probability of evolutionary strategy with niche to initiate the quantum population， and the dynamic quantum rotating angle adjustment strategy to speed up the convergence speed；and adds quantum immigration and elitist selection strategy to improve the planning efficiency and avoid falling into local optimal. Then the paper uses complex function of two variables to test the improved quantum genetic algorithm， and the result proves that the improved quantum genetic algorithm has higher efficiency.

Key words：quantum genetic algorithm； multipeak functions； optimization

1 引 言

量子遗传算法（QGA）是量子计算与遗传算法相结合产生的新的智能算法。利用量子态叠加性和量子旋转门等操作实现染色体的更新，从而实现有效计算[1]。与遗传算法相比，量子遗传算法具有种群多样性好、全局搜索能力强和收敛速度快等特点[2]。然而，文献[3]～文献[4]中也指出，量子遗传算法适于求解组合优化问题，甚至只适于求解背包问题，而不适于求解连续函数的优化问题，特别是多峰函数的优化问题。

因此，本文提出改进量子遗传算法求解多峰值函数最优值，并进行了仿真实验，结果证明了该方法是有效可行的。

2 量子遗传算法及其改进

在量子遗传算法中，最重要的是量子编码和量子门的引入。量子编码是将染色体用量子的态矢量表示，使一条染色体表达多个态的叠加，从而增加了种群多样性，使算法能够在较小的种群规模下求得最优解； 而量子门的引入使算法具备了优化能力，可以保证算法收敛[5]。

2.1 量子编码

如图2，各种群之间通过移民算子进行联系，实现多种群的协同进化，本文的移民算子是在相邻种群间移民，即用当前种群中的最优个体代替相邻种群的最劣个体。加入人工选择算子保存各种群每个进化代中的最优个体。每迭代一次进行一次移民和人工选择运算，选出各种群的最优值存到精华种群。精华种群和其他种群有很大不同，精华种群不进行量子变更，保证进化过程中各种群产生的最优个体不被破坏和丢失。同时，精华种群也是判断算法终止的依据，这里采用最大遗传代数作为终止判据。最后从精华种群中获得最优个体。

4 结束语

本文针对标准量子遗传算法收敛性差，易陷于局部最优的缺点，进行改进运用基于概率划分的小生境协同进化策略初始化量子种群，并采用动态的量子旋转角调整策略来加快收敛速度；加入量子移民和保优选择策略，提高规划效率，避免陷入局部最优。并利用复杂二元函数测试改进量子遗传算法，显示了优良的特性。

参考文献

[1] 梁昌勇，柏 桦，蔡美菊，等.量子遗传算法研究进展[J].计算机应用研究，201207，29（7）：2401-2405.

[2] 周传华，钱锋.改进量子遗传算法及其应用[J].计算机应用，200802，28（2）：286-288.

[3] HAN KH， KIM JH. Parallel quantuminspired genetic algorithm for combinatorial optimization problems[C].Proc of IEEE Conference on Evolutionary Computation. Piscataway： IEEE Press， 2001：1422-1429.

[4] 张葛样，李娜，金炜东.一种新量子遗传算法及其应用[J].电子学报，2004，32（3）：476-479.

[5] 张宗飞.一种改进型量子遗传算法[J].计算机工，201003，36（6）：181-183.

[6] 张小锋， 睢贵芳， 郑冉. 一种改进的量子旋转门量子遗传算法[J] 计算机工程，201304，39（4）：234-238.