Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Default user image.

Carsten Peterson

Expert

Default user image.

Combinatorial Optimization with Neural Networks

Författare

  • Carsten Peterson
  • Bo Söderberg

Redaktör

  • Colin R. Reeves

Summary, in English

A general introduction to the use of feed-back artificial neural networks (ANN) for obtaining good approximate solutions to combinatorial optimization problems is given, assuming no previous knowledge in the field. In particular we emphasize a novel neural mapping technique which efficiently reduces the solution space. This approach maps the problems onto Potts glass rather than spin glass models. The real strength in mapping optimization problems onto neural systems lies in the fact that local minima in the cost functions can be avoided with the use of mean field equations. The system ``feels'' its way towards good solutions. In the settling process it may encounter phase transitions. A systematic prescription can be given for estimating the phase transition temperatures in advance, which facilitates an automatized choice of optimal parameters. This analysis, which can be performed for both serial and synchronous updating of the mean field theory equations, also makes it possible to consistently avoid chaotic behaviour. These techniques are illustrated for the graph partition and the traveling salesman problems (TSP). Also, a realistic high school scheduling problem is dealt with in some detail. These problems are all characterized by equality constraints. The formalism can also be modified to deal with inequality constraints. This is illustrated with the knapsack problem. We also discuss the deformable templates approach, which is closely related to the Potts neural encoding. In problems of geometrical nature like TSP and track finding this method is more economical with its fewer degrees of freedom.

Avdelning/ar

  • Beräkningsbiologi och biologisk fysik - Har omorganiserats

Publiceringsår

1993

Språk

Svenska

Sidor

197-242

Publikation/Tidskrift/Serie

Modern Heuristic Techniques for Combinatorial Optimization

Dokumenttyp

Del av eller Kapitel i bok

Förlag

Blackwell

Ämne

  • Bioinformatics (Computational Biology)

Status

Published