Mit der Evolution ist zu rechnen

Ulrike Fell | aus HEUREKA 5/08 vom 17.12.2008

Ganz gleich ob Flugzeugbau, Verkehrsplanung oder Bilderkennung: Mithilfe von Darwins evolutionären Grundprinzipien lassen sich Algorithmen programmieren, die technische Lösungen für viele Bereiche optimieren.

Der Natur abgeschaut. Wie findet man den schnellsten Weg, die Antenne mit der größten Reichweite, die windschnittigste Turbine? Die Natur hat es uns vorgemacht. In unzähligen Zyklen hat die Evolution stets aufs Neue erfolgreicher angepasste Arten hervorgebracht, Arten, die sich besser gegen Feinde zu schützen oder effizienter Nahrung zu beschaffen wissen. Diese Optimierung geht zwar unendlich langsam vor sich. Und doch schauten sich Informatiker dieses Grundprinzip der Evolution ab, das „survival of the fittest“, um daraus Algorithmen für ihre Programme zu schreiben.

Bereits in den 70er-Jahren kamen der Deutsche Ingo Rechenberg und der US-Amerikaner John Holland unabhängig voneinander auf die Idee, die Darwin’schen Mechanismen als Rechenmodelle zur Lösung mathematischer bzw. technischer Probleme einzusetzen. Seit Beginn der 90er-Jahre haben sich sogenannte „evolutionäre“ oder „genetische“ Algorithmen als Optimierungsstrategien in vielen Bereichen von Wirtschaft und Forschung durchgesetzt.

Ein Computer spielt dabei die elementaren Schritte der Evolution – Mutation, Rekombination und Selektion – durch, um möglichst schnell die jeweils beste Lösung eines Problems zu finden. „Evolutionäre Algorithmen können überall dort helfen, wo klassische Rechenverfahren überfordert sind“, sagt Karsten Weicker von der Hochschule für Technik, Wirtschaft und Kultur in Leipzig.

Gepaarte Lösungen. Mathematisch gesprochen liefert der Algorithmus die Rechenvorschrift, um das Maximum einer Funktion, d.h. den höchsten Punkt in einer Zahlenlandschaft, zu finden. „Man legt sich eine erste Population an Lösungskandidaten an“, so Weicker. Diese übernehmen die Rolle der fortpflanzungsfähigen „Individuen“: „Die werden dann miteinander gepaart, variiert und selektiert“, erklärt Weicker. Jedes Individuum bringt dabei eine bestimmte Überlebensfähigkeit mit. Diese hängt wiederum von einer Reihe von Eigenschaften ab, die in den „Genen“ festgelegt sind.

Günstige Erbmerkmale werden wie in der Natur dadurch erhalten, dass besser angepasste Individuen mehr Nachkommen haben. Aufgabe der evolutionären Algorithmen ist es nun, das tüchtigste Individuum zu finden: „Durch das Wechselspiel zwischen Variation und Selektion nähert man sich schrittweise der besseren Lösung an“, sagt der Informatiker Günter Rudolph von der Technischen Universität Dortmund.

Was bei derartigen Simulation optimiert wird, ist letztlich beliebig: Bei Rudolph sind es Turbinenblätter von Schiffsantrieben. Ebenso lassen sich Architekturmodelle verbessern, wobei Statik und Raum die Spielregeln für die „Evolution in silico“ liefern. Oder Musik: Soll das Stück einem möglichst breiten Publikum gefallen, so lassen sich die Parameter so einstellen, dass von Generation zu Generation immer gefälligere Klänge die Oberhand gewinnen.

In der Automobilindustrie und im Flugzeugbau nutzt man evolutionäre Algorithmen, um beim Fahrzeug die schnittigsten Stromlinienformen, beim Flugzeug optimale Flügelprofile oder die jeweils beste Rumpfform zu entwickeln. In der Finanzwelt dienen die Rechenmodelle der Risikoabschätzung, z.B. bei der Verwaltung von Aktienfonds.

Stillgelegte Strecken. Das klassische Beispiel für ein Optimierungsproblem ist das des Handlungsreisenden, der die kürzeste Route für seine Tour sucht. Bei einer kleinen Anzahl von Städten lässt sich das Problem noch im Kopf lösen. Schnell aber wächst der nötige Rechenaufwand ins Unermessliche. Hier erleichtert ein evolutionärer Algorithmus die Suche.

Zu Beginn erzeugt man eine Anfangspopulation von zufälligen Routen oder „Individuen“. Anschließend reproduzieren sich nur diejenigen Reiserouten, die vergleichsweise kurz sind. Während des Reproduktionsvorgangs kann eine Route zufällig leicht verändert werden – was einer „Mutation“ entspricht. Diejenigen Individuen mit den längeren Weglängen sterben aus. „Nach und nach bilden sich immer bessere Routen heraus“, erklärt Weicker.

In dieser ursprünglichen Form liefert der evolutionäre Algorithmus bereits eine gute, wenn auch nicht notwendigerweise die beste Lösung. Um die Programme effizienter zu machen, haben Informatiker im Laufe der Zeit immer wieder neue Faktoren der natürlichen Evolution eingeführt: etwa die Mehrgeschlechtlichkeit oder die Diploidie, also das Vorhandensein eines doppelten Chromosomensatzes.

Auch das Konzept der Co-Evolution lässt sich nutzen: Das ist die gleichzeitige Evolution zweier miteinander konkurrierender Arten, die durch eine Art Feedbackschleife vorangetrieben wird, wie man das etwa beim Raubtier und seiner Beute beobachten kann. Neuere Erkenntnisse aus der Entwicklungsbiologie wurden ebenfalls bereits zu übertragen versucht: Traditionelle evolutionäre Algorithmen besitzen beispielsweise nicht den Mechanismus, einzelne Gene an- oder auszuschalten, wie es in der natürlichen Embryonalentwicklung geschieht.

„Wir wollen die Natur aber nicht nachahmen, sondern uns lediglich inspirieren lassen“, sagt Rudolph. Die Informatiker greifen pragmatisch jene Ideen auf, die für ihr jeweiliges Problem von Nutzen sind. „Was am besten funktioniert, muss man durch Ausprobieren herausfinden“, sagt auch Weicker und schränkt gleich ein: „Bei vielen Problemen liefern evolutionäre Algorithmen auch keine Lösungen.“

Grüne Welle errechnen. Bewährt haben sich evolutionäre Algorithmen beispielsweise bei dem Versuch, den Straßenverkehr „intelligent“ zu steuern. Beim Projekt „Travolution“ hat eine Forschungsgruppe im bayerischen Ingolstadt 46 Ampeln mit einer Kombination aus Funkempfänger und -sender ausgestattet. Eine spezielle Software berechnet mithilfe evolutionärer Algorithmen die optimale Taktung der Ampelschaltungen.

In der Simulation werden anhand des zu erwartenden Verkehrsaufkommens Warte- und Fahrtzeiten berechnet. Die „fitten“ Steuerungsvarianten dürfen sich weitervermehren, bis sich schließlich die beste Steuerung gebildet hat. „Die Wartezeiten an den Ampeln wurden um bis zu 32 Prozent reduziert“, resümiert Alexander Wulffius vom Softwareunternehmen Gevas. Der Kraftstoffverbrauch sank gleichzeitig um 19 Prozent.

In Wien ist im Rahmen des Verkehrsmanagementsystems ITS Vienna Region ein ähnliches Pilotprojekt angelaufen: „Wir haben ein Testgebiet an der Wienzeile, wo etwa 20 Ampelanlagen mit evolutionären Algorithmen geschaltet werden“, so Stefan Miller von der österreichischen Gevas-Niederlassung. Das Ziel ist auch hier, Staus und damit den Kohlendioxidausstoß zu reduzieren.

Evolution der Phantombilder. Erfolge bringen die evolutionären Verfahren auch in der Bildverarbeitung. Evolutionäre Algorithmen helfen der Polizei bei der Erstellung von Phantombildern. Dabei berechnen Programme aus Merkmalen, an die sich der Zeuge erinnert, eine Serie zufällig erzeugter Gesichter.

Aus dieser „Elterngeneration“ sucht sich der Zeuge jene Bilder aus, die dem Verdächtigen am meisten ähneln. Daraus komponiert der Algorithmus immer neue Varianten, bis der Zeuge zufrieden ist. Ein britisches Pilotprojekt legt nahe, dass solche Verfahren nicht nur schneller, sondern auch zuverlässiger als herkömmliche Zeichenprogramme sind.

Der klassische evolutionäre Algorithmus hat inzwischen selbst so etwas wie eine Evolution durchlebt: Mit leistungsstarken Parallelrechnern oder sogenannten Computer-Grids – einer Art virtueller Supercomputer – lassen sich die Simulationen erheblich beschleunigen und auf komplexere Probleme anwenden.

Roboter lernen lassen. Der neueste Schrei ist das „genetische Programmieren“. Dabei entwickeln sich die Computerprogramme eigenständig nach evolutionären Mechanismen. Dies spielt beispielsweise in der Robotik eine große Rolle, wo man lernfähige Systeme braucht. Erst kürzlich kündigte das schwedische Institute of Robotics in Scandinavia (iRobis) die Markteinführung einer Software für Roboter an, die mit genetischer Programmierung arbeitet. „Das System macht aus Robotern sich selbst entwickelnde, anpassungsfähige, problemlösende und denkende Maschinen“, schwärmt Roger F. Gay von iRobis. Ob der Sprung zum intelligenten Maschinenwesen damit tatsächlich geschafft ist, wird die Zukunft zeigen. Und auch, was die Menschheit davon hat.

Weitere Artikel lesen


Anzeige

Anzeige