Population-based local search algorithms for cross-domain search

Abstract

Population-based local search is a meta-heuristic algorithm combining the principles of the population-based search and the local search. This study presents an extensive comparison of two population-based local search approaches, specifically, the steady state memetic algorithm (SSMA) and a population-based iterated local search (PILS). To the best of our knowledge, PILS is proposed first for cross-domain search. Both approaches are implemented in Hyper-heuristics Flexible Framework (HyFlex) which contains different operators for different problem domains. The operators used in PILS and SSMA are the ones defined in HyFlex and the operator selection is done using two heuristic selection methods, namely, Simple Random and Reinforcement Learning with Tournament selection. The performance of the proposed methods with the selection methods is assessed over nine problem domains in HyFlex. The results reveal the success of the presented approaches for the crossdomain search.

Keywords

• Population-based local search
• Memetic algorithms
• Hyper-heuristics
• Iterated local search
• Combinatorial optimization

Alanlar-arası arama için popülasyona dayalı yerel arama algoritmaları

Abstract

Popülasyona dayalı yerel arama, popülasyona dayalı arama ve yerel aramanın ilkelerini birleştiren meta-sezgisel bir algoritmadır. Bu çalışma, iki farklı popülasyona dayalı yerel arama yaklaşımının kapsamlı bir karşılaştırmasını sunmaktadır: kararlı durum memetik algoritma (SSMA) ve popülasyona dayalı iteratif yerel arama (PILS). PILS, bildiğimiz kadarıyla, alanlar arası arama için ilk önerilen yöntemdir. Her iki yaklaşım da farklı problem alanları için farklı operatörler içeren Hyper-heuristics Flexible Framework (HyFlex) üzerinde uygulanmıştır. PILS ve SSMA'da kullanılan operatörler, HyFlex'te tanımlanan operatörlerdir ve bu operatörler arasından seçim yapmak için Basit Rastgele ve Turnuva seçimi ile Pekiştirmeli Öğrenme yöntemleri kullanılmaktadır. Önerilen yöntemlerin her iki seçim yöntemiyle performansı HyFlex' teki dokuz farklı problem üzerinden değerlendirilmiştir. Sonuçlar, alanlar arası arama için sunulan yaklaşımların başarılı olduğunu ortaya koymaktadır.

Keywords

• Popülasyona dayalı yerel arama
• Memetik algoritma
• Üst-sezgiseller
• Yinelemeli yerel arama
• Kombinatoryal optimizasyon

References

1. [1] Şahin Y, Karagül K. “Solving travelling salesman problem using hybrid fluid genetic algorithm (HFGA)”. Pamukkale University Journal of Engineering Sciences, 25(1), 106-114, 2019.
2. [2] Demir İ, Kiraz B, Corut Ergin F. “Experimental evaluation of meta-heuristics for multi-objective capacitated multiple allocation hub location problem”. Engineering Science and Technology, an International Journal, 29, 1-10, 2022.
3. [3] Du KL, Swamy MNS. Search and Optimization by Metaheuristics: Techniques and Algorithms Inspired by Nature. 1st ed. Cham, Switzerland, Birkhauser, 2016.
4. [4] Martí R, Pardalos PM, Resende MGC. Handbook of Heuristics. 1st ed. Cham, Switzerland, Springer, 2018.
5. [5] Karaoğlan AD. “Optimization of welding job-shop scheduling problem under variable workstation constraint: an industrial application with Arena simulation based genetic algorithm”. Pamukkale University Journal of Engineering Sciences, 28(1), 139-147, 2022.
6. [6] Kocer HG, Türkoğlu B, Uymaz SA. “Chaotic golden ratio guided local search for big data optimization”. Engineering Science and Technology, an International Journal, 41, 1-12, 2023.
7. [7] Türkoğlu B, Eroğlu H. Genetic Algorithm for Route Optimization. Editor: Dey N. Applied Genetic Algorithm and Its Variants, 51-79, Singapore, Springer, 2023.
8. [8] Burke EK, Gendreau M, Hyde MR, Kendall G, Ochoa G, Özcan E, Qu R. “Hyper-heuristics: A survey of the state of the art”. Journal of Operational Research Society, 64(12), 1695–1724, 2013.

9. [9] Chen X, Ong YS, Lim MH, Tan KC. “A multi-facet survey on memetic computation”. IEEE Transactions on Evolutionary Computation, 15(5), 591–607, 2011.
10. [10] Neri F, Cotta C. “Memetic algorithms and memetic computing optimization: A literature review”. Swarm and Evolutionary Computation, 2, 1–14, 2012.
11. [11] Gong G, Deng Q, Chiong R, Gong X, Huang H. “An effective memetic algorithm for multi-objective job-shop scheduling”. Knowledge-Based Systems, 182, 1-14, 2019.
12. [12] Moscato P, Mathieson L. Memetic Algorithms for Business Analytics and Data Science: A Brief Survey. Editors: Moscato P, de Vries NJ. Business and Consumer Analytics: New Ideas, 545–608, Cham, Switzerland, Springer, 2019.
13. [13] Hemanth DJ, Kumar BV, Manavalan GK. Recent Advances on Memetic Algorithms and Its Applications in Image Processing. 1st ed. Singapore, Springer, 2020.
14. [14] Özcan E, Asta S, Altıntaş C. “Memetic algorithms for Cross-domain Heuristic Search”. 13th UK Workshop on Computational Intelligence, Guildford, Surrey, United Kingdom, 9-11 September 2013.
15. [15] Özcan E, Drake JH, Altıntaş C, Asta S. “A self-adaptive Multimeme Memetic Algorithm co-evolving utility scores to control genetic operators and their parameter settings”. Applied Soft Computing Journal, 49, 81-93, 2016.
16. [16] Kheiri A, Özcan E. “An iterated multi-stage selection hyper-heuristic”. European Journal of Operational Research, 250(1), 77–90, 2016.
17. [17] Adriaensen S, Ochoa G, Nowe A. “A benchmark set extension and comparative study for the hyflex framework”. IEEE Congress on Evolutionary Computation, Sendai, Japan, 25-28 May 2015.
18. [18] Drake JH, Kheiri A, Özcan E, Burke EK. “Recent advances in selection hyper-heuristics”. European Journal of Operational Research, 285(2), 405–428, 2020.
19. [19] Cowling P, Kendall G, Soubeiga E. “A hyper-heuristic approach to scheduling a sales summit”. Practice and Theory of Automated Timetabling III: Third International Conference, Konstanz, Germany, 16-18 August 2000.
20. [20] Ahmed L, Mumford C, Kheiri A. “Solving urban transit route design problem using selection hyper-heuristics”. European Journal of Operational Research, 274(2), 545–559, 2019.
21. [21] Kheiri A, Gretsista A, Keedwell E, Lulli G, Epitropakis MG, Burke EK. “A hyper-heuristic approach based upon a hidden Markov model for the multi-stage nurse rostering problem”. Computers and Operations Research, 130, 1-13, 2021.
22. [22] Kheiri A, Keedwell E. “A hidden markov model approach to the problem of heuristic selection in hyper-heuristics with a case study in high school timetabling problems”. Evolutionary Computation, 25(3), 473–501, 2017.
23. [23] Brandao J. “A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem”. European Journal of Operational Research, 284(2), 559–571, 2020.
24. [24] Lourenço HR, Martin OC, Stützle T. Iterated Local Search: Framework and Applications. Editors: Gendreau M, Potvin JY. Handbook of Metaheuristics, 129-168, Boston, USA, Springer International Publishing, 2019.
25. [25] Benmezal L, Benhamou B, Boughaci D. “Evolutionary iterated local search meta-heuristic for the antenna positioning problem in cellular networks”. Computational Intelligence, 38(3), 1183-1214, 2022.
26. [26] Sabar NR, Goh SL, Turky A, Kendall G. “Population-based iterated local search approach for dynamic vehicle routing problems”. IEEE Transactions on Automation Science and Engineering, 19(4), 2933–2943, 2022.
27. [27] Ochoa G, Hyde M, Curtois T, Vazquez-Rodriguez JA, Walker J, Gendreau M, Kendall G, McCollum B, Parkes AJ, Petrovic S, Burke EK. “Hyflex: A benchmark framework for cross-domain heuristic search”. Evolutionary Computation in Combinatorial Optimization, Málaga, Spain, 11-13 April 2012.
28. [28] Burke EK, Gendreau M, Hyde M, Kendall G, McCollum B, Ochoa G, Parkes AJ, Petrovic S. “The cross-domain heuristic search challenge-an international research competition”. Learning and Intelligent Optimization, Rome, Italy, 17-21 January 2011.
29. [29] Kheiri A, Keedwell E. “A sequence-based selection hyper-heuristic utilising a hidden markov model”. Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain, 11-15 July 2015.
30. [30] Asta S, Özcan E. “A tensor-based selection hyper-heuristic for cross-domain heuristic search”. InformationSciences, 299, 412–432, 2015.
31. [31] Meignan D, Schwarze S, Voß S. “Improving local-search metaheuristics through look-ahead policies”. Annals of Mathematics and Artificial Intelligence, 76(1), 59–82, 2016.
32. [32] Ferreira AS, Goncalves RA, Pozo A. “A multi-armed bandit selection strategy for hyper-heuristics”. 2017 IEEE Congress on Evolutionary Computation, Donostia, Spain, 5-8 June 2017.
33. [33] Jackson WG, Özcan E, John RI. “Tuning a simulated annealing metaheuristic for cross-domain search”. 2017 IEEE Congress on Evolutionary Computation, Donostia, Spain, 5-8 June 2017.
34. [34] Almutairi A, Özcan E, Kheiri A, Jackson WG. “Performance of selection hyper-heuristics on the extended hyflex domains”. International Symposium on Computer and Information Sciences, Krakow, Poland, 27-28 October 2016.
35. [35] Adriaensen S, Brys T, Nowe A. “Fair-share ILS: A simple state-of-the-art iterated local search hyperheuristic”. 2014 Annual Conference on Genetic and Evolutionary Computation, New York, USA, 12-16 July 2014.
36. [36] Adubi SA, Oladipupo OO, Olugbara OO. “Configuring the perturbation operations of an iterated local search algorithm for cross-domain search: A probabilistic learning approach”. 2021 IEEE Congress on Evolutionary Computation, Krakow, Poland, 28 June-1 July 2021.
37. [37] Adubi SA, Oladipupo OO, Olugbara OO. “Evolutionary algorithm-based iterated local search hyper-heuristic for combinatorial optimization problems”. Algorithms, 15(11), 1-30, 2022.
38. [38] Gümüş DB, Özcan E, Atkin J. “An investigation of tuning a memetic algorithm for cross-domain search”. 2016 IEEE Congress on Evolutionary Computation, Vancouver, British Columbia, Canada, 24-29 July 2016.
39. [39] Mısır M, Verbeeck K, De Causmaecker P, Vanden Berghe G. “An Intelligent hyper-heuristic framework for CHeSC 2011”. International Conference on Learning and Intelligent Optimization (LION 2012), Paris, France, 16-20 January 2012.
40. [40] Chan CY, Xue F, Ip WH, Cheung CF. “A hyper-heuristic inspired by pearl hunting”. International Conference on Learning and Intelligent Optimization (LION 2012), Paris, France, 16-20 January 2012.
41. [41] Lehrbaum A, Musliu N. “A new hyperheuristic algorithm for cross-domain search problems”. International Conference on Learning and Intelligent Optimization (LION 2012), Paris, France, 16-20 January 2012.