Saya seorang siswa yang mengerjakan simulator koloni semut untuk proyek kursus. Algoritma untuk itu adalah (jelas) algoritma koloni semut. Saya tahu ada berbagai bentuk algoritma tetapi semuanya terlalu rinci secara matematis untuk kami sehingga kami mengambil pendekatan yang kami miliki:
- Semut dilahirkan di koloni dan harus mengumpulkan makanan dari sumber untuk mempertahankan koloni.
- Semua semut serupa.
- Area tempat semut bergerak adalah kisi 1000x1000, sehingga setiap titik kisi berfungsi sebagai titik yang valid bagi semut untuk ditempati. Sekarang, semua algoritma yang saya temui melibatkan perawatan simpul dan tepi secara terpisah tetapi karena kami membatasi pergerakan semut hanya ke empat arah (atas, bawah, kiri, kanan) saya kira tidak masalah di mana kami meletakkan feromon.
- Poin grid yang disebutkan di atas menyimpan feromon.
- Seekor semut menjatuhkan feromon hanya jika ia membawa makanan.
- Untuk semut pada suatu posisi (i, j), ia memutuskan di mana harus bergerak pada langkah berikutnya dengan mengambil jumlah feromon pada empat simpul yang berdekatan ke dalam rumus probabilistik sederhana, yaitu probabilitas perjalanan ke sebuah simpul diberikan oleh (Jumlah feromon pada simpul yang berdekatan tertentu) / (jumlah jumlah feromon dalam 4 simpul yang berdekatan).
- Seekor semut tidak dapat melakukan perjalanan kembali ke posisi asalnya. Itu hanya dapat dilakukan jika berada di lokasi yang memiliki makanan atau di koloninya.
Sekarang kekhawatiran saya adalah (dan apa yang sebenarnya terjadi dalam program kami) bahwa ketika seekor semut PERTAMA mencapai posisi yang memiliki makanan dan mengambilnya, maka dengan cara algoritma kami bekerja, ia dapat bergerak ke mana saja! Ini karena ia hanya akan meninggalkan jejak feromon, setelah memiliki makanan dan tidak sebelum dan karena itu adalah semut pertama, tidak ada jejak yang ada.
Jika semut dapat bergerak ke mana saja, semut yang mencapai sumber makanan setelahnya juga sebagian besar akan cenderung mengikutinya. BAHKAN JIKA itu tidak bergerak kembali ke arah koloni. Ini mengalahkan tujuan dari keseluruhan algoritma.
Jadi pertanyaan saya adalah
- Apakah kekhawatiran di atas valid? Jika tidak, lalu mengapa? Jika ya, lalu bagaimana cara mengatasinya?
- Apakah kita perlu membuat beberapa perubahan dalam pemahaman dasar kita tentang algoritma untuk benar-benar membuatnya bekerja?
- Apa hal-hal halus dan penting lainnya yang mungkin terlewatkan oleh pemula seperti saya dalam kasus ini?
sumber
Jawaban:
Ini bukan cara kerja ACO. ACO hanya menjatuhkan feromon setelah semut bergerak di semua titik di grid. Anda kemudian mengevaluasi sesuatu (mungkin total waktu tempuh) dan kemudian menjatuhkan feromon untuk semut yang baik, dan ulangi.
Mereka tidak pindah ke vertex yang sama dua kali, umumnya, meskipun Anda dapat menyesuaikan ini untuk kekhususan implementasi.
Feromon tidak jatuh setiap gerakan, mereka turun setelah mereka bergerak kemana-mana dan ada sesuatu yang dievaluasi untuk menentukan semut mana yang lebih baik. Semut yang lebih baik daripada menjatuhkan phereomones (mungkin semut 25% terbaik).
sumber
Implementasi yang saya lihat dari orang lain, dan yang saya tulis sendiri, selalu membuat semut melepaskan feromon di sepanjang jalan yang ditempuh untuk mendapatkan makanan, begitu mereka mencapai makanan. Artinya, semut berbaris dari koloni mereka ke makanan setelah berjalan secara acak; jalur yang diikuti oleh semut dari koloni ke makanan kemudian ditandai menggunakan feromon hanya setelah semut berhasil mencapai makanan. Perjalanan kembali tidak disimulasikan secara eksplisit. Secara umum, banyak semut menjalankan programnya sebelum feromon disimpan untuk iterasi saat ini. Feromon kemudian dikerahkan untuk jalur yang sukses, dan babak baru dimulai.
Biasanya, peluang semut untuk melangkah ke simpul tertentu diberi bobot oleh jumlah feromon beberapa kali "kebaikan". Misalnya, ukuran kebaikan mungkin kira-kira seperti kebalikan dari jarak antara semut dan makanan - ini akan membuat semut mencoba bergerak ke arah makanan, terlepas dari endapan feromon sebelumnya. Kebaikan dapat ditimbang lebih lanjut untuk memperhitungkan faktor-faktor lain, misalnya beberapa node mungkin lebih mudah untuk bepergian daripada yang lain. Dan seperti yang ditunjukkan oleh enderland, biasanya ada beberapa bentuk "seleksi" jalur setelah semua semut berhasil menjalankan programnya , di mana hanya sebagian dari jalur "terbaik" yang dipilih untuk deposit feromon. Namun, Anda harus tetap mendapatkan jalur yang masuk akal bahkan tanpa seleksi,
sumber