Pencarian tabu

Pencarian Tabu (bahasa Inggris: Tabu Search; TS) adalah metode pencarian metaheuristik yang menggunakan metode pencarian lokal untuk optimasi matematis. Algoritma ini dibuat oleh Fred W. Glover pada tahun 1986 dan diformalisasi pada tahun 1989.

Pencarian lokal (ketetanggaan) mengambil solusi potensial terhadap suatu masalah dan memeriksa tetangga terdekatnya (yaitu, solusi yang serupa kecuali untuk beberapa detail kecil) dengan harapan menemukan solusi yang lebih baik. Metode pencarian lokal seringkali terjebak di daerah suboptimal atau dataran tinggi dengan banyak solusi yang sama-sama cocok.

Pencarian Tabu meningkatkan kinerja pencarian lokal dengan melonggarkan aturan dasarnya. Pertama, pada setiap langkah, pergerakan yang memburuk dapat diterima jika tidak ada pergerakan yang lebih baik (seperti ketika pencarian terhenti pada minimum lokal yang ketat). Selain itu, larangan (sehingga, istilah tabu) diperkenalkan untuk mencegah pencarian kembali ke solusi yang telah dikunjungi sebelumnya.

Implementasi pencarian tabu menggunakan struktur memori yang menggambarkan solusi yang dikunjungi atau seperangkat aturan yang disediakan pengguna. Jika suatu solusi potensial telah dikunjungi sebelumnya dalam jangka waktu pendek tertentu atau jika telah melanggar suatu aturan, maka solusi tersebut ditandai sebagai “tabu” (terlarang) sehingga algoritma tidak mempertimbangkan kemungkinan tersebut berulang kali.

Latar belakang

Kata tabu berasal dari bahasa Tonga yang berarti benda yang tidak boleh disentuh karena bersifat suci.

Pencarian Tabu adalah algoritma metaheuristik yang dapat digunakan untuk menyelesaikan masalah optimasi kombinatorial (masalah yang menginginkan pengurutan dan pemilihan opsi yang optimal).

Penerapan TS saat ini mencakup bidang perencanaan sumber daya, telekomunikasi, desain VLSI, analisis keuangan, penjadwalan, perencanaan ruang, distribusi energi, teknik molekuler, logistik, klasifikasi pola, manufaktur fleksibel, pengelolaan limbah, eksplorasi mineral, analisis biomedis, konservasi lingkungan dan puluhan lainnya. Dalam beberapa tahun terakhir, jurnal di berbagai bidang telah menerbitkan artikel tutorial dan studi komputasi yang mendokumentasikan keberhasilan pencarian tabu dalam memperluas batasan masalah yang dapat ditangani secara efektif—menghasilkan solusi yang kualitasnya sering kali jauh melampaui metode yang diterapkan sebelumnya. Daftar penerapan yang komprehensif, termasuk deskripsi ringkasan keunggulan yang dicapai dari implementasi praktis, dapat ditemukan pada .

Deskripsi dasar

Pencarian Tabu menggunakan prosedur pencarian lokal atau ketetanggaan untuk berpindah secara iteratif dari satu solusi potensial $x$ menuju solusi yang lebih baik $x'$ di ketetanggaan $x$, hingga beberapa kriteria penghentian terpenuhi (umumnya, batas jumlah percobaan atau ambang batas skor). Prosedur pencarian lokal sering kali terhenti di area yang skornya buruk atau di area yang skornya tidak berubah. Untuk menghindari jebakan ini dan menjelajahi wilayah ruang pencarian yang belum dijelajahi oleh prosedur pencarian lokal lainnya, pencarian tabu dengan hati-hati mengeksplorasi lingkungan setiap solusi seiring kemajuan pencarian. Solusi yang diterima di lingkungan baru, $N^{*}(x)$, ditentukan melalui penggunaan struktur memori. Dengan menggunakan struktur memori ini, pencarian dilanjutkan dengan berpindah secara iteratif dari solusi saat ini $x$ menuju solusi yang lebih baik $x'$ di dalam $N^{*}(x)$.

Pencarian Tabu memiliki beberapa kesamaan dengan simulated annealing, karena keduanya melibatkan kemungkinan pergerakan menurun. Faktanya, simulated annealing dapat dilihat sebagai bentuk khusus dari TS, yang kita menggunakan "graduated tenure", yaitu suatu perpindahan menjadi tabu dengan probabilitas tertentu.

Struktur memori ini membentuk apa yang dikenal sebagai daftar tabu (tabu list), seperangkat aturan dan solusi terlarang yang digunakan untuk menyaring solusi mana yang akan diterima di ketetanggaan tersebut. $N^{*}(x)$ untuk dieksplorasi dengan pencarian. Dalam bentuknya yang paling sederhana, daftar tabu adalah serangkaian solusi jangka pendek yang telah dikunjungi pada masa lalu (kurang dari $n$ iterasi yang lalu, dengan $n$ adalah jumlah solusi sebelumnya yang disimpan — disebut juga tabu tenure). Lebih umum lagi, daftar tabu terdiri dari solusi-solusi yang telah diubah melalui proses perpindahan dari satu solusi ke solusi lainnya. Untuk memudahkan deskripsi, daftar tabu adalah untuk memahami “solusi” yang akan dikodekan dan direpresentasikan oleh atribut-atribut tersebut.

Jenis memori

Struktur memori yang digunakan dalam pencarian tabu secara kasar dapat dibagi menjadi tiga kategori:

• Jangka pendek: Daftar solusi yang baru-baru ini dipertimbangkan. Jika suatu solusi potensial muncul dalam daftar tabu, maka solusi tersebut tidak dapat ditinjau kembali sampai mencapai titik kadaluwarsa.
• Jangka menengah: Aturan intensifikasi yang dimaksudkan untuk membiaskan pencarian pada area pencarian yang menjanjikan.
• Jangka panjang: Aturan diversifikasi yang mendorong pencarian ke wilayah baru (yaitu, mengenai pengaturan ulang ketika pencarian terhenti di dataran tinggi atau jalan buntu yang suboptimal).

Memori jangka pendek, jangka menengah, dan jangka panjang dapat saling tumpang tindih dalam praktiknya. Dalam kategori ini, memori dapat dibedakan lebih lanjut berdasarkan ukuran, seperti frekuensi dan dampak dari perubahan yang diambil. Salah satu contoh struktur memori jangka menengah adalah struktur memori yang melarang atau mendorong solusi yang mengandung atribut tertentu (misalnya, solusi yang menyertakan nilai yang tidak diinginkan atau diinginkan untuk variabel tertentu) atau struktur memori yang mencegah atau mengarahkan pergerakan tertentu (misalnya, berdasarkan memori frekuensi yang diterapkan pada solusi yang memiliki kesamaan dengan solusi yang tidak menarik atau menarik yang ditemukan di masa lalu). Dalam memori jangka pendek, atribut yang dipilih dalam solusi yang baru saja dikunjungi diberi label "tabu-aktif". Solusi yang mengandung elemen tabu-aktif dilarang. Kriteria aspek digunakan untuk menimpa status tabu dari sebuah solusi, sehingga memasukkan solusi yang dikecualikan ke dalam himpunan yang diperbolehkan (asalkan solusi tersebut "cukup baik" menurut ukuran kualitas atau keragaman). Kriteria aspek yang sederhana dan umum digunakan dengan mengizinkan solusi yang lebih baik dari solusi terbaik yang saat ini diketahui.

Memori jangka pendek saja mungkin cukup untuk mencapai solusi yang lebih unggul daripada yang ditemukan dengan metode pencarian lokal konvensional, tetapi struktur jangka menengah dan jangka panjang sering kali diperlukan untuk memecahkan masalah yang lebih sulit. Pencarian Tabu sering kali dibandingkan dengan metode metaheuristik lainnya—seperti simulated annealing, algoritma genetika, algoritma semut, optimasi pencarian reaktif, penelusuran lokal terpandu, atau penelusuran adaptif acak serakah . Selain itu, pencarian tabu terkadang dikombinasikan dengan metaheuristik lain untuk menciptakan metode hibrid. Hibrid (campuran) pencarian tabu yang paling umum muncul dengan menggabungkan TS dengan scatter search, sebuah kelas prosedur berbasis populasi yang memiliki kesamaan dengan pencarian tabu, dan sering digunakan dalam memecahkan masalah optimasi non-linier yang besar.

Pseudocode

Kode semu berikut menyajikan versi sederhana dari algoritma pencarian tabu seperti yang dijelaskan di atas. Implementasi ini memiliki memori jangka pendek yang belum sempurna, tetapi tidak mengandung struktur memori jangka menengah atau jangka panjang. Istilah "kecocokan" atau fitness mengacu pada evaluasi kandidat solusi, sebagaimana diwujudkan dalam fungsi objektif untuk optimasi matematis.

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidateFitness ← -∞
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) 
            and (fitness(sCandidate) > bestCandidateFitness) )
            bestCandidate ← sCandidate
            bestCandidateFitness ← fitness(bestCandidate)
        end
    end
    if (bestCandidateFitness is -∞)
        break;
    end
    if (bestCandidateFitness > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

Baris 1-4 mewakili beberapa pengaturan awal, masing-masing membuat solusi awal (mungkin dipilih secara acak), menetapkan solusi awal tersebut sebagai yang paling baik dilihat hingga saat ini, dan menginisialisasi daftar tabu dengan solusi awal ini. Dalam contoh ini, daftar tabu hanyalah sebuah struktur memori jangka pendek yang akan berisi catatan elemen state yang dikunjungi.

Perulangan algoritmik inti dimulai pada baris 5. Perulangan ini akan terus mencari solusi optimal hingga kondisi penghentian yang ditentukan pengguna terpenuhi (dua contoh kondisi tersebut adalah batas waktu sederhana atau ambang batas skor fitness). Solusi tetangganya diperiksa untuk elemen tabu di baris 9. Selain itu, algoritma ini melacak solusi terbaik di lingkungan tersebut, yaitu bukan tabu.

Fungsi kecocokan umumnya merupakan fungsi matematika, yang mengembalikan skor atau aspek kriteria yang terpenuhi — misalnya, aspek kriteria dapat dianggap sebagai ruang pencarian baru yang ditemukan). Jika kandidat lokal terbaik memiliki nilai kecocokan yang lebih tinggi dibandingkan kandidat terbaik saat ini (baris 13), maka kandidat tersebut ditetapkan sebagai yang terbaik baru (baris 14). Kandidat lokal terbaik selalu ditambahkan ke daftar tabu (baris 16) dan jika daftar tabu penuh (baris 17), beberapa elemen akan dibiarkan kedaluwarsa (baris 18). Umumnya, elemen kedaluwarsa dari daftar dalam urutan yang sama dengan penambahannya. Prosedur ini akan memilih kandidat lokal terbaik (walaupun memiliki kecocokan lebih buruk daripada sBest) untuk menghindari optimal lokal.

Proses ini berlanjut hingga kriteria penghentian yang ditentukan pengguna terpenuhi, dan pada titik tersebut, solusi terbaik yang terlihat selama proses pencarian dikembalikan (baris 21).

Contoh: masalah penjual keliling

Masalah penjual keliling (TSP) terkadang digunakan untuk menunjukkan fungsionalitas pencarian tabu. Masalah ini menimbulkan pertanyaan sederhana: berdasarkan daftar kota, rute terpendek apa yang dapat mengunjungi setiap kota? Misalnya, jika kota A dan kota B bersebelahan, sedangkan kota C semakin jauh, total jarak yang ditempuh akan lebih pendek jika kota A dan B dikunjungi satu demi satu sebelum mengunjungi kota C. Karena menemukan solusi optimal adalah NP-hard, metode perkiraan berbasis heuristik (seperti pencarian lokal) berguna untuk merancang solusi yang mendekati optimal. Untuk mendapatkan solusi TSP yang baik, penting untuk memanfaatkan struktur grafik. Nilai dari eksploitasi struktur masalah adalah tema yang berulang dalam metode metaheuristik, dan pencarian tabu sangat cocok untuk ini. Kelas strategi yang terkait dengan pencarian tabu yang disebut metode rantai ejeksi telah memungkinkan untuk memperoleh solusi TSP berkualitas tinggi secara efisien.

Di sisi lain, pencarian tabu sederhana dapat digunakan untuk menemukan solusi yang memuaskan untuk masalah penjual keliling (yaitu, solusi yang memenuhi kriteria kecukupan, walaupun tidak dengan kualitas tinggi yang diperoleh dengan memanfaatkan struktur graf). Pencarian dimulai dengan solusi awal, yang dapat dihasilkan secara acak atau berdasarkan algoritma tetangga terdekat. Untuk menciptakan solusi baru, urutan dua kota yang dikunjungi dalam solusi potensial ditukar. Total jarak perjalanan antara semua kota digunakan untuk menilai seberapa ideal suatu solusi dibandingkan dengan solusi lainnya. Untuk mencegah siklus – misalnya, berulang kali mengunjungi serangkaian solusi tertentu – dan untuk menghindari terjebak dalam optimal lokal, sebuah solusi ditambahkan ke daftar tabu jika diterima ke dalam lingkungan solusi, $N^{*}(x)$.

Solusi baru dibuat sampai beberapa kriteria penghentian, seperti jumlah iterasi yang berubah-ubah, terpenuhi. Setelah pencarian tabu sederhana berhenti, ia mengembalikan solusi terbaik yang ditemukan selama pelaksanaannya.

Pranala eksternal

• Visualisasi algoritma pencarian Tabu (Applet)
• Konferensi Internasional Metaheuristik (MIC 2011) – Udine
• Komunitas Penelusuran Reaktif
• LION Conference on Learning and Intelligent Optimization techniques