Skip to content
Kembali ke hasil pencarian

Optimasi Koloni Semut — Optimasi Kombinatorial Berbasis Kawanan

Tahun
1992 (foundational thesis); 1997 (Ant Colony System formalization)
Jenis
Metaheuristic — swarm intelligence

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

Ukuran huruf

Apa fungsinya?

Optimasi Koloni Semut (ACO) adalah algoritma metaheuristik yang diperkenalkan oleh Marco Dorigo dan rekan-rekannya pada awal 1990-an yang memecahkan masalah optimasi kombinatorial dengan mensimulasikan perilaku mencari makan kolektif semut.

Semut asli meninggalkan jejak feromon di jalur dan secara preferensial mengikuti jejak yang lebih kuat; ACO mengubah mekanisme umpan balik positif ini menjadi prosedur pencarian yang menemukan solusi berkualitas tinggi untuk masalah terstruktur graf seperti Masalah Pedagang Keliling, perutean kendaraan, dan penjadwalan.

Intuisi di balik metode

Bayangkan koloni semut menjelajahi peta mencari rute terpendek antara sumber makanan. Jalur pendek dilalui lebih sering dan menerima lebih banyak deposit feromon, membuatnya semakin menarik bagi semut berikutnya. Selama banyak iterasi, penguatan ini memusatkan lalu lintas pada rute terbaik sementara penguapan menghentikan koloni agar tidak terpaku pada satu jalur terlalu dini. ACO meniru siklus tersebut — populasi semut buatan membangun solusi kandidat, solusi bagus mendepositkan feromon, dan penguapan secara bertahap menghapus memori jalur lama yang inferior sampai koloni konvergen pada solusi berkualitas tinggi.

Sejarah

Kerangka kerja Optimasi Koloni Semut diperkenalkan oleh Marco Dorigo dalam disertasi doktoralnya tahun 1992, mengambil inspirasi dari pengamatan bagaimana koloni semut asli menemukan jalur terpendek melalui komunikasi feromon stigmergik. Algoritma konkret pertama, Ant System (AS), diterbitkan bersama Maniezzo dan Colorni pada tahun 1996. Pada tahun 1997 Dorigo dan Gambardella menerbitkan Ant Colony System (ACS), yang memperkenalkan pembaruan feromon lokal dan aturan eksploitasi yang lebih agresif, secara substansial meningkatkan kinerja pada Masalah Pedagang Keliling. Monograf MIT Press tahun 2004 oleh Dorigo dan Stützle menyatukan kerangka kerja ACO dan menjadikannya cabang utama kecerdasan kawanan. ACO sejak itu diperluas ke domain kontinu (ACOR), masalah multi-objektif (MOACO), dan graf dinamis.

Kapan digunakan

ACO cocok untuk masalah optimasi kombinatorial yang dapat dinyatakan sebagai tugas pencarian jalur atau penugasan pada graf — contoh klasik termasuk Masalah Pedagang Keliling, perutean kendaraan, penjadwalan job-shop, dan perutean jaringan. Ia menerima variabel keputusan kontinu dan kategorikal ketika masalah dikodekan dengan tepat. Tidak ada asumsi normalitas yang diperlukan dan tidak ada batasan ukuran sampel minimum; masukan yang relevan adalah struktur graf yang terdefinisi dengan baik dan anggaran iterasi yang memadai (biasanya beberapa ratus hingga beberapa ribu iterasi). ACO sangat kompetitif ketika heuristik domain tersedia untuk memandu semut. Jika kurang dari sekitar 100–200 iterasi dapat dianggarkan, Pencarian Tabu adalah alternatif yang lebih disukai.

Batasan dan pertimbangan

  • Membutuhkan anggaran iterasi yang cukup; dengan terlalu sedikit iterasi, jejak feromon tidak dapat diandalkan dan kualitas solusi menurun.
  • Tiga parameter utama — α, β, dan ρ — harus disetel; nilai yang dipilih dengan buruk dapat menyebabkan konvergensi dini atau stagnasi.
  • Konvergensi bisa lambat pada graf yang sangat besar karena sinyal feromon tersebar di banyak sisi.
  • Tidak secara alami cocok untuk masalah optimasi kontinu tanpa pengkodean graf.

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

Kelebihan

  • Menangani ruang pencarian kombinatorial diskrit yang besar yang tidak dapat dipecahkan oleh metode eksak.
  • Pencarian berbasis populasi memungkinkan paralelisme implisit — beberapa solusi kandidat dieksplorasi secara bersamaan.
  • Pengetahuan domain (heuristik η) dapat disuntikkan langsung ke dalam aturan transisi untuk mempercepat konvergensi.
  • Mekanisme feromon umpan balik positif secara alami memfokuskan pencarian pada wilayah yang menjanjikan dari waktu ke waktu.
  • Tahan terhadap restrukturisasi masalah: penambahan atau penghapusan node/sisi graf tidak memerlukan penurunan kembali algoritma.

Penerapan

  • Masalah Pedagang Keliling (TSP) dan perutean kendaraan — menemukan tur biaya minimum di seluruh kota atau titik pengiriman.
  • Penjadwalan job-shop dan open-shop — menugaskan operasi ke mesin untuk meminimalkan makespan atau latensi.
  • Perutean jaringan dalam telekomunikasi — adaptasi jalur paket secara dinamis untuk meminimalkan kemacetan.
  • Optimasi rantai pasokan dan logistik — penugasan gudang, pengurutan pengiriman terakhir.
  • Desain teknik — pemilihan parameter dan masalah tata letak komponen yang dikodekan sebagai ruang pencarian diskrit.

Cara kerjanya

Cara kerjanya

1

Masalah optimasi dikodekan sebagai graf: node mewakili titik keputusan (misalnya, kota, tugas, operasi) dan sisi membawa dua bobot — tingkat feromon τ yang diperbarui setiap iterasi dan nilai heuristik η yang berasal dari pengetahuan domain (misalnya, kebalikan dari jarak). Graf ini adalah lingkungan bersama tempat semua semut berkomunikasi secara tidak langsung.

2

Setiap semut buatan membangun solusi lengkap dengan melintasi graf. Di setiap node, ia secara probabilistik memilih sisi berikutnya sesuai dengan aturan transisi yang menyeimbangkan tingkat feromon (dipangkatkan α) dan daya tarik heuristik (dipangkatkan β). α yang lebih tinggi mendukung eksploitasi jalur bagus yang diketahui; β yang lebih tinggi meningkatkan ketergantungan pada pengetahuan spesifik masalah. Hasilnya adalah populasi solusi kandidat yang diproduksi secara paralel setiap iterasi.

3

Setelah semua semut menyelesaikan tur mereka, tingkat feromon disesuaikan dalam dua langkah. Pertama, penguapan mengurangi feromon setiap sisi sebesar faktor (1 − ρ), mencegah akumulasi tak terbatas dan menjaga pencarian agar tidak terkunci terlalu dini. Kedua, semut mendepositkan feromon pada sisi yang mereka gunakan; solusi yang lebih baik mendepositkan lebih banyak, memperkuat jalur yang lebih pendek atau berkualitas lebih tinggi. Varian Ant Colony System (ACS) juga menerapkan pembaruan feromon lokal selama konstruksi untuk mendiversifikasi pencarian.

4

Prosedur diulang sampai kriteria penghentian terpenuhi — biasanya jumlah iterasi maksimum atau ambang batas stagnasi (tidak ada peningkatan selama sejumlah iterasi yang ditetapkan). Solusi terbaik yang ditemukan di semua iterasi dikembalikan. Jika anggaran iterasi terlalu kecil, koloni mungkin tidak membentuk jejak feromon yang andal dan hasilnya menurun menjadi pencarian yang hampir acak; dalam kasus tersebut disarankan untuk kembali ke Pencarian Tabu.

Kesalahan umum

  • Menjalankan terlalu sedikit iterasi (aturan praktis umum adalah setidaknya beberapa ratus) — koloni tidak pernah membentuk jejak feromon yang stabil, menghasilkan solusi yang hampir acak; beralih ke Pencarian Tabu jika anggaran sangat ketat.
  • Menetapkan tingkat penguapan ρ terlalu rendah — feromon lama terakumulasi, koloni terpaku pada jalur suboptimal sejak dini, dan keragaman runtuh; tingkatkan ρ atau gunakan mekanisme reset feromon.
  • Mengabaikan informasi heuristik (β = 0) — algoritma menjadi murni didorong oleh feromon, yang lambat dan tidak dapat diandalkan pada awalnya ketika jejak tidak terinformasi.
  • Menerapkan ACO pada masalah kontinu tanpa pengkodean graf yang tepat — aturan transisi probabilitas bergantung pada graf diskrit; pemetaan langsung variabel bernilai riil tanpa diskretisasi atau varian ACO yang sesuai (misalnya, ACOR) menghasilkan hasil yang buruk.
  • Gagal melacak solusi global terbaik di semua iterasi — pembaruan feromon hanya berdasarkan semut terbaik iterasi saat ini kehilangan yang terbaik secara keseluruhan yang ditemukan.

Pertanyaan yang sering diajukan

Bagaimana ACO berbeda dari Algoritma Genetik?

Keduanya adalah metaheuristik berbasis populasi, tetapi mereka berbeda dalam cara solusi berevolusi. Algoritma Genetik mempertahankan populasi solusi lengkap dan menggunakan operator persilangan dan mutasi untuk menciptakan keturunan. ACO mempertahankan matriks feromon — memori bersama — dan setiap semut membangun solusi baru dari awal yang dipandu oleh memori tersebut. ACO umumnya lebih alami untuk masalah pencarian jalur dan pengurutan, sementara Algoritma Genetik berlaku luas untuk optimasi berkode riil dan biner.

Nilai apa yang harus saya gunakan untuk α, β, dan ρ?

Benchmark kanonik pada TSP menunjukkan α ≈ 1, β ≈ 2–5, dan ρ ≈ 0.02–0.1 sebagai titik awal yang masuk akal (Dorigo & Stützle, 2004). β yang lebih tinggi meningkatkan pengaruh heuristik (berguna ketika pengetahuan domain dapat diandalkan); ρ yang lebih tinggi meningkatkan penguapan dan keragaman tetapi dapat memperlambat konvergensi. Parameter ini bergantung pada masalah dan harus disetel secara sistematis, misalnya dengan pencarian grid kecil atau optimasi Bayesian.

Bisakah ACO memecahkan masalah optimasi kontinu?

ACO standar dirancang untuk ruang pencarian diskrit yang terstruktur graf. Masalah kontinu dapat diatasi dengan ACOR (Ant Colony Optimization for Continuous Domains), yang menggantikan matriks feromon dengan arsip solusi dan fungsi kepadatan probabilitas. Untuk masalah yang murni kontinu tanpa pengkodean graf alami, alternatif seperti Particle Swarm Optimization atau Differential Evolution mungkin lebih mudah diterapkan.

Berapa banyak semut dan iterasi yang biasanya dibutuhkan?

Tidak ada jawaban universal, tetapi titik awal praktis adalah menetapkan jumlah semut sama dengan jumlah node dalam graf dan berjalan selama beberapa ratus iterasi. Deteksi stagnasi — berhenti ketika solusi terbaik belum membaik selama jumlah iterasi tetap — dapat menghemat komputasi. Jika anggaran ketat kurang dari sekitar 100–200 iterasi diberlakukan, ACO kemungkinan tidak akan menghasilkan hasil yang andal; Pencarian Tabu adalah pilihan yang lebih baik dalam rezim tersebut.

Metode terkait

Sumber

  1. Dorigo, M. & Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

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

    ISBN: 9780262042192
    Disalin.