Physics for Travelling Salesmen: Some New Approaches to Combinatorial Optimisation.
Abstract
Three new approaches to combinatorial optimisation have been described recently. They are based on analogies with physical and biological systems. The first, Kirkpatrick's Optimisation by Simulated Annealing method, has already proved useful in engineering optimisation problems such as layout and routing in VLSI chip design. At present, this probably the most powerful general optimization method for use on conventional serial computers. Although the second, Brady's evolution-based approach, has yet to receive a thorough numerical study, it seems likely to provide powerful optimisation methods for parallel SIMD computer architectures of which the most widely distributed example in the UK is the ICL DAP. The third method, Hopfield and Tank's Optimisation via networks of amplifiers, is the most revolutionary and may lead to a new generation of chips with mixed analog/digital functions for rapid optimisation.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1986
- Accession Number
- ADA169547
Entities
People
- D. G. Bounds
Organizations
- Royal Signals and Radar Establishment