Projektowanie efektywnych algorytmów
Projekt 2
Problem1: Problem komiwojażera
Zadanie 2: Algorytm Tabu search
Elżbieta Tchorowska, 171067
Konrad Kukulski, 163930
Spis treści:
1. Wstęp 3
2. Kryteria algorytmu 3
3. Wyniki algorytmu 4
3.1 Wyniki czasowe 4
3.1.1 Wykres czasu od wielkości instancji 4
3.1.2 Wykres czasu od liczby kroków 5
3.1.2.1 Instancja o wielkości 17 miast 5
3.1.2.2 Instancja o wielkości 52 miast 6
3.1.2.3 Instancja o wielkości 280 miast 6
3.1.2.4 Instancja o wielkości 1291 miast 7
3.1.2.5 Ogólny wykres kroków od czasu 7
3.1.3 Wykres czasu od listy tabu 8
3.1.3.1 Instancja o wielkości 17 miast 8
3.1.3.2 Instancja o wielkości 52 miast 9
3.1.3.3 Instancja o wielkości 280 miast 9
3.1.3.4 Instancja o wielkości 1291 miast 10
3.2 Wyniki odległości 10
3.2.1 Wykres rozwiązań od liczby kroków dla danej listy tabu 10
3.2.1.1 Instancja o wielkości 17 miast 11
3.3 Wyniki ogólne 12
3.3.1 Histogram wyników 12
4. Wnioski 12
Naszym zadaniem było przeprowadzenie szeregu testów algorytmu Tabu search dla podanych danych testowych oraz porównanie ich z dostępnymi wynikami.
Sprzęt, na którym testowano algorytm to Intel Pentium Core Duo 1,83 GHz, 1 GB pamięci RAM.
Algorytm został napisany w języku C++, środowisko DevC++. W działaniu algorytmu ograniczono liczbę wyświetleń na ekran do zera. Zapis był przeprowadzony do pliku wynikowego.
Algorytm Tabu search oraz jego skuteczność zależą od wielkości listy Tabu i liczby kroków algorytmu. Liczba kroków algorytmu zmienia się w zależności od liczby miast w instancji, gdzie wzór wynosi <<liczba_miast*k>>, gdzie k jest liczbą całkowitą z przedziału <2,4>.
W naszym projekcie zmienna jest również wielkość listy tabu, której wielkość jest liczbą całkowitą z przedziału <2,6>.
W pierwszej kolejności postanowiliśmy sprawdzić, jakie są czasy wykonywania algorytmu w zależności od wielkości instancji problemu, czyli liczby miast. Dla lepszej widoczności tej zależności na wykresie znajdują się czasy dla algorytmu liczącego dla minimalnej wielkości listy Tabu=2 oraz minimalnej liczby kroków=liczba_miast*2.
Można przypuścić, że wykres czasu od wielkości instancji przypomina funkcję kwadratową.
Do przeprowadzenia testu jak zmienia się czas algorytmu w zależności od liczby kroków, wybrano kilka w miarę różnych od siebie instancji i porównano ich wykresy, zakładając, że powinny wyglądać podobnie.
Niezależnie od wielkości instancji czas w zależności od liczby kroków rośnie liniowo.
Podobnie jak poprzednio wybrano kilka różnych od siebie instancji i porównano czas działania algorytmu dla różnych wielkości listy tabu.
...
niobe666