An automata network for performing combinatorial optimization

Abstract

There have been several neural network approaches to the tasks of solving combinatorial optimization problems. In this paper, a new type of neural networks-the WTA-type networks, which incorporates the Winner-Take-All mechanism into the automata networks, is proposed. Five specifications of the WTA-type networks (N1-N5) are presented. The theoretical foundations of the networks are developed from the standpoint of taking them as combinatorial optimization solvers. We also investigate the two key issues, reliability and efficiency, related to the application of the networks. The proposed networks and the established theories are applied to a set of combinatorial optimization benchmark problems-traveling salesman problems. The simulation results demonstrate that the proposed WTA-type networks are more effective or comparable with the Hopfield networks, the Boltzmann machine and the self-organizing feature map network. © 2002 Elsevier Science B.V. All rights reserved.