Memory-Based Memetic Algorithms
Marco Wiering · Utrecht University Repository (Utrecht University) · 2004
Memetic algorithms combine genetic algorithms with local search; each time a new individual is generated by the genetic algorithm, a simple local search procedure brings it (closer) to a local maximum.Although memetic algorithms have been shown to work well for particular combinatorial optimization problems, they may sometimes suffer from early convergence to a local maximum.This paper describes (steady-state) memory-based memetic algorithms, which search more efficiently by increasing the diversity of the population.Each time a new individual is created, it is brought to its local maximum using local search, and then the algorithm checks whether the individual has already been found before.If that is the case, the lowest possible fitness value is assigned, so that the individual will be replaced during the next iteration.The experiments compare memory-based memetic algorithms to memetic algorithms, genetic algorithms and multiplerestart local search on deceptive problems.The results indicate that the memory-based memetic algorithm finds the global optimum much more often than the normal memetic algorithm, and performs about the same as genetic algorithms on the chosen test problems which are very difficult for conventional local search algorithms.