Jelaskan mengenai Max-min Ant System dan Ant Colony System


Max-min Ant System

Algoritma Max-min ant system merupakan algoritma yang dibangun sebagai pendekatan alternatif dan perbaikan untuk algoritma koloni semut (Ant Colony Optimization). Algoritma koloni semut menggunakan sebuah model yang dihasilkan dari pengamatan tingkah laku semut sesungguhnya, dan menggunakan model tersebut sebagai inspirasi untuk merancang sebuah algoritma untuk menyelesaikan masalah. Ide utama dari algoritma ini adalah menerapkan prinsip pengorganisasian mandiri yang dilakukan semut sesungguhnya pada populasi artificial agent untuk menyelesaikan masalah komputasional.

Algoritma MAX-MIN ant system memiliki cara kerja yang hampir sama dengan algoritma koloni semut. Pada setiap iterasi, algoritma melibatkan sejumlah artificial ant untuk membentuk solusi. Setiap artificial ant memilih jalur secara probabilistik untuk menuju solusi dengan menggunakan informasi stigmergy berupa jejak feromon. Feromon merupakan zat kimia yang disekresikan semut sesungguhnya untuk berkomunikasi dengan lingkungan dan semut lainnya.

Perbedaan algoritma MAX-MIN ant system dengan algoritma koloni semut terletak pada bagaimana kedua algoritma mengolah informasi jejak feromon, melakukan local search dan aturan meng-update jejak feromon. Selain itu, perbedaan lainnya adalah algoritma max-min ant system menggunakan batas atas dan batas bawah untuk nilai feromon.

Ant Colony System

Ant Colony System (ACS) adalah sebuah metodologi yang dihasilkan melalui pengamatan terhadap semut. Pada algoritma ACS, semut berfungsi sebagai agen yang ditugaskan untuk mencari solusi terhadap suatu masalah optimisasi. ACS telah diterapkan dalam berbagai bidang, salah satunya adalah untuk mencari solusi optimal pada Traveling Salesman Problem (TSP). Dengan memberikan sejumlah n titik, TSP dapat didefinisikan sebagai suatu permasalahan dalam menemukan jalur terpendek dengan mengunjungi setiap titik yang ada hanya sekali.

Secara informal, ACS bekerja sebagai berikut: pertama kali, sejumlah m semut ditempatkan pada sejumlah n titik berdasarkan beberapa aturan inisialisasi (misalnya, secara acak). Setiap semut membuat sebuah tur (yaitu, sebuah solusi TSP yang mungkin) dengan menerapkan sebuah aturan transisi status secara berulang kali. Selagi membangun turnya, seekor semut juga memodifikasi jumlah pheromone (sejumlah informasi yang ditinggalkan oleh semut di tempat yang dilalui dan menandai jalur tersebut) pada ruas-ruas yang dikunjunginya dengan menerapkan aturan pembaruan pheromone lokal. Setelah semua semut mengakhiri tur mereka, jumlah pheromone yang ada pada ruas-ruas dimodifikasi kembali (dengan menerapkan aturan pembaruan pheromone global). Dalam membuat tur, semut ‘dipandu’ oleh informasi heuristik (mereka lebih memilih ruas-ruas yang pendek) dan oleh informasi pheromone. Sebuah ruas dengan jumlah pheromone yang tinggi merupakan pilihan yang sangat diinginkan. Kedua aturan pembaruan pheromone itu dirancang agar semut cenderung untuk memberi lebih banyak pheromone pada ruas-ruas yang harus mereka lewati.

Belum ada Komentar untuk "Jelaskan mengenai Max-min Ant System dan Ant Colony System"

Posting Komentar

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel