Comparison of the Hopfield scheme to the hybrid of Lagrange and transformation approaches for solving the traveling salesman problem

摘要

A novel scheme, the hybrid of Lagrange and transformation approaches (Hybrid LT), was proposed by Xu (1994) to solve a combinatorial optimization problem. It separates the constraints into linear-constant-sum constraints and binary constraints. The linear-constant-sum constraints are treated by the Lagrange approach while the binary constraints are transformed into penalty or barrier functions. This paper compares the performance of the Hopfield net and the Hybrid LT based on computer simulations in solving the traveling salesman problem (TSP). The experimental results show that the Hybrid LT is superior to the Hopfield net for greater speed of convergence, higher rate of finding valid solutions and shorter paths found.