Optimierungsverfahren und Designautomatisierung

In diesem Kapitel sollen - aufbauend auf die Einführung in Artificial Life - Anwendungen des in Form von naturinspirierten Optimierungsverfahren aufgezeigt werden. Anschließend folgt die „Anwendung der Anwendung“, nämlich eine Betrachtung von Dingen, die mit Hilfe solcher Optimierungsverfahren entstehen können.

In den Wissenschaftsdisziplinen gibt es viele mathematische und naturinspirierte Optimierungsverfahren, mit denen man versucht, gute Lösungen für sog. Optimierungsprobleme zu finden. Optimierungsprobleme treten allerorten auf. Sie zeichnen sich durch zwei Dinge aus:

• Es gibt eine einfache Möglichkeit, festzustellen, wie „gut“ ein Lösungskandidat für das jeweilige Problem ist (Fachbegriff: Fitness-Evaluation; man wertet die Fitnessfunktion, die auf dem Raum aller Problemparameter definiert ist, an den Stellen der Lösungskandidaten aus).
• Sie sind analytisch nur schwer anzugehen, man kann also nicht „mal kurz“ rechnerisch gute Lösungen bestimmen.

Ein typisches, mathematisch schwer greifbares Problem wäre beispielsweise:

Wo muss UPS die Basislager aufstellen, damit die Pakete schnell zugestellt werden?

Problemparameter sind also die Orte einer Anzahl Basislager als x- und y-Koordinaten.

• Die Fitness-Evaluation kann hier in kleinen Simulationen bestehen, in denen die Logistik eines Lösungskandidaten durchsimuliert wird. Ergeben sich z.B. unoptimale Wegstrecken zwischen Basislagern, Flughäfen oder sind Basislager schlecht positioniert, so steigen die durchschnittlichen Zustellzeiten versendeter Pakete, die Fitness sinkt. Gibt es zuviele Lager, dann auch.
• Eine Formel zu finden, in welche einfach die Basislagerorte eingegeben und die Fitness ausgegeben wird, ist offensichtlich nicht trivial.

Solchen Problemen versucht man, mit Optimierungsverfahren (ob naturinspiriert oder nicht) zu Leibe zu rücken. In der Regel funktionieren diese Verfahren so, dass iterativ, also in vielen Durchgängen, auf Basis von vorher bestimmten Lösungskandidaten neue Lösungskandidaten bestimmt und ausgewertet werden, wobei als Basis des allerersten Durchlaufes einfach zufällig generierte Lösungskandidaten gewählt werden. Wie genau nun das bestimmen jeweils neuer Lösungskandidaten passiert, unterscheidet sich von Verfahren zu Verfahren. Wir wollen nun mehrere solcher Verfahren betrachten - zunächst ein herkömmliches (das leider nicht so anschaulich ist wie die beiden folgenden), dann zwei biologisch motivierte.

Gradientenverfahren betrachten die Steigung der Fitnessfunktion bezogen auf die Problemparameter, fragen sich also schlicht „an welchen Parametern muss gedreht werden, damit die Fitness besser wird?“. Angefangen wird mit einem zufällig generierten Lösungskandidaten, und aus diesem wird bei jedem Durchlauf ein neuer generiert. Hierfür wird der alte Kandidat „verschoben“, und zwar in die Richtung im Parameterraum, in der (anhand der mathematischen Ableitung der Fitnessfunktion) ein Anstieg der Fitness vermutet wird. Je steiler der Anstieg, desto größere Schritte werden getätigt. Wir suchen also „Berggipfel“ (Maxima) der Fitness.

Gerade der letzte Satz impliziert schon ein Problem: Ist der Anstieg nur sehr flach, so müssen sehr viele Iterationen getätigt werden, um in bessere Fitnesswerte zu rutschen. Zweitens macht es die lokale Betrachtungsweise von Gradientenverfahren (es wird immer nur ein Lösungskandidat betrachtet und verschoben) wahrscheinlich, dass ein Gipfel, den wir erreichen, lange nicht so hoch ist, wie ein anderer, den wir auch hätten erreichen können¹⁾.

Interessanter wäre es, also, eine globalere Betrachtungsweise des Problems zu wählen - mehrere Lösungskandidaten auf einmal zu betrachten und intelligent neue vorzuschlagen, als einfach blind am Hang hochzuklettern. Genau das wird während einer Evolutionären Optimierung gemacht.

Als erstes, naturinspiriertes Beispiel eines Optimierungsverfahrens sei die Evolutionäre Optimierung genannt. Wie der Name schon nahelegt, ist dieses Optimierungsverfahren inspiriert von der natürlichen Evolution, die ja auch nichts anderes tut, als Lebewesen auf Überlebensfähigkeit in ihrer Umwelt hin zu optimieren. Also zuerst zum biologischen Vorbild.

Wie heutzutage bekannt ist, trägt jedes Lebewesen einen komprimierten Bauplan seiner selbst in sich: Das sogenannte Genom. Vereinfacht gesprochen besteht ein Genom aus einer Menge von Parametern (Genen), welche sehr viele Merkmale des zugehörigen Lebewesens definieren. Die Gesamtheit aller Genome einer ganzen Population von Lebewesen nennt man Genpool.

Innerhalb einer Population gibt es Lebewesen, die in der Lage sind, „erfolgreicher“ zu leben als andere. „Erfolg“ bedeutet in der Natur, die eigene Spezies (und damit das eigene Genom) möglichst effizient zu erhalten, also Nachkommen zu zeugen. Ein Lebewesen kann erfolgreicher sein als ein anderes, indem es besser an einen bestimmten Lebensraum angepasst ist: In einer Wüste ist es beispielsweise ein erfolgversprechendes Merkmal, Nahrungsmittel, insbesondere Wasser, sehr effizient zu verbrauchen. Ein Lebewesen, in dessen Genom spezielle Merkmale zur effizienten Wasserspeicherung einkodiert sind, kann sich in der Wüste durch höhere Überlebenschancen auszeichnen, also insbesondere tendenziell mehr Nachkommen haben. Durch diesen Mechanismus, die sogenannte Selektion, wird ein Genom, welches sich in der Umwelt bewährt hat, gegenüber schlechter geeigneten Genomen überproportional verbreitet.

Neben der Selektion gibt es einen zweiten wichtigen Aspekt, der zum Verständnis der Evolution relevant ist: Der Genpool ist nicht statisch. Zum einen enthalten, falls sich Lebewesen sexuell vermehren, die Genome der Nachkommen Merkmale aus beiden Elterngenomen (man spricht hier von der Rekombination von Genomen), zum anderen können auch einzelne Gene durch Faktoren wie z.B. die kosmische Hintergrundstrahlung verändert werden (hier spricht man von Mutation). Es kommen also laufend neue Genome zum Genpool hinzu, andere Genome verlassen den Genpool hingegen. Neue, hinzukommende Genome entstehen durch Rekombination und Mutation aus bereits vorhandenen Elterngenomen, wobei - wie oben dargestellt - erfolgreiche Genome überproportional oft als Eltern dienen. Weniger erfolgreiche Genome sterben hingegen überproportional aus. Wir halten also fest: Mutation und Selektion sind einfache Operatoren, aus alten Genomen neue herzustellen. Die Selektion sorgt dafür, dass dieser Prozess eine Richtung erhält, also gezielt optimiert wird.

Das Zusammenspiel von Selektion, Rekombination und Mutation bewirkt, dass die Überlebensfähigkeit einer Population von Lebewesen in derem Umwelt optimiert wird - die Lebewesen passen sich laufend graduell ihrer Umwelt an. Diese Art der Optimierung versucht man durch evolutionäre Optimierungsverfahren nachzubilden und so für die Lösung verschiedenster Probleme nutzbar zu machen.

Wie oben erwähnt, versucht man evolutionäre Optimierungsverfahren auf Optimierungsprobleme anzuwenden. Optimierungsprobleme sind, wie ebenfalls schon beschrieben, parametrisierbar: Ein Lösungskandidat des Optimierungsproblems wird durch einen Parametersatz (sein Genom) definiert. Weiter kann man für einen partikulären Lösungskandidaten die Güte messen, es steht uns also eine Fitnessfunktion zur Verfügung, welche Elemente des Parameterraums auf Fitnesswerte abbildet. Wie in der Natur lässt sich also messen, wie erfolgreich ein Genom ist - oder technisch ausgedrückt, wie gut ein bestimmter Parametersatz das gegebene Optimierungsproblem löst. Evolutionäre Optimierungsverfahren operieren nun - wie die Natur - auf Grundlage eines Genpools, der aus den Genomen einer Population von Lösungskandidaten besteht. Diese Population wird meist zufällig initialisiert, besteht also Anfangs nur aus zufällig ausgewürfelten Lösungskandidaten.

Einmal initialisiert, durchläuft die Population von Lösungskandidaten verschiedene Phasen, die nun beschrieben werden:

• Evaluation: Für jeden Lösungskandidaten in der Population wird die Fitnessfunktion ausgeführt.
• Selektion: Anhand der Evaluationswerte werden aus der aktuellen Population Elterngenome ausgewählt. Genome mit höherer Güte werden hierbei bevorzugt ausgewählt (beispielsweise anhand einer Wahrscheinlichkeitsverteilung).
• Erneuerung der Population: Die Population wird erneuert (man spricht hier von der nächsten Generation), indem die zuvor selektierten Elterngenome rekombiniert und mutiert werden. Für Rekombination und Mutation sind problemspezifische Operatoren zu entwerfen. Bei unserem UPS-Problem könnte z.B.
  • das leichte Verändern einer Basislagerposition den Mutationsoperator darstellen, und
  • die Rekombination von zwei Elterngenomen zu einem neuen Genom könnte darin bestehen, aus beiden Eltern mehrere Basislager zu übernehmen. Diese Operatoren werden dann auf die vorhandenen Genome angewendet, also aus den alten Problemlösungskandidaten neue generiert.

Diese drei Schritte werden so oft hintereinander ausgeführt, bis ein bestimmtes Kriterium erfüllt ist (z.B. eine im Vorfeld definierte Fitness erreicht wird oder eine vorgegebene Anzahl von Generationen durchlaufen ist). Man hofft, dass sich die Population der Lösungskandidaten analog zur natürlichen Evolution einem Optimum auf der Fitnessfunktion nähert, die schlechten Kandidaten also nach und nach aussortiert werden, und bessere entstehen. Wie wir noch sehen werden, kommen so oft unerwartete, unvoreingenommene Problemlösungen zustande.

Wir bewegen uns durch Anwendung der evolutionären Optimierung also evolutionär durch den Parameterraum, also auf die gleiche Weise, wie die Natur es seit Jahrhunderten tut. Eine andere, ebenso biologische Form der Bewegung durch den Parameterraum soll nun vorgestellt werden.

Wie löst die Menschheit Probleme? Anscheinend nicht evolutionär, denn selbst Menschen, die nichts zur Gesellschaft beitragen, werden durch unser Sozialsystem ernährt - zumindest in einigen Teilen der Welt. Die Evolution, also die rohe Natur, würde diese Individuen beim ersten Fehler wohl aussortieren - und die meisten von uns hätten einen solchen „aussortierungswürdigen“ Fehler schon begangen.

Probleme werden von uns sozial gelöst: Ein kleiner Teil der Menschheit erkennt das Problem und löst es (z.B. eine aus wenigen Menschen bestehende Forschungsgruppe an einer Universität), und die Lösung spricht sich zum Rest der Menschheit herum. Information verbreitet sich durch Kommunikation. Dies war seit jeher das Prinzip der Menschheit, und ist im Grunde das einzige, was die Menschen den Tieren voraushaben²⁾. Particle Swarm Optimization (PSO) ist ein Optimierungsverfahren, welches sich auf soziale Weise durch den Parameterraum bewegt.

PSO modelliert einen Schwarm von Individuen (Partikeln), die sich durch den Suchraum des zu optimierenden Problems bewegen. Die Partikel sind, wie bei der evolutionären Optimierung, diejenigen Punkte im Suchraum, an denen die Fitnessfunktion des zu optimierenden Problems ausgewertet wird. Die Lösungssuche, also die Bewegung eines jeden Partikels durch den Suchraum, basiert sowohl auf der Verarbeitung von partikelspezifischen Informationen (z.B. dem partikelspezifischen Fitness-Bestwert bis zu diesem Zeitpunkt), als auch auf Interaktionen zwischen Partikeln (z.B. können gute Fitnesswerte anderer Partikel die Bewegung ebenfalls beeinflussen, Informationen sprechen sich herum!). Diese einfache Art von Kommunikation ist der eklatante Unterschied zur oben dargestellten Evolutionären Optimierung. Das Ziel der PSO ist, dass der Partikelschwarm sich - ähnlich eines futtersuchenden Vogelschwarms - auf diese Weise nahe zu einem Fitnessoptimum im Parameterraum bewegt.

Nachdem nun in relativ abstrakter Weise Optimierungsverfahren vorgestellt wurden, wollen wir einige Anwendungen betrachten. Hier sollen Anwendungen betrachtet werden, die mit Hilfe evolutionärer Optimierung entstanden sind.

Der evolutionäre Ansatz findet weite Verbreitung im den relativ jungen Gebiet der evolutionären Robotik und kann auch auf Schwarmverhalten und Schwarmrobotik übertragen werden. An dieser Stelle soll zunächst auf Arbeiten in der evolutionären Robotik eingegangen und später zum evolutionären Schwarmverhalten übergegangen werden.

Im Bereich der evolutionären Robotik synthetisiert man Verhalten, indem man Kontrollstrukturen (Gehirne) für z.B. autonome Roboter durch einen evolutionären Algorithmus einstellt, was oft zu unerwarteten, aber robusten Lösungen führt. Beeindruckende Resultate erzielten hier beispielsweise Pollack und Lipson (Chef meiner Cornell-Arbeitsgruppe), die im Rahmen des GOLEM-Projektes nicht nur die Kontrollstruktur, sondern zeitgleich auch die Körper von Robotern durch evolutionäre Algorithmen erzeugten und so in gewisser Weise künstliche Lebensformen schufen (Bild links³⁾). Diese Arbeit trug nicht nur zur evolutionären Robotik, sondern auch zum Feld der Design- und Fertigungsautomatisierung bei, weil entstandene Roboter im Anschluss an die Evolution mittels Rapid-Prototyping-Techniken⁴⁾ gebaut wurden (Bild rechts ⁵⁾). So wurde die Hürde von Simulation zur Realität auf eine zum größten Teil automatisierte Weise überwunden, und es entstanden sozusagen urtümliche Lebensformen. Die Fitnessfunktion war in dem Fall eine Simulation der entstandenen Wesen, in der ganz einfach gemessen wurde, wie weit sie sich innerhalb einer bestimmten Zeit fortbewegten - wer schneller rennt, gewinnt und verbreitet sein Genom weiter. Untenstehend ein YouTube-Video hierzu.

Ein Beispiel aus dem Bereich der evolutionären Schwarmrobotik stellt unser Projekt Beanbag Robotics dar, in welchem Kontrollstrukturen für Individuen eines Schwarms evolutionär erzeugt werden.

Diese Individuen sind extrem simpel modelliert, u.a. können sie nicht lenken. Hierdurch können sie äußerst klein und preiswert gebaut werden. Ein Schwarm dieser minimalistisch modellierten Roboter erlernt dann evolutionär, wieder Navigationsfähigkeit zu erlangen. Ziel der Arbeit ist, durch Schwarmverhalten ein frei verformbares, redundantes robotisches System aus einfachsten Bestandteilen herzustellen - sozusagen einen Flüssigroboter, der sich auch durch enge Lücken quetschen kann (Bild rechts).

Ein theoretischerer Bereich, dessen Anwendungen aber trotzdem offensichtlich sind, ist das automatisierte Reverse-Engineering unbekannter, nichtlinearer, oder sogar dynamischer Systeme. Salopp gesagt: Man hat einen Haufen Daten, kennt aber das System dahinter nicht. Man möchte gewissermaßen eine von Parametern abhängige Formel finden, mit der sich die Daten möglichst gut beschreiben lassen - auch etwas ist mit Techniken wie evolutionärer Optimierung ohne weiteres möglich und schon durchgeführt worden⁶⁾.

Sehr vereinfacht dargestellt, lässt man ein Modell in Form eines Term-Baums (also Rechenanweisungs-Baums) durch Evolution entstehen, wobei als Fitness mit bestimmten Tests gemessen wird, wie gut das Modell die Daten repräsentiert. Als Mutation könnte dem Baum ein Operator angefügt oder eine Konstante leicht verändert werden, Rekombination könnte z.B. zwei Operatorbäume zusammenheften. Mittels einer solchen Evolution kann es sogar gelingen, aus Daten Naturgesetze herauszulesen⁷⁾ (Untenstehend ein YouTube-Video dazu).

Was wäre nun, wenn man Optimierungsverfahren nutzen könnte, um nach und nach künstliche Welten und richtige künstliche Lebewesen erschaffen und in den Kontext der realen Biologie stellen könnte? Auf solche Themen der synthetischen Biologie werden wir später noch zu sprechen kommen.

Bis diese Seite ausführlicher ist, schaut euch mal das gratis erhältliche Buch „Essentials of Metaheuristics“ von Sean Luke an, welches unter http://cs.gmu.edu/~sean/book/metaheuristics/ erhältlich ist (Verlinkt mit Erlaubnis). Es freut mich sehr, dass noch andere Leute ihre Arbeit gratis zur Verfügung stellen.