Was ist ein evolutionärer Algorithmus? Ein kurzer Leitfaden

Das Leben auf der Erde hat sich über Millionen von Jahren entwickelt. Im Laufe dieses Prozesses haben sich Lebewesen an ihre Umwelt angepasst, um zu überleben und zu gedeihen. Giraffen zum Beispiel entwickelten über viele Generationen lange Hälse, um hoch oben in Bäumen an Blätter zu gelangen, die für andere Tiere unerreichbar sind. Dahinter steht die natürliche Selektion: Hilfreiche Merkmale werden häufiger, weil ihre Träger mit größerer Wahrscheinlichkeit überleben.

Einfach gesagt: Organismen, die besser an ihre Umgebung angepasst sind, überleben eher und geben ihre nützlichen Merkmale an ihre Nachkommen weiter. Mit der Zeit summieren sich diese kleinen Veränderungen und helfen Arten, selbst mit den schwierigsten Bedingungen zurechtzukommen.

Evolutionäre Algorithmen (EA) gehören zum Oberbegriff „Computational Intelligence“. Ähnlich wie in der Evolution wählt ein EA die besten Lösungen aus einer Gruppe aus, nimmt kleine Änderungen vor und prüft, ob diese Änderungen die Ergebnisse verbessern. Durch die Wiederholung dieses Prozesses über viele Generationen hinweg findet er die besten Lösungen für komplexe Probleme in verschiedenen Bereichen.

Evolutionäre Algorithmen sind dank ihrer Vielseitigkeit ein interessantes Forschungsgebiet. Laufende Studien untersuchen ihren Einsatz in Bereichen wie Ingenieurwesen, Medizin und Umweltwissenschaften. In diesem Artikel sehen wir uns genauer an, was evolutionäre Algorithmen sind, wie sie funktionieren und wo sie eingesetzt werden.

Evolutionäre Algorithmen einfach erklärt#

Evolutionäre Algorithmen sind Optimierungsverfahren, die im Bereich des maschinellen Lernens eingesetzt werden können, um für eine bestimmte Aufgabe die bestmögliche Lösung oder das bestmögliche Modell zu finden. In der Regel beginnen sie mit einer Gruppe möglicher Lösungen und verbessern diese in vielen Durchläufen danach, wie gut sie das Problem lösen.

Stell dir zum Beispiel vor, du möchtest das kraftstoffsparendste Auto entwickeln. Der Algorithmus beginnt mit verschiedenen Fahrzeugentwürfen, testet ihre Leistung und verbessert die Entwürfe schrittweise, indem er die besten Eigenschaften kombiniert und über viele Durchläufe hinweg kleine Anpassungen vornimmt, bis er den bestmöglichen Entwurf gefunden hat.

Es gibt mehrere Arten evolutionärer Algorithmen, die Lösungen jeweils unterschiedlich darstellen und verbessern, aber alle diesem grundlegenden Ansatz folgen. Hier sind einige gängige Arten evolutionärer Algorithmen:

• Genetische Algorithmen: Bei dieser Art evolutionärer Algorithmen werden Lösungen als einfache codierte Zeichenfolgen dargestellt, etwa als Zahlen- oder Symbolfolgen. Die Lösungen werden verbessert, indem Teile zweier guter Lösungen miteinander kombiniert werden – ähnlich wie beim Kombinieren elterlicher Merkmale – und kleine zufällige Änderungen neue Varianten hervorbringen.
• Genetische Programmierung: Hier werden Lösungen als baumartige Strukturen aufgebaut. Das ist besonders nützlich, wenn die Lösung eine Abfolge von Schritten oder Anweisungen erfordert.
• Evolutionsstrategien: Hier liegt der Schwerpunkt darauf, zu bestimmen, wie groß oder klein die Änderungen beim Aktualisieren von Lösungen sein sollten. Dadurch kann der Algorithmus seine Ergebnisse mit der Zeit effizienter verbessern.
• Differenzielle Evolution: Bei diesem Ansatz entstehen neue Lösungen, indem Teile verschiedener vorhandener Lösungen kombiniert werden. Besonders gut eignet sich das Verfahren für Probleme, bei denen die Antworten kontinuierlich veränderliche Zahlen sind.

Wie evolutionäre Algorithmen funktionieren#

Evolutionäre Algorithmen verwenden ein iteratives Verfahren, um die beste Lösung für ein Problem zu finden. Du kannst dir das wie die natürliche Weiterentwicklung von Arten über Generationen hinweg vorstellen, bei der jeder Zyklus zur Verbesserung der Population beiträgt.

Es gibt zwar verschiedene Arten evolutionärer Algorithmen, doch im Allgemeinen folgen sie diesen grundlegenden Schritten:

• Initialisierung: Der Algorithmus beginnt mit der Erzeugung einer ersten Menge möglicher Lösungen. Sie bildet den Ausgangspunkt des evolutionären Prozesses.
• Bewertung der Fitness: Jede Lösung wird mithilfe einer Fitnessfunktion bewertet, die misst, wie gut sie das Problem löst. Besser abschneidende Lösungen erhalten höhere Bewertungen und werden mit größerer Wahrscheinlichkeit für die nächsten Schritte ausgewählt.
• Fortpflanzung: Neue Lösungen entstehen durch zwei Hauptverfahren: Kreuzung und Mutation. Bei der Kreuzung werden Merkmale zweier Elternlösungen kombiniert, während durch Mutationen kleine zufällige Änderungen vorgenommen werden, um neue Möglichkeiten zu erkunden.
• Ersetzung: Die neu erzeugten Lösungen ersetzen einige oder alle älteren Lösungen. Bei diesem Schritt wird festgelegt, welche Lösungen überleben und in die nächste Generation gelangen.
• Abbruch: Fortpflanzung und Ersetzung werden so lange fortgesetzt, bis eine Abbruchbedingung erfüllt ist. Das kann das Erreichen einer festgelegten Anzahl von Iterationen, eines zufriedenstellenden Fitnesswerts oder eines Punkts ohne weitere Verbesserungen sein – oder das Erreichen rechnerischer Grenzen.

Abb. 1. Ein Überblick über die Funktionsweise evolutionärer Algorithmen. Bild vom Autor.

Anwendungsbereiche evolutionärer Algorithmen#

Nachdem wir nun besser verstehen, was evolutionäre Algorithmen sind und wie sie funktionieren, sehen wir uns einige praktische Anwendungen aus verschiedenen Branchen an.

Bioinspirierte Algorithmen in Windparks#

Einer der wichtigsten Aspekte der Windenergieerzeugung ist die Platzierung der Windkraftanlagen. Die Effizienz eines Windparks kann stark davon abhängen, wie die Anlagen zueinander und zu den Windverhältnissen ausgerichtet sind. Herkömmliche Entwurfsverfahren haben oft Schwierigkeiten, die vielen beteiligten äußeren Einflussfaktoren zu berücksichtigen.

Evolutionäre Algorithmen eignen sich hervorragend dazu, viele verschiedene Layouts für Windparks zu entwickeln und zu testen. Dabei berücksichtigen sie Faktoren wie Windverhältnisse, Turbinentypen und die verfügbare Fläche, um die beste Anordnung zu finden. Mit jeder Testrunde verbessert sich der Entwurf, sodass mehr Energie erzeugt, Kosten gesenkt und Flächen besser genutzt werden. Nach mehreren Iterationen kann der endgültige Entwurf mehr Energie liefern als ein manuell erstellter.

Abb. 2. Ein Windpark.

Optimierungsverfahren im Fahrzeugbau#

Die Entwicklung sicherer, kraftstoffsparender und erschwinglicher Autos hat für heutige Automobilhersteller hohe Priorität. Evolutionäre Algorithmen können diesen Prozess beschleunigen, indem sie zahlreiche Entwurfsoptionen testen und schrittweise verbessern, um die beste Lösung zu finden. So können Hersteller die optimale Balance zwischen Leistung und Effizienz finden.

Ein interessantes Beispiel ist der Einsatz evolutionärer Algorithmen zur Entwicklung der tragenden Fahrzeugstruktur, die als Rohkarosserie (BIW) bezeichnet wird. Das Hauptziel dieses Entwicklungsprozesses besteht darin, das Gewicht der Karosserie zu verringern und dabei ihre Haltbarkeit und Festigkeit zu erhalten.

Genetische Algorithmen können verschiedene Strukturvarianten mit geringfügigen Änderungen erkunden. Anschließend werden diese Entwürfe anhand von Faktoren wie Festigkeit, Gewicht, Haltbarkeit und gesetzlichen Normen geprüft, um die beste Option zu ermitteln.

Abb. 3. Die Rohkarosserie eines Fahrzeugs (Quelle).

Evolutionäre Strategien für die Dienstplanung in Krankenhäusern#

Forschende untersuchen intensiv, wie evolutionäre Algorithmen im Gesundheitswesen helfen können, etwa bei der Dienstplanung des Krankenhauspersonals, der Verbesserung von Behandlungsplänen und der Entdeckung neuer Medikamente. Diese Algorithmen eignen sich gut dafür, weil sie große Datenmengen verarbeiten und Faktoren wie Müdigkeit und Stress berücksichtigen können.

So wurden beispielsweise genetische Algorithmen erprobt, um die Dienstplanung für Pflegekräfte in Krankenhäusern zu verbessern. In einer faszinierenden Studie wurde eine Kombination aus genetischen Algorithmen und lokaler Suche eingesetzt, um Dienstpläne zu erstellen, die die Ermüdung von Pflegekräften verringern. Die Ergebnisse zeigten eine um 10 % geringere Ermüdung und eine um 98 % schnellere Dienstplanung: Der Zeitaufwand sank von über einer Stunde auf etwas mehr als eine Minute.

Abb. 4. Manuelle Dienstplanung im Vergleich zur Dienstplanung mit einem genetischen Algorithmus (GA) (Quelle).

Die Rolle evolutionärer Verfahren in der Bildverarbeitung#

Evolutionäre Algorithmen werden auch in der Computer Vision eingesetzt – einem Bereich der KI, der es Maschinen ermöglicht, visuelle Daten wie Bilder und Videos zu interpretieren und zu analysieren. In laufenden Forschungsarbeiten wird ihr Potenzial für Aufgaben wie Bildsegmentierung, Objekterkennung und Merkmalsextraktion untersucht.

Diese Algorithmen testen zahlreiche mögliche Lösungen und wählen die besten aus. Dadurch sind sie flexibel und können mit komplexen und vielfältigen visuellen Daten umgehen. So haben Forschende evolutionäre Algorithmen eingesetzt, um KI-Systeme zu verbessern, die medizinische Bilder wie Röntgenaufnahmen des Brustkorbs analysieren.

Diese KI-Systeme, sogenannte Faltungsneuronale Netze (CNNs), arbeiten wie erfahrene Radiologen: Sie durchsuchen Bilder nach Anzeichen von Krankheiten wie COVID-19. Der evolutionäre Algorithmus unterstützt diesen Prozess, indem er die Struktur und Einstellungen des CNN automatisch entwirft und feinabstimmt, zahlreiche Versionen testet, die leistungsstärksten auswählt und nach und nach genauere Modelle erstellt. So entstehen KI-Werkzeuge, die Ärzte dabei unterstützen können, COVID-19 zu diagnostizieren – schneller und genauer.

Evolutionäre Verfahren kommen auch beim alltäglichen Modelltraining zum Einsatz. So verwendet beispielsweise die Abstimmung von Hyperparametern im Ultralytics-Python-Paket einen genetischen Algorithmus, der Einstellungen wie Lernrate, Verlustgewichte und Stärke der Datenerweiterung verändert. Anschließend wählt er aus vielen kurzen Trainingsläufen die Konfigurationen mit der besten Leistung aus.

Vor- und Nachteile evolutionärer Algorithmen#

Hier sind einige der wichtigsten Vorteile evolutionärer Algorithmen:

• Globale Suchfähigkeit: Evolutionäre Algorithmen durchsuchen gleichzeitig viele Bereiche des Lösungsraums und bleiben dadurch seltener in ungünstigen Lösungen stecken.
• Robustheit: In unsicheren und wechselnden Umgebungen helfen die Zufälligkeit und die Vielfalt der Lösungen eines evolutionären Algorithmus dabei, eine gleichbleibende Leistung des Systems aufrechtzuerhalten.
• Flexibilität: Evolutionäre Algorithmen lassen sich durch Änderungen an der Darstellung der Lösungen und an der Erfolgsmessung so anpassen, dass sie für viele verschiedene Problemtypen geeignet sind.

Diese Algorithmen bieten zwar viele Vorteile, doch es ist auch wichtig, ihre Grenzen zu kennen. Hier sind einige häufige Nachteile evolutionärer Algorithmen:

• Rechenaufwand: Die wiederholte Bewertung zahlreicher möglicher Lösungen kann leistungsstarke und kostspielige Rechenressourcen erfordern. Bei manchen Anwendungen kann das Verfahren dadurch langsam oder teuer werden.
• Empfindlichkeit gegenüber Parametern: Der Erfolg evolutionärer Algorithmen hängt oft stark von der Wahl der richtigen Anfangseinstellungen ab, etwa der Populationsgröße, der Mutationsrate und der Auswahlverfahren. Ungünstige Einstellungen können die Leistung beeinträchtigen.
• Langsame Konvergenz: Es kann viele Iterationen dauern, bis sich Lösungen verbessern, insbesondere bei sehr komplexen Problemen. Dadurch kann die Laufzeit im Vergleich zu anderen Verfahren länger sein.
• Empfindlichkeit gegenüber der Fitnessfunktion: Eine schlecht entworfene Fitnessfunktion kann dazu führen, dass Algorithmen Schwächen ausnutzen, statt das beabsichtigte Problem zu lösen. Dadurch erhalten Entwicklerinnen und Entwickler einen irreführenden Eindruck von der tatsächlichen Leistung.

Die wichtigsten Erkenntnisse#

Evolutionäre Algorithmen eignen sich hervorragend, um schwierige Probleme zu lösen, an denen andere Verfahren scheitern können. Forschungsergebnisse zeigen, dass sie sich durch Iteration schrittweise verbessern und sich an vielfältige Aufgaben anpassen können. Mit den Fortschritten und der Weiterentwicklung der KI dürften diese Algorithmen bei der Entwicklung intelligenter, effizienter und selbstlernender Technologien für zahlreiche Anwendungen eine noch größere Rolle spielen.

Werde Teil unserer wachsenden Community und besuche unser GitHub-Repository mit KI-Ressourcen. Entdecke auf unseren Lösungsseiten verschiedene Anwendungen der Bildverarbeitung in der Landwirtschaft und von KI in der Logistik. Informiere dich über unsere Lizenzoptionen, um deine Bildverarbeitungsprojekte zu starten.