Pencarian Tabu Multi-objektif (MOTS) — Metaheuristik untuk solusi Pareto-optimal
- Diperkenalkan oleh
- Hansen, M. P.; building on Glover (1989) Tabu Search
- Tahun
- 1997
- Jenis
- Metaheuristic multi-objective optimization
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pencarian Tabu Multi-objektif (MOTS) adalah algoritma metaheuristik yang memperluas kerangka Pencarian Tabu klasik untuk secara simultan mengoptimalkan dua atau lebih fungsi tujuan yang saling bertentangan.
Alih-alih satu optimum tunggal, algoritma ini berupaya mendekati front Pareto — himpunan solusi di mana tidak ada tujuan yang dapat ditingkatkan tanpa memperburuk tujuan lain — sehingga cocok untuk masalah optimasi kombinatorial dan kontinu yang kompleks dalam bidang teknik, logistik, dan riset operasi.
Intuisi di balik metode
Bayangkan menjelajahi lanskap kasar dengan banyak bukit dan lembah, tetapi Anda memiliki beberapa peta yang menunjukkan medan yang berbeda (satu per tujuan) yang saling bertentangan. MOTS menavigasi ruang ini dengan bergerak ke solusi tetangga, menyimpan daftar memori jangka pendek (daftar tabu) dari tempat yang baru saja dikunjungi untuk menghindari siklus, dan memelihara arsip solusi non-dominan yang ditemukan sejauh ini. Secara berkala, diversifikasi strategis mendorong pencarian ke wilayah front Pareto yang belum dijelajahi, menyeimbangkan eksploitasi area yang menjanjikan dengan eksplorasi global.
Sejarah
Pencarian Tabu Multi-objektif memperluas Pencarian Tabu satu-objektif yang diperkenalkan oleh Fred Glover pada tahun 1989. Formulasi MOTS sistematis pertama — termasuk pengarsipan Pareto dan kriteria aspirasi multi-objektif — disajikan oleh M. P. Hansen pada konferensi MCDM tahun 1997. Karya selanjutnya oleh Gandibleux, Teghem, dan lainnya memformalkan varian untuk masalah kombinatorial, dan MOTS sejak itu diterapkan pada masalah penjadwalan, logistik, dan desain teknik sebagai alternatif kompetitif untuk algoritma multi-objektif evolusioner.
Kapan digunakan
Gunakan MOTS ketika Anda menghadapi masalah optimasi kombinatorial atau campuran-bilangan bulat dengan dua atau lebih tujuan yang saling bertentangan (misalnya, biaya vs. kualitas, waktu vs. risiko) dan metode eksak secara komputasi tidak dapat dipecahkan. Algoritma ini unggul pada masalah penjadwalan, perutean kendaraan, desain jaringan, dan pemilihan portofolio di mana ruang pencarian terlalu besar untuk enumerasi menyeluruh. Pilih MOTS daripada pencarian acak murni ketika struktur lingkungan bermakna dan operator pergerakan dapat didefinisikan dengan jelas. JANGAN gunakan MOTS ketika: masalah memiliki satu tujuan (Pencarian Tabu biasa sudah cukup); ketika front Pareto dapat dihitung secara eksak; ketika informasi gradien tersedia dan lanskapnya cembung (gunakan pemrograman matematis sebagai gantinya); atau ketika keputusan waktu nyata memerlukan keluaran deterministik yang dapat direproduksi tanpa variasi stokastik.
Batasan dan pertimbangan
- Kinerja sangat sensitif terhadap panjang daftar tabu, definisi lingkungan, dan strategi diversifikasi — memerlukan penyetelan parameter yang cermat.
- Tidak ada jaminan konvergensi ke front Pareto yang sebenarnya; kualitas solusi bergantung pada panjang eksekusi dan struktur masalah.
- Mahal secara komputasi per iterasi ketika lingkungan besar atau evaluasi tujuan mahal.
- Pemeliharaan dan pembaruan arsip Pareto dapat menjadi mahal seiring bertambahnya jumlah tujuan dan ukuran arsip.
- Implementasi paralel tidak sepele karena sifat berbasis memori yang sekuensial dari mekanisme tabu.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menghindari kunjungan ulang solusi terbaru melalui daftar tabu, mengurangi risiko siklus dalam lanskap yang kompleks.
- Kriteria aspirasi memungkinkan penolakan pembatasan tabu ketika suatu pergerakan menghasilkan peningkatan yang luar biasa, menyeimbangkan memori dengan fleksibilitas.
- Tidak memerlukan informasi gradien, membuatnya dapat diterapkan pada fungsi tujuan yang tidak dapat dibedakan, diskrit, atau kotak hitam.
- Menghasilkan perkiraan seluruh front Pareto dalam satu kali jalan, mendukung pengambilan keputusan multi-kriteria.
- Desain lingkungan dan operator pergerakan yang fleksibel memungkinkan kustomisasi spesifik masalah.
- Mekanisme diversifikasi memungkinkan pelepasan dari optimum lokal dan cakupan front Pareto yang lebih baik.
Penerapan
- Perutean kendaraan multi-objektif dan penjadwalan logistik (meminimalkan biaya dan waktu pengiriman secara bersamaan)
- Penjadwalan proyek bi-objektif: meminimalkan makespan dan biaya sumber daya di bawah kendala preseden
- Optimasi portofolio: menyeimbangkan pengembalian yang diharapkan terhadap risiko di berbagai kelas aset
- Desain jaringan: meminimalkan biaya instalasi sambil memaksimalkan keandalan atau throughput
- Perencanaan proses manufaktur: mengoptimalkan waktu siklus, penggunaan energi, dan metrik kualitas secara bersamaan
- Manajemen lingkungan: menyeimbangkan keluaran ekonomi terhadap polusi atau dampak ekologis
Cara kerjanya
Cara kerjanya
Inisialisasi pencarian dengan satu atau lebih solusi awal (dihasilkan secara acak atau dibangun secara heuristik). Tetapkan daftar tabu kosong dengan panjang tetap L dan inisialisasikan arsip Pareto dengan solusi non-dominan dari populasi awal.
Hasilkan lingkungan N(s) dari solusi saat ini s dengan menerapkan operator pergerakan (pertukaran, penyisipan, perturbasi). Evaluasi semua solusi tetangga pada setiap fungsi tujuan untuk mengidentifikasi kandidat untuk progresi.
Terapkan filter tabu: kecualikan tetangga yang pergerakan penentunya muncul di daftar tabu kecuali jika memenuhi kriteria aspirasi — biasanya bahwa tetangga mendominasi semua anggota arsip saat ini atau meningkatkan nilai terbaik yang diketahui pada setidaknya satu tujuan. Ini mencegah siklus dan memaksa eksplorasi.
Pilih tetangga non-tabu terbaik (atau pemenang kriteria aspirasi) sebagai solusi saat ini berikutnya. Perbarui arsip Pareto dengan menambahkan solusi baru jika non-dominan; hapus anggota arsip yang didominasi oleh entri baru.
Terapkan strategi diversifikasi ketika pencarian stagnan: memori frekuensi jangka panjang mengidentifikasi wilayah yang jarang dikunjungi; mulai ulang dari solusi arsip elit atau solusi yang terperturbasi secara acak untuk memperluas cakupan front Pareto.
Ulangi langkah lingkungan, filter, dan arsip hingga kriteria penghentian terpenuhi — biasanya jumlah maksimum iterasi, evaluasi fungsi, atau waktu CPU yang berlalu. Kembalikan arsip Pareto sebagai perkiraan front Pareto-optimal.
Kesalahan umum
- Menetapkan daftar tabu terlalu pendek menyebabkan siklus; menetapkannya terlalu panjang terlalu membatasi pencarian dan melewatkan solusi yang baik — kalibrasi empiris sangat penting.
- Mengabaikan diversifikasi menyebabkan konvergensi prematur pada satu wilayah front Pareto, menghasilkan perkiraan yang buruk.
- Menerapkan MOTS dengan lebih dari tiga tujuan menurunkan kinerja karena manajemen arsip dan pemeliharaan keragaman menjadi memberatkan secara komputasi; pertimbangkan metode berbasis dekomposisi untuk masalah multi-tujuan.
- Menggunakan operator pergerakan generik tanpa desain spesifik masalah sangat membatasi kualitas solusi dibandingkan dengan implementasi yang disesuaikan.
- Melaporkan hanya arsip akhir tanpa memeriksa riwayat konvergensi dapat menutupi stagnasi prematur.
Pertanyaan yang sering diajukan
Bagaimana MOTS menangani daftar tabu ketika ada banyak tujuan?
Daftar tabu menyimpan pergerakan (bukan solusi), sehingga beroperasi sama seperti dalam Pencarian Tabu satu-objektif. Perbedaan utamanya adalah bahwa pemilihan di antara tetangga non-tabu menggunakan dominasi multi-objektif atau fungsi skalarisasi, dan kriteria aspirasi didefinisikan ulang untuk mengizinkan pergerakan tabu jika solusi yang dihasilkan tidak didominasi oleh semua anggota arsip saat ini.
Apa itu arsip Pareto dan seberapa besar seharusnya?
Arsip Pareto menyimpan semua solusi non-dominan yang ditemukan selama pencarian. Ukuran maksimumnya biasanya dibatasi (misalnya, 100–500 solusi) untuk menjaga biaya memori dan pembaruan tetap terkelola. Ketika arsip penuh, pemangkasan jarak kerumunan (crowding-distance) atau berbasis grid menghapus solusi dari wilayah yang terlalu padat untuk mempertahankan keragaman.
Bagaimana perbandingan MOTS dengan NSGA-II untuk masalah multi-objektif?
NSGA-II menggunakan pendekatan evolusioner berbasis populasi dengan persilangan (crossover) dan mutasi, membuatnya lebih baik dalam eksplorasi global di awal pencarian. MOTS mengandalkan pergerakan lingkungan dan memori, yang sering kali memberikan kualitas pencarian lokal yang lebih baik. Dalam praktiknya, MOTS cenderung berkinerja lebih baik pada masalah kombinatorial dengan struktur lingkungan yang kuat, sementara NSGA-II lebih banyak digunakan untuk masalah kontinu.
Berapa banyak iterasi yang biasanya dibutuhkan?
Tidak ada aturan universal. Praktik umum adalah menganggarkan evaluasi fungsi daripada iterasi — biasanya 10.000 hingga 100.000 evaluasi tergantung pada ukuran masalah — dan menjalankan beberapa kali eksekusi independen untuk menilai kualitas solusi dan stabilitas front Pareto.
Bisakah MOTS menangani lebih dari dua tujuan?
Ya, tetapi efektivitasnya menurun seiring bertambahnya jumlah tujuan melebihi tiga ('kutukan dimensi' dalam ruang tujuan). Untuk empat atau lebih tujuan, ukuran arsip meledak dan pemeliharaan keragaman menjadi sulit; pendekatan berbasis dekomposisi atau berbasis indikator sering kali lebih disukai.
Metode terkait
Sumber
Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.
Buka referensi publikasiDisalin.Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Buka referensi DOIDisalin.