量子群智能优化算法综述

doi:10.3778/j.issn.1002-8331.2110-0141

摘要/Abstract

摘要： 随着科学技术的不断发展，最优化理论及其衍生出的算法已经广泛应用于人们的日常工作与生活当中，现实世界中的很多问题都可以被描述为组合优化问题。群智能优化算法这些年来被证明在解决组合优化问题方面效果显著，将当下处于研究热点的量子计算概念引入群智能优化算法形成的量子群智能优化算法，为更好地解决组合优化问题提出了一个新的研究方向。在过去的二十多年里，许多量子群智能优化算法被不断开发出来，同时在此基础上进行了大量改进与应用。综述了量子蚁群算法、量子粒子群算法、量子人工鱼群算法、量子人工蜂群算法、量子布谷鸟搜索算法、量子混合蛙跳算法、量子萤火虫算法、量子蝙蝠算法等量子群智能优化算法，并对量子群智能优化算法面临的问题以及未来研究方向进行了深入探讨。

关键词: 量子计算, 群智能优化算法, 量子蚁群算法, 量子群智能优化算法, 组合优化

Abstract: With the continuous development of science and technology, optimization theory and its derived algorithms have been widely used in people’s daily work and life, especially in the real world, many problems can be described as combinatorial optimization problems. In recent years, swarm intelligence optimization algorithm has been proved to be effective in solving combinatorial optimization problems. Introducing the concept of quantum computing into swarm intelligence optimization algorithm, a new research direction is opened for better solving combinatorial optimization problems. In the past 20 years, many quantum swarm optimization algorithms have been developed, and more people have improved and applied them. This paper summarizes quantum ant colony algorithm, quantum particle swarm algorithm, quantum artificial fish swarm algorithm, quantum bee colony optimization algorithm, quantum cuckoo search algorithm, quantum hybrid frog leaping algorithm, quantum firefly algorithm, quantum bat algorithm and other quantum swarm Intelligent optimization algorithms. The future problems and research directions of quantum swarm optimization algorithm are discussed.

Key words: quantum computing, swarm intelligence optimization algorithm, quantum ant colony algorithm, quantum swarm intelligence optimization algorithm, combinatorial optimization

安家乐, 刘晓楠, 何明, 宋慧超. 量子群智能优化算法综述[J]. 计算机工程与应用, 2022, 58(7): 31-42.

AN Jiale, LIU Xiaonan, HE Ming, SONG Huichao. Survey of Quantum Swarm Intelligence Optimization Algorithm[J]. Computer Engineering and Applications, 2022, 58(7): 31-42.

参考文献

[1] DUAN H B，LUO Q N.New progresses in swarm intelligence-based computation[J].International Journal of Bio-Inspired Computation，2015，7（1）：26-35.
[2] 何小锋.量子群智能优化算法及其应用研究[D].上海：上海理工大学，2014.
HE X F.Quantum swarm intelligent optimization algorithm and its application[D].Shanghai：Shanghai University of Technology，2014.
[3] 张大可.现代设计方法[M].北京：机械工业出版社，2014：64-66.
ZHANG D K.Modern design method[M].Beijing：China Machine Press，2014：64-66
[4] HOLLAND H J.Genetic algorithms and the optimal allocation of trials[J].Critical Asian Studies，1973，2（2）：88-105.
[5] DORIGO M.Optimization learning and natural algorithms[D].Italy：Politecnico di Milano，1992.
[6] KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proceedings of International Conference on Neural Networks，Perth，WA，Australia，1995：1942-1948.
[7] KARABOGA D，BASTURK B.On the performance of artificial bee colony（ABC） algorithm[J].Applied Soft Computing，2008，8（1）：687-697.
[8] YANG X S，SADAT H S S，GANDOMI A H.Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect[J].Applied Soft Computing，2012，12（3）：1180-1186.
[9] 周雅兰.细菌觅食优化算法的研究与应用[J].计算机工程与应用，2010，46（20）：16-21.
ZHOU Y L.Research and application on bacteria foraging optimization algorithm[J].Computer Engineering and Applications，2010，46（20）：16-21.
[10] DUAN H B，QIAO P X.Pigeon-inspired optimization：A new swarm intelligence optimizer for air robot path planning[J].International Journal of Intelligent Computing and Cybernetics，2014，7（1）：24-37.
[11] FEYNMAN R.Simulating physics with computers[J].International Journal Theoretical Physics，1982，21（6）：467-488.
[12] SHOR P W.Algorithm for quantum computation：discrete logarithms and factoring[C]//Proceedings of the 35th Annual Symposium on Foundations of Computer Science，Santa Fe，NM，USA，1994：124-134.
[13] GROVER L K.A fast quantum mechanics algorithm for database search[C]//Proceedings of the 28th ACM Symposium on Theory of Computing，1996：212-219.
[14] AJIT N，MARK M.Optimization with quantum genetic algorithm[C]//Proceedings of IEEE International Conference on Evolutionary Computation，1996：61-66.
[15] HAN K H，KIM J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 IEEE Congress on Evolutionary Computation，2000：1354-1360.
[16] SUN J，FENG B，XU W B.Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the 2004 Congress on Evolutionary Computation，2004：325-331.
[17] 李盼池，李士勇.求解连续空间优化问题的量子蚁群算法[J].控制理论与应用，2008（2）：237-241.
LI P C，LI S Y.Quantum ant colony algorithm for continuous space optimization[J].Control Theory and Application，2008（2）：237-241.
[18] 唐涛.一种新型二进制编码的量子鱼群算法[J].电脑知识与技术，2008（S1）：52-53.
TANG T.A new binary coded quantum fish swarm algorithm[J].Computer Knowledge and Technology，2008（S1）：52-53.
[19] GAO H Y，LIU Y Q，DIAO M.Robust multi-user detection based on quantum bee colony optimisation[J].International Journal of Innovative Computing and Applications，2011，3（3）：160-168.
[20] LAYEB A.A novel quantum inspired cuckoo search for knapsack problems[J].International Journal of Bio-Inspired Computation，2011，3（5）：297-305.
[21] 孙冲.混合蛙跳算法改进及控制参数优化仿真研究[D].哈尔滨：哈尔滨工业大学，2011.
SUN C.Simulation Research on hybrid frog leaping algorithm improvement and control parameter optimization[D].Harbin：Harbin Institute of Technology，2011.
[22] 张剑飞，杜晓昕，王波.基于量子萤火虫和增益Beta的医学DR图像自适应增强[J].微电子学与计算机，2014，31（5）：135-139.
ZHANG J F，DU X X，WANG B.Adaptive enhancement of medical DR image based on quantum firefly and gain beta[J].Microelectronics and Computer，2014，31（5）：135-139.
[23] 李枝勇.蝙蝠算法及其在函数优化中的应用研究[D].上海：上海理工大学，2013.
LI Z Y.Bat algorithm and its application in function optimization[D].Shanghai：Shanghai University of Technology，2013.
[24] 赵卢月.基于量子蚁群算法的最短路径问题研究[D].青岛：青岛理工大学，2019.
ZHAO L Y.Research on shortest path problem based on quantum ant colony algorithm[D].Qingdao：Qingdao University of Technology，2019.
[25] 万正宜，彭玉旭.求解旅行商问题的改进型量子蚁群算法[J].计算机工程与应用，2016，52（22）：59-63.
WAN Z Y，PENG Y X.Improved quantum ant colony algorithm for traveling salesman problem[J].Computer Engineering and Applications，2016，52（22）：59-63.
[26] 何小锋，马良.求解图着色问题的量子蚁群算法[J].运筹学学报，2013，17（2）：19-26.
HE X F，MA L.Quantum ant colony algorithm for graph coloring problem[J].Journal of Operational Research，2013，17（2）：19-26.
[27] 何小锋，马良.求解0-1背包问题的量子蚁群算法[J].计算机工程与应用，2011，47（16）：29-31.
HE X F，MA L.Quantum-inspired ant algorithm for solving 0-1 knapsack problem[J].Computer Engineering and Applications，2011，47（16）：29-31.
[28] CHEN X F，XIA X Y，YU R Y.Quantum ant colony algorithm based on Bloch coordinates[J].Journal of Computers，2013，8（6）：1536-1543.
[29] 王灵，王秀亭，俞金寿.基于自适应量子蚁群算法的石脑油裂解炉故障诊断[J].化工学报，2009，60（2）：401-408.
WANG L，WANG X T，YU J S.Fault diagnosis of naphtha cracking furnace based on adaptive quantum ant colony algorithm[J].Journal of Chemical Industry and Engineering，2009，60（2）：401-408.
[30] 李絮，刘争艳，谭拂晓.求解TSP的新量子蚁群算法[J].计算机工程与应用，2011，47（32）：42-44.
LI X，LIU Z Y，TAN F X.Novel quantum ant colony algorithm for TSP[J].Computer Engineering and Applications，2011，47（32）：42-44.
[31] 贾瑞玉，李亚龙，管玉勇.求解旅行商问题的混合量子蚁群算法[J].计算机工程与应用，2013，49（22）：36-39.
JIA R Y，LI Y L，GUAN Y Y.Hybrid quantum ant colony algorithm for traveling salesman problem[J].Computer Engineering and Applications，2013，49（22）：36-39.
[32] 张程程.改进量子蚁群算法的动态最优路径诱导研究[D].哈尔滨：哈尔滨工程大学，2015.
ZHANG C C.Research on dynamic optimal path guidance based on improved quantum ant colony algorithm[D].Harbin：Harbin Engineering University，2015.
[33] XIA G Q，HAN Z W，ZHAO B，et al.Global path planning for unmanned surface vehicle based on improved quantum ant colony algorithm[J/OL].Mathematical Problems in Engineering：Article ID 2902170.（2019-04-24）[2021-07-01].https：//doi.org/10.1155/2019/2902170.
[34] WANG L.A novel quantum ant colony optimization algorithm and its application to fault diagnosis[J].Transactions of the Institute of Measurement & Control，2008，30（3/4）：313-329.
[35] LI F，LIU M，XU G W.A quantum ant colony multi-objective routing algorithm in WSN and its application in a manufacturing environment[J].Sensors，2019，19（15）：3334.
[36] LI J J，XU B W，YANG Y S，et al.Quantum ant colony optimization algorithm for AGVs path planning based on Bloch coordinates of pheromones[J].Natural Computing，2020，19：673-682.
[37] 李晓峰，焦洪双，李东.基于量子蚁群算法的医疗图像阈值分割算法[J].沈阳大学学报（自然科学版），2020，32（6）：490-495.
LI X F，JIAO H S，LI D.Medical image threshold segmentation algorithm based on quantum ant colony algorithm[J].Journal of Shenyang University（Natural Science Edition），2020，32（6）：490-495.
[38] 杨树欣，李盼池.基于量子蚁群优化的油田水淹层识别方法[J].计算机与数字工程，2015，43（2）：173-177.
YANG S X，LI P C.Identification method of water flooded zone in oil field based on quantum ant colony optimization[J].Computer and Digital Engineering，2015，43（2）：173-177.
[39] 刘瑜，马良.量子蚁群算法在压力容器优化设计中的应用[J].机械强度，2011，33（5）：786-790.
LIU Y，MA L.Application of quantum ant colony algorithm in optimal design of pressure vessels[J].Mechanical Strength，2011，33（5）：786-790.
[40] WANG X Y，ZHANG H M，GAO H H.Quantum particle swarm optimization based network Intrusion feature selection and detection[J].IFAC Proceedings Volumes，2008，41（2）：12312-12317.
[41] KHAYYATZADEH M，TOUSI B.Damping of power system oscillations via quantum particle swarm optimization based distributed static series compensator[J].Electric Power Components and Systems，2013，41（7）：729-746.
[42] CH S，ANAND N，PANIGRAHI B K，et al.Streamflow forecasting by SVM with quantum behaved particle swarm optimization[J].Neurocomputing，2013，101：18-23.
[43] 高浩，须文波，孙俊.量子粒子群算法在图像分割中的应用[J].计算机工程与应用，2007，43（33）：24-25.
GAO H，XU W B，SUN J.Image segmentation using quantum-behaved particle swarm optimization algorithm[J].Computer Engineering and Applications，2007，43（33）：24-25.
[44] RADHA R，GOPALAKRISHNAN R.A medical analytical system using intelligent fuzzy level set brain image segmentation based on improved quantum particle swarm optimization[J].Microprocessors and Microsystems，2020，79：103283.
[45] ZHAO X G，LIANG J，MENG J，et al.An improved quantum particle swarm optimization algorithm for environmental economic dispatch[J].Expert Systems with Applications，2020，152：113370.
[46] 金鹏.改进量子行为粒子群算法的研究及其在优化问题中的应用[D].徐州：中国矿业大学，2018.
JIN P.Research on improved quantum-behaved particle swarm optimization and its application in optimization problems[D].Xuzhou：China University of Mining and Technology，2018.
[47] 赵国新，陈志炼，魏战红.混合自适应量子粒子群优化算法[J].微电子学与计算机，2019，36（7）：76-80.
ZHAO G X，CHEN Z L，WEI Z H.Hybrid adaptive quantum particle swarm optimization algorithm[J].Microelectronics & Computer，2019，36（7）：76-80.
[48] 刘旭光，宋万干.基于量子人工鱼群算法优化的K-mediods聚类挖掘研究[J].贵阳学院学报（自然科学版），2021，16（1）：26-31.
LIU X G，SONG W G.Research on K-mediods clustering mining based on quantum artificial fish swarm algorithm[J].Journal of Guiyang University（Natural Science Edition），2021，16（1）：26-31.
[49] 王林川，李传虎，罗晓辉，等.基于量子人工鱼群混合算法的输电网规划[J].华中电力，2009，22（6）：1-4.
WANG L C，LI C H，LUO X H，et al.Transmission network planning based on quantum artificial fish swarm hybrid algorithm[J].Central China Electric Power，2009，22（6）：1-4.
[50] 张锴.基于自适应量子人工鱼群算法的动态路径诱导研究[D].沈阳：东北大学，2014.
ZHANG K.Research on dynamic path guidance based on adaptive quantum artificial fish swarm algorithm[D].Shenyang：Northeastern University，2014.
[51] 行鸿彦，韩杰，刘刚.量子人工鱼群优化的随机共振微弱信号检测[J].计算机仿真，2019，36（10）：368-372.
XING H Y，HAN J，LIU G.Stochastic resonance weak signal detection based on quantum artificial fish swarm optimization[J].Computer Simulation，2019，36（10）：368-372.
[52] 李根.基于量子人工鱼群和模糊核聚类算法的网络入侵检测模型研究[J].软件工程，2019，22（6）：33-37.
LI G.Research on network intrusion detection model based on quantum artificial fish swarm and fuzzy kernel clustering algorithm[J].Software Engineering，2019，22（6）：33-37.
[53] GAO H Y，LIU Y Q，DIAO M.Robust multi-user detection based on quantum bee colony optimisation[J].International Journal of Innovative Computing and Applications，2011，3（3）：160-168.
[54] 邓斯凯，毛弋.基于量子人工蜂群算法的配电网多目标优化重构[J].湖南师范大学自然科学学报，2021（2）：80-86.
DENG S K，MAO Y.Multi-objective optimal reconfiguration of distribution network based on quantum artificial bee colony algorithm[J].Journal of Natural Science of Hunan Normal University，2021（2）：80-86.
[55] GAO H Y，LI C W.Membrane-inspired quantum bee colony optimization and its applications for decision engine[J].Journal of Central South University，2014，21（5）：1887-1897.
[56] HUO F C，SUN X T，REN W J.Multilevel image threshold segmentation using an improved Bloch quantum artificial bee colony algorithm[J].Multimedia Tools and Applications，2020，79（3）：2447-2471.
[57] 侯国莲，弓林娟.基于量子蜂群聚类的T-S模糊建模在智能发电运行控制中应用[J].热力发电，2019，48（9）：108-114.
HOU G L，GONG L J.Application of T-S fuzzy modeling based on quantum bee colony clustering in intelligent power generation operation control[J].Thermal Power Generation，2019，48（9）：108-114.
[58] 高相铭，杨世凤，潘三博.基于混沌量子蜂群优化SVR的多峰MPPT算法研究[J].电气传动，2015，45（12）：55-60.
GAO X M，YANG S F，PAN S B.Research on multi-peak MPPT algorithm based on SVR optimized by chaotic quantum-inspired artificial bee colony[J].Electric Drive，2015，45（12）：55-60.
[59] KARTOUS W，LAYEB A，CHIKHI S.A new quantum cuckoo search algorithm for multiple sequence alignment[J].Journal of Intelligent Systems，2014，23（3）：261-275.
[60] 朱海红.量子群智能优化算法设计及其应研究[D].芜湖：安徽师范大学，2018.
ZHU H H.Quantum swarm optimization algorithm design and its application[D].Wuhu：Anhui Normal University，2018.
[61] 杜传报，全厚德，唐友喜，等.基于膜量子布谷鸟搜索的双通道网络频谱资源分配[J].电波科学学报，2016，31（1）：129-137.
DU C B，QUAN H D，TANG Y X，et al.Spectrum resource allocation of dual channel network based on membrane quantum cuckoo search[J].Journal of Radio Science，2016，31（1）：129-137.
[62] 张东寅，王澎涛，袁艳斌，等.基于改进布谷鸟算法的电力系统最优潮流计算[J].水电能源科学，2017，35（1）：200-204.
ZHANG D Y，WANG P T，YUAN Y B，et al.Power system optimal power flow calculation based on improved cuckoo algorithm[J].Hydropower Energy Science，2017，35（1）：200-204.
[63] 刘志刚，杜娟，许少华，等.基于量化正交交叉的量子衍生布谷鸟搜索算法[J].信息与控制，2017，46（4）：408-414.
LIU Z G，DU J，XU S H，et al.Quantum derived cuckoo search algorithm based on quantum orthogonal crossover[J].Information and Control，2017，46（4）：408-414.
[64] BOUSHAKI S I，KAMEL N，BENDJEHABA O.A new quantum chaotic cuckoo search algorithm for data clustering[J].Expert Systems with Applications，2018，96：358-372.
[65] 张强，许少华，刘丽杰.量子混合蛙跳算法在过程神经网络优化中的应用[J].信号处理，2013，29（8）：1003-1011.
ZHANG Q，XU S H，LIU L J.Application of quantum hybrid frog leaping algorithm in process neural network optimization[J].Signal Processing，2013，29（8）：1003-1011.
[66] 陈光宇，何健，施蔚锦，等.基于量子混合蛙跳算法的含分布式电源配电网无功优化[J].电网与清洁能源，2015，31（5）：36-41.
CHEN G Y，HE J，SHI W J，et al.Reactive power optimization of distribution network with distributed generation based on quantum hybrid frog leaping algorithm[J].Power Grid and Clean Energy，2015，31（5）：36-41.
[67] WANG X M，LIU S，LI Q M，et al.Underwater sonar image detection：A novel quantum-inspired shuffled frog leaping algorithm[J].Chinese Journal of Electronics，2018，27（3）：588-594.
[68] 赵俊丽.量子萤火虫算法改进及其在图像阈值分割中的应用[D].银川：宁夏大学，2019.
ZHAO J L.Improvement of quantum firefly algorithm and its application in image threshold segmentation[D].Yinchuan：Ningxia University，2019.
[69] SHAREEF H，LBRAHIM A A，SALMAN N，et al.Power quality and reliability enhancement in distribution systems via optimum network reconfiguration by using quantum firefly algorithm[J].International Journal of Electrical Power and Energy Systems，2014，58：160-169.
[70] 齐学梅，王宏涛，杨洁，等.量子萤火虫算法及在无等待流水调度上的应用[J].信息与控制，2016，45（2）：211-217.
QI X M，WANG H T，YANG J，et al.Quantum firefly algorithm and its application in no wait flow scheduling[J].Information and Control，2016，45（2）：211-217.
[71] TAO S B，LIU D Z，TANG A P，et al.Bridge critical state search by using quantum genetic firefly algorithm[J].Shock and Vibration，2019（2）：1-10.
[72] HUO L，WANG Z L，LI R X.Quantum-behaved bat algorithm for service composition[C]//Proceedings of the 2nd International Conference on Comunication Technology.Melboume：Information Engineering Research Institute Press，2015：8.
[73] HUANG X W，LI C P，PU Y M，et al.Gaussian quantum bat algorithm with direction of mean best position for numerical function optimization[J].Computational Intelligence and Neuroscience，2019（9）：1-18.
[74] LI M W，WANG Y T，GENG J，et al.Chaos cloud quantum bat hybrid optimization algorithm[J].Nonlinear Dynamics，2021，103：1167-1193.
[75] 周志垚，孙自强.改进量子蝙蝠算法的研究及应用[J].计算机工程与设计，2019，40（1）：84-91.
ZHOU Z Y，SUN Z Q.Research and application of improved quantum bat algorithm[J].Computer Engineering and Design，2019，40（1）：84-91.