Article ID: | iaor20072022 |
Country: | United Kingdom |
Volume: | 33 |
Issue: | 5 |
Start Page Number: | 1214 |
End Page Number: | 1225 |
Publication Date: | May 2006 |
Journal: | Computers and Operations Research |
Authors: | Sevaux Marc, Srensen Kenneth |
Keywords: | memetic algorithm |
A new metaheuristic for (combinatorial) optimization is presented: memetic algorithms with population management or MA|PM. An MA|PM is a memetic algorithm, that combines local search and crossover operators, but its main distinguishing feature is the use of distance measures for population management. Population management strategies can be developed to dynamically control the diversity of a small population of high-quality individuals, thereby avoiding slow or premature convergence, and achieve excellent performance on hard combinatorial optimization problems. The new algorithm is tested on two problems: the multidimensional knapsack problem and the weighted tardiness single-machine scheduling problem. On both problems, population management is shown to be able to improve the performance of a similar memetic algorithm without population management.