Mathesis Wiki

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
[[projekte_im_sommersemester_2020|← Zurück zur Projektauswahl]]

====== Simulation von Heuschreckenschwärmen ======

==== Teilnehmer*innen ====

Benedikt \\
Valentin \\
Juanita \\
Emma

==== Projektseiten ====
[[Research Plagensimulation]]\\
[[Projektplan Plagensimulation]]\\
[[Protokoll Plagensimulation]]\\
[[Code Plagensimulation]]\\

====== Dokumentation ======

===== 1. Projektbeschreibung =====

**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). 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.

**Wie funktioniert die Schwarmbildung bei Heuschrecken?**

Panik und Nahrungsmangel lösen bei Heuschrecken Kannibalismus aus. Die kollektive Bewegung im Schwarm verringert das Risiko des Kannibalismus für die einzelnen Individuen. Dabei verfolgen die Tiere ihre Artgenossen und fliehen gleichzeitig vor denen, die sie selbst jagen.

Die Schwarmbildung wird durch räumliche Nähe zu Artgenossen ausgelöst und führt zu Veränderung in Gestalt und Verhalten. Die unterschiedliche Färbung von Einzelgängern (solitären Phase) und Schwarmtieren (gregäre Phase) lässt sich in der folgenden Grafik gut erkennen.

{{:ss20:leben-einer-heuschrecke.jpg?direct|}}
Grafik aus [[https://www.nationalgeographic.de/tiere/2020/05/heuschreckenplage-in-ostafrika-die-insekten-mit-den-zwei-gesichtern]]
===== 2. Implementierung von Schwarmverhalten =====

Schwarmverhalten lässt sich mithilfe von **boids** (von engl. "bird-oid object") simulieren. Boids wurden 1986 von Craig Reynolds entwickelt. Sie bestehen aus miteinander interagierenden Agenten, die mithilfe von drei einfachen Regeln **emergentes Verhalten** darstellen. Diese drei Regeln sind:

  * **Separation**: wählt eine Richtung, die einer Häufung von Boids entgegenwirkt
  * **Angleichung**: wählt eine Richtung, die der mittleren Richtung der benachbarten Boids entspricht
  * **Zusammenhalt**: wählt eine Richtung, die der mittleren Position der benachbarten Boids entspricht
 

{{:ss20:boidsthreerules.png?direct|}}
Grafik aus [[http://coffeepoweredmachine.com/wp-content/uploads/2013/08/boidsThreeRules.png]]

Im Folgenden einige GIFs zu unserer eigenen Implementierung dieser Regeln, zunächst alle kombiniert und dann die drei Regeln im Einzelnen.

{{:ss20:all-together.gif?direct|}}




==== Alignment ====
<code>
def alignment(self,boid,ind):
        avg = Vector(0,0)
        count = 0
        for i in ind[0]: #Für alle Elemente in Ind (Nachbarn innerhalb bestimmtem Radius/ Die k nähesten Nachbarn) wird gecheckt ob ihre Position der Eigenen entspricht(nur bei sich sebst der Fall)
            if boid[i].position != self.position:
                avg += boid[i].velocity #Alle Geschwindigkeitsvektoren der Nachbarn werden zusammenaddiert
                count += 1 #Anzahl der Nachbarn wird gezählt
        if count > 0: #Bei mehr als Null Nachbarn wird der Durchschnittsvektor berechnet, normiert und mit der maximal Geschwindigkeit multipliziert. Anschließend wird der eigene Geschwindigkeitsvektor subtrahiert und der Vektor wird ein weiteres mal Normiert und mit der maximal Kraft multipliziert.
            avg /= count
            avg = (avg /np.linalg.norm(avg)) * self.max_speed
            avg -= self.velocity
            avg = (avg /np.linalg.norm(avg)) * self.max_force
        self.acceleration += avg #Ergebniss wird zu dem Beschleunigungsvektor addiert
</code>
{{:ss20:alignment.gif?direct|}}



==== 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

Seiten-Werkzeuge
