基于多算子协同进化的自适应并行量子遗传算法
|
摘要
量子遗传算法具有种群规模小,全局搜索能力强的特点被广泛应用于各类优化问题的求解.为了进一步提高量子遗传算法的收敛速度和搜索稳定性,克服算法的早熟问题,本文改进了基于自适应机制的量子遗传算法.在自适应量子遗传算法的基础上根据种群的适应度定义了个体相似度评价算子、个体适应度评价算子和种群变异调整算子及相应算子的计算方法,利用多算子协同评价当前种群状态并根据进化代数的变化,自适应的改变个体的变异概率,提高了算法全局寻优能力和收敛速度,降低了算法陷入局部寻优的概率.此外,为了提高算法的时间效率,将算法采用并行多宇宙的方式实现.实验结果表明,本文提出的算法在全局搜索性能、收敛速度和时间效率方面有较好的综合表现.
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.
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.
引文
[1]Qu B Y,Zhu Y S,Jiao Y C,et al. A survey on multi-objec-tive evolutionary algorithms for the solution of the environ-mental/economic dispatch problems[J]. Sw arm and Evo-lutionary Computation,2018,38:1-11.
[2] Wang Y,Feng X Y,Huang Y X,et al. A novel quantumsw arm evolutionary algorithm and its applications[J]. Neu-rocomputing,2007,70(4-6):633-640.
[3] Han K H,Kim J H. Quantum-inspired evolutionary algo-rithm for a class of combinatorial optimization[J]. IEEETransactions 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 forTSP[J]. Chinese Journal of Computers,2007(5):748-755.(in Chinese)
[5]Kuo S Y,Chou Y H,Chen C Y. Quantum-inspired algo-rithm for cyber-physical visual surveillance deploymentsystems[J]. Computer Netw orks,2017,117:5-18.
[6]Wang X M,Liu S,Li Q,Liu Z P. Underwater sonar imagedetection:a novel quantum-inspired shuffled frog leapingalgorithm[J]. Chinese Journal of Electronics,2018,27(3):588-594.
[7] Wu X,Wu S. An elitist quantum-inspired evolutionary al-gorithm for the flexible job-shop scheduling problem[J].Journal of Intelligent M anufacturing,2017,28(6):1441-1457.
[8]Qu Z,Liu X,Zhang X,et al. Hamming-distance-based a-daptive quantum-inspired evolutionary algorithm for net-w ork coding resources optimization[J]. the Journal of Chi-na Universities of Posts and Telecommunications,2015,22(3):92-99.
[9] Qu Zhijian,Fu Jia,Liu Xiaohong,Li Caihong. Networkcoding resources optimization w ith transmission delay con-straint in multicast netw orks[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 quantumgenetic 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-in-spired evolutionary algorithms for community detection insocial netw orks[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. M ulti-universe parallelquantum-inspired evolutionary algorithm based on adap-tive 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 geneticalgorithm based on adaptive mechanism[J]. ApplicationResearch 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. M ulti-universe parallelquantum genetic algorithm[J]. Acta Electronic Sinica,2004,32(6):923-928.(in Chinese)
[2] Wang Y,Feng X Y,Huang Y X,et al. A novel quantumsw arm evolutionary algorithm and its applications[J]. Neu-rocomputing,2007,70(4-6):633-640.
[3] Han K H,Kim J H. Quantum-inspired evolutionary algo-rithm for a class of combinatorial optimization[J]. IEEETransactions 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 forTSP[J]. Chinese Journal of Computers,2007(5):748-755.(in Chinese)
[5]Kuo S Y,Chou Y H,Chen C Y. Quantum-inspired algo-rithm for cyber-physical visual surveillance deploymentsystems[J]. Computer Netw orks,2017,117:5-18.
[6]Wang X M,Liu S,Li Q,Liu Z P. Underwater sonar imagedetection:a novel quantum-inspired shuffled frog leapingalgorithm[J]. Chinese Journal of Electronics,2018,27(3):588-594.
[7] Wu X,Wu S. An elitist quantum-inspired evolutionary al-gorithm for the flexible job-shop scheduling problem[J].Journal of Intelligent M anufacturing,2017,28(6):1441-1457.
[8]Qu Z,Liu X,Zhang X,et al. Hamming-distance-based a-daptive quantum-inspired evolutionary algorithm for net-w ork coding resources optimization[J]. the Journal of Chi-na Universities of Posts and Telecommunications,2015,22(3):92-99.
[9] Qu Zhijian,Fu Jia,Liu Xiaohong,Li Caihong. Networkcoding resources optimization w ith transmission delay con-straint in multicast netw orks[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 quantumgenetic 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-in-spired evolutionary algorithms for community detection insocial netw orks[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. M ulti-universe parallelquantum-inspired evolutionary algorithm based on adap-tive 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 geneticalgorithm based on adaptive mechanism[J]. ApplicationResearch 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. M ulti-universe parallelquantum genetic algorithm[J]. Acta Electronic Sinica,2004,32(6):923-928.(in Chinese)
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |