Loading...
Please wait, while we are loading the content...
Similar Documents
Memetic algorithms for combinatorial optimization problems : fitness landscapes and effective search strategies
| Content Provider | Semantic Scholar |
|---|---|
| Author | Merz, Peter |
| Copyright Year | 2006 |
| Abstract | For many combinatorial optimization problems, no effective algorithms capable of finding guaranteed optimum solutions in short time are available. Therefore, powerful heuristics have been developed that deliver no guarantee to find the optimum, but have shown to be highly effective in many test cases. In this work, a special class of heuristics is investigated. The algorithms under consideration are called memetic algorithms, which are – roughly speaking – hybrids of evolutionary algorithms and problem-specific search algorithms, such as greedy heuristics and local search. In order to provide explanations under which circumstances these memetic algorithms are highly effective, a search space analysis relying on the concept of fitness landscapes is conducted, consisting of an autocorrelation analysis and a fitness distance correlation analysis of the peaks in the fitness landscape. It is shown that the former type of analysis enables a comparison and thus a selection of local search algorithms, while the latter type of analysis provides a guideline for the choice of evolutionary variation operators in the evolutionary meta-algorithm. The search space analysis is conducted for five combinatorial optimization problems, namely the traveling salesman problem, the graph bipartitioning problem, the quadratic assignment problem, NK landscapes, and the unconstrained binary quadratic programming problem. Based on the results of the analysis, new memetic algorithms are presented. Experimental results demonstrate that they are among the best heuristics developed so far for the five problems. Fur viele kombinatorische Optimierungsprobleme sind keine effektiven Algorithmen bekannt, die garantiert optimale Losungen in kurzer Zeit liefern. Daher sind leistungsfahige Heuristiken entwickelt worden, die zwar keine Garantie bieten, das ein Optimum gefunden wird, sich aber in der Praxis als auserst effektiv erwiesen haben. In der vorliegenden Arbeit wird eine bestimmte Klasse von Heuristiken untersucht. Die betrachteten Algorithmen werden memetische Algorithmen genannt und konnen vereinfacht als hybride Verfahren aus evolutionaren Algorithmen und problemspezifischen Heuristiken, wie Greedy-Heuristiken und lokale Suche aufgefast werden. Um erklaren zu konnen, unter welchen Bedingungen diese memetischen Algorithmen effektiv sind, ist eine Suchraumanalyse basierend auf dem Konzept der Fitneslandschaften durchgefuhrt worden, die aus einer Autokorrelationsanalyse und einer Fitnes-Distanz-Korrelationsanalyse der Gebirgsspitzen der Fitneslandschaften besteht. Es wird gezeigt, das die erstgenannte Analysemethode einen Vergleich und somit eine Auswahl von lokalen Suchverfahren erlaubt, wahrend die letztgenannte Analysemethode eine Richtlinie fur die Wahl der Variationsoperatoren im evolutionaren Meta-Algorithmus liefert. Die Suchraumanalyse wurde auf funf kombinatorische Optimierungsprobleme angewandt, dem Problem des Handlungsreisenden, dem Problem der Graph-Zerlegung, dem quadratischen Zuweisungsproblem, dem NK-Modell, und dem binaren quadratischen Optimierungsproblem. Basierend auf den Analyseergebnissen wurden neue memetische Algorithmen entwickelt, und es wurde experimentell gezeigt, das diese Algorithmen zu den besten bisher veroffentlichten Heuristiken fur die funf Probleme zahlen. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.ub.uni-siegen.de/pub/diss/fb12/2001/merz/merz.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
