Adaptive Mutation

Als eine mögliche Gegenmaßnahme kann die Adaption der Mutationsrate dienen. Es wird eine Schwelle definiert, oberhalb welcher die Streuung im Genpool einer Population noch als ausreichend angesehen wird. Fällt dieser Wert unterhalb die Schwelle, so wird aus dem Verhältnis von Schwelle zu tatsächlichem Wert ein Multiplikationsfaktor für die Mutationsrate der jeweils nächsten Generation errechnet.

Als Vergleichswert für die Schwelle lassen sich recht viele Kriterien heranziehen. Die beiden naheliegendsten Möglichkeiten zum Beispiel sind

• die genetische Vielfalt (Konvergenz) der Population.
• die Standardabweichung aller Ziel- oder Fitnesswerte

Wie in 3.4.11 schon erläutert, wird besonders für große Populationen die Berechnung der genetischen Vielfalt zu einem zeitkritischen Faktor, da jedes Gen jedes einzelnen Individuums mit den jeweils korrespondierenden Genen aller anderen Individuen verglichen und bewertet werden muss. Dies führt zu einer exponentiellen Zunahme von Vergleichen.

Deshalb ist für diese Arbeit der Standardabweichungsoperator benutzt worden. Fällt der Wert der Standardabweichung aller Objective Score Werte in der Population unterhalb eines festgelegten Schwellenwertes, wird die Mutationsrate für die Nachfolgegeneration anhand folgender Formel festgelegt:

$mutation_{effektiv}=mutation_{gegeben} \cdot \frac{Schwellenwert}{Standardabweichung der Zielwerte}$

Dieses Verhalten zielt darauf ab, am Anfang eines Laufes den Crossover- Operator zu unterstützen und eine maximale Exploitation bei geringer Exploration zu ermöglichen. Bei fortgeschrittener Konvergenz und abnehmender Bedeutung des Crossover wird die Exploration stärker gewichtet, um ein Optimum in der jeweiligen Umgebung zu finden oder möglicherweise aus einem Suboptimum herauszufinden.

Im Gegensatz zu Cobb und Greffenstette's Hypermutation (1993) mit einem Standardmodus von $p_m=0,001$ und einem Hypermutationsmodus von $p_m=0,5$ setzt die adaptive Mutation die durch Exploitation gewonnenen Informationen für eine eingegrenzte Exploration ein. Der Hypermutationsmodus hingegen kann eher mit einem multiplen sequentiellen Lauf mit teilweiser Reinitialisierung verglichen werden, der viel größere Sprünge bei der Exploration des Suchraumes absolviert.