《计算机应用研究》|Application Research of Computers

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

Quantum-coevolutional algorithm for discrete optimization problem

免费全文下载 (已被下载 次)  
获取PDF全文
作者 崔晓晖,齐建东,蔡祥
机构 北京林业大学 信息学院,北京 100083
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)08-2315-05
DOI 10.3969/j.issn.1001-3695.2018.08.019
摘要 针对现有优化算法在求解具有时效要求的离散问题时容易出现过早或难以收敛问题,提出了面向离散优化问题的量子协同演化算法,旨在有限的求解时间内获得精度较高的求解方案。在算法的初始化阶段,通过种群初始化策略构建分布均匀的初始种群。在算法的执行阶段,将粒子群和单点优化算法改进为具有不同搜索能力的协同演化策略,利用量子旋转门根据种群个体的进化情况自适应地选择合适的演化策略。在每次迭代后利用精英保持策略避免种群退化。通过标准离散问题和背包问题对算法进行测试。实验结果表明已提出的算法在较短的迭代时间内能够稳定地收敛到精度较高的求解方案,即已提出的算法可用于求解具有时效要求的离散优化问题。
关键词 离散优化问题;协同演化算法;量子旋转门
基金项目 中央高校基本科研业务费专项资金资助项目(BLX2014-27)
国家自然科学基金青年基金资助项目(31400621)
本文URL http://www.arocmag.com/article/01-2018-08-019.html
英文标题 Quantum-coevolutional algorithm for discrete optimization problem
作者英文名 Cui Xiaohui, Qi Jiandong, Cai Xiang
机构英文名 SchoolofInformationScience&Technology,BeijingForestryUniversity,Beijing100083,China
英文摘要 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.
英文关键词 discrete optimization problem; coevolutional algorithm; quantum rotation gate
参考文献 查看稿件参考文献
  [1] Wong Kachun, Peng Chengbin, Wong M H, et al. Generalizing and learning protein-DNA binding sequence representations by an evolutionary algorithm[J] . Soft Computing, 2011, 15(8):1631-1642.
[2] Wargh S, Kolhe S. Effective semi-supervised approach towards intrusion detection system using machine learning techniques[J] . International Journal of Electronic Security and Digital Forensics, 2015, 7(3):1290-1304. [3] Li D, Cheng B, Deng N, et al. QoS-aware service composition algorithm and architecture by discrete PSO[J] . Journal of Computational Information Systems, 2010, 6(2):501-511.
[4] Qin Jin, Lin Xin, Yin Yixin. An algorithmic framework of discrete particle swarm optimization[J] . Applied Soft Computing, 2012, 12(3):1125-1130.
[5] 崔晓晖, 印桂生, 董红斌. 面向服务匹配问题的协同演化算法[J] . 软件学报, 2015, 26(7):1601-1614.
[6] Dong Hongbin, He Jun, Huang Houkuan, et al. Evolutionary programming using a mixed mutation strategy[J] . Information Science, 2007, 177(1):312-327.
[7] Behanmian J, Fatemi S M T. Development of a PSO-SA hybrid metaheuristic for a new comprehensive regression model to time-series forecasting[J] . Expert Systems with Application, 2010, 37(2):974-984.
[8] Idoumghar L, Melkemi M, Schott R, et al. Hybrid PSO-SA type algorithms for multimodal function optimization and reducing energy consumption in embedded systems[J] . Applied Computational Intelligence and Soft Computing, 2011, 2011(10):1-12.
[9] Kathpal S, Vohra R, Singh J, et al. Hybrid PSO-SA algorithm for achieving partitioning optimization in various network application[C] // Proc of Conference on Modeling Optimization and Computing. Holland:Elsevier, 2012:1728-1734.
[10] Zhang Xin, Dong Hongbin. A new co-evolutionary programming using operators of single-point and particle swarm[C] //Proc of Conference on Modeling Optimization and Computing. Washington DC:IEEE Computer Society, 2010:5528-5534.
[11] Bharti K K, Singh P K. Opposition chaotic fitness mutation based adaptive inertia weight BPSO for feature selection in text clustering[J] . Applied Soft Computing, 2016, 43(6):20-34.
[12] Chen Ning, Gravin N, Lu Pinyan. Competitive analysis via benchmark decomposition[C] // Proc of ACM Conference on Economics and Computation. New York:ACM Press, 2015:363-367.
[13] Han Bing, Leblet J, Simon G. Hard multidimensional multiple choice knapsack problems, an empirical study[J] . Computers & Operations Research, 2010, 37(1):172-181.
[14] 苏爱东, 高维珉, 张永翼. 基于贪心程度和区域界定的预期效率模型求解0-1背包问题[J] . 计算机应用研究, 2015, 32(11):3304-3308.
[15] Khan S, Li K F, Manning E G, et al. Solving the knapsack problem for adaptive multimedia system[J] . Studia Informatica, Special Issue on Cutting, Packing and Knapsacking Problems, 2001, 9:157-178.
收稿日期 2017/4/10
修回日期 2017/6/5
页码 2315-2319
中图分类号 TP301.6
文献标志码 A