In niederschlagsarmen Regionen, in denen die Grundwasserreserven rar sind und mit grösster Sorgfalt angezapft werden müssen, braucht es ein umfassendes Ressourcen-Management. Verschiedene Faktoren müssen berücksichtigt werden: Wie interagiert der Grundwasserleiter mit seiner Umgebung, wo ist zu bohren, ohne dabei dem Nachbarn das Wasser abzugraben, wie kann das Grundwasser über lange Zeit gesichert und wie können die Erschliessungs-Kosten so niedrig wie möglich gehalten werden. Dieses komplexe Anwendungsproblem untersuchten Tobias Siegfried und Wolfgang Kinzelbach, Professor am Institut für Umweltingenieurwissenschaften der ETH Zürich, mit Hilfe der simulierten Evolution; dabei nutzen sie Methoden, die in der Gruppe von Eckart Zitzler, Assistenzprofessor für Systemoptimierung am Departement für Informationstechnologie und Elektrotechnik, entwickelt wurden. Eckart Zitzler ist darauf spezialisiert, derartig schwierige Problemstellungen mit  «Evolutionären Algorithmen» zu lösen.

Dem Besten annähern

«Evolutionär» heissen die Algorithmen, weil die Wesenszüge der Evolution - Mutation, Rekombination und Selektion - die Basis ihrer Lösungssuche bilden. Sie werden vor allem bei komplizierten Konstruktionsproblemen im Ingenieurwesen genutzt. Die Methode ist zwar zeitintensiv, doch flexibel einsetzbar; dadurch eignet sie sich insbesondere für komplexe Anwendungen, bei denen klassische analytische Verfahren nicht funktionieren.
Bei den stochastischen Suchverfahren, die den Algorithmen zugrunde liegen, geht es nicht darum die beste Lösung zu finden, sondern Lösungen stetig zu verbessern. Die Forscher wissen nie, wann sie die maximale Verbesserung erreicht haben. «Das ist auch nicht die Hauptfrage, sondern wie gut die Ausgangslösung verbessert werden konnte », sagt Zitzler.

Autoelektronik optimal verkabeln

Beim jüngsten Forschungsprojekt der Gruppe Zitzler geht es um Autoelektronik; die Computersysteme, die beispielsweise den Bremsvorgang, die Klimaanlage, und die Airbags steuern, sind zu optimieren. Das Problem dabei: Die Verkabelung der Bauteile, die auf verschiedene Orte im Auto verteilt wird, wiegt über 100 Kilogramm. Die Forscher müssen die Hardwarearchitektur konstruieren und bestimmen, wo welches Element im Auto optimal montiert wird, um das Gewicht der Verkabelung gering, die Kosten minimal und die Reaktionszeit des Gesamtsystems kurz zu halten. Zudem soll die Zuverlässigkeit des Systems möglichst hoch sein.

Zitzler erklärt das Vorgehen anhand eines Rucksackes, der optimal gepackt werden soll. Wenn man auf eine Wanderung geht und verschiedene Dingen auswählen muss, die mit sollen, aber nur ein begrenztes Gewicht einpacken darf, generieren Evolutionäre Algorithmen verschiedene Pack-Kombinationen. Die Gegenstände werden dabei entsprechend ihrem Nutzen mit einer Zahl belegt. Die Zahlenkombinationen einer möglichen Rucksackfüllung bilden eine Art DNA. Anfangs wird eine zufällige Kombination gewählt. Dann werden die DNA-Stränge in zwei Hälften geschnitten und neu kombiniert. Der Inhalt mutiert, indem Gegenstände herausgenommen und durch neue ersetzt werden. Nun wird berechnet, wie gut die Kombinationen sind, wie nützlich und wie schwer und aus den Populationen der verschiedenen Rucksack-Packungen die besten 50 Prozent selektiert.

Prinzip Zufall

Die Evolutionären Algorithmen finden ihre Lösungen nach dem Zufallsprinzip. Paradebeispiel ist eine der ersten Studien dieser Art, die der Bioniker Ingo Rechenberg und der Ingenieur Hans Paul Schwefel in den sechziger Jahren noch von Hand und mit dem Würfel durchführten. Sie verbesserten eine Überschalldüse so, dass sie die durchfliessende Luft optimal beschleunigte. Dazu zerlegten sie die Düse in Scheiben. Die Mutation, wie gross der Durchmesser der Düse sein soll, haben die Forscher gewürfelt. Jede auf diese Art neu entstandene Konfiguration mussten die Forscher testen. Aus der sogenannten Population von Anordnungen wählten sie danach die beste (Selektion) aus und mutierten diese weiter. Jede fünfte Konfiguration erwies sich als besser. Nach 400 Mutationen und  Konfigurationen und einer bizarren neuen Form der Düse, hatte sich der Wirkungsgrad der Überschalldüse von 55 Prozent auf knapp 80 Prozent verbessert.

Damals gab es noch keine erschwinglichen Computer, die das Würfeln übernahmen und die jeweiligen neuen Düsen simulieren konnten. Das Verfahren war deshalb aufwendig und blieb die Erklärung schuldig, warum die neuartige Düse einen besseren Wirkungsgrad erzielte. Heutzutage wird diese Methode Evolutionsstrategischer Algorithmus genannt. Bis diese Art der Problemlösung sich in der und als Wissenschaft etablierte, dauerte es noch rund drei Jahrzehnte. Erst als Computer erschwinglich wurden, setzten die Wissenschaftler die Methode vermehrt ein. Ende der 80iger gab es die erste Tagung zum Thema, heute gibt es jährlich mehrere grosse und kleinere Konferenzen, die sich mit Evolutionären Algorithmen befassen. Die Evolutionären Algorithmen stehen dabei als Sammelbegriff für die verschiedenen Forschungszweige, die sich allmählich entwickelt haben: die Evolutionsstrategien, die Evolutionäre Programmierung, die Genetischen Algorithmen und die Genetische Programmierung.

Heute kommen die Evolutionären Algorithmen auch verschiedentlich in der Lehre zum Einsatz: Studierende am D-ITET haben beispielsweise eine Software geschrieben, die Türme aus Bauklötzchen so konstruiert, dass sie möglichst weit über eine Tischkante hinausragen können (siehe Abbildung und ETH Life Artikel vom 3.12.2007).