Skip to content
Kembali ke hasil pencarian

Robust Tabu Search — Metaheuristik berbasis Tabu yang kuat terhadap ketidakpastian

Diperkenalkan oleh
Glover, F. (Tabu Search); robustness extensions by various authors
Tahun
1989 (TS); robust variant ~2000s
Jenis
Metaheuristic with robustness mechanism
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Robust Tabu Search (RTS) memperluas metaheuristik klasik Tabu Search dengan mengevaluasi solusi kandidat tidak hanya berdasarkan nilai objektif nominalnya tetapi juga kinerjanya di bawah ketidakpastian.

Alih-alih mencari solusi terbaik untuk satu skenario, RTS mencari solusi yang berkinerja baik di berbagai skenario atau realisasi, menukar optimalitas puncak dengan keandalan.

Intuisi di balik metode

Tabu Search klasik menemukan solusi yang sangat baik dengan melarang pergerakan yang baru dikunjungi dan memandu pencarian melalui lingkungan. Namun, dalam praktiknya, masukan dunia nyata—biaya, permintaan, waktu tempuh—bervariasi. Solusi yang tampak optimal di bawah nilai yang diasumsikan mungkin berkinerja buruk ketika kenyataan berbeda. Robust Tabu Search menanamkan kriteria ketahanan langsung ke dalam fungsi evaluasi: setiap solusi kandidat dinilai atas berbagai skenario (sampel atau terenumerasi), dan pencarian mendukung solusi dengan kinerja yang stabil dan varians rendah. Hal ini membuat solusi akhir tangguh terhadap fluktuasi parameter tanpa perlu mengoptimalkan ulang setelah fakta.

Sejarah

Tabu Search diperkenalkan oleh Fred Glover pada tahun 1989–1990 sebagai metaheuristik berbasis memori yang keluar dari optimum lokal dengan melarang pergerakan yang baru dibalik. Perluasan tangguh muncul pada akhir 1990-an dan 2000-an seiring dengan meningkatnya minat pada optimasi tangguh; para peneliti menggabungkan evaluasi berbasis skenario dan kasus terburuk ke dalam penilaian lingkungan TS, yang melahirkan Robust Tabu Search sebagai alat praktis untuk masalah teknik dan logistik di bawah ketidakpastian.

Kapan digunakan

Gunakan Robust Tabu Search ketika Anda menghadapi masalah optimasi kombinatorial atau diskrit di mana parameter masukan utama tidak pasti atau bervariasi—masalah perutean, penjadwalan, penugasan, atau desain jaringan di bawah ketidakpastian permintaan atau biaya. Sangat cocok ketika biaya pengoptimalan ulang setelah penerapan tinggi, atau ketika solusi harus disertifikasi andal sebelum implementasi. Hindari RTS ketika masalah sepenuhnya deterministik (Tabu Search klasik sudah cukup), ketika himpunan ketidakpastian terlalu besar untuk diambil sampelnya secara layak tanpa perhitungan yang memberatkan, atau ketika masalahnya mulus dan cembung (metode tabu berbasis gradien akan lebih cepat dan lebih andal).

Batasan dan pertimbangan

  • Mengevaluasi ketahanan atas himpunan skenario yang besar melipatgandakan biaya komputasi dengan |S| per iterasi, yang bisa memberatkan.
  • Kualitas ketahanan sangat bergantung pada kualitas himpunan skenario; cakupan skenario yang buruk dapat memberikan kepercayaan diri yang salah.
  • Masa berlaku daftar tabu dan ukuran lingkungan adalah hiperparameter spesifik masalah yang memerlukan penyesuaian.
  • Tidak menjamin optimalitas global atau sertifikat kualitas solusi.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menemukan solusi yang tangguh terhadap variabilitas masukan tanpa memerlukan pemeriksaan ketahanan pasca-fakta yang terpisah.
  • Mewarisi kinerja empiris Tabu Search yang kuat pada masalah kombinatorial yang sulit (penjadwalan, VRP, varian TSP).
  • Kriteria ketahanan yang fleksibel: mendukung tujuan minimax, nilai yang diharapkan, rata-rata-varians, dan berbasis persentil.
  • Tidak memerlukan kekonveksan atau diferensiabilitas masalah—dapat diterapkan pada tujuan kotak hitam dan diskrit.
  • Mekanisme tabu mencegah terjebak dalam solusi yang secara lokal tangguh tetapi secara global biasa-biasa saja.

Penerapan

  • Perutean kendaraan tangguh di bawah waktu tempuh stokastik atau permintaan pelanggan
  • Penjadwalan job-shop dan flow-shop dengan waktu pemrosesan yang tidak pasti
  • Desain jaringan dan perencanaan kapasitas di bawah fluktuasi permintaan
  • Optimasi rantai pasokan dengan waktu tunggu atau biaya pemasok yang tidak pasti
  • Penugasan frekuensi dalam telekomunikasi di bawah ketidakpastian interferensi
  • Optimasi portofolio dengan imbal hasil aset yang tidak pasti menggunakan kendala kombinatorial

Cara kerjanya

Cara kerjanya

1

Definisikan masalah optimasi kombinatorial atau kontinu, identifikasi parameter yang tidak pasti (misalnya, permintaan, biaya, waktu pemrosesan), dan tentukan himpunan skenario S yang mewakili realisasi yang masuk akal—baik dengan mengambil sampel dari distribusi atau membangun himpunan ketidakpastian diskrit. Tetapkan tujuan ketahanan: minimalkan biaya kasus terburuk, minimalkan biaya yang diharapkan, atau minimalkan kombinasi tertimbang dari rata-rata dan varians.

2

Untuk setiap solusi kandidat x yang ditemui selama pencarian, evaluasi tujuan f(x, s) di bawah setiap skenario s di S. Hitung ukuran ketahanan R(x)—misalnya, R(x) = maks_{s di S} f(x,s) untuk ketahanan minimax, atau R(x) = E[f(x,s)] + lambda * Var[f(x,s)] untuk ketahanan rata-rata-varians. Ini menggantikan evaluasi nominal tunggal yang digunakan dalam Tabu Search klasik.

3

Hasilkan lingkungan N(x) dari solusi saat ini x dengan menerapkan semua pergerakan yang layak (pertukaran, penyisipan, pembalikan, dll.). Evaluasi R(x') untuk setiap tetangga x', kecuali pergerakan yang saat ini ada dalam daftar tabu kecuali kriteria aspirasi terpenuhi. Pilih tetangga x* dengan nilai ketahanan R(x*) terbaik.

4

Pindah ke x* dan catat kebalikan dari pergerakan yang diterapkan dalam daftar tabu dengan masa berlaku t (biasanya 5–20 iterasi). Daftar tabu mencegah siklus dan mendorong eksplorasi. Kriteria aspirasi—seperti menerima pergerakan tabu jika menghasilkan solusi tabu terbaik secara global—dapat mengesampingkan pembatasan tabu.

5

Perbarui solusi tabu terbaik yang diketahui jika R(x*) meningkatkan yang terbaik saat ini. Lanjutkan iterasi hingga kriteria penghentian terpenuhi: iterasi maksimum, waktu berlalu, atau tidak ada peningkatan selama jumlah langkah yang ditentukan. Kembalikan solusi tabu terbaik yang ditemukan beserta profil kinerjanya per skenario.

Kesalahan umum

  • Menggunakan terlalu sedikit skenario meremehkan ketidakpastian sebenarnya dan menghasilkan solusi yang tampak tangguh tetapi gagal dalam praktik.
  • Mencampuradukkan Robust Tabu Search dengan Stochastic Tabu Search: optimasi tangguh meminimalkan paparan terhadap kasus terburuk, sementara Stochastic TS mengambil sampel untuk memperkirakan nilai yang diharapkan—tujuan dan interpretasinya berbeda.
  • Menerapkan ketahanan minimax ketika skenario terburuk memiliki probabilitas yang dapat diabaikan menghasilkan solusi yang terlalu konservatif dengan biaya yang tidak perlu.
  • Mengabaikan kriteria aspirasi dapat menyebabkan pencarian melewatkan solusi tangguh global yang kebetulan melibatkan pergerakan tabu.
  • Menetapkan masa berlaku tabu terlalu tinggi menciptakan pembatasan yang berlebihan; terlalu rendah menyebabkan siklus—keduanya menurunkan kualitas solusi.

Pertanyaan yang sering diajukan

Bagaimana Robust Tabu Search berbeda dari Stochastic Tabu Search?

Stochastic Tabu Search biasanya menggunakan pengambilan sampel acak dalam prosedur pencarian itu sendiri (misalnya, penerimaan probabilistik atau pengambilan sampel lingkungan acak) untuk memperkirakan nilai yang diharapkan. Robust Tabu Search secara eksplisit mengoptimalkan kriteria ketahanan—seperti kinerja kasus terburuk atau rata-rata-varians—yang dievaluasi atas himpunan ketidakpastian yang ditentukan. Tujuannya dalam TS tangguh adalah stabilitas solusi di seluruh skenario, bukan hanya kinerja yang diharapkan.

Seberapa besar himpunan skenario S seharusnya?

Tidak ada aturan universal. Untuk himpunan ketidakpastian diskrit, enumerasi semua skenario yang kredibel jika memungkinkan. Untuk distribusi kontinu, 50–500 skenario sampel sering memberikan cakupan yang memadai; teknik pengurangan varians seperti pengambilan sampel Latin hypercube dapat meningkatkan efisiensi. Analisis sensitivitas pada |S| disarankan sebelum berkomitmen pada jumlah skenario akhir.

Bisakah Robust Tabu Search menangani masalah multi-objektif?

Ya. Ketika dikombinasikan dengan kerangka kerja Tabu Search multi-objektif, ketahanan menjadi tujuan tambahan atau kendala. Front Pareto dari (kinerja nominal, ketahanan) dapat dieksplorasi, menghasilkan serangkaian solusi yang menukar optimalitas dengan keandalan—berguna ketika pemangku kepentingan harus memilih antara opsi yang toleran terhadap risiko dan yang menghindari risiko.

Ukuran ketahanan apa yang harus saya pilih?

Minimax (kasus terburuk) sesuai ketika kegagalan bersifat katastropik dan hasil buruk dengan probabilitas rendah pun tidak dapat diterima. Nilai yang diharapkan cocok untuk pengambil keputusan yang netral terhadap risiko. Rata-rata-varians menyeimbangkan kinerja rata-rata dan variabilitas dan umum dalam desain teknik. Metrik Value-at-Risk (VaR) atau VaR Bersyarat digunakan dalam aplikasi keuangan dan logistik di mana jaminan berbasis persentil penting.

Apakah Robust Tabu Search cocok untuk instans yang sangat besar?

Itu tergantung pada biaya evaluasi skenario. Jika setiap evaluasi f(x,s) murah (milidetik), ketahanan atas ratusan skenario tetap layak bahkan untuk instans besar. Jika setiap evaluasi memerlukan simulasi atau panggilan pemecah yang mahal, pengurangan skenario agresif atau model pengganti menjadi perlu. Evaluasi skenario paralel di seluruh utas atau mesin adalah mitigasi umum.

Metode terkait

Sumber

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Buka referensi DOI
    Disalin.
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

    Buka referensi publikasi
    Disalin.