Recently I’ve been working with some local search techniques and wanted to share my Steepest Ascent Hill Climbing solution.
The general idea of Steepest Ascent Hill Climbing is that in each iteration of the hill climbing process you apply a set of transforms to your input data and select the best result via a fitness function. This result, or the transform which created it, is then the input for your next iteration. The process stops when no transform in an iteration scored higher than the previous generation’s winner.
In this way each iterative step brings you closer to a local maxima of your fitness function’s graph. This is where the term “Hill Climbing” comes from. It is considered a relatively simple AI technique but is also is broadly applicable, quite easy to reason about and can be tweaked for many different corner cases.
For this particular example we will be assuming composable transforms. For each iteration of our hill climbing we will apply our standard transform set to the winning transform of the last round and so produce a new set of transforms.
public delegate S TransformApplier<S, T>(S set, T transform);
public delegate uint FitnessFunction<S>(S set);
public class HillClimberResult<S, T>
{
public HillClimberResult(uint score, T transform, S set)
{
Score = score;
Transform = transform;
Set = set;
}
public uint Score { get; private set; }
public T Transform { get; private set; }
public S Set { get; private set; }
}
public class HillClimber<S, T>
{
public HillClimber(
TransformComposer<T> composer,
TransformApplier<S, T> applier,
FitnessFunction<S> fitness)
{
TransformComposer = composer;
TransformApplier = applier;
FitnessFunction = fitness;
Transforms = new List<T>();
}
public List<T> Transforms { get; private set; }
private TransformComposer<T> TransformComposer { get; set; }
private TransformApplier<S, T> TransformApplier { get; set; }
private FitnessFunction<S> FitnessFunction { get; set; }
public HillClimberResult<S, T> FindMaxima(S inputSet, T initialTransform)
{
if (inputSet == null)
throw new ArgumentNullException("inputSet");
if (initialTransform == null)
throw new ArgumentNullException("initialTransform");
if (Transforms.Count == 0)
throw new ArgumentException("No transforms were set.");
HillClimberResult<S, T> best;
HillClimberResult<S, T> iterBest = ApplyTransformAndScore(inputSet, initialTransform);
do
{
best = iterBest;
foreach (T transform in Transforms)
{
var nextTransform = TransformComposer(best.Transform, transform);
var result = ApplyTransformAndScore(inputSet, nextTransform);
if (iterBest.Score < result.Score)
iterBest = result;
}
} while (iterBest.Score > best.Score);
return best;
}
private HillClimberResult<S, T> ApplyTransformAndScore(S inputSet, T transform)
{
var transformedSet = TransformApplier(inputSet, transform);
var score = FitnessFunction(transformedSet);
return new HillClimberResult<S, T>(score, transform, transformedSet);
}
}
I like the way this worked out in C# quite a lot. However, take a moment to compare it to a F# version I quickly whipped up:
member x.FindMaxima initialSet initialTransform =
let maxOfScores one two = if fst one > fst two then one else two
let findBestTransform set lastTransform =
transforms
|> List.map (fun(transform) -> composer lastTransform transform)
|> List.map (fun(transform) -> applier set transform, transform)
|> List.map (fun(transformedSet, transform) -> (fitness transformedSet), transform)
|> List.reduce maxOfScores
let rec climb set lastScore lastTransform =
let (thisScore, thisTransform) = findBestTransform set lastTransform
if thisScore <= lastScore then (lastScore, lastTransform)
else climb set thisScore thisTransform
climb initialSet (fitness initialSet) initialTransform
It’s quite shocking how much less code is necessary. However, there is a small problem with this example. As we are not using HillClimber from inside of its own library, all of its function inputs resolve to System.Object. The solution is to simply do a bit of annotating to ensure that compile time types are as generic as possible.
type TransformApplier<'s,'t> = 's -> 't -> 's
type FitnessFunction<'s> = 's -> float
type HillClimber<'s,'t>(composer: TransformComposer<'t>, applier: TransformApplier<'s,'t>, fitness: FitnessFunction<'s>, transforms: list<'t>) =
member x.FindMaxima initialSet initialTransform =
let maxOfScores one two = if fst one > fst two then one else two
let findBestTransform set lastTransform =
transforms
|> List.map (fun(transform) -> composer lastTransform transform)
|> List.map (fun(transform) -> applier set transform, transform)
|> List.map (fun(transformedSet, transform) -> (fitness transformedSet), transform)
|> List.reduce maxOfScores
let rec climb set lastScore lastTransform =
let (thisScore, thisTransform) = findBestTransform set lastTransform
if thisScore <= lastScore then (lastScore, lastTransform)
else climb set thisScore thisTransform
climb initialSet (fitness initialSet) initialTransform
Of course, it would be great if the F# type system would reduce to generics instead of System.Object in this case. I would think the ideal would be to always reduce to the most generic type possible. I’ll have to give it a try tonight with the latest VS2010 beta and see if there is any improvement.
Continuing on, let’s give this a go with something simple. We know that the maximum value of |A| – A^2 is 0.5, –0.5. Can we climb our way to one of these values?
open HillClimber
let composer last next = fun x -> (last x) + (next x)
let applier set transform = transform set;
let fitness x = abs( x ) - (x ** 2.0)
let transforms = [fun x -> x + 1.0;
fun x -> x - 1.0;
fun x -> x + 0.1;
fun x -> x - 0.1;
fun x -> x + 0.01;
fun x -> x - 0.01]
let climber = new HillClimber<float,float->float>(composer, applier, fitness, transforms)
let initialValue = 0.0
let (score, transform) = climber.FindMaxima initialValue (fun x -> x)
let result = transform initialValue
…Highlight, Alt-Enter…
val applier : 'a -> ('a -> 'b) -> 'b
val fitness : float -> float
val transforms : (float -> float) list =
[<fun:transforms@10>; <fun:transforms@11-1>; <fun:transforms@12-2>;
<fun:transforms@13-3>; <fun:transforms@14-4>; <fun:transforms@15-5>]
val climber : HillClimber.HillClimber<float,(float -> float)>
val initialValue : float = 0.0
val transform : (float -> float)
val score : float = 0.25
val result : float = -0.5
Looks good!
Well, it looks like that took a bit longer than I had anticipated. I’ll be back with my weekly update tomorrow.
