A Scalability Study of Evolutionary Algorithms for Clustering

Evolutionäre Algorithmen (EA) sind Optimierungswerkzeuge, welche auf Darwins Evolutionstheorie und Mendels Genetik basieren. In ihrer über 30-jährigen Geschichte, haben sie sich einen Ruf als gute Löser für schwere Probleme erarbeitet. Diese Diplomarbeit betrachtet die Skalierbarkeit von EAs und ihre Anwendbarkeit auf große Probleme.
Literatur zu diesem Thema wird in vier Gruppen vorgestellt:
* Ansätze zur Verbesserung allgemein anwendbarer EAs, welche auf einer Hypothese über die den EAs zu Grunde liegende Theorie basieren (Building Block Hypothese);
* parallele EAs, welche die Ausführungszeit unter Einsatz zusätzlicher Hardware verbessern;
* EAs die problemspezifische Operatoren verwenden; und
* mehrstufige Systeme, welche EA beinhalten.
Die Ansätze der ersten beiden Gruppen haben flexible Algorithmen zum Ziel, welche leicht auf eine Vielzahl von Problemen angewendet werden können. Die beiden letztgenannten Ansätze opfern diese Flexibilität zu Gunsten verbesserter Performanz auf einem spezifischen Problembereich.
Diese Arbeit untersucht experimentell die Skalierbarkeit von evolutionären Clustering-Algorithmen. Clustering Probleme sind allgemein und auch speziell zur Untersuchung von EAs von Interesse. ... mehrDer allgemeine Reiz von Clustering liegt in der verbreiteten Anwendung in vielen Wissenschaftsbereichen; das Clustering Problem ist nicht nur auf die Informatik beschränkt. Diese Arbeit betrachtet Clustering basierend auf paarweisen Ähnlichkeiten, welches die allgemeinste Modellierung des Problems ist. Für die Analyse von EAs ist Clustering auf Grund der verwendeten Repräsentation von Lösungskandidaten interessant. Die gewählte Kodierung führt zu einer hohen Abhängigkeit zwischen vielen Variablen innerhalb eines Lösungskandidaten; dies erhöht die Schwierigkeit des Problems für EAs.
Zur experimentellen Skalierbarkeitsanalyse sind skalierbare Testdaten notwendig, welche als dünn-besetzte paarweise Ähnlichkeitsmatritzen erstellt werden. Ein einfacher EA, welcher als Referenz eingeführt wird, zeigt schlechte Skalierbarkeitseigenschaften für diese Probleme. Mit wachsender Problemgröße nimmt die Laufzeit schneller als quadratisch zu. Schon für ein Problem mit 2.000 Objekten beträgt die durchschnittliche Laufzeit bis zum Erreichen zufriedenstellender Lösungen über 20 Minuten. Dadurch ist der Referenzalgorithmus für große Probleme nicht geeignet.
Verschiedene Erweiterungen des Referenzalgorithmus werden vorgeschlagen. Diese integrieren problemspezifisches Wissen in Form von speziellen Rekombinationsoperatoren und durch die Hybridisierung mit Cluster-Heuristiken. Insgesamt ergeben sich durch Kombinationen der vorgeschlagenen Operatoren 126 verschiedene Algorithmenkonfigurationen, welche für Probleme mit bis zu 2.000 Objekten getestet werden. Als Ergebnis der Experimente lässt sich feststellen, dass eine intelligente Initialisierung alleine, ohne Hybridisierung und mit Standard-Rekombinationsoperatoren, keine verbesserte Skalierbarkeit erreichen kann. Es finden sich aber Algorithmen, welche durch Cluster-basierte Rekombination oder durch die Hybridisierung mit einem hill-climbing Algorithmus. So ist es möglich, Probleme mit 2.000 Objekten durchschnittlich in unter drei Sekunden zu lösen. Es werden Laufzeiten erreicht, die fast linear mit der Problemgröße skalieren. Probleme mit bis zu 100.000 Objekten werden mit einer durchschnittlichen Laufzeit von deutlich unter 1.000 Sekunden gelöst.
Die Algorithmuskonfigurationen die mit guter Performanz gemessen wurden, werden im nächsten Schritt erweitert. Die Verbesserungen basieren auf bekannten zweistufigen Clustering EAs. Die vorgeschlagenen Verfahren clustern in der ersten Stufe ein größenreduziertes Problem mit einem EA. Anschließend wird die berechnete Population verwendet, um den EA der zweiten Stufe zu initialisieren, welcher dann auf dem original Problem arbeitet. Zur Größenreduktion werden zwei Möglichkeiten vorgeschlagen: die Komprimierung des Suchraums durch das Zusammenfassen von Objekten zu Objektgruppen und das Zerlegen des Problems in mehrere kleinere Probleme, welche unabhängig voneinander in der ersten Stufe bearbeitet werden. Die experimentelle Auswertung zeigt, dass der Ansatz mit Objektgruppen Potential zur weiteren Reduzierung der Laufzeit hat, während das Zerlegen des Problems die Laufzeit nicht weiter verbessert. Der Test des zweistufigen Ansatzes mit guten Algorithmuskonfigurationen zeigt eine verringerte Robustheit, da nun manche zuvor erfolgreiche Konfiguration regelmäßig nur lokale Optima erreicht. Andere Konfigurationen hingegen zeigen beträchtliche Verbesserungen der Laufzeit, z.B. erreicht die beste Konfiguration beständig zufriedenstellende Lösungen mit nur 30% der Laufzeit, die ein einstufiger EA in der selben Konfiguration benötigt. Probleme mit bis zu 100.000 Objekten können so mit einer durchschnittlichen Laufzeit von 200 Sekunden gelöst werden.
Abschließend lässt sich sagen, dass für die Clusteringprobleme evolutionäre Ansätze als Basis für erfolgreiche, gut skalierende Methoden dienen können. Dies setzt jedoch die Integration von problemspezifischem Wissen an passenden Stellen voraus. Obwohl ein Standard EA flexibel genug ist, um ohne großen Aufwand für Clustering Probleme angepasst zu werden, sind Standard Operatoren nicht ausreichend um gute Leistung oder Skalierbarkeit zu erzielen. Der Standard EA ist nicht geeignet zum Lösen großer Probleme.
Sollen große Probleme mit wenig Aufwand gelöst werden, so kann der Entwurf von problemspezifischen Operatoren zu kostspielig sein. Hier empfiehlt es sich den Algorithmenentwurf auf einer problemspezifischen Heuristik aufzubauen, auch wenn die Heuristik anfällig ist nur lokale Optima zu erreichen. In Kombination mit einem EA hat dieser Ansatz trotzdem gute Resultate gezeigt: der hybride Algorithmus ist zum einen schneller als ein Standard EA im Erfolgsfall und zum anderen erfolgreicher als die nicht-hybride Anwendung der Heuristik.
Ist jedoch bestmögliche Leistung ein Hauptaugenmerk, so kann der hybride Algorithmus weiter optimiert werden, indem problemspezifische Operatoren oder zweistufige Verfahren eingeführt werden. Diese Optimierungen können die Leistung nochmals beträchtlich verbessern. Jedoch sind sie aufwändiger zu entwickeln und erhöhen die Fehleranfälligkeit auf Grund reduzierter Robustheit.