GRAHF: A Hyper-Heuristic Framework for Evolving Heterogeneous Island Model Topologies
Pages 1054 - 1063
Abstract
Practitioners frequently encounter the challenge of selecting the best optimization algorithm from a pool of options. However, why not, rather than selecting a single algorithm, let evolution determine the optimal combination of all algorithms? In this paper, we present an approach to algorithm design inspired by a well-known traditional method for coarse-grained hybridization: the heterogeneous island model. Our hyper-heuristic framework represents island models as graphs and identifies optimal island topologies and parameters for specific sets of problem instances. Since the framework operates at the level of metaheuristic algorithms rather than components and incorporates a configuration mechanism directly into the search, it combines concepts from algorithm design, selection, and configuration. The proposed framework is investigated on 24 training sets of varying difficulty and demonstrates its ability to discover complex hybrids. A post-evaluation on real-world constrained optimization problems shows a significant improvement over the algorithms on their own. These results suggest that it is a promising way to design hybrid metaheuristics with minimal manual intervention, given representative training instances, a set of optimization algorithms, and sufficient computational resources.
Supplemental Material
PDF File
Supplementary Material
- Download
- 182.22 KB
References
[1]
Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau. 2015. An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems. In 4th International Conference on Pattern Recognition Applications and Methods 2015. Lisbon, Portugal.
[2]
Shakhnaz Akhmedova, Vladimir Stanovov, and Eugene Semenkin. 2018. Soft Island Model for Population-Based Optimization Algorithms. In Advances in Swarm Intelligence (Lecture Notes in Computer Science), Ying Tan, Yuhui Shi, and Qirong Tang (Eds.). Springer International Publishing, Cham, 68--77.
[3]
Ignacio Arnaldo, Iván Contreras, David Millán-Ruiz, J. Ignacio Hidalgo, and Natalio Krasnogor. 2013. Matching Island Topologies to Problem Structure in Parallel Evolutionary Algorithms. Soft Computing 17, 7 (July 2013), 1209--1225.
[4]
Timothy Atkinson, Detlef Plump, and Susan Stepney. 2018. Evolving Graphs by Graph Programming. In Genetic Programming (Lecture Notes in Computer Science), Mauro Castelli, Lukas Sekanina, Mengjie Zhang, Stefano Cagnoni, and Pablo García-Sánchez (Eds.). Springer International Publishing, Cham, 35--51.
[5]
Doğan Aydın, Gürcan Yavuz, and Thomas Stützle. 2017. ABC-X: A Generalized, Automatically Configurable Artificial Bee Colony Framework. Swarm Intelligence 11, 1 (March 2017), 1--38.
[6]
Theodore C. Belding. 1995. The Distributed Genetic Algorithm Revisited. arXiv:adap-org/9504007
[7]
Hans-Georg Beyer and Steffen Finck. 2012. HappyCat - A Simple Function Class Where Well-Known Direct Search Algorithms Do Fail. In Parallel Problem Solving from Nature - PPSN XII (Lecture Notes in Computer Science), Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, and Mario Pavone (Eds.). Springer, Berlin, Heidelberg, 367--376.
[8]
Hans-Georg Beyer and Hans-Paul Schwefel. 2002. Evolution Strategies - A Comprehensive Introduction. Natural Computing 1, 1 (March 2002), 3--52.
[9]
Nathan Brown, Ben McKay, François Gilardoni, and Johann Gasteiger. 2004. A Graph-Based Genetic Algorithm and Its Application to the Multiobjective Evolution of Median Molecules. Journal of Chemical Information and Computer Sciences 44, 3 (May 2004), 1079--1087.
[10]
Christian L. Camacho-Villalón, Marco Dorigo, and Thomas Stützle. 2022. PSO-X: A Component-Based Framework for the Automatic Design of Particle Swarm Optimization Algorithms. IEEE Transactions on Evolutionary Computation 26, 3 (June 2022), 402--416.
[11]
Andreas Fischbach and Thomas Bartz-Beielstein. 2020. Improving the Reliability of Test Functions Generators. Applied Soft Computing 92 (July 2020), 106315.
[12]
Michel Gendreau and Jean-Yves Potvin. 2018. Handbook of Metaheuristics (3rd ed. 2019 edition ed.). Springer, New York, NY.
[13]
Nikolaus Hansen, Anne Auger, Dimo Brockhoff, Dejan Tušar, and Tea Tušar. 2016. COCO: Performance Assessment. arXiv:1605.03560 [cs]
[14]
Nikolaus Hansen, Anne Auger, Dimo Brockhoff, and Tea Tušar. 2022. Anytime Performance Assessment in Blackbox Optimization Benchmarking. IEEE Transactions on Evolutionary Computation 26, 6 (Dec. 2022), 1293--1305.
[15]
Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, and Dimo Brockhoff. 2021. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optimization Methods and Software 36, 1 (Jan. 2021), 114--144.
[16]
Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. 2003. Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). Evolutionary Computation 11, 1 (March 2003), 1--18.
[17]
Sean Harris, Travis Bueter, and Daniel R. Tauritz. 2015. A Comparison of Genetic Programming Variants for Hyper-Heuristics. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO Companion '15). Association for Computing Machinery, New York, NY, USA, 1043--1050.
[18]
Holger Hoos and Thomas Stützle. 2004. Stochastic Local Search: Foundations & Applications. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
[19]
Changwu Huang, Yuanxiang Li, and Xin Yao. 2020. A Survey of Automatic Parameter Tuning Methods for Metaheuristics. IEEE Transactions on Evolutionary Computation 24, 2 (April 2020), 201--216.
[20]
Momin Jamil and Xin-She Yang. 2013. A Literature Survey of Benchmark Functions For Global Optimization Problems. International Journal of Mathematical Modelling and Numerical Optimisation 4, 2 (2013), 150. arXiv:1308.4008 [cs, math]
[21]
Jan Jensen. 2019. A Graph-Based Genetic Algorithm and Generative Model/Monte Carlo Tree Search for the Exploration of Chemical Space. Chemical Science 10, 12 (2019), 3567--3572.
[22]
James Kennedy and Russell Eberhart. 1995. Particle Swarm Optimization. In Proceedings of ICNN'95 - International Conference on Neural Networks, Vol. 4. 1942-1948 vol.4.
[23]
Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation 27, 1 (March 2019), 3--45.
[24]
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220, 4598 (May 1983), 671--680.
[25]
Abhishek Kumar, Guohua Wu, Mostafa Z. Ali, Rammohan Mallipeddi, Ponnuthurai Nagaratnam Suganthan, and Swagatam Das. 2020. A Test-Suite of Non-Convex Constrained Optimization Problems from the Real-World and Some Baseline Results. Swarm and Evolutionary Computation 56 (Aug. 2020), 100693.
[26]
Frédéric Lardeux and Adrien Goëffon. 2010. A Dynamic Island-Based Genetic Algorithms Framework. In Simulated Evolution and Learning (Lecture Notes in Computer Science), Kalyanmoy Deb, Arnab Bhattacharya, Nirupam Chakraborti, Partha Chakroborty, Swagatam Das, Joydeep Dutta, Santosh K. Gupta, Ashu Jain, Varun Aggarwal, Jürgen Branke, Sushil J. Louis, and Kay Chen Tan (Eds.). Springer, Berlin, Heidelberg, 156--165.
[27]
Coromoto León, Gara Miranda, Eduardo Segredo, and Carlos Segura. 2009. Parallel Hypervolume-Guided Hyperheuristic for Adapting the Multi-objective Evolutionary Island Model. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2008), Natalio Krasnogor, María Belén Melián-Batista, José Andrés Moreno Pérez, J. Marcos Moreno-Vega, and David Alejandro Pelta (Eds.). Springer, Berlin, Heidelberg, 261--272.
[28]
Ke Li and Jitendra Malik. 2016. Learning to Optimize. arXiv:1606.01885 [cs, math, stat]
[29]
Michael A. Lones. 2019. Instruction-Level Design of Local Optimisers Using Push GP. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '19). Association for Computing Machinery, New York, NY, USA, 1487--1494.
[30]
Michael A. Lones. 2020. Optimising Optimisers with Push GP. In Genetic Programming (Lecture Notes in Computer Science), Ting Hu, Nuno Lourenço, Eric Medvet, and Federico Divina (Eds.). Springer International Publishing, Cham, 101--117.
[31]
Michael A. Lones. 2021. Evolving Continuous Optimisers from Scratch. Genetic Programming and Evolvable Machines 22, 4 (Dec. 2021), 395--428.
[32]
Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and Thomas Stützle. 2016. The Irace Package: Iterated Racing for Automatic Algorithm Configuration. Operations Research Perspectives 3 (Jan. 2016), 43--58.
[33]
Manuel López-Ibánez, Marie-Eléonore Kessaci, and Thomas Stützle. 2017. Automatic Design of Hybrid Metaheuristics from Algorithmic Components. Technical Report. IRIDIA, Université Libre de Bruxelles, Brussels, Belgium.
[34]
Manuel Lopez-Ibanez and Thomas Stützle. 2012. The Automatic Design of Multi-objective Ant Colony Optimization Algorithms. IEEE Transactions on Evolutionary Computation 16, 6 (Dec. 2012), 861--875.
[35]
Gabriel Luque and Enrique Alba. 2011. Parallel Genetic Algorithms. Studies in Computational Intelligence, Vol. 367. Springer, Berlin, Heidelberg.
[36]
Marie-Eléonore Marmion, Franco Mascia, Manuel López-Ibáñez, and Thomas Stützle. 2013. Automatic Design of Hybrid Stochastic Local Search Algorithms. In Hybrid Metaheuristics (Lecture Notes in Computer Science), María J. Blesa, Christian Blum, Paola Festa, Andrea Roli, and Michael Sampels (Eds.). Springer, Berlin, Heidelberg, 144--158.
[37]
Qinxue Meng, Jia Wu, John Ellis, and Paul J. Kennedy. 2017. Dynamic Island Model Based on Spectral Clustering in Genetic Algorithm. In 2017 International Joint Conference on Neural Networks (IJCNN). 1724--1731.
[38]
Julian F. Miller (Ed.). 2011. Cartesian Genetic Programming. Springer, Berlin, Heidelberg.
[39]
Julian Francis Miller. 2020. Cartesian Genetic Programming: Its Status and Future. Genetic Programming and Evolvable Machines 21, 1 (June 2020), 129--168.
[40]
Péricles B. C. Miranda and Ricardo B. C. Prudêncio. 2020. A Novel Context-Free Grammar for the Generation of PSO Algorithms. Natural Computing 19, 3 (Sept. 2020), 495--513.
[41]
Riccardo Poli and Mario Graff. 2009. There Is a Free Lunch for Hyper-Heuristics, Genetic Programming and Computer Scientists. In Genetic Programming (Lecture Notes in Computer Science), Leonardo Vanneschi, Steven Gustafson, Alberto Moraglio, Ivanoe De Falco, and Marc Ebner (Eds.). Springer, Berlin, Heidelberg, 195--207.
[42]
Riccardo Poli, James Kennedy, and Tim Blackwell. 2007. Particle Swarm Optimization. Swarm Intelligence 1, 1 (June 2007), 33--57.
[43]
Jairo Rojas-Delgado, Josu Ceberio, Borja Calvo, and Jose A. Lozano. 2022. Bayesian Performance Analysis for Algorithm Ranking Comparison. IEEE Transactions on Evolutionary Computation 26, 6 (Dec. 2022), 1281--1292.
[44]
Jani Rönkkönen, Saku Kukkonen, and Kenneth V. Price. 2005. Real-Parameter Optimization with Differential Evolution. In 2005 IEEE Congress on Evolutionary Computation, Vol. 1. 506-513 Vol.1.
[45]
M. Ruciński, D. Izzo, and F. Biscani. 2010. On the Impact of the Migration Topology on the Island Model. Parallel Comput. 36, 10 (Oct. 2010), 555--571.
[46]
Patricia Ryser-Welch, Julian F. Miller, and Shahriar Asta. 2015. Generating Human-readable Algorithms for the Travelling Salesman Problem Using Hyper-Heuristics. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO Companion '15). Association for Computing Machinery, New York, NY, USA, 1067--1074.
[47]
Patricia Ryser-Welch, Julian F. Miller, Jerry Swan, and Martin A. Trefzer. 2016. Iterative Cartesian Genetic Programming: Creating General Algorithms for Solving Travelling Salesman Problems. In Genetic Programming (Lecture Notes in Computer Science), Malcolm I. Heywood, James McDermott, Mauro Castelli, Ernesto Costa, and Kevin Sim (Eds.). Springer International Publishing, Cham, 294--310.
[48]
Elias Schede, Jasmin Brandt, Alexander Tornede, Marcel Wever, Viktor Bengs, Eyke Hüllermeier, and Kevin Tierney. 2022. A Survey of Methods for Automated Algorithm Configuration. Journal of Artificial Intelligence Research 75 (Oct. 2022), 425--487.
[49]
Shinichi Shirakawa and Tomoharu Nagao. 2009. Evolution of Search Algorithms Using Graph Structured Program Evolution. In Genetic Programming (Lecture Notes in Computer Science), Leonardo Vanneschi, Steven Gustafson, Alberto Moraglio, Ivanoe De Falco, and Marc Ebner (Eds.). Springer, Berlin, Heidelberg, 109--120.
[50]
Rainer Storn. 1996. On the Usage of Differential Evolution for Function Optimization. In Proceedings of North American Fuzzy Information Processing. 519--523.
[51]
Thomas Stützle and Manuel López-Ibáñez. 2019. Automated Design of Metaheuristic Algorithms. In Handbook of Metaheuristics, Michel Gendreau and Jean-Yves Potvin (Eds.). Springer International Publishing, Cham, 541--579.
[52]
Sonja Surjanovic and Derek Bingham. 2013. Optimization Test Functions and Datasets. https://www.sfu.ca/~ssurjano/optimization.html.
[53]
Andrew M. Sutton, Monte Lunacek, and L. Darrell Whitley. 2007. Differential Evolution and Non-Separability: Using Selective Pressure to Focus Search. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO '07). Association for Computing Machinery, New York, NY, USA, 1428--1435.
[54]
El-Ghazali Talbi. 2009. Metaheuristics: From Design to Implementation. Wiley, Hoboken, NJ.
[55]
Jorge Tavares and Francisco B. Pereira. 2012. Automatic Design of Ant Algorithms with Grammatical Evolution. In Genetic Programming (Lecture Notes in Computer Science), Alberto Moraglio, Sara Silva, Krzysztof Krawiec, Penousal Machado, and Carlos Cotta (Eds.). Springer, Berlin, Heidelberg, 206--217.
[56]
Braden Tisdale, Deacon Seals, Aaron Scott Pope, and Daniel R. Tauritz. 2021. Directing Evolution: The Automated Design of Evolutionary Pathways Using Directed Graphs. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '21). Association for Computing Machinery, New York, NY, USA, 732--740.
[57]
Shengyin Wang and Kang Tai. 2004. Graph Representation for Structural Topology Optimization Using Genetic Algorithms. Computers & Structures 82, 20 (Aug. 2004), 1609--1622.
[58]
David H. Wolpert and William G. Macready. 1997. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1, 1 (April 1997), 67--82.
[59]
Jonathan Wurth, Helena Stegherr, Michael Heider, Leopold Luley, and Jörg Hähner. 2023. Fast, Flexible, and Fearless: A Rust Framework for the Modular Construction of Metaheuristics. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation (GECCO '23 Companion). Association for Computing Machinery, New York, NY, USA, 1900--1909.
[60]
Wenjie Yi, Rong Qu, Licheng Jiao, and Ben Niu. 2023. Automated Design of Metaheuristics Using Reinforcement Learning Within a Novel General Search Framework. IEEE Transactions on Evolutionary Computation 27, 4 (Aug. 2023), 1072--1084.
[61]
Qi Zhao, Qiqi Duan, Bai Yan, Shi Cheng, and Yuhui Shi. 2024. Automated Design of Metaheuristic Algorithms: A Survey. arXiv:2303.06532 [cs]
[62]
Qi Zhao, Bai Yan, Xianglong Chen, Taiwei Hu, Shi Cheng, and Yuhui Shi. 2023. AutoOpt: A General Framework for Automatically Designing Metaheuristic Optimization Algorithms with Diverse Structures. arXiv:2204.00998 [cs]
Index Terms
- GRAHF: A Hyper-Heuristic Framework for Evolving Heterogeneous Island Model Topologies
Recommendations
Analysis of evolutionary multi-tasking as an island model
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference CompanionRecently, an idea of evolutionary multi-tasking has been proposed and applied to various types of optimization problems. The basic idea of evolutionary multi-tasking is to simultaneously solve multiple optimization problems (i.e., tasks) in a ...
Island-based harmony search for optimization problems
Island model are embedded within framework of HS algorithm to build iHS.Island number ( I n ), migration frequency ( F m ), migration rate ( R m ) are iHS parameters.Higher values of I n and F m lead to better results but R m value needs to be ...
An empirical study into the structure of heuristic combinations in an evolutionary algorithm hyper-heuristic for the examination timetabling problem
SAICSIT '10: Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information TechnologistsA hyper-heuristic for the examination timetabling problem searches a space of constructive heuristic combinations instead of a space of examination timetables. The most optimal heuristic combination found by the search is used to construct the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1657 pages
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '24
Sponsor:
GECCO '24: Genetic and Evolutionary Computation Conference
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 69Total Downloads
- Downloads (Last 12 months)69
- Downloads (Last 6 weeks)19
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in