Compact analogue neural network: a new paradigm for neural based combinatorial optimisation

摘要

The authors present a new approach to neural based optimisation, to be termed the compact analogue neural network (CANN), which requires substantially fewer neurons and interconnection weights as compared to the Hopfield net. They demonstrate that the graph colouring problem can be solved by using the CANN, with only O(N) neurons and O(N/sup 2/) interconnections, where N is the number of nodes. In contrast, a Hopfield net would require N/sup 2/ neurons and O(N/sup 4/) interconnection weights. A novel scheme for realising the CANN in hardware form is discussed, in which each neuron consists of a modified phase locked loop (PLL), whose output frequency represents the colour of the relevant node in a graph. Interactions between coupled neurons cause the PLLs to equilibrate to frequencies corresponding to a valid colouring. Computer simulations and experimental results using hardware bear out the efficacy of the approach.