4552034828

3.3 Krzyżowanie

Zdawać by się mogło, że algorytm krzyżowania sprowadza się do przedzielenia dwóch równolicznych ścieżek w tym samym losowym kroku i zamienienia miejscami „odciętych" części ścieżek:

Przed krzyżowaniem:	Po skrzyżowaniu:
Ścieżka #1: A B C D E F	Ścieżka #1: A B~^^H
Ścieżka	Ścieżka #2: |) F C D E F
^A Losowa oś krzyżowania

Jednak widać, że uzyskane w ten sposób ścieżki są niepoprawne - ścieżka #1 dwukrotnie zawiera miasta A i B, tak samo ścieżka #2 zawiera podwójne miasta D i F. W związku z tym należało nieco zmodyfikować proces krzyżowania.

W naszym algorytmie krzyżowane ze sobą chromosomy (ścieżki) zawsze będą miały tę samą ilość alleli (miast) - dla przykładu przyjmijmy ilość P.

1.    W pierwszym kroku generujemy liczbę pseudolosową R z zakresu <1, P-l>, czyli tak, aby wyeliminować krańcowe wartości - będzie to nasza oś krzyżowania.

2.    Następnie bierzemy (R+l)-wsze miasto Ml ze ścieżki pierwszej oraz (R+l)-wsze miasto M2 ze ścieżki drugiej. Przechodzimy przez wszystkie miasta ścieżki pierwszej zamieniając wszystkie wystąpienia miasta Ml miastem M2, a wystąpienia miasta M2 zamieniając na Ml. Analogicznie przechodzimy przez wszystkie miasta ścieżki drugiej w identyczny sposób podmieniając miasta.

Przykładowo: P=6; R=2; Ml=|; M2=|;

(Kolor    oznacza zamienione miasta)

Przed krzyżowaniem:

Po zamianie Ml z M2 dla miasta R+l:

Ścieżka #1: Ścieżka #2:

■ HfH

Ścieżka #1: Ścieżka #2:

:B ADE F

^A Oś krzyżowania R

3. Powtarzamy poprzedni krok rozpatrując następne w kolejności miasto - (R+2)-gie, (R+3)-cie, dochodząc do miasta (P-l)-wszego włącznie.

Teraz Ml=g; M2=|;

Po zamianie Ml z M2 dla miasta R+2:

Ścieżka #1:    C    D    A    B    E    F

Ścieżka #2:    |B    F    C    D    E    A

Teraz Ml=|; M2=|;

Po zamianie Ml z M2 dla miasta R+3:

Ścieżka #1:

Ścieżka #2:

Teraz Ml=g;M2=|;

Po zamianie Ml z M2 dla miasta R+4:

Ścieżka #1:    C    D    F    B    E    A

Ścieżka #2:    B    A    C    D    E    F