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 z
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 z
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.