A Modified Elastic Net Algorithm for Traveling Salesman Problem
HU Hong-ping · Journal of North China Institute of Technology · 2005
The modified elastic net algorithm for finding solutions to the traveling salesman problem (TSP) is introduced. The elastic net method is basically a gradient descent algorithm that will attempt to take the best path to the nearest minimum, whether global or local. If a local minimum is reached, the network will fail to learn. This paper introduces a gradient ascent learning algorithm of the elastic net for TSP. The learning algorithm is that the elastic net minimizes the path through cities. The procedure is equivalent to gradient descent of an energy function; and lends to a local minimum of energy that represents a good solution to the problem. Once the elastic net gets stuck in local minima, the gradient ascent algorithm attempts to fill up the valley by modifying parameters in a gradient ascent direction of the energy function. These two phases are repeated until the elastic net gets out of local minima and produces the shorted or better tour through cities. We test the algorithm on a set of TSP. For all instances, the modified algorithm is showed to be capable of escaping from the elastic net local minima and producing optimal tours or more meaningful tours than the original elastic net.