fbpx

Mateusz Mazurek – programista z pasją

Czyli o użyciu Pythona i kilku innych technologii do tworzenia świetnej jakości aplikacji w oparciu o stabilny proces dostarczania oprogramowania.

Algorytmika Programowanie

Algorytmy genetyczne w Pythonie – ciąg dalszy

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.

Problem komiwojażera

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.

Z perspektywy matematyka

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.

obrazek
Przykładowy graf (bez wag) dla 10 miast.

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.

Rozwiązanie naiwne

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?

Rozwiązania przybliżone

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!

Kod

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.

Rezultat

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

Wizualizacja

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ń:

Github

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.

Dzięki za wizytę,
Mateusz Mazurek

A może wolisz nowości na mail?

2
Dodaj komentarz

avatar
2 Wątki
0 Odpowiedzi
2 Śledzący
 
Komentarz z największą liczbą reakcji
Najczęściej komentowany wątek
1 Komentarze autora
Mateusz Rus Ostatnie komentarze autora

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subskrybuj  
Powiadom o
trackback

[…] Ciąg dalszy nastąpił, zapraszam – https://mmazurek.dev/algorytmy-genetyczne-w-pythonie-ciag-dalszy/ […]

Mateusz Rus
Gość

Jak zwykle bardzo ciekawy wpis. Problem komiwojażera to jedno z ciekawszych zagadnień w świecie IT.

Pozdrawiam, Mateusz.

Jeśli podoba Ci się to co tworzę, polub mój fanpage :)