Mutation von Permutationen

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

[Bearbeiten] 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 $P 0$ , 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 $P 0$ nach $P 1$ 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 $P 1$ fertig.	$P_1 = \left( G,A,C,D,E,B,F \right)$

[Bearbeiten] 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 $P 0$ , 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 $P 0$ nach $P 1$ und spiegele die Teil-Liste.	$P_1 = \left( \underline {G,F{,}}C,D,E,\underline {B,A} \right)$
Und schon ist das mutierte Genom $P 1$ 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 sollte und durch die Spiegelung einfach ein Teil-Weg in umgekehrter Reihenfolge gegangen wird.

Von „http://de.wikipedia.org../../../m/u/t/Mutation_von_Permutationen_36b4.html“

Kategorie: Künstliche Intelligenz

Mutation von Permutationen

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] Rotation nach rechts

[Bearbeiten] Spiegelung

Views

Navigation

Mitmachen

Suche