The Reactive Tabu Search

Reactive tabu search merupakan salah satu varian algoritma local search [link] dan termasuk dalam kategori algoritma stokastik, algoritma yang berdasarkan ilmu probabilitas dan statistika.  Sesuai namanya algoritma ini adalah pengembangan dari Tabu Search [link].  Tabu Search sendiri merupakan perbaikan dari local search, dimana optimasinya dilakukan dengan menandai solusi yang sudah pernah dilewati supaya tidak perlu dilewati lagi, dengan kata lain dimasukkan ke tabu list.  Kelemahan dari tabu search sendiri adalah ukuran dari tabu list yang tetap ataupun random dan perlunya setting parameter tabu list terkait seberapa besar ukuran tabu list yang optimal.  Pada reactive tabu search, kelemahan tabu search disolusikan dengan implementasi Reactive Search Optimization.  Berbeda dengan tabu search yang langsung memasukkan langkah sebelumnya ke dalam tabu list, reactive tabu search memungkinkan solusi yang sama untuk bisa dijelajahi kembali, untuk masuk ke dalam tabu search, suatu solusi akan diamati secara eksplisit, jika dianggap sering dilalui maka solusi ini baru dimasukkan ke dalam tabu list.

Secara garis besar Algoritma Reactive Tabu Search berpoin di tiga optimasi yang membedakannya dari Tabu Search biasa.

  1. Ukuran Tabu List yang Reactive terhadap proses iterasi.  Tabu list bisa increase (bertambah besar ukurannya) dengan cepat dan Decrease (bertambah kecil ukurannya) dengan perlahan berdasar kondisi iterasi yang terjadi.  Hal ini memberikan poin lebih karena tabu search menjadi lebih ‘cerdas’, memperbesar tabu list saat ada kemungkinan iterasi memasuki area berupa kumpulan optimum lokal dan mengurangi memori saat tabu search membutuhkan kondisi aspirasi dengan cara mundur perlahan ke solusi yang pernah ‘tabu’ namun dilegalkan karena ukuran tabu list yang kecil.
  2. Untuk masuk kedalam tabu list dengan kata lain menjadi solusi yang tabu, reactive tabu search memberlakukan kondisi tertentu dengan boleh memasukkan solusi yang sama secara berulang-ulang selama solusi ini tidak baru saja dipakai dalam periode tertentu.  Dengan teknik ini, solusi yang telah lama bisa menjadi tidak tabu atau boleh dipakai kembali, keuntungan yang didapat adalah membantu untuk memasuki kondisi aspirasi disaat tabu list dipenuhi oleh solusi yang mengarah ke lokal minimum sehingga algoritma terjebak atau stagnant.
  3. Best Solution dari Reactive Tabu Search dalam setiap iterasi nya ditentukan dengan membandingkan solusi terbaik antara langkah-langkah yang ada di tabu list dengan langkah-langkah yang ada di ‘legal moves’.  Hal ini diperlukan karena pada reactive tabu search yang digunakan untuk acuan pergerakan iterasi adalah langkah saat ini, sehingga solusi yang dicari tidak selau terjebak ke arah lokal minimum.

Pseudo code dibawah diambil dari [link]

 

Algoritma Utama Reactive Tabu Search

Input: $Iteration_{max}$, Increase, Decrease, ProblemSize
Output: $S_{best}$
$S_{curr}$ $\leftarrow$ ConstructInitialSolution()
$S_{best}$ $\leftarrow$ $S_{curr}$
TabuList $\leftarrow \emptyset$
ProhibitionPeriod $\leftarrow$ 1
For ($Iteration_{i}$ $\in$ $Iteration_{max}$)
MemoryBasedReaction(Increase, Decrease, ProblemSize)
CandidateList $\leftarrow$ GenerateCandidateNeighborhood($S_{curr}$)
$S_{curr}$ $\leftarrow$ BestMove(CandidateList)
TabuList $\leftarrow$ $Scurr_{feature}$
If (Cost($S_{curr}$) $\leq$ Cost($S_{best}$))
$S_{best}$ $\leftarrow$ $S_{curr}$
End
End
Return ($S_{best}$)
Algoritma di penjelasan poin nomor 1
Input: Increase, Decrease, ProblemSize
If (HaveVisitedSolutionBefore($S_{curr}$, VisitedSolutions))
$Scurr_{t}$ $\leftarrow$ RetrieveLastTimeVisited(VisitedSolutions, $S_{curr}$)
RepetitionInterval $\leftarrow$ $Iteration_{i}$ – $Scurr_{t}$
$Scurr_{t}$ $\leftarrow$ $Iteration_{i}$
If (RepetitionInterval < 2 $\times$ ProblemSize)
$RepetitionInterval_{avg}$ $\leftarrow$ 0.1 $\times$ RepetitionInterval + 0.9 $\times$ $RepetitionInterval_{avg}$
ProhibitionPeriod $\leftarrow$ ProhibitionPeriod $\times$ Increase
$ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
End
Else
VisitedSolutions $\leftarrow$ $S_{curr}$
$Scurr_{t}$ $\leftarrow$ $Iteration_{i}$
End
If ($Iteration_{i}$ – $ProhibitionPeriod_{t}$ > $RepetitionInterval_{avg}$)
ProhibitionPeriod $\leftarrow$ Max(1, ProhibitionPeriod $\times$ Decrease)
$ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
End
Algoritma di penjelasan poin no 2
Input: ProblemSize
Output: $S_{curr}$
$CandidateList_{admissible}$ $\leftarrow$ GetAdmissibleMoves(CandidateList)
$CandidateList_{tabu}$ $\leftarrow$ CandidateList – $CandidateList_{admissible}$
If (Size($CandidateList_{admissible}$) < 2)
ProhibitionPeriod $\leftarrow$ ProblemSize – 2
$ProhibitionPeriod_{t}$ $\leftarrow$ $Iteration_{i}$
End
$S_{curr}$ $\leftarrow$ GetBest($CandidateList_{admissible}$)
$Sbest_{tabu}$ $\leftarrow$ GetBest($CandidateList_{tabu}$)
If (Cost($Sbest_{tabu}$) < Cost($S_{best}$) $\wedge$ Cost($Sbest_{tabu}$) < Cost($S_{curr}$) )
$S_{curr}$ $\leftarrow$ $Sbest_{tabu}$
End
Return ($S_{curr}$)
Algoritma di penjelasan poin nomor 3 (dipanggil saat GetAdmissibleMoves di algoritma penjelasan no 2)
Output: Tabu
Tabu $\leftarrow$ False
$Scurr_{feature}^{t}$ $\leftarrow$ RetrieveTimeFeatureLastUsed($Scurr_{feature}$)
If ($Scurr_{feature}^{t}$ $\geq$ $Iteration_{curr}$ – ProhibitionPeriod)
Tabu $\leftarrow$ True
End
Return (Tabu)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s