Algoritma Pembenaman Perlakuan Individu Semut (Agen) ke Dalam Sistem Koloni Semut
Zulaiha Ali Othman, MoMohd Helmi Raisaisais, Roslan Ahmad & Abdul Razak Hamdan
ABSTRAK
PSemut adalah suatu hidupan yang terkenal dengan sifat kerjasama antara satu sama lain untuk mendapatkan makanan dan membawa balik makanan tersebut kesarangnya. Kebolehan secara berkoloni terutamanya bagi menghasilkan laluan terbaik untuk mendapatkan makanan telah menjadi sumber inspirasi kepada pembangunan algoritma yang dikenali sebagai Sistem Koloni Semut (SKS). Prinsip kooperasi antara semut adalah tulang belakang kepada pembangunan algoritma ini untuk menghasilkan laluan terdekat dalam Permasalahan Perjalanan Jurujual (PPJ). Phoremone adalah bahan kimia yang dihasilkan oleh semut sebagai perantara untuk mereka berkomunikasi antara satu sama lain. Perlakuan individu semut (Agen) berupaya memanipulasi paras phoremone dan seterusnya membantu SKS menghasilkan penyelesaian terbaik. Tujuan kertas kerja ini adalah untuk memperkenalkan satu algoritma Sistem Koloni Semut Dinamik Pengemaskinian Tiga Paras (SKSD3) yang dibina hasil pembenaman perlakuan individu semut dalam SKS yang ada. Model perlakuan individu semut dicerap daripada hasil beberapa ujikaji terhadap perlakuan seekor semut dalam sistem koloni semut merah Malaysia. Keupayaan SKSD3 diukur dengan membandingkannya dengan beberapa algoritma Koloni Semut set data PPJ julat di antara 14 hingga 100 bandar. Hasil ujikaji menunjukkan bahawa pembenaman perlakuan individual semut dalam SKS telah memperbaiki algorithms tersebut.
Kata kunci: Sistem Koloni Semut, Pengoptimuman, Permasalahan Perjalanan Jurujual.
ABSTRACT
Ants are fascinating creatures that demonstrate the ability to find food and bring it back to their nest. Their ability as a colony, to find paths to food sources has inspired the development of algorithms known as Ant Colony Systems (ACS). The principle of cooperation forms the backbone of such algorithms, commonly used to find solutions to problems such as the Traveling Salesman Problem (TSP). Ants communicate to each other through chemical substances called pheromones. Modeling individual ants’ ability to manipulate this substance can help an ACS find the best solution. This paper introduces a Dynamic Ant Colony System with three-level updates (DACS3) which embeds individual ant behavior(agent) in existing ACS. Experiments were conducted to observe single ant behavior in a colony of Malaysian House Red Ants. Such behaviour was incorporated into the DACS3 algorithm. We benchmarked the performance of DACS3 against several Ant Colony Optimizations (ACO) algorithms on TSP instances ranging from 14 to 100 cities. The result showed that embedding a simple behaviour into an ant improved an ACS algorithm.
Keywords: Ant Colony System, Optimisation, Traveling Sales Problem.
