Metody i algorytmy sztucznej inteligencji

Program dydaktyczny:

Problem transportowy – algorytm genetyczny, symulowanego wyżarzania (porównanie)

Raport został opracowany na zaliczenie przedmiotu ze sztucznej inteligencji

Projekt wykonał: Jacek Szyszka

Prowadzący: dr inż. Witold Paluszyński

1.     Założenia

    Celem projektu jest stworzenie programu dydaktycznego wprowadzającego w problematykę zadań transportowych, oraz ich metody i algorytmy rozwiązywania. Końcowym efektem jest statystyczne porównanie uzyskanych wyników.

2.     Opis zadania

    Program jest dydaktyczna formą przedstawienia problemu transportowego rozwiązanego kilkoma algorytmami. Jest przeznaczona dla odbiorów mało zaznajomionych z tematem chcących lepiej poznać zagadnienie zarówno problemu transportowego jak i algorytmów heurystycznych. Program w prosty sposób za pomocą slajdów wprowadza użytkownika w cześć teoretyczna problemu. Może przeczytać o zagadnieniu, warunkach i wymaganiach stawianych przez problem. Następnie na kolejnym slajdzie użytkownik przechodzi do części praktycznej gdzie jest konkretne zadanie do rozwiązania. A mianowicie mamy pewnego właściciela firmy transportowej Jana Kowalskiego, który zwraca się do nas o pomoc w rozwiązaniu jego problemu. Ma do dyspozycji kilka ciężarówek i mnóstwo  klientów, których ma odwiedzić. Całe zagadnienie sprowadza się do rozwiązania problemu komiwojażera (TSP). Użytkownik ma pełna kontrole nad zadaniem. Może ustawić takie parametry jak ilość klientów do odwiedzenia oraz ich współrzędne na mapie, koszt paliwa, ilość ciężarówek, ilość litrów spalanych przez ciężarówkę, itp.  Poruszając się za pomocą myszki użytkownik programu ma możliwość dokonać wszelkich zmian, według własnego upodobania. Kiedy już sprecyzuje zadanie może przejść do rozwiązania problemu. Tutaj ma pełną swobodę wyboru algorytmu, oraz ich parametrów, może odpowiednio przyśpieszyć lub polepszyć działanie programu:

Do dyspozycji są algorytmy:

a)      Symulowane wyżarzanie

b)      Algorytm genetyczny

c)      Algorytm zachłanny (losowy)

Po wybraniu odpowiednich parametrów użytkownik może uruchomić algorytm, zobaczyć jego efekty działania, oraz wyznaczoną trasę. Na koniec użytkownik może na wykresie zobaczyć przebieg poszukiwań rozwiązania, ilość cykli, oraz  odczytać statystyki dla najlepszego rozwiązania. Daje to możliwość efektywnego porównania algorytmów, oraz ich wyników. Oczywiście istnieje możliwość powtórzenia działania algorytmu, uruchomienie innego algorytmu z innymi parametrami tak aby zobaczyć jak dane zmiany wpływają na końcowy wynik. Poruszając się wstecz i do przodu w slajdach można dowolnie zmieniać wszelkie wcześniej ustawione parametry.

3.     Metoda rozwiązania problemu

Do rozwiązania problemu zastosowano 3 algorytmy:

Algorytm symulowanego wyżarzania

Opis algorytmu pochodzi ze strony: http://kysy.rst.com.pl/projects.php

    Jedną z popularnych metod poszukiwania globalnego rozwiązania jest symulowane wyżarzanie. W 1983 roku naukowcy Scott Kirkpatrick, Charles Gelatt i Mario Vecchi zaproponowali algorytm, którego ideę obrazuje stosowana od wielu wieków przez kowali metoda wyżarzania metalu w procesie jego hartowania. W algorytmach przeszukiwania, w tym także symulowanego wyżarzania, zakłada się, że dla każdego elementu przestrzeni rozwiązań potrafimy wyznaczyć wartość funkcji oceniającej jakość rozwiązania. Zazwyczaj funkcja ta ma interpretację kosztową i jej wartość jest odwrotnie proporcjonalna do jakości rozwiązania. Szukamy, zatem takiego elementu przestrzeni rozwiązań, w którym funkcja kosztów jest minimalna. Algorytm symulowanego wyżarzania działa iteracyjnie, krok po
kroku zbliżając się do rozwiązania optymalnego. Jako kolejne przybliżenie rozwiązania może być wybrany dowolny element przestrzeni potencjalnych rozwiązań. Jednak jego wybór jest uzależniony od dwóch podstawowych czynników. Po pierwsze - od różnicy wartości między starym rozwiązaniem a propozycją nowego rozwiązania. Jeżeli propozycja nowego rozwiązania jest lepsza od swego poprzednika, to zostaje ona zatwierdzona jako nowe rozwiązanie (ponieważ lepiej przybliża rozwiązanie optymalne). Natomiast, jeśli nowa propozycja jest gorsza od dotychczasowego rozwiązania, wybiera się je drogą losowania. Wówczas prawdopodobieństwo wyboru nowej propozycji rozwiązania jest tym mniejsze, im różnica między rozwiązaniami jest większa. Ma to na celu ograniczenie zbytniego oddalenia się od wcześniej znalezionego rozwiązania.

Parametr nazywany temperaturą reguluje proces wyboru kolejnych przybliżeń w przypadku, gdy propozycja nowego rozwiązania jest gorsza. Jeżeli wartość temperatury jest duża, to prawdopodobieństwo wyboru jest duże. Jeżeli wartość temperatury jest mała, to  prawdopodobieństwo wyboru nowego rozwiązania, gorszego od poprzednika, jest bardzo małe. Temperatura jest w miarę postępowania algorytmu stale obniżana. Oznacza to, że w kolejnych krokach szansa przejścia do nowego, gorszego położenia maleje. Z upływem czasu rozwiązanie stabilizuje się, aż wreszcie żadne zmiany nie są akceptowane. Algorytmy tego typu są wykorzystywane do poszukiwania rozwiązań bliskich rozwiązaniom optymalnym w dużych zadaniach optymalizacyjnych.

Algorytm genetyczny

Opis algorytmu pochodzi ze strony: http://www.alife.pl/portal/gp/p/AGwstep.html

Algorytm genetyczny to najprościej rzecz ujmując jest to próba zasymulowania w pamięci komputera populacji jakiegoś gatunku. Na taką populację składają się dziesiątki, setki, tysiące pojedynczych osobników. Osobniki te między sobą mogą się krzyżować, mogą również następować jakieś samoistne zmiany w strukturze pojedynczego osobnika (tzw. mutacja). W wyniku krzyżowania i mutacji powstają nowe osobniki. Ze względu na fakt, że populacja ma swój z góry narzucony maksymalny rozmiar część osobników należy z niej usunąć (ten krok nazywany jest selekcją). Oczywiście usuwane są te najmniej przystosowane... Cały ten proces (krzyżowanie, mutacja, selekcja) powtarzany ustaloną wartość kroków. Jeżeli przez dłuższy czas nic się nie zmieni to kończone jest działanie programu. 

 Jako 'gatunek' przyjmujemy drogę dla ciężarówki, która ma pokonać. Każdy osobnik będzie pamiętał jedną trasę. Takich osobników może być dowolna ilość (im więcej tym bardziej zróżnicowana populacja jednak kosztem dłuższych obliczeń). Na początku do każdego osobnika wpisujemy trasę zupełnie losową... I rozpoczynamy algorytm genetyczny. Krzyżowanie polega na wymianie pomiędzy dwoma osobnikami pewnych elementów tras, natomiast mutacja może oznaczać wymianę w pojedynczym osobniku dwóch miast między sobą. Jeśli dodamy do tego krok selekcji, czyli wybór do następnej populacji osobników najlepiej przystosowanych (to znaczy takich które reprezentują trasy o najmniejszym koszcie) otrzymamy algorytm, który po pewnej liczbie kroków znajdzie nam całkiem niezłą trasę przez wszystkie miasta.

Algorytm losowy

Dla porównania napisano kolejny prosty algorytm, który działa całkowicie w sposób losowy. Z istniejącej trasy wybierane są 2 dowolne miasta i cały ciąg miast pomiędzy nimi zamienia swoją kolejność. Jeżeli funkcja celu polepszyła się to nowa trasa zostaje zapisana. Potem znowu losujemy 2 miasta itd. Algorytm dzięki niewielu operacjom jest w stanie w szybkim czasie zaleś rozsądne rozwiązanie, które jest minimum lokalnym.

4.     Opis implementacji

Opisany program oraz algorytmy całkowicie został zaimplementowane w C++  Borland Builder. W znacznej części wykorzystane zostały komponenty VCL do komunikacji programu z użytkownikiem. Wszystkie implementacje algorytmów zostały samodzielnie napisane z wykorzystaniem ogólnej teorii na temat sposobów realizacji.

5.     Sposób użytkowania programu

Pierwszy slajd przedstawia wstęp teoretyczny do zagadnienia problemu transportowego. Założenia transportowe oraz sposób wyznaczania funkcji celu. Aby móc przejść do następnej strony klikamy w przycisk „>>” znajdujący się na prawo od napisu Teoria.

Slajd nr 1 przedstawiający wstęp teoretyczny do zagadnienia transportowego

Kolejny slajd opisuje konkretny problem właściciela pewnej firmy transportowej, który zwraca z pomocą o rozwiązanie problemu minimalizacji kosztów transportu. Poniżej opisany jest sposób rozwiązania problemu, ustawienia parametrów, oraz możliwe do wyboru algorytmy.

Slajd 2: Opis zadania problemu transportowego

Poniżej należy sprecyzować parametry zadania. Najpierw należy ustalić liczbę odbiorców do odwiedzenia. Następnie wybrać współrzędne dla punktów odbioru towarów. Do wyboru mamy, współrzędne:

1. Wygenerowane losowo
2. Załadowane z pliku txt (plik powinien zawierać najpierw ilość odbiorców, a następnie współrzędne każdego z punktów)
3. Własne współrzędne podane po kolei z klawiatury

Po wybraniu współrzędnych należy sprecyzować ceny paliwa, zużycie benzyny na 100 km, oraz ilość dostępnych ciężarówek przez firmę. Na prawo wyświetlone zostaną współrzędne punktów dystrybucji. Aby anulować współrzędne należy kliknąć w przycisk resetuj współrzędne.

Slajd 3: Ustawienie parametrów zadania transportowego

Ustawienie parametrów algorytmu dokonuje się przez wpisanie odpowiednich wartości w podanych poniżej polach. Do symulowanego wyżarzania możemy zmienić:

1.      temperaturę  początkową

2.      szybkość studzenia (parametr delta)

W algorytmie genetycznym mamy większą możliwość zmiany parametrów. Ustawić możemy:

1.      Liczebność populacji

2.      Prawdopodobieństwo krzyżowania

3.      Prawdopodobieństwo mutacji

4.      Ilość kroków powtórzeń

Jest również możliwość wybrania algorytmu zachłannego, który daje całkiem dobre rezultaty przeszukiwania. Tutaj nie mamy możliwości sprecyzowania parametrów.

Na mapie możemy zobaczyć i ocenić jakość wybranej trasy. 

Slajd 4 Algorytmy rozwiązania problemu

Na ostatnim slajdzie możemy zobaczyć statystyki znalezionego rozwiązania. Wykres obrazuje przebieg poszukiwania rozwiązania. Koszty danego rozwiązania w stosunku do cykli działania programu. Im więcej cykli tym rozwiązanie jest bliższe optymalnemu.

Slajd 5 Wykres i statystyki danego rozwiązania

Poniżej znajduje się tabela wraz z danymi uzyskanymi dla najlepszego znalezionego rozwiązania dla poszczególnych algorytmów. Na jej podstawie można precyzyjnie porównać i ocenić jakość danego algorytmu, oraz znalezionego rozwiania.

6.     Testy porównawcze

Do testów wybierzemy 2 zestawy zadań i porównamy uzyskane wyniki:

Zad 1

Ilość odbiorców:        15 losowo

Cena paliwa:              4.1 zł

Zużycie benzyny:        12 l

Ilość ciężarówek:       5

Zad 2

Ilość odbiorców:        50 losowo

Cena paliwa:              4.1 zł

Zużycie benzyny:        12 l

Ilość ciężarówek:         5

7.     Analiza i wnioski

Analizując zad 1 wynika, że najlepsze znalezione rozwiązanie to droga o długości:

166,6 [km]      koszt: 409,84   Koszt miesięczny:  8196 [ zł]

co w skali miesiąca daje najbardziej optymalny wynik

1. Algorytm wyżarzania najlepsze wyniki osiągał dla parametrów:

Temp=30   Delta=0.99   Powt=50

Skuteczność znajdywania najlepszego rozwiązania miał na poziomie 100% w czasie zadowalającym 0,1s.

2. Algorytm zachłanny nigdy nie osiągnął najlepszego rozwiązania ale miał wynik bliski najlepszemu. Jego średnia wynosi 169,82 co daje wynik średnio 1,9% gorszy od najlepszego rozwiązania
3. Algorytm genetyczny również nie znalazł najlepszego rozwiązania Średni wynik to: 179,3 co daje wynik 7,6% gorszy od najlepszego rozwiązania natomiast czasowo bardzo kiepsko się prezentuje. Wyniki osiągał po czasie 3 sekund. Co daje kilkakrotnie gorszy wynik od pozostałych algorytmów.

Dla zadania 2 sytuacja się prezentowała podobnie:

Również symulowane wyżarzanie najlepiej się prezentowało ze wszystkich algorytmów. Znajdywało najlepsze rozwiązanie, oraz charakteryzuje się dużą regularnością powtarzania wyników w jednakowym czasie. Rozrzut uzyskiwanych wyników jest minimalny.

Algorytm zachłanny nie znalazł najlepszego rozwiązania, ale jego wyniki były 5% gorsze od symulowanego wyżarzania. Również czasowo był 4 razy dłuższy. Najgorzej się prezentował algorytm genetyczny. Jego wyniki były dużo gorsze od oczekiwanych.

Wynika to z tego, że algorytm genetyczny w bardzo szybkim czasie osiągał minimum lokalne. Cała populacja zostaje zdominowana przez jeden i ten sam osobnik, przez co nie ma możliwości wymiany genu. Zastosowana metoda ruletki do selekcji osobników nie jest najlepszym rozwiązaniem. Powoduje to właśnie osiąganie minimum lokalnego. Wówczas nawet mutacja niewiele nam pomaga. Zbyt mało zmian wprowadza w pojedynczym osobniku. Należało by zmienić sposób reprezentacji osobnika oraz poprawić metodę selekcji osobników, wówczas uzyskalibyśmy znacznie lepsze rezultaty, a algorytm nie osiągałby szybko minimum lokalnego.

Najlepiej zaprezentował się algorytm symulowanego wyżarzania. Zastosowane metody znacznie przyśpieszyły działanie programu, wizualnie widać ze praktycznie dany algorytm znajduje rozwiązanie optymalne. Radzi sobie doskonale z dużą ilością węzłów,: nawet 100 i 150.

Znalezienie najlepszego rozwiązania ma ogromne znaczenie. W przypadku kiedy najlepszym rozwiązaniem jest trasa o koszcie miesięcznym 11586 zł to algorytm zachłanny znajdywał najlepsza trasę o koszcie 12724 zł. To daje 800 zł różnicy. Jak widać różnica jest spora. 800 zł to minimalne wynagrodzenie 1 pracownika. Przy lepszym algorytmie osiągamy większe zyski, nie tracąc na kosztach transportu. Mimo że algorytm jest lepszy tylko o 1% to rzeczywiste koszty mają znacznie wyraźniejszą różnice. Wiec nawet jeśli algorytm symulowanego wyżarzania świetnie prezentuje się to warto jeszcze postarać się o zaimplementowanie algorytmu znajdującego jeszcze lepsze rozwiązanie. Poprawa o 1% algorytmu pozwoli zredukować koszty w skali miesięcznej nawet o pensje 1 pracownika. Wiec jest o co walczyć.

8.     Bibliografia

1.      http://www.alife.pl/portal/gp/p/AGwstep.html

2.      http://kysy.rst.com.pl/projects.php

3.      http://pl.wikipedia.org/wiki/Komiwojażer

4.      math.uni.lodz.pl/~marta/zajecia/sztuczna/cw6/gen.pdf