Was sind evolutionäre Algorithmen?

Komponente in der künstlichen Intelligenz

Evolutionäre Algorithmen (EA) werden in der heutigen Welt immer wichtiger. Lösungen mit künstlicher Intelligenz werden zunehmend in Branchen wie digitales Marketing, Finanzen und Verkehrs- und Gesundheitswesen eingesetzt. Doch was genau sind evolutionäre Algorithmen und wie unterscheiden sie sich von anderen Formen der KI? Die folgenden Zeilen vermitteln Dir einen Einblick in die Welt der evolutionären Algorithmen. Dafür musst Du nicht einmal einen Abschluss in Informatik oder Mathematik haben.

Was sind evolutionäre Algorithmen

Ein EA wird als eine Komponente der evolutionären Berechnung in der künstlichen Intelligenz betrachtet. Das Verfahren arbeitet mit einem Auswahlprozess und einer Optimierung. Dabei werden die am wenigsten passenden Mitglieder einer Population eliminiert, während die passenden Mitglieder überleben und fortfahren können, bis bessere Lösungen bestimmt sind. Mit anderen Worten, EA sind Computeranwendungen, die biologische Prozesse nachahmen, um komplexe Probleme zu lösen. Im Laufe der Zeit entwickeln sich die erfolgreichen Mitglieder, um die optimierte Lösung für das Problem zu präsentieren.

Evolutionäre Algorithmen verwenden Konzepte aus der Biologie wie beispielsweise Selektion, Reproduktion und Mutation. Es gibt drei grundlegende Arten von EA, nämlich:

• Genetische Algorithmen
• Evolutionäre Programmierung
• Evolutionäre Strategien

Es gibt viele Vorteile, die mit EA verbunden sind. Einer der größten Nutzen liegt in der Flexibilität, da die meisten evolutionären Algorithmus-Konzepte auch für komplexe Probleme geeignet sind. Mit EA ist oft eine bessere Optimierung möglich, da die Lösungspopulation verhindert, dass der Algorithmus eine bestimmte Lösung von vornherein ausschließt.

Es gibt jedoch auch einige Nachteile, die mit EA verbunden sind. Zum einen ist die gefundene Lösung im Vergleich zu anderen bekannten Lösungen oft besser. Trotzdem kann man mit dem Verfahren nicht beweisen, dass eine Lösung insgesamt optimal ist, sondern nur, dass sie im Vergleich zu den anderen Ergebnissen optimal ist.

Wo und wofür werden evolutionäre Algorithmen benutzt?

EA werden typischerweise verwendet, um gute Näherungslösungen für Probleme bereitzustellen, die nicht einfach mit anderen Techniken gelöst werden können. Viele Verfahren der Optimierung fallen in diese Kategorie. Manchmal ist ein Verfahren zu rechenintensiv, um eine exakte Lösung zu finden, aber oft ist eine nahezu optimale Lösung ausreichend. In diesen Situationen können evolutionäre Techniken effektiv sein. Aufgrund ihrer zufälligen Natur garantieren EA niemals eine optimale Lösung für irgendein Problem zu finden. Diese Verfahren werden jedoch oft eine gute Lösung finden, falls diese existiert.

Ein Beispiel für eine solche Optimierung ist die Herausforderung, Fahrpläne sinnvoll zu gestalten. Schulen und Universitäten müssen die Raum- und Personalzuweisungen an die Bedürfnisse ihres Lehrplans anpassen. Dabei gibt mehrere Einschränkungen, die erfüllt sein müssen: Ein Mitarbeiter kann sich immer nur an einem Ort aufhalten, er kann nur Klassen unterrichten, die in seinem Fachgebiet liegen, Räume können keine Unterrichtsstunden aufnehmen, wenn sie bereits besetzt sind, und Klassen dürfen nicht mit anderen Klassen derselben Schüler kollidieren. Dies ist ein kombinatorisches Problem und aufgrund des hohen Rechenaufwands ist eine erschöpfende Suche nach den optimalen Lösungen nicht immer möglich. Stattdessen werden für diese Optimierung häufig Heuristiken verwendet.

EA können auch verwendet werden, um Probleme anzugehen, die Menschen nicht wirklich lösen können. Ein EA, der frei von menschlichen Vorurteilen oder Vorurteilen ist, kann überraschende Lösungen hervorbringen. Diese sind oft vergleichbar oder besser als die von Menschen erzeugten Lösungen. Es ist lediglich notwendig, dass wir eine gute Lösung erkennen, wenn sie von einem EA präsentiert wird.

Wie funktionieren evolutionäre Algorithmen?

Es gibt viele Varianten von EA, und in unserem Fall werden wir uns auf den allgemeineren Ansatz dieser Algorithmen konzentrieren. Die gemeinsame Grundidee, die diese Ansätze vereint, ist die gleiche. Angenommen, Du hast ein Problem, für das Du eine Lösung finden möchtest. Nehmen wir weiterhin an, dass diese Lösung nicht offensichtlich ist. Oder Du hast eine Lösung, aber Du bist Dir nicht sicher, ob diese Lösung die optimale Lösung für Dein Problem ist. Dies ist genau die Art von Situation, auf die EA ausgerichtet sind.

Evolutionäre Algorithmen verwenden eine Fitnessfunktion

Der erste Schritt besteht darin, eine Population mit zufällig möglichen Lösungen für das gegebene Problem zu erzeugen. Um die Analogie konsistent zu halten, denken wir als Lösung an ein Mitglied einer Tierart. Jede dieser Lösungen wird von einer Fitnessfunktion ausgewertet, um festzustellen, wie gut sie das Problem lösen können. Die Fitnessfunktion entspricht dabei der Fähigkeit eines Organismus, sich an seine Umgebung anzupassen. In gewisser Hinsicht wirkt diese Fitnessfunktion als der Umweltdruck, dem ein Organismus ausgesetzt ist. Aus dieser Population von Kandidatenlösungen wird eine kleine Teilmenge (typischerweise 5%) durch diese Fitnessfunktion ausgewählt, um “Eltern” zu werden.

Der nächste Schritt besteht darin, diese ausgewählten Lösungen zu “paaren”, um eine ganze Reihe neuer möglicher Lösungen zu generieren. Idealerweise bestehen die Ergebnisse aus Lösungen, die besser sind als die ersten möglichen Lösungen.

Mutation und Variation

Es gibt viele Möglichkeiten, Lösungen zu reproduzieren, und die Reproduktion hängt ganz davon ab, welche Art von Lösungen man hat und welche Art von Problemen Du lösen möchtest. Die Paarungsfunktion verwendet einen so genannten “Variationsoperator”, der eine Mutation auf die resultierende Kindlösung anwendet. Es ist leicht zu sehen, wie dieser Prozess eine echte Mutation während der Reproduktion darstellt. Dieser Variationsoperator ermöglicht es dem nächsten Pool von Lösungen, neue Merkmale (Mutationen) hervorzubringen, die besser sein können als die Merkmale der vorherigen Generation.

Einsatzgebiete und Fazit

EA werden in einer Vielzahl von Anwendungen und Verfahren wie Bildverarbeitung, Verkehrsführung, Mobilfunk-Optimierung, Software-Engineering und sogar beim Training künstlicher neuronaler Netze eingesetzt. Diese Tools basieren auf vielen Apps und Websites, die Nutzer täglich nutzen, darunter Google Maps und sogar Simulationsspiele. Darüber hinaus nutzt der medizinische Bereich EA, um bei klinischen Entscheidungen zur Krebsbehandlung zu finden. Tatsächlich sind EA so robust, dass sie fast jedes Optimierungsproblem lösen können.