Full metadata record
DC FieldValueLanguage
dc.contributor.authorJansen, Thomasde
dc.date.accessioned2004-12-06T12:50:18Z-
dc.date.available2004-12-06T12:50:18Z-
dc.date.created2000de
dc.date.issued2000-10-16de
dc.identifier.urihttp://hdl.handle.net/2003/2537-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-1190-
dc.description.abstractEvolutionäre Algorithmen sind allgemeine, randomisierte Suchverfahren, die in verschiedenen Bereichen erfolgreich eingesetzt werden. Ein wichtiges und typisches Anwendungsgebiet ist die Optimierung. In dieser Arbeit werden evolutionäre Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumen, konkret bei der Maximierung pseudo-boolescher Funktionen, theoretisch analysiert. Dabei werden vor allem einfache evolutionäre Algorithmen auf konkreten, typischen Zielfunktionen oder Klassen von Zielfunktionen bezüglich ihrer Effizienz untersucht. Als Maße der Effizienz dienen dabei die erwartete Laufzeit und die Wahrscheinlichkeit pt, mit der nach t Zielfunktionsauswertungen ein globales Maximum erreicht wird. Die Analyse beginnt nach einer allgemeinen Einführung, in der Grenzen und Möglichkeiten evolutionärer Algorithmen sehr grundsätzlich diskutiert werden, mit dem vielleicht einfachsten evolutionären Algorithmus, dem (1+1) EA. Wesentliche Ergebnisse sind vor allem die asymptotisch exakte Bestimmung der erwarteten Laufzeit für die Klasse der linearen Funktionen und eine exponentielle untere Schranke für eine unimodale Funktion. Ausgehend von diesem sehr einfachen Algorithmus wird das weite Feld evolutionärer Algorithmen erschlossen mittels Analyse von Variationen des (1+1) EA. Variationen der Mutation führen zur Diskussion der Wahl des Mutationswahrscheinlichkeit und motivieren den Entwurf eines einfachen evolutionären Algorithmus mit dynamischer Parametersteuerung, für den die erwartete Laufzeit auf einer Reihe von Funktionen bestimmt wird. Variationen der Selektion führen unter anderem zur Analyse des Metropolis-Algorithmus von Simulated Annealing. Schließlich wird die Analyse ausgedehnt auf "richtige" evolutionäre Algorithmen: für einen speziellen Steady State GA wird auf einer bestimmten Funktionenfamilie nachgewiesen, dass er mutationsbasierte Algorithmen bei weitem schlägt. Neben den konkreten Ergebnissen ist besonders die Bereitstellung verschiedener Methoden, mit denen sowohl obere als auch untere Schranken für die erwartete Laufzeit eines evolutionären Algorithmus bestimmt werden können, wichtig.de
dc.language.isodede
dc.publisherUniversität Dortmundde
dc.subject(1+1) EAde
dc.subjectEvolutionäre Algorithmende
dc.subjectFitnesslandschaftende
dc.subjectMutationde
dc.subjectOptimierungde
dc.subjectRekombinationde
dc.subjectSimulationde
dc.subject.ddc004de
dc.titleTheoretische Analyse evolutionärer Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumende
dc.typeTextde
dc.date.accepted2000-10-09de
dc.type.publicationtypedoctoralThesisen
dcterms.accessRightsopen access-
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen

Files in This Item:
File Description SizeFormat 
diss.ps1.84 MBPostscriptView/Open
jansen.pdfDNB1.25 MBAdobe PDFView/Open


This item is protected by original copyright



This item is protected by original copyright rightsstatements.org