plik

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

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:

(x) = N(x) \ S

, gdzie:

(·) - sąsiedztwo dynamiczne,

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

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

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

)

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

);

x* := x

; {x* - najlepsze dotychczasowe rozwiązanie}

K* := K(x

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

inicjuj listę tabu; {jako pustą}

i := 0;

repeat

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

’

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

przeszukiwania N(x

)}

for j := 1 to Mi do

begin

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

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.

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

3449

0,084

3,8%

3578

0,011

7,7%

ulysses16

6891

0,100

0,5%

6941

0,014

1,2%

gr17

2085

0,095

0,0%

2123

0,016

1,8%

gr24

1272

0,130

0,0%

1331

0,033

4,6%

ulysses22

7099

0,143

1,2%

7133

0,035

1,7%

bays29

2026

0,161

0,3%

2126

0,039

5,2%

swiss42

1366

0,239

7,3%

1380

0,092

8,4%

dantzig42

699

0,228

0,0%

699

0,160

0,0%

hk48

11780

0,291

2,8%

11859

0,144

3,5%

berlin52

8145

0,309

8,0%

8703

0,213

15,4%

brazil58

26428

0,370

4,1%

26213

0,201

3,2%

st70

773

0,389

14,5%

694

0,293

2,8%

gr96

67885

0,635

23,0%

64973

0,526

17,7%

kroB100

100

26015

0,626

17,5%

23316

1,144

5,3%

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

100

200

300

400

500

600

]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search

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

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

0,116

0,0%

0,014

0,0%

ftv33

1422

0,209

10,6%

1702

0,111

32,3%

ftv35

1537

0,213

4,3%

1780

0,078

20,8%

ftv38

1605

0,229

4,9%

2040

0,079

33,3%

p43

5634

0,264

0,2%

5761

0,119

2,5%

ftv44

1891

0,278

17,2%

2037

0,108

26,3%

ftv47

2015

0,284

13,5%

2696

0,132

51,8%

ry48p

15314

0,314

6,2% 15417

0,237

6,9%

ft53

8067

0,336

16,8% 13526

0,184

95,9%

ftv55

1979

0,334

23,1%

2562

0,201

59,3%

ftv64

2328

0,380

26,6%

2890

0,276

57,2%

ft70

41997

0,440

8,6% 50709

0,305

31,1%

ftv70

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%

100

200

300

400

500

600

łąd

]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search

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

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%

100

150

200

250

300

350

400

łąd

]

Rozmiar instancji problemu (N)

Symulowane wyżarzanie

Tabu Search