4
$\begingroup$

[This question was initially asked here. It went unanswered so I thought I should ask it in a different community.]

I am reading this paper by Hopfield et al. On page six, the authors defined the energy function of the Traveling-Salesman-Problem (TSP) mapped onto an artificial neural network as follows:

$$E = \frac{A}{2} \sum_X \sum_i \sum_{j \ne i} V_{Xi} V_{Xj} + \frac{B}{2} \sum_i \sum_X \sum_{X\ne Y} V_{Xi} V_{Yi} + \frac{C}{2} (\sum_X \sum_i V_{Xi} - n)^2 + \frac{1}{2D} \sum_X \sum_{Y\ne X} \sum_i d_{XY} V_{Xi} (V_{Y, i+1} + V_{Y, i-1})$$

Here the first three terms maintain correctness of the function while the final term calculate actual distance of the tour. Later on page seven, the authors picked the values of A, B, C and D for simulation.

I don't understand on what basis they choose those values. Any help?

$\endgroup$
  • 3
    $\begingroup$ Pretty much arbitrarily. $\endgroup$ – MCH Jul 12 '13 at 14:32
  • $\begingroup$ @MCH If arbitrarily how can we use it for practical purposes? $\endgroup$ – Omar Shehab Jul 12 '13 at 14:37
  • 2
    $\begingroup$ When it comes to heuristics, we care more about whether things work rather than why. $\endgroup$ – MCH Jul 12 '13 at 21:44
  • $\begingroup$ @MCH, I am afraid I don't get it yet. Why didn't Hopfield just defined A, B and C to be 2's so that we could get rid of the fractions? $\endgroup$ – Omar Shehab Jul 13 '13 at 5:53
  • 2
    $\begingroup$ @Kaveh, when we implement this expression, do we take derivatives at any point? $\endgroup$ – Omar Shehab Jul 14 '13 at 13:37
10
$\begingroup$

There is no way to choose the parameters A, B, C, D properly; as it is the case for most heuristics, the parameters are chosen ''by experience''. Worse, there is no guarantee that the solution (the array of the outputs) of this heuristic is indeed a feasible TSP tour!

In this context, perhaps interesting to read: Wilson and Pawley, On the stability of the Travelling Salesman Problem algorithm of Hopfield and Tank, Biological Cybernetics 58 (1988) 63-70.

To your first comment: I don't think that this TSP energy function is useful for practical purposes. If you want to solve TSP in practice, maybe here is the right starting point.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.