A proposal for an improved version of EigenAnt algorithm with performance evaluation on combinatorial optimization problems

Abstract

The EigenAnt algorithm has recently been introduced to solve the problem of finding the shortest path between two nodes by using dynamics involving local pheromone evaporation. This algorithm has a mathematical proof of convergence to the shortest path between two nodes. In this thesis, the stability and parameter impact analysis of EigenAnt algorithm applied to N-node Binary Chain Problems is carried out. Motivated by this analysis, an improved EigenAnt algorithm is proposed, in which the exploration of different stable equilibria and speed of convergence to them can be tuned separately. A comparative analysis of Improved EigenAnt algorithm with its predecessor EigenAnt and other Ant Colony Optimization algorithms is performed for combinatorial Routing Network shortest path problems. In addition, the application of the proposed Improved EigenAnt algorithm to Multidimensional Knapsack Problems is investigated, by modeling these problems as an N-node Binary Chain shortest path problems with constraints. Local pheromone evaporation and fast convergence features of the EigenAnt algorithm are advantageous for tracking the optimal solutions of dynamic optimization problems in which the problem instances, objective function and constraint parameters change over time. An experimental investigation of the application of the proposed Improved EigenAnt algorithm to track the optimal Dynamic Routing Networks and Dynamic Multidimensional Knapsack problems is another contribution of this thesis.