Skip to content
Kembali ke hasil pencarian

Algoritma Genetika Berbasis Agen — Pencarian Evolusioner Terdistribusi Melalui Agen Otonom

Diperkenalkan oleh
Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
Tahun
1990s
Jenis
Hybrid evolutionary-agent simulation
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Algoritma Genetika Berbasis Agen (ABGA) mempartisi populasi algoritma genetika di seluruh jaringan agen otonom, masing-masing memelihara sub-populasi lokal dan mengembangkannya secara independen.

Agen secara berkala bertukar individu (migrasi) berdasarkan kedekatan atau aturan komunikasi, memungkinkan eksplorasi paralel ruang pencarian sambil mempertahankan keragaman populasi dan menghindari konvergensi prematur.

Intuisi di balik metode

Algoritma genetika konvensional memperlakukan seluruh populasi sebagai satu kumpulan, yang dapat menyebabkan konvergensi cepat pada optimum lokal karena satu genotipe dominan mengambil alih. Pendekatan berbasis agen malah mendistribusikan sub-populasi ke agen semi-otonom yang diatur dalam topologi lingkungan. Setiap agen menjalankan seleksi, persilangan, dan mutasi lokalnya sendiri, kemudian sesekali berbagi individu berkinerja tinggi dengan agen tetangga. Ini mencerminkan bagaimana spesiasi biologis terjadi di seluruh populasi yang terisolasi secara geografis tetapi kadang-kadang terhubung, membiarkan tekanan evolusioner yang beragam bertindak secara paralel dan menggabungkan solusi di berbagai ceruk.

Sejarah

Algoritma genetika terdistribusi dan paralel muncul pada awal 1990-an ketika para peneliti berusaha mengatasi konvergensi prematur dan memanfaatkan perangkat keras paralel. Adamidis dan Petridis (1996) memformalkan populasi agen yang bekerja sama dengan perilaku evolusioner yang berbeda. Kerangka kerja berbasis agen mendapatkan daya tarik melalui akhir 1990-an dan 2000-an seiring penyebaran pemodelan berbasis agen di seluruh ilmu komputasi, memformalkan model interaksi otonom yang diatur oleh topologi yang sekarang banyak diterapkan dalam optimasi kompleks.

Kapan digunakan

Gunakan ABGA ketika lanskap kebugaran kasar atau multimodal dan GA standar secara konsisten konvergen secara prematur; ketika perangkat keras paralel atau terdistribusi tersedia yang dapat menampung proses agen bersamaan; atau ketika struktur masalah secara alami memetakan ke sub-masalah semi-independen (misalnya, rantai pasokan regional, kebijakan multi-sektor). Juga sesuai ketika mengeksplorasi perilaku algoritma di bawah tekanan evolusioner yang heterogen. JANGAN gunakan ketika masalah memiliki lanskap unimodal tunggal (GA yang lebih sederhana sudah cukup), ketika overhead komunikasi antar-agen mendominasi komputasi, ketika ukuran populasi terlalu kecil untuk dipartisi secara bermakna, atau ketika populasi terpusat diperlukan untuk reproduktibilitas yang tepat.

Batasan dan pertimbangan

  • Penyetelan kebijakan migrasi (laju, topologi, frekuensi) menambahkan hiperparameter yang memerlukan kalibrasi hati-hati dan bergantung pada masalah.
  • Overhead komunikasi antar agen dapat meniadakan manfaat paralelisme dalam lingkungan komputasi latensi tinggi atau yang terhubung longgar.
  • Jaminan konvergensi teoretis lebih lemah daripada GA standar; analisis formal dinamika ABGA tetap menjadi area penelitian terbuka.
  • Mereproduksi hasil memerlukan perbaikan topologi agen, jadwal migrasi, dan benih acak di semua agen, mempersulit replikasi.
  • Jika ukuran sub-populasi terlalu kecil, agen individual rentan terhadap hanyutan genetik terlepas dari migrasi.

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

Kelebihan

  • Mempertahankan keragaman populasi yang lebih tinggi daripada GA panmiktik, mengurangi konvergensi prematur pada lanskap kebugaran yang kasar.
  • Secara alami memanfaatkan infrastruktur komputasi paralel atau terdistribusi untuk masalah optimasi skala besar.
  • Pengaturan operator heterogen per agen memungkinkan eksplorasi dan eksploitasi simultan di berbagai strategi.
  • Migrasi individu yang bugar antar agen memungkinkan rekombinasi lintas-ceruk yang dapat menemukan solusi berkualitas tinggi yang baru.
  • Arsitektur modular memudahkan integrasi heuristik spesifik domain dalam loop evolusi agen individual.
  • Skala dengan baik dengan dimensionalitas masalah ketika sub-populasi dapat dipartisi secara bermakna.

Penerapan

  • Penjadwalan dan logistik: masalah job-shop atau vehicle routing terdistribusi di mana sub-masalah geografis secara alami memetakan ke agen.
  • Optimasi desain teknik: desain struktural atau aerodinamis dengan ruang pencarian multimodal yang mendapat manfaat dari eksplorasi ceruk paralel.
  • Simulasi kebijakan: optimasi parameter kebijakan dalam model simulasi sosial di mana agen mewakili aktor regional atau sektoral.
  • Pencarian hyperparameter pembelajaran mesin: penyetelan evolusioner paralel konfigurasi model di seluruh kluster komputasi terdistribusi.
  • Bioinformatika: prediksi struktur protein dan inferensi jaringan gen pada lanskap kebugaran berdimensi tinggi dan kasar.
  • AI permainan dan robotika: mengembangkan strategi perilaku agen di lingkungan multi-agen dengan dinamika ko-evolusioner.

Cara kerjanya

Cara kerjanya

1

Definisikan topologi agen: tentukan jumlah agen (sub-populasi), struktur lingkungan mereka (cincin, kisi, grafik dunia kecil, atau terhubung penuh), dan protokol komunikasi yang mengatur kapan dan bagaimana agen bertukar individu. Setiap agen adalah entitas komputasi otonom dengan kumpulan kromosomnya sendiri.

2

Inisialisasi sub-populasi lokal setiap agen dengan kromosom yang dihasilkan secara acak (atau solusi yang di-seed). Tetapkan ukuran populasi lokal, operator genetik (jenis dan laju persilangan, laju mutasi), dan mekanisme seleksi (turnamen, roulette, berbasis peringkat) secara independen untuk setiap agen atau seragam di semua agen.

3

Setiap agen secara independen menjalankan beberapa generasi seleksi, persilangan, dan mutasi pada sub-populasi lokalnya. Beroperasi secara paralel (atau pseudo-paralel dalam simulasi sekuensial), agen mengeksplorasi berbagai wilayah ruang solusi di bawah konfigurasi operator yang berpotensi berbeda, mempertahankan keragaman di seluruh sistem.

4

Pada interval migrasi yang ditentukan, agen berbagi subset individu berkinerja terbaik mereka dengan agen tetangga sesuai dengan kebijakan migrasi (misalnya, kirim-terbaik, terima-ganti-terburuk). Laju migrasi dan topologi membentuk keseimbangan antara eksploitasi lokal dan eksplorasi global; migrasi yang terlalu sering merusak keragaman, migrasi yang terlalu jarang menyia-nyiakan arsitektur terdistribusi.

5

Semua kromosom yang diimpor dan berevolusi secara lokal dievaluasi terhadap fungsi kebugaran bersama. Agen dapat menerapkan tekanan seleksi lokal setelah migrasi untuk mengintegrasikan individu yang diterima ke dalam populasi mereka, berpotensi membuang yang kurang bugar. Evaluasi kebugaran adalah biaya komputasi yang dominan.

6

Berhenti ketika kriteria penghentian global terpenuhi (generasi maksimum, konvergensi kebugaran terbaik di seluruh agen, atau waktu yang berlalu). Kumpulkan solusi terbaik yang ditemukan di seluruh agen sebagai keluaran akhir. Laporkan kurva konvergensi per agen untuk mendiagnosis keragaman populasi dan efektivitas migrasi.

Kesalahan umum

  • Menetapkan laju migrasi terlalu tinggi merusak keragaman sub-populasi menjadi kumpulan tunggal de facto, menghilangkan keuntungan utama dari arsitektur agen.
  • Mengabaikan desain topologi lingkungan: topologi yang terhubung penuh menyebabkan konvergensi cepat; cincin dengan frekuensi migrasi yang buruk dapat membuat agen terisolasi dan stagnan.
  • Mengevaluasi kebugaran hanya secara lokal tanpa fungsi kebugaran global bersama menyebabkan agen mengoptimalkan tujuan yang tidak kompatibel.
  • Mencampuradukkan ABGA dengan GA multi-objektif: ABGA adalah varian arsitektur untuk efisiensi pencarian, bukan metode multi-objektif yang melekat — ABGA multi-objektif memerlukan mesin Pareto tambahan.
  • Berhenti pada konvergensi agen individual daripada konvergensi global dapat melewatkan solusi yang lebih baik yang masih berevolusi di agen lain.

Pertanyaan yang sering diajukan

Bagaimana ABGA berbeda dari GA paralel standar?

GA paralel standar biasanya mendistribusikan evaluasi kebugaran dari satu populasi terpusat ke berbagai prosesor. ABGA memberikan setiap agen sub-populasi otonom dengan loop evolusionernya sendiri; interaksi hanya terjadi melalui migrasi eksplisit, bukan melalui kumpulan bersama. Perbedaan ini mempertahankan tekanan selektif independen per agen.

Topologi migrasi apa yang harus saya pilih?

Topologi cincin dan kisi adalah titik awal standar: mereka membatasi aliran migrasi dan mempertahankan keragaman. Topologi dunia kecil (beberapa tautan jarak jauh ditambahkan ke cincin) mempercepat propagasi solusi yang baik tanpa merusak keragaman. Topologi yang terhubung penuh umumnya harus dihindari kecuali Anda menginginkan perilaku konvergensi yang cepat.

Berapa banyak agen dan ukuran sub-populasi apa yang sesuai?

Heuristik umum adalah 16-4 agen dengan ukuran sub-populasi masing-masing 20-50 individu, untuk total populasi yang sebanding dengan yang akan digunakan GA standar. Terlalu sedikit agen meniadakan keuntungan keragaman arsitektur; terlalu banyak agen dengan sub-populasi kecil menderita hanyutan. Penyetelan empiris pada masalah spesifik diperlukan.

Bisakah ABGA digunakan untuk optimasi multi-objektif?

Ya, tetapi mesin Pareto tambahan (seperti peringkat NSGA-II di dalam setiap agen) harus ditambahkan. Arsitektur agen kemudian membantu mempertahankan aproksimasi front Pareto yang lebih beragam. Ini adalah dasar dari varian ABGA multi-objektif.

Apakah ABGA dijamin menemukan optimum global?

Tidak. Seperti semua GA, ABGA bersifat heuristik dan tidak memberikan jaminan optimalitas global. Peningkatan pelestarian keragaman meningkatkan probabilitas menghindari optimum lokal dalam praktik, tetapi jaminan konvergensi tidak lebih kuat daripada GA standar dan merupakan pertanyaan penelitian teoretis yang aktif.

Metode terkait

Sumber

  1. Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.

    Buka referensi publikasi
    Disalin.
  2. Genetic algorithm. Wikipedia.

    Buka referensi publikasi
    Disalin.