Mutation von Permutationen

aus Wikipedia, der freien Enzyklopädie

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 werden sollte und durch die Spiegelung einfach ein Teil-Weg in umgekehrter Reihenfolge gegangen wird.

Kategorie: Künstliche Intelligenz

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Mutation von Permutationen

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] Rotation nach rechts

[Bearbeiten] Spiegelung

Views

Navigation

Mitmachen

Suche