Solving TSP Using Improved Elitist Ant System Based on Improved Pheromone Strategy and Dynamic Candidate List

Rahul Karmakar, Ramkrishna Mitra, Avishek Dey, Vaswati Chakraborty, Arabinda Nayak

Abstract


Ant colony optimization is a technique for optimization that was introduced by Marco Dorigo in the early 1990’s. The inspiring source of ant colony optimization is the foraging behaviour of real ant colonies. The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. TSP is one of the most famous NP HARD combinatorial optimization (CO) problems and which has wide application background. Combinatorial optimization (CO) is a topic that consist of finding an optimal object from a set of object. Ant colony optimization which has been proven a successful technique and applied to a number of combinatorial optimization problems and taken as one of the high performance computing methods for travelling salesman problem (TSP). But ACO algorithm costs too much time to convergence and traps in local optima in order to find an optimal solution for TSP problems. In this paper we propose an improved ant colony optimization algorithm with two highlights. First, candidate set strategy is adapted to rapid convergence speed. Second, the adaptive adjustment pheromone strategy is used to make relatively uniform pheromone distribution to balance the exploration and exploitation between the random search of ant.

Full Text:

PDF

References


Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm (Zar Chi Su SuHlaing and May Aye Khine, Member, IACSIT)

A Modified Ant Colony Algorithm for Traveling Salesman Problem (X. Wei, L. Han, L. Hong)

Solving the Travelling Salesman Problem Using the Ant Colony Optimization (Ivan Brezina Jr. ZuzanaČičková)

An improved ant colony algorithm based on 3-opt and chaos for travelling salesman problem (Qingping Yu1 ,Xiaoming You1 and Sheng Liu2 )

Ant Colony Optimization for the Traveling Salesman Problem Based on Ants with Memory (Bifan Li1, LipoWang and Wu Song)

An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem (Zar Chi Su SuHlaing, May Aye Khine)

An Improved Ant Colony Optimization Algorithm for Solving TSP (Yimeng Yue1 and Xin Wang)

Parameter Optimization of SVM Based on Improved ACO for Data Classification (Wen Chen and Yixiang Tian)

Elitist Ant System for Route Allocation Problem (SORIN C. NEGULESCU, CONSTANTIN OPREAN, CLAUDIU V.KIFOR, ILIE CARABULEA)

A. Colomi, M. Dorigo, V. Maniezzo, “Distributed optimization by ant colonies,” Proceedings of the 1stEuropean Conference on Artificial Life, pp.134-142, 1991.

M. Dorigo, V. Maniezzo and A. Colorni. “Ant System: Optimization by a colony of cooperating Agents,” IEEETransactions on Systems, Man, and Cybernetics, Part B, vol.26, no.2, pp. 29–41,1996.

T. Stützle and H.H. Hoos, “Improving the Ant System: A detailed report on the MAX–MIN Ant System,” FG Intellektik, FB Informatik, TU Darmstadt, Germany, Tech. Rep. AIDA–96–12, Aug. 1996.

M. Dorigo and L.M. Gambardella. “Ant Colony System: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp.53–66, 1997.

D. X. Yu, “Hybrid ant colony optimization using memetic algorithm for traveling salesman problem,” in Proceedings of the 2007 IEEESymposium on Approximate Dynamic Programming and Reinforcement Learning (ADPRD 2007).

L. Min and J. Yant, “A shortest path routing based on ant algorithm,”Journal of Communication and Computer, ISSN1548-7709, USA, September 2005.

M. Dorigo and L. M. Gambardella, “The colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, April, 1997.

M. Dorigo, M. Birattari, and T. Stuzle, “Ant colony optimization, artificial ants as computational intelligence technique,” IEEE computational intelligence magazine, November 2006.

TSPLIB Web Page, available:

An ant colony optimization method for generalized TSP problem (Jinhui Yang, Xiaohu Shi, Maurizio Marchese, Yanchun Liang) March 2008.

Solving the Travelling Salesman Problem Using the Ant Colony Optimization. Management Information Systems, Vol. 6 (2011), No. 4, pp. 010-014, September 2011.

Ant Colony Optimization Algorithm for Solving the Provider - Modified Traveling Salesman Problem. (Krzysztobaranowski, Iwona Poźniak-Koszałka, Andrzej Kasprzak, Leszek Koszałka) 201

A Novel Approach To Solve Tsp Using Ant Colony Optimization (Jyoti Garg, Renu Singla M.Tech Student, Dept. of CS E, SRCEM, Palwal, India Assistant Prof., Dept. Of CSE, SRCEM, Palwal, India) May 2015.


Refbacks

  • There are currently no refbacks.


MAYFEB Journal of Electrical and Computer Engineering
MAYFEB TECHNOLOGY DEVELOPMENT
Toronto, Ontario, Canada