Hill Climbing Variations

Many algorithms have variations for a multitude of reasons and Hill Climbing is no different. Last time I presented the most basic hill climbing algorithm and implementation. There are some known flaws with that algorithm and some known improvements to it as well. Here are 3 of the most common or useful variations.

Steepest Ascent

If you recall, in the basic hill climbing algorithm, you look at the neighbors of a solution and choose the first one that improves on the current solution and climb to it. In Steepest Ascent, the idea is to choose the route that ascends the fastest similar to a best-first search approach. That is, every time you take a step, you take the largest step you can.

In a problem like we had last time, where we flipped a bit in our string, we’ll never have a situation where we would have variable magnitude ascents. To see why, start with the bit string 001. The possible neighbors of 001 are 000, 011 and 101. 000 is less fit, and the remainder are equally as fit. This can be extrapolated and shown to be true in the case of all candidate solutions.

Never-the-less, given our code, it can be modified to perform steepest ascent hill climbing. In order to do so, we need some code that will be able to find a neighbor solution that has the biggest increase in fitness score over the current fitness score. To do that, we’ll modify the Optimize function.

public async Task Optimize(TimeSpan timeout)
{
    DateTimeOffset start = DateTimeOffset.Now;
    T current = this.RandomSolution();
    C currentFitness = this.Fitness(current);

    return await Task.Factory.StartNew(() =>
    {
        do
        {
            T steepestAscentNeighbour = default(T);
            C steepestAscentFitness = default(C);

            foreach (var n in this.Neighbours(current))
            {
                steepestAscentFitness = this.Fitness(n);
                if (Comparer.Default.Compare(steepestAscentFitness, currentFitness) >= 0)
                {
                    current = n;
                    currentFitness = steepestAscentFitness;
                }
            }

            if (steepestAscentNeighbour != null && 
                Comparer.Default.Compare(currentFitness, steepestAscentFitness) >= 0) 
            {
                current = steepestAscentNeighbour;
            }

        } while (DateTimeOffset.Now - start < timeout);

        return current;
    });
}

Stochastic Hill Climbing

There are times where the set of neighbor solutions is too large, or for whatever reason it’s impractical to iterate through them all when evaluating neighbor solutions. The stochastic variation attempts to solve this problem, by randomly selecting neighbor solutions instead of iterating through all of them.

To use our example from last time, we need a different Neighbour method that will generate random neighbors.

public static IEnumerable RandomNeighbours(BitArray barray)
{
    do
    {
        var n = new BitArray(barray);
        var i = ThreadLocalRandom.Next(0, barray.Length);

        n[i] = !n[i];

        yield return n;
    }
    while (true);
}

… except that this is clearly an infinitely generating sequence that will also, likely, generate duplicates. I was tempted to write a small shuffler, but an entire blog series could be written about those (seriously, go check it out).

It’s a matter of personal taste that I like generating infinite sequences. In this case, the caller decides to cap the number of neighbors generated to 10 when instantiating the hill climber.

var search = new HillClimber<BitArray, int>(
    () => RandomBitArray(10),
    (b) => RandomNeighbours(b).Take(10),
    Fitness);

Random Restart

If you recall the metaphor from last time, this is basically the scenario where you start climbing a hill, reach the top, but it’s not the tallest hill in the solution landscape. That is to say: normal hill climbing suffers from being only a local optimization algorithm. To solve this scenario, a surprisingly simple solution is found: start again somewhere else.

The idea is simple, each time you reach a peak, or wander on a plateau for a long time, then compare the fitness score at the current location with the current (global) best and store it if it’s better. Then restart from a new random location. After a predetermined number of iterations, or time, you’ve finished.

Our problem from last time doesn’t have any local maxima (visually, it should look like something along the lines of a stepped cone), so Random Restart doesn’t do us a whole lot of good. That’s the upside of us writing a generic algorithm, so that we can still implement the algorithm, even when we don’t necessarily have a problem to solve at the present time.

The first thing we need, is to figure out when we’ve reached a peak. That’s fairly simple, we’ll keep a count of how many times we didn’t find a good neighbor. After that is a whole lot of book keeping. I’m not terribly happy with the following code, but it does do what we need it to do.

public async Task Optimize(TimeSpan timeout)
{
    DateTimeOffset start = DateTimeOffset.Now;

    T current = this.RandomSolution();
    C currentFitness = this.Fitness(current);
    T globalBest = current;
    C globalBestFitness = currentFitness;

    int iterationsAtLevel = 0;

    return await Task.Factory.StartNew(() =>
    {
        do
        {
            var firstGoodNeighbour =
                this.Neighbours(current)
                    .SkipWhile(n => Comparer.Default.Compare(this.Fitness(n), currentFitness) < 0)
                    .FirstOrDefault();

            if (firstGoodNeighbour != null)
            {
                if (Comparer.Default.Compare(currentFitness, this.Fitness(firstGoodNeighbour)) < 0)
                {                     
                    iterationsAtLevel = 0;
                }
                else
                {
                    iterationsAtLevel++;
                }

                current = firstGoodNeighbour;
                currentFitness = this.Fitness(firstGoodNeighbour);
            }
            else
            {
                iterationsAtLevel++;
            }
            if (iterationsAtLevel > this.PeakThreshold)
            {
                if (Comparer.Default.Compare(currentFitness, globalBestFitness) < 0)
                {
                    globalBest = current;
                    globalBestFitness = currentFitness;
                }

                current = this.RandomSolution();
                currentFitness = this.Fitness(current);
                iterationsAtLevel = 0;
            }
        } while (DateTimeOffset.Now - start < timeout);

        return current;
    });
}

As you can see, that’s a fair bit more verbose than before. I may have to revisit it in the future and clean it up a bit. What’s being done here is that we need to store the best global solution (and its fitness, to avoid some excessive re-calculation) as well as the current solution. Then, when we finally find a suitable neighbor we have to check to see if it’s better than our global best. If it is, we update the global best.

Side note: we discussed it last time, but it’s important to discuss again;in order to be able to traverse plateaus in the solution landscape, we need to accept neighbor solutions that are as fit as the current solution. In Random Restart, though, being as fit isn’t enough to reset the clock on how long we’ve been roaming on a peak.

No matter what, we have to check to see if we’ve been on a peak for too long. How long? We check the PeakThreshold.

We’re obviously not done there. The Random Restart variation is a particularly invasive graft on the Hill Climbing algorithm. We need to update our constructor(s) to take a value for PeakThreshold.

public int PeakThreshold { get; set; }

public HillClimber(Func randomSolution, Func<T, IEnumerable> neighbours, Func<T, C> fitness)
    : this(randomSolution, neighbours, fitness, 5)
{
}

public HillClimber(Func randomSolution, Func<T, IEnumerable> neighbours, Func<T, C> fitness, int peakThreshold)
{
    this.RandomSolution = randomSolution;
    this.Neighbours = neighbours;
    this.Fitness = fitness;
    this.PeakThreshold = peakThreshold;
}

And we’re basically done. Updating the call to create the HillClimber to include a value for the PeakThreshold (will vary greatly depending on the characteristics of the solution landscape) and we’ve finished.

Conclusion

Outside of the changes listed here, for each variation, the rest of the algorithm is the same. If there’s interest or anyone is having particular difficulty, I’ll create a github repository to provide the source or something along those lines (I’m using a private Team Foundation Service at the moment).

I had promised some more examples and the equivalent F# implementations. I’d still like to do that, because it’s difficult to see the benefits at runtime using the original example provided, but it’ll have to be in a future post. There’s some other algorithms that I’m itching to touch on before that.

To wrap up, what have we looked at? Three variations to the original Hill Climbing algorithm.

  • Steepest Ascent: always take the biggest step up
  • Stochastic: Choose random neighbors, and pick the first good one
  • Random Restart: when you reach the top, start over somewhere else

Bonus points for the eager: Random Restart can be combined with both of the two variations…