Tabu Search – Introduction

Tabu search (TS) pertama kali diperkenalkan oleh Glover sekitar tahun 1986. Glover menyatakan bahwa TS adalah salah satu prosedur metaheuristik tingkat tinggi untuk penyelesaian permasalahan optimisasi kombinatorial. TS ini dirancang untuk mengarahkan metode-metode lain (atau komponen proses TS itu sendiri) untuk keluar atau menghindari dari masuk dalam solusi optimal yang bersifat lokal. Kemampuan TS dalam menghasilkan solusi yang mendekati optimal telah dimanfaatkan dalam beragam permasalahan klasik dan parktis dari berbagai bidang mulai bidang penjadwalan hingga bidang telekomunikasi .

Glover mengatakan bahwa prosedur TS ini dapat ditemukan dalam tiga pola (scheme) utama. Pola pertama adalah adanya penggunaan struktur memori berbasiskan atribut-atribut fleksibel yang dirancang untuk membolehkan sebuah kriteria evaluasi dan hasil pencarian di masa lalu dieksploitasi lebih mendalam. Pola ini menjadikan TS berbeda dengan aplikasi lain yang menggunakan struktur memori yang rigid (kaku) atau tanpa menggunakan struktur memori (seperti simulated annealing). Pola kedua adalah penggunaan mekanisme atau kondisi yang dapat membatasi atau membebaskan suatu proses pencarian yang sedang berlangsung. Pola kedua ini dikenal sebagai mekanisme tabu restriction dan aspiration criteria. Pola ketiga adalah pelibatan suatu fungsi memori dengan rentang waktu yang berbeda yakni berupa memori jangka pendek (short term memory) dan memori jangka panjang (long term memory) untuk menjalankan strategi intensifikasi dan diversifikasi dalam proses pencarian solusi. Strategi intensifikasi adalah strategi pencarian yang mengarahkan/ mengfokuskan pencarian pada suatu area tertentu, sedangkan strategi diversifikasi adalah strategi pencarian yang mengarahkan pencarian pada area baru.

Skema umum TS disajikan pada gambar di bawah ini. Pemilihan kandidat terbaik didasarkan nilai fungsi tujuan. Pemeriksaan nilai fungsi tujuan lebih didahulukan sebelum pemeriksaan status tabu. Apabila nilai fungsi tujuan sebuah kandidat lebih baik dari yang lain, maka kandidat tersebut berpotensi untuk diterima sehingga perlu diperiksa status tabunya. Urutan pemeriksaan nilai fungsi tujuan kemudian status tabu memberikan kemungkinan proses penyelesaian program yang lebih cepat. Pemilihan kandidat solusi terbaik yang dilakukan oleh TS menggunakan prinsip global-best strategy (GB) bukan first–best strategy (FB). GB adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini dengan solusi terbaik yang ada pada neighborhood. Adapun FB adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini secara langsung jika solusi yang lebih baik ditemukan.

Skema Algoritma Tabu Search

Gendreau et.al (1998) menyatakan bahwa TS adalah pendekatan yang paling efektif untuk pemecahan masalah penentuan rute kendaraan. Kelebihan TS terletak pada struktur memori yang fleksibel. Struktur memori itu akan membolehkan pencarian terus dilakukan meskipun solusi yang diperoleh saat ini tidak ada yang lebih baik dari solusi terbaik yang telah diperoleh. Struktur memori tersebut juga mampu menjaga agar proses pencarian tidak jatuh pada lokal optimal yang pernah muncul pada pencarian sebelumnya. Adanya strukur memori fleksibel ini yang membedakan TS dengan branch and bound yang menggunakan struktur memori kaku atau simulated annealing yang tidak menggunakan struktur memori (Glover, 1990)

TS umumnya tidak menggunakan pembentukan kandidat solusi secara acak sebagaimana simulated annealing dan genetic algorithm. Pemilihan kandidat solusi dalam TS juga tidak dilakukan secara probabilistik sebagaimana ant colony system, simulated annealing dan genetic algorithm. Karakteristik ini menjadikan solusi yang dihasilkan TS akan sama setiap kali dilakukan proses pencarian solusi terhadap suatu permasalahan. Karakterstik ini juga menjadi salah satu keunggulan TS dibanding ant colony system, simulated annealing dan genetic algorithm.

Sumber: Glover (1990) dan Gendreau et.al (1998)