Embedding Malaysian House Red Ant behavior into an Ant Colony System.

INTRODUCTION

Today's business environment is increasingly complex and dynamic, with substantial flexibility required in operations. This is especially true of the logistics and transportation industry, where the need to deliver on time and to fulfill changes in customer requests makes it important to find the shortest paths for a delivery route. People, as we know, have a reduced ability to see the overall problem, particularly when the problem is relatively complex in term of its size and constraints. However, this inability can be overcome with the help of certain advanced optimization methods, which can aid humans in expediting the process.

The Ant Colony System (ACS) is one the most successful algorithm used in combinatorial optimization problems such as the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), Job-Shop Scheduling Problem (JSP) and Quadratic Assignment Problem (QAP) (1), (6). The algorithm is inspired by the foraging behavior of a colony of ants, which communicate through chemical substances called pheromones, acting as a memory preservation mechanism and providing guidance for ants in searching for shortest paths (2).

The principle of cooperation is the backbone of these algorithms. However, observing the behavior of a single ant can add value to the principle. Manipulating pheromone substances is a simple addition that can help to find the best solution. Therefore, many versions of ACS algorithms have been produced to find the shortest path by using the principle of cooperation among the ants. This study looks at individual ants' behavior in trying to reconnect paths previously laid by the colony when an obstacle is placed on such paths. Such blockages add another level of pheromone updates, which could contribute to faster optimum solutions.

This study concentrates on an improvement of an ACS applied to the TSP domain, as first presented by Marco Dorigo (3). The problem is to find the shortest tour of all the cities, where all cities are connected to each other and visiting each city only once.

MATERIALS AND METHODS

Ant behaviors: Nature is a good source of solutions to problems faced by humans. Ants provide a good example for the case of transporting goods or finding shortest paths. Ants are social insects which cooperate through group communication, laying down chemical substances called pheromones (4) to mark locations that have already been visited. The pheromones also serve as a reference for the return route back to their nest. These pheromones are then used by other ants as an indicator of the best path between the nest and food sources. The amount of pheromone laid determines whether the path is desirable to be taken by others; higher pheromone levels indicate more desirable routes.

Research on social insects began in the early twentieth century, when the South African scientist Eugene Marais (1872-1936) focused his attention on the behavior of termites, which he refers to as White Ants in his research. His research was then picked up by Konrad Lorenz (1903-1989) in his studies of imprinting and instinctive behavior of termites. Although both scientists are considered to be pioneers in the field of Ethology, the scientific studies of animal behavior, they were unaware of the actual mechanics of termite communication (5). The answer to this question was discovered in the 1940s and 1950s when a French biologist named Pierre Paul Grasse investigated how termites communicate. He discovered that social insects react to significant stimuli that activate genetically encoded reactions called stigmergy, which describe as a type of indirect communication that workers stimulated by the performance they achieved (6). The characteristics of stigmergy were also found in single and double bridge experiments on Argentine Ants, where they studied the pheromones laying and following behavior of ants (7).

Margo Dorigo et al. (11) applied the results of these experiments to artificial ants, basing his research on ethologist studies that found ants established shortest paths based on pheromone trails. He took it one step further to study the random movement of ants, which he referred to as autocatalytic behavior, where ants move at random, detect an existing trail, decide to follow and then re-enforce by laying down its own pheromones. …