Memetic algorithm. It is a population of agents that alternate periods of self-improvement (through local search) with periods of cooperation and competition (through selection)
Summary
[ hide ]
- 1 Definition
- 1 Memetic algorithm
- 2 Representatives
- 3 Exploration Mechanisms
- 2 Sources
Definition
Given the wide development obtained by traditional meta-heuristic and heuristic methods, these can be subdivided into two large groups, with very distinctive characteristics, on the one hand there are the mechanisms of exploitation of the solutions or methods of Local Search (BL) and on the other the mechanisms for exploring solutions or Population Algorithms.
The former quickly achieve precise solutions in the vicinity of the starting point, possessing a great tendency to get caught in local optimum and not the global optimum, which is the best solution within the search space. Furthermore, these mechanisms are highly dependent on the initial point, being some of their representatives.
Memetic algorithm
The objective of the memetic algorithms is to make both components: Local Search and Population Algorithm work cooperatively to achieve a synergy between the two that allows improving the search process. Many have been the designs of memetic algorithms raised.
Some of the proposals are mentioned below:
- The GLS Based Memetic Algorithm proposed in (Holstein and Moscato, 1999).
- Genetic Local Search (Aarts and Verhoeven, 1997) to solve business traveler problems.
- The memetic algorithm with local search based on the Crossover Operator (AMCR) (Molina Cabrera, 2007).
- Hybridmulti-colony algorithm (ACOR) (Herrera et al., 2009 ).
Representatives
- The Descent / Ascent methods( Luenberguer , 1984 )
- The Quasi-Newton methods(Luenberguer, 1984)
- The methods of the gradient(Luenberguer, 1984)
- The Nelder and Mead Simplex method(Nelder and Mead, 1965 )
- The Solis West(Solis and West, 1981 )
- The Taboo Search( Glover and Laguna , 1997 ),
- The Simulated Annealing(Kirkpatrick et al., 1983 ),
- The Local Guided Search(Voudouris and Tsang, 1995 ), etc.
Exploration Mechanisms
On the other hand, the mechanisms for exploring solutions have great independence from the nature of the solution space, being able to traverse the search space with multiple local maximums or minimums and reaching a global solution, but at the same time they have drawbacks to reach precise solutions quickly. they do not take advantage of the local characteristics of the search space.
Some examples are:
- The Genetic Algorithms(AGs) (Goldberg, 1998 )
- The Scattered Search(Laguna and Martí, 2003 )
- The Differential Evolution(Storn and Price, 1997 )
- Algorithms Based on Estimation of Distributions(Lozano et al., 2006 )
- The optimization based on ant colonies(Dorigo and Caro, 1999 )
- Particle Systems(Kennedy and Eberhart, 1995 )
- The Optimization Based on Mallas Variables(VMO) (Puris, 2009 )
Given these two criteria (exploration and exploitation), it has been shown that the combined use of these has beneficial properties during the search process, since the incorporation of Local Search allows addressing the need for precision throughout the process, unlike a Population algorithm in which fine-tuning of solutions only occurs in the final stages. In recent years, algorithms have been developed that seek to address the search problem (global search but with the ability to reach precise solutions quickly, taking advantage of the advantages of local search).
Numerous names have been for this type of models that combine both approaches: Algorithms Hybrid , Genetic Algorithms premises , etc. (Moscato, 1999 ) uses the term Memetic Algorithms to name these procedures, as well as the following description of them: