# Balancing Exploration And Exploitation By An Elitist Ant System With Exponential Pheromone Deposition Rule

Ayan Acharya1, Deepyaman Maiti2, Aritra Banerjee3, Amit Konar4 1,2,3,4Department of Electronics and Telecommunication Engineering, Jadavpur University, Kolkata: 700032 1masterayan@gmail.com, 2deepyamanmaiti@gmail.com, 3aritraetece@gmail.com, 4konaramit@yahoo.co.in Abstract— **The paper presents an exponential pheromone** deposition rule to modify the basic ant system algorithm which employs constant deposition rule. A stability analysis using differential equation is carried out to find out the values of parameters that make the ant system dynamics stable for both kinds of deposition rule. A roadmap of connected cities is chosen as the problem environment where the shortest route between two given cities is required to be discovered. Simulations performed with both forms of deposition approach using Elitist Ant System model reveal that the exponential deposition approach outperforms the classical one by a large extent. Exhaustive experiments are also carried out to find out the optimum setting of different controlling parameters for exponential deposition approach and an empirical relationship between the major controlling parameters of the algorithm and some features of problem environment. Keywords- Ant Colony Optimization, Ant System, Elitist Ant System, Stability Analysis, Exponential Pheromone Deposition. 

## I. Introduction

Ant Colony Optimization (ACO) is a paradigm for designing metaheuristic algorithms for combinatorial optimization problems. While roaming from food sources to the nest and vice versa, ants deposit on the ground a substance called pheromone. Ants can smell pheromone and choose, in probability, paths marked by stronger pheromone concentrations. Hence, the pheromone trail allows the ants to find their way back to the food source or to the nest. ACO algorithm simulates this behavior of ant colony to solve difficult NP hard optimization problems. 

 **Ant System (AS)** is the earliest form of ant colony optimization algorithm that has been modified by numerous researchers till date. **Elitist Ant System (EAS)** model is one such improved model of the primary version of ant system. 

Our paper extends the AS model by introducing an exponential pheromone deposition approach, contrary to the uniform deposition approach used in classical AS algorithms. 

We attempt to solve the deterministic AS dynamics using differential equation. This novel analysis helps in determining the range of parameters in the exponential pheromone deposition rule to confirm stability in pheromone trails. The deterministic solution does not violate the stochastic nature of the AS because a segment of trajectory here is always selected probabilistically. Our previous work [8] was based on stability analysis using difference equation. In this paper, we have employed differential equations which not only characterize the system more precisely but also are more popular than difference equations. The previous paper, with experiments performed over TSP instances, could not at all highlight the philosophy of the non uniform deposition rule. This paper presents sufficient simulation backup to establish the proposed algorithm's superiority over the traditional one. Problem environment is also chosen very cleverly to emphasize the efficacy of the proposed algorithm. Exhaustive experimentations also help find out the suitable values of parameter for which the proposed algorithm works best and from these results we try to ascertain an algebraic relationship between the parameter set of the algorithm and feature set of the problem environment. The paper is structured in 6 sections. In section II, a brief introduction of AS and **EAS** are provided. We formulate a scheme for the general solution of the Ant System in section III. Stability analysis with complete solution for different pheromone deposition rules is undertaken in section IV. 

Performance analyses of the proposed and classical AS are compared in section V on elitist model. Finally, the conclusions are listed in section VI. 

II. ANT SYSTEM AND ELITIST ANT SYSTEM
 The theory of ant system can best be explained in the context of Travelling Salesperson Problem (TSP)([6]). The basic ACO algorithm for TSP can be described as follows:
procedure ACO algorithm for TSPs Ø Set parameters, initialize pheromone and ants' memory while (termination condition not met)
Ø Construct Solution Ø Apply Local Search ( optional) 
Ø Best Tour check Ø Update Trails 
 **end** end ACO algorithm for TSPs 
 **Ant System (AS)** ([1],[2],[3]) basically consists of two levels: 