ALGORITMA TABU SEARCH

1.      ALGORITMA TABU SEARCH

Kata tabu atau “taboo” berasal dari bahasa Tongan, suatu bahasa Polinesia yang digunakan oleh suku Aborigin pulau tonga untuk mengindikasikan suatu hal yang tidak boleh “disentuh” karena kesakralannya. Tabu menunjukkan tidak boleh/terlarang untuk dilakukan (penting) yang berkaitan erat dengan memori sosial dari suatu kelompok masyarakat. Menurut kasus Webster, tabu berarti larangan yang dipaksakan oleh kebudayaan sosial sebagai suatu tindakan pencegahan atau sesuatu yang dilarang karena berbahaya. Bahaya yang harus dihindari dalam tabu search adalah penjadwalan yang tidak layak, dan terjebak tanpa ada jalan keluar.

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

Glover mengatakan bahwa prosedur tabu search ini dapat ditemukan dalam tiga pola (scheme) utama. Pola pertama adalah adanya penggunaan struktur memori berbasiskan atribut-atribut fleksibel yang dirancang untuk memperbolehkan sebuah kriteria evaluasi dan hasil pencarian di masa lalu dieksploitasi lebih mendalam. Pola ini menjadikan tabu search 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.

Tabu search adalah sebuah metode optimasi yang berbasis pada local search. Proses pencarian bergerak dari satu solusi ke solusi berikutnya, dengan cara memilih solusi terbaik neighbourhood solusi sekarang (current) yang tidak tergolong ke dalam solusi terlarang (tabu). Ide dasar dari algoritma tabu search adalah mencegah proses pencarian dari local search agar tidak melakukan pencarian ulang pada ruang solusi yang sudah pernah ditelusuri, dengan memanfaatkan suatu struktur memori yang mencatat sebagian jejak proses pencarian yang telah dilakukan.

Struktur memori fundamental dalam tabu search dinamakan tabu list. Tabu list menyimpan atribut dari sebagian move (transisi solusi) yang telah diterapkan pada iterasi-iterasi sebelumnya. Tabu search menggunakan tabu list untuk menolak solusi solusi yang memenuhi atribut tertentu guna mencegah proses pencarian mengalami cycling pada daerah solusi yang sama, dan menuntun proses pencarian menelusuri daerah solusi yang belum dikunjungi. Tanpa menggunakan strategi ini, local search yang sudah menemukan solusi optimum local dapat terjebak pada daerah solusi optimum local tersebut pada iterasi-iterasi berikutnya.

Struktur tabu search menggunakan empat dimensi, terdiri dari recency, frequency, quality, dan influence yang ditunjukkan oleh gambar berikut:

Recency-based dan frequency-based memory saling melengkapi satu sama lain. Dimensi quality berhubungan dengan kemampuan membedakan manfaat solusi yang diperoleh selama proses pencarian. Memory dapat mengidentifikasi elemen yang umum pada solusi yang baik atau pada path yang mengarah pada solusi yang baik. Dimensi influence mempertimbangkan akibat pilihan yang dibuat selama proses pencarian tidak hanya terhadap kualitas maupun pada struktur.

Perekaman solusi secara lengkap dalam sebuah forbidden list dan pengecekan apakah sebuah kandidat solusi tercatat dalam list tersebut merupakan cara yang mahal,baik dari sisi kebutuhan memori maupun kebutuhan waktu komputasi. Jadi, tabu list hanya menyimpan langkah transisi (move) yang merupakan lawan atau kebalikan dari langkah yang telah digunakan dalam iterasi sebelumnya untuk bergerak dari satu solusi ke solusi berikutnya. Dengan kata lain tabu list berisi langkah-langkah yang mengembalikan solusi yang baru ke solusi yang lama.

Pada tiap iterasi, dipilih solusi baru yang merupakan solusi terbaik dalam neighbourhood dan tidak tergolong sebagai tabu. Kualitas solusi baru ini tidak harus lebih baik dari kualitas solusi sekarang. Apabila solusi baru ini memiliki nilai fungsi objektif lebih baik dibandingkan solusi terbaik yang telah dicapai sebelumnya, maka solusi baru ini dicatat sebagai solusi terbaik yang baru. Sebagai tambahan dari tabu list, dikenal adanya kriteria aspirasi, yaitu suatu penanganan khusus terhadap move yang dinilai dapat menghasilkan solusi yang dinilai dapat menghasilkan solusi yang baik namun move tersebut berstatus tabu. Dalam hal ini, jika move tersebut memenuhi kriteria aspirasi yang telah ditetapkan sebelumnya, maka move tersebut dapat digunakan utnuk membentuk solusi berikutnya (status tabu-nya dibatalkan).

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 tabu-nya. Urutan pemeriksaan nilai fungsi tujuan kemudian status tabu memberikan kemungkinan proses penyelesaian program yang lebih cepat. Pemilihan kandidat solusi terbaik yang dilakukan oleh tabu search menggunakan prinsip global-best strategy bukan first-best strategy. global-best strategy adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini dengan solusi terbaik yang ada pada neighborhood. Adapun first-best strategy adalah strategi dimana algoritma akan mengganti solusi terbaik saat ini secara langsung jika solusi yang lebih baik ditemukan.

Algoritma tabu search memiliki kemampuan untuk keluar dari solusi optimum lokal, tetapi tabu search tidak dapat menentukan optimum global. Tabu search harus memiliki batasan maksimum jumlah iterasi dan ukuran tabu list yang ditentukan sendiri oleh individu yang menggunakan metode ini/administrator sistem. Jumlah iterasi yaitu banyaknya iterasi yang akan dilakukan untuk mengeksplorasi berbagai space search area. Semakin besar jumlah maksimum iterasi, semakin besar pula peluang untuk menentukan solusi optimal secara global, namun memerlukan waktu perhitungan yang lama.

Secara garis besar elemen-elemen utama pada tabu search adalah sebagai berikut:

1.      Representasi solusi: setiap solusi feasible pada suatu permasalahan optimasi harus direpresentasikan secara unik.

2.      Fungsi cost: setiap fungsi cost (fungsi tujuan) akan memetakan setiap solusi feasible ke nilai cost-nya.

3.      Neighbourhood (tetangga): suatu fungsi cost akan memetakan setiap solusi feasible S ke solusi-solusi yang lainnya.

4.      Tabu list: suatu list yang berisi T gerakan (move) terakhir.

5.      Jumlah elemen yang harus ada pada suatu solusi.

Hal-hal di atas dapat dikatakan sebagai bahan-bahan dasar dari metode tabu search yang nantinya akan digunakan untuk memecahkan masalah penjadwalan kuliah pada pembahasan selanjutnya.