Nutzung von GaFrame

Ein Beispiel für einen einfachen Genetischen Algorithmus ist die Klasse de.htwdd.ga.examples.KnapSack, diese ist direkt ausführbar und modelliert ein klassisches Beispiel Genetischer Algorithmen, das Rucksackproblem.
Das Problem besteht darin, aus einer Menge verschiedener Objekte (z.B. Zubehör für eine Bergwanderung) diejenigen auszuwählen, die in einen Rucksack gepackt werden sollen. Jedem Gegenstand ist dabei ein Nutzwert und ein Gewicht zugeordnet, der Rucksack hat ein maximal zulässiges Gesamtgewicht. Die optimale Kombination ist zu ermitteln.

Anhand dieses Beispiels wird die Nutzung von GaFrame deutlich, die wichtigsten Elemente des Frameworks werden hierzu im nächsten Abschnitt erläutert.

Das folgende Diagramm zeigt das grundsätzliche Vorgehen, um mit GaFrame einen eigenen Genetischen Algorithmus zu implementieren. Die einzelnen Punkte werden in den folgenden Unterabschnitten weiter erläutert.

Grundlegende Elemente von GaFrame

Chromosom

Ein Chromosom besteht aus einer Folge von Bits, in GaFrame wird es durch ein java.util.BitSet repräsentiert.

Vor der Nutzung eines Genetischen Algorithmus muss also festgelegt werden, wie sich das vorliegende Problem am sinnvollsten codieren lässt. Eine sinnvolle Codierung des Rucksackproblems ist, für jeden Gegenstand ein Bit zu reservieren, das festlegt, ob der Gegenstand im Rucksack enthalten ist oder nicht.

Der folgende Code gibt eine "Rucksackpopulation" auf der Konsole aus. Jeder im Rucksack enthaltene Gegenstand wird mit einem x markiert.

private static void displayPopulation(Individual[] population)
{
	StringBuffer out = new StringBuffer();
	for (Individual individual : population)
	{
		BitSet b = individual.getChromosome();
		
		out.append("individual ");
		for (int i = 0; i < KnapsackFitness.NUM_ITEMS; i++)
		{
			if (b.get(i))
				out.append("x ");
			else
				out.append("- ");
		}
		out.append("\n");
	}
	System.out.println(out.toString());
}
							

Bei der Arbeit mit einem BitSet kann entweder direkt auf die einzelnen Bits zugegriffen werden (wie im Beispiel), oder es kann die Klasse de.htwdd.ga.util.BitSetUtil genutzt werden, um Ganz- und Gleitkommazahlen in bestimmte Teile des BitSets zu schreiben bzw. wieder auszulesen.

Der folgende Code extrahiert eine Ganzzahl aus den Bits 3-12 des BitSets chromosome:

BitSetUtil.bitSetToInt(chromosome, 3, 10); 

An dieser Stelle wollen wir auch darauf hinweisen, dass standardmäßig keine Gray-Codierung verwendet wird. Diese kann allerdings leicht durch die eben schon genutzte Klasse de.htwdd.ga.util.BitSetUtil nachgereicht werden. Hierzu muss man nur nach dem Setzen der Bitkombination BitSetUtil.doGrayCoding(bitSet) aufrufen. Diese statische Methode transformiert das übergebene BitSet (in binärer Darstellung) in einen Gray-Code.

Die Rücktransformation kann auf gleiche Weise mittels BitSetUtil.doInvGrayCoding(BitSet bitSet) erfolgen.

Individuen/Populationen

Ein Individuum (de.htwdd.ga.Individual) wird duch sein Chromosom repräsentiert, eine Population besteht aus einem Array von Individuen.

Die Klasse de.htwdd.ga.util.GaXMLUtil bietet Methoden, um eine Population in einer XML-Datei zu persistieren oder sie wieder zu extrahieren.

Fitnessfunktion

Um die Fitness eines Individuums zu bestimmen, benötigt der Genetische Algorithmus eine auf das Problem zugeschnittene Fitnessfunktion. Diese muss das Interface de.htwdd.ga.FitnessFunction implementieren.

Die Fitness eines Rucksackindividuums wird duch die aufsummierten Nutzwerte der enthaltenen Gegenstände bestimmt, die Nutzwerte werden aus einer Tabelle ausgelesen. Ein zu schwerer Rucksack hat die Fitness 0. Das Array knapSackArray enthält Nutzwert und Gewicht der einzelnen Gegenstände, der zweite Gegenstand hat z.B. das Gewicht 7 und den Nutzwert 5.

public class KnapsackFitness implements FitnessFunction
{
    public static final int NUM_ITEMS   = 9;
    private static final int MAX_WEIGHT	= 58;
    public static long delay            = 0;
	
	private int	knapSackArray[][] = {
	{ 3, 3 }, { 7, 5 }, { 4, 2 }, { 12, 11 },
	{ 8, 4 }, { 10, 6 }, { 9, 2 }, { 14, 15 },
	{ 10, 12 }, { 12, 9 } };



	public double computeFitness(BitSet chromosome)
	{
		int weightSum = 0, valueSum = 0;
		for (int iGene = 0; iGene < NUM_ITEMS; ++iGene)
		{
			if (chromosome.get(iGene))
			{
				weightSum += knapSackArray[iGene][0];
				valueSum += knapSackArray[iGene][1];
			}
		}

		if (weightSum <= MAX_WEIGHT)
			return valueSum;
		else
			return 0;
	}
}
							

Genetischer Algorithmus

Die Klasse de.htwdd.ga.GeneticAlgorithm ist die zentrale Klasse von GaFrame, sie steuert den Ablauf des Genetischen Algorithmus. Um einen Genetischen Algorithmus zu nutzen, muss diese Klasse instanziiert werden. Dabei ist anzugeben:

• chromosomeLength - die Länge des Chromosoms aller Individuen
• maxCycles - die maximale Anzahl von Generationen, die erzeugt werden sollen
• terminationFitness - sobald mindestens ein Individuum der Population diese Fitness erreicht, wird der Algorithmus beendet.
• populationSize - die Anzahl von Individuen pro Population

Im Weiteren muss dem Genetischen Algorithmus eine Fitnessfunktion (siehe unten) angegeben werden. Optional können außerdem die einzelnen Bestandteile (Initialisierungsfunktion, Ersetzungsschema, ...) definiert werden, falls von den Standardeinstellungen abweichende Verfahren verwendet werden sollen.

run() startet den Genetischen Algorithmus.

Der folgende Code zeigt die entsprechende Lösung im Rucksackproblem:

GeneticAlgorithm algorithm = new GeneticAlgorithm(KnapsackFitness.NUM_ITEMS, 100, 66, 20);
algorithm.setFitnessFunction(KnapsackFitness.class);
algorithm.setCrossoverMethod(new TwoPointCrossover());
algorithm.setMutationRate(0.1);
algorithm.setSelectionStrategy(new RankingSelection(.3, .4));

algorithm.run();
							

Optionale Konfigurationsmöglichkeiten

GaFrame individualisieren

GaFrame kann leicht individualisiert werden, um z.B. Log-Ausgaben oder das automatische Speichern der Populationen nach jedem Durchlauf zu realisieren. Zu diesem Zweck muss lediglich die Klasse de.htwdd.ga.GeneticAlgorithm abgeleitet werden. Alle nicht als final deklarierten Methoden lassen sich leicht überschreiben, um individuelle Erweiterungen zu realisieren. Dabei ist darauf zu achten, dass im Verlauf der Methode super aufgerufen wird.

Im folgenden Beispiel wird die Methode runReplacement() überschrieben, um eine Logausgabe zu realisieren und die Population zu speichern.

public class MyGA extends GeneticAlgorithm
{
	public MyGA(int chromosomeLength, int numCycles, int populationSize)
	{
		super(chromosomeLength, numCycles, 0.98, populationSize);
	}

	@Override
	protected void runReplacement()
	{
		super.runReplacement();

		// Fitnesswerte aller Individuen ausgeben
		StringBuffer buffer = new StringBuffer();
		buffer.append("##population fitness after cycle ");
		buffer.append(cycle + 1);
		IndividualSorter.sortIndividuals(population);
		for (Individual individual : population)
		{
			buffer.append(String.format(" %1.4f", individual.getFitness()));
		}
		System.out.println(buffer.toString());

		//Population speichern
		GaXmlUtil.writeToFile(population, "data/" + cycle + ".xml");
	}
}
							

Neben der Möglichkeit, GeneticAlgorithm zu überschreiben, können auch alle weiteren austauschbaren Komponenten durch individuelle Implementierungen (z.B. eine eigene Ersetzungsstrategie) ersetzt werden.

Mutationsrate

Die Mutationsrate bestimmt, mit welcher Wahrscheinlichkeit ein Individuum mutiert, also sein Erbmaterial zufällig verändert. Mutationen werden nach der Ersetzung durchgeführt (siehe Ablaufmodellierung).

Beispiel:

GeneticAlgorithm algorithm;
...
algorithm.setMutationRate(0.2);
							

Initialisierungsfunktion

Die Initialisierungsfunktion erzeugt eine Startpopulation, mit der der Genetische Algorithmus im Folgenden arbeiten wird (de.htwdd.ga.InitializationFunction). Standardmäßig werden die hier erzeugten Individuen mit einem zufällig erzeugten Chromosom ausgestattet. Weiterhin ist es möglich, eine Überpopulation erzeugen zu lassen, deren "fitteste" Individuen dann die initiale Population bilden. Standardmäßig wird keine Überpopulation erzeugt.

Das folgende Beispiel erzeugt eine Überpopulation von 50%:

GeneticAlgorithm algorithm;
...
algorithm.getInitializationFunction().setInitializationCoeff(1.5);
							

Die Klasse de.htwdd.ga.FileInitialization erlaubt es, eine aus einer XML-Datei extrahierte Population als Startpopulation zu nutzen, weitere eigene Implementierungen sind denkbar.

Beispiel:

GeneticAlgorithm algorithm;
...
FileInitialization init = new FileInitialization("alte_Population.xml");
algorithm.setInitializationFunction(init);
							

Selektionsverfahren

Das Selektionsverfahren bestimmt, welche Individuen einer aktuellen Population sich vermehren dürfen, Basisklasse für Selektionsverfahren ist de.htwdd.ga.SelectionStrategy.

Vorhandene Selektionsverfahren:

• zufällige Auswahl von Heiratskandidaten: de.htwdd.ga.RandomSelection
• rangbasierte Auswahl: de.htwdd.ga.RankingSelektion

Beispiel:

GeneticAlgorithm algorithm;
...
algorithm.setSelectionStrategy(new RankingSelection(.3, .4));
							

Kreuzungsverfahren

Um aus einer vorhandenen Population von Individuen Nachkommen zu gewinnen, werden jeweils zwei Individuen aus dem Heiratspool mittels eines Kreuzungsverfahrens rekombiniert.

Grundsätzlich bedeutet dies, dass das "Erbgut" (also das Chromosom) der Eltern in geeigneter Weise gespalten wird, wodurch man (üblicherweise) zwei neue Individuen, die Kinder, erhält.

GaFrame enthält zwei grundlegenden Kreuzungsverfahren:

• de.htwdd.ga.SinglePointCrossover: Bei diesem Verfahren wird zufällig eine Stelle des Chromosoms ausgewählt, die Chromosomen der beiden Eltern werden an dieser Stelle aufgeteilt. Durch Vertauschen der jeweils zweiten Hälften der Chromsomen entstehen zwei neue Individuen.
  
• de.htwdd.ga.TwoPointCrossover: Aus dem Namen wird bereits klar, dass bei diesem Verfahren zwei Stellen des Chromosoms ausgewählt werden. So wird aus der Mitte der Chromosomen der Eltern ein Teil herausgetrennt, durch Kreuzung erhält man auch hier zwei neue Individuen.
  

Beispiel:

GeneticAlgorithm algorithm;
...
algorithm.setCrossoverMethod(new TwoPointCrossover());