As a little aside in learning Scala I took some time to write a fairly general implementation of the Hill Climbing optimisation algorithm. I thought it would make good topic for a blog entry.
It would take too long to introduce mathematical optimisation and hill climbing methods in this entry so I am going to assume you have a general idea of what they are, besides the topic has been introduced far better than I could do here and here
The basic algorithm we are going to implement is
- current = random state
- do
- Generate Neighbours(current)
- Find best score of neighbours
- if(neighbour score > current score) current = best neighbour
- else exit
- loop
So a pretty easy to understand algorithm really. What I wanted to do was produce a reusable frame work for this technique to solve many different problems, hopefully learning a little bit of Scala along the way.
We define a simple interface from which we can create concrete classes that allow us to forumalate the optimisation problems we want to solve. Based on the pseudo code above we can define the HillClimbInterface trait as follows
trait HillClimbInterface[T] {
type State = T
def neighbours(state:T, rand:Random):List[T];
def randomState(rand:Random):T;
def eval(state:T):Double;
}
The first line creates a state type, we shall see later this could be as simple as a Double or something more complex. The three functions are then fairly obvious, neighbours will generate the neighbours of the current state, randomState will generate a random state to initialise the whole process and finally eval with return a score for the state, the higher the better.
Before we actually get onto the Hill Climbing implementation lets take a look at a very simple HillClimbInterface concrete class We are going to create a class that uses the Hill Climbing algorithm to find the maximum value of a sin wave. The answer is ofcourse 1, knowing the answer helps us to check we have our Hill Climbing algorithm correct.
class SinWave() extends HillClimbInterface[Double] {
val delta = 0.00001
override def neighbours(state:State, rand:Random) = List( if(state>=delta) state-delta else state,
if(state<=2*Math.Pi - delta) state+delta else state
);
override def randomState(rand:Random) = rand.nextFloat;
override def eval(state:State):Double = Math.sin(state)
}
Our state type is a Double, the position at which we want to evaluate the sin function. To work out the score we just take the sin of the state as shown in out eval function. The random state if just some random value between 0.0 and 1.0 and the neighbours is a list of two values one slightly larger than the current state and one slightly less. We clamp the values between 0 and 2 Pi for no particular reason other than I want to work in that range and demonstrate how to apply simple contraints.
The class SinWave is effectively a controller for the hill climbing algorithm, I use this term below when defining the Hill climbing algorithm. Here is the class.
class HillClimb[T]{
val rand = new Random()
def optimise(controller:HillClimbInterface[T]) ={
climb(controller)
}
private def climb(controller:HillClimbInterface[T]) = {
def climbImp(controller:HillClimbInterface[T], best:T, atMax:Boolean):T = {
atMax match {
case true => best
case false => {
var atMax = true
var newBest = best
val newStates = controller.neighbours(newBest, rand)
var bestScore = controller.eval(newBest)
for(state <- newStates) {
val newScore = controller.eval(state)
if(newScore > bestScore){
atMax = false
bestScore = newScore
newBest = state
}
}
climbImp(controller, newBest, atMax)
}
}
}
climbImp(controller, controller.randomState(rand), false)
}
}
Class HillClimb is parametised by the state type. In the case of sin wave this is a Double. The public functions are quite simply the function optimise which does what it says on the tin. The private function climb is where the action is, well actually the local function in that does all the work. I could have written this using a more procedural way which would be closer to algorithm we specified at the top but as I am trying to learn more functional way of thinking I decided to use tail recussion. I am of course open to suggestions on how to improve this code.
As the algorithm closely follows the pseudo algorithm above I won’t bother to discuss it here, just think recussively and all is well!
To use this class with our SinWave controller we could write this
val sinWave = new SinWave()
val hillClimb = new HillClimb[sinWave.State]
println(hillClimb.optimise(sinWave))
Pretty simple I hope you would agree. I am not totally happy with the sinWave.State part when creating the hillClimb value but struggled to figure out a better way to do this.
The ShotGun Method.
One problem with Hill Climbing is it can get stuck at local maximums. More complicated optimisation algorithms exist to get around this although a very simple approach to try to mitigate this is to run the Hill climbing algorithm many times with random initial states. This is often call the Shot Gun method for obvious reasons. It is pretty easy to create a function in HillClimb that implements this.
def shotgunMethod(controller:HillClimbInterface[T], numIters:Int) = {
def shotgunImp(controller:HillClimbInterface[T], iter:Int, best:T) : T = {
iter match {
case 0 => best
case _ => {
val latest = climb(controller)
val newBest = if(controller.eval(latest)> controller.eval(best)) latest else best
shotgunImp(controller, iter-1, newBest)
}
}
}
shotgunImp(controller, numIters, controller.randomState(rand))
}
We can specify the number of iterations. Again it uses tail recurrsion rather than procedual loops. Basically we keep calling the climb function and storing the best result so far until the value iter is zero at which point we return the best result so far. To use the Shot Gun approach we would use this code.
val sinWave = new SinWave()
val hillClimb = new HillClimb[sinWave.State]
println(hillClimb.optimise(sinWave))
println("With shotgun" + hillClimb.shotgunMethod(sinWave, 10))
The KnapSack Problem.
So far we have not really stressed tested framework. Finding the largest value of a sin wave does not exactly contain many local minima so lets try a more difficult problem. Packing items into a rucksack to maximise the value of the items while being constrained by the cost of the items. This problem is taken from here a genetic algorithm library written in Scala. Here is the code to implement it using our hill climbing algorithm. To get the max value you need to use the shotgun method.
// Max Cost: 17
// Best Value is 24 the last two added together 11.0 + 13.0
// see http://code.google.com/p/jiva-ng/wiki/KnapsackProblem
class KnapSack extends HillClimbInterface[Array[Boolean]] {
val costToValues= Map(3.0->4.0, 4.0->5.0, 7.0->10.0, 8.0->11.0, 9.0->13.0)
val costs = Array(3.0, 3.0, 3.0, 3.0, 3.0, 4.0, 4.0, 4.0, 7.0, 7.0, 8.0, 8.0, 9.0)
def stateCost(state:State):Double = {
val setStates = costs.zipWithIndex.filter(x=> state(x._2)==true)
val currentCosts = setStates.map(x =>(costs(x._2)))
currentCosts.foldLeft(0.0)(_+_)
}
override def neighbours(state:State, rand:Random) = {
val maxNeighbours = 5
var neighbours = List[State]()
for(i <- 0 to maxNeighbours) {
var arr = state.toArray
arr(rand.nextInt(arr.length)) = true
while(stateCost(arr) > 17) {
arr(rand.nextInt(arr.length)) = false
}
neighbours = arr::neighbours
}
neighbours
}
override def randomState(rand:Random) = {
var s = new State(13)
for(i <- 0 until 10){
s(i) = rand.nextBoolean
}
// this state may not be valid, so generate neighbours that are guarenteed valid
neighbours(s, rand).head
}
override def eval(state:State):Double = {
val setStates = costs.zipWithIndex.filter(x=> state(x._2)==true)
val currentCosts = setStates.map(x =>(costToValues(costs(x._2))))
currentCosts.foldLeft(0.0)(_+_)
}
}
This time our state variable is an array of bools and our randomState function just fills it and array with random boolean values. As this could state may not be valid (have a cost > 17) we generate neighbours from it which are guaranteed to be valid and take the head of it. I make a fair amount of use of the built in processing functions such as map, zip and filter but found the neighbours function just looked better using more procedural idioms. Obviously suggestions are welcome to add clarity.
Here is the code to run it
val knap = new KnapSack
val climber = new HillClimb[knap.State]
val res2 = climber.shotgunMethod(knap, 20)
println(res2.deepToString)
println("Cost is:"+knap.eval(res2));
println("State cost is:" +knap.stateCost(res2))
Using the shotgun method we get the expected value of 24.
Conclusions
I wrote this code about a month ago but have only just got round to posting it and it compile under Scala 2.72RC1. I would certainly change a few things now, like using a List rather than an Array for the State in the KnapSack container and changing the name of HillClimbInterface to HillClimbController. I am not sure if the whole map, filter and zip add to the clarity of the KnapSack implementation, perhaps reworking to use for loops would be better? As always I welcome any comments as I am still learning Scala.
Here is the complete code for the HillClimb class.
import scala.util.Random
trait HillClimbInterface[T] {
type State = T
def neighbours(state:T, rand:Random):List[T];
def randomState(rand:Random):T;
def eval(state:T):Double;
}
// Hill climbing optimasation
class HillClimb[T]{
val rand = new Random()
def optimise(controller:HillClimbInterface[T]) ={
climb(controller)
}
private def climb(controller:HillClimbInterface[T]) = {
def climbImp(controller:HillClimbInterface[T], best:T, atMax:Boolean):T = {
atMax match {
case true => best
case false => {
var atMax = true
var newBest = best
val newStates = controller.neighbours(newBest, rand)
var bestScore = controller.eval(newBest)
for(state <- newStates) {
val newScore = controller.eval(state)
if(newScore > bestScore){
atMax = false
bestScore = newScore
newBest = state
}
}
climbImp(controller, newBest, atMax)
}
}
}
climbImp(controller, controller.randomState(rand), false)
}
// Uses many random initial states to try to avoid
// local minimums.
// numIters specifies the how many random states that will be considered
def shotgunMethod(controller:HillClimbInterface[T], numIters:Int) = {
def shotgunImp(controller:HillClimbInterface[T], iter:Int, best:T) : T = {
iter match {
case 0 => best
case _ => {
//var bestScore = controller.eval(best)
val latest = climb(controller)
val newBest = if(controller.eval(latest)> controller.eval(best)) latest else best
shotgunImp(controller, iter-1, newBest)
}
}
}
shotgunImp(controller, numIters, controller.randomState(rand))
}
}