Mutation von Permutationen

Eine Mutation von Permutationen ist im Kontext eines genetischen Algorithmus' eine spezielle Mutation, die für Genome ausgelegt ist, die selbst Permutationen einer Menge sind.

Rotation nach rechts

Eine Variante von Mutation von Permutationen ist folgendes Verfahren:

Verfahren	Beispiel
Gegeben ist eine Permutation,	$P_0 = \left( A,B,C,D,E,F,G \right)$
Man wähle eine Teil-Liste aus, also einen Start-Index i und einen End-Index j in P0, sodass $i,j \in \left( \left[0, \left|P_0\right| \right[ \cap \mathbb{N} \right)$. Man beachte, dass der Start-Index nach dem End-Index kommen kann. Dann fängt die Teil-Liste einfach von vorne wieder an. (Dies ist notwendig, damit die Permutationswahrscheinlichkeit im Genom überall gleich ist und nicht in der Mitte größer ist als an den Rändern.)	i = 5, j = 2
Man kopiere P0 nach P1 und rotiere die Teil-Liste nach rechts.	$P_1 = \left( \underline {G,A{,}}C,D,E,\underline {B,F} \right)$
Und schon ist das mutierte Genom P1 fertig.	$P_1 = \left( G,A,C,D,E,B,F \right)$

Spiegelung

Eine weitere Variante von Mutation von Permutationen ist folgendes Verfahren:

Verfahren	Beispiel
Gegeben ist eine Permutation,	$P_0 = \left( A,B,C,D,E,F,G \right)$
Man wähle eine Teil-Liste aus, also einen Start-Index i und einen End-Index j in P0, sodass $i,j \in \left( \left[0, \left|P_0\right| \right[ \cap \mathbb{N} \right)$. Man beachte, dass der Start-Index nach dem End-Index kommen kann. Dann fängt die Teil-Liste einfach von vorne wieder an. (Dies ist notwendig, damit die Permutationswahrscheinlichkeit im Genom überall gleich ist und nicht in der Mitte größer ist als an den Rändern.)	i = 5, j = 2
Man kopiere P0 nach P1 und spiegele die Teil-Liste.	$P_1 = \left( \underline {G,F{,}}C,D,E,\underline {B,A} \right)$
Und schon ist das mutierte Genom P1 fertig.	$P_1 = \left( G,F,C,D,E,B,A \right)$

Diese Variante ist besser geeignet zur Lösung vom Problem des Handlungsreisenden, da hier die Änderung der Nachbarschaft minimal gehalten werden sollte und durch die Spiegelung einfach ein Teil-Weg in umgekehrter Reihenfolge gegangen wird.