Darwin (Evolutions-) Simulation mit

1
2
3
4
…
- 5
- 6
- 7
- 8
- 9
10

Werbeanzeige

NachoMan

Community-Fossil

Beiträge: 3 885

Wohnort: Berlin

Beruf: (Nachhilfe)Lehrer (Mathematik, C++, Java, C#)

24.02.2012, 10:26

Ich finde das Thema Evolutionssimulation sehr interessant und habe auch schon lang vor soetwas zu entwickeln. Ich hab aber gerade schon zwei Projekte laufen und dann noch die Schule (das Leben eines Programmierers ist einfach zu kurz

). Deshalb könnt ich dir jetzt auch nicht helfen.
Und selbst wenn dir ein paar Programmierer helfen würden, hielt ich es für unwahrscheinlich eine realistische Simulation, die auch noch Nicht-Informatiker verstehen sollen, in einer Woche zum laufen zu bringen. Halte uns aber bitte auf dem Laufenden.

Achja, darf ich dich anschreiben wenn ich mit meinem Projekt anfange? Ein paar zusätzliche Informationen von einem Fachmann sind da bestimmt nützlich. Du kriegst dann natürlich auch eine Kopie.

"Der erste Trunk aus dem Becher der Erkenntnis macht einem zum Atheist, doch auf dem Grund des Bechers wartet Gott." - Werner Heisenberg
Biete Privatunterricht in Berlin und Online.
Kommt jemand mit Nach oMan?

Zum Seitenanfang

CharlesDarwin

Frischling

Beiträge: 25

Beruf: Visionär

24.02.2012, 10:39

Zitat

Nun, dann hast du aber nicht sehr gründlich gesucht.

Das habe ich auf die Schnelle gefunden:

Davon hatte ich schon einiges gesehen. Ich denke ich will "plastischere" Geschöpfe, an deren Körperbau genetische Merkmale erkennbar sind.

Zitat

Und selbst wenn dir ein paar Programmierer helfen würden, hielt ich es
für unwahrscheinlich eine realistische Simulation, die auch noch
Nicht-Informatiker verstehen sollen, in einer Woche zum laufen zu
bringen. Halte uns aber bitte auf dem Laufenden.

Harausforderung angenommen.

Ich sag mal so im Sommer wird ein Prof von uns pensioniert. Die stellen dafür einen neuen Dozenten fest an. Da ich plane mich nach der Promotion zu habilitieren bin ich da sehr ambitioniert.

Zitat

Achja, darf ich dich anschreiben wenn ich mit meinem Projekt anfange? Ein paar zusätzliche Informationen von einem Fachmann sind da bestimmt
nützlich.

Am Freitag werde ich so weit fertig sein. Und ich stelle gerne den gesamten Quellcode zur Verfügung. Dafür ist ja Anschauungsmaterial gedacht.

LG

EDIT:
Wie entkopplett man bei XNA die Framerate? Ich habe konstante Frames egal wie viele "Billardkugeln" ich simuliere.

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

24.02.2012, 11:10

Und das Verhalten der Lebewesen?
Sollte das nicht auch ein wesentlicher Aspekt sein, der durch die Evolution optimiert wird?
Klar, das kann man nicht gut visualisieren. Aber bei "Räuber-Beute" kommt es doch stark auf das Verhalten an.
Sowas könnte man durch neuronale Netze realisieren, die das Verhalten steuern. Diese könnte man zufällig mutieren lassen oder die Netze zweier Lebewesen "kreuzen".

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

CharlesDarwin

Frischling

Beiträge: 25

Beruf: Visionär

24.02.2012, 11:37

Zitat

Und das Verhalten der Lebewesen?

Sollte das nicht auch ein wesentlicher Aspekt sein, der durch die Evolution optimiert wird?

Klar, das kann man nicht gut visualisieren. Aber bei "Räuber-Beute" kommt es doch stark auf das Verhalten an.

Sowas könnte man durch neuronale Netze realisieren, die das Verhalten steuern. Diese könnte man zufällig mutieren lassen oder die Netze zweier Lebewesen "kreuzen".

Das Verhalten soll erst mal durch den Körperbau bestimmt werden. Möglicherweise lasse ich die "Zellen" sich gegenseitig erregen. Das wäre dann ein neuronales Netz?

Es soll folgende Zelltypen geben:
Photosynthese Zellen => Energie
Fresszellen =>Energie und Baumaterial
Eizellen => Fortpflanzung
Antriebszellen => Bewegung des "Lebewesens"
Panzerzellen => Schutz vor Fresszellen

Die Variablen für das Genom habe ich fertig.

C#-Quelltext

   int[,] Gen_0_Zell_Typ = new int[AnzahlId, 5];
        bool[,] Gen_0_Zell_Enabled = new bool[AnzahlId, 5];
        int[,] Gen_1_Zell_Typ = new int[AnzahlId, 4];
        bool[,] Gen_1_Zell_Enabled = new bool[AnzahlId, 4];
        int[,] Gen_2_Zell_Typ = new int[AnzahlId, 3];
        bool[,] Gen_2_Zell_Enabled = new bool[AnzahlId, 3];
        int[] Gen_ZellenGesamt = new int[AnzahlId];

Es bildet 3 Reihen Zellen mit den versch. Eigenschaften. Die Anordnung erfolgt hexagonal. Die äußeren Reihen werden vertikal gespiegelt.

So ergeben sich max 19 Zellen pro individuum.
Bisher habe ich vor die Evolution ohne kreuzen zu realisieren. Durch "klonen und mutieren" (Parthenogenesis).

LG

Zum Seitenanfang

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

24.02.2012, 11:56

Kreuzung wäre nicht sonderlich schwer umzusetzen. Vom Prinzip willst du doch eigentlich sowas hier grafisch umsetzen oder nicht? Die Evolution dahinter wäre dann je nach Komplexität deiner Simulation noch relativ einfach umzusetzen. Ich finde eher den grafischen Aspekt dahinter schwierig. Wie willst du das alles darstellen? Aus einfachen Kreisen und Punkten erkennt man ja noch relativ wenig, was dann wieder wenig anschaulich wäre.
Ansonsten wäre die Wator-Simulation die David angesprochen hat sicherlich mal einen Blick wert. Dabei kannst du dir ein Grundprinzip abgucken. Die Parameter die die Simulation dann steuern könntest du dann evolutionär bestimmen. Dann könntest du deine Simulation zwischen den Generationen pausieren lassen, und eine Möglichkeit einbauen, die einzelnen Werte der Agenten anzuzeigen. Vielleicht noch die Durchschnittswerte der einzelnen Parteien. Dann könnte man dadurch sehen, wie sie sich weiterentwickeln. So etwas sollte machbar sein und müsste doch eigentlich auch in die Richtung von dem gehen, was du am Ende gerne haben möchtest.

„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Zum Seitenanfang

CharlesDarwin

Frischling

Beiträge: 25

Beruf: Visionär

24.02.2012, 12:22

Zitat

Kreuzung wäre nicht sonderlich schwer umzusetzen. Vom Prinzip willst du doch eigentlich sowas hier grafisch umsetzen oder nicht?

Genua so ist es.

Zitat

die Wator-Simulation die David angesprochen hat sicherlich mal einen Blick wert

Habe ich mir schon angeguckt.

Ich will die Wator-Simulation praktisch mit einem evolutionären Algorithmus kombinieren. Haie und Fische sollen aus Zellhaufen bestehen, die mutieren und interagieren. Denke das ist am einfachsten.

Ich will einen Überlebenskampf vorführen.

Sonst ist das Interesse schnell weg.

Ein Test hat ergeben dass ich bis 500 Zellen flüssig berechnen kann. Das reicht noch nicht.

Ich will den Abstand aller Zellen mal versuchen zu speichern und dann linear eine angenommene maximale Geschwindigkeit abziehen. So kann ich mir bei 80% der Fälle den Pythagoras sparen. :hmm:

LG

EDIT:

Ist es möglich Sprites zu Laden statt normalen Texturen oder muss ich da ganz viele Texturen nacheinander zeigen?

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

24.02.2012, 13:11

Der Pythagoras ist nicht dein Problem.

Im Moment gehst du sicher alle Paare von Partikeln durch und testest, ob sie sich nah genug kommen?
Das bedeutet quadratischer Aufwand, oder wie wir Informatiker sagen, O(N²).

Wenn du 500 Zellen hast, musst du (500*499)/2 Paare testen, das sind knapp 125000!
Wenn du nun 1000 Zellen hast, sind es nicht doppelt so viele Paare, sondern 4x so viele.

Um richtig viele Partikel zu simulieren, musst du eine räumliche Datenstruktur benutzen. Ein reguläres Gitter täte es hier. Im Prinzip teilst du den Raum in kleine Quadrate auf (wie Rechenkästchen). In jedem führst du eine Liste über die Partikel, die darin enthalten sind. Nun kannst du diese Struktur benutzen, um schnell eine Liste potenzieller Kollisionen zu erhalten, nämlich können Partikel nur dann kollidieren, wenn sie sich im selben Kästchen oder in benachbarten Kästchen befinden.

Hier siehst du schon, dass der Teufel im Detail steckt.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

CharlesDarwin

Frischling

Beiträge: 25

Beruf: Visionär

24.02.2012, 13:45

Zitat

Wenn du 500 Zellen hast, musst du (500*499)/2 Paare testen, das sind knapp 125000!

Wenn du nun 1000 Zellen hast, sind es nicht doppelt so viele Paare, sondern 4x so viele.

In der 2. Schleife zähle ich ab dem Index der ersten Schleife dadurch lässt sich das bereits etwas reduzieren. Aber im Prinzip hast du recht.

Zitat

Um richtig viele Partikel zu simulieren, musst du eine räumliche
Datenstruktur benutzen. Ein reguläres Gitter täte es hier. Im Prinzip
teilst du den Raum in kleine Quadrate auf (wie Rechenkästchen). In jedem
führst du eine Liste über die Partikel, die darin enthalten sind. Nun
kannst du diese Struktur benutzen, um schnell eine Liste potenzieller
Kollisionen zu erhalten, nämlich können Partikel nur dann kollidieren,
wenn sie sich im selben Kästchen oder in benachbarten Kästchen befinden.

Aha, ja das klingt logisch.
Frage ich in der Schleife dann statt den Zellen die Kästchen ab und bewege die Partikel die dort gelistet sind?Gibt es ein Tutorial dazu? Oder ein Schlagwort zum suchen.

Zitat

Hier siehst du schon, dass der Teufel im Detail steckt.

Deshalb bin ich hier.

Nur jetzt bin ich für 2 Stunden beim Sport.
Ich poste mal meine momentane Hauptschleife. Das mit der lienaren Reduzierung der Entfernung hat die Leistung auf über 1000 Partikel gesteigert.

C#-Quelltext

            for (n1 = 0; n1 < MaxZellenGesamt; n1++)
            {
                if (Z_Typ[n1] >-1)//Zellen mit dem Typ -1 sind deaktiviert
                {
                    AnzZellen++;//Zellen Zählen
                    Update_ZellEngine_ZellAktivität(n1);//Zellaktivitäten
                    for (n2 = n1; n2 < MaxZellenGesamt; n2++)
                    {
                        if (Z_Typ[n2] >-1)
                        {
                            Z_Distanz[n1, n2]--;//Lineare Distanzoperation zur Einsparung von Rechenleistung
                            if (Z_Distanz[n1, n2] < 14)//(Die Größe aller Zellen ist 8)
                            {
                                Z_Distanz[n1, n2] = Vector2.Distance(Z_Position[n1], Z_Position[n2]);
                                if (Z_Distanz[n1, n2] < (float)9.6)
                                {
                                    //Zellkontakt
                                    Update_ZellEngine_Physik(n1, n2);//Hier dann der Pythagoras sowie der Austausch von Nahrung und Baumaterial
                                    if (Z_Schlafen[n1] == 1)//Zellen sind nur alle 10 Frames aktiv beim Zellkontakt.
                                    {
                                        Update_ZellEngine_Zellkontakt(n1, n2);
                                        Update_ZellEngine_Zellkontakt(n2, n1);
                                    };
                                };
                            };
                        };
                    };
                };
            };

Vielleicht sehen die Profis hier ja noch etwas, dass sich verbessern lässt. Nach dem Sport mache ich mich an die "Gene" und "Zellen".
Ein Gitternetz wie oben beschrieben mache ich wenn die Simulation mit 1000 Zellen läuft. Wie Groß sollte ein Gitter sein, gemessen an der Zellen/Partikel-Größe.

Kann ich auch das ganze Projekt hier hochladen?

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

24.02.2012, 14:02

Den Wertebereich deiner 2. Schleife habe ich schon mit eingerechnet.

Vector2.Distance berechnet sicherlich die Vektorlänge mit Wurzelziehen, nicht?
Sicher gibt es auch eine Funktion, die die Wurzel nicht zieht und dir die quadrierte Länge liefert. Dann nimmst du die und vergleichst nicht mit 9.6, sondern mit 9.6² = 92.16.
Das dürfte dir ein bisschen mehr Leistung geben.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

24.02.2012, 15:25

Genau die gibt es. Hier kannst du dir was zur Methoden ansehen. Wie groß du dein Gitter wählst, bzw wie viele Gitterzellen du dir anlegst, dass musst du selbst raus finden. Du solltest einen Wert wählen, bei dem du einen guten Mittelweg zwischen Anzahl der Zellen vom Gitter und Anzahl der Objekte in den Zellen hast. Wenn du 100 Agenten in deiner Simulation hast, dann macht es sicherlich wenig Sinn, wenn du 1000 Zellen im Gitter hast. Dabei verschwendest du dann zu viel Aufwand, um die Zellen untereinander zu testen. Das kannst du aber auch leicht durch ausprobieren herausfinden. Du hast eine Anzahl an Agenten die du anstrebst, implementierst dir dein zweidimensionales Gitter und machst einfach einen Parameter für die Anzahl der Gitter. Dann kannst du mit den Werten ein bisschen experimentieren und siehst selbst welche Werte sich eignen. Du musst dir halt einfach eine Art Schachbrett vorstellen. Bewegt sich ein Agent aus einer Zelle in eine benachbarte Zelle, so wird er aus der Liste der vorherigen gelöscht und in die Liste der neuen Zelle eingefügt.
Zu O(n^2): Es bedeutet weniger, dass du bei n Elementen eine genaue Laufzeit n^2 bekommst, sondern viel mehr eine Abschätzung des Laufzeitverhaltens. Dabei betrachtet man normalerweise auch nur sehr große n und so kommt man dann zu einer quadratischen Laufzeit. Dazu könnte man noch um einiges mehr erklären, aber an sich ist nur wichtig, dass hier weniger ein Konkreter Wert für die Laufzeit bestimmt wird, als ein Maß dafür, wie schnell ein Algorithmus arbeitet.

„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Zum Seitenanfang

Werbeanzeige

1
2
3
4
…
- 5
- 6
- 7
- 8
- 9
10

spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung