Ant Colony Optimization (ACO) Algorithm to solve Numericcal Optimization Problem

1. Introduction

       In the 1990’s, Ant Colony Optimization was introduced as a novel nature-inspired method for the solution of hard combinatorial optimization problems. The Ant Colony Algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations [1]. Initially proposed by Marco Dorigo in 1992 in his PhD thesis, the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants. From a broader perspective, ACO performs a model-based search and shares some similarities with estimation of distribution algorithms. The ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs [2]. Artificial Ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of Artificial Ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing. The burgeoning activity in this field has led to conferences dedicated solely to Artificial Ants, and to numerous commercial applications by specialized companies such as AntOptima. Ant colony optimization is a class of optimization algorithms modeled on the actions of an ant colony. Artificial ‘ants’ (e.g. simulation agents) locate optimal solutions by moving through a parameter space representing all possible solutions. Real ants lay down pheromones directing each other to resources while exploring their environment. The simulated ‘ants’ similarly record their positions and the quality of their solutions, so that in later simulation iterations more ants locate better solutions.[4] One variation on this approach is the bees algorithm, which is more analogous to the foraging patterns of the honey bee, another social insect [3].

        In the natural world, ants of some species (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but instead to follow the trail, returning and reinforcing it if they eventually find food (see Ant communication). Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength [4]. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over more frequently, and thus the pheromone density becomes higher on shorter paths than longer ones. Pheromone evaporation also has the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained. The influence of pheromone evaporation in real ant systems is unclear, but it is very important in artificial systems. The overall result is that when one ant finds a good (i.e., short) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leads to many ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with “simulated ants” walking around the graph representing the problem to solve [5].

2. Life Cycle of Ant Colony Optimization Algorithm

       The lifecycle of ants is based on 4 stages of the development: egg → larva → pupa → adult. Eggs are of microscopic size and white colour. Next stage in the development is larva – larvae are legless and fragile and need to be protected/taken care of by worker ants. Pupae are similar to adults, but they are immobile, soft and of a white colour. The last stage of the development is an adult ant. Caste system is remained in colonies and we can distinguish two types of ants: 1. Reproductive – queen(s) and males and 2. Non-reproductive – workers and immature (ants on earlier stages of development) [6].

     Colonies are structured and the division of labour is crucial for the colony to survive. The queen is responsible for laying eggs. Workers are the most common ants seen by people and have a wide range of tasks. They gather and storage food, bring it to immature and defend the nest and clean it from the remnants.

     The queen is the most important ant and her function is to lay thousands of eggs to ensure the continuity of the colony. Queens mate only once and then are able to reproduce throughout the while life. Therefore males are only needed to mate the queen and most of them die after mating [7].

2.1. Structure of Ant

      Ants, like all insects, have jointed legs, three body parts (the head, thorax and abdomen), a pair of antennae, and a hard exoskeleton. The exoskeleton is made up of a material that is very similar to our fingernails. Ants range in color from yellow to brown to red to black. Some ants have a stinger and some can even inject poisonous acid from the stinger (the stinger is at the tip of the abdomen, the rear body segment) [8]. Ants can also bite using their jaws (mandibles). Ants range in size from about 0.08 inch (2 mm) to up to about 1 inch (25 mm) long.

Abdomen – The abdomen is the segmented tail area of an ant. It contains the heart,Malpighian tubules, reproductive organs, and most of the digestive system (foregut, hindgut and rectum). It is protected by an exoskeleton.

Antennae – Ants have two jointed antennae. They are sensory appendages attached to the head.

Compound eye – Ants have two compound eyes. These eyes are made up of many hexagonal lens/corneas which focus light from each part of the insect’s field of view onto a rhabdome (the equivalent of our retina) [9].

Head – The head of an ant (or any insect) is the location of its brain, two compound eyes, its proboscis, pharynx (the start of the digestive system), the point of attachment of its two antennae, etc.

Jointed Leg – Ants, like all insects, have six jointed legs.

Thorax – The thorax is the chest area of an insect (including ants). The thorax is divided into three segments; on each segment is a pair of legs. The thorax contains the muscles that make the legs move [10].

3. Ant Colony Optimization Algorithm (ACO)

     The inspiring source of ACO is the foraging behavior of real ants. When searching for food, ants initially explore the area surrounding their nest in a random manner. As soon as an ant finds a food source, it evaluates it and carries some food back to the nest. During the return trip, the ant deposits a pheromone trail on the ground. The pheromone deposited, the amount of which may depend on the quantity and quality of the food, guides other ants to the food source. Indirect communication among ants via pheromone trails enables them to find shortest paths between their nest and food sources. This capability of real ant colonies has inspired the definition of artificial ant colonies that can find approximate solutions to hard combinatorial optimization problems. The central component of ACO algorithms is the pheromone model, which is used to probabilistically sample the search space [11]. ACO is one of the adaptive meta-heuristic optimization methods inspired by nature which include simulated annealing, GA, and tabu search. ACO is distinctly different from other meta-heuristic methods in that it constructs an entire new solution set (colony) in each generation, while others focus on improving the set of solutions or a single solution from previous iterations. ACO was inspired by the behavior of real ants. Ethologists have studied how blind animals, such as ants, could establish shortest paths from their nest to food sources. The medium that is used to communicate information among individual ants regarding paths is pheromone. A moving ant lays some pheromone on the ground, thus marking the path. The pheromone, while gradually dissipating over time, is reinforced as other ants use the same trail. Therefore, efficient trails increase their pheromone level over time while poor ones reduce to nil [12]. The characteristics of ant colony optimization include:

• A method to construct solutions which balances pheromone trails (characteristics of past solutions) with a problem-specific heuristic (normally, a simple greedy rule),
• Amethod to both reinforce & evaporate pheromone.
• Local (neighborhood) search to improve solutions.

3.1. Steps for Ant Colony Optimization Algorithm

• Initialization process
• Evaluation of the selected subsets
• Construction process
• Update process
• Decision process

3.1.1. Initialization Process

    Initialization of the population is commonly done by seeding the population with random values. The fitness value is proportional to the performance measurement of the function being optimized. The calculation of fitness values is conceptually simple [13]. It can, however, be quite complex to implement in a way that optimizes the efficiency of the GAs search of the problem space. It is this fitness that guides the search of the problem space. Determine the population of ants.  Set the intensity of pheromone trial associated with any feature.  Determine the maximum of allowed iterations.

3.1.2. Evaluation of the selected subsets

    Assign any ant randomly to one feature and visiting features, each ant builds solutions completely. In this step, the evaluation criterion is mean square error (MSE) of the classifier. If an ant is not able to decrease the MSE of the classifier in ten successive steps, it will finish its work and exit. After fitness calculation, the next step is reproduction. Reproduction comprises forming a newpopulation, usually with the sametotal number of chromosomes, by selecting from members of the current population using a stochastic process that is weighted by each of their fitness values [14]. The higher the fitness, the more likely it is that the chromosome will be selected for the new generation.

3.1.3. Construction process

     The basic ingredient of anyACOalgorithm is a constructive heuristic for probabilistically constructing solutions [15]. Aconstructi ve heuristic assembles solutions as sequences of elements from the finite set of solution components.

3.1.4. Update process

     Decrease pheromone concentrations of nodes then, all ants deposit the quantity of pheromone on graph. Finally, allow the best ant to deposit additional pheromone on nodes.

3.1.5. Decision process

     The objective of this module is to find the global best ant so far over all iterations in  and to record the selected consequent combination of this ant once it is found in an iteration [16].

3.2. Flow Chart of ACO

4. Numerical Expression of ACO 

    The Ant Colony Optimization (ACO) Algorithm Numerical Expressions are given [17];

5. Applications of ACO

• Travelling Sales man problem
• Job Shop Scheduling problem[18]
• Network model problem
• Vehicle Routing[19]
• Graph Coloring
• Digital Image Processing
• Quadratic Assignment problem[20]

6. Applications of ACO

• Can be used in dynamic applications
• Positive feedback leads to rapid discovery of good solutions[21]
• Distributed computation avoids permature convergence
• Can search among a population in parallel[22]
• Can adapt to changes such as new distance
• Have guaranteed convergence[23]
• Performance better against other global optimization techniques such as neural net, genetic algorithms, simulated annealing[24]
• The collective interaction of a population of agents
• The greedy heuristic helps find acceptable solution in the early solution in the stages of the search process[25]

Reference

[1] Serra, M. and Venini, P. (2006). On some applications of ant colony optimization metaheuristic to plane truss optimization. Structural and Multidisciplinary Optimization, 32(6), pp.499-506.

[2] Dorigo, M. and Blum, C. (2005). Ant colony optimization theory: A survey. Theoretical Computer Science, 344(2-3), pp.243-278.

[3] LIU, X. (2009). Ant colony algorithm for continuous space optimization. Journal of Computer Applications, 29(10), pp.2744-2747.

[4] Liang, Y. and Smith, A. (2004). An Ant Colony Optimization Algorithm for the Redundancy Allocation Problem (RAP). IEEE Transactions on Reliability, 53(3), pp.417-423.

[5] Huan, Y. (2016). Image Edge Detection Based on Ant Colony Optimization Algorithm. International Journal of Advanced Pervasive and Ubiquitous Computing, 8(1), pp.1-12.

[6] Karaboga, D. and Basturk, B. (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3), pp.459-471.

[7] Lee, Z., Lee, C. and Su, S. (2002). An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem. Applied Soft Computing, 2(1), pp.39-47.

[8] Sun, J. (2013). An Ant Colony Optimization Algorithm for the Press Shop Scheduling Problem. Applied Mechanics and Materials, 321-324, pp.2116-2121.

[9] T’kindt, V., Monmarché, N., Tercinet, F. and Laügt, D. (2002). An Ant Colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 142(2), pp.250-257.

[10] Shelokar, P., Siarry, P., Jayaraman, V. and Kulkarni, B. (2007). Particle swarm and ant colony algorithms hybridized for improved continuous optimization. Applied Mathematics and Computation, 188(1), pp.129-142.

[11] Solimanpur, M., Vrat, P. and Shankar, R. (2004). Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing. European Journal of Operational Research, 157(3), pp.592-606.

[12] Kong, M., Tian, P. and Kao, Y. (2008). A new ant colony optimization algorithm for the multidimensional Knapsack problem. Computers & Operations Research, 35(8), pp.2672-2683.

[13] Yalian, T. (2016). An Improved Ant Colony Optimization for Multi-Depot Vehicle Routing Problem. International Journal of Engineering and Technology, 8(5), pp.385-388.

[14] Aghdam, M., Ghasem-Aghaee, N. and Basiri, M. (2009). Text feature selection using ant colony optimization. Expert Systems with Applications, 36(3), pp.6843-6853.

[15] García-Martínez, C., Cordón, O. and Herrera, F. (2007). A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. European Journal of Operational Research, 180(1), pp.116-148.

[16] Wang, J., Osagie, E., Thulasiraman, P. and Thulasiram, R. (2009). HOPNET: A hybrid ant colony optimization routing algorithm for mobile ad hoc network. Ad Hoc Networks, 7(4), pp.690-705.

[17] Geetha, R. and Umarani Srikanth, G. (2012). Ant Colony Optimization in Different Engineering Applications: An Overview. International Journal of Computer Applications, 49(17), pp.19-25.

[18] Shan, B. and Zhang, D. (2014). Path Planning of Robot Based on Ant Colony Optimization Algorithm. Applied Mechanics and Materials, 614, pp.199-202.

[19] Lee, Z., Su, S., Chuang, C. and Liu, K. (2008). Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Applied Soft Computing, 8(1), pp.55-78.

[20] Huang, S. and Lin, P. (2010). A modified ant colony optimization algorithm for multi-item inventory routing problems with demand uncertainty. Transportation Research Part E: Logistics and Transportation Review, 46(5), pp.598-611.

[21] Rajo-Iglesias, E. and Quevedo-Teruel, O. (2007). Linear array synthesis using an ant-colony-optimization-based algorithm. IEEE Antennas and Propagation Magazine, 49(2), pp.70-79.

[22] Blum, C. (2005). Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operations Research, 32(6), pp.1565-1591.

[23] Chia-Feng Juang, Chun-Ming Lu, Chiang Lo and Chi-Yen Wang (2008). Ant Colony Optimization Algorithm for Fuzzy Controller Design and Its FPGA Implementation. IEEE Transactions on Industrial Electronics, 55(3), pp.1453-1462.

[24] Chandra Mohan, B. and Baskaran, R. (2012). A survey: Ant Colony Optimization based recent research and implementation on several engineering domain. Expert Systems with Applications, 39(4), pp.4618-4627.

[25] Yuren Zhou (2009). Runtime Analysis of an Ant Colony Optimization Algorithm for TSP Instances. IEEE Transactions on Evolutionary Computation, 13(5), pp.1083-1092.