| Autor |
Beitrag |
mimi
      
Beiträge: 3458
Ubuntu, Win XP
Lazarus
|
Verfasst: 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.
_________________ MFG
Michael Springwald, "kann kein englisch...."
|
|
Jack Falworth 
      
Beiträge: 222
Win XP Pro, Slackware 10.0
D5 Enterprise, C++, ABAP
|
Verfasst: 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. |
_________________ Andere zu kritisieren ist mitunter eine Möglichkeit, sich selbst ins bessere Licht zu setzen.
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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  )
_________________ We are, we were and will not be.
|
|
Jack Falworth 
      
Beiträge: 222
Win XP Pro, Slackware 10.0
D5 Enterprise, C++, ABAP
|
Verfasst: 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
_________________ Andere zu kritisieren ist mitunter eine Möglichkeit, sich selbst ins bessere Licht zu setzen.
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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!
_________________ We are, we were and will not be.
|
|
Jack Falworth 
      
Beiträge: 222
Win XP Pro, Slackware 10.0
D5 Enterprise, C++, ABAP
|
Verfasst: 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  )
MfG
Jack Falworth
_________________ Andere zu kritisieren ist mitunter eine Möglichkeit, sich selbst ins bessere Licht zu setzen.
|
|
cbs
      
Beiträge: 207
Erhaltene Danke: 1
|
Verfasst: Sa 20.09.03 08:48
huhu
wie wärs damit? beam me up schrotti
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 
|
|
Mentor86
      
Beiträge: 46
|
Verfasst: 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.
_________________ Man kann Probleme nicht mit Denkweisen lösen, die zu ihnen geführt haben.
|
|
Mentor86
      
Beiträge: 46
|
Verfasst: 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]
_________________ Man kann Probleme nicht mit Denkweisen lösen, die zu ihnen geführt haben.
|
|
mad_progger
      
Beiträge: 49
WIN XP, Linux
D7 Pro
|
Verfasst: 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
      
Beiträge: 103
Alle Win´s
D5 Prof
|
Verfasst: 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.
_________________ "Diner for One" objektorientiert:
"The same method as last year, Ms. Sophie?" (was für´n Schwachsinn)
|
|
bash1
Hält's aus hier
Beiträge: 2
WIN XP
D7 Enterprise
|
Verfasst: 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
|
|
|