This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
The main problem with hill climbing (which is also sometimes called gradient
descent) is that we are not guaranteed to find the best solution. In fact, we
are not offered any guarantees about the solution. It could be abysmally bad.
Imagine that you are in the Alps and you want to find the highest peak. You
parachute into the Alps but when you land you are in thick fog. Undeterred you
start moving upwards. Eventually, you come to a point where you cannot move
upwards anymore.
You reason that you have found the highest peak.
Of course, that is not necessarily the case. There might be many other higher peaks around you but you cannot see them because of the fog.
And this is exactly the same problem with hill climbing. When we reach a position
where there are no better neighbours, it is not a guarantee that we have found
the best solution. In fact it could be one of the worst solutions. In terms
of the Alps analogy we might be standing on a small hillock instead of at the
top of the mountain range.
Therefore, the solution that hill climbing returns may not be that good.
We can represent the problem we have just described on this diagram.
|
You can see that we will eventually reach a state that has no better neighbours but there are better solutions elsewhere in the search space.
The problem we have just described is called a local maxima.
One solution to this problem is to conduct a multi-start hill-climb.
This consists of a series of hill climbing searches, each one starting at a
random point in the search space.
The best result is saved from all the searches and is returned as the best
solution.
But, unless we look at all possible solutions we are still not guaranteed to find to global optimum.
Another type of problem we may find with hill climbing searches is finding
a plateau. This is an area where the search space is flat so that
all neighbours return the same evaluation.
If a search hits this type of problem the usual solution is to conduct a random walk until you find an area that starts to give better quality solutions (or you may find that no neighbours are ever of better quality - in which case we can assume we are on the top of table top mountain!)
· Russell, S., Norvig, P. 1995. Artificial Intelligence A Modern Approach. Prentice-Hall
| Previous Page | Index Page | Next Page |
Last Updated : 25/01/2002