Hill Climbing: A simple optimization method
An optimization problem can usually also be modelled as a search problem, since we are searching for the optimum solution from among the solution space. Without any loss of generality, we can assume that our optimization problems are of the maximization category.
So, here is the hill climbing technique of search:
- Start with an initial solution, also called the starting point. Set current point as the starting point
- Make a move to a next solution, called the move operation
- If the move is a good move, then set the new point as the current point and repeat (2). If the move is a bad move, terminate. The last current solution is the possible optimum solution.
Move operation: The move operation is problem dependent. In a discrete optimization problem, such as the Travelling Salesman Problem, a move operation would probably shuffle a couple of positions in the original solution. In problems where the search space is continuous, techniques such as those used in steepest ascent/descent methods are used to obtain the next solution.
Good/Bad Move: A move is said to be good, if a point obtained by the move operation improves the quality of the solution, as compared to the previous solution. A bad move is defined similarly.
Quality of solution: In all optimization problems, there is always atleast on quantity (in single-objective optimization problems) that we want to improve. A quality of solution is judged on the basis of this quantity. In a function maximization problem, the function value itself is a measure of the quality.
Let us now consider a simple one-peaked function f(x) = -x*x and we seek the maximum of this function. This is a plot of the function:
- Let A be the starting point, and let the move operation take us to point B (pretty far away; usually it will be much closer to A but it will serve the purpose here). Consider the quality of the two solutions, A & B
- B definitely improves our search, since the function value at B is more than A, we keep moving, setting B as the current point
- Our next move operation takes us to C (our desired solution, but we don’t know that yet). Now, compare B & C. Since C is definitely a good move, so, we set the current point to C and keep moving
- Our next move takes us to D. On comparing C &D, we see that it was a bad move, Hence we terminate. Hence, the current point, C is our solution.
The following plot shows the results obtained via simple Hill-climbing on the above function:
Simplicity is a hallmark of the Hill climbing search procedure. However, its simplicity comes at a price. In a multi-modal landscape, Hill climbing procedure will terminate the first peak it finds. It may be the global maximum, but it could also be a local maxima. This is illustrated below:
As you can see from the figures above, depending on your starting point, you will reach the nearest peak of your function. That is definitely a weak point in a multimodal landscape. To overcome this limitation random restart hill climbing algorithm, i.e with a random initial point has been proposed (by who?).
Hill climbing has been used on its own for many optimization problems (See http://scholar.google.co.in/scholar?q=hill+climbing) as well as as a local search operator in global search algorithms, like Evolutionary Algorithms (GAs, ES, etc).
This is a simple Python implementation of hill climbing that I used for illustration. It contains some of the functions that I plotted above as well.
Hill-climbing with Multiple Solutions
As you have noticed earlier, the classic hill climbing will not go beyond the first peak it reaches. In a multi-modal landscape this can indeed be limiting. I made some simple changes to the above algorithm to allow hill-climbing to go beyond the first peak it reaches. They are:
- Multiple starting points: Instead of searching for the highest peak, starting from a single peak, search from multiple points. This simulates a parallel search, similar in principle to the way population based algorithms function. This is also sometimes referred to as a random-restart hill-climbing.
- Random move when stuck: If a particular point gets stuck on its uphill climb, a random noise is added to it. A point is allowed to be stuck for a specified number of times, before beginning with the next point, if any.
With these changes, I saw that the algorithm is now able to find the highest peak with two simple 1-D functions:
The updated code is now available here Some other minor changes in the code are given as comments. The code also reports the best solution reached with each of the multiple starting points: (the output below is for the sample function 1)
Best Solution with 1.142805 :: 0.260280
Best Solution with 0.857778 :: 0.503222
Best Solution with 1.156183 :: 0.260280
Best Solution with 0.412196 :: 0.780970
Best Solution with 1.626643 :: 0.108062
Best Solution with 1.647178 :: 0.108062
Best Solution with 1.306945 :: 0.260280
Best Solution with 0.320459 :: 0.972905
Best Solution with 1.041339 :: 0.260280
Best Solution with 0.655546 :: 0.780970
One final plot to show how the multiple points searched the peaks:
Solutions from each point goes to its nearest peak, effectively forming a parallel search. Its interesting to note that how it finds all the peaks. This is a very naive way of finding all the optima in a Multi-modal optimization algorithm.
Please feel free to drop a comment/email to discuss this.
very very gud explanation thanks a lot
Hi, good topic!
Just to add, in the Hill Climbing algorithm you don’t need to stop searching if the current
point is worse than the previous, you simply don’t update the current point:
currentPoint = randomSolution()
while (currentPoint is not good enough)
tempPoint = makeLittleChange(currentPoint.clone())
if (tempPoint.quality > currentPoint.quality)
currentPoint = tempPoint
Hello. Thanks for your comment. What would be your termination criteria in this case? A maximum number of iterations?
Do you intend to implemetn the makeLittleChange procedure as a small random change from its current value?
Wonderful, what a webpage it is! This web site provides valuable data to us, keep it up.
My programmer is trying to persuade me to move to .
net from PHP. I have always disliked the idea because
of the costs. But he’s tryiong none the less. I’ve been using Movable-type on a
variety of websites for about a year and am concerned
about switching to another platform. I have heard fantastic things about blogengine.
net. Is there a way I can import all my wordpress content into it?
Any kind of help would be greatly appreciated!
I absolutely love your website.. Very nice colors & theme.
Did you build this amazing site yourself? Please reply back as I’m attempting to create my own personal website and would love to find out where you got this from or exactly what the theme is named. Many thanks!
It’s perfect time to make some plans for the future and it’s time to be happy.
I have read this publish and if I could I wish to suggest you few fascinating issues or advice.
Perhaps you can write subsequent articles referring to this
article. I wish to read more issues approximately it!
I do noot even know the way I stopped up here, however I assumed this
publish was great. I don’t recognise whoo youu might be but definitely you arre
going to a famous blogger should youu aare not already.
Please let me know if you’re looking for a writer for your weblog.
Youu have some really good posts and I feel I would be a
good asset. If you ever want to takme some oof the load off, I’d absolutely love to
write some articles for your blog in exchange for a link back
to mine. Please end me ann e-mail if interested. Cheers!
Hey just wanted to givbe you a quick heads up. The words in your content seem to be running off tthe
screen in Opera. I’m not sure if this is a formatting issue or somethning to do with web browser compatibility butt I figured I’d post to leet you know.
The design look great though! Hope you get the problem
fixed soon. Cheers
I don’t even know the way I ended up here, however I thought this submit used to be great.
I do not understand who you might be but certainly you’re going to a famous
blogger if you happen to aren’t already. Cheers!
The cat will start to dry, dusty, or take a certain food derived polypeptides are found in many cases, the purified by-product, not all events on a chart, excluding the
totals. The dosage in the form of support with you one-on-one and typically spends an hour while she
dealt with. For children, opening a” dietary ingredient” intended to supplement traditional healing methods.
When a individual car or truck is chosen by a person the program will exhibit which auto sections have presently been marketed relating
to the car or truck. Though many credit counseling organizations are nonprofit, their services may not be free, cheap,
or even legitimate, so do your research. When playing golf you
want to know of which you are usually choosing the best tools offered on the course.
Hello would you mind sharing which blog platform you’re working with?
I’m looking to start my own blog soon but I’m having a tough
time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most
blogs and I’m looking for something completely unique.
P.S Sorry for being off-topic but I had to ask!
I believe this is among the most important information for me.
Andd i’m happy reading your article. However
want too commentary on some normal things, The webste taste is ideal, the
articles is actually great : D. Just right job, cheers
plz help me to implement hill climbing using c program
am stucked ,plz help me
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some time and
was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your new updates.
Hey would you mind letting me know which hosting company you’re using?
I’ve loaded your blog in 3 completely different web browsers and I must say this blog loads a lot
faster then most. Can you recommend a good hosting provider at a fair price?
Kudos, I appreciate it!
Ridiculous story there. What happened after?
wonderful points altogether, you just gained a brand new reader.
What may you recommend about your publish that you made some days ago?
Hello, i believe that i saw you visited my website thus i came to return the prefer?.I am attempting
to find issues to improve my web site!I assume its good enough to use a few of your ideas!!
Appreciate thhe recommendɑtion. Will try it out.
Os cuento: A mi perro Eros no le gustaba ningún pienso y por casualidad se me ocurrió pedir el de cachorros para razas grandes.
We are using the ja_purity2 and have enclosed the template to the center of the display screen (much such as the joomla website). Now I wish to add a shadow for the left and right from the “confined” template/website but have no clue on how to get it done.. Any help would be valued.. Thank You beforehand..
“A good golfer has the determination to win and the patience to wait for the breaks.” -Gary Player