Algorytm mrówkowy

Obecnie w dziedzinie sztucznej inteligencji coraz większą popularność zyskują algorytmy inspirowane światem naturalnym. Nie inaczej jest w przypadku algorytmów mrówkowych. Jak sama nazwa wskazuje swoje działanie opierają one na zachowaniu kolonii mrówek. Zacznijmy więc od sposobu w jaki owady te znajdują pożywienie.

Jak funkcjonuje mrowisko?

Jak dobrze wiadomo głównym zadaniem kolonii mrówek jest budowa mrowiska oraz poszukiwanie pożywienia. Dla tak mały istot jest to zadanie bardzo złożone, które zdecydowanie przerasta możliwości pojedynczego osobnika. Kluczem do poprawnego funkcjonowania całego mrowiska jest w tym przypadku współpraca pomiędzy wszystkimi osobnikami z danej kolonii. Pojedyncza mrówka jest istotą mało inteligentną i bez pomocy swoich towarzyszy nie byłaby w stanie znaleźć pożywienia. Jak jednak łatwo zauważyć mrówki istnieją od bardzo dawna i jakoś sobie radzą. Każdy z nas będąc dzieckiem zapewne nieraz starał się utrudnić trochę życie mrówkom stawiając na ich drodze jakąś przeszkodę. „Niestety” owady te zawsze w jakiś sposób potrafiły sobie z tą trudnością poradzić. Najpierw ruch pojedynczych mrówek wydawał się bardzo chaotyczny, po pewnym czasie jednak droga którą poruszały się mrówki stawała się coraz bardziej optymalna. Czy nie zastanawiało was wtedy w jaki sposób ten proces się odbywa?

Poszukiwanie najlepszej trasy do pożywienia zapewnia mrówkom feromon (pewna substancja fizyczna), którą mrówki wydzielają podczas poruszania się. Każdy osobnik podczas podejmowania decyzji o kierunku w którym będzie się poruszał kieruje się zarówno swoją intuicją jak i zapachem feromonów pozostawionych przez współtowarzyszy z mrowiska. W tym wypadku można powiedzieć, że feromon pełni rolę „mózgu” całego mrowiska. Powstaje jednak kolejne pytanie: Dlaczego wybierana przez mrówki trasa jest optymalna? Wynika to z faktu, że na trasach częściej używanych znajduje się większa ilość feromonu więc mrówki będą wybierały tą drogę z większym prawdopodobieństwem. Po pewnej ilości czasu wszystkie trasy zaczną się zbiegać do jednej, która będzie drogą optymalną. Poniżej przedstawiamy przykład w jaki droga wybrana przez mrówki zmienia się w czasie:

Obrazek powyżej ukazuje w jaki sposób mrówki znajdują najkrótsze trasy.

A: Mrówka dociera do punktu, którym musi podjąć decyzję
B: Część mrówek wybiera górną, a część dolną ścieżkę
C: Zakładając, że mrówki poruszają się ze stałą prędkością, mrówki które wybrały dolną krótszą ścieżkę dojdą szybciej do następnego punktu decyzyjnego niż mrówki, które wybrały dłuższą górną ścieżkę
D: Ilość feromonu wzrasta szybciej na krótszej ścieżce. Liczba myślników na obrazku jest w przybliżeniu proporcjonalna ilości zostawionego feromonu poprzez mrówki

Algorytm mrówkowy

Algorytm mrówkowy został po raz pierwszy zaproponowany przez Marco Dorigo. Pozwala on na znalezienie pewnej trasy w wejściowym grafie a jego działanie jest inspirowane zachowaniem kolonii mrówek. Dzięki temu, że droga zwracana przez ten algorytm jest bardzo bliska trasie optymalnej algorytm mrówkowy jest bardzo często wykorzystywany przy rozwiązywaniu problemów NP zupełnych.

W algorytmach mrówkowych kolonia sztucznych osobników współpracuje ze sobą w trakcie poszukiwania optymalnych rozwiązań trudnych problemów kombinatorycznych.

Podstawowym aspektem działania ACO (Ant Colony Optimization) jest współpraca pomiędzy sztucznymi mrówkami. Tak samo jak w naturze komputerowe mrówki pozostawiają na trasie jaką przebyły ślad feromonowy, natomiast w początkowych iteracjach poruszają się w sposób losowy. Jest jednak kilka różnic pomiędzy prawdziwymi a sztucznymi osobnikami. Pierwszą z tych różnic jest fakt, że sztuczne mrówki poruszają się jedynie w granicach wyznaczonych przez wejściowy graf. W rzeczywistości natomiast mogą one wybrać trasę dowolną. Po drugie ilość pozostawionego feromonu w przypadku algorytmu ACO jest uzależniona od jakości rozwiązania znalezionego przez daną mrówka. W świecie naturalnym wartość ta związana jest natomiast z kondycją mrówki, która go zostawia. Kolejną różnicą jest fakt, że podczas działania algorytmu ślad feromonowy jest uaktualniany jedynie w przypadku kiedy mrówka znajdzie lepszą trasę.

Kolejną kwestią jako warto poruszyć jest sposób w jaki sztuczne mrówki znajdują pożądane rozwiązanie. W algorytmach ACO każda mrówka w każdym obiegu znajduje pewne rozwiązanie. Wynikiem działania całego programu jest rozwiązanie znalezione przez najlepszą z mrówek. Jeżeli trasa znaleziona przez sztucznego osobnika jest lepsza od dotychczasowo wygenerowanej na trasie aktualizowany jest ślad feromonowy dzięki czemu kolejne mrówki chętnie wybierają określone krawędzie w grafie.

Schemat algorytmu mrówkowego

Standardowe algorytmy mrówkowe działają wg następującego schematu:

Każda ze sztucznym mrówek buduje swoje rozwiązanie, krawędź którą będzie się poruszać losuje z określonym prawdopodobieństwem na które wpływają:
- wartość funkcji lokalnej (najczęściej waga krawędzi)
- ilość feromonu jaka zgromadzona jest na krawędzi
Po znalezieniu rozwiązania mrówka zostawia na swojej trasie pewną ilość feromonu związaną z jakością znalezionej drogi.
Analogicznie do sytuacji jaka ma miejsce w naturalnym świecie feromon po pewnym czasie wyparowuje. Podejście takie pozwala na uniknięcie zbieżności poszukiwanego rozwiązania do minimum lokalnego.
Po określonej ilości iteracji algorytm mrówkowy kończy swoje działanie. Zwracanym wynikiem jest najlepsze znaleziona do tej pory trasa.

Zastosowanie algorytmu mrówkowego do problemu marszrutyzacji

W naszym problemie każda sztuczna mrówka symbolizuje flotę samochód dostawczych, które rozwożą towar do klientów. Pierwszym problemem na jaki napotkaliśmy jest fakt, że algorytmy mrówkowe oczekują na wejściu programu grafu pełnego. Kwestię tę rozwiązaliśmy w taki sposób, że przed rozpoczęciem działania algorytmu graf wejściowy jest zamieniany na graf pełny (w tym miejscu zakładamy więc, że istnieje droga łącząca każde z dwóch miast, droga taka może przebiegać przez inne miasta). W naszej implementacji przyjęliśmy również, że zmiana samochodu następuje w momencie gdy mrówka wraca do bazy (ponieważ fakt ten oznacza, że aktualnemu samochodowi skończyła się dostępna przestrzeń bagażowa). Ważnym aspektem dostosowanego przez nas algorytmu jest także fakt, że nie dopuszczamy możliwości generacji trasy błędnej. W przypadku gdy mrówka (czyli samochód dostawczy) nie może wybrać już żadnej z krawędzi (ponieważ klienci mają zbyt duże wymagania dotyczące towaru) musi ona wrócić do bazy w celu ponownego załadunku.

Schemat i wejście algorytmu

Nasz algorytm przyjmuje na wejściu następujące parametry

liczba_kroków liczba_mrówek q0 t0 alfa p beta

Gdzie otrzymane współczynniki oznaczają:

α - parametr regulujący wpływ feromonu znajdującego się na krawędzi 0 < < 1

ρ - parametr określający stopień parowania feromonu

β - parametr regulujący wpływ wartości lokalnej funkcji celu

q0 – określający prawdopodobieństwo pomiędzy eksploracją, a wyborem najlepszej ścieżki podczas pobytu w punkcie decyzyjnym. Za każdym razem kiedy mrówka znajduje się w mieście i musi wybrać kolejne miasto na trasie jej podróży, losuje liczbę z przedziału [0;1]. Jeśli ta wylosowana liczba jest mniejsza od parametru q0 wtedy wybierana jest najlepsza ścieżka zgodnie ze wzorem (1):

gdzie τ(r, u) jest to wartość feromonu na krawędzi pomiędzy miastami r i u a η(r, u) jest to dystans pomiędzy tymi miastami.

W przeciwnym wypadku (eksporacja) wybierana jest ścieżka zgodnie ze wzorem (2)

t0 – początkowy poziom feromonu

Następnie program otrzymuje na standardowe wejście linijkę w formacie:

liczba_sam liczba_miast liczba_dróg liczba_paczek pojemność_samochodu

Przyjmujemy ze pojemność samochodu i masy towarów to liczby całkowite.

W celu uzyskania lepszego rozwiązania startowego przed rozpoczęciem właściwego algorytmy następuje wykonanie algorytmu zachłannego (w naszym wypadku jest to 1 iteracja 1 mrówki w naszym algorytmie). Następnie następuje inicjalizacja feromonu wg następującego wzoru (3)

Kod źródłowy algorytmu

#include "AntColony.h"
#include <cmath>
#include <iostream>
#include <limits>
Ant::Ant(unsigned n, unsigned k):
        path(n+1, 0), current(k%n), start(k%n), J(n, 1)
{
        J[current] = 0;
        path[0] = start;
}
AntColony::AntColony(unsigned n, double** distance, unsigned m, double q0, double t0, double alfa, double p, double beta, unsigned carCount, double carCapacity, double totalWeight, std::vector<City> cities, double c):
        n(n),distance(distance), m(m), t0(t0), beta(beta), q0(q0), alfa(alfa), p(p), i(0), totalBest(std::numeric_limits<double>::infinity()), carCount(carCount), carCapacity(carCapacity), c(c), totalWeight(totalWeight), cities(cities) // t0(0.1), beta(2.0), q0(0.98), alfa(0.1), p(0.1)
{
        _pheromone = new double[n*n];
        pheromone = new double*[n];
        for(unsigned i = 0; i < n; i++)
                pheromone[i] = &_pheromone[i*n];

/* wyznaczenie najkrótszej ścieżki w grafie*/        
        double minDistance = std::numeric_limits<double>::infinity();
        for(unsigned ii = 0; ii < n; ii++)
            for(unsigned jj = 0; jj < n; jj++)
                if(ii != jj)
                    if(minDistance > distance[ii][jj]) minDistance = distance[ii][jj];
/* inicjalizacja feromonu zgodnie ze wzorem 3*/

       for(unsigned ii = 0; ii < n; ii++)
            for(unsigned jj = 0; jj < n; jj++)
                if(distance[ii][jj] == minDistance)
                    pheromone[ii][jj] = c*t0;
                else
                    pheromone[ii][jj] = minDistance/distance[ii][jj]*c*t0;
/* Utworzenie odpowiedniej ilości mrówek*/
        for(int k = 0; k < m; k++) {
                ants.push_back(Ant(n, 0));
        }
        
}
/* metoda obliczająca prawdopodobieństwo pójścia daną ścieżką zgodnie ze wzorem 1*/
double AntColony::prob(unsigned k, unsigned r, unsigned s) {
        Ant& ant = ants[k];
        if(ant.J[s]) {
                return licznik = pheromone[r][s]/pow((distance[r][s]), beta);
        } else
                return 0;
}
/* metoda wyznaczająca miasto, które zostanie odwiedzone w aktualnym kroku czasowym*/
unsigned AntColony::next(unsigned k) {
        unsigned r = ants[k].current;

	/* decyzja o pójściu za feromonem, bądź eksploracją*/
        if(double(random())/double((1<<31)-1) < q0) {
                int maxU = -1;
                double maxV = -1;
		/* wybór ścieżki o najwyższej wartości współczynnika ilości feromony do jej długości z uwzględnieniem współczynnika beta*/
                for(unsigned u = 0; u < n; u++) {
                        if(!ants[k].J[u]) continue;
                        double tmp = pheromone[r][u]/pow((distance[r][u]),beta);
                        if(tmp > maxV) { maxV = tmp; maxU = u; }                
                }
                if(maxU == -1) throw;
                return maxU;
        } else {
		/* eksploracja zgodnie ze wzorem nr 2*/
                double mianownik = 0.0;
                for(unsigned u = 0; u < n; u++) {
                        if(ants[k].J[u]) {
                                mianownik += pheromone[r][u]/pow((distance[r][u]), beta);
                        }
                }
                double rand = double(random())/double((1<<31)-1)*mianownik;
                double sum = 0;
                unsigned u;
                for(u = 0; u < n; u++) {
                        if(!ants[k].J[u]) continue;
                        sum += prob(k, r, u);
                        if(rand < sum) {
                            return u;
                        }
                }
                throw;
                return n-1;
        }
}
/* Metoda wyznaczająca dystans pokonany przez mrówkę o numerze k*/
double AntColony::AntDistance(unsigned k) {
        double sum = distance[ants[k].start][ants[k].path[0]];
        for(int i = 0; i < ants[k].path.size()-1; i++) {
                sum += distance[ants[k].path[i]][ants[k].path[i+1]];
        }
        return sum;
}
/* Metoda uaktualniająca poziom feromonu na ścieżce pomiędzy miastami s i t do poziomu value*/
void AntColony::updatePheromone(unsigned r, unsigned s, double value) {
        pheromone[r][s] = pheromone[s][r] = value;
}
/* Metoda odpowiedzialna za każdy kolejny krok czasowy wykonany przez całą kolonię mrówek*/
unsigned AntColony::step() {
	/* Początkowo mrówki znajdują się w bazie, nie przenoszą towaru i posiadają pustą ścieżkę przejścia*/
        for(unsigned k = 0; k < m; k++) {
                for(int j = 0; j < n; j++) ants[k].J[j] = 1;
                ants[k].J[0] = 0;       
                ants[k].current = 0;
                ants[k].remaining = totalWeight;
                ants[k].remainingCapacity = carCapacity;
                ants[k].path.clear();
                ants[k].path.push_back(0);
        }
	/* Wszystkie mrówki muszą wykonać swoją pracę*/
        unsigned antsRunning = m;
	/* Dopóki jakaś mrówka kontynuuje swoją podróż*/
        while(antsRunning) {
		/* dla każdej mrówki*/
                for(unsigned k = 0; k < m; k++) {
		/* jeśli nie cały towar został do tej pory rozwieziony*/
                    if(ants[k].remaining != 0) {
			/* wybierz następne miasto*/
                        unsigned ne = next(k);
			/* Jeśli wymagana do rozwiezienia ilość towaru jest większa niż obecne ilość 			towaru w samochodzie, to powróć do bazy*/
                        if(ants[k].remainingCapacity < cities[ne].weight) {
                            ants[k].next = ants[k].start;
                            ants[k].path.push_back(ants[k].start);
                            ants[k].remainingCapacity = carCapacity;
                        } else {
				/* zostaw wymaganą ilość towaru i dodaj dane miasto do ścieżki*/
                            ants[k].J[ne] = 0;
                            ants[k].next = ne;
                            ants[k].path.push_back(ne);
                            ants[k].remainingCapacity -= cities[ne].weight;
                            ants[k].remaining -= cities[ne].weight;
			/* Jeśli rozwieziono cały towar to wróć do bazy*/
                            if(ants[k].remaining == 0) {
                                ants[k].next = ants[k].start;
                                ants[k].path.push_back(ants[k].start);
                                antsRunning -= 1;
                            }
                        }
                        if(ants[k].current == ne) throw;
                    }
                }
		/* Symulacja parowania feromonu (lokalna aktualizacja feromonu) */
                for(unsigned k = 0; k < m; k++) {
                        int ii = ants[k].current;
                        int jj = ants[k].next;
                        updatePheromone(ii,jj, pheromone[ii][jj]*(1-p) + p*t0);
                        ants[k].current = ants[k].next;
                }
        }               
        
	/* Znalezienie najlepszego rozwiązania znalezionego przez wszystkie mrówki podczas obecnego kroku czasowego*/
        unsigned bestAnt = 0;
        double bestDistance = AntDistance(0);
        for(unsigned k = 1; k < m; k++) {
                double tmp = AntDistance(k);
                if(tmp < bestDistance) { bestDistance = tmp; bestAnt = k; }
        }
 
	/* Aktualizacja feromonu zgodnie ze współczynnikiem rozkładu feromonu (globalna aktualizacja feromonu) */       
        for(int ii = 0; ii < n; ii++)
                for(int jj = 0; jj < n; jj++) {
                        updatePheromone(ii,jj, pheromone[ii][jj]*(1-alfa));
                }
	/* Jeśłi znalezione rozwiązanie jest lepsze od dotychczasowego rozwiązania, to zaktualizuj najlepsze rozwiązanie*/
        if(this->totalBest > bestDistance) {
            totalBest = bestDistance;
            totalBestPath = ants[bestAnt].path;
        }
	/* Wzmocnienie feromonu na aktualnej najlepszej ścieżce */       
        int ii = ants[bestAnt].path[0];
        int jj = ants[bestAnt].start;
        updatePheromone(ii,jj, pheromone[ii][jj] + alfa*1/(totalBest));
        for(unsigned i = 0; i < n; i++) {
                ii = totalBestPath[i+1];
                jj = totalBestPath[i];
                updatePheromone(ii,jj, pheromone[ii][jj] + alfa*1/(totalBest));
        }       
        return bestAnt;
}
pair<double, vector<unsigned> > AntColony::run() {
        AntDistance(step());
        i++;
        return make_pair(totalBest, totalBestPath);
}

Porównanie z algorytmem zachłannym

Testy wykonaliśmy na przykładowym grafie będącym w rzeczywistości mapą Kataru. Optymalne rozwiązanie dla tego zestawu danych wejściowych dla standardowego problemu komiwojażera to około 9600. Jeśli zastosujemy nasz algorytm dla jednego pojazdu to rezultat oscyluje w granicach 10000 co uważamy za dobry wynik. Poniżej przedstawiamy porównanie wyników uzyskanych przez algorytm zachłanny oraz zaimplementowany przez nas algorytm mrówkowy dla różnej ilości mrówek. Program uruchamiano na 200 iteracji algorytmu, w tabeli podano liczbę kroków potrzebnych do osiągnięcia ostatecznego wyniku.

	Liczba kroków	Liczba mrówek	\alfa	t_0	p	q0	\beta	Otrzymany rezultat
1	1	1	1.00	0.00001	0.1	0.1	2	17018.6	(algorytm zachłanny)
2	189	20	0.90	0.00001	0.1	0.1	2	14404.4
3	125	20	0.95	0.00001	0.1	0.1	2	15350.3
4	30	8	0.92	0.00001	0.1	0.1	2	14801.9
5	47	10	0.90	0.00001	0.1	0.1	20	16069.9
6	100	10	0.95	0.00001	0.1	0.1	2	15677.9
7	52	5	0.90	0.00001	0.1	0.1	2	15476.9
8	50	5	0.95	0.00001	0.1	0.1	2	15061.3

Jak widać w powyższej tabeli, w przypadku algorytmu mrówkowego bardzo istotne jest dobranie optymalnej parametryzacji algorytmu. Dobór ten jest ściśle uzależniony od specyfiki danych wejściowych, przez co nie istnieje uniwersalna optymalna parametryzacja algorytmu. Dobór konkretnej parametryzacji dla danego wdrożenia może być jedynie podparty testami na testowych danych – zawsze jednak możemy w rzeczywistości trafić na dane o zupełnie innej specyfice.

Dodatkowo, należy brać pod uwagę znaczny czas obliczeń - bardzo często będziemy potrzebowali otrzymać jakieś (suboptymalne) rozwiązanie w krótkim czasie. Jak widać na przykładzie parametryzacji 4, w bardzo krótkim czasie otrzymaliśmy niewiele gorszy rezultat od parametryzacji 2. Czas realizacji tego naszego algorytmu zależy od iloczynu liczby kroków, liczby mrówek oraz wielkości grafu, jak również od parametru alfa.