4552034827

3. Poszczególne kroki algorytmu

3.1 Losowanie pierwszej generacji

Ponieważ pierwsze próby uruchomienia algorytmu przy losowaniu populacji z całego zbioru miast dawały bardzo słabe wyniki w kryterium czasu wyszukiwania rozwiązania, postanowiliśmy zastosować optymalizację dzielenia grafu na wiele niezależnych podgrafów , w których dopiero dokonywaliśmy losowania cech poszczególnych osobników.

Po przemyśleniu sposobu dzielenia grafu zdecydowaliśmy się go dzielić na grupy zawierające K wierzchołków, gdzie ostatnia grupa może posiadać mniej niż K wierzchołków.

Sposób dzielenia grafu ukazuje poniższy rysunek

Gdzie:

Czerwony punkt - magazyn Ilość miast-16 K - 4

Jak łatwo zauważyć nie jest to jedyny sposób dokonania podziału na podgrafy. Dlatego postanowiliśmy równolegle dokonywać obliczeń przy zastosowaniu innych podziałów.

3.2 Selekcja

Przed każdym krzyżowaniem osobników w populacji musimy dokonać wyboru, które osobniki powinny mieć największą szansę zostania rodzicem, by cechy określające największą jakość byty przekazywane następnym pokoleniom. Operacja ta nazywana jest selekcją.

W naszym projekcie postanowiliśmy skorzystać z metody ruletkowej przy doborze rodziców. Polega ona na wypełnieniu koła ruletki ocenami jakości wszystkich chromosomów w danej populacji. Każdy chromosom w ten sposób zajmuje część koła, która odpowiada jego jakości.

Mając tak wypełnione koło ruletki dokonując losowania łatwo można zauważyć, że chromosom 1 ma największą jakość, a co za tym idzie - ma największą szansę zostania rodzicem.

Ponieważ w naszym przypadku jakość osobnika jednoznacznie określana jest przez długość trasy, gdzie lepszym wynikiem jest trasa krótsza byliśmy zmuszeni funkcję oceny zmodyfikować.

Modyfikacja polega na wstępnym posortowaniu rosnąco populacji według długości ich tras po czym nadaniu im ocen od 1 do N, gdzie ocena „1" nadawana jest osobnikowi ostatniemu, a ocena N (równa liczebności populacji) osobnikowi pierwszemu - najlepszemu. Tak nadane oceny mogą być użyte w celu dokonywania selekcji.