Ir al contenido

Documat

Harnessing memetic algorithms: a practical guide

    1. [1] Universidad de Málaga

      Universidad de Málaga

      Málaga, España

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 327-356
  • Idioma: inglés
  • DOI: 10.1007/s11750-024-00694-8
  • Enlaces
  • Resumen

    • The aim of this work is to provide a didactic approximation to memetic algorithms (MAs) and how to apply these techniques to an optimization problem. MAs are based on the synergistic combination of ideas from population-based metaheuristics and trajectory-based search/optimization techniques. Most commonly, MAs feature a population-based algorithm as the underlying search engine, endowing it with problem-specific components for exploring the search space, and in particular with local-search mechanisms. In this work, we describe the design of the different elements of the MA to fit the problem under consideration, and go on to perform a detailed case study on a constrained combinatorial optimization problem related to aircraft landing scheduling. An outline of some advanced topics and research directions is also provided.

  • Referencias bibliográficas
    • Aickelin U (2002) An indirect genetic algorithm for set covering problems. Journal of the Operational Research Society 53(10):1118–1126
    • Alba E, Cotta C (2005) Evolutionary algorithms. In: Olariu S, Zomaya AY (Eds)., Chapman and Hall/CRC
    • Al-Dulaimy A, Jansen M, Johansson B, Trivedi A, Iosup A, Ashjaei M, Papadopoulos AV (2024) The computing continuum: From IoT to the cloud....
    • Altenberg L (1995) The Schema Theorem and Price’s Theorem. Foundations of Genetic Algorithms, Vol. 3, pp. 23–49. Elsevier
    • Amaya JE, Cotta C, Fernández-Leiva AJ, García-Sánchez P (2020) Deep memetic models for combinatorial optimization problems: application to...
    • Armbrust M, Fox A, Griffith R, Joseph AD, Katz R, Konwinski A, Zaharia M (2010) A view of cloud computing. Commun ACM 53(4):50–58
    • Beasley JE, Krishnamoorthy M, Sharaiha YM, Abramson D (2000) Scheduling Aircraft Landings-The Static Case. Transp Sci 34(2):180–197
    • Bennell JA, Mesgarpour M, Potts CN (2011) Airport runway scheduling. 4OR – A Quarterly Journal of Operations Research 9(2):115–138
    • Bernardino EM, Bernardino AM, Sánchez-Pérez JM, Gómez-Pulido JA, Vega-Rodríguez MA (2008) A genetic algorithm with multiple operators for...
    • Blum C, Blesa Aguilera MJ, Roli A, Sampels M (2008) Hybrid metaheuristics: An emerging approach to optimization, vol 144. Springer, Berlin...
    • Blum C, Cotta C, Fernández AJ, Gallardo JE, Mastrolilli M (2008) Hybridizations of metaheuristics with branch & bound derivates. In: Blum...
    • Blum C, Puchinger J, Raidl GR, Roli A (2011) Hybrid metaheuristics in combinatorial optimization: A survey. Appl Soft Comput 11(6):4135–4151
    • Blum C, Roli A (2003) Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Comput Surv 35(3):268–308
    • Bonyadi MR, Michalewicz Z (2017) Particle Swarm Optimization for Single Objective Continuous Space Problems: A Review. Evol Comput 25(1):1–54
    • Boudia M, Louly M, Prins C (2007) A reactive GRASP and path relinking for a combined production-distribution problem. Computers & Operations...
    • Bäck T (1996) Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming. Oxford University Press, Genetic...
    • Camacho D, Lara-Cabrera R, Merelo-Guervós J, Castillo PA, Cotta C, Fernández-Leiva AJ, Chávez F (2018) From ephemeral computing to deep bioinspired...
    • Campelo F, Aranha C (2023) Lessons from the Evolutionary Computation Bestiary. Artif Life 29(4):421–432
    • Caraffini F, Neri F, Picinali L (2014) An analysis on separability for memetic computing automatic design. Inf Sci 265:1–22
    • Chen X, Ong Y-S, Lim M-H, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans Evol Comput 15(5):591–607
    • Cheng V, Crawford L, Menon P (1999) Air traffic control using genetic search techniques. Proceedings of the 1999 IEEE International Conference...
    • Constantino OH, Segura C (2022) A parallel memetic algorithm with explicit management of diversity for the job shop scheduling problem. Appl...
    • Cotta C (2003) Protein structure prediction using evolutionary algorithms hybridized with backtracking. In: Mira J, Álvarez J (Eds.), Artificial...
    • Cotta C (2005) Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In: Mira J, Álvarez J (Eds.), Artificial...
    • Cotta C, Fernández A (2004) A hybrid GRASP - evolutionary algorithm approach to golomb ruler search. In: Yao X et al.(Eds.), Parallel problem...
    • Cotta C, Leiva AJF, Gallardo JE (2012) Memetic algorithms and complete techniques. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic...
    • Cotta C, Mathieson L, Moscato P (2018) Memetic Algorithms. In: Martí R, Pardalos PM, Resende MGC (eds) Handbook of Heuristics. Springer International...
    • Cotta C, Moscato P (2003) The k-Feature Set problem is W[2]-complete. Journal of Computer and Systems Science 67(4):686–690
    • Cotta C, Moscato P (2004) Evolutionary computation: Challenges and duties. In: Menon A (ed) Frontiers of evolutionary computation. Kluwer...
    • Cotta C, Neri F (2012) Memetic algorithms in continuous optimization. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic algorithms,...
    • Cotta C, Troya J (1998) Genetic forma recombination in permutation flowshop problems. Evol Comput 6(1):25–44
    • Das S, Mullick SS, Suganthan P (2016) Recent advances in differential evolution - an updated survey. Swarm Evol Comput 27:1–30
    • Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold Computer Library, New York
    • Dawkins R (1976) The selfish gene. Clarendon Press, Oxford
    • Dorronsoro B, Alba E (2008) Cellular genetic algorithms, Vol. 42. New York, NY: Springer. (Operations Research/Computer Science Interfaces...
    • Eiben AE (2003) Multiparent Recombination in Evolutionary Computing. In: Rozenberg G et al (eds) Advances in Evolutionary Computing. Springer,...
    • Elsayed SM, Sarker RA, Essam DL (2011) Multi-operator based evolutionary algorithms for solving constrained optimization problems. Computers...
    • Eremeev AV (2008) On complexity of optimal recombination for binary representations of solutions. Evol Comput 16(1):127–147
    • Eremeev AV (2011) On complexity of the optimal recombination for the travelling salesman problem. 11th European Conference on Evolutionary...
    • Farhadi F (2016) Heuristics and meta-heuristics for runway scheduling problems. In: Rabadi G (ed) Heuristics, Metaheuristics and Approximate...
    • Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8(2):67–71
    • Freisleben B, Merz P (1996) A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. 1996 IEEE International...
    • Gallardo JE, Cotta C (2015) A GRASP-based memetic algorithm with path relinking for the far from most string problem. Eng Appl Artif Intell...
    • Gallardo JE, Cotta C, Fernández AJ (2006) A memetic algorithm with bucket elimination for the still life problem. In: Gottlieb J, Raidl G...
    • Gallardo JE, Cotta C, Fernandez AJ (2007) On the Hybridization of Memetic Algorithms With Branch-and-Bound Techniques. IEEE Transactions on...
    • Gallardo JE, Cotta C, Fernández AJ (2009) Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms. Journal...
    • García Sánchez P, González J, Castillo PA, Arenas MG, Merelo Guervós JJ (2013) Service oriented evolutionary algorithms. Soft Comput 17:1059–1075
    • Gendreau M, Potvin J-Y (Eds.) (2019) Handbook of Metaheuristics, Vol. 272. Cham: Springer International Publishing. (International Series...
    • Glover F, Campos V, Martì R (2021) Tabu search tutorial. A graph drawing application. TOP 29:319–350
    • Gonçalves J, Resende M (2018) Random-key genetic algorithms. In: Martí R, Pardalos PM, Resende MGC (eds) Handbook of Heuristics. Springer...
    • Grefenstette JJ (1992) Genetic algorithms for changing environments. In: Männer R, Manderick B (eds) Parallel Problem Solving from Nature...
    • Gulisano V, Medvet E (2024) Evolutionary computation meets stream processing. In: Smith S, Correia J, Cintrano C (eds) Applications of evolutionary...
    • Hansen JV (2004) Genetic search methods in air traffic control. Computers & Operations Research 31(3):445–459
    • Hansen P, Mladenović N (2001) Variable neighborhood search: Principles and applications. Eur J Oper Res 130(3):449–467
    • Hao J (2012) Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic algorithms, vol 379. Springer,...
    • Holm S (1979) A Simple Sequentially Rejective Multiple Test Procedure. Scand J Stat 6(2):66–70
    • Hong T-P, Wang H-S, Chen W-C (2000) Simultaneously applying multiple mutation operators in genetic algorithms. Journal of Heuristics 6(4):439–455
    • Houck C, Joines J, Kay M, Wilson J (1997) Empirical investigation of the benefits of partial lamarckianism. Evol Comput 5(1):31–60
    • Hutter F, Hoos H, Leyton-Brown K, Stützle T (2009) ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence...
    • Ikli S, Mancel C, Mongeau M, Olive X, Rachelson E (2021) The aircraft runway scheduling problem: A survey. Computers & Operations Research...
    • Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation...
    • Jaszkiewicz A, Ishibuchi H, Zhang Q (2012) Multiobjective memetic algorithms. In: Neri F, Cotta C, Moscato P (eds) Handbook of Memetic Algorithms,...
    • Julstrom BA (1995) Very greedy crossover in a genetic algorithm for the traveling salesman problem. Proceedings of the 1995 ACM Symposium...
    • Koziel S, Michalewicz Z (1998) A decoder-based evolutionary algorithm for constrained parameter optimization problems. In: Goos G et al. (Eds.),...
    • Krasnogor N, Blackburne B, Burke E, Hirst J (2002) Multimeme algorithms for protein structure prediction. In: Merelo JJ et al. (Eds.), Parallel...
    • Krasnogor N, Smith J (2005) A tutorial for competent memetic algorithms: Model, taxonomy, and design issues. IEEE Trans Evol Comput 9(5):474–488
    • Krasnogor N, Smith J (2008) Memetic algorithms: The polynomial local search complexity theory perspective. Journal of Mathematical Modelling...
    • LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436–444
    • Liaw C-F (2000) A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research 124:28–42
    • Lindauer M, Eggensperger K, Feurer M, Biedenkapp A, Deng D, Benjamins C, Hutter F (2022) SMAC3: A versatile bayesian optimization package...
    • Liu Y-H (2011) A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem....
    • López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L, Birattari M, Stützle T (2016) The irace package: Iterated racing for automatic algorithm...
    • Malan KM (2021) A Survey of Advances in Landscape Analysis for Optimisation. Algorithms 14(2):40
    • Martí R, Corberán A, Peiró J (2018) Scatter Search. In: Martí R, Pardalos PM, Resende MGC (eds) Handbook of Heuristics. Springer International...
    • Martí R, Pardalos PM, Resende MGC (eds) (2018) Handbook of Heuristics. Springer International Publishing, Cham
    • Meri K, Arenas MG, Mora AM, Merelo JJ, Castillo PA, Sánchez PG, Laredo JLJ (2013) Cloud-based evolutionary algorithms: An algorithmic study....
    • Merz P (2012) Memetic algorithms and fitness landscapes in combinatorial optimization. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic...
    • Molina D, Lozano M, García-Martínez C, Herrera F (2010) Memetic algorithms for continuous optimisation based on local search chains. Evol...
    • Molina D, Lozano M, Sánchez AM, Herrera F (2011) Memetic algorithms based on local search chains for large scale continuous optimisation problems:...
    • Montes de Oca MA, Cotta C, Neri F (2012) Local search. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic algorithms, vol 379. Springer,...
    • Moscato P (1989) On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms (Tech. Rep. Nos. Caltech...
    • Moscato P (1999) Memetic algorithms: A short introduction. In: Corne D, Dorigo M, Glover F (eds) New ideas in optimization. McGraw-Hill, pp...
    • Moscato P (2012) Memetic algorithms: The untold story. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic algorithms, vol 379. Springer,...
    • Moscato P, Cotta C (2007) Memetic algorithms. In: Gonzalez TF (ed) Handbook of Approximation Algorithms and Metaheuristics (chap. 27). Chapman...
    • Moscato P, Cotta C (2019) An Accelerated Introduction to Memetic Algorithms. In: Gendreau M, Potvin JY (eds) Handbook of Metaheuristics, vol...
    • Moscato P, Norman MG (1992) A Memetic Approach for the Traveling Salesman Problem Implementation of a Computational Ecology for Combinatorial...
    • Nagata Y (2004) Criteria for designing crossovers for TSP. Proceedings of the 2004 congress on evolutionary computation, Vol. 2, pp. 1465–1472....
    • Nagata Y, Kobayashi S (1997) Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. In: Bäck T (ed) Seventh...
    • Neri F (2012) Diversity management in memetic algorithms. In: Neri F, Cotta C, Moscato P (eds) Handbook of memetic algorithms, vol 379. Springer,...
    • Neri F, Cotta C (2012) Memetic algorithms and memetic computing optimization: A literature review. Swarm Evol Comput 2:1–14
    • Neri F, Cotta C, Moscato P (Eds.) (2012) Handbook of Memetic Algorithms, Vol. 379. Berlin, Heidelberg: Springer Berlin Heidelberg. (Studies...
    • Neri F, Tirronen V (2008) On memetic differential evolution frameworks: A study of advantages and limitations in hybridization. Proceedings...
    • Niu D, Liu B, Yin M, Zhou Y (2023) A new local search algorithm with greedy crossover restart for the dominating tree problem. Expert Syst...
    • Norman M, Moscato P (1989) A competitive and cooperative approach to complex combinatorial search (Tech. Rep. Nos. Caltech Concurrent Computation...
    • Ochoa G, Chicano F, Tinós R, Whitley D (2015) Tunnelling crossover networks. Proceedings of the 2015 annual conference on genetic and evolutionary...
    • Ochoa G, Verel S, Daolio F, Tomassini M (2014) Local optima networks: A new model of combinatorial fitness landscapes. In: Richter H, Engelbrecht...
    • Ong Y-S, Keane A (2004) Meta-lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2):99–110
    • Ong Y-S, Lim M-H, Chen X (2010) Memetic computation—past, present and future. IEEE Comput Intell Mag 5(2):24–31
    • Ong Y-S, Lim M-H, Zhu N, Wong K-W (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern B...
    • Papazoglou MP, van den Heuvel WJ (2007) Service oriented architectures: approaches, technologies and research issues. VLDB J 16:389–415
    • Parejo J (2016) MOSES: A metaheuristic optimization software ecosystem. AI Commun 29(1):223–225
    • Petalas Y, Parsopoulos K, Vrahatis M (2007) Memetic particle swarm optimization. Ann Oper Res 156:99–127
    • Pošík P (2010) Stochastic local search in continuous domains: questions to be answered when designing a novel algorithm. Proceedings of the...
    • Prais M, Ribeiro CC (2000) Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J Comput 12(3):164–176
    • Qu X, Ong Y-S, Hou Y, Shen X (2019) Memetic evolution strategy for reinforcement learning. IEEE congress on evolutionary computation, (CEC)...
    • Quade D (1979) Using Weighted Rankings in the Analysis of Complete Blocks with Additive Block Effects. J Am Stat Assoc 74(367):680–683
    • Rabadi G (Ed.) (2016) Heuristics, Metaheuristics and Approximate Methods in Planning and Scheduling (1st ed.) (No. 236). Cham: Springer
    • Radcliffe N (1994) The algebra of genetic algorithms. Ann Math Artif Intell 10:339–384
    • Radcliffe N, Surry P (1994) Fitness Variance of Formae and Performance Prediction. In: Whitley L, Vose M (eds) 3rd workshop on foundations...
    • Radcliffe NJ, Surry PD (1994) Formal memetic algorithms. In: Fogarty TC (ed) AISB workshop on evolutionary computing, vol 865. Springer. (Lecture...
    • Raidl GR (2006) A unified view on hybrid metaheuristics. In: Almeida F et al (eds) Hybrid metaheuristics, vol 4030. Springer, Berlin Heidelberg,...
    • Resende MGC (2012) Biased random-key genetic algorithms with applications in telecommunications. TOP 20:130–153
    • Resende MGC, Ribeiro CC (2019) Greedy randomized adaptive search procedures: Advances and extensions. In: Gendreau M, Potvin J-Y (eds) Handbook...
    • Rothlauf F (2019) Representations for evolutionary algorithms. Proceedings of the Genetic and Evolutionary Computation Conference Companion,...
    • Rudolph G (2012) Evolutionary strategies. In: Rozenberg G, Bäck T, Kok JN (eds) Handbook of natural computing. Springer, Berlin Heidelberg,...
    • Salehipour A, Modarres M, Moslemi Naeni L (2013) An efficient hybrid meta-heuristic for aircraft landing problem. Computers & Operations...
    • Smith JE (2012) Self-adaptative and coevolving memetic algorithms. In: Neri F, Cotta C, Moscato P (eds), Handbook of Memetic Algorithms (vol....
    • Soykan B, Rabadi G (2016) A tabu search algorithm for the multiple runway aircraft scheduling problem. In: Rabadi G (ed) Heuristics, Metaheuristics...
    • Stützle T, López-Ibáñez M, Pérez-Cáceres L (2022) Automated algorithm configuration and design. Proceedings of the genetic and evolutionary...
    • Sudholt D (2009) The impact of parametrization in memetic evolutionary algorithms. Theoret Comput Sci 410(26):2511–2528
    • Sudholt D (2012) Parametrization and balancing local and global search. In: Neri F, Cotta C, Moscato P (eds), Handbook of Memetic Algorithms...
    • Sörensen K (2015) Metaheuristics–the metaphor exposed. Int Trans Oper Res 22(1):3–18
    • Tomassini M (2005) Spatially structured evolutionary algorithms. Berlin, Heidelberg: Springer-Verlag. (Natural Computing Series)
    • Wang Z, Leung M, Che H, Coello Coello C (2023) Thematic issue on advances in analysis and application of multi-objective memetic optimization...
    • Whitley D, Hains D, Howe A (2010) A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover. In:...
    • Whitley LD, Rowe JE (2011) A “no free lunch” tutorial: Sharpened and focused no free lunch. In: Auger A, Doerr B (eds) Theory of randomized...
    • Wolpert D, Macready W (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67– 82
    • Wolpert DH (2021) What Is Important About the No Free Lunch Theorems? In: Pardalos PM, Rasskazova V, Vrahatis MN (Eds.), Black Box Optimization,...
    • Zhou A, Qu B-Y, Li H, Zhao S-Z, Suganthan PN, Zhang Q (2011) Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm...
    • Zulkifli A, Ab Aziz NA, Ibrahim Z, Mokhtar N (2018) Review on computational techniques in solving aircraft landing problem. In: Jia Y, Ito...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno