Tabu learning: a neural network search method for solving nonconvex optimization problems

The authors present a novel technique, called tabu learning, for solving nonconvex optimization problems using neural networks. Tabu learning applies the concept of tabu search to neural networks by continuously increasing the energy surface in a neighborhood of the current state, thus penalizing states already visited. This enables the state trajectory to climb out of local minima while tending toward areas not yet visited, thus performing an efficient search of the problem´s energy surface. For a quadratic penalty function, the learning equation causes the connection weights and bias currents to be modified continuously based on local information. Simulations on the 20-city traveling salesman problem indicate that quadratic tabu learning finds solutions of a given cost 65 times more quickly than repetitive gradient descent using random initial states. Simulations on the 100-node maximum independent set problem indicate that tabu learning finds the optimal solution 60 to 600 times more quickly