Genetische Algorithmen mit Java

Mit dem etablierten Open Source Framework JGAP auf einfache Weise genetische Algorithmen programmieren und komplexe Probleme lösen.

Genetische Algorithmen

Genetische Algorithmen erklärt

Angelehnt an Konzepte aus der Natur, ist es mit dieser Art von Herangehensweise möglich, Lösungen für komplexe Problemstellungen zu finden. Insbesondere eignen sich Genetische Algorithmen für Probleme, die einen schier endlosen Lösungsraum haben und für die es ad hoc keine optimale Lösung zu geben scheint. Beispiel hierfür ist eine Antenne, die im Weltraum eingesetzt werden soll. Sie muss Signale aus allen möglichen Richtungen möglichst gut empfangen können. Herkömmliche Verfahren, insbesondere Brute Force Algorithmen (stumpes Ausprobieren aller Möglichkeiten) scheiden hier oft aus. Daas Antennenbeispiel stammt aus der Praxis. Die NASA hat tatsächlich evolutionäre Algorithmen eingesetzt, um eine Lösung zu finden und eine Antenne für das Weltall zu entwickeln.

Mutation, Crossing Over und Replikation

Den meisten sind diese Begriffe aus dem Biologieunterricht noch vertraut. Ein Genetischer Algorithmus (GA) verwendet diese Prinzipien zur Generierung neuer Populationen. Eine Population besteht aus mehreren Individuen, genau wir in Wirklichkeit auch. Jedes Individuum definiert sich über einen Satz Chromosomen, der das Erbgut darstellt, also die DNA. Ein Chromosom wiederum setzt sich aus mehreren verschiedenen Genen zusammen, den eigentlichen Trägern der Erbinformationen.

Eine Fitnessfunktion bewertet nun, wie gut ein Individuum in der gegebenen Umgebung bestehen kann. Die Umgebung ist bei der Lösung von Problemen mit Java die Problemstellung. Die Fitnessfunktion berechnet einen Defektwert, also die Abweichung der optimalen zur durch das Individuum geleisteten Performanz. Alternativ kann man den invertierten Wert berechnen, die Erfolgsrate.

Steht nun fest, welche Individuen einer Population besonders gut für das Problem geeignet zu sein scheinen, werden diese bevorzugt in die nächste Generation übernommen. Das wird als Replikation bezeichnet.

Damit Evolution stattfinden kann, bedarf es darüber hinaus Veränderungen am Erbgut. Die Mutation fügt zufällige Änderungen in Gene ein. Das Crossing Over hingegen nimmt zwei Gene verschiedener Individuen und kreuzt sie. Dabei entsteht ein neues Chromosom mit Genen, die teils von einem Individuum (analog der Natur, dem Vater) und teils von einem anderen Individuum (analog der Mutter) stammen.

Ablauf der Evolution

Es werden nun so lange neue Generationen erzeugt, bis ein Abbruchkriterium erreicht ist. Das ist im Idealfall dann gegeben, wenn ein Optimum erreicht ist oder zumindest eine sehr gute Annäherung an eine maximal gute Lösung. Ein Abbruch kann aber auch nach Überschreiten einer Anzahl Durchläufe stattfinden. In diesem Fall ist keine optimale Lösung gefunden worden.

Die Fitnessfunktion spielt eine zentrale Rolle. Für mathematische Problemstellungen ist sie leicht aufstellbar. Geht es um physikalische Prozesse, muss ein Simulator erstellt werden, der die Realität im Computer abbildet. Das ist oftmals mit viel Arbeit verbunden. Man kann hierbei aber auch auf Frameworks zurückgreifen.

Wie viele Individuen in einer Population vorhanden sind, muss der Programmierer vorgeben. Ebenso muss definiert werden, wie hoch die Mutationsrate und die Wahrscheinlichkeit für Crossing Over sind.

Das Framework JGAP für Java

JGAP ist ein Open Source Framework, das kostenfrei für private Projekte erhältlich ist. JGAP steht für Java Genetic Algorithms Package. Neben Genetischen Algorithmen unterstützt JGAP auch die Genetische Programmierung, die wesentlich flexibler, aber auch komplizierter zu programmieren ist.

Über die JGAP Homepage kann das Framework heruntergeladen werden, der Quelltext ist frei verfügbar.

Weitere Informationen auf Deutsch sind auf der Artikelseite verfügbar. Ein bekannter Vertreter für eine Problemklasse Genetischer Algorithmen ist das Mona Lisa Malproblem, zu dem es hier ebenfalls weitere Infos gibt.

Wer sich näher für das Thema interessiert, dem empfehlen wir das Buch Algorithmen kompakt und verständlich: Lösungsstrategien am Computer.


War diese Seite informativ für Sie?

Genetische Algorithmen mit Java: 1 Stern2 Sterne3 Sterne4 Sterne5 Sterne 5,00 von 5 Punkten, basieren auf 3 abgegebenen Stimmen.
Loading...
Share on FacebookShare on Google+Tweet about this on TwitterPin on PinterestShare on TumblrShare on LinkedIn