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$
6
  • 3
    $\begingroup$ Pretty much arbitrarily. $\endgroup$ Jul 12, 2013 at 14:32
  • $\begingroup$ @MCH If arbitrarily how can we use it for practical purposes? $\endgroup$ Jul 12, 2013 at 14:37
  • 2
    $\begingroup$ When it comes to heuristics, we care more about whether things work rather than why. $\endgroup$ Jul 12, 2013 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$ Jul 13, 2013 at 5:53
  • 2
    $\begingroup$ @Kaveh, when we implement this expression, do we take derivatives at any point? $\endgroup$ Jul 14, 2013 at 13:37

1 Answer 1

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 and acknowledge you have read our privacy policy.

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