Browse Prior Art Database

Linear Algorithm Solving the Traveling Salesman Optimization Problem

IP.com Disclosure Number: IPCOM000112889D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 2 page(s) / 33K

Publishing Venue

IBM

Related People

Fritsch, T: AUTHOR [+4]

Abstract

Disclosed is a linear algorithm solving the traveling salesman problem, such as finding the shortest path between holes to be drilled into a board, using a Kohonen neural network with supremum metric.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 89% of the total text.

Linear Algorithm Solving the Traveling Salesman Optimization Problem

      Disclosed is a linear algorithm solving the traveling salesman
problem, such as finding the shortest path between holes to be
drilled into a board, using a Kohonen neural network with supremum
metric.

      The algorithm utilizes a growing ring-shaped and closed chain
of neurons and works according to the following steps:

1.  Randomly offering the drill hole coordinates b[i]  =
    (b[i,x],b[i,y]) to the neurons;

2.  Determining the distance dj between the excitation center and
    each neuron for the actual offered drill hole coordinate b =
    (b[x], b[y]) according to the supremum metric
    d[j]  = max(|b[x]  - w[j,x](k) |,|b[y]  - w[j,y](k)|).
    with w[j,x](k) and w[j,y](k) being the junction weights between
    the input coordinate and the neuron j at step k of the algorithm;

3.  Choosing the neuron with the shortest distance and defining the
    junction weights in the neighbourhood of this neuron according to
    w[j,z](k+1) = w[j,z](k) + &eta.(k)(b[z] - w[j,z](k)) with z being
    the important coordinate when determining the distance maximum of
    step 2 and &eta.(k) being a monotonously falling function;

4.  Increasing the number of neurons and thus expanding the structure
    of the neural network and

5.  Repeating steps 1 to 4 until remaining under a given fault
    tolerance.

Having completed this algorithm each neuron clearly cor...