{"id":2356,"date":"2020-07-29T17:29:21","date_gmt":"2020-07-29T15:29:21","guid":{"rendered":"https:\/\/www.kompikownia.pl\/?p=2356"},"modified":"2021-03-13T14:09:59","modified_gmt":"2021-03-13T13:09:59","slug":"problem-komiwojazera-rozwiazywany-algorytmem-genetycznym","status":"publish","type":"post","link":"https:\/\/www.kompikownia.pl\/index.php\/2020\/07\/29\/problem-komiwojazera-rozwiazywany-algorytmem-genetycznym\/","title":{"rendered":"Problem komiwoja\u017cera rozwi\u0105zywany algorytmem genetycznym"},"content":{"rendered":"Czas czytania:<\/span> 8<\/span> minut<\/span><\/span>\n

Sztuczna inteligencja, perceptrony, algorytmy genetyczne – pewnie cz\u0119sto s\u0142ysza\u0142e\u015b te s\u0142owa. Coraz wi\u0119cej rzeczy staje si\u0119 „inteligentnych”. Sztuczn\u0105 inteligencj\u0119 (AI) wsadza si\u0119 do wszystkiego – telefon\u00f3w, telewizor\u00f3w itd. Czy to dobrze? Nie wiem. Lecz na pewno warto wiedzie\u0107, jak to mniej wi\u0119cej dzia\u0142a. Dlatego w tym artykule przeanalizujemy dzia\u0142anie jednego z algorytm\u00f3w, kt\u00f3ry wchodzi w sk\u0142ad bardzo du\u017cej rodziny AI – algorytmu genetycznego<\/strong>. Rozwi\u0105\u017cemy za jego pomoc\u0105 problem komiwoja\u017cera. <\/strong><\/p>\n\n\n\n

\n

Problem komiwoja\u017cera? Co to jest? <\/h2>\n\n\n\n

Problem komiwoja\u017cera jest jednym z najbardziej charakterystycznych i popularnych problem\u00f3w optymalizacyjnych wsp\u00f3\u0142czesnej algorytmiki. Charakteryzuje si\u0119 on nast\u0119puj\u0105co. <\/p>\n\n\n\n

Jest sobie pewien cz\u0142owiek, zwany komiwoja\u017cerem. Jak ka\u017cdy sprzedawca, handluje jakimi\u015b, bli\u017cej nieokre\u015blonymi, towarami. Oczywi\u015bcie, pragn\u0105\u0142by zarobi\u0107 jak najwi\u0119cej. Musi wi\u0119c wyruszy\u0107 ze swojego domu i odwiedzi\u0107 wszystkie miasta, kt\u00f3re mog\u0105 by\u0107 zainteresowane ofert\u0105. Nast\u0119pnie chcia\u0142by wr\u00f3ci\u0107 do miasta, z kt\u00f3rego zacz\u0105\u0142 podr\u00f3\u017c. Komiwoja\u017cer musi zarabia\u0107, wi\u0119c chcia\u0142by odwiedza\u0107 miasta w takiej kolejno\u015bci, aby przejecha\u0107 jak najmniej kilometr\u00f3w. Dzi\u0119ki temu oszcz\u0119dzi na benzynie i wi\u0119cej zostanie w jego kieszeni.<\/p>\n\n\n\n

Problem pozornie mo\u017ce nie wydawa\u0107 si\u0119 trudny. Nie b\u0119dziemy wchodzili tu w zawi\u0142o\u015bci matematyczne r\u00f3\u017cnych teorii, gdy\u017c to nie jest celem tego artyku\u0142u. Przeanalizujemy problem u\u017cywaj\u0105c jak najprostszych poj\u0119\u0107. <\/p>\n\n\n\n

Problem komiwoja\u017cera – ilo\u015b\u0107 tras<\/h3>\n<\/div><\/div>\n\n\n\n

Jaki by\u0142by najprostszy spos\u00f3b na znalezienie najkr\u00f3tszej trasy? Wyznaczenie wszystkich mo\u017cliwo\u015bci i wybranie najkr\u00f3tszej. No jasne – to samo nasuwa si\u0119 na my\u015bl! Przecie\u017c taki spos\u00f3b zawsze da po pewnym czasie najlepszy wynik. Sprawd\u017amy na przyk\u0142adzie. <\/p>\n\n\n\n

<\/td>Ostrowiec \u015awi\u0119tokrzyski<\/td>Kielce<\/td>Warszawa<\/td>Krak\u00f3w<\/td>Pozna\u0144<\/td>Lublin<\/td><\/tr>
Ostrowiec \u015awi\u0119tokrzyski<\/td>0 km<\/td>61 km<\/td>177 km<\/td>188 km<\/td>381 km<\/td>104 km<\/td><\/tr>
Kielce<\/td>61 km<\/td>0<\/td>177 km<\/td>118 km<\/td>338 km<\/td>165 km<\/td><\/tr>
Warszawa<\/td>177 km<\/td>177 km<\/td>0 km<\/td>294 km<\/td>296 km<\/td>165 km<\/td><\/tr>
Krak\u00f3w<\/td>188 km<\/td>118 km<\/td>294 km<\/td>0 km<\/td>368 km<\/td>255 km<\/td><\/tr>
Pozna\u0144<\/td>381 km<\/td>338 km<\/td>296 km<\/td>368 km<\/td>0 km<\/td>440 km<\/td><\/tr>
Lublin<\/td>104 km<\/td>165 km<\/td>165 km<\/td>255 km<\/td>440 km<\/td>0 km<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Jakie istniej\u0105 mo\u017cliwe trasy, takie aby\u015bmy rozpocz\u0119li i sko\u0144czyli w tym samym mie\u015bcie?<\/p>\n\n\n\n

L.p<\/td>Miasto 1<\/td> Miasto 2<\/td>Miasto 3<\/td>Miasto 4<\/td>Miasto 5<\/td>Miasto 6<\/td>Miasto 7<\/td>Dystans<\/td><\/tr>
1<\/td>Ostrowiec<\/td>Krak\u00f3w<\/td>Kielce<\/td>Warszawa<\/td>Lublin<\/td>Pozna\u0144<\/td>Ostrowiec<\/td>1469 km<\/td><\/tr>
2<\/td>Krak\u00f3w<\/td>Ostrowiec<\/td>Kielce<\/td>Warszawa<\/td>Pozna\u0144<\/td>Lublin<\/td>Krak\u00f3w<\/td>1417 km<\/td><\/tr>
3<\/td>Kielce<\/td>Ostrowiec<\/td>Krak\u00f3w<\/td>Lublin<\/td>Pozna\u0144<\/td>Warszawa<\/td>Kielce<\/td>1417 km<\/td><\/tr>
4<\/td>Ostrowiec<\/td>Lublin<\/td>Pozna\u0144<\/td>Warszawa<\/td>Kielce<\/td>Krak\u00f3w<\/td>Ostrowiec<\/td>1323 km<\/td><\/tr>
5<\/td>Lublin<\/td>Warszawa<\/td>Ostrowiec<\/td>Pozna\u0144<\/td>Krak\u00f3w<\/td>Kielce<\/td>Lublin<\/td>1374 km<\/td><\/tr>
6<\/td>Pozna\u0144<\/td>Lublin<\/td>Krak\u00f3w<\/td>Ostrowiec<\/td>Kielce<\/td>Warszawa<\/td>Pozna\u0144<\/td>1417 km<\/td><\/tr>
7<\/td>Ostrowiec<\/td>Pozna\u0144<\/td>Warszawa<\/td>Kielce<\/td>Krak\u00f3w<\/td>Lublin<\/td>Ostrowiec<\/td>1331 km<\/td><\/tr>
…<\/td>…<\/td>…<\/td>…<\/td>…<\/td>…<\/td>…<\/td>…<\/td>…<\/td><\/tr>
360<\/td>Warszawa<\/td>Pozna\u0144<\/td>Krak\u00f3w<\/td>Kielce<\/td>Ostrowiec<\/td>Lublin<\/td>Warszawa<\/td> 1197 km<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Jak widzisz – mamy tylko 6 miast. Istnieje mi\u0119dzy nimi a\u017c 360 unikalnych mo\u017cliwych po\u0142\u0105cze\u0144! W tabelce, jak widzisz, nie zosta\u0142y wypisane wszystkie mo\u017cliwo\u015bci. Jak wi\u0119c wyznaczy\u0107 ich ilo\u015b\u0107?<\/p>\n\n\n\n

Zak\u0142adaj\u0105c, \u017ce mo\u017cemy wystartowa\u0107 w dowolnym mie\u015bcie, istnieje n! mo\u017cliwych tras. Dla przyk\u0142adu powy\u017cej: Pierwsze miasto mo\u017cemy wybra\u0107 na 6 sposob\u00f3w, drugie na 5 (gdy\u017c jedno miasto wykorzystali\u015bmy ju\u017c na pierwszej pozycji), trzecie miasto na 4 sposoby itd. Efektywnie b\u0119dzie to 6*5*4*3*2*1=6! mo\u017cliwych tras. Upro\u015b\u0107my troch\u0119 rozwa\u017cania i przyjmijmy \u017ce trasa O->KR->KI->L->P->O b\u0119dzie mia\u0142a tak\u0105 sam\u0105 d\u0142ugo\u015b\u0107 jak trasa O->P->L->KI->KR->O (miasta s\u0105 odwiedzane w odwrotnej kolejno\u015bci). Dzi\u0119ki temu mo\u017cemy ograniczy\u0107 nieco ilo\u015b\u0107 sprawdzanych opcji. Ilo\u015b\u0107 tras mo\u017cemy wyznaczy\u0107 za pomoc\u0105 wzoru:<\/p>\n\n\n

\"\frac{n!}{2}\"<\/center><\/p>\n\n\n\n

Je\u015bli chcemy rozwi\u0105za\u0107 problem komiwoja\u017cera przypadku, gdy miasto startowe zosta\u0142o okre\u015blone i jest sta\u0142e (np.: Ostrowiec dla powy\u017cszego przypadku) – wz\u00f3r przyjmie nast\u0119puj\u0105c\u0105 posta\u0107:<\/p>\n\n\n

\"\frac{(n-1)!}{2}\"<\/center><\/p>\n\n\n\n

Powy\u017cej opisane zbiory miast s\u0105 tzw. permutacjami.<\/em><\/p>\n\n\n\n

Zauwa\u017c, \u017ce je\u015bli chcieliby\u015bmy sprawdzi\u0107 r\u0119cznie ka\u017cd\u0105 mo\u017cliw\u0105 tras\u0119, ilo\u015b\u0107 tras kt\u00f3re musimy sprawdzi\u0107 b\u0119dzie ros\u0142a bardzo szybko. Za\u0142\u00f3\u017cmy, \u017ce dysponujemy komputerem przeliczaj\u0105cym milion operacji na sekund\u0119. Poni\u017csza tabelka przedstawia czas dzia\u0142ania algorytmu: (zak\u0142adamy \u017ce mo\u017cemy startowa\u0107 w dowolnym mie\u015bcie<\/p>\n\n\n\n

Ilo\u015b\u0107 miast<\/td>Ilo\u015b\u0107 tras<\/td>Czas dzia\u0142ania algorytmu<\/td><\/tr>
10<\/td>1 814 400<\/td>1.8s<\/td><\/tr>
11<\/td>19 958 400<\/td>19s<\/td><\/tr>
12<\/td>239 500 800<\/td>239s<\/td><\/tr>
13<\/td>3 113 510 400<\/td>51 minut<\/td><\/tr>
14<\/td>43 589 145 600<\/td>726 minut<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Z tego powodu powsta\u0142o wiele metod wyznaczania przybli\u017conego<\/em> rozwi\u0105zania problemu komiwoja\u017cera, kt\u00f3re nie wymagaj\u0105 sprawdzania wszystkich mo\u017cliwych kombinacji. Jednym z takich sposob\u00f3w jest algorytm genetyczny.<\/p>\n\n\n\n

Algorytm genetyczny – na czym polega?<\/h2>\n\n\n\n

Czym jest algorytm genetyczny? Jest to swego rodzaju „symulacja ewolucji”. Co przez to mo\u017cna rozumie\u0107? <\/p>\n\n\n\n

Mamy na pocz\u0105tku pewn\u0105 populacj\u0119. Ta populacja sk\u0142ada si\u0119 z osobnik\u00f3w. Ka\u017cdy z nich posiada pewien wska\u017anik, kt\u00f3ry okre\u015bla jak dobrze jest on przystosowany do \u017cycia. Ka\u017cdy osobnik posiada te\u017c sw\u00f3j „kod genetyczny”, kt\u00f3ry okre\u015bla w jaki spos\u00f3b rozwi\u0105\u017ce on dany problem. <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Powy\u017cej znajduje si\u0119 schemat blokowy przyk\u0142adowego algorytmu genetycznego. Jak widzisz, nie jest on skomplikowany. <\/p>\n\n\n\n

Przygotowanie – w jaki spos\u00f3b zakodowa\u0107 genom?<\/h3>\n\n\n\n

Kodowanie jest jednym z najwa\u017cniejszych etap\u00f3w opracowywania algorytmu genetycznego rozwi\u0105zuj\u0105cego dany problem. Dlaczego? Gdy\u017c w\u0142a\u015bnie spos\u00f3b zakodowania informacji w genomie oraz opracowanie funkcji przystosowania decyduj\u0105 o tym, jakiego operatora selekcji czy krzy\u017cowania u\u017cyjemy oraz jak dobry b\u0119dzie nasz algorytm. <\/p>\n\n\n\n

Zastan\u00f3wmy si\u0119, w jaki spos\u00f3b mo\u017cemy zakodowa\u0107 w spos\u00f3b jednoznaczny <\/strong>genom pojedynczego osobnika, kt\u00f3ry pomo\u017ce nam rozwi\u0105za\u0107 problem komiwoja\u017cera? Kto b\u0119dzie w og\u00f3le takim osobnikiem?<\/p>\n\n\n\n

Szukamy najbardziej optymalnej trasy, a wi\u0119c w\u0142a\u015bnie pojedyncza trasa b\u0119dzie najlepszym wyborem na naszego „wzorcowego” osobnika. Genomem osobnika b\u0119dzie natomiast lista miast. Miejscowo\u015bci oznaczymy sobie kolejnymi liczbami. Odczytuj\u0105c genom od lewej do prawej otrzymamy kolejno\u015b\u0107 w jakiej powinni\u015bmy odwiedza\u0107 miasta. <\/p>\n\n\n\n

Przygotowanie – warunek stopu<\/h3>\n\n\n\n

Sp\u00f3jrz na bloczek oznaczony STOP? na wykresie. Jest to nasz warunek stopu. Co to jest? M\u00f3wi nam o tym, kiedy nasz algorytm powinien przesta\u0107 dzia\u0142a\u0107. Je\u015bli nie okre\u015blimy warunku stopu – algorytm genetyczny b\u0119dzie wykonywany w niesko\u0144czono\u015b\u0107. <\/p>\n\n\n\n

Jakie mog\u0105 by\u0107 warunki stopu? Przer\u00f3\u017cne. Od najprostszych (pokroju ilo\u015bci iteracji algorytmu) przez bardzo z\u0142o\u017cone (np.: zatrzymujemy algorytm wtedy, kiedy osi\u0105gniemy zadowalaj\u0105ce nas wyniki). <\/p>\n\n\n\n

Przygotowanie – funkcja przystosowania<\/h3>\n\n\n\n

Ostatnim krokiem „przygotowawczym” jest opracowanie funkcji przystosowania. Czym jest funkcja przystosowania? Przekazuje nam ona informacje o tym, jak dobry jest konkretny osobnik. <\/strong>Czym jest lepszy, tym warto\u015b\u0107 funkcji przystosowania powinna by\u0107 wi\u0119ksza. <\/p>\n\n\n\n

Funkcja przystosowania powinna by\u0107 sformu\u0142owana w prosty i efektywny spos\u00f3b. Powinna jasno przekazywa\u0107, czy osobnik A jest lepszym kandydatem do reprodukcji, czy jednak osobnik B. <\/p>\n\n\n\n

Co b\u0119dzie najlepsz\u0105 funkcj\u0105 przystosowania w naszym wypadku? Zale\u017cy nam na tym, aby odnaleziona trasa by\u0142a jak najkr\u00f3tsza. Wydaje si\u0119 intuicyjnie, \u017ce to w\u0142a\u015bnie d\u0142ugo\u015b\u0107 trasy powinna by\u0107 wska\u017anikiem, jak dobry jest dany osobnik. <\/p>\n\n\n\n

Jest jedyny drobny problem. W przypadku problemu komiwoja\u017cera kr\u00f3tsza trasa (a wi\u0119c mniejsza warto\u015b\u0107) jest lepsza. Natomiast funkcja dostosowania formalnie dzia\u0142a na odwr\u00f3t. Im wi\u0119ksza warto\u015b\u0107 – tym lepiej. Sformu\u0142ujemy wi\u0119c nasz\u0105 funkcj\u0119 jako odwrotno\u015b\u0107 ca\u0142kowitej d\u0142ugo\u015bci trasy zapisan\u0105 w genomie. (funkcja przystosowania=1\/ca\u0142kowita d\u0142ugo\u015b\u0107 trasy)<\/p>\n\n\n\n

Etap zerowy – wygenerowanie populacji<\/h3>\n\n\n\n

W celu zilustrowania przyk\u0142adami kolejnych etap\u00f3w algorytmu genetycznego, „wygenerujmy” sobie populacj\u0119. Za\u0142\u00f3\u017cmy, \u017ce chcemy wyznaczy\u0107 najlepsz\u0105 tras\u0119 pomi\u0119dzy sze\u015bcioma miejscowo\u015bciami. Za\u0142\u00f3\u017cmy, \u017ce rozmiar naszej populacji wynosi 8. (Oczywi\u015bcie w rzeczywistej implementacji, im wi\u0119ksza ilo\u015b\u0107 osobnik\u00f3w w populacji tym szybciej osi\u0105gniemy dobre rezultaty) W celu \u0142atwiejszej prezentacji pomno\u017cymy warto\u015b\u0107 funkcji przystosowania przez 1 000 000 i zaokr\u0105glimy do liczb ca\u0142kowitych. Dzi\u0119ki temu nie b\u0119dziemy m\u0119czyli si\u0119 z u\u0142amkami w przyk\u0142adach.<\/p>\n\n\n\n

Zakodujmy sobie miasta w nast\u0119puj\u0105cy spos\u00f3b:
1 – Ostrowiec \u015awi\u0119tokrzyski
2 – Kielce
3 – Warszawa
4 – Krak\u00f3w
5 – Pozna\u0144
6 – Lublin<\/p>\n\n\n\n

Nasi osobnicy te\u017c s\u0105 znani – to s\u0105 trasy kt\u00f3re zosta\u0142y ju\u017c obliczone we wcze\u015bniejszej cz\u0119\u015bci tego artyku\u0142u. Zakodujmy je teraz<\/p>\n\n\n\n

L.p<\/td>Miasto 1<\/td>Miasto 2<\/td>Miasto 3<\/td>Miasto 4<\/td>Miasto 5<\/td>Miasto 6<\/td>Warto\u015b\u0107 funkcji przystosowania<\/td><\/tr>
A<\/td>1<\/td>4<\/td>2<\/td>3<\/td>6<\/td>5<\/td>681<\/td><\/tr>
B<\/td>4<\/td>1<\/td>2<\/td>3<\/td>5<\/td>6<\/td>706<\/td><\/tr>
C<\/td>2<\/td>1<\/td>4<\/td>6<\/td>5<\/td>3<\/td>706<\/td><\/tr>
D<\/td>1<\/td>6<\/td>5<\/td>3<\/td>2<\/td>4<\/td>756<\/td><\/tr>
E<\/td>6<\/td>3<\/td>1<\/td>5<\/td>4<\/td>2<\/td>728<\/td><\/tr>
F<\/td>5<\/td>6<\/td>4<\/td>1<\/td>2<\/td>3<\/td>706<\/td><\/tr>
G<\/td>1<\/td>5<\/td>3<\/td>2<\/td>4<\/td>6<\/td>751<\/td><\/tr>
H<\/td>3<\/td>5<\/td>4<\/td>2<\/td>1<\/td>6<\/td>835<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Zauwa\u017cy\u0142e\u015b, \u017ce w powy\u017cszym kodowaniu nie zosta\u0142 „uwzgl\u0119dniony” powr\u00f3t do miasta pocz\u0105tkowego? Zrobili\u015bmy tak, aby wprowadzi\u0107 jednoznaczno\u015b\u0107 zapisu. Przy wyliczaniu funkcji przystosowania odleg\u0142o\u015b\u0107 z miasta 6 do miasta 1 jest oczywi\u015bcie brana pod uwag\u0119. Przyjmujemy „niejawnie” \u017ce zawsze wracamy z miasta odwiedzanego jako ostatnie do miasta odwiedzanego jako pierwsze. <\/p>\n\n\n\n

Pierwszy etap algorytmu genetycznego – selekcja<\/h3>\n\n\n\n

Wg teorii ewolucji jedynie najsilniejsi osobnicy mog\u0105 przekaza\u0107 swoj\u0105 informacj\u0119 genetyczn\u0105 potomstwu. Algorytmy genetyczne symuluj\u0105 to zachowanie. Pierwszym etapem dzia\u0142ania takiego algorytmu jest selekcja. <\/strong>Na tym etapie wybieramy, kt\u00f3re osobniki dost\u0105pi\u0105 zaszczytu przekazania swoich gen\u00f3w potomstwu. Istnieje wiele metod selekcji, pocz\u0105wszy od najprostszej mo\u017cliwo\u015bci, gdzie po prostu wybieramy losowo x osobnik\u00f3w, przez bardziej skomplikowane jak metoda ruletki, a\u017c po inne o wiele bardziej rozbudowane metody.<\/p>\n\n\n\n

Selekcja turniejowa (tournament selection) – jeden z rodzaj\u00f3w selekcji<\/h4>\n\n\n\n

Wyr\u00f3\u017cni\u0142em ten konkretny rodzaj selekcji, gdy\u017c b\u0119dziemy go u\u017cywali w przyk\u0142adowej implementacji. Na czym polega selekcja turniejowa?<\/p>\n\n\n\n

W selekcji „turniejowej” uruchamiamy szereg „pojedynk\u00f3w” pomi\u0119dzy kandydatami do kolejnego etapu. Z ka\u017cdego z pojedynk\u00f3w wybieramy „zwyci\u0119zc\u0119” i umieszczamy go w populacji ko\u0144cowej. Jedynie najlepiej „przystosowani” osobnicy przetrwaj\u0105. Dzia\u0142anie selekcji mo\u017ce by\u0107 regulowane przez kilka parametr\u00f3w. S\u0105 to przede wszystkim rozmiar turnieju (ile osobnik\u00f3w we\u017amie udzia\u0142 w turnieju) oraz tzw „presja wyboru”. Presja wyboru jest parametrem, kt\u00f3ry okre\u015bla prawdopodobie\u0144stwo tego, \u017ce dany osobnik we\u017amie udzia\u0142 w danym turnieju. Je\u015bli osobnik jest s\u0142aby, istnieje szansa \u017ce do turnieju nawet nie przyst\u0105pi, gdy\u017c i tak przegra\u0142by z mocniejszymi kandydatami. <\/p>\n\n\n\n

Uruchamiaj\u0105c kolejne turnieje, budujemy populacj\u0119 rodzic\u00f3w, kt\u00f3rzy zostan\u0105 u\u017cyci w kolejnym etapie dzia\u0142ania algorytmu. <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Na powy\u017cszym rysunku znajduje si\u0119 nasza populacja. Ka\u017cdy osobnik po kropce ma wypisan\u0105 warto\u015b\u0107 funkcji przystosowania. Wybierzmy „losowo” czterech osobnik\u00f3w do pierwszego pojedynku.<\/p>\n\n\n\n

Pierwszy pojedynek: H.835, G.735, A.681, B.706<\/strong>. Kt\u00f3ra z tych warto\u015bci jest najwi\u0119ksza? 835. A wi\u0119c pierwszym z rodzic\u00f3w zakwalifikowanym do etapu krzy\u017cowania b\u0119dzie rodzic H<\/strong><\/p>\n\n\n\n

Drugi pojedynek: A. 681, G. 751, F.706, C. 706<\/strong>. Najwi\u0119ksz\u0105 warto\u015bci\u0105 jest 751, a wi\u0119c drugim rodzicem zostanie osobnik G.<\/strong> <\/p>\n\n\n\n

Drugi etap algorytmu genetycznego – krzy\u017cowanie<\/h3>\n\n\n\n

Gdy ju\u017c dobierzemy osobniki, kt\u00f3re b\u0119d\u0105 mog\u0142y si\u0119 „rozmno\u017cy\u0107”, b\u0119dziemy mogli przeprowadzi\u0107 operacj\u0119 krzy\u017cowania. <\/strong>Czym ona jest? Najpro\u015bciej rzecz ujmuj\u0105c – bierzemy cz\u0119\u015b\u0107 „genomu” od pierwszego rodzica i inn\u0105 cz\u0119\u015b\u0107 od drugiego rodzica, a nast\u0119pnie \u0142\u0105czymy. Dla ka\u017cdego nowego dziecka liczymy warto\u015b\u0107 funkcji przystosowania. Z wszystkich potomk\u00f3w, kt\u00f3rych uzyskamy na drodze krzy\u017cowania tworzymy now\u0105 populacj\u0119. <\/p>\n\n\n\n

Krzy\u017cowanie PMX <\/h4>\n\n\n\n

W naszym algorytmie genetycznym u\u017cyjemy krzy\u017cowania PMX. Na czym ono polega? Jest to „troszk\u0119” skomplikowany algorytm, wi\u0119c niezb\u0119dne b\u0119d\u0105 rysunki. <\/p>\n\n\n\n

Na pocz\u0105tku, jak w ka\u017cdym krzy\u017cowaniu, mamy dw\u00f3ch rodzic\u00f3w, kt\u00f3rzy posiadaj\u0105 pewny genom. (To s\u0105 nasi rodzice wybrani w etapie selekcji. Ich genom zosta\u0142 przepisany z tabelki wyznaczonej na etapie generowania populacji)<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Nast\u0119pnie losujemy dwa punkty – pocz\u0105tkowy i ko\u0144cowy, w kt\u00f3rych genom zostanie „poci\u0119ty”. Za\u0142\u00f3\u017cmy, \u017ce wytniemy fragment od trzeciego (w\u0142\u0105cznie) do pi\u0105tego (w\u0142\u0105cznie) elementu genomu. Oznaczmy wycinane fragmenty czerwon\u0105 ramk\u0105. <\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Zamieniamy ze sob\u0105 wyci\u0119te cz\u0119\u015bci. Ta znajduj\u0105ca si\u0119 w rodzicu pierwszym (4,2,1) trafia do rodzica drugiego. Natomiast ta z rodzica drugiego trafia do pierwszego. <\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Zauwa\u017cy\u0142e\u015b, \u017ce powsta\u0142 pewien problem? W rodzicu pierwszym dwa razy wyst\u0119puje miasto nr 3. Natomiast w rodzicu nr 2 wyst\u0119puje podobna sytuacja z miastem nr 1. Jak zaradzi\u0107 temu problemowi? Pomo\u017ce nam w tym „mapowanie”, kt\u00f3re zaraz utworzymy. <\/p>\n\n\n\n

Zapiszmy sobie, jakie miasta przechodz\u0105 w jakie w zamienionych fragmentach:
3->4
2->2
4->1
Mapowanie 2->2 jest ca\u0142kowicie nieistotne. Zauwa\u017cmy, \u017ce mapowania 3->4 i 4->1 s\u0105 „przechodnie”. To znaczy: skoro tr\u00f3jka w pierwszym rodzicu przechodzi w czw\u00f3rk\u0119 z drugiego, a czw\u00f3rka w pierwszym przechodzi w jedynk\u0119. to mo\u017cna powiedzie\u0107 \u017ce tr\u00f3jka od razu mo\u017ce przej\u015b\u0107 w jedynk\u0119. Mapowanie takie w ostatecznej postaci b\u0119dzie wygl\u0105da\u0142o nast\u0119puj\u0105co:
3->4->1 (tr\u00f3jka z pierwszego przechodzi w czw\u00f3rk\u0119 z drugiego rodzica. Natomiast ta czw\u00f3rka znajduj\u0105cy si\u0119 w pierwszym rodzicu przechodzi w jedynk\u0119 z drugiego). Efekt: tr\u00f3jka zmieni si\u0119 w jedynk\u0119. <\/p>\n\n\n\n

Co musimy zrobi\u0107? Wykona\u0107 dodatkow\u0105 zamian\u0119 kt\u00f3r\u0105 ustalili\u015bmy dzi\u0119ki temu mapowaniu!<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Otrzymali\u015bmy dw\u00f3ch potomk\u00f3w. Obliczamy warto\u015b\u0107 funkcji przystosowania dla ka\u017cdego z nich.<\/p>\n\n\n\n

Potomek 1: 1331 km -> 1\/1331*1 000 000 = 751
Potomek 2: 1112 km -> 1\/1112*1 000 000 = 899<\/p>\n\n\n\n

Lepszy jest potomek 2, wi\u0119c to on przejdzie do nast\u0119pnego etapu. Zauwa\u017c, \u017ce potomek ten jest lepszy tak\u017ce od ka\u017cdego z dwojga swoich rodzic\u00f3w.<\/p>\n\n\n\n

Poni\u017cszy filmik dobrze obrazuje spos\u00f3b dzia\u0142ania krzy\u017cowania PMX.<\/p>\n\n\n\n

\n