Combinatorial optimization problems arise throughout science, industry, and commerce. The demonstration that analogue neural networks could, in principle, rapidly find near-optimal solutions to such problems - many of which appear computationally intractable - was important both for the novelty of the approach and because these networks are potentially implementable in parallel hardware. However, subsequent research, conducted largely on the travelling salesman problem, revealed problems regarding the original network's parameter sensitivity and tendency to give invalid states. Although this has led to improvements and new network designs which at least partly overcome the above problems, many issues concerning the performance of optimization networks remain unresolved. This thesis explores how to optimize the performance of two neural networks current in the literature: the elastic net, and the mean field Potts network, both of which are designed for the travelling salesman problem. Analytical methods elucidate issues of parameter sensitivty and enable parameter values to be chosen in a rational manner. Systematic numerical experiments on realistic size problems complement and support the theoretical analyses throughout. An existing analysis of how the elastic net algorithm may generate invalid solutions is reviewed and extended. A new analysis locates the parameter regime in which the net may converge to a second type of invalid solution. Combining the two analyses yields a prescription for setting the value of a key parameter optimally with respect to avoiding invalid solutions. The elastic net operates by minimizing a computational energy function. Several new forms of dynamics using locally adaptive step-sizes are developed, and shown to increase greatly the efficiency of the minimization process. Analytical work constraining the range of safe adaptation rates is presented. A new form of dynamics, with a user defined step-size, is introduced for the mean field Potts network. An analysis of the network's critical temperature under these dynamics is given, by generalizing a previous analysis valid for a special case of the dynamics.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:661926 |
| Date | January 1992 |
| Creators | Simmen, Martin Walter |
| Publisher | University of Edinburgh |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/1842/12942 |
Page generated in 0.0021 seconds