Embedding Malaysian House Red Ant Behavior into an Ant Colony System

Abstract

Problem statement: Ant Colony System (ACS) is the most popular algorithm used to find a shortest path solution in Traveling Salesman Problem (TSP). Several ACS versions have been proposed which aim to achieve an optimum solution by adjusting pheromone levels. However, it still has a room on an improvement. This research aims to improve the algorithm by embedding individual Malaysian House Red Ant behavior into ACS. Approach: Modeling individual ants' ability reconstructing a path can provide a general idea on how such behavior can improve existing basic ACS ability in finding solution. This study presents a model of Dynamic Ant Colony System with Three Level Update (DACS3) which developed by embedding such behavior into ACS. The three level phases of pheromone updates are: local construction, local reinforcement and global reinforcement. The performance of DACS3 is measured by its shortest distance and time taken to reach the solution against several ant colony optimization algorithms (ACO) on TSP ranging from 14 to 100 cities by running the algorithm in c language. Results: The result shows that DACS3 has reached the shortest distance benchmark for dataset 14, 30 and 57 and has 0.5% differences for data set 100. While, others ACO manage to reach for data set 14 and 30 only and reached about 2.5% differences for data set 100. For dataset 57, DACS has reached 4.6% differences whilst ACS has reached 2.5% differences. Conclusion: Embedding a simple behavior of a single ant into ACS influences an achievement to reach an optimal distance and also can perform considerably faster compare to other ACO's algorithms.