network-ant.gif

Przykład:

 

Jedna z 3 mrówek ma zadanie dotarcia do Królowej Mrówek. Należy wybrać najlepszą z mrówek, tzn. taką, której łączny “wysiłek” w dotarciu do Królowej będzie najmniejszy.

mrówki.001.jpeg

W pierwszym scenariuszu, droga każdej z mrówek do Królowej jest równa, tzn.

d(M1) = d(M2) = d(M3).

 

W takim wypadku nie ma znaczenia, którą z mrówek wybierzemy - każda jest w takim samym stopniu “dostosowana” do wykonania zadania.

Rozpatrzmy teraz drugi scenariusz, w którym mrówka M3 ma najkrótszą drogę do Królowej.

 

W tym wypadku zasadnym jest wybór tej mrówki do realizacji zadania.

mrówki.002.jpeg
mrówki.003.jpeg

W trzecim scenariuszu wprowadzamy “zakłócenie”.

 

Mrówka M3 ma co prawda najkrótszą drogę do Królowej, ale jest “zmęczona” całodzienną pracą i jej czas (t = 1x) dotarcia do Królowej jest dwukrotnie dłuższy (t=2x) niż dwóch pozostałych mrówek.

Którą mrówkę wybierzemy w takim wypadku do realizacji zadania?
Jeżeli odrzucimy M3 to wybór spośród dwóch pozostałych nie jest jednoznaczny - obie mrówki są w takim samym stopniu “dostosowane” do wykonania zadania.

Czwarty scenariusz zakłada kolejne zakłócenie. Droga mrówek M1 i M3 jest “bezpieczna” - na drodze mrówki M2 żeruje niebezpieczny owad, gotowy do jej zjedzenia.

 

M2 musi ominąć owada wydłużając swoją drogę do Królowej 1.5 krotnie (t = 1.5x). Oczywiście, wydłuży się również droga mrówki do Królowej.

W tym przypadku wskazane  jest wykonanie obliczeń, które pozwolą nam na wybór odpowiedniej mrówki.

mrówki.004.jpeg
mrówki.005.jpeg

W ostatnim (piątym) scenariuszu sytuacja jest bardziej skomplikowana.

Mamy trzy Królowe w kolonii (pleometrozja) oraz sześć mrówek, które mają w parach po dwie dotrzeć do każdej z Królowych. Każda z mrówek posiada inne “właściwości” a na drodze mrówek istnieją “ograniczenia”. Naszym zadaniem jest wybór “najbardziej dopasowanych” par mrówek dla każdej z Królowych.

Układając różne kombinacje przydziału mrówek do Królowych jesteśmy w stanie znaleźć najlepsze (z punktu widzenia funkcji celu) - optymalne - rozwiązanie.

Problem polega na tym, że dla np. 15 mrówek (z których każda posiada inne właściwości) i 3 Królowych (z których każda również posiada inne właściwości) istnieje 756 756 możliwych rozwiązań.

Dodatkowo należy uwzględnić fakt, że drogi mrówek się przecinają (kolizje) - co powoduje dodatkowe komplikacje w doborze optymalnego rozwiązania…
 
Nasz zespół podjął się zadania rozwiązywania przedstawionych problemów optymalizacyjnych w naszym oprogramowaniu.

Jeżeli chcesz się dowiedzieć, w jaki sposób zaimplementowaliśmy przydział x bezzałogowych statków powietrznych do y celów (z uwzględnieniem właściwości obiektów, istniejących ograniczeń oraz reguł) przy wykorzystaniu algorytmów genetycznych - skontaktuj się z nami.
mapa.PNG