An Evolutionary Algorithm Using Utility Function as Evolution Directing Function for the Traveling Salesman Problem

摘要

The Traveling Salesman Problem is a typical NP-Hard combinatorial optimization problem. This paper proposes an evolutionary algorithm based on multi-players game theory (EAMG) for the TSP. EAMG transforms TSP to an n-person game, through agents' rational behavior to optimize the solution of problem. This paper introduces in detail the design and experiments of EAMG, and analyzes its ability and time complexity, and also compares our algorithm with some other optimization algorithms. The theoretical analysis and experiment results show that EAMG has a good ability of problem solving.