On Tue, 23 May 2000, friedrich_h@gmx.de wrote:
Morgen an alle LUGies,
a) Habe ich ein Frage, wir hatten zum letzen LUG-Treff (ich glaube 19.4.) mal über Darwin und die Enten-Evolutionstheorie auf dem quatratischen Teich gesprochen. Und ich hätte da gerne mal, so weit vorhanden, nähere Information über den Algorithums. (will nähmlich damit mal unsere letzten mathe-stunden füllen :-)
Mathe-Stunden fuer wen? Studies? Abiturienten? Wenn darunter, dann vergiss es lieber. Es handelte sich dabei um einen genetischen Algorithmus. Also ein relativ junges Gebiet der KI. Das Ententeich-Problem ist nur mit sehr hohem Aufwand (also Rechner) loesbar. Eine deterministische Loesung wuerde bestenfalls eine sehr grosse Optimierungsmatrix liefern (bitte bitte nicht fragen, wie das geht: ist schwer und ich habs seit dem 2. Semester verdraengt).
Also zur KI-Loesung: genetische Algos sind Algorithmen, die durch einen Datenstrom gesteuert werden, der auch Chromosom genannt wird (siehe Bio).
Nehmen wir an, der Teich besteht aus 8*8 Feldern. Die Ente kann sich entweder einen Schritt nach rechts oder nach unten bewegen. [Sie folgt der Manhatten Logik, der Weg von A nach B ist immer gleich viele Schritte weit weg, egal welcher Weg gewaehlt wird.] Die Ente muss also 14 Schritte machen, um von rechts oben nach links unten zu kommen.
Repraesentieren wir einmal jeden Schritt durch ein Bit: 0 heisst nach rechts, 1 nach unten. Erzeugen wir eine handvoll Enten (sagen wir mal 10) und initialisieren ihre Gene mit Zufallswerten. Eine Ente ist also durch diesen Algorithmus gekennzeichnet [Attachment "ente1.c"].
Vervollstaendigen wir den See etwas: ein Drittel wird mit Pflanzen, also Entenfutter gefuellt. Aufgabe ist es jetzt die Ente so weit zu optimieren, dass sie moeglichst viel zu fressen bekommt auf ihrem Weg ueber den See. Dazu bedient man sich des Darwinschen Prinzips. Es wird ein See und eine Anzahl Enten erzeugt, die Enten werden auf Ueberlebensfaehigkeit geprueft. Die besten duerfen sich fortpflanzen: dadurch werden die Gene der Enten kombiniert und hoffentlich kommt was besseres raus, der Test in der naechsten Generation zeigt es. [ente2.c]
Interessant an diesem Vorgehen ist, dass man die Ente an den See anpasst. Bei Umweltveraenderungen sind diese Enten also aufgeschmissen. [ente3.c]
viel Spass bei der Entenjagd, Konrad
PS.: richtig lustig wird das erst, wenn man die Algorithmen weiter ausbaut und dem Professor das Vokabular langsam aber sicher peinlich wird.