printlogo
ETH Zuerich - Homepage
Systems Optimization (SOP)
 
Search

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

ETH Zürich - D-ITET - TIK - SOP - Education - Lectures - PPS Bauklötze
print page
  
this webpage might no longer be updated more...

PPS Bauklötze für Profis - HS 2008

Jenga Turm
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

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.

turm1

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.

turm2

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

top
© 2008 Institut TIK, ETH Zürich | Imprint | Last updated: Wed, 17 Sep 2008 14:44 | Valid XHTML 1.0! Valid CSS! Valid XHTML 1.0