Solving combinatorial optimisation problems using neural networks
Marimuthu Swami Palaniswami, Kate Smith‐Miles · 1996
Combinatorial optimisation problems (COP's) arise naturally when mathematically modelling many practical optimisation problems from science and engineering. Unfortunately, existing neural techniques are widely considered to be unsuited to optimisation due to their tendency to produce infeasible or poor quality solutions. Over the last decade or so, two main types of neural networks have been proposed for solving COP's--in particular, the Travelling Salesman Problem (TSP). The first of these neural approaches is the Hopfield neural network which evolves in such a way as to minimise a system energy function. In its original form, the Hopfield energy function involves many parameters which need to be tuned, and constructing a suitable energy function which enables the network to arrive at feasible near-optimal solutions is a difficult task. The other main neural approach found in the literature is based upon the theory of self-organisation. The vast majority of research into self-organisation for solving COP's however, has been restricted to solving the TSP. The reason for this focus on the TSP is not just because of its standing as a benchmark problem, but more because most of these networks are embedded into the Euclidean plane by their dependence on the Elastic Net method. Consequently, results cannot be generalised to solve many COP's arising from practical situations which are not restricted to the Euclidean plane. In this thesis, modifications are made to the Hopfield neural network to enable escape from local minima, while feasibility of the solutions is ensured. Convergence and stability properties are analysed through a dynamical systems perspective and are less restrictive than those commonly accepted in the literature. A new self-organising neural network is also designed which generalises to solve a broad class of COP's. The approach is purely combinatorial in nature, operating on feasible permutation matrices rather than within any restrictive geometric structures. Convergence properties are also discussed. The wide applicability of these neural techniques is demonstrated in this thesis through the solution of three practical COP's which have arisen from various areas of Australian industry: car manufacturing, postal services, and telecommunications.