170 171

170 Zadanie transportowe i problem komiwojażera

Tablica 3.38

*12	*13	X,A		*21	*2.3	*24	*25		*32	*34	*35	*4.		*4.1	*45	*51	*52	*33	<«
0	0	0	t	i	0	0	0	0	0	i	0	0	1	0	0	0	0	i	0

3.6.3. Mechanizmy działania

algorytmu genetycznego

Zadanie komiwojażera jest również rozwiązywane za pomocą metod przybliżonych. Najprostszy algorytm przybliżony polega na konstrukcji trasy komiwojażera w taki sposób, by kolejno włączać miasta, położone najbliżej, które nie były dotąd odwiedzane. Stosując tę najprostszą możliwość, należałoby zaplanować przejazd z miasta I do miasta 2 (odległość 10), następnie z miasta 2 do miasta 4 (odległość 10), z miasta 4 do miasta 3 (odległość 10), z miasta 3 do miasta 5 (odległość 12) oraz z miasta 5 do miasta 1 (odległość i 1). Okazuje się, że łączna długość trasy jest taka sama, jak w przypadku otrzymanego uprzednio rozwiązania optymalnego i wynosi 53. Skuteczność tej najprostszej metody jest jednak pozorna, gdyż w wielu przypadkach trasa, otrzymana w taki sposób, będzie znacząco dłuższa od trasy optymalnej.

Jednym ze sposobów uzyskania dobrych rozwiązań przybliżonych jest zastosowanie algorytmów genetycznych, wymagających wykonania operacji na rozwiązaniach przedstawionych w postaci zer i jedynek.

Działanie algorytmów genetycznych jest wzorowane na mechanizmach zaczerpniętych z genetyki, dlatego też przy ich opisie wykorzystywana jest specyficzna nomenklatura. Rozpatrywane podzbiory rozwiązań (niekoniecznie dopuszczalnych) o ustalonej liczbie elementów nazywamy populacją. Pierwszą losowo wygenerowaną populację nazywa się populacją początkową. Rozwiązania nazywamy chromosomami i przedstawiamy je w postaci zer i jedynek. Kolejne elementy tworzące chromosom nazywane są genami. Ocena jakości konkretnego chromosomu polega na obliczeniu wartości funkcji oceniającej, zwanej funkcją przystosowania i odpowiadającej funkcji celu rozpatrywanego problemu optymalizacyjnego. Funkcja przystosowania powinna uwzględniać możliwość rozróżnienia rozwiązań dopuszczalnych od niedopuszczalnych. Można to osiągnąć poprzez wprowadzenie systemu kar dla chromosomów naruszających warunki dopuszczalności zadania wyjściowego.

W kolejnych iteracjach algorytmu genetycznego ocenia się rozpatrywaną aktualnie populację oraz stosuje losowe mechanizmy selekcji, krzyżowania i mutacji w celu wygenerowania kolejnej populacji.

Selekcja służy do wyboru chromosomów przy generowaniu nowej populacji. Polega na wybraniu zbioru chromosomów o tej samej liczności, co populacja początkowa, które staną się rodzicami nowotworzonej populacji potomków. Ma ona przebieg losowy, jednak przeprowadzona jest w taki sposób, aby chromosomy

najlepsze miały największe szanse wylosowania. Bardzo często przeprowadza się selekcję, bazując na regule ruletki. Poszczególne działki na tarczy ruletki odpowiadają poszczególnym chromosomom i są odpowiednio wyskalowane w stosunku do wartości funkcji przystosowania.

Krzyżowanie ma następujący przebieg: z grupy chromosomów przeznaczonych do krzyżowania tworzone są losowo pary rodziców. Dla każdej pary rodziców losowany jest punkt krzyżowania, który oznaczamy symbolem p. Stosowana jest następująca reguła:

—    potomek pierwszy otrzymuje p genów od rodzica pierwszego, a pozostałe geny, począwszy od genu p+ 1. od rodzica drugiego,

—    potomek drugi otrzymuje pierwsze p genów od rodzica drugiego, natomiast pozostałe geny, począwszy od genu p + 1, od rodzica pierwszego.

Mutacja chromosomu polega na zamianie genu odpowiednio z 0 na 1 lub z 1 na 0. Przyjmujemy, że prawdopodobieństwo wystąpienia mutacji jest niewielkie.

Warunek końca algorytmu w najprostszym przypadku zakłada z góry określona liczbę iteracji (zazwyczaj rzędu kilku tysięcy). Najlepszy z otrzymanych chromosomów traktowany jest jako rozwiązanie danego problemu. Algorytm należy zakończyć również wówczas, gdy dwie kolejne populacje nie różnią się między sobą.

3.6.4. Symulacja działania

algorytmu genetycznego

Pokażemy działanie algorytmu genetycznego dla zadania, przedstawionego w przykładzie 3.5.

Populacja początkowa

Każdy chromosom można przedstawić jako 20-elementowy ciąg zer i jedynek. Przyjmiemy, że liczność populacji początkowej (i każdej następnej populacji) wynosi 6. Ponieważ w rozwiązaniu dopuszczalnym z każdego miasta należy wyjechać do jednego z czterech pozostałych, dlatego kolejne geny każdego z chromosomów, wchodzących w skład populacji początkowej uzyskujemy jako wynik losowania, w którym 0 pojawia się z prawdopodobieństwem 0,75, natomiast I — z prawdopodobieństwem 0,25. Chromosomy, otrzymane w wyniku zastosowania takiego mechanizmu losowego, przedstawia tablica 3.39. Wylosowane chromosomy oznaczamy jako Cu, C12, Cn, Cu, Co i Cu,.

Kolejne chromosomy przedstawione zostały graficznie na rysunku 3.3.

Widać, że żaden z wylosowanych chromosomów nie jest rozwiązaniem dopuszczalnym.