基于多算子协同进化的自适应并行量子遗传算法

doi:10.3969/j.issn.0372-2112.2019.02.002

电子学报 ›› 2019, Vol. 47 ›› Issue (2): 266-273.DOI: 10.3969/j.issn.0372-2112.2019.02.002

基于多算子协同进化的自适应并行量子遗传算法

曲志坚, 陈宇航, 李盘靖, 刘晓红, 李彩虹

山东理工大学计算机科学与技术学院, 山东淄博 255049

收稿日期:2018-04-23 修回日期:2018-07-01 出版日期:2019-02-25
- 通讯作者:
- 李彩虹
- 作者简介:
- 曲志坚 男,1980年生于山东青岛.现为山东理工大学计算机科学与技术学院副教授、硕士生导师.主要研究方向为进化算法和网络资源优化.E-mail:zhijianqu@sdut.edu.cn;陈宇航 男,1997年生于浙江丽水.现为山东理工大学计算机科学与技术专业本科生.ACM-ICPC亚洲区域赛银奖获得者.主要研究方向为算法分析与设计.E-mail:sdut_snow@163.com
- 基金资助:
- 国家自然科学基金 (No.61473179）; 山东省自然科学基金 (No.ZR2016FM18）; 山东省高等学校科技计划项目 (No.J16LN20）

Cooperative Evolution of Multiple Operators Based Adaptive Parallel Quantum Genetic Algorithm

QU Zhi-jian, CHEN Yu-hang, LI Pan-jing, LIU Xiao-hong, LI Cai-hong

School of Computer Science and Technology, Shandong University of Technology, Zibo, Shandong 255049, China

Received:2018-04-23 Revised:2018-07-01 Online:2019-02-25 Published:2019-02-25

摘要/Abstract

摘要： 量子遗传算法具有种群规模小，全局搜索能力强的特点被广泛应用于各类优化问题的求解.为了进一步提高量子遗传算法的收敛速度和搜索稳定性，克服算法的早熟问题，本文改进了基于自适应机制的量子遗传算法.在自适应量子遗传算法的基础上根据种群的适应度定义了个体相似度评价算子、个体适应度评价算子和种群变异调整算子及相应算子的计算方法，利用多算子协同评价当前种群状态并根据进化代数的变化，自适应的改变个体的变异概率，提高了算法全局寻优能力和收敛速度，降低了算法陷入局部寻优的概率.此外，为了提高算法的时间效率，将算法采用并行多宇宙的方式实现.实验结果表明，本文提出的算法在全局搜索性能、收敛速度和时间效率方面有较好的综合表现.

关键词: 遗传算法, 并行计算, 自适应机制, 量子变异

Abstract: The characteristics of strong global search ability with small population size lead to the quantum genetic algorithm is well popular in solving optimization problems.In order to further improve the convergence speed,search stability and overcome the pre-matureness of the quantum genetic algorithm,an improved adaptive mechanism based quantum genetic algorithm was presented in the paper.For the presented algorithm,the individual similarity evaluation operator,individual fitness evaluation operator and population mutation adjustment operator were defined and added into the self-adaptive based quantum genetic algorithm.The way of calculating the three operators were also proposed.Therefore,the current population state can be evaluated by the operators cooperatively,and the individual's mutation probability can be determined according to the current population state.The proposed algorithm can improve the global optimization ability and convergence speed,and reduces the probability of falling into local optimization.In addition,a parallel multi-universe mechanism is employed to improve the time efficiency of the algorithm.Experimental results show that the proposed algorithm has a good performance in the global search performance and time efficiency.

Key words: genetic algorithm, parallel computing, adaptive mechanism, quantum mutation

中图分类号:

TP301.6

曲志坚, 陈宇航, 李盘靖, 刘晓红, 李彩虹. 基于多算子协同进化的自适应并行量子遗传算法[J]. 电子学报, 2019, 47(2): 266-273.

QU Zhi-jian, CHEN Yu-hang, LI Pan-jing, LIU Xiao-hong, LI Cai-hong. Cooperative Evolution of Multiple Operators Based Adaptive Parallel Quantum Genetic Algorithm[J]. Acta Electronica Sinica, 2019, 47(2): 266-273.

参考文献

[1] Qu B Y,Zhu Y S,Jiao Y C,et al.A survey on multi-objective evolutionary algorithms for the solution of the environmental/economic dispatch problems[J].Swarm and Evolutionary Computation,2018,38:1-11.
[2] Wang Y,Feng X Y,Huang Y X,et al.A novel quantum swarm evolutionary algorithm and its applications[J].Neurocomputing,2007,70(4-6):633-640.
[3] Han K H,Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(6):580-593.
[4] 王宇平,李英华.求解TSP的量子遗传算法[J].计算机学报,2007,30(5):748-755. Wang Y P,Li Y H.A novel quantum genetic algorithm for TSP[J].Chinese Journal of Computers,2007(5):748-755.(in Chinese)
[5] Kuo S Y,Chou Y H,Chen C Y.Quantum-inspired algorithm for cyber-physical visual surveillance deployment systems[J].Computer Networks,2017,117:5-18.
[6] Wang X M,Liu S,Li Q,Liu Z P.Underwater sonar image detection:a novel quantum-inspired shuffled frog leaping algorithm[J].Chinese Journal of Electronics,2018,27(3):588-594.
[7] Wu X,Wu S.An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem[J].Journal of Intelligent Manufacturing,2017,28(6):1441-1457.
[8] Qu Z,Liu X,Zhang X,et al.Hamming-distance-based adaptive quantum-inspired evolutionary algorithm for network coding resources optimization[J].the Journal of China Universities of Posts and Telecommunications,2015,22(3):92-99.
[9] Qu Zhijian,Fu Jia,Liu Xiaohong,Li Caihong.Network coding resources optimization with transmission delay constraint in multicast networks[J].High Technology Letters,2017,23(1):30-37.
[10] 邢焕来,潘炜,邹喜华.一种解决组合优化问题的改进型量子遗传算法[J].电子学报,2007,35(10):1999-2002. Xing H L,Pan W,Zou X H.A novel improved quantum genetic algorithm for combinatorial optimization problems[J].Acta Electronic Sinica,2007,35(10):1999-2002.(in Chinese)
[11] Gupta S,Mittal S,Gupta T,et al.Parallel quantum-inspired evolutionary algorithms for community detection in social networks[J].Applied Soft Computing,2017,61:331-353.
[12] 刘晓红,曲志坚,曹雁锋,等.基于自适应机制的多宇宙并行量子衍生进化算法[J].计算机应用,2015,35(02):369-373. Liu X H,Qu Z J,Cao Y F,et al.Multi-universe parallel quantum-inspired evolutionary algorithm based on adaptive mechanism[J].Journal of Computer Applications,2015,35(02):369-373.(in Chinese)
[13] 曲志坚,张先伟,曹雁锋,等.基于自适应机制的遗传算法研究[J].计算机应用研究,2015,32(11):3222-3225+3229. Qu Z J,Zhang X W,Cao Y F,et al.Research on genetic algorithm based on adaptive mechanism[J].Application Research of Computers,2015,32(11):3222-3225+3229.(in Chinese)
[14] 杨俊安,庄镇泉,史亮.多宇宙并行量子遗传算法[J].电子学报,2004,32(6):923-928. Yang J A,Zhuang Z Q,Shi L.Multi-universe parallel quantum genetic algorithm[J].Acta Electronic Sinica,2004,32(6):923-928.(in Chinese)

[1]	袁海英, 曾智勇, 成君鹏. 面向灵活并行度的稀疏卷积神经网络加速器[J]. 电子学报, 2022, 50(8): 1811-1818.
[2]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[3]	钱忠胜, 俞情媛, 宋涛, 朱懿敏, 祝洁, 赵畅. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021, 49(7): 1386-1391.
[4]	刘焕淋, 黄美娜, 陈勇, 杨健, 黄冰川, 张彤. 基于NOMA技术的PLC-VLC用户配对和子载波分配方法[J]. 电子学报, 2021, 49(10): 1952-1959.
[5]	王卫杰, 胡少亮, 郑宇腾, 赵振国, 周海京. 并行预处理有限元方法及其在系统级封装结构电磁模拟中的应用[J]. 电子学报, 2021, 49(1): 58-63.
[6]	金泽芬芬, 侯志强, 余旺盛, 王鑫, 寇人可. 基于量子遗传算法的视觉目标跟踪[J]. 电子学报, 2020, 48(8): 1493-1501.
[7]	范书平, 张岩, 马宝英, 万里, 姚念民, 宋妍. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.
[8]	薛河, 苟思育, 倪陈强. 紧凑拉伸试样参比电位差接线点布局的优化方法[J]. 电子学报, 2020, 48(7): 1396-1402.
[9]	郭广颂, 陈良骥, 文振华, 张勇. 求解高维混合指标优化问题的交互式进化计算[J]. 电子学报, 2020, 48(7): 1361-1368.
[10]	徐超群, 易忠, 孟立飞, 刘超波, 黄魁. 基于遗传算法的卫星磁模型研究[J]. 电子学报, 2020, 48(6): 1108-1112.
[11]	唐香琼, 黄春跃, 梁颖, 匡兵, 赵胜军. 基于再流焊冷却过程应力分析的板极组件BGA焊点参数优化[J]. 电子学报, 2020, 48(6): 1117-1123.
[12]	梁颖, 黄春跃, 邹涯梅, 高超, 匡兵. 基于扭转载荷的微尺度CSP焊点应力应变分析与优化[J]. 电子学报, 2020, 48(10): 2033-2040.
[13]	段毅, 谭贤四, 曲智国, 王红. 基于分支定界法的相控阵雷达事件调度算法[J]. 电子学报, 2019, 47(6): 1309-1315.
[14]	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.
[15]	李军华, 黎明, 陈昊, 伍家驹. 正态随机噪声环境下遗传算法的动态适应度评价[J]. 电子学报, 2019, 47(3): 649-656.

基于多算子协同进化的自适应并行量子遗传算法

Cooperative Evolution of Multiple Operators Based Adaptive Parallel Quantum Genetic Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics