1

Sztuczna inteligencja

Badania i optymalizacja algorytmu mrówkowego

Przebieg ćwiczeń laboratoryjnych i warunki zaliczenia przedmiotu

studia zaoczne sem. VI rok. akad.2009/10

A. Ćwiczenia laboratoryjne ( 3 zajęcia * 3 godziny = 9 godzin )

Przedmiotem ćwiczeń jest badanie własności klasycznego algorytmu mrówkowego i taka jego
optymalizacja, aby w jak najkrótszym czasie znajdował najkrótszą ścieżkę w grafie od węzła
będącego ”mrowiskiem” do węzła symulującego ”pokarm” przy przyjętej skali problemu
określonej poprzez:
- ilość węzłów grafu w którym poruszają się mrówki,
- rozmieszczenie węzłów,
- ilość mrówek.

Studenci otrzymują szkielet aplikacji w postaci zestawu klas i ich implementacji, niezbędnych
do rozpoczęcia badań – aplikacja obiektowa AntAlgorithm v.1.0.0 napisana języku C++.

Studenci pracują w grupach 2-osobowych.

Ćwiczenia laboratoryjne przebiegają wg. niżej podanego schematu:

1. Zajęcia nr 1:

Podział na grupy. Zapoznanie się szczegółowo z dostarczonym szkieletem aplikacji.
Dyskusja na temat otrzymanego zadania. Uzupełnienie aplikacji o metody niezbędne
do właściwego wyprowadzania wyników badań (konieczna będzie praca w domu).
Przeprowadzenie wstępnych badań własności algorytmu.

2. Zajęcia nr 2:

Pokazanie osiągniętych wyników prowadzącemu zajęcia celem oceny. (Za wykonanie
tej części ćwiczeń student może otrzymać 10-20 punktów). Indywidualne ustalenie w
każdej z grup opisanej wyżej skali problemu celem dalszych badań, przeprowadzenie
badań zachowania się algorytmu mrówkowego przy różnych parametrach aplikacji i
jego optymalizacja, zebranie odpowiednich danych i przygotowanie sprawozdania
końcowego(konieczna będzie praca w domu).

3. Zajęcia nr 3:

Zajęcia przeznaczone są na ocenę i dyskusję osiągniętych przez poszczególne grupy
wyników, oraz końcową ocenę indywidualną studentów. Za wykonanie drugiej części
ćwiczeń student może otrzymać 20-40 punktów.

Promowana jest: jakość i terminowość realizacji poszczególnych etapów projektu (ocena dla
grupy), organizacja i współdziałanie poszczególnych członków w zespole (ocena dla grupy),
osiągnięte rezultaty (ocena dla grupy), ponadto indywidualny wkład każdego z członków
zespołu w osiągnięte rezultaty (ocena indywidualna).

Przedmiotem oceny będzie: rodzaj, obszerność i celowość przeprowadzonych badań, oraz
sposób prezentacji osiągniętych wyników w sprawozdaniu końcowym, dokumentującym
osiągnięte wyniki.

2

Parametry algorytmu (których wpływ na jego optymalizację należy przede wszystkim
przebadać):
alfa (parametr ”świata”) – współczynnik "kuszenia" mrówki feromonem,
beta (parametr ”świata”) – współczynnik "kuszenia" mrówki bliskością sąsiedniego węzła,
feromon (parametr ”mrowiska”) – ilość pozostawianego feromonu przez mrówkę w węzłach
grafu po osiągnięciu pokarmu.

Dalsze badania (których ilość, obszerność i rzetelność może być przedmiotem bardzo
wysokiej oceny punktowej) będą polegały na:

 uzupełnieniu algorytmu o zjawisko zaniku śladu feromonowego w każdym cyklu we

wszystkich węzłach grafu o pewną wielkość (uzupełnienie raczej niezbędne),

 uzupełnieniu algorytmu o nowe źródło pokarmu, pojawiające się w trakcie obliczeń,
 zaproponowanie innej, niż przyjęta w aplikacji, metody wyboru kolejnego węzła przez

mrówkę.

Minimalna zawartość sprawozdania :

 opisanie celu badań,
 przedstawienie przyjętych parametrów skali problemu z uzasadnieniem,
 wyniki badań udokumentowane odpowiednimi tabelami i wykresami zależności,
 wnioski końcowe,
 kod źródłowy własnego programu jako załącznik.

Ponadto (jeśli zastosowano dla algorytmu ulepszenia) :

 wyniki badań po zastosowaniu dla algorytmu ulepszeń,
 porównanie wyników dla algorytmu klasycznego i algorytmu z zastosowanymi

ulepszeniami.

2. Warunki zaliczenia laboratorium

Za ćwiczenia laboratoryjne student może uzyskać na zaliczeniu maksymalnie 60 punktów.
Ćwiczenia uznaje się za zaliczone jeśli student uzyska nie mniej niż 30 punktów.

Ostatni dzień zajęć laboratoryjnych, wskazany w harmonogramie zajęć, jest ostatecznym
terminem zaliczenia ćwiczeń laboratoryjnych.