Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 26. December 2011 11:04

Last week I posted some screen captures of Bumblebee in action on the Traveling Salesman Problem. One thing was bugging me, though – the algorithm didn’t seem to handle crossings very well. I ended up adding a de-crossing routing, which ended up speeding up the process quite a bit. The full C# demo, illustrating how to use Bumblebee from C#, has been pushed as version 0.2 to CodePlex.

Below is an illustration of the algorithm in action, in a nice seasonal color scheme. Santa needs to travel through 200 random cities: starting from a terrible initial route, the algorithm progressively disentangles them and ends up with a pretty good-looking solution under 2 minutes, significantly reducing the carbon footprint of those reindeers:

TSP with 200 cities running for 2 minutes

So what was the issue with line crossings? Consider the following route, in perfect order:

image

Now imagine that while searching, the algorithm discovers the following path:

image

More...

by Mathias 18. December 2011 14:59

I spent some time this week putting together an example illustrating how to use Bumblebee from C# code. I figured it would be more exciting to have a graphical representation of the bee colony working on the traveling salesman problem, so I put together a small WPF application which creates a random set of cities, and displays the improvements live as they are found by the algorithm.

Here is a screen capture of the first 10 seconds of a 100-cities problem:

Bumblebee working on 100 cities

The source code for the example is available in the current head revision, under the TspDemo.CSharp project; I’ll push an “official” downloadable version as soon as I have time for some cleanup. Note that, besides a reference to Bumblebee, a reference to FSharp.Core 4.0 is required – the rest is all pure C#.

More...

by Mathias 11. December 2011 11:06

Yesterday, I made the first version of Bumblee public on Codeplex. Version 0.1 is an Alpha release, meaning that it’s usable, but still rough around the edges.

What is Bumblebee? It is an Artificial Bee Colony (ABC) algorithm, a randomized search method which mimics the behavior of bee hives. Given a search problem, the algorithm will dispatch Scout bees to look for new solutions, and Active bees to explore around known solutions. Once their search is complete, bees return to the Hive and share information with Inactive bees, and new searches are allocated based on the information available so far.

I have multiple goals with Bumblebee. I came across the algorithm for the first time in this article, which illustrates it on the Traveling Salesman Problem with a C# implementation. I enjoyed the article, but wondered if I could

  • parallelize the algorithm to use multiple cores,
  • provide a general API to run arbitrary problems.

… and I figured it would be a good sample project to sharpen my F# skills.

For the parallelization part, I decided to use the Task Parallel Library: the Hive creates Tasks for each bee beginning a search, which returns to a Queue to be processed and share the search result with the inactive bees in the Hive (see outline here).

Deciding on a design for the API took some back and forth, and will likely evolve in the next release. The API should:

  • accommodate any problem that can be solved by that approach,
  • be reasonably simple to use by default,
  • limit parallelization problems, in particular around random numbers generation,
  • be palatable for F# and C# users.

Regarding the first point, 3 things are needed to solve a problem using ABC: Scouts need to know how to find new random solutions, Active bees need to be able to find a random neighbor of a solution, and solutions need to be comparable. I figured this could be expressed via 3 functions, held together in a Problem class:

  • a generator, which given a RNG returns a new random solution,
  • a mutator, which given a RNG + solution tuple, returns a random neighbor of the solution,
  • an evaluator, which given a solution returns a float, measuring the quality of the solution.

You can see the algorithm in action in the TspDemo console application included in the source code.

I opted to have the Random Number Generator as an argument because the algorithm is responsible for spawning Tasks, and is therefore in a good position to provide a RNG that is safe to use, relieving the client of the responsibility of creating RNGs. I’ll probably rework this a bit, though, because I don’t like the direct dependency on Random; it is not very safe, and I would like to provide the ability to use whatever RNG users may happen to prefer.

The reason I chose to have the evaluator return a float (instead of using IComparable) is because I figured it might be interesting to have a measure which allowed the computation of rates of improvements in solution quality.

As for simplicity, I ended up with a main class Solver with 2 main methods. Search(Problem) initiates a search as a Task, and goes on forever until Stop( ) is called. The Solver exposes an event, FoundSolution, which fires every time an improvement is found, and returns a SolutionMessage, containing the solution, its quality, and the time of discovery. It is the responsibility of the user to decide when to stop the search, based on the information returned via the events.

By default, the Solver is configured with “reasonable” parameters, but if needed, they are exposed via properties, which can be modified before the search is initiated.

No effort has gone for the first release to make this C# friendly – this, and abstracting the RNG, are the goals of the next release.

I would love to get feedback, both on the overall design and the code itself! You can download the project from here.

by Mathias 4. December 2011 15:47

I am in the middle of “Working Effectively with Legacy Code”, and found it every bit as great as it was said to be. In the book, Feathers introduces the concept of Seams and Enabling Points:

a Seam is a place where you can alter behavior in your program without editing it in that place

every seam has an enabling point, a place where you can make the decision to use one behavior or another.

The idea - as I understand it - is that an enabling point is a hook for testability, a place where you can replace the behavior of a piece of code with your own controlled behavior, and validate that the results are as expected.

The reason I am bringing this up is that I have been writing lots of F# lately, and it made me realize that a functional style provides lots of enabling points, and can be much easier to test than object-oriented code.

Here is a simplified, but representative, example of the problem I was looking at: I needed to pick a random item in a list. In C#, a method along these lines would do the job:

public T PickFrom(IList<T> list)
{
   var random = new Random();
   return list[random.Next(list.Count())];
}

However, this code is utterly untestable; it’s also probably a terrible idea to instantiate a new Random every time this is called, so we modify it this way:

public T PickFrom(IList<T> list, Random random)
{
   return list[random.Next(list.Count())];
}

This is much better: now we have a decent Enabling Point, because the list of arguments of the method contains everything that is used inside the method. However, this is still untestable, but for a different reason: by definition, Random.Next() will return different values every time PickFrom is called, and expecting a repeatable result from PickFrom is a bit of a desperate enterprise.

More...

Comments

Comment RSS