Article ID: | iaor20071496 |
Country: | China |
Volume: | 26 |
Issue: | 4 |
Start Page Number: | 235 |
End Page Number: | 238 |
Publication Date: | Aug 2005 |
Journal: | Journal of North China Institute of Technology |
Authors: | Bai Yanping, Hu Hongping |
Keywords: | heuristics, neural networks |
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 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 shortest (or a better) tour through cities. We test the algorithm on a set of TSPs. For all instances, the modified algorithm is shown to be capable of escaping from the elastic net local minima and producing optimal tours or more meaningful tours than the original elastic net.