Die PARPROG-Toolbox mit drei Verfahren
Evolutionäre Algorithmen sind globale Optimierverfahren, die in einem mathematischen Suchraum Mechanismen der Evolution nachbilden und dabei möglichst guten Werten einer von außen vorgegebenen Zielfunktion zustreben. Mutation, Rekombination und Selektion werden immer wieder auf eine Population von potentiellen Lösungen angewandt, die sich dann an lokalen Spitzen vorbei auf das globale Optimum zubewegen.
Ein großer Vorteil Evolutionärer Algorithmen ist ihre mathematische Anspruchslosigkeit an das von außen vorgegebene Problem. Es kann praktisch als Black-Box angesehen werden und muß lediglich ein Qualitätskriterium für gute Lösungen bereitstellen. So konnten z.B. die Marketing Systems-Produkte zur kurz- und mittel- bis langfristigen Prognose ohne genaues Wissen um die internen Abläufe mit einem parallelen EA gekoppelt werden. Die angesprochene Modularität ermöglichte es uns, verschiedene Optimierprobleme mit der gleichen graphischen Schnittstelle in die im Projekt erstellte Toolbox einzufügen und sowohl serielle als auch parallele Varianten der Lösungssuche vollständig über diese zu steuern.
Evolutionäre Algorithmen zeichnen sich auch durch eine besondere Robustheit aus, die sie gegen Störungen - wie sie etwa durch asynchrone Kommunikation hervorgerufen wird - weitgehend unempfindlich macht. Das ermöglicht eine effiziente Parallelisierung, die nicht durch ständige Synchronisation unnötig Ressourcen verbraucht.
Forderungen an die implementierten parallelisierten Algorithmen waren und sind vor allem:
Die Portabilität ist durch die Verwendung von PVM gegeben, das dem Anwender ein gemeinsames Interface für alle Arten von Parallelrechnern oder vernetzten Systemen bietet.
Skalierbarkeit wird vom gewählten Parallelisierungsansatz gewährleistet, dem ein gemischtes Migrations- und Nachbarschaftsmodell zugrunde liegt: Die vom EA benötigte Population von parallel existierenden potentiellen Lösungen (Individuen) wird logisch als Torus untereinander verbunden. Vertikal geschnittene Scheiben davon werden jeweils einem Rechenknoten zugeordnet, der diesen Bereich vollständig eigenständig berechnet und nur in gewissen Zeitabständen mit seinen beiden Nachbarknoten Kontakt aufnimmt und die am Rand der Scheibe liegenden Individuen mit diesen austauscht.
Die in der logischen Anordnung räumlich zusammengesetzten Teilpopulationen ergeben einen Torus. Die unterschiedlichen Färbungen reflektieren die unterschiedliche Güte der vorläufigen Lösungen.
Da die Individuen auch innerhalb eines Bereiches nur mit ihren direkten Nachbarn verbunden sind, hat dieser Parallelisierungsansatz für den Evolutionären Algorithmus eine starke Lokalisierung zufolge. Gute Lösungen können sich nur langsam über die Gesamtpopulation ausbreiten, womit andererseits aber auch eine hohe Diversität erhalten bleibt. Dabei bilden sich die typischen Flecken aus, die Gegenden mit ähnlichen Lösungen darstellen und sich gegen Einflüsse von außen lange Zeit behaupten.
Neuronale Netze werden nach zwei Ansätzen parallelisiert: