The Coupled EigenAnt algorithm for shortest path problems

Author

Kaszkurewicz, Eugenius ; Bhaya, Amit ; Jayadeva ; Meirelles da Silva, Joao Marcos

Author_Institution

Dept. of Electr. Eng., Indian Inst. of Technol., New Delhi, New Delhi, India

fYear

2014

fDate

6-11 July 2014

Firstpage

1729

Lastpage

1735

Abstract

This paper introduces an ACO model and associated algorithm, called Coupled EigenAnt, for the problem of finding the shortest of N paths between a source and a destination node. It is based on the recently introduced EigenAnt algorithm, the novelty being that it allows probabilistic path choice on both the forward and return journeys, as well as the fact that it introduces decay of pheromone deposition following a geometric progression. Equilibrium points of the model are calculated and the local stability of the two path synchronous version analyzed. Simulations illustrate the main features of the algorithm.

Keywords

ant colony optimisation; eigenvalues and eigenfunctions; probability; search problems; ACO model; ant colony optimization; coupled eigenant algorithm; equilibrium points; geometric progression; path synchronous version; pheromone deposition; probabilistic path choice; shortest path problems; Approximation algorithms; Heuristic algorithms; Probabilistic logic; Radiation detectors; Shortest path problem; Stability analysis; Vectors;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation (CEC), 2014 IEEE Congress on

Conference_Location

Beijing

Print_ISBN

978-1-4799-6626-4

Type

conf

DOI

10.1109/CEC.2014.6900647

Filename

6900647