| Recently, the Artificial Neural Network (ANN) has been widely researched and applied due to its strong self-study,self-adaptation and self-organization capabilities. In addition, it also has better error toleration,parallel process capabilities and nonlinear function approach capability. The combinatorial optimization problems are one important application field of ANN. The Traveling Salesman Problem (TSP) is a representative combinatorial optimization problem and has been researched by numerous researchers. During the past ten years, the neural network model starts to be used to calculate the TSP and has gained some famous results. This paper focuses on the following aspects:Firstly, I propose a Lagrange object relaxation technique that can obtain a more near-optimal solution for the TSP. It consists of two stages. First, a feasible solution is calculated and second, a more near-optimal solution is calculated by a Hopfield neural network (HNN). The Lagrange object relaxation technique can help the HNN escape from the local minimum by correcting Lagrange multipliers. The Lagrange object relaxation neural network is analyzed theoretically and evaluated experimentally through simulating the TSP. The simulation results based on some TSPLIB benchmark problems show that the proposed method can find 100% valid solutions which are near-optimal solutions.Secondly, I give two improved algorithms of Guided Local Search (GLS), GLS-like algorithm and Objective function Adjustment (OA) algorithm, to improve the local optima of local search. In the GLS-like algorithm, a new penalty principle is proposed to further improve the effectiveness of GLS. The Objective function Adjustment algorithm is an improved algorithm of GLS-like using multipliers which can be adjusted during the search process. The simulation results based on some TSPLIB benchmark problems showed that the OA algorithm could find better solutions than the local search, guided local search, Tabu Search and GLS-like. |
PDF Full Text Request