Hill Climbing

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.