Autor(en): Scharnow, Jens
Tinnefeld, Karsten
Wegener, Ingo
Titel: Fitness Landscapes Based on Sorting and Shortest Path Problems
Sprache (ISO): en
Zusammenfassung: 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.
URI: http://hdl.handle.net/2003/5421
http://dx.doi.org/10.17877/DE290R-15262
Erscheinungsdatum: 2002-04-08
Provinienz: Universität Dortmund
Enthalten in den Sammlungen:Sonderforschungsbereich (SFB) 531

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
128.pdfDNB117.98 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org