Evolutionäre Algorithmen

Da ich mich derzeit intensiv mit dem Thema beschäftige, schreibe ich einmal einen kleinen Beitrag zu genetischen Algorithmen. Evolutionäre Algorithmen sind randomisiert, problemunabhänge Algorithmen, die oft dazu benutzt werden, ein Optimum einer bestimmten Funktion zu finden. Diese Funktion können wir zumeist nicht direkt analysieren, sondern nur an bestimmten Stellen auswerten. Auch benutzt man oft evolutionäre Algorithmen, wenn es an Ressourcen (Zeit, Personal, Geld etc.) fehlt, um eine analytische Lösung zu finden.

Die Idee hinter den evolutionären Algorithmen wurde der Natur entnommen. In der Natur ist die Evolution ein Prozess, der Individuen einer Population miteinander kreuzt oder zufälligen Mutationen aussetzt. Dabei entstehen Kinder. Diese Kinder werden nun von der Natur bewertet und das fitteste Individuum (oder die fittesten Individuen) überlebt und darf in der nächsten Generation für weitere Nachkommen sorgen.

Bei den evolutionären Algorithmen definiert man sich nun, was ein Individuum ist, dies können zum Beispiel Zahlen sein, Computerprogramme (genetische Programmierung) oder eigene Objekte, die man sich eventuell erstellt hat. Nun gibt es auch bei den evolutionären Algorithmen Operatoren, die man sich definiert, um eine Evolution zu durchlaufen, diese nennt man Crossover, Mutation und Selektion. Einige spezielle Formen der evolutionären Algorithmen verzichten auch schonmal auf einen der genannten Operatoren. Diese Operatoren tun genau das gleiche, wie die Evolution.

Ein Crossover nimmt sich eine Menge von Individuen und erstellt aus ihnen eine Menge von Kindern. Diese Kinder erben dann bestimmte Eigenschaften von zufällig gewählten Elternteilen, eben wie in der Natur (zum Beispiel kann ein Kind die Augenfarbe des Vaters und die Haarfarbe der Mutter besitzen).

Die Mutation arbeitet auf den Kindern, die aus dem Crossover hervorgegangen sind und sorgt dafür, dass zufällig gewählte Eigenschaften geändert (mutiert) werden. So kann es zu Mutationen kommen, die die Fitness des Individuums verbessern, diese Mutationen werden sich dann in der Evolution durchsetzen.

Schließlich wertet die Selektion die Individuen aus und anhand dieser Auswertung werden die schwächsten Individuen "aussterben" und aus den fitteren Individuen neue Generationen erzeugt.

Oft werden evolutionäre Algorithmen in den Himmel gelobt, weil sie jedes Problem lösen können. In der Theorie mag das vielleicht so sein, so können theoretische Algorithmen unter Umständen auch globale Optima finden. Wie lange sie dafür brauchen ist aber ungewiss. Oft besteht auch das Problem, dass man nicht weiß, wie das Optimum überhaupt auszusehen hat, so dass man keine Aussage darüber treffen kann, wann die evolutionären Algorithmen aufhören zu arbeiten.

Wie denkt ihr über diese Algorithmen? Ich denke, richtig angewandt können diese Algorithmen durchaus richtig gute Ergebnisse bringen. Man sollte sich aber stets bewusst sein, dass diese Erfolge zufällig sind und nicht auf jedes Problem evolutionäre Algorithmen jagen.