I have been looking at iterated local search and memetic algorithm recently. Both algorithms have some form of perturbations and apply a local search. It appears that pattern is present in both algorithm. So is an iterated local search a kind of memetic algorithm? Or a memetic algorithm a kind of iterated local search?
What is your opinion?
Many thanks in advanced for your contributions.
I think these methods have similar advanced characters. Sometimes, we may introduce some operators used in MA to ILS, such as store some solutions, and then get new solutions by crossover two parents.
Also the ILS has an evolutionary version, Evolutionary Local Search.
But strictly speaking, MA means the hybrid genetic algorithm, which incorporates the local search into the GA, according to the definition. So ILS is not a form of MA.
If you look at a memetic algorithm as a means of finding initial points from which to start a local optimization method, then it is indeed a form of iterated local search. There are of course other perspectives from which to consider memetic algorithms (e.g. population dynamics), but examining recombination from the perspective of a single solution can be very useful.
In the end, the goals of restarting a local optimization method are A) restart it from a point that will lead to a different local optimum, and B) try to select the restart point so that it will be better than random. Since many combinatorial optimization problems have been shown to be globally convex (i.e. the best local optima are clustered in a small region of the search space), restart points near good local optima are a promising place from which to find other good local optima.
An advantage of memetic algorithms is that a population of initial starting points makes it easier to do things like maintain search diversity and keep a memory of highly promising areas of the search space.
I think they are quite different. One is population based (the memetic algorithm) while the other is a trajectory based algorithm (keeps one solution at a time).
Besides the main motivation of ILS is, as I understand, trying to perform local search on the space of local minimum/maximum.
Although at the end you have a vector of real numbers that are changed in some ways (that is the essence of any metaheuristic), there several "flavours" of memetic algorithms so I do not see a clear relation between them and ILS
I think the only aspect in common is the use local search, but this is common with many other metaheuristics. The ILS is a simple local search method but powerful method with very few parameters that allows a fast adaptation to many different problems.
An metaheuristic should be evaluate by the following attributes: accuracy (quality of results), simplicity of design and implementation (including the avoidance of complex and time consuming fine-tuning processes), efficiency (relation between computational time employed and quality of results), robustness
(regarding changes in the inputs and constraints), and flexibility (the ability to deal
with general combinatorial optimization problems under different scenarios) (see Cordeau et al. (2002)). An certainly ILS has the previous attributes.
The perturbation phase is not just a more move of a more complex neighborhood, it should be careful design to take the search to another area of the space solutions without destroy in great scale the current solution. It can even be a type of matheuristic.
Also it should be considered the history of research in both area, ILS already exists before 90', where the work of David Johnson and Oliver Martin use the first algorithms (applied to TSP) and that are the base of the ILS. I recommend you to look on the two review works on ILS (see below).
So, I do not agree that ILS is a special case of memetic algorithms, ILS is an extension of local search algorithms.
Cordeau J.F., Gendreau M., Laporte G., Potvin J.Y. and Semet F., 2002. A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53, 512-522.
Lourenço H.R., Martin O. and Stützle T. (2010), Iterated Local Search: Framework and Applications. In Handbook of Metaheuristics, 2nd. Edition. Vol.146. M. Gendreau and J.Y. Potvin (eds.), Kluwer Academic Publishers, International Series in Operations Research & Management Science, pp. 363-397.
Lourenço H.R., Martin O. and Stützle T. (2003), Iterated Local Search. In Handbook of Metaheuristics, F. Glover and G. Kochenberger, (eds.), Kluwer Academic Publishers, International Series in Operations Research and Management Science, pp. 321-353.
I think this paper may helpful. >> Hybrid metaheuristics in combinatorial optimization: A survey
http://www.sciencedirect.com/science/article/pii/S1568494611000962
- Badges
- Science topic
- Similar topics
- Analytical Chemistry
- Extraction