Efficient and Adaptive Operator Selection in Swarm Intelligence Using Machine Learning Approaches

Abstract

Problem solving is one of renown artificial intelligence fields, which has kept attracting research for decades. Swarm intelligence is recognised as the family of the state-of-art approaches in problem solving, which attracted much research attention for the enduring problems. The main challenge appears to be in the speed of algorithmic approximation where many approaches were proposed to accelerate approximation avoiding local optima. Recent research demonstrates that inefficiencies in search procedures can be side-stepped using the experiences gained while search is undergoing utilising machine learning approaches. Reinforcement learning is a success-proven approach for online learning, especial when training data is not available upfront. In this paper, we overview the usefulness of machine learning in performance improvement of artificial bee colony algorithms in solving combinatorial optimisation problems. Furthermore, we demonstrate how reinforcement learning approaches facilitate swarm intelligence algorithms to gain experience for immediate and later use to build capable and powerful operator selection schemes, which help improve efficiency of swarm intelligence problem solvers

Keywords

• adaptive operator selection
• machine learning
• reinforcement learning
• artificial bee colony
• set union knapsack problem

References

1. [1] G. J. Woeginger, ‘Exact Algorithms for NP-Hard Problems: A Survey’, in Combinatorial Optimization — Eureka, You Shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers, G. and R. G. Jünger Michael and Reinelt, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 185–207. doi: 10.1007/3-540-36478-1_17.
2. [2] M. Črepinšek, S.-H. Liu, and M. Mernik, ‘Exploration and exploitation in evolutionary algorithms: A survey’, ACM computing surveys (CSUR), vol. 45, no. 3, pp. 1–33, 2013.
3. [3] D. H. Wolpert and W. G. Macready, ‘No free lunch theorems for optimization’, IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, Apr. 1997, doi: 10.1109/4235.585893.
4. [4] K.-P. L. Proctor Robert W. and Vu, ‘Human Information Processing’, in Encyclopedia of the Sciences of Learning, N. M. Seel, Ed., Boston, MA: Springer US, 2012, pp. 1458–1460. doi: 10.1007/978-1-4419-1428-6_722.
5. [5] D. B. Leake, ‘Problem Solving and Reasoning: Case-based’, International Encyclopedia of the Social & Behavioral Sciences, pp. 12117–12120, 2001, doi: 10.1016/B0-08-043076-7/00545-3.
6. [6] R. Durgut and M. E. Aydin, ‘Adaptive binary artificial bee colony algorithm’, Appl Soft Comput, vol. 101, p. 107054, Mar. 2021, doi: 10.1016/J.ASOC.2020.107054.
7. [7] R. Durgut, M. E. Aydin, and A. Rakib, ‘Transfer Learning for Operator Selection: A Reinforcement Learning Approach’, Algorithms, vol. 15, no. 1, Jan. 2022, doi: 10.3390/A15010024.
8. [8] R. Durgut, M. E. Aydin, and I. Atli, ‘Adaptive operator selection with reinforcement learning’, Inf Sci (N Y), vol. 581, pp. 773–790, Dec. 2021, doi: 10.1016/J.INS.2021.10.025.

9. [9] E.-G. Talbi, ‘Machine Learning into Metaheuristics: A Survey and Taxonomy’, ACM Comput. Surv., vol. 54, no. 6, Jul. 2021, doi: 10.1145/3459664.
10. [10] M. Tessari and G. Iacca, ‘Reinforcement Learning Based Adaptive Metaheuristics’, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, in GECCO ’22. New York, NY, USA: Association for Computing Machinery, 2022, pp. 1854–1861. doi: 10.1145/3520304.3533983.
11. [11] T. Wauters, K. Verbeeck, P. de Causmaecker, and G. vanden Berghe, ‘Boosting metaheuristic search using reinforcement learning’, in Hybrid metaheuristics, Springer, 2013, pp. 433–452.
12. [12] J. C. Bansal, H. Sharma, and S. S. Jadon, ‘Artificial bee colony algorithm: a survey’, International Journal of Advanced Intelligence Paradigms, vol. 5, no. 1–2, pp. 123–159, Jan. 2013, doi: 10.1504/IJAIP.2013.054681.
13. [13] C. Ozturk, E. Hancer, and D. Karaboga, ‘A novel binary artificial bee colony algorithm based on genetic operators’, Inf Sci (N Y), vol. 297, pp. 154–170, Mar. 2015, doi: 10.1016/J.INS.2014.10.060.
14. [14] R. DURGUT and M. AYDİN, ‘Çok boyutlu sırt çantası problemi için adaptif ikili yapay arı kolonisi algoritması (AİYAK)’, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, May 2021, doi: 10.17341/gazimmfd.804858.
15. [15] M. Düğenci and M. E. Aydin, ‘A honeybees-inspired heuristic algorithm for numerical optimisation’, Neural Comput Appl, vol. 32, no. 16, pp. 12311–12325, Aug. 2020, doi: 10.1007/s00521-019-04533-x.
16. [16] R. Durgut and M. E. Aydin, ‘Multi Strategy Search with Crow Search Algorithm’, in Optimisation Algorithms and Swarm Intelligence, Prof. N. Vakhania, Ed., Rijeka: IntechOpen, 2022. doi: 10.5772/intechopen.102862.
17. [17] Z. Cui et al., ‘Hybrid many-objective particle swarm optimization algorithm for green coal production problem’, Inf Sci (N Y), vol. 518, pp. 256–271, May 2020, doi: 10.1016/j.ins.2020.01.018.
18. [18] D. Kizilay, M. F. Tasgetiren, H. Oztop, L. Kandiller, and P. N. Suganthan, ‘A Differential Evolution Algorithm with Q-Learning for Solving Engineering Design Problems’, in 2020 IEEE Congress on Evolutionary Computation (CEC), IEEE, Jul. 2020, pp. 1–8. doi: 10.1109/CEC48606.2020.9185743.
19. [19] W. xiang Wang, K. shun Li, X. zhen Tao, and F. hui Gu, ‘An improved MOEA/D algorithm with an adaptive evolutionary strategy’, Inf Sci (N Y), vol. 539, pp. 1–15, Oct. 2020, doi: 10.1016/J.INS.2020.05.082.
20. [20] Q. Lin et al., ‘Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm’, Inf Sci (N Y), vol. 339, pp. 332–352, Apr. 2016, doi: 10.1016/J.INS.2015.12.022.
21. [21] C. Qu, W. Gai, M. Zhong, and J. Zhang, ‘A novel reinforcement learning based grey wolf optimizer algorithm for unmanned aerial vehicles (UAVs) path planning’, Appl Soft Comput, vol. 89, p. 106099, Apr. 2020, doi: 10.1016/J.ASOC.2020.106099.
22. [22] K. Li, A. Fialho, S. Kwong, and Q. Zhang, ‘Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition’, IEEE Transactions on Evolutionary Computation, vol. 18, no. 1, pp. 114–130, 2013.
23. [23] M. A. Al-Betar, I. A. Doush, A. T. Khader, and M. A. Awadallah, ‘Novel selection schemes for harmony search’, Appl Math Comput, vol. 218, no. 10, pp. 6095–6117, Jan. 2012, doi: 10.1016/J.AMC.2011.11.095.
24. [24] K. M. Sallam, S. M. Elsayed, R. A. Sarker, and D. L. Essam, ‘Landscape-based adaptive operator selection mechanism for differential evolution’, Inf Sci (N Y), vol. 418–419, pp. 383–404, Dec. 2017, doi: 10.1016/J.INS.2017.08.028.
25. [25] W. Khan Mashwani, A. Salhi, O. Yeniay, H. Hussian, and M. A. Jan, ‘Hybrid non-dominated sorting genetic algorithm with adaptive operators selection’, Appl Soft Comput, vol. 56, pp. 1–18, Jul. 2017, doi: 10.1016/J.ASOC.2017.01.056.
26. [26] D. B. Fogel, ‘Phenotypes, genotypes, and operators in evolutionary computation’, in Proceedings of 1995 IEEE International Conference on Evolutionary Computation, p. 193.
27. [27] Á. Fialho, ‘Adaptive Operator Selection for Optimization’, Université Paris Sud - Paris XI, 2010. [Online]. Available: https://tel.archives-ouvertes.fr/tel-00578431
28. [28] R. Durgut, M. E. Aydin, H. Ihshaish, and R. Abdur, ‘Analysing the Predictivity of Features to Characterise the Search Space’, in Artificial Neural Networks and Machine Learning – ICANN 2022, E. Pimenidis and M. E. Aydin, Eds., Bristol: Springer, Sep. 2022, pp. 1–13.
29. [29] M. E. Aydin, R. Durgut, A. Rakib, and H. Ihshaish, ‘Feature-based search space characterisation for data-driven adaptive operator selection’, Evolving Systems, Dec. 2023, doi: 10.1007/s12530-023-09560-7.
30. [30] Y. He, H. Xie, T. L. Wong, and X. Wang, ‘A novel binary artificial bee colony algorithm for the set-union knapsack problem’, Future Generation Computer Systems, vol. 78, pp. 77–86, Jan. 2018, doi: 10.1016/J.FUTURE.2017.05.044.