Enhancing a genetic algorithm by a complete solution archive based on a trie data structure
Andrej Šramko · reposiTUm (TU Wien) · 2009
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.