Hill Climbing Algorithm

[zak100]

Hi,

 

I am trying to understand the Hill Climbing algorithm. I found a question at:

https://stackoverflow.com/questions/8946719/hill-climbing-algorithm-simple-example

 

Somebody please guide me.

 

Zulfi.

[Ghideon]

17 hours ago, zak100 said:

I am trying to understand the Hill Climbing algorithm.

The approach towards understanding may depend on the background knowledge and/or if one is struggling with some specific aspects of the algorithm. Below is an overview, I assume the question is about simple hill climbing rather than any of the variants. You need to be familiar with the underlined terms. Look them up or ask here.

Hill climbing algorithm belongs to the family of local search. Starting with an arbitrary solution to a problem iterations ares used to attempt to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

Note that depending on the problem hill climbing finds optimal solutions or local optima which are not necessarily the best possible solution out of all possible solutions. Problems where hill climbing finds optimal solutions are convex problems where every local maximum (or minimum) is also a global maximum (or minimum). For problems that are not convex the hill climb may get stuck in a local extreme point that is not the global extreme point. To avoid that there are several available methods that may be selected by knowing more about the specific problem to be solved. 

The outcome when using hill climb algorithm (success or failure) is sensitive to the shape of the search space, such as local extremes, ridges and alleys and plateaus. 

 

Note 1: The link in the opening post goes to a specific question about a specific example. The question was answered in detail at the link; I have no further comments at this time. 
Note 2: I loosely based my answer on Wikipedia.

Edited October 4, 2020 by Ghideon

[zak100]

Hi,

Thanks for your response. God blesses you. They are saying that if I got stuck at 'g' , I can select 'j' or 'c', for selecting 'j' I have to go back to 'a' which is backtracking and they are saying that backtracking not possible. Please guide me how to seect 'j' or 'c' without back tracking.

 

Please guide me'

Zulfi.

[Ghideon]

I assume we are discussing simple hill climbing.

6 hours ago, zak100 said:

They are saying that if I got stuck at 'g' , I can select 'j' or 'c', for selecting 'j' I have to go back to 'a' which is backtracking and they are saying that backtracking not possible. Please guide me how to seect 'j' or 'c' without back tracking.

Not sure what the above is about, it does not sound like hill climbing. To make it clearer lets first focus on:

On 10/4/2020 at 4:21 AM, zak100 said:

understand the Hill Climbing algorithm

Backtracking is not part of simple hill climbing. So while using backtracking to solve a specific problem may be a perfectly valid approach doing so would introduce some other algorithm than simple hill climbing. 

a: Are you trying to find the best possible solution (the global optima) instead of a local optima? Do you know the difference between global optima and local optima and how they are connected to hill climbing?

b: Have you so far understood the difference between guarantee (P=1) to find the best solution vs a probability P<1 to find the best solution? An improvement to simple hill climbing may increase the probability of finding a global best solution but it is no guarantee. You seem to wish to select some specific value or get to a specific result but that may not be possible by using hill climbing. Do you know what properties of the hill climb algorithm and what properties of a problem that may cause that to happen? Hint: My first post contains the topics you may want to look at. 

Once you fully understand simple Hill Climbing you may want a modified version, there are several versions to choose from.

[zak100]

Hi,

I am just interested in Simple Hill climbing, This is what I have to do. I am just telling you the problem which the original posted faced in the stack Exchange link. If you please read the question asked by the poster at the stack exchange link which I have provided and then kindly tell me how can I solve that problem, it would be helpful to me. Local minima is related to current segment but global minima is related to the whole tree.

Zulfi.

[Ghideon]

32 minutes ago, zak100 said:

I am just interested in Simple Hill climbing

Ok.

32 minutes ago, zak100 said:

Local minima is related to current segment but global minima is related to the whole tree.

True.

32 minutes ago, zak100 said:

I am just telling you the problem which the original posted faced in the stack Exchange link. If you please read the question asked by the poster at the stack exchange link which I have provided and then kindly tell me how can I solve that problem, it would be helpful to me.

Hill climbing will stop on a local minima and will not continue to search the whole search space for a global minima; hill climbing is a local search. Your question that seems to be related to leaving some local minima that the algorithm found and moving on to find a global minima. Since simple hill climbing does not work that way there is no solution to your problem under the given conditions. You need a convex problem to guarantee that the global minima is found. For problems that are not convex simple hill climbing will find a local minima* and that is fine, that is what the algorithm is designed to do. 

 

*) or maxima if that is searched for

Edited October 5, 2020 by Ghideon

[zak100]

Hi,

In the attached image why we don't go to ABHK?

 

Please guide me.

 

 

 

 

 

Zulfi.

Edited October 6, 2020 by zak100

[Ghideon]

1 hour ago, zak100 said:

In the attached image why we don't go to ABHK?

Do you mean why we don't go to ABHK using simple hill climb? Please state questions more clearly. 
To answer one have to assume things that are not in the picture. I what order are the nodes searched? Can we assume left to right? 

Here is the solution:
Start from A with costs =10.
Apply what you have learned from earlier posts: Write down the nodes (B, C, D) that are selected or rejected and why they are rejected or selected.
Continue the analysis from the selected node.

When you perform the steps above, what is the final state you reach? If you do not reach J (by going ABGJ) where did you select another node along the path? Was the selection done by applying something else that simple hill climbing?

 

 Note: Maybe the source for the picture have additional text explaining this specific example in more detail?

Edited October 6, 2020 by Ghideon

[zak100]

Hi,

I read the following post: https://stackoverflow.com/questions/8060028/what-is-the-difference-between-hill-climbing-and-greedy-algorithms

It says that Hill Climbing will generate the solution randomly whereas Gradient Search will always use the smallest value.

That looks fine with me.

 

Zulfi.

 

[Ghideon]

You asked this:

On 10/6/2020 at 6:09 AM, zak100 said:

In the attached image why we don't go to ABHK?

I tried to guide you . 

Have you understood hill climbing? That was your initial question. 
Have you solved the ABHK example and understood why the hill climb gets the result the in Hill Climbing Example 2 picture you posted?
If you have not yet understood the ABHK example, where are you stuck? Please provide details, so additional guiding is possible.
If you have lost interest in the ABHK example you posted, please say so before moving on to new material.
In what way is the following related to the ABHK example? Pleas provide context

5 hours ago, zak100 said:

I read the following post: https://stackoverflow.com/questions/8060028/what-is-the-difference-between-hill-climbing-and-greedy-algorithms

It says that Hill Climbing will generate the solution randomly whereas Gradient Search will always use the smallest value.

That looks fine with me.

 

[zak100]

Hi,

I have already provided the solution, please tell me your comments if its wrong or right, if its wrong, I would search more.

 

Zulfi.

[Ghideon]

16 minutes ago, zak100 said:

I have already provided the solution, please tell me your comments if its wrong or right, if its wrong, I would search more.

Do you mean this?

On 10/7/2020 at 12:41 AM, zak100 said:

It says that Hill Climbing will generate the solution randomly whereas Gradient Search will always use the smallest value.

That is not related to your questions so far. We are discussing simple hill climb: 

On 10/5/2020 at 9:30 PM, zak100 said:

I am just interested in Simple Hill climbing

 

Please be more specific and add more context to your posts.

 

Edited October 8, 2020 by Ghideon