A more robust ant colony learning algorithm : with application to travelling salesman problem

Graph problems model many real life applications, where the quantity of the nodes often changes with time. In such graphs, the evaluation of shortest tour is important as various guiding and navigation systems use this information. Nodes of a graph, in many applications, often change over time, and evaluation of shortest tour is essential whenever a new node is added or deleted. We propose an algorithm that deals with such situations. We have used the Ant System with a different meta-heuristics, to find the shortest tour in a graph. We have analyzed the performance of our proposed algorithm with other algorithms by using the problem instances given in TSPLIB. The proposed modification to the Ant System heuristics will also work for directed and non-fully connected graphs. We show the use of meta-heuristics that make our algorithm free from stagnation, that is, we prevent the ants from taking up the same tour repeatedly which helps to continuously search for better results. Our approach further adopts a method that is a modification to Gallants Technique, to choose the appropriate convergence within the reasonable computation time.'

Name thesis:degree_name

Computer Engineering

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Year

2010

Author dc:creator

• Nandina, Viswanath

Contributors dc:contributor

• Heileman, Gregory L.
• Verzi, Stephen J.
• Ghani, Nasir

• Ant algorithms
• Traveling-salesman problem--Computer simulation.

Language dc:language

English

Repository record dc:identifier

https://digitalrepository.unm.edu/ece_etds/187

OAI identifier oai:identifier

oai:digitalrepository.unm.edu:ece_etds-1186