Wstęp

Podstawową wartością, którą będziemy chcieli mierzyć w przypadku różnych wersji algorytmu jest czas po jakim zostaje znalezione co najmniej jedno poprawne rozwiązanie problemu wyjściowego. W szczególności rozwiązanie takie może nie zostać znalezione w akceptowalnym czasie, np. ze względu na źle dobrane parametry algorytmu.

Tam gdzie to możliwe, mierzony będzie nie rzeczywisty czas, ale liczba iteracji algorytmu wymagana do znalezienia rozwiązania. Ze względu na stochastyczną naturę algorytmu, liczba iteracji nie jest jednoznacznie zależna od parametrów algorytmu i wyjściowego problemu, więc w każdym przypadku algorytm musi zostać wykonany wielokrotnie, i porównywać będziemy średnią liczbę iteracji oraz odchylenie standardowe.

Parametry

Możemy porównać dwie wersje algorytmu: hierachiczną i klasyczną (prosty algorytm genetyczny).

W obu przypadkach istnieje kilka podstawowych parametrów, które możemy modyfikować:

• rozmiar populacji
• prawdopodobieństwo mutacji

Ponadto, jakość algorytmu silnie zależy od:

• wybranej funkcji oceny - w tym przypadku do sprawdzenia jest wiele wariantów
• sposobu krzyżowania - wybór fragmentu planszy
• rodzaju mutacji

Dodatkowo, w przypadku algorytmu hierarchicznego, kluczowy jest podział na prefix i sufix. Chcemy więc porównać ze sobą różne sposoby wyboru prefixu.

Otrzymane wyniki

[ dokument ten będzie rozszerzany o otrzymane wyniki ]