Hill climbing and single-pair shortest path algorithms

Question

I have a bit of a strange question. Can anyone tell me where to find information about, or give me a little bit of an introduction to using shortest path algorithms that use a hill climbing approach? I understand the basics of both, but I can't put the two together. Wikipedia has an interesting part about solving the Travelling Sales Person with hill climbing, but doesn't provide a more in-depth explanation of how to go about it exactly.

For example, hill climbing can be applied to the traveling salesman problem. It is easy to find a solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much better route is obtained.

As far as I understand it, you should pick any path and then iterate through it and make optimisations along the way. For instance going back and picking a different link from the starting node and checking whether that gives a shorter path.

I am sorry - I did not make myself very clear. I understand how to apply the idea to Travelling Salesperson. I would like to use it on a shortest distance algorithm.

Answer 1

You could just randomly exchange two cities.

You first path is: A B C D E F A with length 200

Now you change it by swapping C and D: A B D C E F A with length 350 - Worse!

Next step: A B C D F E A: length 150 - You improved your solution. ;-)

Hill climbing algorithms are really easy to implement but have several problems with local maxima! [A better approch based on the same idea is simulated annealing.]

Hill climbing is a very simple kind of evolutionary optimization, a much more sophisticated algorithm class are genetic algorithms.

Another good metaheuristic for solving the TSP is ant colony optimization

Answer 2

Examples would be genetic algorithms or expectation maximization in data clustering. With an iteration of single steps it is tried to come to a better solution with every step. The problem is that it only finds a local maximum/minimum, it is never assured that it finds the global maximum/minimum.

A solution for the travelling salesman problem as a genetic algorithm for which we need:

• Representation of the solution as order of visited cities, e.g. [New York, Chicago, Denver, Salt Lake City, San Francisco]
• Fitness function as the travelled distance
• Selection of the best results is done by selecting items randomly depending on their fitness, the higher the fitness, the higher the probability that the solution is chosen to survive
• Mutation would be switching to cities in a list, like [A,B,C,D] becomes [A,C,B,D]
• Crossing of two possible solutions [B,A,C,D] and [A,B,D,C] result in [B,A,D,C], i.e. cutting both list in the middle and use the beginning of one parent and the end of the other parent to form the child

The algorithm then:

• initalization of the starting set of solution
• calculation of the fitness of every solution
• until desired maximum fitness or until no changes happen any more
  • selection of the best solutions
  • crossing and mutation
  • fitness calculation of every solution

It is possible that with every execution of the algorithm the result is differently, therefore it should be executed more then once.

Answer 3

To hillclimb the TSP you should have a starting route. Of course picking a "smart" route wouldn't hurt.

From that starting route you make one change and compare the result. If it's higher you keep the new one, if it's lower keep the old one. Repeat this until you reach a point from where you can't climb anymore, which becomes your best result.

Obviously, with TSP, you will more than likely hit a local maximum. But it is possible to get decent results.

Answer 4

I'm not sure why you would want to use a hill-climbing algorithm, since Djikstra's algorithm is polynomial complexity O( | E | + | V | log | V | ) using Fibonacci queues: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

If you're looking for an heuristic approach to the single-path problem, then you can use A*: http://en.wikipedia.org/wiki/A*_search_algorithm

but an improvement in efficiency is dependent on having an admissible heuristic estimate of the distance to the goal. http://en.wikipedia.org/wiki/A*_search_algorithm