Skip to content
Kembali ke hasil pencarian

Optimasi Koloni Semut Multi-Objektif (MOACO)

Diperkenalkan oleh
Gambardella, Taillard & Agazzi; Dorigo & Stützle
Tahun
1999
Jenis
Population-based metaheuristic
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Optimasi Koloni Semut Multi-Objektif (MOACO) adalah metaheuristik kecerdasan kawanan yang memperluas kerangka Optimasi Koloni Semut klasik untuk mengoptimalkan dua atau lebih tujuan yang saling bertentangan secara bersamaan.

Semut buatan membangun solusi kandidat yang dipandu oleh jejak feromon dan informasi heuristik, secara progresif membangun arsip solusi Pareto-optimal daripada konvergen ke satu jawaban terbaik.

Intuisi di balik metode

Bayangkan koloni semut mencari makan di lanskap yang tidak memiliki satu jalur terbaik — sebaliknya, jalur yang berbeda mengorbankan jarak terhadap keamanan, atau kecepatan terhadap energi. Setiap semut meninggalkan feromon yang sebanding dengan kualitas jalurnya pada beberapa kriteria secara bersamaan. Selama beberapa generasi, koloni secara kolektif memetakan batas pengorbanan — front Pareto — tanpa memaksakan bobot tujuan yang telah ditentukan sebelumnya. Wawasan kuncinya adalah bahwa stigmergy (komunikasi tidak langsung melalui feromon) dapat mengkodekan informasi kualitas multi-objektif, memungkinkan perkiraan yang muncul dari seluruh permukaan pengorbanan.

Sejarah

Optimasi Koloni Semut diperkenalkan oleh Marco Dorigo dalam tesis doktoralnya tahun 1992 dan diformalkan dengan Maniezzo dan Colorni. Perluasan multi-objektif muncul pada akhir 1990-an; MACS-VRPTW oleh Gambardella, Taillard, dan Agazzi (1999) mendemonstrasikan beberapa koloni semut yang menargetkan tujuan yang berbeda. Kerangka kerja selanjutnya oleh Doerner, Hartl, dan lainnya memformalkan MOACO sebagai sebuah kelas, dan buku teks Dorigo dan Stützle tahun 2004 memberikan perlakuan algoritmis kanonik. MOACO tetap menjadi area penelitian aktif dengan aplikasi dalam perutean jaringan, bioinformatika, dan logistik berkelanjutan.

Kapan digunakan

Gunakan MOACO ketika masalah memiliki dua atau lebih tujuan yang saling bertentangan, ruang solusi kombinatorial atau diskrit (misalnya, perutean, penjadwalan, desain jaringan), dan tidak ada preferensi awal yang kuat atas tujuan yang akan membenarkan peruntuhannya menjadi skalar. Ini unggul dalam masalah logistik, rantai pasokan, dan penjadwalan alur kerja di mana ACO sudah berkinerja baik pada tujuan tunggal. Hindari MOACO ketika masalahnya kontinu dan metode multi-objektif berbasis gradien (misalnya, NSGA-II dengan pengkodean nyata, atau optimasi Bayesian) lebih efisien; ketika anggaran komputasi sangat terbatas, karena MOACO memerlukan banyak evaluasi; atau ketika front Pareto yang tepat diperlukan untuk masalah di mana pemrograman multi-objektif yang tepat (misalnya, MILP multi-objektif) dapat dikelola.

Batasan dan pertimbangan

  • Memerlukan penyetelan hati-hati beberapa hyperparameter (α, β, ρ, ukuran koloni, kapasitas arsip), dan sensitivitas terhadap pengaturan ini bisa tinggi.
  • Konvergensi lebih lambat daripada pemecah eksak untuk masalah kecil yang terstruktur dengan baik di mana metode pemrograman integer atau dinamis dapat dikelola.
  • Kualitas perkiraan dan keragaman front Pareto tidak dijamin; hasil bervariasi antar jalan karena konstruksi stokastik.
  • Penskalaan ke ruang tujuan berdimensi tinggi (>3 tujuan) sulit dan mungkin memerlukan strategi dekomposisi khusus.
  • Tidak ada bukti konvergensi untuk contoh masalah arbitrer; jaminan teoretis terbatas dibandingkan dengan pemrograman matematika.

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

Kelebihan

  • Secara alami menangani ruang solusi kombinatorial dan berbasis permutasi di mana metode gradien gagal.
  • Menghasilkan perkiraan front Pareto penuh dalam satu kali jalan, memberikan informasi pengorbanan eksplisit kepada pengambil keputusan.
  • Keragaman kawanan mencegah konvergensi dini dan mendukung eksplorasi wilayah Pareto yang terputus.
  • Memori feromon menyediakan pembelajaran implisit antar iterasi, memungkinkan intensifikasi terpandu tanpa mengabaikan eksplorasi.
  • Mudah diparalelkan: beberapa koloni semut atau koloni spesifik tujuan dapat berjalan secara bersamaan.
  • Tahan terhadap fitur lanskap spesifik masalah seperti banyak optima lokal.

Penerapan

  • Perutean kendaraan multi-objektif dan penjadwalan logistik dengan jendela waktu dan batasan kapasitas.
  • Desain topologi jaringan yang mengoptimalkan biaya, latensi, dan keandalan secara bersamaan.
  • Penjadwalan job-shop fleksibel yang menyeimbangkan makespan, konsumsi energi, dan utilisasi mesin.
  • Bioinformatika: prediksi struktur protein dan pemilihan fitur untuk klasifikasi multi-label.
  • Desain rantai pasokan berkelanjutan yang mengoptimalkan biaya ekonomi, emisi karbon, dan kriteria sosial.
  • Penjadwalan alur kerja multi-objektif di lingkungan komputasi awan.

Cara kerjanya

Cara kerjanya

1

Inisialisasi matriks feromon (satu per tujuan atau matriks berbobot bersama) dengan nilai seragam. Tentukan informasi heuristik η untuk setiap komponen solusi. Buat arsip Pareto kosong untuk menyimpan solusi non-dominan yang ditemukan selama pencarian.

2

Setiap semut membangun solusi lengkap langkah demi langkah dengan memilih komponen solusi secara probabilistik. Probabilitas transisi menggunakan kekuatan feromon τ dan keinginan heuristik η yang dinaikkan ke eksponen penyetelan α dan β. Varian MOACO yang berbeda menetapkan matriks feromon per tujuan atau menggunakan bobot skalarisasi yang berubah di antara semut.

Rumus
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}
3

Evaluasi setiap solusi yang dibangun pada semua fungsi tujuan secara bersamaan. Identifikasi hubungan dominasinya sehubungan dengan anggota arsip yang ada: sebuah solusi mendominasi yang lain jika setidaknya sama baiknya pada semua tujuan dan secara ketat lebih baik pada setidaknya satu.

4

Perbarui arsip Pareto dengan menambahkan solusi non-dominan dan menghapus anggota arsip yang sekarang didominasi oleh solusi baru. Terapkan mekanisme pelestarian keragaman (misalnya, jarak kerumunan, kepadatan berbasis grid) untuk mencegah arsip menjadi terlalu terkonsentrasi di wilayah sempit ruang tujuan.

5

Uapkan semua jejak feromon dengan faktor (1 − ρ) untuk memungkinkan informasi lama memudar. Depositkan feromon baru pada komponen solusi yang termasuk dalam solusi arsip (elite). Jumlah deposit Δτ mencerminkan kualitas spesifik tujuan atau peringkat berbasis kerumunan, memperkuat komponen yang terkait dengan solusi Pareto-optimal yang tersebar merata.

Rumus
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^k
6

Ulangi konstruksi melalui pembaruan feromon untuk jumlah iterasi tetap atau sampai kriteria konvergensi terpenuhi. Kembalikan arsip Pareto akhir sebagai front Pareto perkiraan, yang mewakili spektrum penuh solusi optimal pengorbanan bagi pengambil keputusan untuk dipilih.

Kesalahan umum

  • Menggunakan satu matriks feromon bersama tanpa diferensiasi spesifik tujuan sering menghasilkan front Pareto yang bias dan tersebar buruk.
  • Mengabaikan manajemen keragaman arsip menyebabkan front yang ramai di satu wilayah dan celah besar di tempat lain, memberikan gambaran pengorbanan yang menyesatkan.
  • Menetapkan laju penguapan ρ terlalu tinggi menyebabkan pencucian feromon dan hilangnya pembelajaran yang terakumulasi; terlalu rendah menyebabkan stagnasi di sekitar solusi suboptimal.
  • Membandingkan hasil MOACO antar jalan tanpa replikasi statistik (beberapa seed, indikator hypervolume) menghasilkan penilaian kualitas yang menyesatkan.
  • Lupa menormalisasi nilai tujuan sebelum menghitung dominasi atau deposit feromon mendistorsi pencarian ketika tujuan memiliki skala yang sangat berbeda.

Pertanyaan yang sering diajukan

Bagaimana MOACO berbeda dari menjalankan ACO tujuan tunggal beberapa kali dengan kombinasi bobot yang berbeda?

Jalan ACO tujuan tunggal berbobot memerlukan penentuan bobot di muka dan setiap jalan hanya memperkirakan satu titik Pareto-optimal. MOACO menghasilkan arsip solusi non-dominan di seluruh permukaan pengorbanan dalam satu kali jalan, dan pembaruan feromonnya memperkuat solusi berkualitas tinggi yang beragam daripada satu optimum skalar.

Varian MOACO mana yang harus saya gunakan untuk masalah baru?

Jika tujuan dapat dipisahkan dan masing-masing memiliki heuristik alami, pendekatan multi-koloni (satu koloni per tujuan yang berbagi arsip Pareto umum) adalah titik awal yang baik. Jika tujuan terkait erat, satu koloni dengan skalarisasi berbasis dekomposisi (gaya MOACO/D) sering kali konvergen lebih efisien. Periksa literatur untuk domain masalah spesifik Anda terlebih dahulu.

Berapa banyak semut dan iterasi yang biasanya dibutuhkan?

Tidak ada jawaban universal, tetapi konfigurasi awal yang umum adalah 20–100 semut per koloni dan 500–2000 iterasi untuk masalah kombinatorial berukuran sedang. Ruang solusi yang lebih besar dan lebih banyak tujuan memerlukan lebih banyak iterasi. Selalu jalankan beberapa pengulangan independen dan laporkan indikator hypervolume atau IGD yang dirata-ratakan di atas seed.

Bisakah MOACO menangani masalah optimasi kontinu?

ACO standar dirancang untuk ruang diskrit. Varian MOACO kontinu ada (misalnya, berbasis ACOR) tetapi umumnya dikalahkan oleh NSGA-II atau MOEA/D pada masalah kontinu. Cadangkan MOACO untuk masalah kombinatorial atau integer campuran di mana konstruksi berbasis grafnya memberikan keuntungan alami.

Bagaimana ukuran arsip Pareto harus diatur?

Batas ukuran arsip membatasi jumlah solusi elite yang digunakan untuk deposisi feromon. Arsip yang terlalu kecil kehilangan keragaman; terlalu besar memperlambat penguatan feromon. Nilai tipikal berkisar dari 10 hingga 100 solusi; gunakan strategi jarak kerumunan atau berbasis grid untuk mempertahankan arsip yang tersebar merata terlepas dari ukurannya.

Metode terkait

Sumber

  1. Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.

    Buka referensi publikasi
    Disalin.
  2. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.

    ISBN: 9780262042192
    Disalin.