Skip to content
Kembali ke hasil pencarian

Pencarian Tabu Berbasis Agen — Optimasi Metaheuristik Multi-Agen Terdistribusi

Diperkenalkan oleh
Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
Tahun
1989–1995
Jenis
Hybrid metaheuristic — agent-based distributed tabu search
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Pencarian Tabu Berbasis Agen (ABTS) menyematkan metaheuristik pencarian tabu di dalam kerangka kerja multi-agen di mana agen otonom masing-masing menjalankan utas pencarian tabu independen atau kooperatif, berbagi solusi yang menjanjikan untuk keluar dari optimum lokal dan secara kolektif menjelajahi ruang pencarian kombinatorial atau kontinu yang besar secara lebih efektif daripada implementasi utas tunggal.

Intuisi di balik metode

Pencarian tabu klasik dapat terjebak menjelajahi wilayah sempit bahkan dengan mekanisme memori jangka pendeknya. Dengan menerapkan beberapa agen otonom, masing-masing memelihara daftar tabu dan lingkungannya sendiri, pencarian menyebar ke berbagai titik awal. Agen secara berkala berbagi solusi elit (intensifikasi) dan sengaja menyebar ke wilayah yang belum dijelajahi (diversifikasi). Struktur kooperatif namun independen ini mencerminkan perilaku kawanan biologis — tidak ada agen tunggal yang memiliki gambaran lengkap, namun kolektif menemukan solusi berkualitas tinggi jauh lebih cepat daripada pencari individu mana pun.

Sejarah

Pencarian tabu diformalkan oleh Fred Glover pada tahun 1986–1989. Varian terdistribusi dan paralel muncul pada awal 1990-an ketika para peneliti berusaha memanfaatkan arsitektur multi-prosesor. Verhoeven dan Aarts (1995) memberikan studi sistematis tentang pencarian lokal paralel termasuk strategi tabu kooperatif. Kerangka kerja berbasis agen menjadi menonjol pada tahun 2000-an ketika kosakata pemodelan berbasis agen memasuki riset operasi.

Kapan digunakan

Gunakan Pencarian Tabu Berbasis Agen saat memecahkan masalah optimasi kombinatorial atau campuran-bilangan bulat yang sulit (penjadwalan, perutean, desain jaringan, alokasi sumber daya) di mana pencarian tabu utas tunggal stagnan dan sumber daya komputasi paralel tersedia. Ini sangat efektif ketika lanskap pencarian memiliki banyak optimum lokal dengan kualitas serupa. Hindari jika masalahnya cukup kecil untuk pemecah eksak (MILP, branch-and-bound), ketika satu evaluasi sangat mahal secara komputasi (membuat banyak evaluasi paralel tidak mungkin), atau ketika persyaratan reproduktibilitas bertentangan dengan dinamika interaksi agen yang non-deterministik.

Batasan dan pertimbangan

  • Overhead sinkronisasi dan biaya komunikasi antar agen dapat meniadakan keuntungan paralelisme pada sistem yang terhubung erat atau jaringan yang lambat.
  • Lebih banyak hyperparameter daripada pencarian tabu utas tunggal: jumlah agen, topologi komunikasi, frekuensi sinkronisasi, dan pemicu diversifikasi semuanya memerlukan penyetelan.
  • Jaminan konvergensi teoretis lebih lemah daripada metode eksak; kualitas solusi sangat bergantung pada penyetelan dan struktur masalah.
  • Reproduktibilitas sulit dicapai karena interaksi agen memperkenalkan stokastisitas tambahan di luar inisialisasi acak.

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

Kelebihan

  • Eksplorasi paralel secara signifikan mengurangi waktu-ke-solusi pada masalah kombinatorial besar dibandingkan dengan pencarian tabu utas tunggal.
  • Kerangka kerja multi-agen secara alami mendukung diversifikasi, mengurangi risiko konvergensi prematur ke optimum lokal yang buruk.
  • Arsitektur fleksibel memungkinkan agen heterogen dengan struktur lingkungan yang berbeda, strategi masa berlaku tabu, atau bahkan metaheuristik campuran.
  • Berbagi solusi kooperatif mentransfer penemuan antar agen, mempercepat intensifikasi di sekitar wilayah berkualitas tinggi.
  • Skala dengan baik dengan inti komputasi yang tersedia, membuatnya cocok untuk lingkungan komputasi multi-core dan terdistribusi modern.

Penerapan

  • Perutean kendaraan dan logistik: mengoordinasikan beberapa agen yang masing-masing mengoptimalkan sub-masalah rute.
  • Penjadwalan job-shop dan manufaktur fleksibel: agen menangani subset mesin secara kooperatif.
  • Desain jaringan telekomunikasi: penugasan saluran terdistribusi dan optimasi topologi.
  • Perencanaan rantai pasokan: optimasi inventaris dan distribusi multi-tingkat.
  • Prediksi struktur protein: pencarian lingkungan paralel di atas ruang konformasi.
  • Penjadwalan akademik dan penjadwalan mata kuliah dengan agen tingkat departemen terdistribusi.

Cara kerjanya

Cara kerjanya

1

Definisikan populasi agen otonom. Setiap agen diberi peran: beberapa fokus pada intensifikasi (pencarian lokal mendalam di sekitar wilayah yang menjanjikan), yang lain pada diversifikasi (keluar ke area yang belum dijelajahi). Setiap agen memelihara daftar tabu sendiri untuk gerakan terlarang, solusi saat ini, dan struktur lingkungan yang disesuaikan dengan jenis masalah (misalnya, gerakan tukar, penyisipan, atau 2-opt untuk masalah kombinatorial).

2

Inisialisasi agen dengan solusi awal yang berbeda, baik yang dihasilkan secara acak atau di-seed melalui heuristik konstruktif (misalnya, tetangga terdekat untuk perutean). Keberagaman di antara solusi awal sangat penting — awal yang identik mengarah pada pencarian paralel yang berlebihan. Evaluasi fungsi tujuan untuk setiap solusi awal dan catat solusi terbaik global di semua agen.

3

Setiap agen menjalankan loop pencarian tabu sendiri: hasilkan lingkungan dari solusi saat ini, evaluasi semua (atau sebagian) solusi tetangga, pilih tetangga non-tabu terbaik sebagai gerakan berikutnya (kriteria aspirasi memungkinkan penimpaan daftar tabu jika kandidat melampaui yang terbaik secara global), dan perbarui daftar tabu dengan menambahkan gerakan terbalik dengan masa berlaku yang ditarik dari rentang tetap atau adaptif.

4

Agen berkomunikasi pada interval sinkronisasi yang ditentukan atau pemicu peristiwa. Strategi umum termasuk menyiarkan yang terbaik secara global saat ini ke semua agen (yang mungkin memulai kembali darinya), menyuntikkan solusi elit ke dalam kumpulan bersama yang dikonsultasikan agen secara berkala, atau pertukaran solusi antar agen tetangga dalam topologi (cincin, terhubung penuh, atau acak). Kontrol keberagaman mencegah konvergensi prematur dengan menghukum agen dengan solusi identik.

5

Hentikan ketika anggaran iterasi maksimum, batas waktu jam dinding, atau kriteria stagnasi terpenuhi (misalnya, tidak ada peningkatan pada yang terbaik secara global untuk sejumlah iterasi). Pilih solusi terbaik secara global yang ditemukan di semua agen di semua iterasi sebagai keluaran akhir. Opsional laporkan front Pareto jika beberapa tujuan dilacak.

Kesalahan umum

  • Menetapkan semua agen ke solusi awal yang identik membuang kapasitas paralel — pastikan inisialisasi yang beragam.
  • Komunikasi yang terlalu sering memaksa agen ke dalam cekungan solusi yang sama, menghilangkan manfaat diversifikasi dan secara efektif mengurangi pencarian menjadi satu utas.
  • Mengabaikan kriteria aspirasi dalam desain daftar tabu dapat menyebabkan agen melewatkan solusi yang jelas lebih baik, terutama pada fase pencarian awal.
  • Menerapkan ABTS pada masalah di mana evaluasi lingkungan sangat mahal tanpa model pengganti akan menghasilkan waktu berjalan yang sangat mahal.

Pertanyaan yang sering diajukan

Bagaimana Pencarian Tabu Berbasis Agen berbeda dari sekadar menjalankan beberapa utas pencarian tabu?

Perbedaan utamanya adalah kerja sama. Dalam menjalankan paralel independen, utas tidak pernah berbagi informasi. Dalam ABTS, agen secara aktif bertukar solusi, memperbarui kumpulan elit bersama, atau mengadopsi pemicu diversifikasi berdasarkan keadaan kolektif — menghasilkan perilaku pencarian yang muncul yang tidak ada dalam menjalankan independen.

Berapa banyak agen yang harus saya gunakan?

Titik awal yang umum adalah satu agen per inti CPU yang tersedia. Penelitian menunjukkan penurunan imbalan di luar 8–16 agen untuk sebagian besar masalah kombinatorial, karena overhead komunikasi meningkat. Eksperimen percontohan dengan 4, 8, dan 16 agen membantu mengidentifikasi titik optimal untuk masalah tertentu.

Bisakah ABTS menangani masalah multi-objektif?

Ya. Agen dapat memelihara perkiraan lokal dari front Pareto dan berbagi solusi non-dominan melalui arsip bersama. Ini terkadang disebut Pencarian Tabu Berbasis Agen Multi-Objektif dan berbeda dari ABTS standar satu-objektif.

Topologi komunikasi mana yang terbaik?

Topologi yang terhubung penuh menyebarkan solusi bagus tercepat tetapi menciptakan biaya komunikasi yang tinggi. Topologi cincin atau dunia kecil menyeimbangkan difusi informasi dengan otonomi. Untuk sebagian besar masalah praktis, topologi cincin atau acak yang jarang berfungsi baik sebagai default.

Kapan saya harus memilih algoritma genetik atau kawanan partikel daripada ABTS?

Pilih metode berbasis populasi (GA, PSO) ketika masalah memiliki lanskap kontinu yang mulus atau ketika operator persilangan/rekombinasi terdefinisi dengan baik. ABTS unggul pada masalah diskrit, kombinatorial dengan operator lingkungan yang terdefinisi dengan baik di mana memori tabu memberikan keuntungan pencarian yang kuat.

Metode terkait

Sumber

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

    Buka referensi DOI
    Disalin.
  2. Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.

    Buka referensi DOI
    Disalin.