Authors: Scharnow, Jens
Tinnefeld, Karsten
Wegener, Ingo
Title: Fitness Landscapes Based on Sorting and Shortest Path Problems
Language (ISO): en
Abstract: The analysis of evolutionary algorithms is up to now limited to special classes of functions and fitness landscapes. It is not possible to describe those subproblems of NP-hard optimization problems where certain evolutionary algorithms work in polynomial time. Therefore, fitness landscapes based on important computer science problems as sorting and shortest paths problems are investigated here. Although it cannot be expected that evolutionary algorithms outperform the well-known problem specific algorithms on these simple problems, it is interesting to analyze how evolutionary algorithms work on these fitness landscapes which are based on practical problems. The following results are obtained: - Sorting is the maximization of "sortedness" which is measured by one of several well-known measures of presortedness. The different measures of presortedness lead to fitness landscapes of quite different difficulty for EAs. - Shortest paths problems are hard for all types of EA, if they are considered as single-objective optimization problems, while they are easy as multi-objective optimization problems.
Issue Date: 2002-04-08
Provenance: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
128.pdfDNB117.98 kBAdobe PDFView/Open

This item is protected by original copyright

Items in Eldorado are protected by copyright, with all rights reserved, unless otherwise indicated.