WYKŁAD 09: SYSTEM OPTYMALIZACJI MRÓWKOWEJ

Mrówki porozumiewają się ze sobą za pomocą znaków substaancji chemicznych. Poruszają się
zgodsnie z jakimś rozkładem prawdopodobieństwa zgodnie ze znakami chemicznymi
zostawionymi.
Z badań nad feromonami wiemy, że to substancja, kóra wyparowuje. Jeżeli mamy zatem mrówkę,
która przejdzie po jakiejś trasie, to jej ślad będie znikał. Ale gdy wiele mrówek podąża za nią, to
one wzmacniają ten ślad. Oznacza to, że trasa ma większe prawdopodobieństwo, po której będą
przechodzi mrówki.

Zatem należy jakoś zaimplementować tę metodę.

Graf:
G(V,E)
V - takie wierzchołki, które reprezentują komponent, który może zostać dodany do rozwiązania.
E - Zbiór ścieżek, po której mogą poruszać się mrówki.
Z definicji graf jest pełny.
Mrówka startuje z S. Wybiera losowo ścieżkę, po której przejdzie z jednego wierzchołka do
kolejnego. Z niego do wierzchołka V2 itd. Te wierzchołki, to komponenty rozwiazania. Startując
oczywiście od zera.

Przykłąd komiwojażera.
Rozpoczynamy od zbieru, gdzie s = 1.

Mrówka losowo wybiera miasto do którego przejdzie w kolejnym kroku. Budujemy permutację
rozwiazania problemu komiwojażera. Ale ten graf jest pełny. Jeżeli ta mrówka dojdzie gdzieś, to
mamy pewną permutację. Może się losowo trafić tak, że z powrotem wrócimy do jakeigoś
wcześniejszego wierzchołka. A too niedopuszczalne. Graf jest pełny, ale my budujemy rozkład
prawdopowobieństwa ruchu, ale ruchy, które częściowo prowadzą do rozwiązań złych, to nie są
brane pod uwagę. Podejmując decyzję w węźle i mając rozwiązanie dotychczasowe tworzymy zbiór
rozwiazań dopuszczalnych. Na tej podstawie tworzymy rozkłąd pstwa wyboru kolejnego
wierzchołka/.

Jest to zatem klasyczny konstrukcyjny algorytm.
Jeżeli mrówka skonstruuje jakieś rozwiazanie, to na tej trasie zwiększamy ilość feromonów.
Następne mrówki mają większe prawdopodobieństwo wybrania tej właśnie trasy.

Ale można też sterować pierwszą mrówką i wypuścić za nią 500 mrówek. Oba rozwiązania są
dobre.

Należy opracować metodę, które regulują ilość feromonu zostawianego przez mrówkę (np f +=
0.1). Albo można też liczyć to troche inaczej.

Np mrówka startuje z S. Po każdym kroku można na krawędzi, przez która przechodzi zwiększać
ilość feromonu. Natomiast, jak jesteśmy w punkcie T i mmamy całe rozwiazanie, to można ocenić
jakość rozwiazanie, np. licząc kryterium. Można pomyślęć o metodzie, że dodajemy feromon, ale w
miejscu, gdzie znajdzie dobre rozwiazanie , to zostawi go więcej. Można zatem: na bieżąco
zmieniać ilość feromonu, albo pamiętać ścieżkę, po której przejdzie i wracać po tej ścieżce i szukać
dalej. Dla najlepszej dać +100.

Zwioększenie feromonów to "poprawianie onlinowe feromonu". Albo jest też ""Opóźniona
poprawka/update feromonu". JEżeli mamy najlepsze, to mrówka może coś zrobić, albo jak

znajdziemy najgorsze, to można je "kasować".

Dla ogólności można określić systemy, gdzie krawędzie i komponenty roziwązania mogą być
obdarzone feromomonem. Przejście mrówki może zatem zmieniać wagi krawędzi i wierzchołków
(graf podwójnie
Musimy stworzyć funkcję, która na podst wag stworzy funkcję rozkładu prawdopodobieństwa dla
wszystkich ruchów. Bierze np. najlepsze do tej pory rozwiązania i [pewne ruchy dyskwalifikuje, a
dla każdego dopuszczalnego ruchu musi przypisać prawdopodobieństwo.
Musi sie ono sumować do 1!!!

zatem:

<wzór 1<>

Więc gra.
Trzeba zainicjować też algorytmy, albo małą wartość, albo prawdopodobieństwo 1/2 dla każdego.

Podstawowy model. Do tego wszystkiego zaczęto robić to, co w alg zachłannych. Mrówka działa
losowa, ale musi być świadoma lokalnego rozwiazania. Więc dodajemy informację heurystyczną
związaną z ruchem.
Np. duże beta, to zachłanny alg. itd...

Teraz wymyślamy jak feromon wyparowuje. Zanimzrobimy update, to tę wartość zmniejszamy
wcześniejszą, przypisaną atrybutowi

<wzór 3>

Po roku 2000 stało się popularne: boska interwencja. Mrówki działają, ale my znając różne
parametry,i wiedząc, że to gdzie się te mrówki kierują zmienić w momencie, gdy idą całkowicie źle.
Czyli pewnym komponentom lub krawędziom dodajemy +100. Albo inna metoda: wszytsko działa
tak jak wcześniej, ale do schematu dodajemy determinizm. Pewne ruchy są losowe, ale są takie,
któ¶e powinny wystąpić. Np możemy być pewni, że jeżeli komiwojażer jest w mieście A to
następne musi być w mieście B. I to się robi tak, że wśród tych komponentów roziwązania
determinujemy zbiór wartości deterministycznych. Więc mrówka nie startuje z początkowego
rozwiązania, więc mrówka tylko dodaje do tego roziwązania szeczegóły.

No i tyle...

Zazwyczaj metaheurystyka jest dziwna. Ważne, aby dobrać jakieś dobre parametry alfa i beta.
Wiele rozwiazań stworzonych działały, ale nie było dodane, że np rozwiązanie dane znalazły w
rok...