Stochastic Hill Climbing

Question

I am trying to implement Stoachastic Hill Climbing in Java. I understand that this algorthim makes a new solution which is picked randomly and then accept the solution based on how bad/good it is. For example, if its very bad then it will have a small chance and if its slighlty bad then it will have more chances of being selected but I am not sure how I can implement this probability in java.

Whilst browing on Google, I came across this equation, where;

• f respresent the old fitness
• f' respresent the new fitness
• T is a parameter

I am not really sure how to interpret this equation.

Can someone please help me on how I can implement this in Java?

Diez

Pr() is probability. So Pr(accept) is the probability of accepting the solution for a given f, f', and T. – Texas

In order to help you, we'll need more information about the code you've tried and why it doesn't suit your needs. An example would be much appreciated. – Texas

Hi Alex, I am trying to understand this algorithm. I am not really sure how to implement it in Java. – Diez

Answer 1

The left hand side of the equation p will be a double between 0 and 1, inclusively. oldFitness, newFitness and T can also be doubles.

You will have something similar to this in your code:

double p = 1 / (1 + Math.exp((oldFitness - newFitness) / T));
if (Math.random() < p) {
    // accept the new solution

Lenee

Answer 2

You can find a good understating about the hill climbing algorithm in this book Artificial Intelligence a Modern Approach. This book also have a code repository, here you can found this.

And here is an implementation of HillClimbing (HillclimbingSearch.java) in java. But this java file requires some other source file to be imported. It's better If you have a look at the code repository. In this class you have a public method search() -

public List<Action> search(Problem p){}  

From the method signature you can see this method require a Problem p and returns List of Action. To get these Problem and Action you have to use the aima framework.

You may found some more explanation about stochastic hill climbing here

Hope it will help.
Thanks a lot.

Theocritus