### Hill Climbing: A simple optimization method

#### by Amit

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.

**Illustration: **

** **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:

**Case I:**

**Case II:**

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.

**Added: **13-April-2012

**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()

currentPoint.setQuality()

while (currentPoint is not good enough)

tempPoint = makeLittleChange(currentPoint.clone())

tempPoint.setQuality()

if (tempPoint.quality > currentPoint.quality)

currentPoint = tempPoint

loop

return currentPoint

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.

Cheers!

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?

Thanks!

wonderful points altogether, you just gained a brand new reader.

What may you recommend about your publish that you made some days ago?

Any certain?

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.