[b]Wprowadzenie:[/b]

Jednym z wielu operatorów krzyżowania algorytmów genetycznych jest operator krzyżowania PMX. Moim zdaniem jest to najprostszy operator. Poniżej w prostych słowach przedstawię sposób przeprowadzenia krzyżowania operatorem PMX na dwóch przykładowych rodzicach.

[b]PMX[/b]

Punkt „cięcia” genotypów „rodziców”: po 3cim i 6tym genie Przykładowi „rodzice”:

Os1 = {3,5,1,2,4,6,8,9,7} 0s2 = {9,5,6,8,7,4,1,3,2}

1.Dokonujemy „cięcia”: Os1 = {3,5,1,|2,4,6,|8,9,7} 0s2 = {9,5,6,|8,7,4,|1,3,2}

2.Zamieniamy miejscami środki rodziców… (2<->8, 4<->7 i 6<->4)

Os1 = {3,5,1,|8,7,4,|8,9,7} 0s2 = {9,5,6,|2,4,6,|1,3,2}

…i wywalamy geny „zewnętrzne” równe tym w środku

Os1 = {3,5,1,|8,7,4,|X,9,X} 0s2 = {9,5,X,|2,4,6,|1,3,X}

(genami, które powtarzają się w środku i na zewnątrz są 8,7,2,6. Zamiast nich tymczasowo wstawiłem X. (geny w środku nie są zmieniane).)

3.Miejsca oznaczone X zmieniamy za pomocą reguł, jakimi zamienialiśmy środki: (jeśli X było 6, to teraz będzie 4. Patrz pkt2):

Os1 = {3,5,1,|8,7,4,|2,9,4} 0s2 = {9,5,4,|2,4,6,|1,3,8}

4.Otrzymujemy potomków:

Pt1 = {3,5,1,8,7,4,2,9,4} Pt2 = {9,5,4,2,4,6,1,3,8}

[b]Mutacje:[/b]

Mutacje wprowadzają do genotypu losowe zmiany. Ich zadaniem jest wprowadzanie różnorodności w populacji, czyli zapobieganie (przynajmniej częściowe) przedwczesnej zbieżności algorytmu. Poniżej przedstawiam dwie metody mutacji genotypów:

[b]1.Mutacja 2-punktowa[/b] Przeprowadzamy linie cięcia i przepisujemy środek od tyłu np.:

Os1 = {1,2,3,4,5,6}

Linie cięcia po 2-gim i 5-tym genie

Os1 = {1,2,|3,4,5,|6}

I dokonujemy mutacji:

Os1’ = {1,2,5,4,3,6}

[b]2.Mutacja wymierna:[/b]

Elementy przed liniami cięcia zamieniamy miejscami:

Os1 = {1,2,|3,4,5,|6}

Os1’ = {1,5,3,4,2,6}