Can neural network with unsupervised learning minimize a cost-function?

Question

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)?

Answer 1

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.