Wprowadzenie:

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.

PMX

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}

Mutacje:

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:

1.Mutacja 2-punktowa

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}

2.Mutacja wymierna:

Elementy przed liniami cięcia zamieniamy miejscami:

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

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