Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ss20:plagen-simulation [2020/08/26 16:39]
valentingiogoli [Separation]
+++ ss20:plagen-simulation [2020/09/08 17:00] (aktuell)
valentingiogoli [2.1 Performance Optimierung]
@@ Zeile 1: / Zeile 1: @@
-====== Plagenbekämpfung ======
+[[projekte_im_sommersemester_2020|← Zurück zur Projektauswahl]]
+====== Simulation von Heuschreckenschwärmen ======
-==== Projektziel ====
-Wir wollen die Verbreitung von Heuschreckenschwärmen abhängig von unterschiedlichen Parameter simulieren und in einem Spiel - ähnlich wie \\ [[https://www.ndemiccreations.com/en/22-plague-inc | Plague Inc.]] - visualisieren. Dabei wollen wir möglichst realitätsnah bleiben und aktuelle Erkenntnisse mit einbeziehen.
 ==== Teilnehmer*innen ====
@@ Zeile 22: / Zeile 22: @@
 **Was ist das Ziel unseres Projekts?**
-Wir wollen inspiriert von der aktuellen Heuschreckenplage in Ostafrika Heuschreckenplagen simulieren und visualisieren. Dabei betrachten wir das Schwarmverhalten der Heuschrecken und äußere Einflussfaktoren wie Futterquellen und Bekämpfung (z.B. durch Pestizide). Dabei wollen wir möglichst realitätsnah bleiben und aktuelle Erkenntnisse mit einbeziehen.
+Wir wollen inspiriert von der aktuellen Heuschreckenplage in Ostafrika Heuschreckenplagen simulieren und visualisieren. Dabei betrachten wir das Schwarmverhalten der Heuschrecken und äußere Einflussfaktoren wie Futterquellen und Bekämpfung (z.B. durch Pestizide). Wir wollen hierbei möglichst realitätsnah bleiben und aktuelle Erkenntnisse mit einbeziehen.
 **Was ist Schwarmverhalten?**
-Schwarmverhalten bezeichnet den Zusammenschluss von Tiere zu Aggregationen, dabei bewegen sich die Individuen in eine gemeinsame Richtung.Daraus ergeben sich Vorteile bei der Nahrungssuche und erhöhter Schutz vor Fressfeinden. Typische Schwarmtiere sind Fische, Vögel und Insekten wie die Wander- und Wüstenheuschrecken.
+Schwarmverhalten bezeichnet den Zusammenschluss von Tiere zu Aggregationen, dabei bewegen sich die Individuen in eine gemeinsame Richtung. Daraus ergeben sich Vorteile bei der Nahrungssuche und erhöhter Schutz vor Fressfeinden. Typische Schwarmtiere sind Fische, Vögel und Insekten wie die Wander- und Wüstenheuschrecken.
 **Wie funktioniert die Schwarmbildung bei Heuschrecken?**
@@ Zeile 53: / Zeile 52: @@
 {{:ss20:all-together.gif?direct|}}
-==== Separation ====
-<code>
-    def seperation(self,boid,ind): #gleich dem allignment, bloß mit der der differenz dem normierten Abstand(differenz der Positionen)
-        dist = Vector(0,0)
-        count = 0
-        for i in ind[0]:
-            if boid[i].position != self.position:
-                dist += (self.position - boid[i].position)/np.linalg.norm(boid[i].position - self.position)
-                count += 1
-        if count > 0 :
-            dist /= count
-            dist = (dist /np.linalg.norm(dist)) * self.max_speed
-            dist -= self.velocity
-            dist = (dist /np.linalg.norm(dist)) * self.max_force
-        self.acceleration += dist
-</code>
-{{:ss20:seperation.gif?direct|}}
@@ Zeile 96: / Zeile 76: @@
 ==== Cohesion ====
+<code>
+    def cohesion(self,boid,ind): #gleich dem allignment, bloß mit der positon
+        center = Vector(0,0)
+        count = 0
+        for i in ind[0]:
+            if boid[i].position != self.position:
+                center += boid[i].position
+                count += 1
+        if count > 0:
+            center /= count
+            center -= self.position
+            center = (center /np.linalg.norm(center)) * self.max_speed
+            center -= self.velocity
+            center = (center /np.linalg.norm(center)) * self.max_force
+        self.acceleration += center
+</code>
 {{:ss20:cohesion.gif?direct|}}
+==== Separation ====
+<code>
+    def seperation(self,boid,ind): #gleich dem allignment, bloß mit der der differenz dem normierten Abstand(differenz der Positionen)
+        dist = Vector(0,0)
+        count = 0
+        for i in ind[0]:
+            if boid[i].position != self.position:
+                dist += (self.position - boid[i].position)/np.linalg.norm(boid[i].position - self.position)
+                count += 1
+        if count > 0 :
+            dist /= count
+            dist = (dist /np.linalg.norm(dist)) * self.max_speed
+            dist -= self.velocity
+            dist = (dist /np.linalg.norm(dist)) * self.max_force
+        self.acceleration += dist
+</code>
+{{:ss20:seperation.gif?direct|}}
+===== 2.1 Performance Optimierung =====
+In der grundlegenden Implementierung des Algorithmus prüft jeder Boid alle anderen Boids aus der flock Liste, um zu berechnen, ob sie sich innerhalb eines vorgegebenen Radius befinden und somit als Nachbarn gelten.
+Hierbei werden in jedem Schritt viele vermeidbare Berechnungen ausgeführt, weshalb der Code bei n > 50 Boids sehr langsam wird. Ohne weitere Bearbeitung wäre der Algorithmus sehr ineffizient mit einer Komplexität von O(n^2).
+Um dem Entgegen zu wirken haben wir uns entscheiden KD-Trees zu verwenden. KD-Trees sind Suchbäume um Punkte in einem k dimensionalen zu organisieren. In unserem Projekt ist k = 2. KD-Trees sind besonders praktisch für die Suche nach den nähsten Nachbarn oder der Suche innerhalb eines bestimmten Abstands.
+In unserem Code haben wir sklearn library verwendet. Durch die Implementierung des KDTree aus sklearn.neighbors werden nur noch die Nachbarn eines Boids innerhalb eines Radius r = 50 betrachtet.
+Hierdurch konnten wir, je nach verfügbarer Rechenleistung, Schwärme mit bis zu n = 500 Boids simulieren.
+[[https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html#sklearn.neighbors.KDTree| weitere Einzelheiten zu den KD-Trees von scikit-learn]]
+===== 3. Fazit =====
+Wir hatten uns mehr vorgenommen, als wir schlussendlich erreicht haben. Ursprünglich wir wollten eine interaktive Visualisierung von Heuschreckenplagen realisieren. Im Laufe der Zeit haben wir den interaktiven Aspekt etwas vernachlässigt und uns dafür auf die Simulation des Schwarmverhalten fokussiert. Dabei haben wir einiges über Schwärme und objektorientierte Programmierung in Phyton gelernt.

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge