Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 27. June 2012 15:06

This months’ issue of MSDN Magazine has an interesting piece on evolutionary algorithms. The article applies a genetic algorithm to identify the minimum value of a “pathological” continuous function, the Schwefel function.

SchefelFunction

The Schwefel function

For X and Y values between –500 and 500, the “correct” answer is X and Y = 420.9687.

This function is designed to give fits to optimization algorithms. The issue here is that  the function has numerous peaks and valleys. As a result, if the search strategy is to use some form of gradient approach, that is, from a starting point, follow the steepest descent until a minimum is reached, there is a big risk to end up in a place which is a local minimum: the algorithm gets stuck in a valley with no path downwards, but there are other, better solutions around, which can be reached only by “climbing out of the hole” and temporarily following a path which heads in the wrong direction.

Out of curiosity, I checked how the Excel Solver would fare on this problem:

ExcelSchwefel

The result was an abject failure – not even close to the true solution.

I thought it would be interesting to see how Bumblebee, my Artificial Bee Colony framework, would perform. There are some general similarities between the underlying ideas behind the articles’ algorithm and Bumblebee, the main difference being that Bumblebee simply mutates individual solutions, and doesn’t create “crossover solutions”.

Let’s open Visual Studio, create an F# Console project, grab the NuGet package for Bumblebee – and start coding.

As usual, we need 4 elements to leverage Bumblebee – a Type of Solution, and 3 functions: a Generator, which returns a brand-new, random solution, a Mutator, which transforms a known solution into a new, similar solution, and an Evaluator, which evaluates a solution and returns a float, increasing with the quality of the solution.

In this case, the Solution type is fairly straightforward. We are looking for 2 floats x and y, so we’ll go for a Tuple. Similarly, the Evaluation is a given, it is the negative of the Schwefel function. The reason we go for the negative is that Bumblebee will try to maximize the Evaluation, so if we are looking for a minimum, we need to reverse the sign – because the Minimum of a function is the Maximum of its negative.

let schwefel x = 
   -x * Math.Sin(Math.Sqrt(Math.Abs(x)))

let evaluate (x, y) = 
   - schwefel (x) - schwefel (y)

The Generation function is also trivial – we’ll simply pick random pairs of floats in the [ –500.0; 500.0 ] interval:

let min = -500.0
let max = 500.0

let generate (rng: Random) = (
   rng.NextDouble() * (max - min) + min,
   rng.NextDouble() * (max - min) + min)

The Mutation function takes a tiny bit more of effort. The idea I followed is essentially the same as the one used in the article: given a solution defined by a pair of floats, randomly decide if any of the elements will be mutated, and if yes, add a random permutation to that element, scaled to the precision we want to achieve:

let precision = 0.00001
let rate = 0.5

let mutate (rng: Random) solution =
   let (x, y) = solution
   let x =
      if rng.NextDouble() < rate 
      then x + precision * ((max - min) * rng.NextDouble() + min)
      else x
   let y =
      if rng.NextDouble() < rate 
      then y + precision * ((max - min) * rng.NextDouble() + min)
      else y
   (x, y)

More...

by Mathias 6. June 2012 15:05

I have just pushed version 0.3 of Bumblebee on CodePlex. Bumblebee is an Artificial Bee Colony algorithm implementation in F#. In a nutshell, it’s a randomized search method that mimics the behavior of bees looking for food, and can be suitable to find approximate solutions to large scale problems where deterministic approaches are impractical. Bumblebee provides a C#-friendly Solver, which will search for solutions to a problem, sending messages to the caller whenever an improved solution is found, until the search is stopped. It uses the Task Parallel Library to parallelize the searches as much as possible.

The source code includes two sample projects that illustrate the algorithm in action on the Travelling Salesman Problem, one in F#, one in C#, with a “fancy” WPF user interface.

What’s new in Version 0.3? Mostly code cleanup – when I revisited my original code a few months after the fact, I had a hard time following it, so I reorganized things internally in a way which I hope is clearer. The main change from an API perspective is the constructor for C# problems: I removed the Tuples from the Func delegates, which were mostly noise and didn’t help much.

Other than that, the changes are mostly cosmetic: the main Search loop has been transformed into a recursive immutable loop, code has been shuffled around and renamed for readability, the test suite has been updated and uses the FsUnit NuGet package.

Speaking of NuGet, I published Bumblebee as a NuGet package here. It’s my first NuGet package, so hopefully I haven’t messed up anything there – if you see anything amiss, please let me know!

That’s it for the moment. I am working on some ideas right now, the main one being to use Azure to allow Bumblebee to scale out and attack larger problems – we’ll see how that turns out. I kept Bumblebee as Alpha stage, as I may still change the API in the future.

On a related note, I will be travelling to Boston mid-June, where I will have the pleasure to present Bumblebee at the New England F# user group. I am extremely excited about this opportunity (thanks to Talbott Crowell for the invitation!) - I plan on discussing the algorithm and its implementation, writing F# code live to solve a problem and hopefully show why F# is so fun to work with, and talk in general about my experience learning F# after years of C# development. I am really looking forward to it, and hope to see some of you there!

Comments

Comment RSS