Stochastic Tabu Search — Metaheuristik Acak dengan Memori
- Diperkenalkan oleh
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- Tahun
- 1990s
- Jenis
- Stochastic metaheuristic optimizer
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Stochastic Tabu Search (STS) adalah perluasan dari Tabu Search klasik yang memperkenalkan keacakan ke dalam fase eksplorasi lingkungan dan pemilihan langkah.
Dengan menggabungkan memori tabu — yang melarang solusi yang baru saja dikunjungi — dengan penerimaan probabilistik atau pengambilan sampel kandidat acak, STS lebih efektif dalam keluar dari optimum lokal dan menjelajahi lanskap solusi yang bergelombang yang mungkin gagal dilalui oleh TS deterministik.
Intuisi di balik metode
Tabu Search klasik menavigasi ruang solusi dengan selalu bergerak ke tetangga terbaik yang diizinkan, menggunakan memori jangka pendek (daftar tabu) untuk mencegah siklus. Namun, dalam praktiknya, langkah terbaik yang diizinkan masih dapat menjebak algoritma di suatu wilayah lanskap. Stochastic Tabu Search menyuntikkan keacakan yang terkontrol: langkah berikutnya dipilih secara probabilistik dari sekumpulan kandidat tetangga daripada secara serakah, dan gangguan acak sesekali diperkenalkan untuk mendiversifikasi pencarian. Hal ini mempertahankan disiplin TS yang dipandu memori sambil menambahkan kekuatan eksplorasi yang tidak dimiliki oleh penurunan deterministik murni.
Sejarah
Tabu Search secara formal diperkenalkan oleh Fred Glover pada tahun 1986 dan diuraikan dalam makalah penting melalui 1989-1990. Perluasan stokastik muncul pada tahun 1990-an ketika para peneliti menyadari bahwa evaluasi lingkungan deterministik adalah hambatan dalam masalah skala besar. Pengambilan sampel kandidat acak, penerimaan langkah probabilistik, dan injeksi noise dimasukkan untuk meningkatkan diversifikasi, melahirkan apa yang secara luas disebut Stochastic Tabu Search. Teknik ini diterapkan secara luas dalam riset operasi, desain teknik, dan optimasi hyperparameter machine learning.
Kapan digunakan
Gunakan Stochastic Tabu Search saat memecahkan masalah optimasi black-box kombinatorial atau kontinu dengan lanskap bergelombang dan multimodal di mana pencarian lokal deterministik secara konsisten terjebak (misalnya, penjadwalan, perutean, pemilihan fitur). Ini sangat berharga ketika evaluasi lingkungan penuh mahal secara komputasi, membuat pengambilan sampel acak menjadi perlu. JANGAN gunakan STS ketika masalahnya cembung atau unimodal — metode berbasis gradien atau eksak lebih cepat dan optimal. Hindari jika Anda membutuhkan optimalitas global yang terjamin, karena STS tidak menawarkan jaminan konvergensi selain solusi terbaik yang ditemukan secara heuristik. Juga hindari ketika fungsi tujuan murah untuk dievaluasi sepenuhnya dan TS deterministik dengan pencarian lingkungan menyeluruh layak dilakukan.
Batasan dan pertimbangan
- Tidak ada jaminan teoretis untuk menemukan optimum global; kualitas solusi sangat bergantung pada pengaturan parameter.
- Masa berlaku tabu dan ukuran daftar kandidat memerlukan penyesuaian spesifik masalah; pilihan yang buruk mengarah pada konvergensi dini atau kemajuan yang lambat.
- Jalankan stokastik tidak dapat direproduksi tanpa seed acak yang tetap, mempersulit perbandingan dan audit.
- Overhead memori tumbuh dengan ukuran daftar tabu; representasi tabu berbasis atribut diperlukan untuk ruang solusi besar.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Keluar dari optimum lokal lebih efektif daripada Tabu Search deterministik dengan menggabungkan memori dengan eksplorasi probabilistik.
- Skala ke struktur lingkungan besar dengan mengambil sampel kandidat, mengurangi biaya komputasi per iterasi.
- Memori tabu mencegah siklus, mode kegagalan umum dari metode stokastik murni seperti hill climbing restart acak.
- Kerangka kerja fleksibel: probabilitas gangguan dan masa berlaku tabu dapat disesuaikan untuk menyeimbangkan intensifikasi dan diversifikasi.
- Dapat diterapkan pada masalah kombinatorial (TSP, penjadwalan) dan optimasi kontinu dengan adaptasi minor.
Penerapan
- Perutean kendaraan dan optimasi logistik di bawah permintaan yang tidak pasti
- Penjadwalan job-shop dan open-shop dengan waktu pemrosesan stokastik
- Pemilihan fitur dalam dataset machine learning berdimensi tinggi
- Desain jaringan dan optimasi topologi
- Optimasi portofolio dengan kendala pemilihan aset kombinatorial
- Penyetelan hyper-parameter untuk model simulasi kompleks
Cara kerjanya
Cara kerjanya
Hasilkan solusi awal x0 (secara acak atau heuristik). Atur daftar tabu T ke kosong, tentukan masa berlaku tabu tau, batas iterasi I_max, dan parameter stokastik (misalnya, ukuran daftar kandidat k, probabilitas gangguan p_perturb).
Pada setiap iterasi, secara acak ambil sampel subset N_s dari lingkungan penuh N(x_current) daripada mengevaluasi semua tetangga. Ini mengurangi biaya per iterasi dan memperkenalkan stokastisitas ke dalam wilayah mana dari ruang yang dieksplorasi.
Pilih solusi berikutnya x_next dari N_s: baik (a) pilih kandidat non-tabu terbaik dengan probabilitas 1-p_perturb, atau (b) dengan probabilitas p_perturb pilih kandidat non-tabu acak untuk diversifikasi. Kriteria aspirasi dapat mengesampingkan status tabu jika x_next meningkatkan solusi terbaik yang diketahui.
Tambahkan x_current (atau atribut langkah) ke daftar tabu T. Hapus entri tertua jika |T| > tau. Perbarui solusi terbaik insentif x_best jika f(x_next) < f(x_best).
Ulangi neighborhood_sampling hingga tabu_update hingga I_max iterasi tercapai, nilai tujuan target terpenuhi, atau tidak ada peningkatan yang terjadi selama jendela kesabaran. Kembalikan x_best sebagai solusi akhir.
Kesalahan umum
- Menetapkan masa berlaku tabu terlalu pendek memungkinkan siklus meskipun ada daftar tabu; terlalu lama memblokir wilayah yang menjanjikan tanpa perlu.
- Menggunakan daftar kandidat yang terlalu kecil (pengambilan sampel agresif) dapat membuat pencarian secara konsisten melewatkan tetangga yang baik.
- Mengabaikan kriteria aspirasi menyebabkan algoritma menolak langkah yang secara global meningkatkan yang kebetulan tabu.
- Melaporkan hanya satu kali jalan tanpa restart atau seed berganda memberikan gambaran yang menyesatkan tentang kualitas solusi tipikal.
- Mencampuradukkan Stochastic Tabu Search dengan Simulated Annealing: keduanya stokastik tetapi berbeda secara fundamental — STS menggunakan memori eksplisit sedangkan SA menggunakan penerimaan probabilistik berbasis suhu tanpa memori.
Pertanyaan yang sering diajukan
Bagaimana Stochastic Tabu Search berbeda dari Simulated Annealing?
Keduanya adalah metaheuristik stokastik, tetapi STS menggunakan memori tabu eksplisit untuk melarang langkah yang baru saja dikunjungi, mencegah siklus. SA tidak memiliki memori — ia menerima solusi yang lebih buruk dengan probabilitas yang menurun seiring waktu (jadwal suhu). STS umumnya lebih kuat pada masalah kombinatorial di mana mengunjungi kembali langkah adalah bahaya yang jelas.
Berapa iterasi (I_max) yang harus saya jalankan?
Tidak ada aturan universal. Praktik umum adalah menjalankan beberapa percobaan independen (misalnya, 10-30 restart) dengan anggaran yang sebanding dengan ukuran masalah, kemudian melaporkan hasil terbaik dan rata-rata. Untuk perbandingan, sesuaikan total anggaran evaluasi fungsi yang digunakan oleh metode pesaing.
Bisakah Stochastic Tabu Search menangani variabel kontinu?
Ya, tetapi memerlukan pendefinisian lingkungan kontinu (misalnya, gangguan Gaussian di sekitar solusi saat ini) dan atribut yang sesuai untuk daftar tabu (misalnya, wilayah atau arah). Sebagian besar literatur STS menargetkan masalah kombinatorial; untuk ruang kontinu, Differential Evolution atau CMA-ES seringkali merupakan alternatif yang lebih alami.
Apa peran kriteria aspirasi?
Kriteria aspirasi mengesampingkan status tabu dari suatu langkah jika menerimanya menghasilkan solusi yang lebih baik daripada yang terbaik yang ditemukan sejauh ini. Tanpa aspirasi, algoritma mungkin secara permanen menolak langkah yang secara global meningkatkan yang kebetulan tabu, sangat membatasi kualitas solusi.
Haruskah saya memperbaiki seed acak untuk reproduktibilitas?
Ya, perbaiki seed saat melaporkan hasil dalam penelitian untuk memastikan reproduktibilitas. Dalam praktiknya, jalankan dengan beberapa seed dan laporkan statistik (rata-rata, terbaik, standar deviasi) untuk memberikan gambaran yang andal tentang kinerja algoritma di seluruh lanskap stokastik.
Metode terkait
Sumber
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Buka referensi DOIDisalin.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
Buka referensi DOIDisalin.