Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A New Method for Mapping Optimization Problems onto Neural Networks

Peterson, Carsten LU and Söderberg, Bo LU (1989) In International Journal of Neural Systems 1(1). p.3-22
Abstract
A novel modified method for obtaining approximate solutions to difficult optimization problems within the neural network paradigm is presented. We consider the graph partition and the travelling salesman problems. The key new ingredient is a reduction of solution space by one dimension by using graded neurons, thereby avoiding the destructive redundancy that has plagued these problems when using straightforward neural network techniques. This approach maps the problems onto Potts glass rather than spin glass theories. A systematic prescription is given for estimating the phase transition temperatures in advance, which facilitates the choice of optimal parameters. This analysis, which is performed for both serial and synchronous updating of... (More)
A novel modified method for obtaining approximate solutions to difficult optimization problems within the neural network paradigm is presented. We consider the graph partition and the travelling salesman problems. The key new ingredient is a reduction of solution space by one dimension by using graded neurons, thereby avoiding the destructive redundancy that has plagued these problems when using straightforward neural network techniques. This approach maps the problems onto Potts glass rather than spin glass theories. A systematic prescription is given for estimating the phase transition temperatures in advance, which facilitates the choice of optimal parameters. This analysis, which is performed for both serial and synchronous updating of the mean field theory equations, makes it possible to consistently avoid chaotic behavior.

When exploring this new technique numerically we find the results very encouraging; the quality of the solutions are in parity with those obtained by using optimally tuned simulated annealing heuristics. Our numerical study, which for TSP extends to 200-city problems, exhibits an impressive level of parameter insensitivity. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
International Journal of Neural Systems
volume
1
issue
1
pages
20 pages
publisher
World Scientific Publishing
ISSN
0129-0657
DOI
10.1142/S0129065789000414
language
English
LU publication?
yes
id
cc197d5d-65ef-4da0-b37b-0a35c1c38283
date added to LUP
2019-05-13 19:31:32
date last changed
2019-08-06 12:07:49
@article{cc197d5d-65ef-4da0-b37b-0a35c1c38283,
  abstract     = {{A novel modified method for obtaining approximate solutions to difficult optimization problems within the neural network paradigm is presented. We consider the graph partition and the travelling salesman problems. The key new ingredient is a reduction of solution space by one dimension by using graded neurons, thereby avoiding the destructive redundancy that has plagued these problems when using straightforward neural network techniques. This approach maps the problems onto Potts glass rather than spin glass theories. A systematic prescription is given for estimating the phase transition temperatures in advance, which facilitates the choice of optimal parameters. This analysis, which is performed for both serial and synchronous updating of the mean field theory equations, makes it possible to consistently avoid chaotic behavior.<br/><br/>When exploring this new technique numerically we find the results very encouraging; the quality of the solutions are in parity with those obtained by using optimally tuned simulated annealing heuristics. Our numerical study, which for TSP extends to 200-city problems, exhibits an impressive level of parameter insensitivity.}},
  author       = {{Peterson, Carsten and Söderberg, Bo}},
  issn         = {{0129-0657}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{3--22}},
  publisher    = {{World Scientific Publishing}},
  series       = {{International Journal of Neural Systems}},
  title        = {{A New Method for Mapping Optimization Problems onto Neural Networks}},
  url          = {{http://dx.doi.org/10.1142/S0129065789000414}},
  doi          = {{10.1142/S0129065789000414}},
  volume       = {{1}},
  year         = {{1989}},
}