Titelaufnahme

Titel
Enhancing a genetic algorithm by a complete solution archive based on a trie data structure / von Andrej Šramko
VerfasserŠramko, Andrej
Begutachter / BegutachterinRaidl, Günther R.
Erschienen2009
UmfangX, 97 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2009
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)archiv genetische algorithmen "ohne wiederbesuche"
Schlagwörter (EN)archive genetic algorithms non-revisiting
URNurn:nbn:at:at-ubtuw:1-27056 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Enhancing a genetic algorithm by a complete solution archive based on a trie data structure [1.63 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Genetische Algorithmen sind robuste Optimierungstechniken. Sie haben sich als effektiv für viele verschiedene Optimierungsprobleme erwiesen. Viele Teilverbesserungen wurden entwickelt um spezielle Probleme zu lösen. Es ist aber schwierig eine Technik, die allgemeiner angewandt werden kann, zu finden. Im Rahmen dieser Arbeit beschreibe ich einen Mechanismus, der die Fähigkeit der Genetischen Algorithmen eine bessere Lösung zu finden erhöhen sollte. Ein komplettes Archiv, das auf der Trie-Datenstruktur basiert, wird eingeführt.

Die Idee des Archivs ist alle besuchte Lösungen effizient zu speichern, Wiederbesuche vermeiden und ein gutes und intelligentes Verfahren zur Transformation bereits besuchter Lösungen auf ähnliche noch nicht besuchte Lösungen zu haben.

Der genetische Algorithmus kann als separates Modul, das Kandidatenlösungen generiert, gesehen werden. Jede generierte Lösung wird zum Trie weitergeleitet. Wenn der Trie die Lösung erhält, kontrolliert er, ob sie bereits im Archiv vorhanden ist. Falls nein, wird die Lösung einfach gespeichert. Falls ja, würde ein Wiederbesuch entstehen. Das Vermeiden von Wiederbesuchen kann auf verschiedene Art und Weise erreicht werden. Das Ziel ist eine ähnliche noch nicht besuchte Lösung zu erzeugen. Das Archiv unterstützt dies sehr gut. Nach diesem Prozess wird die ursprüngliche oder geänderte Lösung dem genetischen Algorithmus zurückgegeben.

Dieses Verfahren wurde auf drei Problemen implementiert und getestet:

das Royal Road Problem, NK Landscapes und das MAX-SAT Problem. Der standard genetische Algorithmus wird mit verschiedenen Varianten des neuen Verfahrens verglichen. Die Ergebnisse zeigen, dass in vielen Fällen das Archiv hilft die Qualität der Endlösungen zu verbessern, oder dass es die Anzahl der notwendigen Iterationen um die optimale Lösung zu finden reduziert.

Zusammenfassung (Englisch)

Genetic algorithms are robust optimization techniques that have proven to be effective for a large variety of optimization problems.

Many particular improvements have been designed to solve special problems. However, it is difficult to find techniques which can be used more generally. In this thesis, I describe a mechanism that should improve the ability to find a better solution for a larger spectrum of genetic algorithm applications. A complete solution archive based on a trie data structure is introduced.

The idea of the archive is to efficiently store all visited solutions, avoid revisits, and have a good and intelligent mechanism for transforming already visited solutions into similar unvisited ones.

The genetic algorithm can be seen as a separate module which generates solutions in a specific way. Every created solution is forwarded to the trie. As the trie accepts the solution, it checks whether it is already included in the archive. If the solution is not yet in the archive, it is simply inserted. On the other hand, when the solution is in the trie, a revisit would occur. Avoiding the revisit can be done in several ways; in general the aim is to derive a similar but yet unvisited solution, and the trie data structure supports this well. It is important to find a good balance between the quality of the changed solution and the effort needed to change it. After inserting or altering a solution, it is sent back to the genetic algorithm module and then handled as usual.

The approach has been implemented and tested on three problems; the Royal Road function, NK landscapes, and the MAX-SAT problem. The standard genetic algorithm is compared to the different variations of the new approach that use the archive. Results show that in many cases the archive contributes to the quality of the solutions, or reduces the number of iterations for finding optimal solutions.