W jednym z ostatnich wpisów omówiliśmy, czym jest algorytm genetyczny, z czego się składa i na czym polega jego działanie. Napisaliśmy również mini framework, ułatwiający pracę z tym rozwiązaniem, aby na końcu, w oparciu o nasz poprzedni kod, stworzyć przykład, który pozwala przekształcić losowy ciąg znaków w zadany tekst. Zrobiliśmy tam naprawdę dużo! Jeśli nie czytałeś poprzedniego wpisu, zachęcam do nadrobienia zaległości, link załączam tutaj.
Przykład, który pokazałem w poprzednim artykule, chociaż ciekawy, to nie rozwiązuje żadnego konkretnego problemu. Zatem, aby AI nie było tutaj tylko buzzwordem, dziś zajmiemy się konkretnym zadaniem.
Zajmiemy się problemem, z którym na co dzień borykają się chociażby firmy kurierskie. W szczególności teraz, pod koniec roku, kiedy wszyscy zamawiamy prezenty. Ilość paczek, które trzeba dostarczyć jest ogromna i żeby dokonać tego w rozsądnym czasie, trzeba zaplanować trasę, którą kurier ma jechać.
I to właśnie problem wyznaczenia optymalnej trasy jest nazywany problemem komiwojażera.
Problem ten z perspektywy matematyki to problem z dziedziny grafów. Zbudować należy graf ważony, którego wierzchołki są miastami. Najpierw każdą parę miast łączymy krawędziami. Następnie każdej krawędzi nadajemy wagę równą odległości miedzy odpowiednimi miastami.
Istnieją dwie odmiany tego problemu. Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne. My rozważamy pierwszą odmianę.
Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków, ile miast musi odwiedzić komiwojażer (wliczając w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, który przechodzi przez każdy wierzchołek danego grafu dokładnie raz. Cykl taki nazywamy cyklem Hamiltona. Poszukujemy wiec w grafie pełnym cyklu Hamiltona o minimalnej sumie wag krawędzi.
Pierwsze rozwiązanie, które przychodzi na myśl, to oczywiście wyznaczyć wszystkie możliwe drogi, obliczyć ich długości i wybrać najkrótszą.
Głównym problemem tego rozwiązania jest ilość danych, które trzeba przetworzyć. Zakładając, że rozważamy symetryczną odmianę tego problemu, ilość możliwych kombinacji wynosi
co dla zaledwie 20 miast (lub po prostu konkretnych punktów na mapie) daje
możliwych kombinacji. Sporo! Komputer może się nieźle napocić. A co, jeśli punktów do przejechania mamy sto?
Jak już pewnie zauważyliście, okazuje się, że rozwiązanie tego problemu nie jest trywialne. W związku z tym akceptowalne są rozwiązania przybliżone, czyli po prostu bliskie najlepszemu, ale nie najlepsze. Akceptując niedoskonałość, potrafimy rozwiązać ten problem właśnie z użyciem algorytmów genetycznych!
Napiszmy więc kawałek kodu, dzięki któremu rozwiążemy problem komiwojażera. Użyjemy do tego naszego mini AI framework’a, czyli zaimplementujmy klasę Element:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | from genetic_library import GeneticAlgorithm, Element from genetic_library.selection_models import elite_selection_model from random import randint, sample from math import sqrt START_POINT = [(1, 1)] END_POINT = [(1, 1)] # POINTS = [(randint(0, 40), randint(0, 40)) for k in range(50)] POINTS = [(3, 4), (11, 5), (27, 23), (27, 25), (22, 32), (24, 34), (19, 38), (17, 37), (7, 40), (8, 36), (8, 28), (16, 21), (14, 17), (25, 11), (24, 19), (32, 26), (29, 34), (27, 34), (38, 36), (35, 12), (33, 8), (31, 2), (24, 5), (23, 3), (17, 3), (16, 3), (24, 11), (21, 21), (23, 21), (17, 10), (19, 7), (33, 14), (38, 18), (34, 19), (20, 30), (9, 38), (6, 27), (7, 12), (3, 15), (0, 24), (5, 30), (3, 33), (4, 33), (6, 28), (7, 6), (4, 4), (2, 10), (2, 23), (8, 20)] class Route(Element): def __init__(self, points): self.points = points super().__init__() def _perform_mutation(self): first = randint(1, len(self.points) - 2) second = randint(1, len(self.points) - 2) self.points[first], self.points[second] = self.points[second], self.points[first] def crossover(self, element2: 'Element') -> 'Element': child_points = self.points[1:int(len(self.points) / 2)] for point in element2.points: if point not in child_points and point not in END_POINT + START_POINT: child_points.append(point) if len(child_points) == len(element2.points): break return Route(START_POINT + child_points + END_POINT) def evaluate_function(self): def _calculate_distance(x1, x2, y1, y2): return sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) sum = 0 for i, p in enumerate(self.points): if i + 1 > len(self.points) - 1: break next_point = self.points[i + 1] sum += _calculate_distance(p[0], next_point[0], p[1], next_point[1]) return sum def __repr__(self): return str(self.points) def first_generation_generator(): return [Route(START_POINT + sample(POINTS, len(POINTS)) + END_POINT) for _ in range(100)] def stop_condition(string, current_fitness, i): return i == 3000 ga = GeneticAlgorithm(first_generation_generator, elite_selection_model, stop_condition) ga.run() |
Zaczynając od samej góry, najpierw definiujemy punkt będący jednocześnie punktem początkowym jak i końcowym. Lista POINTS to po prostu koordynaty naszych miast do odwiedzenia. Zajmijmy się opisanymi w poprzednim artykule metodami, zaczynając od mutacji:
1 2 3 4 5 | def _perform_mutation(self): first = randint(1, len(self.points) - 2) second = randint(1, len(self.points) - 2) self.points[first], self.points[second] = self.points[second], self.points[first] |
Jej działanie to po prostu zamiana miejscami dwóch różnych punktów na trasie. Krzyżowanie się osobników wygląda tak:
1 2 3 4 5 6 7 8 9 | def crossover(self, element2: 'Element') -> 'Element': child_points = self.points[1:int(len(self.points) / 2)] for point in element2.points: if point not in child_points and point not in END_POINT + START_POINT: child_points.append(point) if len(child_points) == len(element2.points): break return Route(START_POINT + child_points + END_POINT) |
Polega ono na wzięciu z pierwszego osobnika (czyli możliwej drogi) części punktów jego trasy (pomijając punkt początkowy) i dobieraniu w pętli kolejnych punktów z drugiego osobnika (czyli innej możliwej drogi) tak, by się one nie powtarzały. Osiągnięcie tego celu kończy pętlę i zwraca nowego osobnika (drogę), w tym przypadku klasę Route. Dalej mamy funkcję oceny:
1 2 3 4 5 6 7 8 9 10 11 12 | def evaluate_function(self): def _calculate_distance(x1, x2, y1, y2): return sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) sum = 0 for i, p in enumerate(self.points): if i + 1 > len(self.points) - 1: break next_point = self.points[i + 1] sum += _calculate_distance(p[0], next_point[0], p[1], next_point[1]) return sum |
tutaj mamy prosto – liczymy odległość pomiędzy punktami
wg wzoru:
Innymi słowy – liczymy odległość od punktu startu do pierwszego punktu. Następnie odległość między drugim a trzecim punktem i tak dalej, aż do końca listy miast z rozważanego osobnika (drogi). Uzyskane wyniki sumujemy, czyli uzyskujemy długość konkretnej drogi.
Tak jak w poprzednim artykule tak i tu każde uruchomienie programu zakończy się innym wynikiem. Z kodu wynika, że ustawiłem limit 3000 pokoleń – i to wystarczy żeby średnio z 850 jednostek długości zoptymalizować trasę do średnio 360 jednostek. Wynik ten jest dla 51 miast. Przypomnę, że generuje to wg wzoru
około
kombinacji!! Jeśli ktoś nie jest zaznajomiony z matematycznym zapisem używającym potęgi liczby 10, czyli z notacją wykładniczą, to oto liczba kombinacji:
15207046600856689021806304083032384422188820784480256000000000000
Załączam niżej wizualizację jednego uruchomienia programu. Do kodu, który jest wyżej, dopisałem kawałek matplotlib’a, który umie takie fajne rzeczy robić!
Video pokazuje również output jaki generuje nasz framework. Filmik oczywiście jest przyśpieszony. Dla osób nie lubiących filmików załączam wynik innego uruchomienia, stan początkowy:
stan po 3500 pokoleń:
stan po 10000 pokoleń:
Na githubie, o którym wspomniałem w poprzednim artykule tj https://github.com/mmazurekdev/genetic-algorithm pojawiła się wersja kodu, który przygotowaliśmy w tym artykule – zarówno z generowaniem wizualizacji jak i bez.
Ostatnio tygodnie były tak bardzo wypełnione, że nie udało mi się napisać nawet krótkiego podsumowanie. Więc dziś zbiorczo podsumuję luty… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W styczniu przeczytałem "Homo Deus: Historia jutra". Książka łudząco podoba do wcześniejszej książki tego… Read More
Cześć! Zapraszam na podsumowanie roku 2023. Książki Zacznijmy od książek. W tym roku cel 35 książek nie został osiągnięty. Niemniej… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W grudniu skończyłem czytać Mein Kampf. Nudna książka. Ciekawsze fragmenty można by było streścić… Read More
Cześć, ostatnio w Internecie pojawiło się dużo artykułów, które nie były przychylne pracy zdalnej. Z drugiej strony większość komentarzy pod… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W listopadzie dokończyłem cykl "Z mgły zrodzony" Sandersona. Tylko "Stop prawa" mi nie do… Read More
Pokaż komentarze
Jak zwykle bardzo ciekawy wpis. Problem komiwojażera to jedno z ciekawszych zagadnień w świecie IT.
Pozdrawiam, Mateusz.