Tabu Search — Metaheuristik Pencarian Lokal
- Diperkenalkan oleh
- Fred Glover
- Tahun
- 1989
- Jenis
- Local-search metaheuristic
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Tabu Search adalah metaheuristik pencarian lokal yang diperkenalkan oleh Fred Glover pada tahun 1989 yang menggunakan daftar tabu — memori jangka pendek dari solusi yang baru saja dikunjungi — untuk mencegah siklus dan keluar dari optimum lokal. Dengan secara eksplisit melarang pergerakan yang membalikkan keputusan terbaru, algoritma ini menjelajahi ruang pencarian secara lebih luas dan, melalui struktur memori jangka panjang seperti kriteria aspirasi, bertujuan untuk mendekati optimum global bahkan pada masalah kombinatorial yang besar dan kompleks.
Intuisi di balik metode
Bayangkan menavigasi lanskap pegunungan dalam kegelapan, mencoba menemukan puncak tertinggi. Pendaki pencarian lokal sederhana selalu melangkah ke atas dan terjebak di bukit terdekat yang dicapainya. Tabu Search membawa buku catatan tempat-tempat yang baru saja dikunjungi dan menolak untuk kembali ke sana, bahkan jika kembali tampaknya menggoda. Amnesia yang dipaksakan tentang pergerakan terbaru ini memaksa pencarian keluar dari jalan buntu dan ke wilayah yang belum dijelajahi, memungkinkannya untuk akhirnya menemukan tanah yang jauh lebih tinggi daripada yang pernah bisa dilakukan oleh pencarian lokal biasa.
Sejarah
Tabu Search diperkenalkan oleh Fred Glover dalam makalah penting tahun 1989 di ORSA Journal on Computing, di mana ia disajikan sebagai strategi untuk memandu pencarian lokal dengan memanfaatkan memori pergerakan masa lalu. Ide-ide dasar dikonsolidasikan dan diperluas dalam monograf Springer tahun 1997 oleh Glover dan Laguna, yang menetapkan daftar tabu jangka pendek kanonik, kriteria aspirasi, dan strategi diversifikasi dan intensifikasi jangka panjang yang tetap menjadi pusat metode ini hingga saat ini. Sejak diperkenalkan, Tabu Search telah diterapkan secara ekstensif dalam riset operasi, penjadwalan, logistik, dan desain kombinatorial, dan terus menjadi metaheuristik benchmark standar bersama dengan simulated annealing dan algoritma genetik.
Kapan digunakan
Tabu Search sangat cocok untuk masalah optimasi kombinatorial dan diskrit di mana ruang solusi terlalu besar untuk metode eksak dan struktur masalah memungkinkan lingkungan yang bermakna untuk didefinisikan. Aplikasi tipikal termasuk penjadwalan, perutean, penugasan, dan masalah pengurutan. Ini sangat efektif ketika lanskap pencarian memiliki banyak optimum lokal yang menjebak metode yang lebih sederhana. Ini tidak memerlukan fungsi tujuan untuk dapat dibedakan atau kontinu. Definisi lingkungan dan masa berlaku tabu harus disesuaikan dengan hati-hati dengan masalah tertentu; lingkungan yang dipilih dengan buruk atau masa berlaku yang terlalu pendek atau terlalu lama dapat menurunkan kinerja secara signifikan. Setidaknya beberapa ratus — dan idealnya lebih dari seribu — iterasi diperlukan agar pencarian dapat menjelajahi ruang secara memadai.
Batasan dan pertimbangan
- Kinerja sensitif terhadap definisi lingkungan dan masa berlaku tabu; pilihan yang buruk dapat menjebak pencarian atau membuatnya berputar meskipun ada mekanisme tabu.
- Memerlukan anggaran iterasi minimum — biasanya lebih dari 1.000 iterasi — untuk menjelajahi lingkungan secara memadai; dengan terlalu sedikit iterasi, hasilnya tidak lebih baik daripada pencarian lokal sederhana.
- Daftar tabu menyimpan atribut pergerakan daripada solusi lengkap, sehingga kriteria aspirasi diperlukan untuk mencegah pemblokiran pergerakan yang benar-benar baik secara tidak sengaja.
- Berbeda dengan pemecah eksak, Tabu Search tidak menawarkan jaminan optimalitas dan kualitas hasil dapat bervariasi antar eksekusi jika solusi awal atau lingkungan bersifat stokastik.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Keluar dari optimum lokal melalui mekanisme tabu tanpa memerlukan informasi gradien.
- Dapat diterapkan pada masalah kombinatorial, tipe campuran, dan bahkan kontinu — tidak mengasumsikan normalitas atau properti distribusi apa pun.
- Menggabungkan memori pada berbagai skala waktu (daftar tabu jangka pendek, diversifikasi/intensifikasi jangka panjang) memungkinkan eksplorasi ruang pencarian yang terstruktur.
- Sering menemukan solusi berkualitas tinggi dengan anggaran komputasi yang relatif sederhana dibandingkan dengan metode eksak pada instance besar.
Penerapan
- Penjadwalan job-shop dan flow-shop — mengoptimalkan urutan operasi untuk meminimalkan makespan atau keterlambatan.
- Perutean kendaraan — menemukan rute pengiriman yang efisien tunduk pada batasan kapasitas dan jendela waktu.
- Penugasan dan lokasi fasilitas — menugaskan tugas ke sumber daya atau melokasi fasilitas untuk meminimalkan biaya.
- Pewarnaan graf, desain jaringan, dan telekomunikasi — memecahkan masalah optimasi struktural diskrit.
- Pemilihan fitur dan pencarian hyperparameter — menjelajahi ruang konfigurasi diskrit dalam pipeline machine learning.
Cara kerjanya
Cara kerjanya
Pencarian dimulai dari solusi kandidat awal, yang dapat dibangun secara acak atau dengan heuristik serakah. Daftar tabu diatur sebagai antrean antrean dengan panjang tetap yang kosong, dan solusi terbaik yang ditemukan sejauh ini dicatat. Struktur lingkungan — aturan yang mendefinisikan solusi mana yang berjarak satu langkah dari solusi saat ini — harus didefinisikan dengan cara yang bermakna untuk masalah tertentu.
Dari solusi saat ini, semua pergerakan di lingkungan yang ditentukan dihasilkan dan dievaluasi terhadap fungsi tujuan. Setiap pergerakan sesuai dengan gangguan kecil, seperti menukar dua elemen dalam urutan atau membalik variabel biner. Lingkungan harus cukup kaya untuk memungkinkan eksplorasi yang bermakna tetapi cukup kecil untuk dapat dikelola dalam setiap iterasi.
Setiap pergerakan kandidat diuji terhadap daftar tabu. Jika pergerakan — atau atribut yang mengkarakterisasinya — muncul di daftar, pergerakan tersebut diklasifikasikan sebagai tabu dan dilarang, kecuali jika memenuhi kriteria aspirasi: biasanya, jika solusi yang dihasilkan akan lebih baik daripada solusi terbaik yang ditemukan sejauh ini, status tabu akan dibatalkan dan pergerakan diizinkan. Mekanisme aspirasi ini memberikan fleksibilitas algoritma tanpa meninggalkan disiplin anti-siklusnya.
Di antara semua pergerakan non-tabu (dan pergerakan tabu apa pun yang melewati kriteria aspirasi), pergerakan berkinerja terbaik dipilih dan dieksekusi, bahkan jika itu memperburuk nilai tujuan. Kesediaan untuk menerima penurunan inilah yang memungkinkan algoritma untuk keluar dari optimum lokal, yang merupakan ciri khas Tabu Search dibandingkan dengan pendakian bukit sederhana.
Setelah pergerakan dieksekusi, daftar tabu diperbarui dengan menambahkan kebalikan dari pergerakan yang baru saja dilakukan (atau atribut yang mengkarakterisasinya), dan entri tertua dihapus jika daftar penuh, mempertahankan panjang tetapnya — masa berlaku tabu. Jika solusi baru lebih baik daripada solusi terbaik yang tercatat, solusi terbaik diperbarui. Struktur memori jangka panjang opsional dapat melacak frekuensi atau kekinian solusi untuk memandu diversifikasi ke wilayah yang kurang dikunjungi atau intensifikasi di sekitar wilayah yang menjanjikan.
Algoritma terus beriterasi hingga kriteria penghentian terpenuhi: jumlah maksimum iterasi, nilai tujuan target, atau jumlah iterasi tetap tanpa peningkatan. Solusi terbaik yang ditemukan sepanjang seluruh pencarian dikembalikan sebagai hasil. Memilih anggaran iterasi yang memadai sangat penting — terlalu sedikit iterasi mencegah eksplorasi lingkungan yang cukup.
Kesalahan umum
- Menetapkan masa berlaku tabu terlalu pendek memungkinkan siklus berulang, menggagalkan tujuan mekanisme tabu; masa berlaku harus disesuaikan untuk ukuran masalah.
- Menetapkan masa berlaku terlalu lama terlalu membatasi pencarian dan mencegah algoritma mengunjungi kembali wilayah yang mungkin berisi peningkatan.
- Menjalankan kurang dari sekitar 1.000 iterasi berarti pencarian belum cukup menjelajahi lingkungan — jika komputasi terbatas, gunakan simulated annealing yang dapat menghasilkan hasil yang berguna lebih cepat dengan lebih sedikit iterasi.
- Menggunakan lingkungan yang terlalu sempit (misalnya, hanya pergerakan tukar tunggal pada struktur kompleks) mengarah pada pencarian yang dangkal; pastikan lingkungan cukup kaya untuk menghubungkan semua wilayah yang menjanjikan dari ruang solusi.
- Mengabaikan kriteria aspirasi dapat secara permanen memblokir pergerakan ke optimum global jika pergerakan tersebut kebetulan tabu; selalu terapkan setidaknya pembatalan status tabu solusi terbaik standar.
Pertanyaan yang sering diajukan
Bagaimana Tabu Search berbeda dari simulated annealing?
Kedua metode menerima pergerakan yang memburuk untuk keluar dari optimum lokal, tetapi mereka berbeda dalam mekanisme. Simulated annealing menerima pergerakan yang lebih buruk secara probabilistik, dipandu oleh parameter suhu pendinginan. Tabu Search menerima pergerakan non-tabu terbaik yang tersedia secara deterministik, dipandu oleh memori eksplisit dari pergerakan terbaru. Tabu Search umumnya lebih efektif pada masalah kombinatorial terstruktur; simulated annealing bisa lebih mudah disesuaikan pada masalah dengan lanskap kontinu atau mendekati kontinu dan lebih disukai ketika anggaran iterasi kecil (di bawah sekitar 1.000 iterasi).
Berapa lama daftar tabu seharusnya?
Masa berlaku tabu — jumlah iterasi pergerakan tetap dilarang — bergantung pada masalah. Titik awal yang umum dikutip adalah masa berlaku yang sebanding dengan akar kuadrat dari ukuran masalah, tetapi ini harus disesuaikan secara empiris. Masa berlaku yang terlalu pendek memungkinkan siklus; masa berlaku yang terlalu lama terlalu membatasi pencarian. Strategi masa berlaku adaptif atau acak dapat mengurangi sensitivitas terhadap pilihan ini.
Apakah Tabu Search menjamin penemuan optimum global?
Tidak. Tabu Search adalah metaheuristik dan tidak memberikan jaminan optimalitas. Tujuannya adalah untuk menemukan solusi berkualitas tinggi secara efisien, tetapi hasilnya bergantung pada struktur lingkungan, masa berlaku, jumlah iterasi, dan solusi awal. Untuk jaminan optimalitas, metode eksak seperti pemrograman integer diperlukan, meskipun metode eksak mungkin tidak layak secara komputasi untuk instance besar.
Apa itu kriteria aspirasi dan mengapa itu diperlukan?
Kriteria aspirasi adalah aturan yang membatalkan status tabu suatu pergerakan dalam kondisi khusus. Kriteria yang paling umum adalah: jika mengeksekusi pergerakan tabu akan menghasilkan solusi yang lebih baik daripada solusi terbaik yang ditemukan sejauh ini, batasan tabu dicabut dan pergerakan diizinkan. Tanpa pembatalan ini, mekanisme tabu dapat secara permanen memblokir jalur ke optimum global jika jalur tersebut melewati pergerakan yang baru saja dikunjungi.
Metode terkait
Sumber
Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Buka referensi publikasiDisalin.Glover, F. & Laguna, M. (1997). Tabu Search. Springer.
ISBN: 9780792349907Disalin.