Group Updates and Multiscaling: An Efficient Neural Network Approach to Combinatorial Optimization

A multiscale method is described in the context of binary Hopfield--type neural networks. The appropriateness of the proposed technique for solving several classes of optimization problems is established by means of the notion of group update which is introduced here and investigated in relation to the properties of multiscaling. The method has been tested in the solution of partitioning and covering problems, for which an original mapping to Hopfield-type neural networks has been developed. Experimental results indicate that the multiscale approach is very effective in exploring the state-space of the problem and providing feasible solutions of acceptable quality, while at the same it offers a significant acceleration. 1 Introduction The Hopfield neural network model [7, 8] and closely related models such as the Boltzmann Machine [3, 1] have proved effective in dealing with hard optimization problems and yield near-optimal solutions with polynomial time complexity [6, 20]. The basic ..