Heuristic Procedure Neural Networks for the CMST Problem

Scope and Purpose – For solving combinatorial optimization problems, neural networks have traditionally been outperformed by traditional heuristic techniques developed specifically for the problem in question. This research is a step toward integrating the problem specific knowledge embedded in a traditional heuristic with the adaptive capabilities of neural networks. This is accomplished by creating a neural network topological design that embeds the steps of the traditional heuristic. The neural network learning then improves upon the performance of the embedded heuristic by modifying the neural weights attached to the embedded heuristic. Combinatorial optimization problems are by nature very difficult to solve, and the Capacitated Minimum Spanning Tree problem is one such problem. Much work has been done in the management sciences to develop heuristic solution procedures that suboptimally solve large instances of the Capacitated Minimum Spanning Tree problem in a reasonable amount of time. The Capacitated Minimum Spanning Tree problem is used in this paper to develop and demonstrate a hybrid neural network methodology that incorporates heuristic methods into the neural network topological design. The heuristic procedure is embedded into the neural network topological design, and an iterative improvement process is performed using the neural network. The semi-relaxed energy function of the problem is used to develop a neural network weight adjustment procedure that modifies the problem costs. In three-quarters (75%) of our experiments, the hybrid neural networks produced better results than any of the traditional procedures tested