Entwickler-Ecke
Sonstiges (Delphi) - [Genetisches Programmieren] Interessante Anwendung?
Jack Falworth - So 14.09.03 22:58
Titel: [Genetisches Programmieren] Interessante Anwendung?
also ein Kollege und ich sind gerade dabei uns in die Grundlagen der genetischen Programmierung einzuarbeiten. Da wir uns nach der Einarbeitung an ein größeres Projekt trauen wollen, suchen wir noch eine interessante Anwendung, möglicherweise hat hier jemand etwas Erfahrung darin und kann uns gute Ideen geben.
Wenn möglich nicht einfach nur z.B. Robotik als Vorschlag sondern etwas genauer das Thema beschreiben.
Achja und falls jemand vielleicht gute E-Books oder Seiten über GP auf Deutsch kennt wäre ich ihm sehr verbunden, da wir das Meiste momentan nur auf Englisch haben.
MfG
Jack Falworth
Gausi - Mo 15.09.03 09:38
Was ist den genetische Programmierung? Habe davon noch nie was gehört...
Geht es da um spezielle Programmiertechniken, oder um das Thema Gene?
focus - Mo 15.09.03 11:01
sicher das du nicht KI programmierung meinst?!?
gruss
michael
ps: oder nennt man die auch genetische Programmierung!?!
Andi1982 - Mo 15.09.03 11:06
Hi,
ich glaube die meinen sowas oder????
| Prof. Dr. Wolfgang Banzhaf hat folgendes geschrieben: |
Genetisches Programmieren
Das Genetische Programmieren ist eine neue Methode zur Erzeugung von
Programmen. Hierbei werden Anleihen beim Paradigma der biologischen
Evolution gemacht. Programme werden "`gezüchtet"', indem eine Population
von anfänglichen Zufallsprogrammen durch kontinuierliche Variation und
Selektion der Besseren in die Richtung eines Zielverhaltens gezwungen
wird.
Diese seit Anfang der 90er-Jahre bekannte Methode des maschinellen Lernens ... |
Gausi - Mo 15.09.03 11:24
*schluck* Na dann viel spass beim Programmieren. Ich hab mein erstes "HelloWorld" mal in ne Petrischale getan, mal sehn, ob ich da nächstes Jahr ein neues Office Paket drin habe ;-)
Ne, mal im Ernst:
Hört sich verdammt interessant an. Bin die Tage mal in ne Sendung über maschinelles lernen und so reingezappt. Da sollte ein Roboter lernen, einen Stab zu balancieren, indem er es immer wieder probiert hat, und nur die Meldung "Erfolg" oder "kein Erfolg" erhalten hat. Hat das was damit zu tun?
Viel Spass bei dem Projekt!
lemming - Mo 15.09.03 11:39
| Zitat: |
| Ich hab mein erstes "HelloWorld" mal in ne Petrischale getan, mal sehn, ob ich da nächstes Jahr ein neues Office Paket drin habe |
Der war gut.
Aber jetzt mal im ernst. Wie funktioniert das genau? gibt es da bereits benutzbare Anwendungen oder sowas? Eigentlich machen die sich nichts anderes als das Darwinsche Gesetz zu nutze.
Nachher kommt voll der Kampfkoloos eines Viruses raus der sich SkyNet nennt.
Jack Falworth - Mo 15.09.03 13:00
also erstmal eine kleine Zusammenfassung "Was ist Genetische Programmierung (GP)" für alle die nichts damit anfangen können:
| Zitat: |
Was versteht man unter GP?
Das Genetische Programmieren (GP) wurde 1992 von John R. Koza als Weiterentwicklung
der Genetischen Algorithmen (GA) beschrieben. Die zentrale Frage, die dabei verfolgt wird
lautet:
How can computers be made to do what needs to be done,
without being told exactly how to do it?
Arthur Samuel, 1959
Das Ziel liegt demnach in der automatischen Programmerzeugung. Wie bringe ich also
meinen Computer dazu, sich selbst zu programmieren und was muss ich ihm dazu
notwendigerweise zur Verfügung stellen?
Wie schon vorher bei den GA, sucht sich auch die GP ihr Vorbild in der Natur und versucht,
eine ‚natürliche’ Evolution zu simulieren, bei der nur die Stärksten (in diesem Falle Besten)
erhalten bleiben. Zu Anfang wird demnach eine ‚Initial-Population’ aus zufällig generierten
Computerprogrammen benötigt. Die ‚Individuen’ dieser Population werden nun auf
‚Überlebensfähigkeit’ (sprich also z.B. Korrektheit und Effizienz) getestet. Die
Überlebensfähigkeit bezeichnen wir mit der Fitness und geben den Individuen mit der größten
Fitness die größten Chancen in die nächste Generation übernommen zu werden (entweder
identisch oder modifiziert), wobei nicht auszuschließen ist, das auch ein Individuum mit guter
Fitness einmal verworfen wird. Der Computer versucht also aus der Fülle von möglichen
Programmen das für das vorliegende Problem Geeignetste zu entwickeln. |
@replies:
Nein ich meine nicht Maschinelles Lernen (KI). Maschinelles Lernen ist eine Anwendungsmöglichkeit der GP.
Ich hab auch schon mehrere hundert seiten literatur über das Thema, was halt fehlt ist noch eine interessante, spezielle Anwendung.
@focus: Danke für die Links, doch das Meiste kenne ich schon.
Wäre gut, wenn noch ein paar Vorschläge kommen würden.
MfG
Jack Falworth
Andi1982 - Mo 15.09.03 13:12
Zu arg, wenn man das so ließt ist Terminator vielleicht doch irgendwann mal mehr als nur ein Film :D Hoffentlich lebt Arnold noch so lange dass er uns dann beschützen kann. 8)
Aber würde auch gerne mal ein Beispielprojekt zu diesem Thema sehen. Klingt echt cool und super aufwändig!
Delete - Mo 15.09.03 14:23
Hm, ich denke aber es wird in deinem Fall nur bei der Theorie bleiben. Um in absehbarer Zeit brauchbare Ergebnisse zu bekommen, ist wohl ein Rechnepower nötig den nur Großcomputer bieten können. Es müssen ja mehrer tausend, wenn nicht sogar hunderttausend Versionen erzeugt werden. Diese müssen dann noch getestett und ausgewertet werden.
Aber interessant ist das alle male. Ich habe mal in einem Buich gelesen, da hat einer sowas mit einem einfachen Sortieralgorithmus gemacht. Rausgekommen ist ein Code der besser funktioniert hat als jeder andere Algorithmus, nur verstanden hat den Code keiner. :shock:
Jack Falworth - Mo 15.09.03 15:19
Ich muss hier mal noch loswerden, dass Genetische Algorithmen
nicht das gleiche ist, wie Genetische Programmierung.
Daher kann ich auch mit dem Buch nicht so viel anfangen @focus.
@Luckie: Das mit der Rechenpower war früher ein großes Problem. Mittlerweile nicht mehr so. Außerdem kann man das variabel machen, sodass man Population, Individuenanzahl, Generationenanzahl etc. im Vorfeld festlegen kann, daher sollte das keinen Ärger machen (aber dass das Programm mal 10 min oder so braucht ist klar).
Wäre nett wenn vielleicht jemand was über ne Anwendung schreibt, die mann machen könnte, deshalb ja hauptsächlich das Topic :D.
Damit euch die ein oder andere Idee einfällt hier noch ein paar Punkte, wann man Genetische Programmierung einsetzen sollte:
| Zitat: |
Allgemein ist es sinnvoll mit GP zu arbeiten, wenn ein oder mehrere der folgenden Punkte zutreffen:
- Das Problem kann nicht durch konventionelle mathematische Analyse gelöst werden
- Bei dem Problem ist nicht ganz klar in welcher Beziehung notwendige Variablen
zueinander stehen müssen.
- Es lässt sich nicht sicher vorhersagen wie groß das Programm zur Lösung werden wird
und welche Gestalt es zweckmässigerweise haben sollte
- Zur Erfüllung der Aufgabe genügt bereits eine Annäherung an das exakte Ergebnis
- Zur Lösung des Problems liegen große Mengen an Daten in elektronischer Form vor.
- Eine vorliegende Lösung soll verbessert werden |
MfG
Jack Falworth
UGrohne - Mo 15.09.03 17:20
Wie wäre es denn hiermit: Vorhersage von Aktienkursen, wäre das vielleicht eine Möglichkeit?
Die einzige Bedingung, wo ich mir nicht sicher bin, ob sie erfüllt ist, ist die letzte, also ich weiß nicht, ob es dazu schon etwas konkretes gibt.
Jack Falworth - Mo 15.09.03 21:45
Es müssen ja nicht alle Bedingungen erfüllt sein, sondern min. eine.
Naja Aktien ich weiß nicht. Ich kenn mich damit nicht aus. Vorhersagen zu treffen ist eh so eine Sache (oder tieferes Wissen und Einblick ins aktuelle Geschehen ist da eh nicht so viel zu machen). Außerdem ändern sich die Aktien teilweise so schnell, dass so ein Programm kaum Sinn macht.
Trotzdem danke aber wenn du noch mehr Vorschläge hast, her damit ;)
MfG
Jack Falworth
mhsteuer - Di 16.09.03 10:55
Titel: Literatur
Nur mal so ein Lesehinweis. Eines der Letzten Bücher von Michael Criton (Prey) behandelt dieses Thema. Allerdings nicht wissenschaftlich, sondern nur als Fiction. Ist aber wirklich gut. Was für Euch vielleicht von Interesse ist, ist sein Quellenverzeichnis am Schluss. Criton recherchiert nämlich immer sehr gründlich, bevor er die Bücher schreibt. Da ist meines Wissens nach auch einiges auf Deutsch dabei.
Bis dann, Martin
Jack Falworth - Di 16.09.03 16:26
Hast du vielleicht Titel und/oder ISBN Nummer von dem Buch. Dann schau ich mal ob ich bei Amazon was finde.
Bisher habe ich (fast) ausschließlich englische Bücher gefunden, die gut sein sollen.
MfG
Jack Falworth
mimi - Di 16.09.03 16:50
wenn ich das jetzt richtverstanden habe funktion GP also so:
der rechner such sich aus einer sammlung von exe datei perzufall das passende zusammen. oder ist das falsch ?
wie schnell ist eingentlich das GP sonst könnte du doch die geschwindigkeit nutzen z.b. um wetter vorhersagen zu treffen.
oder du könntes ein programm damit erzeugen was folgende aufgabe bewältigen kann:
ich habe ein foto von mir das gebe ich den rechner und sagen ihn, wie sehe ich in 10 jahren aus?
dafür braucht er natürlich noch zwei oder drei weiter fotos von mir.
oder stimmen analiyen(oder wie das heißt)
Jack Falworth - Di 16.09.03 17:19
nein man hat am anfang ein paar zufällige funktionen für das Problem. nun werden über Replikation, Mutation und Crossover (Kreuzung) neue Funktionen "gezüchtet", die der Lösung schon ein Stück näher kommen. Nun wird das solange weitergeführt, bis im besten fall eine optimale Funktion für das problem rauskommt. Man hat eine sogannte Fitnessfunktion die ständig überprüft, wie gut oder schlecht eine funktion ist. Danach wird entschieden welche funktionen in die nächste generation kommen.
Wettervorhersage ist ein anwendungsgebiet, für uns aber nicht machbar, weil wir keine wetterstation hinterm haus haben, die uns mit aktuellen Informationen versorgt.
mimi - Mi 17.09.03 16:25
könntes du noch genauere bechreiben ?
wie wäres dann mit einem programm womit man webung aus filmen schneiden könnte... die man aufgezeichnet hat ?
lambruco - Mi 17.09.03 16:55
Wie wäre es hiermit:
Die Antwort lautet 42.
Wie lautete die Frage ?
:lol:
Spass beiseite, bin beeindruckt von eurem Vorhaben. Ihr könntet ja mit etwas kleinem anfangen:
z.B. mit einem Programm, das durch ein Labyrinth muss.
mimi - Mi 17.09.03 16:58
AWT:
Die Antwort lautet 42.
Wie lautete die Frage ?
Was ist 40 + 2 ?
genau eine wegfinding programm könntes du doch schreiben.
Jack Falworth - Mi 17.09.03 17:33
@lambruco: das mit dem labyrinth wird oft in Beispielen gezeigt und ist daher schon weit verbreitet.
Aber ich habe ein paar gute anwendungsmöglichkeit gefunden (hat mir auch jemand von ner Uni nen Tipp gegeben):
| Zitat: |
3-COL Problem
Bei dieser Aufgabenstellung ist die Eingabe ein Graph mit Knoten und Kanten
und die Frage ist: kann man die Knoten mit 3 Farben so färben, daß 2
verbundene Knoten nicht dieselbe Farbe haben. 3-COL bzw. k-COL ist von
praktischer Bedeutung bei der Netzwerkplanung z.B. von Mobilfunknetzbetreibern.
Bei diesem Problem, treten 2 Problemtypen auf: 1. Entscheidungsproblem:
Ist der Graph 3-färbbar und 2. Berechnungsproblem: berechne eine korrekte 3- Färbung. |
| Zitat: |
Traveling Salesperson Problem (TSP)
Gegeben ist ein Strassennetz mit Städten und Entfernungen (gewichteter Graph).
Fragestellung ist, gibt es einen Zyklus, der alle St¨adte beinhaltet und kleiner als eine vorgegebene Schranke ist, bzw. berechne eine Tour, die kleiner als die Schranke ist bzw. die minimal ist. |
Gausi - Do 18.09.03 20:12
| Zitat: |
Wie wäre es hiermit:
Die Antwort lautet 42.
Wie lautete die Frage ?
|
Hehe, soo dumm ist dieses Beispiel gar nicht! Diejenigen, die wissen, woher ich das habe, werden auch wissen, dass genau dieses Problem wohl das beste Beispiel für genetische Programmierung ist!
Schliesslich wurde zur Lösung dieses Problems der größte Computer aller Zeiten gebaut. Das Programm, was auf diesem abläuft, ist wohl wirklich nach dem Prinzip der genetischen Programmierung gestrickt.
Der Name dieses Großrechners ist übrigens Erde. Dummerweise wude dieser Computer 5 Minuten vor Ende der Rechenzeit von den Vogonen zerstört, weil durch unser Sternensystem eine Hyperraum-Expreß-Route gebaut werden sollte. Aber ich schweife ab....
Die Probleme 3COL und TSP kenne ich nur zu gut. Und dann fallen mir noch weitere ein, die genauso schwer sind wie diese: SAT, 3SAT (nein, nicht die Fernsehsender...) oder KNAPSACK. Kurz gesagt, alles was sich so NP-Vollständig schimpft.
Und zu dem Wegfindungs-Programm: Ich glaube auch, dass das nicht besonders sinnvoll ist, denn da gibt es schon schnelle Standard-Algorithmen. Ausserdem ist das Problem "Finde einen Weg" sehr einfach. Und dann mit "Genetischer Programmierung" daranzugehen ist ungefähr so, als würde man mit Atombomben auf Spatzen schiessen. (Kanonen reichen mir da nicht :D)
Jack Falworth - Do 18.09.03 21:17
natürlich gibt es schon standart algorithmen dafür.
aber nehmen wir mal an jemand möchte alle länder der welt besuchen (193). um alle kombinationen auszurechnen müsste man 192! Möglichkeiten berechnen. Dann wird das selbst für die algorithmen ein problem. Da würde Genetische Programmierung von großem nutzen sein, da bei jeder neuen Generation, zig tausende Möglichkeiten wegfallen und man eine immer bessere Kombination erhält.
Aber der Einwand ist ok. Hast du vielleicht ein anspruchsvolleres Problem oder eine weitergehende Aufgabenstellung dafür? Bin für alles offen.
MfG
Jack Falworth
Gausi - Do 18.09.03 21:58
nene, ich glaube, da hast du mich mißverstanden. Mit Wege-Problem meinte ich den Vorschlag mit dem Labyrinth ein paar Posts früher. Dafür kann man einfach Breitensuche auf Graphen nehmen, und der Weg durch das Labyrinth is ruckzuck gefunden.
Genauso das mit der Werbung rausschneiden. Ich weiss zwar nicht, wie das geht, aber aus Sicht eines Mathe-informatik-Studenten ist das kein prinzipielles Problem. Ein Ansatz wäre z.B. über die Lautstärke zu gehen (Werbung ist ja tatsächlich immer lauter bzw. basslastiger als der rest). Oder das Logo des Senders zu erkennen, was bei Werbung ausgeblendet wird.
Für TSP gibt es zwar auch Standard-Algorithmen, und wenn mein Info-Prof mich nicht angelogen hat, dann kann man das mit heutigen Rechnern für ungefähr 120 Städte exakt lösen. In ca. 18 Monaten kann man dann eine Stadt dazupacken. Alles andre sind Näherungslösungen, die eine mehr oder weniger gute Lösung ausgeben. Und ganau da liegt ja der/ein Ansatz für genetische Programmierung, wenn ich das richtig verstanden habe.
Ich finde also, dass ihr euch schon an TSP ranmachen solltet. Ich denke, das ist anspruchsvoll genug ;-)
Mich würde auch mal interessieren, was dabei rauskommt...aber wenn man schon das Ergebnis bei Sortieralgorithmen nicht versteht, dann kann man das bei TSP wohl ganz vergessen...
Viel Erfolg weiterhin!
Jack Falworth - Do 18.09.03 23:15
hmm da hab ich mich wohl verlesen ;)
das mit dem labyrinth und mit der Werbung find ich auch nicht so passend um mit GP da ran zu gehen.
das mit TSP werden wir dann auch wahrscheinlich machen.
Müssen zunächst aber erst mal etwas theoretisches wissen pauken um überhaupt anfangen zu können.
Das ganze wird sich wohl auf ein halbes bis dreiviertel jahr ausdehnen, aber das wird sicherlich auch ganz interessant.
| Zitat: |
| ...aber wenn man schon das Ergebnis bei Sortieralgorithmen nicht versteht, dann kann man das bei TSP wohl ganz vergessen... |
dieser satz hat mich etwas verwirrt. Was soll ich damit anfangen ?
Werde euch dann auf dem Laufenden halten, wenn wir mit dem Projekt anfangen (natürlich nur wenn ihr wollt :D )
MfG
Jack Falworth
cbs - Sa 20.09.03 08:48
huhu
wie wärs damit? beam me up schrotti :lol:
bastelt euch nen elektronik simulator oder so was und lasst euer genetisches programm technologien erfinden. man kann ja zur kontrolle mit was kleinem anfangen. zb ein handgesteuerten 2 Hz prozessor :rofl:
Mentor86 - Sa 20.09.03 15:18
Also, wir habe in der Schule mit unserem Lehrer einen zellulären Automaten nach der von neumann Funktion erstellt.
Kannst ja ein bisschen googeln, habe nämlich grad keine Zeit es lang zu erklären. So schwer wars auch nicht.
Mentor86 - Sa 20.09.03 15:24
Also sagen wir mal so ein Stringgrid mit x Spalten und 2 Zeilen.
Beim Start des Programms werden zufällig einige Zellen der ersten Spalte den Wert 1 erhalten. Diese aktiven Zellen pflanzen sich dann folgendermaßen fort:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:
| if (stringgrid1.Cells[x,0]='1') xor (stringgrid1.cells[x+2,0]='1') then begin stringgrid1.cells[x+1,1]:='1'; end else begin stringgrid1.cells[x+1,1]:='0'; end; x:=x+1; end; for i:=0 to 50 do begin stringgrid1.cells[y,0]:=stringgrid1.cells[y,1]; y:=y+1; end; |
Also: Eine passive zelle wird im nächsten Evolutionsschritt aktiv, wenn
entweder der rechte
oder der linke Nachbar aktiv ist.
Man definiert: 1=aktiv=lebendig
0=passiv=tot
Die Zählschleife zählt bis 50, weil mein Stringgrid 50 Spalten hat. Muss angepasst werden.
So kannst du einen unendlich langen Evolutionsvorgang beobachten, wenn du genung Zeit hast.
Das Prog ist aber eher was für Einsteiger, wie mich.
[/b]
mad_progger - Di 13.01.04 13:27
Wie weit seid ihr inzwischen?
Ich habe nämlich beim Bundeswettbewerb Informatik nun eine Aufgabe welche dem TSP gleichkommt, jedoch etwas erweitert wurde. Deswegen würde mich das interessieren wie das der Computer errechnet hätte bzw. was ihr ihm für Funktionen zur Verfügung gestellt habt.
iGoA - Di 15.06.04 09:15
@an den Anwendungsbeispielsucher:
Oben stand ein gutes Anwendungsbeispiel: Verbesserung von Sortieralgorithmen. Find ich sehr eindrucksvoll als Anwendung von GP.
Kann man mit GP eigentlich auch Programme erzeugen, die später mit dem User interagieren sollen? Da stell ich mir die Überprüfung der "Fitness" ziemlich schwierig vor.
bash1 - Do 02.12.04 17:43
ehm ja um das thema ma nen bisschen aufzufrischen.. weiß ja nich wie weit ihr schon seid mit eurem tsp projekt, wolltet euch ja nen dreiviertel jahr dransetzen ^^
wir machen genau das was ihr sucht in unserm leistungskurs, d.h. das travelling-salesman-problem mit hilfe des genetischen programmierens! dazu kommt noch, dass wir seit beginn des lks nur objektorientiert programmieren.
kann ja ma kurz unser gerüst vorstellen:
1. anwender unit: da kommzt eben das unwichtige am schluss rein ^^
2. baseclss: da wir später bei den programmen alle möglichen arten von objekten einsetzen wollen (bsp. integer, strings, usw. aber auch bilder, listen etc.), haben wir uns die unit geschrieben, die vergleicht kopiert und solche typen erstellt auf die wir später immer wieder zugreifen werden!
3. listclss: ist ja klar was hier drin steht, hier wird ne komplette liste erstellt , sogar mit sortlist (hey, hey ;) ).. naja brauchen wir fürs genetische programmieren
4. geneticclss: eigentlich die wichtigste klasse. sie wird wie auch alle anderen klassen so geschrieben, dass man sie für fast jedes genetische problem nutzen kann. sehr vorteilhaft...
5.grdatenclss: hier stehen alle wichtige daten drin die benötigt werden um das programm hinterher zum laufen zu bringen, und auch für die zeichung aufm image . wir wollen die städterundreisen ja sehr detailliert darstellen.
naja ich glaub das wars auch schon... wenn noch einer hilfe braucht, bzw. das programm haben will kann sich ja hier melden. aber ganz fertig bin ich selbst noch nich ^^, vielleicht brauch ich später noch hilfe :)
gruß bash1
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!