Global Minimum Elastic Net for the Euclidean Travelling Salesman Problem
Imaculate Mosha · 2017
The Travelling Salesman Problem belongs to the class of NP (Non Deterministic Polynomial) Complete problems. It can be solved by Exact or heuristic algorithms. Heuristic algorithms find approximate solutions to the problems and include Neural Network algorithms such as Hopfield Network, Self-Organizing Map and the Elastic Net. The Elastic Net is made of a network of neurons and a defined energy function whose minimum renders the most optimal configuration. It proceeds by minimizing the energy of the configuration. This article proposes a variant of the Elastic Net to solve the Traveling Salesman Problem. The original Elastic Net algorithm finds the energy minimum by gradient descent and is therefore prone to conclude at the local minimum. The proposed method aims to reach the global minimum by reinitializing the neurons each time a local minimum is reached. This enables the network to explore a wider sub space of solutions. Experiments reveal shorter tours than other Elastic Net variants at the slight expense of processing time.