Authors: Sudholt, Dirk
Title: Local search in memetic algorithms
Other Titles: the Impact of the Local Search Frequency
Language (ISO): en
Abstract: Memetic algorithms are popular randomized search heuristics combining evolutionary algorithms and local search. Their efficiency has been demonstrated in countless applications covering a wide area of practical problems. However, theory of memetic algorithms is still in its infancy and there is a strong need for a rigorous theoretical foundation to better understand these heuristics. Here, we attack one of the fundamental issues in the design of memetic algorithms from a theoretical perspective, namely the choice of the frequency with which local search is applied. Since no guidelines are known for the choice of this parameter, we care about its impact on memetic algorithm performance. We present worst-case problems where the choice of the local search frequency has an enormous impact on the performance of a simple memetic algorithm. A rigorous theoretical analysis shows that on these problems, with overwhelming probability, even a small factor of 2 decides about polynomial versus exponential optimization times.
Issue Date: 2006-06
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
20806.pdfDNB251.78 kBAdobe PDFView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.