1
$\begingroup$

I understand that solving Traveling Salesperson-style problems is a topic of open research, but I'm wondering what the architecture of such a neural network would look like.

Specifically, it's not clear to me how to configure neural networks to solve a non-categorization problem, without any training data.

Here is a concrete problem I am trying to solve:

  • The input into the system is the maximum amount of money the customer is willing to spend.
  • The desired output is a list of cities that the customer will travel to.
  • Our goal is to minimize the cost of the overall trip.
  • Note that the cost function we are trying to minimize is not a direct consequence of the output value. We need to look up the cost of traveling between each origin-destination pair using an external system, and minimize that cost. Further, the cost will never reach zero and we don't know what the target cost looks like (we just know that the lower, the better).

How would the above constraints change the neural network architecture? Is this even solvable using neural networks (if not, what is a better approach)?

$\endgroup$
  • $\begingroup$ Pointer Networks (arxiv.org/abs/1506.03134) have had some success on solving combinatorial optimiaztion problems, including TSP $\endgroup$ – shimao Oct 27 '17 at 21:40
2
$\begingroup$

This is an optimization problem rather than an unsupervised learning problem. You're not trying to learn from examples, but to minimize a function of known quantities. Neural nets can be used to solve this type of problem, but it looks different than solving supervised/unsupervised problems that one typically sees in the machine learning literature (no learning is involved here).

For exmaple, see work using Hopfied nets to solve the traveling salesman problem (Hopfield and Tank 1985, and many others since then). A recurrent network is configured such that it encodes the problem. The network has an energy function that governs the behavior of the network (which tends to move to lower energy states). Each network state corresponds to a possible solution. The weights are set such that low-cost solutions (that respect the constraints of the problem) have lower energy. The network is then run from some initial state until it converges to a low energy (i.e. low cost) solution. The traveling salesman problem is NP complete, so it's probably infeasible to compute exact solutions for large problems. The purpose of this method is to compute approximate solutions in a reasonable amount of time (and to do so in a way that mimics biological neural nets; raw performance isn't necessarily the goal here).

There's no need to limit yourself to neural nets; this is a discrete optimization problem and most methods look nothing like neural nets. There may well be more efficient heuristic approaches. For reading, the discrete optimization, operations research, and computer science literature will probably be more helpful than the machine learning literature.

References:

Hopfield and Tank (1985). Neural computation of decisions in optimization problems.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So if I read between the lines, you are saying that neural are best suited for curve fitting a series of known data points whereas I am trying to minimize the value of a function without any data points. Is that correct? Why do unsupervised neural networks work then? They don't have any examples to work with, do they? $\endgroup$ – Gili Oct 29 '17 at 2:26
  • 1
    $\begingroup$ That's not quite what I'm saying. I'm saying that using a neural net to optimize a function is a fundamentally different problem than both supervised and unsupervised learning. Neural nets have successfully been used to solve optimization problems, as in the paper I mentioned. It's just not common to see them used for this purpose. Unsupervised learning algorithms do learn from examples, btw (but they don't have target outputs). $\endgroup$ – user20160 Oct 29 '17 at 9:01

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.