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.