Fitness Landscapes Based on Sorting and Shortest Path Problems

Scharnow, Jens; Tinnefeld, Karsten; Wegener, Ingo

Fitness Landscapes Based on Sorting and Shortest Path Problems

dc.contributor.author	Scharnow, Jens	de
dc.contributor.author	Tinnefeld, Karsten	de
dc.contributor.author	Wegener, Ingo	de
dc.date.accessioned	2004-12-07T08:21:05Z
dc.date.available	2004-12-07T08:21:05Z
dc.date.created	2002	de
dc.date.issued	2002-04-08	de
dc.description.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.	en
dc.format.extent	120808 bytes
dc.format.mimetype	application/pdf
dc.identifier.uri	http://hdl.handle.net/2003/5421
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-15262
dc.language.iso	en	de
dc.publisher	Universität Dortmund	de
dc.relation.ispartofseries	Reihe Computational Intelligence ; 128	de
dc.subject.ddc	004	de
dc.title	Fitness Landscapes Based on Sorting and Shortest Path Problems	en
dc.type	Text	de
dc.type.publicationtype	report
dcterms.accessRights	open access

Files

Original bundle

Now showing 1 - 1 of 1

Name:: 128.pdf
Size:: 117.98 KB
Format:: Adobe Portable Document Format
Description:: DNB

Download

Collections

Sonderforschungsbereich (SFB) 531