Oftmals konzipieren und entwickeln wir technische Lösungen um komplexe Probleme zu lösen. Hierbei bedienen wir uns an etablierten Ansätzen und Methoden um diese auf unser individuelles Problem anzuwenden. Neuronale Netze stellen beispielsweise einen solchen Ansatz dar und haben in den letzten Jahren große Verwendung gefunden. Neuronale Netze imitieren die Funktionsweise des menschlichen Gehirns. Dabei stellen neuronale Netze bei Weitem nicht den einzigen Ansatz dar, der von der Natur inspiriert ist. Das übergreifende Feld der Informatik nennt sich Computational Intelligence und umfasst eine Reihe an Ansätzen, die ihren Ursprung in der Natur haben. Weniger bekannt – aber mindestens genauso spannend wie neuronale Netze – sind evolutionäre Algorithmen. Im Vergleich zu neuronalen Netzen sind evolutionäre Algorithmen deutlich weiter erforscht, einfacher zu verstehen und sind in ihrer Funktionsweise absolut faszinierend. Am relevantesten jedoch ist die breite Menge an Problemen auf die sich evolutionäre Algorithmen anwenden lassen. In diesem Blogartikel geben wir euch einen kurzen Einblick in die Funktionsweise und Anwendungsbereiche von evolutionären Algorithmen.

‍

Anwendungsbereiche

Wir halten evolutionäre Algorithmen besonders deshalb für relevant, weil sie sich auf eine große Menge an Problemen anwenden lassen. Hierbei müssen im Kern zwei Bedingungen erfüllt werden.

  1. Die Anzahl an möglichen Lösungen muss zu groß sein, als dass alle Lösungen betrachtet werden können.
  2. Die Qualität jeder Lösung muss quantifizierbar sein.

Stellt euch den Designprozess einer Autokarosserie vor. Jeder Entwurf lässt sich virtuell simulieren um die Aerodynamik zu quantifizieren. Allerdings gibt es nahezu unzählige mögliche Designs. Jede kleinste Änderung der Form oder des Materials resultiert in potenziell anderen Ergebnissen. Ein weiteres Beispiel stellt die Verteilung von Aufträgen auf Produktionsmaschinen dar. Um die Effizienz zu maximieren, müssen die Aufträge so auf die Maschinen verteilt werden, dass möglichst wenig Leerlauf entsteht. Ungeeignet sind evolutionäre Algorithmen beispielsweise zum Hacken von Passwörtern. Zwar gibt es sehr viele mögliche Passwörter, aber die Qualität lässt sich nicht quantifizieren. Ein Passwort ist entweder richtig oder falsch. Ein Passwort ist niemals zu 80% korrekt.

‍

Routenoptimierung mittels Evolutionäre Algorithmen

Der Traveling Salesman ist wohl eins der bekanntesten Probleme aus der Informatik. Eine möglichst kurze Route soll gefunden werden, wobei jeder Punkt genau einmal besucht wird. In dem folgenden vereinfachten Beispiel gibt es fünf Punkte, wodurch sich 60 mögliche Routen ergeben (n!/2). Die Qualität einer Lösung wird in der Welt der evolutionären Algorithmen Fitness genannt. Die Fitness einer Route errechnet sich in diesem Beispiel durch die Summe der Distanzen zwischen den Punkten. Die zweite Anforderung zur Verwendung von evolutionären Algorithmen ist also erfüllt. Bei diesem einfachen Beispiel könnten alle 60 mögliche Routen berechnet werden, dies ändert sich aber sehr schnell mit steigender Anzahl der Punkte. Bereits bei zehn Punkten gibt es ca. 1.800.000 Möglichkeiten. Bei 100 Punkten sind es 4,67 x 10<sup>157</sup> Routen. Die erste Anforderung zur Verwendung von evolutionären Algorithmen ist daher bei dieser Problemart sehr schnell gegeben. Zur Veranschaulichung der Funktionsweise von evolutionären Algorithmen verwenden wir in diesem Beispiel weiterhin das vereinfachte Problem mit fünf Punkten.

‍

Erforschung des Lösungsraums

Aber wie funktionieren evolutionäre Algorithmen und was haben diese mit der Evolution zu tun? Bei der Evolution geht es im Kern darum, dass sich Lebewesen über viele Jahrtausende und Generationen an eine Umgebung anpassen. Daher verfügen Tiere aus nördlichen Regionen über eine andere genetische Veranlagung als Tiere aus sehr heißen Gebieten. Dieser Prozess ist die Basis für evolutionäre Algorithmen. Inspiriert von der Entwicklung eines Lebewesens über Millionen von Generationen werden mögliche Lösungen für ein Problem in kürzester Zeit über mehrere Generationen weiterentwickelt. Um diesen Prozess besser zu verstehen stellen wir uns den Lösungsraum (die Menge aller möglichen Routen) als reale Landschaft vor.

Die folgende Abbildung zeigt eine Landschaft, bei der jedes kleine Quadrat eine mögliche Lösung bzw. Route repräsentiert. Besonders gute Routen werden als Berge dargestellt. Schlechte, also lange Routen, werden als Täler dargestellt. Wo genau Berge und Täler sind wissen wir aber nicht, denn dafür wollen wir den evolutionären Algorithmus verwenden. Der Algorithmus soll einige Quadrate der Landschaft besuchen und herausfinden, ob es sich um ein versprechendes Gebiet handelt. Genau hierfür wird die Evolution simuliert.

‍

Evolutionärer Zyklus

Zu Beginn des Prozesses werden zufällige Routen generiert. Jede Route repräsentiert ein Quadrat in unserer Landschaft. Die Menge dieser Lösungen repräsentiert unsere Population, die wir evolutionär vorantreiben wollen. Der Algorithmus wählt nun einige Lösungen aus, die als Eltern dienen. Diese Lösungen werden miteinander kombiniert, es wird ein Kind erzeugt. Der Grundgedanke hier ist, dass die Kombination aus zwei starken Eltern höchstwahrscheinlich ein genauso starkes bzw. stärkeres Kind ergibt. Dieses Kind wird dann wieder in die Population gespielt und ersetzt dort eine schwache Lösung. Nun werden wieder Eltern ausgesucht, Kinder erzeugt und die Population erneuert. Dieser Prozess wird sehr schnell, sehr oft wiederholt, bis das Zeitlimit erreicht ist. Das zeitliche oder ähnliche Limit wird je nach Problem gesetzt. Am Ende wird die kürzeste Route ausgewählt.

‍

Fazit

In diesem Blogartikel wurde ein kleiner Einblick in die Funktionsweise und die Anwendungsbereiche von Evolutionären Algorithmen gegeben. Aufgrund ihrer leichten Verständlichkeit und besonders durch das breite Anwendungsfeld sehen wir bei Orbit Evolutionäre Algorithmen als Geheimtipp der Künstlichen Intelligenz. Evolutionäre Algorithmen können in kurzer Zeit gute Lösungen für sehr komplexe Probleme finden.