|
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.
Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to the latest Netscape.
More information
Fachnummer | 227-0080-00 L und 227-0085-00 L | Raum und Zeit | ETZ G91, 13h15-15h00 |
Dozent | Prof. Dr. Eckart Zitzler (ETZ G84) | Beginn | Mittwoch, 24. September 2008 |
Ansprechpartner | Johannes Bader (ETZ G81) Tim Hohm (ETZ G81) |
Semester | 1 und 3 |
Umfang | 2 SWS / 4 PPS-Einheiten |
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.