Self-adaptive mechanism based genetic algorithms for combinatorial optimization problems

doi:10.19682/j.cnki.1005-8885.2019.0021

中国邮电高校学报(英文版) ›› 2019, Vol. 26 ›› Issue (5): 11-21.doi: 10.19682/j.cnki.1005-8885.2019.0021

• Artificial Intelligence • 上一篇下一篇

Self-adaptive mechanism based genetic algorithms for combinatorial optimization problems

Qu Zhijian , Wang Shasha, Xu Hongbo, Li Panjing, Li Caihong

1. 山东理工大学

收稿日期:2018-11-14 修回日期:2019-04-09 出版日期:2019-10-31 发布日期:2019-11-06
通讯作者: 曲志坚 E-mail:handuhandu@163.com
基金资助:
国家自然科学基金

Self-adaptive mechanism based genetic algorithms for combinatorial optimization problems

Qu Zhijian , Wang Shasha, Xu Hongbo, Li Panjing, Li Caihong

Received:2018-11-14 Revised:2019-04-09 Online:2019-10-31 Published:2019-11-06
Contact: Zhi-Jian QU E-mail:handuhandu@163.com
Supported by:
National Natural Science Foundation of China

摘要/Abstract

摘要： To improve the evolutionary algorithm performance, especially in convergence speed and global optimization ability, a self-adaptive mechanism is designed both for the conventional genetic algorithm (CGA) and the quantum inspired genetic algorithm (QIGA). For the self-adaptive mechanism, each individual was assigned with suitable evolutionary parameter according to its current evolutionary state. Therefore, each individual can evolve toward to the currently best solution. Moreover, to reduce the running time of the proposed self-adaptive mechanism based QIGA (SAM-QIGA), a multi-universe parallel structure was employed in the paper. Simulation results show that the proposed SAM-QIGA have better performances both in convergence and global optimization ability.

关键词: combinatorial optimization, self-adaptive, genetic algorithm, multi-universe parallel

Abstract: To improve the evolutionary algorithm performance, especially in convergence speed and global optimization ability, a self-adaptive mechanism is designed both for the conventional genetic algorithm (CGA) and the quantum inspired genetic algorithm (QIGA). For the self-adaptive mechanism, each individual was assigned with suitable evolutionary parameter according to its current evolutionary state. Therefore, each individual can evolve toward to the currently best solution. Moreover, to reduce the running time of the proposed self-adaptive mechanism based QIGA (SAM-QIGA), a multi-universe parallel structure was employed in the paper. Simulation results show that the proposed SAM-QIGA have better performances both in convergence and global optimization ability.

Key words: combinatorial optimization, self-adaptive, genetic algorithm, multi-universe parallel

Qu Zhijian, Wang Shasha, Xu Hongbo, Li Panjing, Li Caihong. Self-adaptive mechanism based genetic algorithms for combinatorial optimization problems[J]. The Journal of China Universities of Posts and Telecommunications, 2019, 26(5): 11-21.

参考文献

1. Qu B Y, Zhu Y S, Jiao Y C, and et al. A survey on multi-objective evolutionary algorithms for the solution of the environmental/economic dispatch problems. Swarm and Evolutionary Computation, 2018, 38: 1-11. 2. Xing H, Ji Y, Bai L, and et al. An adaptive evolution based quantum inspired evolutionary algorithm for QoS multicasting in IP/DWDM networks. Computer Communications, 2009, 32(6): 1086-1094. 3. Qu Z, Fu J, Liu X, Li C. Network coding resources optimization with transmission delay constraint in multicast networks. High Technology Letters, 2017, 23(1): 30-37. 4. Hou Y, Wu N, Zhou M, Li Z. Pareto-Optimization for Scheduling of Crude Oil Operations in Refinery via Genetic Algorithm. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(3): 296-307. 5. Zitzler E, and Lothar T. Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 1999, 3(4): 517-530. 6. Cho J, Wang Y, Chen I, Chan K. A Survey on Modeling and Optimizing Multi-Objective Systems. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1867-1901. 7. Han K H, and Kim J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE transactions on evolutionary computation, 2002, 6(6): 580-593. 8. Ada C, Wu P, Chu F, and Zhou M C. Improved quantum-inspired evolutionary algorithm for large-size lane reservation. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(12): 1535-1548. 9. Gupta S, Stuti M, Tamanna G, and et al. Parallel quantum-inspired evolutionary algorithms for community detection in social networks. Applied Soft Computing, 2017, 61: 331-353. 10. Konar D, Siddhartha B, Kalpana S, and et al. An improved Hybrid Quantum-Inspired Genetic Algorithm (HQIGA) for scheduling of real-time task in multiprocessor system. Applied Soft Computing, 2017, 53: 296-307. 11. Qu Z, Liu X, Zhang X, and et al. Hamming-distance-based adaptive quantum-inspired evolutionary algorithm for network coding resources optimization. The Journal of China Universities of Posts and Telecommunications, 2015, 22(3): 92-99. 12. Sheng X, He Y, Chang L, and et al. An Improved Quantum-Inspired Evolutionary Algorithm for Knapsack Problems. The 3rd International Conference on Cloud Computing and Security (ICCCS 2017), 16-18 Jun, 2017, Nanjing, China. Springer, Cham, 2017: 694-708. 13. Li J, Li W, Huang Y. A New Quantum Rotation Angle of Quantum-Inspired Evolutionary Algorithm for TSP. 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), 21-24 July, 2017, Guangzhou, China. IEEE, 2017: 369-374. 14. Xiong H, Wu Z, Fan H, Li G, Jiang G. Quantum rotation gate in quantum-inspired evolutionary algorithm: A review, analysis and comparison study. Swarm and Evolutionary Computation, 2018, 42: 43-57. 15. Darrell W. A genetic algorithm tutorial. Statistics and computing, 1994, 4(2): 65-85. 16. Han K H, Park K H, Lee C H, and et al. Parallel quantum-inspired genetic algorithm for combinatorial optimization problem. Evolutionary Computation, 2001. Proceedings of the 2001 Congress on. IEEE, 2001, 2: 1422-1429. 17. Wang Y, Feng X Y, Huang Y X, et al. A novel quantum swarm evolutionary algorithm and its applications. Neurocomputing, 2007, 70(4-6): 633-640. 18. Wang Y P, Li Y H. A Novel Quantum Genetic Algorithm for TSP. Chinese journal of computers, 2007(05):5748-5755. (in chinese)

Self-adaptive mechanism based genetic algorithms for combinatorial optimization problems

Self-adaptive mechanism based genetic algorithms for combinatorial optimization problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价