{"id":2390,"date":"2020-08-26T15:12:42","date_gmt":"2020-08-26T13:12:42","guid":{"rendered":"https:\/\/www.kompikownia.pl\/?p=2390"},"modified":"2020-08-26T15:13:08","modified_gmt":"2020-08-26T13:13:08","slug":"jak-rozwiazac-problem-komiwojazera-implementacja-algorytmu-genetycznego","status":"publish","type":"post","link":"https:\/\/www.kompikownia.pl\/index.php\/2020\/08\/26\/jak-rozwiazac-problem-komiwojazera-implementacja-algorytmu-genetycznego\/","title":{"rendered":"Jak rozwi\u0105za\u0107 problem komiwoja\u017cera? Implementacja algorytmu genetycznego"},"content":{"rendered":"<span class=\"rt-reading-time\" style=\"display: block;\"><span class=\"rt-label rt-prefix\">Czas czytania:<\/span> <span class=\"rt-time\">4<\/span> <span class=\"rt-label rt-postfix\">minut<\/span><\/span>\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.kompikownia.pl\/index.php\/2020\/07\/29\/problem-komiwojazera-rozwiazywany-algorytmem-genetycznym\/\" target=\"_blank\">W poprzednim artykule om\u00f3wili\u015bmy<\/a>, jak powinien dzia\u0142a\u0107 algorytm genetyczny rozwi\u0105zuj\u0105cy problem komiwoja\u017cera. Skoro posiadamy podstawy teoretyczne, pora zabra\u0107 si\u0119 za praktyk\u0119. Spr\u00f3bujemy zaimplementowa\u0107 rozwi\u0105zanie problemu komiwoja\u017cera za pomoc\u0105 algorytmu genetycznego w j\u0119zyku TypeScript z u\u017cyciem frameworka Angular. Do dzie\u0142a!<br>Je\u015bli chcesz przetestowa\u0107 aplikacj\u0119, kt\u00f3ra zosta\u0142a tu om\u00f3wiona,<a href=\"http:\/\/komiwojazer.kompikownia.pl\" target=\"_blank\" rel=\"noreferrer noopener\"> wejd\u017a pod ten adres.<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Definicja podstawowych klas<\/h2>\n\n\n\n<p><strong>Osobnik &#8211; <\/strong>b\u0119dzie to jedna z mo\u017cliwych tras, odwiedzaj\u0105cych wszystkie miasta. Po\u0142\u0105czenia pomi\u0119dzy poszczeg\u00f3lnymi miastami w trasie b\u0119d\u0105 zarazem jego genomem. Np.: takim osobnikiem (i jego genomem) mo\u017ce by\u0107 trasa Ostrowiec-&gt;Krak\u00f3w-&gt;Kielce-&gt;Warszawa.<\/p>\n\n\n\n<p>Aby zdefiniowa\u0107 osobnika, potrzebujemy <strong>miast <\/strong>i <strong>tras.<\/strong><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Miasto<\/h3>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/94125b6b2fe8d91300a0f59d633c717a.js\"><\/script>\n\n\n\n<p class=\"example_code\">Nasza klasa &#8222;Miasto&#8221; jest bardzo prosta. Definiujemy sobie w niej tylko metod\u0119 pomocnicz\u0105 <em>getDistance<\/em> kt\u00f3ra pozwala nam obliczy\u0107 w prosty spos\u00f3b odleg\u0142o\u015b\u0107 do innego miasta. Korzystamy w tym miejscu ze wzoru Pitagorasa, kt\u00f3ry pewnie wszyscy doskonale znacie \ud83d\ude42 Zdefiniowane atrybuty to pozycja miasta (x, y) oraz jego identyfikator (id). Identyfikatorem nie zaprz\u0105taj sobie g\u0142owy &#8211; nie b\u0119dzie nam potrzebny w rozwi\u0105zywaniu tego problemu \ud83d\ude42 <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Trasa<\/h3>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/7b540771ba365fb6b668938268240290.js\"><\/script>\n\n\n\n<p class=\"example_code\">Powy\u017cej znajduje si\u0119 definicja klasy <strong>Tour, <\/strong>kt\u00f3ra reprezentuje nasz\u0105 tras\u0119, przechodz\u0105c\u0105 przez wszystkie miasta. W linijce drugiej definiujemy sobie tablic\u0119 miast, kt\u00f3re b\u0119dziemy odwiedzali.Linijka 4 to getter pozwalaj\u0105cy pobra\u0107 d\u0142ugo\u015b\u0107 ca\u0142ej trasy. B\u0119dziemy u\u017cywali tej metody do obliczenia funkcji przystosowania.<\/p>\n\n\n\n<p>Funkcj\u0119 przystosowania liczymy w <em>linijce 19. <\/em>Jak widzisz, m\u00f3j drogi czytelniku, nie jest to nic skomplikowanego. Po prostu dzielimy 1 przez d\u0142ugo\u015b\u0107 ca\u0142ej trasy. Zwykle b\u0119dzie to bardzo ma\u0142a liczba, ale najwa\u017cniejsze aby ros\u0142a wraz z popraw\u0105 jako\u015bci trasy.<\/p>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/32c0f21e6ff429f9283b57d0ed06da77.js\"><\/script>\n\n\n\n<p class=\"example_code\">Powy\u017cej znajduje si\u0119 kolejny zbi\u00f3r metod pomocniczych znajduj\u0105cych si\u0119 w klasie <em>Tour.<\/em> <em>setCity <\/em>pozwala nam podmieni\u0107&nbsp;miasto znajduj\u0105ce si\u0119 na konkretnej pozycji w trasie na inne. Metoda <em>shuffle<\/em> pozwala na wymieszanie miast znajduj\u0105cych si\u0119 w trasie. Wykorzystywana jest ona do generowania nowych tras w metodzie <em>generate.<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Populacja<\/h3>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/cb508f8c1b131cb016bea365c9b06f2a.js\"><\/script>\n\n\n\n<p>Mamy ju\u017c zdefiniowane miasta i trasy. Mo\u017cemy wi\u0119c zaj\u0105\u0107 si\u0119 populacj\u0105!<\/p>\n\n\n\n<p class=\"example_code\">Podobnie jak trasa posiada list\u0119 miast, tak populacja posiada list\u0119 tras zdefiniowan\u0105 w linijce 2. Dalej mamy standardowe gettery. W konstruktorze tworzymy populacj\u0119 z\u0142o\u017con\u0105 z okre\u015blonej ilo\u015bci tras. Metoda <em>init<\/em> generuje t\u0119 populacj\u0119. Metoda <em>saveTour <\/em>natomiast pozwala podmieni\u0107 tras\u0119 w populacji na inn\u0105. Za pomoc\u0105&nbsp;metody <em>getFittiest <\/em>mo\u017cemy wybra\u0107 tras\u0119 (czyli osobnika) kt\u00f3ry jest najlepiej przystosowany w danej populacji.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Algorytm genetyczny<\/h2>\n\n\n\n<p>Om\u00f3wili\u015bmy ju\u017c wszystkie klasy pomocnicze. Pora zaj\u0105\u0107 si\u0119 wisienk\u0105 na torcie, czyli implementacj\u0105 samego algorytmu genetycznego :). Ze wzgl\u0119du na wielko\u015b\u0107 tej klasy, b\u0119dziemy j\u0105 omawiali fragmentami.<\/p>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/d1f29080eb8327d98901ba5d2a7d6597.js\"><\/script>\n\n\n\n<p class=\"example_code\">Na pocz\u0105tku powy\u017cszego listingu, jak zwykle, mamy zadeklarowane prywatne atrybuty klasy. <em> _mutationRate <\/em>jest to domy\u015blne prawdopodobie\u0144stwo zaj\u015bcia mutacji (0,015*100%=1.5%). <em> _tournamentSize <\/em>jest to ilo\u015b\u0107&nbsp;tras, jak\u0105 b\u0119dziemy poddawali &#8222;turniejowi&#8221;. (Je\u015bli nie pami\u0119tasz, o co chodzi, przypomnij sobie <a rel=\"noreferrer noopener\" href=\"https:\/\/www.kompikownia.pl\/index.php\/2020\/07\/29\/problem-komiwojazera-rozwiazywany-algorytmem-genetycznym\/\" target=\"_blank\">poprzedni artyku\u0142<\/a>, w kt\u00f3rym omawiali\u015bmy selekcj\u0119 turniejow\u0105.<\/p>\n\n\n\n<p class=\"example_code\">Gwoli wyja\u015bnienia wymaga zmienna <em>selectedStrategy <\/em>typu <em>CrossoverStrategy. <\/em>C\u00f3\u017c to takiego jest? Ot\u00f3\u017c, jak doskonale wiemy, istnieje wiele r\u00f3\u017cnych sposob\u00f3w przeprowadzania krzy\u017cowania. Wobec tego, wykorzystali\u015bmy w tym miejscu wzorzec projektowy <em>Strategia.<\/em>Zastosowanie wzorca pozwala nam w prosty spos\u00f3b rozszerzy\u0107&nbsp;aplikacj\u0119 o inne algorytmy krzy\u017cowania. W konstruktorze do wspieranych strategii dodajemy strategi\u0119 <em>PMX. <\/em>Aby doda\u0107 wsparcie nowej strategii, wystarczy stworzy\u0107 klas\u0119 rozszerzaj\u0105c\u0105 <em>CrossoverStrategy<\/em> i stworzy\u0107 obiekt tej klasy w konstruktorze <em>Genetic. <\/em><\/p>\n\n\n\n<p class=\"example_code\">Nast\u0119pnie mamy metod\u0119 <em>evolvePopulation<\/em>, kt\u00f3ra jako argumenty przyjmuje: populacj\u0119, wielko\u015b\u0107 pojedynczego turnieju oraz wsp\u00f3\u0142czynnik mutacji. Warto\u015bci tych zmiennych s\u0105 przypisywane do prywatnych atrybut\u00f3w. Nast\u0119pnie tworzona jest nowa, pusta populacja. <\/p>\n\n\n\n<p>P\u0119tla for w linijce <em>17 <\/em>przechodzi po wszystkich elementach populacji i wykonuje selekcj\u0119 oraz krzy\u017cowanie. Po krzy\u017cowaniu wykonywana jest mutacja. <\/p>\n\n\n\n<p>Metoda zwraca now\u0105 lepsz\u0105 ewolucyjnie populacj\u0119. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Selekcja i krzy\u017cowanie<\/h3>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/e251f768e258ca7439317dff68c45423.js\"><\/script>\n\n\n\n<p class=\"example_code\">Metoda <em>performSelectionAndCrossover <\/em>przyjmuje trzy argumenty: populacja, nowa populacja oraz index potomka, kt\u00f3rego aktualnie przetwarzamy. <\/p>\n\n\n\n<p class=\"example_code\">Najpierw tworzymy rodzic\u00f3w. Przeprowadzamy dwa razy selekcj\u0119 turniejow\u0105 aby wyznaczy\u0107 ka\u017cdego z rodzic\u00f3w. <\/p>\n\n\n\n<p class=\"example_code\">W kolejnym kroku wykonujemy krzy\u017cowanie. S\u0142u\u017c\u0105 do tego dwie metody pochodz\u0105ce od om\u00f3wionej wcze\u015bniej zmiennej <em>selectedStrategy.<\/em><br><em>prepareStrategyData<\/em> &#8211; przygotowuje wszystkie dane, kt\u00f3re s\u0105 potrzebne do wykonania krzy\u017cowania potomk\u00f3w. W przypadku strategii PMX jest to wylosowanie fragmentu genomu, kt\u00f3ry zostanie wyci\u0119ty.<br><em>generateTourFromParents<\/em> &#8211; wykonuje w\u0142a\u015bciwe krzy\u017cowanie.<\/p>\n\n\n\n<p>Na samym ko\u0144cu lepszy potomek staje si\u0119 cz\u0119\u015bci\u0105 nowej populacji. Gorszy niestety musi zosta\u0107 unicestwiony &#8230; <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Selekcja turniejowa<\/h4>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/7e6a1a6b52072c2f446b7682a6b71ed7.js\"><\/script>\n\n\n\n<p>Zastosowany algorytm selekcji turniejowej jest niezwykle prosty. Najpierw tworzymy now\u0105 populacj\u0119 o rozmiarze turnieju. Nast\u0119pnie losujemy osobnik\u00f3w, kt\u00f3rzy wezm\u0105 udzia\u0142 w turnieju. Jako wynik selekcji zwracamy najlepszego osobnika tej populacji. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Krzy\u017cowanie PMX<\/h4>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/dca54f7dab9aa716c720ca73992b5a9d.js\"><\/script>\n\n\n\n<p>Pora zaj\u0105\u0107 si\u0119 jedn\u0105 z najwa\u017cniejszych cz\u0119\u015bci algorytmu genetycznego, czyli krzy\u017cowaniem :). <\/p>\n\n\n\n<p class=\"example_code\">Atrybuty klasy <em>x1<\/em> i <em>x2<\/em> to punkty: pocz\u0105tkowy i ko\u0144cowy w ramach kt\u00f3rych b\u0119dziemy &#8222;wycinali&#8221; genom. <\/p>\n\n\n\n<p class=\"example_code\">W metodzie <em>prepareStrategyData <\/em>dokonujemy wyboru tych punkt\u00f3w.<\/p>\n\n\n\n<p class=\"example_code\">Kolejn\u0105 metod\u0105 kt\u00f3r\u0105 om\u00f3wimy jest <em>generateTourFromParents.<\/em> Przyjmuje ona jako argument osobnik\u00f3w, kt\u00f3rzy stan\u0105 si\u0119 rodzicami dla nowych potomk\u00f3w. Wewn\u0105trz tej metody uruchamiamy metod\u0119 <em>performCrossoverForChildren<\/em>. Generujemy dw\u00f3ch potomk\u00f3w.<\/p>\n\n\n\n<p class=\"example_code\"><em>performCrossoverForChildren <\/em>zawiera praktycznie ca\u0142\u0105 logik\u0119 algorytmu PMX. Najpierw tworzymy sobie kopi\u0119 tablicy z rodzica pierwszego, za pomoc\u0105 <em>Array.from<\/em>. Nast\u0119pnie wykonujemy pierwsz\u0105 cz\u0119\u015b\u0107 algorytmu krzy\u017cowania PMX, czyli kopiujemy fragment znajduj\u0105cy si\u0119 pomi\u0119dzy wylosowanymi wcze\u015bniej punktami x1 i x2 z jednego rodzica do drugiego. Jednocze\u015bnie uzupe\u0142niamy sobie tablic\u0119 <em>mappingForChildren<\/em>, w kt\u00f3rej zapiszemy jakie elementy przesz\u0142y w jakie podczas zamiany. <\/p>\n\n\n\n<p><strong>Pojawia si\u0119 problem:<\/strong><br>Rozwa\u017cmy nast\u0119puj\u0105ce genomy: <\/p>\n\n\n\n<p>Rodzic 1: * * * 4 6 5 * * *<br>Rodzic 2: * * * 6 5 4 * * *<\/p>\n\n\n\n<p>Zostan\u0105 utworzone nast\u0119puj\u0105ce mapowania: (dla dziecka nr 1. Dla dziecka nr 2 b\u0119d\u0105 one analogiczne, tyle&nbsp;\u017ce odwrotne)<br>4-&gt;6<br>6-&gt;5<br>5-&gt;4<\/p>\n\n\n\n<p class=\"example_code\">Zauwa\u017cy\u0142e\u015b pewn\u0105 ciekaw\u0105 rzecz? Wykonuj\u0105c zamiany wg tych mapowa\u0144, dokonujemy odkrycia dw\u00f3ch bardzo nieciekawych zale\u017cno\u015bci:<br>a) <strong>zale\u017cno\u015b\u0107 przechodnia &#8211; <\/strong>skoro czw\u00f3rka przechodzi w sz\u00f3stk\u0119 i sz\u00f3stka w pi\u0105tk\u0119, a pi\u0105tka w czw\u00f3rk\u0119 to czw\u00f3rka przechodzi w czw\u00f3rk\u0119. <br>b) <strong>cykl &#8211; <\/strong>wynikaj\u0105cy z tej zale\u017cno\u015bci -&gt; czw\u00f3rka przechodzi w czw\u00f3rk\u0119.<br>Obydwie zale\u017cno\u015bci s\u0105 niedopuszczalne. Dlaczego? Poniewa\u017c doprowadz\u0105 one do &#8222;zakleszczenia si\u0119&#8221; naszego algorytmu. (sp\u00f3jrz na p\u0119tle while w linijkach 48\/54) W\u0142a\u015bnie dlatego u\u017cywamy dw\u00f3ch metod pomocniczych: <em>eliminateTransitives <\/em>&#8211; kt\u00f3ra eliminuje zale\u017cno\u015bci tranzytywne ( oraz <em>eliminateCycles<\/em> &#8211; kt\u00f3ra eliminuje cykle z mapowa\u0144.<\/p>\n\n\n\n<p>Po wyeliminowaniu wszystkich niepo\u017c\u0105danych cech mapowania mo\u017cemy go u\u017cy\u0107. S\u0142u\u017c\u0105 do tego dwie kolejne p\u0119tle for. Znajduj\u0105ca si\u0119 w nich p\u0119tla while szuka takich element\u00f3w w dziecku, kt\u00f3re znajduj\u0105 si\u0119 w mapowaniu. Nast\u0119pnie dokonywana jest wymiana. Wymian dokonujemy dop\u00f3ty, dop\u00f3ki w dziecku znajduj\u0105 si\u0119 takie elementy, kt\u00f3re podlegaj\u0105 wymianie.<\/p>\n\n\n\n<p>Algorytmem s\u0142u\u017c\u0105cym do eliminacji cykli oraz zale\u017cno\u015bci przechodnich zajmiemy si\u0119 w innym artykule. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Mutacja<\/h3>\n\n\n\n<script src=\"https:\/\/gist.github.com\/karol221-10\/90355c8e30d32139887e9a05c57dab6e.js\"><\/script>\n\n\n\n<p>Mutacja w niniejszym algorytmie jest bardzo prostym operatorem. Jako argument przyjmujemy tras\u0119. dla ka\u017cdego elementu tej trasy losujemy liczb\u0119 (z zakresu od 0 do 1) i sprawdzamy czy jest ona mniejsza ni\u017c wsp\u00f3\u0142czynnik mutacji. Jesli tak &#8211; losowo dokonujemy zamiany dw\u00f3ch element\u00f3w trasy ze sob\u0105 (dok\u0142adny opis algorytmu znajduje si\u0119<a href=\"https:\/\/www.kompikownia.pl\/index.php\/2020\/07\/29\/problem-komiwojazera-rozwiazywany-algorytmem-genetycznym\/\"> w artykule wprowadzaj\u0105cym do tego tematu<\/a>).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Stworzyli\u015bmy pierwszy dzia\u0142aj\u0105cy algorytm genetyczny!<\/h2>\n\n\n\n<p>Sukces \ud83d\ude42 Stworzyli\u015bmy algorytm genetyczny, kt\u00f3ry z du\u017c\u0105 doz\u0105 prawdopodobie\u0144stwa wyznaczy w miar\u0119 optymaln\u0105 tras\u0119 rozwi\u0105zuj\u0105c\u0105 problem komiwoja\u017cera. Kompletna aplikacja dost\u0119pna jest na <a href=\"https:\/\/github.com\/karol221-10\/GeneticSalesmanProblem\">Githubie<\/a>. (Wersja om\u00f3wiona w tym artykule znajduje si\u0119 na branchu <em>artykul_1. <\/em>Na branchu master mo\u017ce znajdowa\u0107 si\u0119 nieco odmienna wersja). <\/p>\n\n\n\n<p>Przypominam, \u017ce mo\u017cesz przetestowa\u0107 om\u00f3wiony powy\u017cej program bez instalowania kompletnego \u015brodowiska. <a href=\"http:\/\/komiwojazer.kompikownia.pl\/\" target=\"_blank\" rel=\"noreferrer noopener\">Jest on dost\u0119pny pod tym adresem.<\/a><\/p>\n\n\n\n<p>Masz jakie\u015b pytania, w\u0105tpliwo\u015bci? Mo\u017ce pope\u0142ni\u0142em gdzie\u015b b\u0142\u0105d? \u015amia\u0142o &#8211; napisz komentarz \ud83d\ude42<\/p>\n\n\n\n<p>Pozdrawiam i do nast\u0119pnego razu \ud83d\ude42 <\/p>\n","protected":false},"excerpt":{"rendered":"<p><span class=\"rt-reading-time\" style=\"display: block;\"><span class=\"rt-label rt-prefix\">Czas czytania:<\/span> <span class=\"rt-time\">4<\/span> <span class=\"rt-label rt-postfix\">minut<\/span><\/span> W poprzednim artykule om\u00f3wili\u015bmy, jak powinien dzia\u0142a\u0107 algorytm genetyczny rozwi\u0105zuj\u0105cy problem komiwoja\u017cera. Skoro posiadamy podstawy teoretyczne, pora zabra\u0107 si\u0119 za praktyk\u0119. Spr\u00f3bujemy zaimplementowa\u0107 rozwi\u0105zanie problemu komiwoja\u017cera za pomoc\u0105 algorytmu genetycznego &#8230;<\/p>\n","protected":false},"author":1,"featured_media":2471,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[25],"tags":[96,97,95,79,100,103,99,101,78],"_links":{"self":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts\/2390"}],"collection":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/comments?post=2390"}],"version-history":[{"count":36,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts\/2390\/revisions"}],"predecessor-version":[{"id":2472,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts\/2390\/revisions\/2472"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/media\/2471"}],"wp:attachment":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/media?parent=2390"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/categories?post=2390"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/tags?post=2390"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}