Stellen Sie sich vor, Sie belegen während 14 Wochen einen Kurs in Koreanisch und müssen dann vor einem koreanischen Fachpublikum einen Vortrag halten über die Besonderheiten grammatikalischer Ausnahmefälle in eben dieser Sprache. So ähnlich muss sich das angefühlt haben, was drei ETH-Studenten des Departements für Informationstechnologie und Elektrotechnik (D-ITET) kürzlich im französischen Tours erlebt haben. Die angehenden Elektroingenieure Samuel Gähwiler, Mathias Karlsson und Matthias Egli haben an der achten internationalen Konferenz über künstliche Evolution ihr erstes eigenes wissenschaftliches Paper vorgestellt. Dabei hatten sie wenige Monate zuvor weder eine Ahnung von künstlicher Evolution noch Erfahrung mit Präsentationen vor internationalen Experten. „Es war schon ein spezielles Gefühl“, erinnert sich strahlend Mathias Karlsson, der diese Aufgabe übernommen hatte. Bemerkenswert an der Geschichte ist vor allem eines: Dass Studenten der Bachelor-Stufe überhaupt ein eigenes Paper einreichen und den offiziellen Review-Prozess nicht nur bestehen, sondern für ihre Arbeit auch noch mit einem Award ausgezeichnet werden. „Viele Anwesende wunderten sich, als sie erfuhren, dass wir noch am Anfang des Studiums stehen“, erzählt Samuel Gähwiler lachend.

Anspruchsvolles Optimierungsproblem

Hervorgegangen ist ihre Arbeit aus einem Studentenprojekt. Die Aufgabe, die den insgesamt zwölf Teilnehmenden Anfang Semester gestellt wurde, war auf den ersten Blick recht banal: Sie sollten eine Software zum Bauen eines Turms aus Bauklötzchen entwickeln. Allerdings war nicht irgendeine beliebige Konstruktion gesucht. Vielmehr sollte das Programm einen Turm aus 20 beziehungsweise 50 Klötzchen bauen, der mit maximalem Überhang über eine Tischkante hinausragt, ohne in sich zusammenzufallen. „Es handelt sich dabei um ein sehr anspruchsvolles Optimierungsproblem, das auch repräsentativ ist für viele praktische Konstruktionsprobleme – seien es nun Computer, Motoren oder Brücken, die es zu entwerfen gilt.“, erklärt Eckart Zitzler, Assistenzprofessor für Systemoptimierung am D-ITET. Vorgegeben war, dass die Aufgabe mit Hilfe eines sogenannten evolutionären Algorithmus gelöst werden sollte. Dabei wird im Prinzip die natürliche Evolution nachgeahmt. Diese kann insofern als Lösung eines Optimierungsproblems angesehen werden, als dass sich die lebenden Organismen dabei durch Selektion, Mutation und Rekombination stets optimal an die herrschenden Umweltbedingungen anpassen. „Aufgabe war es, diese Prozesse in Bezug auf den Turmbau zu imitieren“, so Zitzler.

Es galt also, einen Algorithmus zu entwickeln, der zunächst eine Population von Klötzchen generiert, mittels Selektion einen Teil von ihnen auswählt und diese durch Mutation und Rekombination so verändert, dass sie am Ende den optimalen Turm bilden. Der Einfachheit halber beschränkte man sich auf einen zweidimensionalen Raum. Die Studierenden bildeten drei Gruppen: die einen kümmerten sich um den Algorithmus, die anderen um denjenigen Programmteil, der die Stabilität des Turms nach jedem Zwischenschritt überprüft und die dritten arbeiteten an der grafischen Umsetzung des Ganzen. Einmal wöchentlich trafen sie sich zum gemeinsamen Meeting, bei dem auch die Betreuer Tim Hohm und Stefan Bleuler dabei waren. „Die grösste Schwierigkeit bestand für die Studierenden darin, vom Konzept zur Umsetzung zu gelangen“, erinnert sich Hohm. Manchmal hätten sie die Tatsache unterschätzt, dass trotz scheinbar perfektem Design noch vieles schief gehen könne.

Unmögliches ausschliessen

Dennoch hat die Gruppe ihre Aufgabe gut gemeistert. In der Theorie sollte man mit 50 Klötzchen einen maximalen Überhang von rund 3,28 Klötzchenlängen erreichen können. Die Studenten schafften 2,97 Längen und hatten somit einen Algorithmus gefunden, der sehr nahe ans Optimum heranreicht. Knackpunkte waren einerseits die Repräsentation und die Operationalisierung von Selektion und Variation. Werden die Klötzchen im zweidimensionalen Raum mit X- und Y-Koordinaten repräsentiert, ergibt sich das Problem, dass die Klötzchen sich ineinanderschieben lassen. Der Turm wäre zwar stabil, in der Realität ist aber natürlich ausgeschlossen, dass Klötzchen sich überlappen. „Die Studierenden mussten sich überlegen, wie sie solche Fälle entweder zum Vornherein oder im Nachhinein ausschliessen können“, erklärt Eckart Zitzler. Sie fanden eine sehr elegante Lösung: Es werden beim Rechnen jeweils nur die X-Koordinaten der Klötzchen berücksichtigt, jedoch wird zusätzlich auch die Reihenfolge beachtet, in der sie aufgetürmt werden. Sie fallen sozusagen von oben nach unten und kommen somit stets übereinander, niemals jedoch ineinander zu liegen.

Lerneffekt auf vielen Ebenen

Auch für die Operationalisierung von Selektion und Variation fand die Gruppe adäquate Lösungen. Die Selektion basiert auf einem Zufallsalgorithmus. Die Mutation wird imitiert, indem sich die x-Position eines einzelnen Klötzchens verändert, wobei es zwei Varianten gibt: Entweder wird nur das eine Klötzchen verschoben oder auch alle auf ihm liegenden Klötzchen. Zur Rekombination im Rahmen der Evolution werden rechnerisch Teile von Klötzchen abgeschnitten und neu zusammengesetzt. Den besten Turm, den die Studierenden auf diese Weise generieren konnten, haben sie anschliessend mit richtigen Holzklötzchen nachgebaut – mit viel Klebstoff. „So perfekt wie der Rechner können wir natürlich nicht bauen. Dafür ist nur schon die Oberfläche der Klötzchen zu uneben“, erklärt Samuel Gähwiler. Fünf bis zehn Stunden habe er wöchentlich ins Projekt investiert, doch das habe sich gelohnt, der Lerneffekt sei gross. „Der Begriff evolutionärer Algorithmus war zuvor ein grosses Fragezeichen, jetzt verstehe ich zumindest die Grundidee“, sagt auch Mathias Karlsson. Vor allem aber habe man profitiert von der bislang eher ungewohnten Arbeit im Team, was bisweilen auch an den Nerven zehrte. „Wir mussten zum Teil viel Zeit für langwierige Diskussionen aufwenden“, erinnert sich Samuel Gähwiler seufzend. Dennoch war es für ihn keine Frage, nach Abschluss des Studentenprojekts im Dreierteam noch mehr Zeit in das Verfassen eines wissenschaftlichen Papers zu investieren. „Eine tolle Chance als Student im dritten Semester“, sagt er.