Authors: Sudholt, Dirk
Title: Memetic algorithms with variable-depth search to overcome local optima
Language (ISO): en
Abstract: Variable-depth search (VDS) is well-known as Lin-Kernighan strategy for the TSP and Kernighan-Lin for graph partitioning. The basic idea is to make a sequence of local moves and to freeze all moved combinatorial objects to prevent the search from looping. VDS stops when no further local move is possible and returns a best found solution. We analyze memetic algorithms with VDS for three binary combinatorial problems: Mincut, Knapsack, and Maxsat. More precisely, we focus on simply structured problem instances containing local optima that are very hard to overcome. Many common trajectory-based algorithms fail to find a global optimum: the (1+1) EA, iterated local search, and simulated annealing need exponential time with high probability. However, memetic algorithms using VDS easily manage to find a global optimum in expected polynomial time. These results strengthen the usefulness of memetic algorithms with VDS from a theoretical perspective.
Issue Date: 2008-01
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
23808.pdfDNB242.88 kBAdobe PDFView/Open

This item is protected by original copyright

If no CC-License is given, pleas contact the the creator, if you want to use thre resource other than only read it.