174 175

174 Zadanie transportowe i problem komiwojażera

Tablica 3.41

Chromosom	Wartość funkcji przystosowania	Odwrotność wartości funkcji przystosowania	Suma odwrotności funkcji przystosowania	Prawdopodobieństwa selekcji
c„	1 109	0,0009017	0,0138631	0,065044 « 7%
£*12	250	0,0040000		0,288536 ss 29%
C|3	269	0,0037175		0.268156 s= 27%.
C|4	551	0,0018149		0.130915ss 13%
Cif,	785	0,0012739		0,091890 sr 9%
C,4	464	0,0021552		0.155461 *5 15%

Tablica 3.42

Chromosom	*12	* 1 3	*14	*15	*21	*24	*24	*25	*31	*32	*34	*35	*41	*42	*43	*45	*51	*52	*53	*54	PK
c„	0	0	0	1	0	1	0	0	1	0	0	1	0	0	0	0	1	0	0	1	11
	0	0	1	0	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	1
C,J	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	0	1	0	0	0	3
Cl2	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	0	1	0	0	0
C14	0	0	0	1	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	17
C„	0	0	1	0	1	0	0	0	1	0	0	0	0	0	0	1	0	0	1	0

(może nim być mechanizm ruletki) i otrzymujemy populację przed krzyżowaniem. Wylosowane chromosomy przedstawiono w tablicy 3.42.

Chromosomy łączymy w pary. Pierwszą parę stanowią chromosomy Cis i Cić, druga parę — C12 i Cu, trzecią — C14 i C’u. Wybór każdego punktu krzyżowania powinien być równie prawdopodobny. Ponieważ mamy 19 punktów krzyżowania (PK), prawdopodobieństwo wybrania każdego z nich wynosi 1/19=0,00526. Wykorzystując mechanizm losowy uwzględniający to prawdopodobieństwo, losujemy punkty krzyżowania PK i otrzymujemy: dla pary pierwszej — 11, dla pary drugiej — 3, dla pary trzeciej — 17 (tablica 3.42).

Dokonujemy krzyżowania chromosomów zgodnie z opisaną uprzednio zasadą. Dla pary pierwszej pierwszy potomek C21 ma 11 pierwszych genów od chromosomu Cis, a pozostałe 9 — od chromosomu C16. Drugi potomek — C21 — ma pierwszych I 1 genów od chromosomu Ci6, a pozostałe od chromosomu C15. Para druga to dwa chromosomy C12, stąd też, niezależnie od tego, jaki byłby punkt krzyżowania, potomkowie — C23 i C24 — mają taki sam zestaw genów, jak ich rodzice. Wreszcie dla pary trzeciej pierwszy potomek — C25 — ma 17 pierwszych genów od chromosomu C14 oraz pozostałe 3 geny od chromosomu Cu. Drugi potomek — C26 ma 17 pierwszych genów od chromosomu Cu oraz pozostałe 3 od chromosomu Cu.

Mutacja

Przyjmujemy prawdopodobieństwo mutacji na poziomie 1/100. Uruchamiając mechanizm losowy uwzględniający to prawdopodobieństwo, otrzymujemy stwierdzamy, że mutacja pojawiła się w chromosomie C-m w szóstym genie. Chromosom ten przed i po dokonaniu mutacji przedstawiono w tablicy 3.43.

Tablica 3.43

Chromosom	*17	*jj	A u	*15	*21	*23	*24	*25	*31	*32	*34	*35	*41	*42	*43	*45	*51	*52	*53	*54
Cu	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	0	1	0	0	0
Ci4	1	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	I	0	0	0

Otrzymujemy w ten sposób populację początkowa dla nowej iteracji, przedstawioną w tablicy 3.44.

Tablica 3.44

Chromosom	*12	*1.1	*14	*15	*21	*2?	*24	*25	*31	*32	*34	*35	*41	*42	*41	*45	*51	*52	*51	*54
^21	0	0	0	1	0	1	0	0	1	0	0	0	0	t	0	0	0	0	0	1
c,2	0	0	1	0	0	1	0	0	0	0	0	1	0	0	0	0	1	0	0	1
C23	1	0	0	0	0	1	0	0	0	0	1	0	0	0	0	0	1	0	0	0
Ci4	]	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0
£25	0	0	0	I	0	0	1	0	0	0	0	0	0	1	0	0	1	0	1	0
£26	0	0	1	0	1	0	0	0	1	0	0	0	0	0	0	1	0	0	0	I

Chromosomy te przedstawiono graficznie na rysunku 3.4.

W populacji początkowej dla drugiej iteracji znajduje się chromosom C21, odpowiadający rozwiązaniu dopuszczalnemu. Widzimy więc, że połączenie w pary dwóch chromosomów, które nie są dopuszczalne, może w wyniku reprodukcji dać potomka, będącego rozwiązaniem dopuszczalnym. Oczywiście mogłaby zaistnieć również sytuacja odwrotna i w wyniku krzyżowania dwóch chromosomów, odpowiadających rozwiązaniom dopuszczalnym, po krzyżowaniu otrzymalibyśmy dwa chromosomy niedopuszczalne.

Wartości funkcji przystosowania dla kolejnych rozwiązań, tworzących otrzymaną populacje, przedstawia tablica 3.45.

Średnia wartość funkcji przystosowania zmniejszyła się i wynosi obecnie 358,33. Jednocześnie wartość najlepszego znalezionego dotychczas rozwiązania znacząco się obniżyła. O ile dla populacji wyjściowej wartość ta wynosiła 250, to obecnie wynosi ona 72.