Combining new Fast Opposite Gradient Search with Ant Colony Optimization for solving travelling salesman problem

Most of the discrete optimization techniques based on evolutionary computing did not deploy and involve the actual geometrical structure of objective function in the process of generating new population. The candidate solutions are selected by considering only a set of high values of objective function which may not lead to the best solutions. A new evolutionary optimization algorithm based on the actual manifold of objective function and fast opposite gradient search was proposed to improve the accuracy and speed of solution finding. The algorithm is divided into two phases. The first phase searches the best candidate solutions by using our Fast Opposite Gradient Search on the manifold of objective function. The second phase applies Ant Colony Optimization to improve the candidate solutions. The problem of travelling salesman was experimented and the objective function based on Hopfield and Tank׳s was adopted. To demonstrate the effectiveness and efficiency of the proposed algorithm, the benchmark problems from TSPLIB were tested and compared with the techniques of Tabu Search, GAs, PSO, ACO, PS–ACO and GA–PSO–ACO. The results showed that our algorithm achieved shorter distances in all cases within fewer generations.