Michał Kaczara 181132
Marek Karpiński 181172

Projektowanie Efektywnych Algorytmów

Projekt nr 2:

Badanie efektywności algorytmu Tabu Search dla problemu
komiwojażera.

Prowadzący: Prof. dr hab. inż. Adam Janiak

Grupa:

środa, godz. 18:55-20:35

POLITECHNIKA WROCŁAWSKA – GRUDZIEŃ 2011

2

1.

Wstęp

Celem projektu jest zbadanie efektywności algorytmu Tabu Search dla

symetrycznego i asymetrycznego problemu komiwojażera. W tym celu napisaliśmy
program testowy (w języku C++, skompilowany przy pomocy Microsoft Visual Studio 2008)
implementujący powyższy algorytm. Program został przetestowany przy pomocy
komputera z procesorem Intel Pentium Dual-

Core T3200 @ 2.0 GHz posiadającego 3 GB

pamięci RAM. Podczas testu zostały dokonane pomiary czasu wykonania algorytmu dla
różnych instancji problemu, które zostały zaprezentowane w sprawozdaniu. Dokonano
również porównania z algorytmem symulowanego wyżarzania zawartego w pierwszym
projekcie.

2. Opis

problemu komiwojażera

Problem komiwo

jażera (ang. TSP - Travelling Salesman Problem) to zagadnienie

z dziedziny teorii grafów polegające na znalezieniu w grafie pełnym ważonym cyklu
Hamilt

ona o minimalnej sumie krawędzi. W ogólności polega on na znalezieniu takiej

kolejności odwiedzania danego zbioru miast, aby łączna długość trasy (wraz z powrotem
do początkowego miasta) była jak najkrótsza. Problem ten należy do klasy problemów NP-
trudnych.

Zai

mplementowany przez nas algorytm ma za zadanie rozwiązanie tego problemu

w wersji symetrycznej i asymetrycznej

wykorzystując przy tym rodzaj sąsiedztwa typu 2-

opt. Polega ono

na wymianie dwóch łuków w grafie opisującym ścieżkę komiwojażera.

Wybieramy parę liczb (i,j) następnie z grafu usuwamy krawędzie i następnie tworzymy
nowe krawędzie.

3. Opis algorytmu Tabu Search

Tabu Search to

metaheurystyką, szukająca rozwiązania problemu poprzez

nadzorowanie innych procedur heurystycznych, w celu eksploracji przestrzeni rozwiązań
poza lokalne minimum. Metaheurystyka Tabu Search jest algorytmem samotnego
poszukiwacza, stanowiącym niemonotoniczne rozwinięcie deterministycznej heurystyki
lokalnych ulepszeń. Blokadę wywoływana przez optima lokalne przełamuje się tu dzięki
osłabieniu reguły selekcji. Rozwiązanie bieżące jest zawsze zastępowane przez najlepsze
rozwiązanie w sąsiedztwie, nawet jeśli powoduje to pogorszenie jakości.
Aby przeciwdziałać możliwości powtarzania się tych samych rozwiązań bieżących (a więc
powstawaniu

cykli),

zastosowano

tu

metodę

dynamicznego

sąsiedztwa.

Koncepcyjnie, polega to na

„okrojeniu” zdefiniowanego w zwykły sposób sąsiedztwa

poprzez usuniecie z niego rozwiązań, które już wcześniej były zaakceptowane jako
rozwiązania bieżące. Te ostatnie tworzą zbiór tabu. Można to symbolicznie zapisać
następująco:

N

d

(x) = N(x) \ S

T

, gdzie:

N

d

(·) - sąsiedztwo dynamiczne,

S

T

-

zbiór tabu.

W rzeczywistości mamy do czynienia z dwoma rodzaju odstępstwami od opisanej

zasady:



zamiast samych rozwiązań, zakazem obejmuje się transformacje (zwane tu ruchami)
zastosowane do wytworzenia tych rozwiązań (ze względów efektywnościowych)



zakaz powtórnego wyboru ruchu ma charakter czasowy

3

Tak wiec w praktycznych implementacjach zbiór (zwany niekiedy listą) tabu składa

się z ruchów wykonanych w ostatnich T krokach, gdzie T to czas ważności tabu.
Ponieważ przeniesienie zakazu z rozwiązań na transformacje może w konsekwencji
uniemożliwiać akceptacje „legalnych” rozwiązań (które jeszcze się nie pojawiły),
wprowadzono dodatkową regułę selekcji oparta na tzw. kryteriach aspiracji, spełniającą
role

„wyjątku od reguły”. Reguła ta określa, że zakazany ruch, spełniający pewne kryterium

aspiracji, jest ruchem dozwolonym. Podstawowym kryterium aspiracji jest wytworzenie
w wyniku zastosowania danego ruchu rozwiązania lepszego niż bieżące. Inne kryterium
aspiracji może być związane z pustością dynamicznego sąsiedztwa. Do realizacji zbioru
tabu używa się tzw. pamięci krótkoterminowej. W metodzie Tabu Search wykorzystuje się
również pamięć długoterminowa, gromadząca różne informacje statystyczne o przebiegu
procesu przeszukiwania, jak np. częstość wykonania „zwycięskich” ruchów. Informacje te
mogą być użyte w celu intensyfikacji lub dywersyfikacji procesu przeszukiwania.
Intensyfikacja polega na

„zagęszczeniu” próbkowania pewnego obszaru przestrzeni,

natomiast dywersyfikacja -

na rozproszeniu próbkowania w taki sposób, by żaden istotny

obszar nie został pominięty. Jedna z technik opartych na pamięci długoterminowej jest
modyfikacja funkcji oceny. Przykładem może być dodawanie do oryginalnej funkcji oceny
członu „kary” będącego funkcją częstości użycia odpowiedniego ruchu. Tabu Search
obfituje w rozmaitego rodzaju rozszerzenia i modyfikacje.

Algorytm Tabu S

earch to metoda przeszukiwania zbioru rozwiązań naśladująca

proces poszukiwania wykonywany przez człowieka. Jej podstawowymi cechami są:



wybieranie lokalnie najlepszego rozwiązania,



omijanie już odwiedzanych rozwiązań lub tych, które przypominają już odwiedzone
rozwiązania.

Algorytm rozpoczyna się od pewnego rozwiązania początkowego x

0

i sukcesywnie

porusza się po rozwiązaniach sąsiednich, przeglądając każdorazowo całe sąsiedztwo
rozwiązania bieżącego. W danej iteracji i, z sąsiedztwa aktualnego rozwiązania N(x

i

)

wybierane jest „niezakazane” rozwiązanie x

(i+1)

takie, że

K(x

(i+1)

) = min {K(x)} , gdzie x



N(xi).

Wybrane rozwiązanie jest zapamiętywane i w dalszym procesie poszukiwań jest
zakazane, czyli posiada status tabu. Do zapamiętywania rozwiązań odwiedzonych
wykorzystujemy pamięć krótkoterminową zwaną inaczej listą tabu. Następnie na liście
tabu zapamiętujemy pewną liczbę: ostatnio odwiedzonych rozwiązań, ich parametrów lub
ruchów do nich prowadzących. Lista ta jest kolejką typu LIFO, czyli nowe rozwiązanie
będzie zastępować najstarsze rozwiązanie.

Listing 1.

Pseudokod metody realizującej algorytm Tabu Search

procedure Tabu Search;

begin

wyznacz(x

0

);

x* := x

0

; {x* - najlepsze dotychczasowe rozwiązanie}

K* := K(x

0

); {K* - wartość f. kryterialnej dla x*}

inicjuj listę tabu; {jako pustą}

i := 0;

repeat

M

i

:= liczba elementów(N(xi));

K

’

:= ; {K’ - wart. najlepszego rozwiązania znaleziona podczas

przeszukiwania N(x

i

)}

for j := 1 to Mi do

begin

4

x:=kolejny element(N(xi));

if (K(x) < K’) AND (przejście x’-> x nie jest na liście tabu
OR przejście xi ! x jest na liście tabu ale spełnia kryterium
aspiracji)

then K’ := K(x); x

i+1

:= x;

if K’ < K* then x* := x

i+1

; K* = K’;

dodaj przejście xi -> xi

+1

na koniec listy tabu

(usuwając przejście z początku listy jeśli jest pełna);

i := i+1;

end;

until kryterium stopu;

end;

Lista tabu przechowuje iteracje ostatniej zamiany, co pozwoli nam sprawdzać czy dany
element znajduje się w tabu w czasie O(1). A następnie z każdą kolejną iteracją
dokonywana

jest aktualizacja tabu, czyli sprawdzenie polega na porównaniu odległości

w ite

racjach od obecnej instancji czy dany element znajduje się w tabu. Została również

stworzona tablica zawierająca częstotliwości dokonywania zmian, która jest
wykorzystywane wtedy gdy dokonywana jest dywersja. Nasz zaimplementowany algorytm
trwa tak długo jak wykona się odpowiednia ilość iteracji bądź w przypadku gdy waga
ostatniej zmiany będzie bardzo mała. Następnie rozpoczynamy procedurę przeglądu
sąsiedztwa w celu znalezienia najlepszego elementu. Obliczamy różnicę w długości drogi
co spowoduje zmiana s

ąsiedztwa typu 2-opt i sprawdzamy czy nowa droga będzie

krótsza. W przypadku gdy ta zamiana nie będzie znajdować się w tabu lub gdy uzyskana
droga będzie lepsza od najlepszej uzyskanej to wtedy ustawiamy nowe przemieszczenie.

4.

Analiza wyników przeprowadzonych badań

4.1 Wyniki badań dla symetrycznego problemu komiwojażera wraz
z porównaniem z algorytmem symulowanego wyżarzania

Tabela 1

. Zestawienie wyników i czasu działania algorytmu dla TSP w wersji symetrycznej

Algorytm:

Symulowane wyżarzanie

Tabu Search

Nazwa instancji Rozmiar Koszt Czas [s]

Błąd [%] Koszt Czas [s] Błąd [%]

burma14

14

3449

0,084

3,8%

3578

0,011

7,7%

ulysses16

16

6891

0,100

0,5%

6941

0,014

1,2%

gr17

17

2085

0,095

0,0%

2123

0,016

1,8%

gr24

24

1272

0,130

0,0%

1331

0,033

4,6%

ulysses22

22

7099

0,143

1,2%

7133

0,035

1,7%

bays29

29

2026

0,161

0,3%

2126

0,039

5,2%

swiss42

42

1366

0,239

7,3%

1380

0,092

8,4%

dantzig42

42

699

0,228

0,0%

699

0,160

0,0%

hk48

48

11780

0,291

2,8%

11859

0,144

3,5%

berlin52

52

8145

0,309

8,0%

8703

0,213

15,4%

brazil58

58

26428

0,370

4,1%

26213

0,201

3,2%

st70

70

773

0,389

14,5%

694

0,293

2,8%

gr96

96

67885

0,635

23,0%

64973

0,526

17,7%

kroB100

100

26015

0,626

17,5%

23316

1,144

5,3%

5

lin105

105

18517

0,663

28,8%

16315

0,775

13,5%

pr107

107

55863

0,754

26,1%

50390

0,927

13,7%

bier127

127

139522

0,866

18,0% 129015

1,309

9,1%

ch130

130

7861

0,755

28,7%

6446

1,476

5,5%

pr136

136

130030

1,111

34,4% 106486

1,449

10,0%

gr137

137

94241

0,933

34,9%

81181

1,228

16,2%

pr144

144

93526

1,073

59,8%

67831

1,102

15,9%

u159

159

43381

1,235

3,1%

42080

1,768

0,0%

kroB200

200

41791

1,263

42,0%

33423

3,023

13,5%

tsp225

225

5542

1,521

41,4%

4183

3,213

6,7%

pr264

264

77977

1,895

58,7%

54995

8,782

11,9%

a280

280

2808

1,931

8,9%

2634

8,825

2,1%

lin318

318

73460

2,134

74,8%

48055

9,397

14,3%

fl417

417

33403

2,791

181,6%

14228

14,705

20,0%

rd400

400

25337

2,529

65,8%

16585

25,492

8,5%

pcb442

442

84027

3,060

65,5%

52231

47,017

2,9%

d493

493

56335

4,239

60,9%

38323

63,224

9,5%

att532

532

50192

3,914

81,3%

30985

86,529

11,9%

pa561

561

4869

3,554

76,2%

2974 107,626

7,6%

u574

574

40197

5,386

8,9%

38328

44,099

3,9%

gr666

666

428150

5,686

45,5% 337199

69,573

14,6%

Wykres 1

. Zależność czasu wykonywania algorytmu od rozmiaru instancji problemu (N)

0,000

20,000

40,000

60,000

80,000

100,000

120,000

140,000

160,000

0

100

200

300

400

500

600

C

za

s

[s

]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search

6

Wykres 2

. Zależność błędu wyznaczania optymalnego kosztu drogi w zależności do rozmiaru instancji

problemu (N)

4.2

Wyniki badań dla asymetrycznego problemu komiwojażera wraz

z

porównaniem z algorytmem symulowanego wyżarzania

Tabela 2

. Zestawienie wyników i czasu działania algorytmu dla TSP w wersji asymetrycznej

Algorytm:

Symulowane wyżarzanie

Tabu Search

Nazwa instancji Rozmiar Koszt Czas [s]

Błąd [%] Koszt Czas [s] Błąd [%]

br17

17

39

0,116

0,0%

39

0,014

0,0%

ftv33

34

1422

0,209

10,6%

1702

0,111

32,3%

ftv35

36

1537

0,213

4,3%

1780

0,078

20,8%

ftv38

39

1605

0,229

4,9%

2040

0,079

33,3%

p43

43

5634

0,264

0,2%

5761

0,119

2,5%

ftv44

45

1891

0,278

17,2%

2037

0,108

26,3%

ftv47

48

2015

0,284

13,5%

2696

0,132

51,8%

ry48p

48

15314

0,314

6,2% 15417

0,237

6,9%

ft53

53

8067

0,336

16,8% 13526

0,184

95,9%

ftv55

56

1979

0,334

23,1%

2562

0,201

59,3%

ftv64

65

2328

0,380

26,6%

2890

0,276

57,2%

ft70

70

41997

0,440

8,6% 50709

0,305

31,1%

ftv70

71

2533

0,417

29,9%

3536

0,310

81,3%

ftv170

171

5025

1,019

82,4%

5717

2,259

107,5%

rbg323

323

1557

1,610

17,4%

3458

9,999

160,8%

rbg358

358

1390

1,829

19,5%

3571

13,525

207,1%

rbg403

403

2597

2,081

5,4%

4177

18,385

69,5%

rbg443

443

2887

2,345

6,1%

5134

17,082

88,7%

0,0%

20,0%

40,0%

60,0%

80,0%

100,0%

120,0%

140,0%

160,0%

180,0%

200,0%

0

100

200

300

400

500

600

B

łąd

[%

]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search

7

Wykres 3

.Zależność czasu wykonywania algorytmu od rozmiaru instancji problemu (N)

Wykres 4

. Zależność błędu wyznaczania optymalnego kosztu drogi w zależności do rozmiaru instancji

problemu (N)

5. Wnioski oraz podsumowanie

Z przeprowadzonych przez nas badań i otrzymanych wyników można wyciągnąć

kilka wniosków. Oczywistym wnioskiem jest fakt, że wraz ze wzrostem rozmiaru instancji
rośnie czas działania algorytmu Tabu Search. Dotyczy to również wersji symetrycznej jak i
asymetrycznej. W wersji symetrycznej

dla rozmiarów instancji mniejszych niż 300

elementów czas wykonywania algorytmu jest stosunkowo mały i sięga do 10 sekund. Dla
instancji

większych od powyższej czasy wzrastają znacząco. Czasy wykonywania dla

dużych instancji są o wiele większe niż czasy dla algorytmu symulowanego wyżarzania.
Jednak ta metoda daje dużo mniejszy zakres błędu.

0,000

2,000

4,000

6,000

8,000

10,000

12,000

14,000

16,000

18,000

20,000

0

50

100

150

200

250

300

350

400

Czas

[s]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search

0,0%

50,0%

100,0%

150,0%

200,0%

250,0%

0

50

100

150

200

250

300

350

400

B

łąd

[%

]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search

8

W przypadku symetrycznym oscyluje on w przedziale od 0-20% od optymalnego
rozwiązania. Natomiast w metodzie symulowanego wyżarzania błąd był kilkakrotnie
większy niż w metodzie Tabu Search.
W przypadku asymetrycznym czas wykonywania algorytmu Tabu Search dla instancji
mniejszych niż 100 dochodził do 0,3 sekundy, lecz dla większych instancji czas wzrastał
kilkakrotnie.

Największy czas dla wersji asymetrycznej wynosił około 18 sekund.

Czasy wykonywania algorytmu Tabu S

earch są większe niż czasy z algorytmu

symulowanego wyżarzania. Można powiedzieć, że metoda Tabu Search jest o wiele
wolniejsza, lecz bardziej skuteczna w znalezieniu optymalnego rozwiązania niż metoda
symulowanego wyżarzania. W naszej kwestii leży to czy chcemy szybko otrzymać
rozwiązania, ale znacznie odbiegające od optymalnego, czy może dysponujemy większym
zasobem czasu i otrzyma

my znacznie lepsze rozwiązania.

9

6. Bibliografia

1. Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford:

Wprowadzenie do algorytmów, WNT

2.

Z. Michalewicz, D.B. Fogel: Jak to rozwiązać, czyli nowoczesna heurystyka., WNT

3. V. Cerny, A thermodynamical approach to the travelling salesman problem: an

efficient simulation algorithm. Journal of Optimization Theory and Applications,
45:41-51, 1985