SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS USING NEURAL NETWORKS
Sreeram V. B. Aiyer (PhD Thesis)
October 1992
Combinatorial optimization problems arise naturally in many areas of science and engineering. Unfortunately, the accurate solution of a large class of these problems requires an amount of computation which increases exponentially with the problem size. The extensive research into ways of avoiding this difficulty has recently been given even further impetus by the widespread occurrence of these problems in the field of Artificial Intelligence, especially in the pattern recognition problems associated with speech and vision processing. However, the only computationally tractable methods that have so far been developed all rely on some form of heuristic: essentially an intelligent guess which offers a reasonable compromise between solution quality and computational complexity.
Neural networks offer a novel and potentially powerful heuristic for solving these problems. They are also intrinsically parallel systems, with significant potential for fast hardware implementation. Out of recent research, two related families of neural network for solving combinatorial optimization problems have emerged: Hopfield networks, and Mean Field Annealing networks. A number of researchers has applied these networks to a wide variety of problems, and there now exists a large body of rather inconclusive experimental results, with several researchers reporting very poor performances. No theoretical framework has yet been developed which can either account for these inconclusive results in a systematic way, or offer a robust method of correcting the root causes of these poor performances. Consequently, some researchers have concluded that these networks are fatally flawed.
This thesis is aimed at developing such a theoretical framework. By doing this, it will be possible to explain and correct the poor network performances that have emerged from the experimental results. This framework also has the further advantage of making it possible to analyze how these networks achieve their solutions, and to characterize which types of problems these networks can be expected to solve accurately. Based on this analysis, a series of modifications will then be described which greatly improve the efficiency and final solution quality of these networks. Finally a mapping of the Viterbi algorithm onto these network will be developed, which will be used to demonstrate that combinatorial optimization problems of practical significance to speech recognition can be solved using neural networks.
If you have difficulty viewing files that end '.gz',
which are gzip compressed, then you may be able to find
tools to uncompress them at the gzip
web site.
If you have difficulty viewing files that are in PostScript, (ending
'.ps' or '.ps.gz'), then you may be able to
find tools to view them at
the gsview
web site.
We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.