PPS Bauklötze für Profis - HS 2008

Inhalt

Wie weit kann ein Turm aus Bauklötzchen über eine Tischkante hinausragen, ohne dass er einstürzt? Ziel ist es, mit N identischen Bauklötzchen den Turm zu bauen, der den maximalen Überhang aufweist. Ein Klötzchen kann logischerweise nicht mehr als die Hälfte seiner Länge über die Tischkante ragen, sonst fällt es. Könnte man nun nicht einfach jedes Klötzchen immer z.B. einen Viertel über das darunterliegenden hinausragen lassen? Wie die folgende Skizze veranschaulicht, klappt das schon beim vierten Klötzchen nicht mehr. Die graue Fläche rechts der Tischkante ist grösser als die Fläche links davon; das ganze kippt. Der Überhang, den man so erreicht, beträgt also 3/4 eines Klötzchens.

Wenn man nun die Klötzchen statt einen Viertel immer nur einen Achtel über das darunterliegende hinausschiebt, ist beim 8. Klötzchen Schluss. Man erreicht also einen Überhang von 7/8.

Kann der Überhang also gar nie grösser werden als 1? Kann er doch - das lässt sich recht einfach zeigen. Doch den Turm zu finden, der mit N Klötzchen den maximalen Überhang erzeugt, ist gar nicht einfach. Es ist vielmehr ein schwieriges Optimierungsproblem, bei welchem die optimalen Lösungen alles andere als intuitiv sind, wie das nachfolgende Beispiel zeigt.

In diesem Projekt entwickeln und implementieren wir ein Softwaretool zur Lösung dieses Problem, das auf simulierter Evolution beruht. Die Idee ist, ausgehend von zufällig konstruierten Türmen zwei Prinzipien der Evolution wiederholt anzuwenden: 1.) Variation, d.h., mittels kleiner Modifikationen (Mutationen und Rekombinationen) neue, bessere Konstruktionen finden, und 2.) Selektion, d.h., wenig vielversprechende Konstruktionen verwerfen. Diese Art der Optimierung wird als Evolutionärer Algorithmus bezeichnet.

Lernziele

• Ihr setzt euch mit einem schwierigem kombinatorischem Optimierungsproblem auseinander und lernt die Anwendung von Evolutionären Algorithmen kennen.
• Ihr lernt die wichtigen Prinzipien von Projektarbeit und Softwareentwicklung kennen.