When it comes to optimization, there’s a class of algorithms called Hill Climbing. Wikipedia can tell you much about the details, but I find that information is often lost in details, so I’m going to try to spell it out in more straightforward terms, with easy examples, a real example and with luck we’ll also come upon a generic solution that can be re-used afterward.

So you have a problem that requires you to optimize (or minimize) something. To apply Hill Climbing, you need to know what a solution looks like, how to generate one, how to figure out how good it is, and how to find its neighbors. That can be a pretty tall order. Using more concise terms, respectively, you need a solution encoding, a solution generator, a fitness function and a neighbor function.

So let’s get started

Before designing a solution to a problem, we need a problem. We’ll use the “ones problem”:

Given a string of 1s and 0s, maximize the number of ones in the string.

In order to solve this problem, we need to be able to get a seed value. It suits us to randomly generate a string of 1s and 0s.

public static BitArray RandomBitArray(int length) { BitArray b = new BitArray(length, false); for (int i = 0; i < length; i++) b[i] = Convert.ToBoolean(ThreadLocalRandom.Next(0, 2)); return b; }

Note here the use of the ThreadLocalRandom, a handy class originally written by Jon Skeet.

After this, we need to be able to know what a solution’s neighbors are. This is not always easy because it’s not always obvious what constitutes a neighbor. In our problem, a neighbor is any string that differs by 1 bit. So, given a BitArray, all of its neighbors can be found by flipping each bit.

public static IEnumerable<BitArray> Neighbours(BitArray barray) { for (int i = 0; i < barray.Length; i++) { var n = new BitArray(barray); n[i] = !n[i]; yield return n; } }

At this point, we only have 1 component left. We need a way to find out how good a solution is. That is, we need a way to score a solution. This is a pretty common task and some, or most, algorithms call this a fitness function. It’s helpful to generate some random solutions in your problem domain, and compare them yourself to figure out what a good scoring function would be. In our cause, we can just take a count of the 1s in our BitArray like so:

public static int Fitness(BitArray barray) { return barray.ToEnumerable().Count(b => b); } public static IEnumerable<bool> ToEnumerable(this BitArray barray) { for (int i = 0; i < barray.Length; i++) yield return barray[i]; }

That makes every piece of the puzzle, except the algorithm itself! I’ve described it already, so I present the algorithm below pulled together into a single object:

public class HillClimber<T, C> { public Func<T> RandomSolution { get; set; } public Func<T, IEnumerable<T>> Neighbours { get; set; } public Func<T, C> Fitness { get; set; } public HillClimber(Func<T> randomSolution, Func<T, IEnumerable<T>> neighbours, Func<T, C> fitness) { this.RandomSolution = randomSolution; this.Neighbours = neighbours; this.Fitness = fitness; } public async Task<T> Optimize(TimeSpan timeout) { DateTimeOffset start = DateTimeOffset.Now; T current = this.RandomSolution(); return await Task.Factory.StartNew(() => { do { var firstGoodNeighbour = this.Neighbours(current) .SkipWhile(n => Comparer<C>.Default.Compare(this.Fitness(n), this.Fitness(current)) < 0) .FirstOrDefault(); if (firstGoodNeighbour != null) current = firstGoodNeighbour; } while (DateTimeOffset.Now - start < timeout); return current; }); } }

The class has 2 generic types:

- T, the encoding which represents a solution (BitArray, in this case)
- C, the type that represents a solution’s fitness score (int, in this case)

The constructor takes our 3 functions:

- A random solution generator
- A neighbor function
- A fitness function

The Optimize function uses RandomSolution to generate a random seed, it then goes through the current solution’s neighbors and uses the fitness function to find the first neighbor that has the same or better fitness.^{1} If such a solution is found, the current solution is updated to be the neighbor, and we repeat until a timeout has been reached.

For kicks, I’ve also made it asynchronous. Finding the solution to our original problem is fairly straightforward:

var search = new HillClimber<BitArray, int>(() => RandomBitArray(10), Neighbours, Fitness); var optimized = await search.Optimize(TimeSpan.FromSeconds(1));

The optimized value return is 1111111111, as is expected.

That’s all for today; coming soon I’ll go over…

- F# implementation of hill climbing
- Variations on the basic hill climbing algorithm
- Real world example(s)

1 The reason for accepting neighbours that are just as fit is so that the hill climbing algorithm can traverse plateaus.