面向离散优化问题的量子协同演化算法  

Quantum-coevolutional algorithm for discrete optimization problem

作　　者：崔晓晖[1] 齐建东[1] 蔡祥[1] Cui Xiaohui;Qi Jiandong;Cai Xiang(School of Information Science ＆ Technology,Beijing Forestry University,Beijing 100083,China)

机构地区：[1]北京林业大学信息学院,北京100083

出　　处：《计算机应用研究》2018年第8期2315-2319,共5页Application Research of Computers

基　　金：中央高校基本科研业务费专项资金资助项目(BLX2014-27);国家自然科学基金青年基金资助项目(31400621)

摘　　要：针对现有优化算法在求解具有时效要求的离散问题时容易出现过早或难以收敛问题,提出了面向离散优化问题的量子协同演化算法,旨在有限的求解时间内获得精度较高的求解方案。在算法的初始化阶段,通过种群初始化策略构建分布均匀的初始种群。在算法的执行阶段,将粒子群和单点优化算法改进为具有不同搜索能力的协同演化策略,利用量子旋转门根据种群个体的进化情况自适应地选择合适的演化策略。在每次迭代后利用精英保持策略避免种群退化。通过标准离散问题和背包问题对算法进行测试。实验结果表明已提出的算法在较短的迭代时间内能够稳定地收敛到精度较高的求解方案,即已提出的算法可用于求解具有时效要求的离散优化问题。Existing optimization algorithms are prone to premature convergence or difficult to converge when solving discrete problem that requiring solving efficiency. This paper proposed a quantum-coevolutional algorithm （QCA） for discrete optimization problem, aiming to obtain the solution with a higher precision within the limited time. In the initial phase, QCA used initialization strategy to generate the initial population with uniform distribution. In the operation phase, QCA improved the exis-ting particle swarm optimization algorithm and the single point algorithm to the coevolutional strategies with various searching ability. Then, QCA involved quantum rotation gate to adaptively select the appropriate evolution strategy according to the individual evolution. Also, QCA adopted elitist strategy to avoid the degradation of population after each iteration. In the test environment of standard discrete problem and knapsack problem, the experimental results show that QCA can steadily converge to the solution of higher precision within the limited iterations, and will be used to solve the discrete problem requiring solving efficiency.

关 键 词：离散优化问题 协同演化算法 量子旋转门 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]