Memetic algorithms with variable-depth search to overcome local optima

dc.contributor.author	Sudholt, Dirk	de
dc.date.accessioned	2009-05-12T16:01:39Z
dc.date.available	2009-05-12T16:01:39Z
dc.date.issued	2008-01	de
dc.description.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.	en
dc.identifier.uri	http://hdl.handle.net/2003/26145
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9025
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 238-08	de
dc.subject.ddc	004	de
dc.title	Memetic algorithms with variable-depth search to overcome local optima	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Now showing 1 - 1 of 1