BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR94-1416
ENTRY:: 1994-04-19
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Empirical Evidence of the Chaotic Behavior of the Hopfield-Tank TSP 
        Model
AUTHOR:: Vassiliadis, Stamatis
AUTHOR:: Pitsianis, Nikos P. 
AUTHOR:: Pechanek, Gerald G.
DATE:: March 1994
PAGES:: 31
ABSTRACT::
Since its introduction, the Hopfield-Tank model for the Traveling Salesman 
Problem (TSP) has been surrounded by controversial evidence regarding its 
viability as a model and its capabilities to produce good results to this hard 
optimization problem. In this paper we investigate the reasons behind the 
difficulty of obtaining verifiable results and the viability of the model, by 
investigating the behavior the Hopfield-Tank neural network for the TSP has in 
circumstances when it is expected to produce identical tours. Our 
investigations strongly suggest that, when it is expected from the network to 
converge in a predetermined tour, the neural network converges to almost 
all possible tours when an insignificant perturbation to the initial 
conditions is applied. The overall consequence of our findings regarding the 
viability of the Hopfield-Tank model and the cause of the controversy 
surrounding the Hopffield-Tank model for the TSP can be summarized by the
following: The cause of the Hopfield-Tank neural network for the TSP 
controversy and the difficulties in reproducing results is the chaotic 
behavior of the model. The finding of useful results for the TSP using the 
Hopfield-Tank network are purely casual and not to be attributed to the 
viability of the model. In essence the Hopfield-Tank neural network for the 
TSP is as viable as chaotic systems can be.
END:: CORNELLCS//TR94-1416
BODY::
Empirical
Evidence of the Chaotic
Behavior of the
Hopfield-Tank TSP Model
Stamatis Vassiliadis*
Nikos P. Pitsianis**
Gerald G. Pechanek***
TR 94-1416
March 1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
* Electrical Engineering Dept., T.U. Deift, DeIft, The Netherlands.
** Dept. of Computer Science, Cornell University, Ithaca, NY.
IBM Microelectronics Division, Research Triangle Park, NC.
Empirical Evidence of the Chaotic Behavior of the
Hopfield-Taiik TSP Model
Stamatis Vassiliadis *
Nikos P. Pitsianis
March 24, 1994
Abstract
Gerald G. Pechanek ?
Since its introduction, the Hopfield-Tank model for the Traveling Salesman Problem
(TSP) has been surrounded by controversial evidence regarding its viability as a model
and its capabilities to produce good results to this hard optimization problem. In this
paper we investigate the reasons behind the difficulty of obtaining verifiable results and
the viability of the model, by investigating the behavior the Hopfield-Tank neural network
for the TSP has in circumstances when it is expected to produce identical tours. Our
investigations strongly suggest that, when it is expected from the network to converge in
a predetermined tour, the neural network converges to aimost all possible tours when an
insignificant perturbation to the initial conditions is applied. The overall consequence
of our findings regarding the viability of the llopfield-Tank model and the cause of the
controversy surrounding the Hopfield-Tank model for the TSP can be summarized by the
following: The cause of the Hopfield-Tank neural network for the TSP controversy and
the difficulties in reproducing results is the chaotic behavior of the model. The finding of
useful results for the TSP using the llopfield-Tank network are purely casual and not to
be attributed to the viability of the model. In essence the Hopfield-Tank neural network
for the TSP is as viable as chaotic systems can be.
1 Introduction
The Traveling Salesman Problem (TSP) [PS82] is often considered as one of the most, if not
the most, representative combinatorial optimization problem. The problem can be described
simply by the following: Given a finite set C of cities and a distance function dx,y > 0 for
each pair of cities X, Y ? C, a salesman wants to find a tour visiting all the cities in C and
returning to the starting city, that has the minimum length. A tour is an ordering of the set
C, or a permutation of the elements of C and its length is defined as the sum of the distances
*Electrical Engineering Dept., T.U. Delft, Deift, The Netherlands.
tDept. of Computer Science, Cornell University, Ithaca, NY.
tIBM Microelectronics Division, Research Triangle Park, NC.
of the cities when moving from one to the other and returning to the first city, according to
the tour ordering.
The corresponding decision problem to this optimization problem has been shown to be
NP-hard and unless NP --H P there is no polynomial time algorithm for finding an optimal
tour. Actually when the triangle inequality does not apply, i.e. there exists a triplet of
cities X, Y and Z such that dx,z > dx,y + dy,z, there is no e-approM.mate polynomial time
algorithm for the unrestricted TSP [PS82]. That is, for any given ?, an algorithm can not
be found which determines a tour that is no longer than ?% from the optimal tour.
One of the approaches suggested to be promising in providing an acceptable, but not
optimal solution, to this classical hard problem is due to llopfield and Tank [11T85]. The
model as proposed by Hopfield and Tank is based in neural networks [11T85] and its valida-
tion was performed with a 10 city problem. Based on simulations, Hopfield and Tank have
suggested that their neural network can provide results of good quality for the 10 city TSP
problem they considered. Since its introduction, a number of investigations have attempted
to improve and to validate the llopfield-Tank neural network model for the TSP. Generally
speaking, the research regarding the Hopfield-Tank model for the TSP and Hopfield-Tank
related models is characterized by investigating:
o+ The convergence of the model to a solution within an "acceptable" amount of time.
o+ The convergence of the model to valid solutions (legitimate tours).
o+ The quality of the valid solutions.
o+ The scalability of the model.
Following this investigation paradigm, based on the modification of various parameters
in the model, a number of Hopfield-Tank based models have appeared with the intention to
improve the performance of the original Hopfield and Tank neural network model, see for
example [Biz91, B189]. Clearly, there is no lack of reports suggesting that simulations of
the llopfield-Tank (llT) and Hopfield-Tank based models have been successful in providing
acceptable solutions to the TSP (and other optimization problems) for a number of city
configurations [BWLM88, CR89, XT91, Biz91, B189]. On the other hand, regarding the val-
idation of the llopfield-Tank model, a number of conflicting findings have also been reported.
In a number of occasions, see for example [WP88, KPKP9O], it has been suggested based
also on simulations that the results of the llopfield and Tank original proposal could not
be repeated.
One of the important aspects of the investigations, regarding the reproduction of the
results of the llopfield-Tank model and the improvements of the model, is that what has
been found thus far does not provide a consistent view of the behavior of the model. As
exemplified by the research reported in [11T85] and [WP88], what has been found by an
investigation is partially found, or not found at all, by another investigation. While there is
a constant disagreement on the behavior of the proposal, and while it may be becoming more
and more evident to the scientific community that the Hopfield-Tank model may in instances
2
produce unpredictable results, what remain as definite open questions is establishing an
explanation of the causes of such a behavior and determining whether the model has any
possibility of being considered as a viable model.
In this paper, we investigate these open problems and we establish the causes of the
unexpected behavior of the model as observed by many. Further we provide an explanation of
the reason why results of one investigation are not easily reproducible by other investigations
and provide some insights on the viability of the Hopfield-Tank model. We provide the answer
to the open problems by showing, using simulations on the original city problem proposed
by llopfield-Tank, that when the network should be producing identical tours, it consistently
does not. In particular we show that very small (negligible) variations from the initial set up
of the network will produce different tours when in reality it should be converging to identical
tours. Our findings strongly suggest that the non-linear recursive Hopfield-Tank equations
for the TSP are chaotic, indicating that the cause of the entire controversy is the chaotic
behavior of the network and is thus to be expected. Clearly, our investigation suggests,
in view of the chaotic nature of the model, that the model can not be considered viable
in producing consistent good quality tours. Our investigation also suggests that any other
variation of the network equations may have identical behavior and thus it can not be used
for the TSP problem, as in general, such models will produce unreliable and unpredictable
results.
The presentation of the paper is in the following format: In section 2 we introduce briefly
the approach taken by Hopfield-Tank to model the TSP. Additionally we survey the findings
of a number of investigations regarding reported improvements and the repeatability of the
results for the Hopfield-Tank TSP model. Further, we discuss in some detail the main con-
tributions of the investigation reported in this paper. In section 3 we describe our simulation
approach. Consequently we present the results of both simulations and conclude with some
remarks regarding the behavior of the llopfield-Tank network.
2 Background, Open Questions, and Main Results
Briefly, in the Hopfield and Tank Model, a N city TSP is represented by a network of N2
fully interconnected neurons (X, i) which we can think of as an N by N matrix. Each row of
this matrix corresponds to a city X and each column to a particular index i in the ordering.
In the Hopfield and Tank Model, the tour ordering is represented as a permutation matrix, a
matrix that results from the permutation of the rows (or the columns) of the identity matrix.
Each row of this matrix corresponds to a city and each column to a particular position in the
ordering. For example, consider a five-city TSP, then the tour DACEB (that is, start from
city D then visit A, C, E, B and finally return back to D) is represented as the matrix in
Table 1. We will say that a Hopfield-Tank network converged to this tour when the network
converges to the above permutatioll matrix. More discussion regarding the specifics of the
operation of the model can be found in the simulations section.
Regarding the Hopfield and Tank's method for solving the Traveling Salesman Problem,
initially the research has been directed towards two very important issues, namely: How
3
12345
A0100 0
B0000 1
COOlO 0
D1000 0
E 0 0 0 1 0.
Table 1: All Example of a Five-city TSP Using the Hopfield and Tank Model
to increase the number of converging valid tours and how to improve the quality of the
resulting tours. While some investigations have been successful in their quest [BWLM88,
CR89, XT9l, Biz9l, B189], others have discovered that the model can be unpredictable and
it may not be a viable model for the TSP. We initiate this section, for background purposes,
by discussing briefly the controversy for the viability of the llopfield-Tank neural model for
the TSP. Consequently we discuss the open questions left by previous investigations and
discuss to some extend our main contributions in answering the open questions.
Previous Experiments: The first investigation reporting questions regarding the
Hopfield-Tank model was conducted by Wilson and Pawley. In their investigation [WP88],
Wilson and Pawley have found conflicting results with respect to the original llopfield-
Tank experimentation. In particular, Hopfield and Tank have suggested that 16 of their
20 experiments converged to legitimate tours with 50% of the experiments producing the
2 shortest tours. The Wilson and Pawley simulations, using the same 10-city set llopfield
and Tank used' suggest that of the 100 experiments they conducted 40 did not converge
within an acceptable time (acceptable time was assumed to be 1000 neuron iterations), 15
converged to states corresponding to valid tours and 45 "froze" into invalid configurations.
Furthermore, they have also concluded, regarding the length of the valid tours, that the
15 tours obtained by the experimentation are slightly better than randomly selected tours.
In conducting additional experimentations with ten different randomly-generated sets of 10
cities, using 50 runs per set, Wilson and Pawley found that 8% of the runs converged to a
valid tour state (with proportions for a given set running between 0% and 20%). Furthermore
they found that 48% froze to invalid tours and that 44% did not converge within the 1000
timeout iteration limit.
Behzad Kamgar-Parsi and Behrooz Kamgar-Parsi in [KPKP90j, by reexamining the
llopfield-Tank TSP model have found -in agreement with the Wilson-Pawley investigation--H
that the number of times the network succeeds in finding valid solutions is considerably less
than that found by llopfield and Tank. Their findings however disagree with the Wilson and
1Note that the coordinates of the 10 cities Wilson and Pawley used in their experimentation has been
obtained by photo-expanding a figure of the Hopfield Tank paper [HT85j and by measuring the locations
directly.
4
Pawley findings in regards to the tour lengths. Behzad Kamgar-Parsi and Behrooz Kamgar-
Parsi found that when the neural net finds a tour then the solution is "of a remarkably
good quality". Additionally, Behzad Kamgar-Parsi and Behrooz Kamgar-Parsi suggest that
the success rate of finding valid solutions can be improved. Finally, they suggest that the
Hopfield-Tank solution does not scale well with the size of the problem (while the solutions
found are still remarkably good, finding valid solutions becomes increasingly difficult as the
size of the problem increases).
Van Den Bout and Miller [B189] report that the setting of the model parameters has an
influence on the tour outcome with small value parameters leading to short invalid tours
while large parameter values "stiffen" the penalties to a degree that the network tends to
converge to any valid tour independent of the tour length. Regarding the model parameters,
the experimental work discussed in Hedge et al [HSL88] indicates that good parameter value
may exist in difficult to find regions of parameter space. Modifications to avoid the diffi-
culty of finding "good" network parameters have been attempted by [BWLM88], and also
by [Szu88] which propose a modification of the Brandt et al [BWLM88] model. However
Van Den Bout and Miller [B189] indicate that such kind of solution improves the genera-
tion of valid tours but it produces notably non-optimal solutions as the size of the problem
increases. Furthermore, they suggest that incremental changes involving "neural normaliza-
tion, annealing and annealing with non-uniform temperatures" will improve the quality of
the tours found by the Hopfield-Tank network.
Further, regarding the scalability of the model, David S. Johnson in [Joh90, Joh87] sug-
gests that the Hopfield-Tank neural network approach cannot even outperform 2-Opt2 at 30
cities. Additionally, regarding the validity of the tours produced by the TSP Hopfield-Tank
model, Aiyer et al [ANF90] using eigenvalues and a number of approximations, suggest pos-
sible relationships among the various parameters in the model. They conclude that "the
formulation of the connection matrix sets up a subspace, which contains only the valid solu-
tions of the problem" and suggest that "by carefully selecting the network parameters, it is
possible to ensure that the network converges to hypercube corners in this subspace". They
test their analytic expressions of their parameters using experimentation and report that the
simulation they conducted produces 100% valid solutions.
Regarding the instability and the sensitivity to the initial conditions Kahng [Kah89J
has reported symptoms of numerical instability and sensitivity to initial conditions for the
model. It is suggested that the final tour is highly dependent on the initial perturbations used
for the symmetry breaking of the network. Finally, the investigation reported in W.Lin et
al [LDFVP93] suggests that there is a definite influence of the number representation and the
precision of the operations on the outcome of the simulations and on the tour convergence.
Open Questions and Main Results: Due to the conflicts regarding the capabilities
of the original Hopfield-Tank TSP model, the question whether or not the Hopfield-Tank
model [HT85] constitutes a viable approach for the TSP remains still open. Further, while
22-Opt is a heuristic for improving a TSP tour by exchanging two edges of the tour with two other edges
of shorter length.
5
various investigators, e.g. Kahng [Kah89] and W.Lin et al [LDFVP93J, have reported de-
pendability of the final outcome of the neural network on the initial conditions and the
computations carried out by the network, they fail to quantify the smallest magnitude of
the changes required to produce a deviation of the network, they do not provide a complete
conclusive study of such influences, and finally they do not provide an answer for the cause
of this network behavior.
In this paper we provide an answer to the open questions by examining closely a related
question The related open question and the essence of our investigation is on determining
the behavior the neural network has when it is expected to produce identical tours. Assuming
certain initial input values and parameter setting, this open problem can be rephrased for
simulation purposes to the following question:
Does a small (negligible for all computing purposes) variation of the initial conditions
have any influence on the convergence of the network and the validity and the length
of the tours?
As it will be seen later, the answer to this question is affirmative and it allows us to
determine the magnitude of the initial condition changes that produce a deviation from the
expected behavior and provide a cause for the behavior of the neural network. In particular,
the affirmative answer to this question indicates that the non-linear recursive equations
describing the Hopfield-Tank TSP neural model for small (negligible) variations of the input
variables cause the production of a different tour than the tour it produced before applying
the insignificant initial condition variation. Given that the magnitude of the changes in the
initial conditions are insignificant, it is expected that the model "absorbs" the differences
and produces identical tours. Because this is not the case, the essence of our experiment
is captured by stating that the llopfield-Tank network has chaotic behavior determined by
the non-linear recursive equations and indicated by the "unexpected" results when small
input variations are applied in the network with all of the other parameters of the network
fixed. Because an instance of the network exhibits chaotic characteristics, we postulate that
in general the equations describing the llopfield-Tank neural network are inherently chaotic.
More in particular, as it will be shown by the actual simulations, we have established the
following for the Hopfield-Tank neural model for the TSP:
o+ The smallest possible perturbation 3 to some values in the initial conditions will alter
the tour the network converged before the perturbation.
o+ Assuming that for a given set of values, before perturbation, the model converges to a
legitimate tour, a small insignificant perturbation in some of the values in the set not
only does not not produce the identical tour but it may also converge to an illegitimate
tour.
3The smallest possible perturbation of a value corresponds to the change of the least significant bit of
this value's double floating point representation. Because we conducted our experimentation with a SUN
4m/670 MP Sparc computer system, the smallest perturbation of a single value in the set of the initial values
corresponds to changing the least significant bit of the mantissa of a double accuracy real.
6
o+ Finally, the effect on the initial tour the negligible perturbations on some values in the
initial conditions have is that they produce almost all possible tour lengths when the
running of the model converges to a valid solution.
The overall consequence of our findings regarding the viability of the llopfield-Tank model
for the TSP and the cause of the controversy surrounding the model can summarized by the
following:
o+ The cause of the Hopfield-Tank neural network for the TSP controversy and the diffi-
culties in reproducing results, is the chaotic behavior of the model.
o+ The finding of useful results for the TSP using the llopfield-Tank network are purely
casual and not to be attributed to the viability of the model. In essence the llopfield-
Tank neural network for the TSP is as viable as chaotic systems can be.
3 The Simulation Strategy and Algorithm
To prove that the llopfield-Tank neural network model has a chaotic behavior, it is enough to
show that there is at least one city problem that forces the model to exhibit such a behavior.
We assume the "counter example" city problem for our experimentation to be the same city
problem used in the experimentation by Hopfield-Tank in [11T851 having the coordinates
determined by Wilson and Pawley in [WP88] and reported in Table 2. Further, given that
we are interested in proving via simulation that the neural network corresponding to the
Hopfield-Tank city problem [HT85] is chaotic and to show that in general the model is not
viable, it is enough to show that an instance of the network for the city problem we consider
has these properties. This type of experimentation is sufficient because if there is an instance
of the model that exhibits a chaotic behavior, then it can be concluded that in general the
model is chaotic and thus also not viable. Note that our goal is not to show that the entire
space of the definition of the network (comprising the initial conditions and parameters) is
chaotic as such an experimentation is difficult 4 and it possibly does not add to the overall
conclusions. Further we are not interested in investigating the possibility of a set of values
for which the Hopfield-Tank neural network for the TSP does not exhibit a chaotic behavior.
This type of investigation, if it is of any interest, can be viewed as a new research topic and
possibly be considered in a later investigation.
In order to conduct our experimentations we consider the instance of the network in
which the various parameters of the Energy equation (e.g. the values of the parameters A,
I? F and A) of the model [HT85] of the network are invariant and by considering variation
on the initial conditions. We assume throughout the experimentation the parameter values
to be the same as the ones used by llopfield-Tank in [HT85]. The specifics of the entire
experimentation follows.
The llopfield-Tank Model : As discussed in the background section, the llopfield-
Tank network for an N-city TSP consists of an N-by-N array of neurons. For every neuron
4This experimentation requires the consideration of all parameters considered in their entire space.
7
0.4000			0.4439
0.2439			0.1463
0.1707			0.2293
0.2293			0.7610
0.5171			0.9414
0.8732			0.6536
0.6878			0.5219
0.8488			0.3609
0.6683			0.2536
0.6195			0.2634
Table 2: Coordinates of the 10 city problem in the unit square from Hopfield and Tank.
(X, i), where X is a variable that takes values from the set of the cities C and ? is an
index from the range [1,..' N], we consider a current state input voltage Ux,i or "mean soma
potential" [Hop84] and an output voltage Vx,t. A sigmoid monotonic function Vx,i = g(Ux,i)
describes the output voltage Vx,i of neuron (X, i) due to an input voltage Ux,i. The output of
each neuron (X, i) is connected to the input of each other neuron (Y, j) through a resistance
of value T(x,i)(Y,j). At time step n, current state voltages u??? and output voltages v??? are
two N-by-N matrices, (denoted here also as the U and V matrices), while the connectivity
matrix T is N2-by-N2 matrix.
The equation of motion describing the time evolution of the network, is the differential
equation:
au _ u			(1)
--H --HtTvec(V)+I
at
where T is a global coefficient depending on the neuron capacitance and resistance, vec() is
an operator that turns a matrix into a vector by stacking its columns on top of each other
starting from the first one [llS81j. I is an N-by-N matrix, Ix,? is the offset bias that is
externally supplied to the input of neuron (X, i). By integrating this equation, i.e. solving
the Initial Value Problem that is defined by Equation 1 and the initial value of matrix U,
we can simulate the operation of the llT network on a computer.
Hopfield and Tank in their paper[HT85] propose an energy function E that should describe
their network so as to be able to solve the N-city TSP with distances dxy.
E(V) =
42?Zj%VX?Xi t ?B2?s ? VxiW+ F2 ??? -N
x y#x
+			? dxyVxi(W,i+i + Wi-i)			(2)
Y#x
where A, B, F and A are constants chosen ab initio in order to "assist" the network con-
verge to a valid and short tour. The minimizers of the energy function E are 2N different
8
permutation matrices V that correspond to the shortest TSP tour (assuming that such a
tour is unique). That is because the first term of the sum is zero only when every row of V
has at most one nonzero value. Similarly, the second term is zero when every column of V
has at most one nonzero value. The third term is zero when the sum of the nouzero terms
of V is equal to N, the number of cities. Finally, the fourth term is equal to the length of
the tour scaled by A/2 when V is a permutation matrix. In order to constrain the values of
the elements of matrix V in the range [0,..., 1], Hopfield and Tank propose that the sigmoid
monotonic function V = g(U) be the hyperbolic tangent:
1			Ux2			(3)
Vx2?=--H(1+tanh(			))
2
where u0 is the gain factor of the hyperbolic tangent.
Moreover, by using the energy function E(V) as a guide, llopfield and Tank derive the
value that matrix T should have, in order to make the network operate according to the target
energy function defined in equation 2. Thus the general equation of motion in equation 1 is
transformed into:
dUxi _ Uxt AZVcj?B ? w
dt			T			Y#x
F			Vyj --H			Zy dxy(Vy?t+i + W,t-i
(4)
that is the specific equation of motion for the TSP solving HT network .5 For a more
extensive treatment and derivations the interested reader is refereed to [11T85].
The algorithm we use for the simulation of the model can be briefly described by the
following:
The HT Network Simulation : We use the synchronous update scheme.
o+ Initialize the matrix U such that U?t gets 1/N+ +6x? where each ?x? is randomly chosen
uniformly in the interval
--H0.1u0 ? 6x? ? 0.1u0.
o+ Repeatedly iterate
--H Calculate the values of matrix V according to equation 3.
--H Calculate the TSP tour length Adxy(V).
5Our equation differs from the one suggested in [HT85, WP88] on the choice of the free variable of the
summation of the third term F (?y ?j Vyj --H			. They have used ??, instead of			which appears
to be a bad choice for a free variable since the variable X is bound (this term belongs to the calculation of
dUdtX?)
9
--H Using the equations of motion for this network, calculate the quantities dUdXt for all
(X, ?) from equation 4.
--H Update the values of matrix U
Uxi = Uxi +
i6t.
dt
o+ Repeat until the length of the TSP tour Adxy(V) remained unchanged for the last 200
iterations.
The various parameters of the simulations and some specifics of the simulation algorithm
are discussed bellow.
Initial values: The parameters used for the simulations are the same ones proposed in
the original paper [HT85j and they specifically have the following values:
A = B = 500, F = 200, ? = 500, N+ = 15, T = 1, uo = 0.02
(5)
The value of 6 --H io-5 was used by Wilson and Pawley in[WP88], Hopfield and Tank were
not explicit about it, thus we used this value also in our experiments. Each simulation, unless
otherwise stated, begins with all neurons assigned equal "voliages" of value 1/N+ plus or
minus some noise that does not exceed 10 percent of u0.
Length function: In order to have a linear measure between the different runs, a length
function Ad?y (V) is used to calculate the length of a tour for a given activation matrix V
and a distance function dxy. When V does not correspond to a valid tour, the value of
Adxy (V) is just a real number, and no other significance should be given to it except for
differentiating between two illegal tours.
The value of Adxy (V) is calculated by finding the index of the maximum element of every
row of the activation matrix V and considering this index as the order in which the cities
are visited. The length of this path, including the length of moving from the last city visited
to the first one, is the value Adxy(V).
Notice that it is possible two different rows of V to have their maximum element on the
same column. In this case the same city will be visited twice and therefore V does not
represent a valid TSP tour.
Termination : Instead of terminating the execution of the simulation algorithm after
a pre-specified number of updates, we have decided to terminate the simulation after the
network does not change the value Adxy(V) for 200 consecutive iterations. In [Hop84], it
has been suggested that networks with symmetric connections, i.e. networks with equations
of motion with matrix T symmetric, always converge to a stable state. Since the TSP
network has symmetric connections when the distance function dxy is symmetric, --Has it is
our case with the cities having Euclidean distances--H, it is therefore suggested that its output
converges. For a simulation point of view, the numerical noise might inhibit the detection of
10
convergence. Instead of looking at the values of the matrices U and V, and a matrix norm
of them, as Wilson and Pawley in [WP88] did, we are looking at the value of the function
Adxy (V). That is, we implicitly project the current V from the interior of the unit hypercube
[0,..., 1jN2 to a near-by vertex of it (that obviously belongs to [0, 11N ) Please note that
we do this only for the purpose of calculating the length function value and not the update
values of U. This action smoothes the numerical noise, so whenever there is no change in
the value of Adxy (V) for a long enough period, we can assume we reached the convergence
point. The choice to discontinue a simulation after Adxy (V) remained unchanged for 200
iterations is arbitrary and we did not test whether the network will converge to a different
state if we had waited a longer time.
We consider this length as the convergence length, and the resulting tour is legitimate
only when the final V is a near-permutation, that is, whenever element V,j is the maximum
element of row i, to also be the maximum of column j. In this way we know we are really
close to a vertex of the N2-dimensional hypercube that corresponds to a valid tour.
In [HT85J it is required the resulting activation matrix V to be a permutation matrix.
For this study we relax this requirement and only want V to be a near-permutation 6 for the
simple reason that a near permutation matrix contains enough information to define a tour,
even in the case that U fluctuates due to numerical noise, between different values, to still
be able to detect convergence, when those fluctuations correspond to equivalent tours.
4 Experiments
To validate our claims regarding the chaotic behavior we performed two diverse sets of ex-
periments. In the first experiment (Experiment # 1) we have attempted to repeat the results
of other investigations and to determine data points to be used as a reference for various
conclusions for the second experimentation (Experiment # 2). In the second experiment
we prove the claim indicating that the smallest variation to initial values allowable by the
numerical accuracy of Sun 4m/670 MP Sparc, the computer used in our experiments, can re-
suit in almost any imaginable valid and invalid tour. The second experiment clearly suggests
that the model produces unpredictable results when it should be "absorbing" the negligible
perturbation and behaving the same as before the addition of the perturbation of the initial
values occurred. More in detail the following has been been established by the experiments:
Experiment # 1 : As a first experiment, we run 10,000 experiments by starting with
an initial state U equal to 1/N+ plus-or-minus noise that does not exceed 10% of u0. In
Figure 1, we plot the lengths of the valid tours found. It is interesting to notice that only
2,404 from the 10,000 runs converged to a legal tour despite our relaxation to accept as
valid a near permutation. This percentage (24%) is higher than the percentage reported by
Wilson et al. in [WP88] that was only 15%, but a lot smaller from the Hopfleld and Tank
6Whenever element Vi,j is the ma?mum element of row i, then we assume to be also the maximum of
column j.
11
Leng?hBofv?kjToum
3-5
M
M
A
L
/1
2 -			__ -			-- _________-
500			1000			1500			2000
Puns
Figure 1: Plot of the lengths of only the valid tours from the 10,000 runs, in ascending order.
paper where they claim that 16 out of 20 runs (80%) converged to legitimate tours. We
also observed that the resulting lengths span in the whole range of possible lengths for this
specific problem, without giving any indication that the algorithm converges to any near
optimum tour. This is evident in the distribution of the lengths of valid tours in figure
2. Clearly the results of other investigations, such as the investigation by Kahng ?Kah89],
suggesting that the final tour is highly dependent on the initial perturbations used for the
symmetry breaking of the network are clearly verified also by this first experiment. One
question that can be asked regards the number of runs in an experiment. In essence it can
be asked if 10000 runs are enough to characterize the model. To investigate this question
we have plotted the statistics of the model for every 50,100, 500, and 1000 runs. The only
basic conclusion that can be reached is that 10000 runs do not have different characteristics
than the any of the other runs.
Figures 3 and 4 display some of the statistics of the network simulations for the runs, seen
in groups of 1000 runs. The additional plots for the other runs can be found in Appendix
A. Almost all the sets of runs have a minimum tour close to the shortest TSP tour found
in our experimentation, and a maximum tour of a length around 5.5. Also notice that the
mean and the median tour lengths literally coincide at a value just above 4. The overall
conclusion is that the averages reported in the Figures, really represent the performance of the
network, and they do not come from the accumulation of different simulations. An interesting
implication of this finding is that a "small" number of runs is sufficient to characterize the
overall behavior of the model.
Experiment # 2 The previous experiment suggests that in general the llopfield-Tank
results are not repeatable. Further, the experiment suggests that the number of runs required
to validate the results is not very relevant, as a small number is sufficient to characterize the
12
?stroob.o, of fengthe of ?efm- foum, sferbng.;. 10% ..
600			-?
Th
500
Al
400
300 I
200
100			.ji
9Th.! mmm
3.5			4			4.5			5--m.5?,-6
Length of qf? ?r
#4			--__
13
Figure 3: TSP Tour Length Statistics for the HT simulations1 where the initial point had
10% noise.
Figure 2: Distribution of the lengths of only the valid tours from the 10,000 runs, where the
initial point had 10% noise.
5			6			7			a			9			10			11
Sets of 1000 emLiafoore
TSP Tour Length 5tsf.t?cs for the ongN?- in?faf roee HT ?mufeb.ons
5.5?
-s
o?4.5
-a
15
3.5
st
male-fl
mm
oon?rgenoe o? the o?? ifl???? KT
27
j25[
! Y1
A)
\\ I
S?s Of 1000 s?mufefiOns
Figure 4: Percentage of HT simulations converged to valid TSP tours, where the initial point
had 10% noise.
model. In particular the experiment also indicated that
o+ All three investigations (the Hopfield-Tank [11T85], the Wilson/Pawley [WP88], and
experiment one) do not agree on the overall behavior of the model.
Both the Kahng [Kah89] investigation and experiment # 1, indicated the final tour
is highly dependent on the initial perturbations used for the symmetry breaking of the
network.
We note here that we conducted additional experiments. In those experiments we reduced
the noise level from the initial point of io% down to 1% or even lower to 10?1%. We run
10000 simulations for each noise level. The overall conclusions for the additional experiments
have been the same as in Experiment # 1 and thus we do not report the details of those
experiments. The only possible interesting point that may add some additional insight in
this neural network paradigm is the fact that we have observed that the number of the runs
that converged to valid tours increased and moreover the overall quality of the resulting
tours improved with the decreasing of the noise. While the results of the Experiment # 1
and of the additional experiments we run can be viewed as a possible indication for a chaotic
behavior, such evidence is not conclusive as it can always be argued that the model does not
produce "unexpected" results.
To clarify the previous statement consider the following: Generally speaking, (assuming
that the equations describing the model are deterministic, recursive and non linear, and
assuming that the equations are modeling the TSP) for the model not to be chaotic the
following must occur:
o+ Assume that on a certain input, the model converges to a certain tour.
14
o+ Assume that numerical changes occur in the initial value conditions. Assume that the
changes are being numerically insignificant from the initial values.
Then it is expected that the insignificant changes are ignored by the model and the
model should be producing the identical tour with the run that had no perturbation in
its input values.
To provide evidence suggesting that the Hopfield-Tank neural network for the TSP has a
chaotic behavior, we must show that a small (negligible for all computing purposes) variation
of the initial conditions has a significant influence on the convergence of the network, validity
and length of the tours. If this is true then it can be concluded that the network has a chaotic
behayior, because the experiment indicates that the non linear recursive equations describing
the llopfield-Tank TSP neural model for small (negligible) variations of the input variables,
produce "unexpected" results ("unexpected" being the convergence of the model to a state
that does not correspond to the tour the network converged with the unperturbed input
values).
To show that this is the case, we have to address the question of what constitutes neg-
ligible from the computational point of view and then show that the model will produce
"unexpected" results. Clearly, assuming a large number representation, the smallest possi-
ble "noise" that is allowed by the number representation of the simulation tool can be viewed
as a negligible number when used to differentiate two values. In conducting the second ex-
periment we reduced the initial noise to the absolute minimum that our machinery will allow,
that is adding or subtracting 1 from the least significant bit (LSB) of the mantissa of the
double accuracy (8 byte) floating point representation of the suggested initial value 1/N+.
This perturbation of the initial condition results in a set of two values ??, p? that are almost
7
indistinguishable from the initial 1/N+ value. We run as many experiments as practicable
which in our case it happened to be 21,249 from which 7,185 converged to valid tours (that
is 33.81%). This is an improvement from the 24% rate we got initially but it clearly suggests
nothing as the model should have converged to the same tour all the runs. Again as we
observe in Figure 5, the resulting lengths span the entire range of possible lengths we have
found during the experimentation for this model problem. Clearly as the figure suggests the
negligible noise of the level of 1O-'?% is more than enough to generate a perturbation that
produces "unexpected" results.
Even though there is no true meaning, (producing better tours when the model should be
producing identical tours is hardly of any meaning) it can be observed that the valid tours
are of much better quality than the tours observed in the previous experiment! Clearly the
distribution of the lengths for the valid tours in figure 6 shows a clear preference to shorter
tours. Also similarly to the previous experiment, by breaking the simulations into chunks
of 1000 runs we see that the behavior of the network is the same as reported by the total
statistics.
7As the previous experimentation suggests and as the figures to follow will also suggest, the number of
runs does not influence the overall outcome of the conclusions.
15
D?ent oulcomes ? 21249 woe (sorted)
4.5
3.5
M
IM
2. --H--H_________________________
0.5			1.5
x 10
Figure 5: Different outcomes (lengths) resulting from a starting point of only io--H'4% noise.
Dmsoufoo1 of lengIfe of the good fours (7155 otn of 21249 woe)
1600K			-.Th
Thi
1400L . 1
4			?i
1000
500			11			Y
?1
3.5			4			4.5			5
Figure 6: Distribution of the lengths of only the valid tours where the initial point have
10--H14% noise.
16
TSP Tour Length Stateoxo tor the r9duret fl?euI ro?se HT ??trrre
4-5
I			max
`a
`5
4-
0 -? 0			-?			-?			0 0 0 rnet?afl
15			30
toeteot 1O00eknutat?re
2			----- _______			_____			____
25
Figure 7: TSP Tour Length Statistics for the HT simulations, where the initial point had
minimum noise.
Figures 7 and 8 display those statistics, additional information can be found in Appendix
A which includes statistics for every 50, 100, and 500 runs, as for the experiment # 1.
All the sets of 1000 runs contain very good tours, the maximum tours are of length
approximately 4.5, compared with the maximums in Experiment #1 that are larger than
5.5; and more impressively, the mean and median tour lengths are at about 3.25, compared
with the corresponding ones of Experiment #1 that are above 4.0. Also the median is always
smaller than the average. While we do not have any explanation for this outcome, the bottom
line for the experimentation is that the negligible perturbation will produce similar results as
other larger perturbations. Further, while the network should be converging to a single tour
it is observed that the model converges to almost all possible combinations. This behavior
with the setting of the experiments allows us to suggest that for the city problem we consider
the neural model has a chaotic behavior.
Additional experimentation : In order to appreciate the effects the chaotic behavior
has on the outcome of a run we did two additional experiments. The main theme of those
experiments is the consideration of some "particular" conditions. In the first experiment we
considered three different initial U matrices and observe closely the run. We denoted those
matrices as U1, U2 and U3. Their values are shown in Tables 4, 5, and 6 in Appendix B. They
consist of two different values ?			(3fb1111111111112)16 and p			(3fb1111111111110)16.
Note that the o and p representations are in hexadecimal. The numbers for the initial
conditions are either OL or ? and they are obtained by adding and subtracting I to the
least significant bit of the mantissa of 1/N+ with the entire 1/N+ 64-bit number being
(3fb1111111111111)16 in hex.
In following closely the trace (see Figure 9) of the three runs we observe that there are
multiple common "convergence" points however at the end two out of three runs converge
17
Co?ergence ofthe rooo? in??fnofse ?5irrMJttt?ofls
1035
It
34
33
532
? 31
10
.30
\ ;7?\\\) \\ !\ 1TA
2t0 --H-_________			______________
In			15
20
fte0,of1000srrnitaf?ons
35
Figure 8: Percentage of HT simulations converged to valid TSP tours, where the initial point
had minimum noise.
at the same length value. This scenario occurs even though the difference between the three
initial states is, in any numerical respect, insignificant. Actually, the difference between all
21,249 initial states is insignificant. Despite that, the Hoplield-Tank algorithm terminated
in almost all possible different tours, valid and invalid; in the same way as when the initial
states were coming from the larger initial region proposed by them.
In experiment # 2 we have shown that a small deviation of some initial conditions generate
unpredictable results exhibiting a chaotic behavior. In the experiment we have assumed that
the initial conditions have been perturbed at random. An interesting question to investigate
is the following:
o+ How many values should be perturbed for the model to exhibit a chaotic behavior?
To answer this question we operated as follows: First we chosed the initial conditions that
resulted in a simulation that converged to a legitimate tour. We checked on the neighborhood
of the initial starting point U1 of the previous experiment. The tour the matrix U1 converges
happens to be the shortest tour our runs converged to. We changed exactly one value of the
initial matrix: if it was o? it was changed to P and vice-versa. We have performed all 100
possible experiments. That is, from the initial matrix U1 we generate 10 x 10 = 100 initial
matrices U that only differ from U1 at the position i, j. The lengths of the tours that resulted
from running the Hopfield-Tank network with these matrices as initial states, are displayed
on Table 3. In the table the position (i,j) reports the outcome of the simulation for the
initial condition matrix with the change of the value U1(i,j) to the value U(i,j). Invalid
tours are indicated by using italics. The outcome of this experimentation is approximately
the same as for the experiments ? 1 and # 2. The over all conclusion is that it is enough to
insignificantly perturb one of the initial values for the network to exhibit a chaotic behavior.
18
Trace of three different runs
.5
?0
0)
c
a)
2
?II... --H
--H __ I
I--H?			--H Io+--H?--Ho+
IIs			;? I/?
: I			I			1.: I.
.1I			I: I
I			j rt ??
- I
II'--
.???
r			I			I I
50
100 150 200 250 300 350 400 450 500
Time step index
Figure 9: Trace ofthree different runs.
19
1			3.902			3.019			2.803			4.342			3.180			3.785			3.595			2.836			3.887			3.360
2			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691
3			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691
4			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691
5			2.691			2.904			2.691			2.753			2.778			3.019			2.752			2.691			2.691			3.019
6			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691			2.691
7			4.206			3.427			3.735			3.514			2.873			3.067			3.446			2.753			3.735			4.035
8			2.752			2.752			3.019			2.862			3.735			3.584			2.904			2.778			2.862			3.584
9			3.259			3.609			2.839			2.829			4.018			2.884			2.904			2.904			2.862			3.114
10			3.761			3.735			2.904			2.752			3.785			2.778			3.091			2.947			3.833			3.761
Table 3: Tour lengths resulting by changing the (i,j) entry of U1. Numbers in italic corre-
spond to invalid tours.
In particular we observed that the network converged only 44% of the runs to the expected
tour with length 2.691 when it was expected to converge to this tour always. Further there
are a number of different tours produced by this insignificant change in the initial conditions.
Finally, we have observed that the change of value on the lines 2, 3, 4 and 6 do not change
the convergence length. The change in line 5, gave either the same tour as the original
starting state or some different tours of good quality. The change in the rest of the lines
gave arbitrary and invalid tours. The over all conclusion again is that the model has a
chaotic behavior even for the smallest single value change.
5 Conclusions
In this paper, we considered the llopfield-Tank model for the TSP and investigated its viabil-
ity as a model and its capabilities to produce good results to the hard optimization problem.
Furthermore, we investigated the reasons behind the difficulty of obtaining verifiable results.
The basis of the investigations we conducted were instances of the initial values where the
behavior of the neural network was expected to produce identical tours. We have assumed
that the set of initial values producing identical results need be very close, (close being
determined by the tool used in the experimentation), and we simulated the behavior on a
10-city problem. The 10-city problem has been used by the experimentation to show that
there is at least one city problem exhibiting chaotic behavior in a certain initial condition
settings. In essence our experimentation indicates that the non linear recursive equations
describing the Hopfield-Tank TSP neural model for small (negligible) variations of the input
variables, cause the production of a different tour than the tour it produced before applying
the insignificant initial condition variation. Given that the magnitude of the changes in the
initial conditions are insignificant, it is expected that the model produces the same identical
tour. Because this is not the case, the essence of our experiment is captured by stating
20
that the Hopfield-Tank network has chaotic behavior determined by the non linear recursive
equations and indicated by the "unexpected" results when small input variations are applied
in the network with all of the other parameters of the network fixed. Because an instance
of the network exhibits chaotic characteristics we postulate that in general the equations
describing the Hoplield-Tank neural network are inherently chaotic.
More in particular, after running more than 65000 simulations, we have established the
following for the llopfield-Tank neural model for the TSP
o+ The smallest possible perturbation of some initial values will alter the tour correspond-
ing to the initial conditions before the perturbation.
o+ Assuming that for a given set of values, before perturbation, the model converges to a
?egitimate tour, a small insignificant perturbation in some of the values may cause the
model to converge to an illegitimate tour.
The effect on the initial tour the negligible perturbations on some values in the initial
conditions has, is that it produces almost all possible tour lengths when the running of
the model converges to a valid solution.
We have shown that the model behaves as indicated by the previous three items even
with the perturbation of a single value (the perturbation also being numerically insignif-
icant for computation purposes).
o+ Finally, our experiments suggest that a small number of runs is sufficient to characterize
the behavior of the llopfield-Tank network model for the TSP.
The overall consequence of our findings regarding the viability of the llopfield-Tank model
and the cause of the controversy surrounding the llopfield-Tank model for the TSP can
summarized by the following:
The cause of the llopfield-Tank neural network for the TSP controversy and the diffi-
culties in reproducing results is the chaotic behavior of the model. Consequently the
controversy should have been expected.
The finding of useful results for the TSP using the Hopfield-Tank network are purely
casual and not to be attributed to the viability of the model. In essence the llopfield-
Tank neural network for the TSP is as viable as chaotic systems can be.
References
?ANF90J S. V. B. Aiyer, M. Niranjan, and F. Fallside. A theoretical investigation into
the performance of the hopfield model. IEEE Transactions on Neural Networks,
1(2):204--H215, 1990.
21
[B189]
[Biz91j
[BWLM88]
[CR89]
[11op84]
[11581]
[HSL88j
D. E. Van Den Bout and T. K. Miller III. Improving the performance of the
hopfield-tank neural network through normalization and annealing. Biological
Cybernetics, 62:129--H139, 1989.
A. R. Bizzari. Convergence properties of a modified hopfield-tank model. Bio-
logical Cybernetics, 64:293--H300,1991.
R. D. Brandt, Y. Wang, A. J. Laub, and 5. K. Mitra. Alternative networks for
solving the traveling salesman problem and the list-matching problem. IEEE
International Conference on Neural Networks, 11:333--H340, July 1988.
R. Cuykendall and R. Reese. Scaling the neural tsp algorithm. Biological Cy-
bernetics, 60:365--H71, 1989.
J. J. Hopfield. Neurons with graded responce have collective computational
properties like those of two state neurons. Proc. Nat. Acad. Sc. U.S., 81:3088--H
3092, 1984.
II. V. Henderson and 5. R. Searle. The vec-permutation matrix, the vec operator
and kronecker products: A review. Linear and Multilinear Algebra, 9:271--H88,
1981.
5. U. Hedge, J. L. Sweet, and L. W. Levy. Determination of parameters in a
hopfield/tank computational network. Proc IEEE Int Conf Neural Netw, 11:291--H
298, 1988.
[HT85] J. J. Hopfield and D. W. Tank. Neural computation of decisions in optimization
problems. Biological Cybernetics, 52:141--H152, 1985.
[Joh87] D. 5. Johnson. More approaches to the travelling salesman guide. Nature,
330:525, December 10 1987.
[Joh90] D. 5. Johnson. Local optimization and the travelling salesman problem. Proc
17th Colloq on Automata, Languages and Programming, pages 446--H461,1990.
[Kah89] A. B. Kahng. Traveling salesman heuristics and the embedding dimension in
the hopfield model. Proc IEEE Int Joint Conf Neural Netw, 1:513--H520,1989.
[KPKP90]
B. Kamgar-Parsi and B. Kamgar-Parsi. On problem solving with hopfield neural
networks. Biological Cybernetics, 62:415--H423, 1990.
[LDFVP93] W. Lin, J. Delgado-Frias, 5. Vassiliadis, and G.G. Pechanek. Machine and bit
precision on the hopfield neural network model for the tsp. Proc IEEE Int Conf
Neural Netw, Nagoya, Japan, pages pp. 1516--H1519, 1993.
Ch. Papadimitriou and K. Steiglitz. Combinatorial optimization, Algorithms
and complexity. Prentice Hall, 1982.
22
[PS82]
[Szu88]
[WP88]
[XT9l]
Szu. Fast tsp algorithm based on binary neuron output and analog input using
the zero-diagonal interconnect matrix and necessary and sufficient constraints
of the permutation matrix. Pwc JEEE Int Conf Neural Netw, 11:259--H266, 1988.
G. V. Wilson and G. S. Pawley. On the stability of the travelling salesman
problem algorithm of hopfield and tank. Biological Cybernetics, 58:63--H70, 1988.
X. Xu and W. T. Tsai. Effective neural algorithms for the traveling salesman
problem. Neural Networks, 4:193--H205,1991.
23
A Appendix
In this Appendix we report additional charts supporting the claim suggesting that: A "small"
number of runs is sufficient to characterize the overall behavior of the model. The various
figures plot statistics of the TSP model for every 50, 100, and 500 runs. The runs are
performed on two different scenarios. The first scenario involves a "noise" level equal to the
"noise" level used by the original Hopfield-Tank proposal. The second scenario involves a
``noise'' level that is negligible for all computing purposes. The charts are ``labeled'' with
either "original noise" or "reduced initial noise" for the first and second scenario respectively.
For every scenario we plot two different figures. The first figure regards the lengths of the
TSP tour, the second reports the percentages the model converged to. As the figures suggest
the model even for a modest number of runs (modest being 50 or more but less than 1000)
supports the following conclusions:
o+ The model does have a very poor convergence rate (seldom exceeds the 50% convergence
rate).
o+ It does not converge to the same tour when it supposed to.
o+ It assumes a plurality of tour lengths when it converges to a tour.
b
TSPTo??n?h????torthe???Ittt? noseHT??nu?aor?
6Th?-
M
o+ v 7			o+
4#ffl g?
44 4
4?
20 o+0 80 100 120 140 1? ?
Sets?t0s?to?
24
ronv??rsre of the original ir6? rolse fT srro??rs
2
12
?2t
en			im			i?o			IdO			ISO			lao
20			40			60
Se?of
20
TSP Tour ?ergih tteffstss for the rectoef Iriffef noise fT simofeffors
2
If
--H35
4			?			--H5
4			5
`Sr
____y?)y4y1?
sets of 50 s?rmjIef?ons
25
convergBnce of the re(Load irO? nmse KT snw??ns
?15 I
100i4o?
200			250			300			350			400			450
Sets of 50 ?rru;at?ons
-f
15
3'5
TsP Thw Len? StnBb? f? fe oflg?oef ?f? no? HT swnu?-e
A
2			-			--			- __________
10			20			30			40			50			60			?			50			100
Sets of 100 s?noin?ons
26
forwe?noe of Ire orIginal int? noise HT sknu??rs
`r6			?
24
?18
16
0			10			20			30			40			50			60			70			80			60			100
telsot 100 arnt?he
TSP Tour Length Statet? for the re(1?oet irnt? nose HT ???Iatiore
4?54<?6$ffi)?ffi1rhIr?ffiffi????????????
-a
oIIt,???-			clan
u			50			100			150			200			250
sets of 100 simulltlone
27
Com,er? ot the re?1iced i???' no?se HT sknu??ns
?45
:20
?sof 1OO?rmJ??ns
TSP Tour Le?h ??EtIcs or the??` ?n??? mhe HT s?rru??ns
5-5
W?45
3-5
5-
Q			?			rne(,?
2			4			8			10			12			14			16
Sets ot 500 sn'itetbre
28
com'ergsnce ? the or?g?na? I??I n?se KT sIrtu??s
?27
? 26
025
.24
?21
j2o['
Y?\ I' I
y y
ti
Sets of 500 ??ou?brs
TSP Tour Lerqh stetet-?ttrtte tsrret ?rO?? tette HT etmttet?ons
-e
4-
rn?r
-?			- _______ _______
15			20			25 ?			as
setoft500Corrutet?ns
29
Corwerg? ? the re(ljced In?? ..? HT ?irmJ??ns
-?36
? 37
s 36
.35
?34
-33
T32
?31
30
j\ !
i			??) \ ?!?\l \1kJ			`??
0 0 15 20 25 30 35 40 45
sets of 500 ?rr'J??ns
p ?			? p ? p ?
? p ?			p p ?			? p
Q ? ? p ? p ? p p
?13f3PPoLPPPP
? p ?			OL ?
Table 4: Initial matrix U1
30
B Appendix
???oL?PPPPoL
? p p p o?			o?
? p ? ? p ? p p ?
P???PPoLotPP
OL ?			? p p
Table 5: Initial matrix U2
OL			Q ? p ?
??PQPoLPPflP
ppp?pp?ppp
p			?			p ?			ct?
p			?			?			p ? p p
Table 6: Initial matrix U3
31
