Applying non-revisiting genetic algorithm to traveling salesman problem

Abstract

In [1], we propose non-revisiting genetic algorithm (NrGA) and apply it to a set of bench mark real valued test functions. NrGA has the advantage that it is non-revisiting, i.e. a visited point will not be visited again. This provides an automatic mechanism for diversity maintenance which does not suffer from premature convergence. Another advantage is that it supports a parameter-less adaptive mutation mechanism. In this paper, we show how NrGA can be adapted to a real world combinatorial optimization problem - the famous traveling salesman problem (TSP). Comparison with genetic algorithm (GA) (with revisits and standard mutation) is made. It is shown that NrGA gives superior performance compared to GA. Moreover, it gives the same stable performance using different types of mutation operators. Moreover, turning off GA's mutation operator but only use the NrGA inherent parameter-less adaptive mutation gives the best performance. © 2008 IEEE.