-
Notifications
You must be signed in to change notification settings - Fork 0
Example: Creating An Optimization Problem For Hill Climbing
This is an example of creating an optimization problem that will be used by the hill climbing optimization framework. There are three main steps: create a class that represents a possible solution, create a class that generates random solutions, and create a class that represents the problem itself.
For this example we will use the problem of optimizing a function. To make this problem more constrained, we will focus on functions with a single independent variable and a single variable ie(the mapping from R -> R). Some example of these types of functions are: f(x)= x^2, f(x)=log(1/x), f(x)=x^4. These function are often referred to as a real valued function with a single variable. To make the problem even more constrained we will only focus on minimization and we will only search for solutions over a range.
For this problem a solution is just a random x value since we are searching for a single x value that minimizes the function. To create a representation of the solution we create a class that implements IHillClimbSolution, but will will add a method to get the x value stored.
Here is the entire class:
public class OneVarSolution implements IHillClimbSolution {
private double score;
private double xValue;
public OneVarSolution(double xValue) {
this.xValue = xValue;
}
public void getXValue() {
return this.xValue;
}
@Override
public double getScore() {
return this.score;
}
@Override
public void setScore(double score) {
this.score = score;
}
@Override
public String toString() {
return "X Value - " + this.getXValue();
}
}Since this framework is developed using Java 1.8 we can make the problem class flexible and easy to use by representing the function being optimized with a lambda. To do this we first must create a functional interface to represent the desired lambda(takes in a single double and returns a double).
Here is the entire interface:
@FunctionalInterface
public interface IOneVariableFunction {
double getFuncValue(double xValue);
}Now we create the class that represents the problem. This class will implement IHillClimbProblem.
Here is the boilerplate:
public class MinimizeOneVar implements IHillClimbProblem {
private IHillClimbSolution initialGuess;
@Override
public IHillClimbSolution getInitialGuess() {
return this.initialGuess;
}
@Override
public IHillClimbSolution getBestSolution(List<IHillClimbSolution> possibleSolns) {
return null
}
@Override
public boolean atPeakOrPlateau(IHillClimbSolution currentSolution, IHillClimbSolution newSolution) {
return false;
}
@Override
public boolean firstSolutionBetterThanOther(IHillClimbSolution current, IHillClimbSolution best) {
return false;
}
@Override
public double scoreSolution(IHillClimbSolution solution) {
return 0.0;
}
@Override
public List<IHillClimbSolution> generateNextSolutions(IHillClimbSolution solution) {
return null;
}
}Now we will create the constructor. For starters we will need to store the function we are optimizing, so will supply it to the constructor. Next we need to focus on how we will create new solutions later on in the class because we will need to store some parameters for that task. Since a solution only contains a single x value there is only two ways to move, increase the x value or decrease the x value. We are going to represent our x value as a double; the big question is how much should we increase or decrease the x value. To make the class more flexible, we will allow the user to specify this amount. We will refer to this amount as the step size. The value of step size will be supplied to the constructor. Also we will account for only searching in a limited range of values. The search range will be defined by two doubles a minDomain and a maxDomain.
private IHillClimbSolution initialGuess;
private IOneVariableFunction function;
private double minDomain;
private double maxDomain;
private double stepSize;
public MinimizeOneVar(IHillClimbSolution initialGuess, IOneVariableFunction function, double minDomain, double maxDomain, double stepSize) {
this.initialGuess = initialGuess;
this.function = function;
this.minDomain = minDomain;
this.maxDomain = maxDomain;
this.stepSize = stepSize;
}To get the best solution out of the list we will find the one with the smallest score since we are minimizing.
Here is the code using a stream:
@Override
public IHillClimbSolution getBestSolution(List<IHillClimbSolution> possibleSolns) {
return possibleSolns.stream()
.min(Comparator.comparing(IHillClimbSolution::getScore))
.get();
}Next, we must be able to determine if we have found a peak/valley or a plateau in order to terminate the hill climb or trigger a random restart. Since we are minimizing a valley or plateau occurs if the current solution is less than or equal to the best new solution.
@Override
public boolean atPeakOrPlateau(IHillClimbSolution currentSolution, IHillClimbSolution newSolution) {
return newSolution.getScore() >= currentSolution.getScore();
}We need a method that compares two solutions and determines if the first is greater than the second. Since we are minimizing the first param is better than the second if it has a smaller score.
@Override
public boolean firstSolutionBetterThanOther(IHillClimbSolution current, IHillClimbSolution best) {
return current.getScore() < best.getScore();
}We need to be able to score a solution. Score for this problem is just the value of the function after plugging in a solution's x value. We just use the lambda to get the value.
@Override
public double scoreSolution(IHillClimbSolution solution) {
return this.function.getFuncValue(((OneVarSolution) solution).getXValue());
}Finally, we will implement the generateNextSolutions() method. We are going to generate a new OneVarSolution for each direction. So create one for xValue-stepSize and one for xValue+stepSize. Also if a solution is generated that goes past the search range we will not add it to the list of new solutions
@Override
public List<IHillClimbSolution> generateNextSolutions(IHillClimbSolution solution) {
OneVarSolution solutionAsOneVar = (OneVarSolution) solution;
List<IHillClimbSolution> list = new ArrayList<>();
double largerValue = solutionAsOneVar.getXValue() + this.stepSize;
if(largerValue <= this.maxDomain)
list.add(new OneVarSolution(largerValue));
double smallerValue = solutionAsOneVar.getXValue() - this.stepSize;
if(smallerValue >= this.minDomain)
list.add(new OneVarSolution(smallerValue));
return list;
}Since our solution class is really simple, we just need to create a random number and use it to create a OneVarSolution. To make the generator consistent with the search range and step size, we will generate numbers that are in units of the step size and fit within the search range. This class must implement IHillClimbSolnGenerator.
Here is the entire class:
public class OneVarSolnGenerator implements IHillClimbSolnGenerator {
private double minDomain;
private double maxDomain;
private double stepSize;
private Random random;
private int numberOfStepsInSearchRange;
public OneVarSolnGenerator(double minDomain, double maxDomain, double stepSize, Random random) {
this.minDomain = minDomain;
this.maxDomain = maxDomain;
this.stepSize = stepSize;
this.random = random;
this.numberOfStepsInSearchRange = (int) Math.floor((maxDomain-minDomain)/stepSize);
}
@Override
public IHillClimbSolution randomSolution() {
double randomValue = this.minDomain + this.stepSize * this.random.nextInt(numberOfStepsInSearchRange+1);
return new OneVarSolution(randomValue, minDomain, maxDomain, stepSize);
}
}Here are two examples, one using normal hill climb and the other hill climb with random restarts
Here is an example of using normal hill climb for the function f(x)=x^2:
HillClimbParams params = new HillClimbParams();
params.setMaxIterations(10000);
IHillClimbSolution initialState = new OneVarSolution(-8.0, -10, 10, 1);
IHillClimbProblem problem = new MinimizeOneVar(initialState, (x) -> Math.pow(x, 2));
HillClimb climber = new HillClimb(problem, params);
IHillClimbSolution optimal = climber.optimize();Here is an example of using hill climb with random restarts for the function f(x)=4x^6-5x^2+x-1:
HillClimbParams params = new HillClimbParams();
params.setMaxIterations(1000000);
IOneVariableFunction function = (x) -> 4*Math.pow(x, 6) - 5*Math.pow(x, 2) + x - 1;
IHillClimbSolution initialState = new OneVarSolution(2, -2, 2, .01);
IHillClimbSolnGenerator generator = new OneVarSolnGenerator(-2, 2, .01, new Random());
IHillClimbProblem problem = new MinimizeOneVar(initialState, function);
HillClimbRandRestart climber = new HillClimbRandRestart(problem, params, generator);
IHillClimbSolution optimal = climber.optimize();Here are links to gists of the files created in this write up:
If you have any questions feel free to contact me!