Bumblebee: a C# example

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#.

The goal of the algorithm is to search for the shortest path connecting every city in a list; a City is defined as a simple struct, which has a name and 2 coordinates:

using System.Diagnostics;

[DebuggerDisplay("{Name}")]
public struct City
{
    private readonly string name;
    private readonly double x;
    private readonly double y;

    public City(string name, double x, double y)
    {
        this.name = name;
        this.x = x;
        this.y = y;
    }

    public string Name
    {
        get { return this.name; }
    }

    public double X
    {
        get { return this.x; }
    }

    public double Y
    {
        get { return this.y; }
    }
}

The core of the search algorithm is in the Tsp class, which defines 3 core methods, and an auxiliary method:

using System;
using System.Collections.Generic;
using System.Linq;

public class Tsp
{
    public static IList<City> Shuffle(Random rng, IList<City> cities)
    {
        var shuffled = new List<City>(cities);
        for (var i = cities.Count() - 1; i >= 1; i--)
        {
            var j = rng.Next(i + 1);
            var temp = shuffled[i];
            shuffled[i] = shuffled[j];
            shuffled[j] = temp;
        }

        return shuffled;
    }

    public static IList<City> Swap(Random rng, IList<City> cities)
    {
        var count = cities.Count();
        var first = rng.Next(count);
        var second = rng.Next(count);

        var swapped = new List<City>(cities);
        var temp = swapped[first];
        swapped[first] = swapped[second];
        swapped[second] = temp;

        return swapped;
    }

    public static double Length(IList<City> cities)
    {
        var length = 0d;
        for (var i = 0; i < cities.Count() - 1; i++)
        {
            length = length + Distance(cities[i], cities[i + 1]);
        }

        length = length + Distance(cities[cities.Count() - 1], cities[0]);
        return length;
    }

    public static double Distance(City city1, City city2)
    {
        return Math.Sqrt(
        Math.Pow((city1.X - city2.X), 2d) +
        Math.Pow((city1.Y - city2.Y), 2d));
    }
}

The Shuffle method returns a random shuffle of a list of Cities, Swap simply permutes 2 cities in the itinerary, and Length computes the total length of the circuit, using the Distance method, which computes the Euclidean distance between two cities.

The actual resolution is happening in the RouteViewModel. The StartSearch method passes the 3 methods to the Bumblebee solver, with a list of Cities, and begins the search:

private void StartSearch(IList<City> cities)
{
    var generator = new Func<Random, IList<City>>(
        (random) => Tsp.Shuffle(random, cities));

    var mutator = new Func<Tuple<Random, IList<City>>, IList<City>>(
        (tuple) => Tsp.Swap(tuple.Item1, tuple.Item2));

    var evaluator = new Func<IList<City>, double>(
        (circuit) => -Tsp.Length(circuit));

    var problem = new Problem<IList<City>>(generator, mutator, evaluator);

    this.solver.Search(problem);
    this.IsSearching = true;
}

In the ViewModel constructor, the event solver.FoundSolution is hooked to the SolutionFound handler, which retrieves the list of Cities from the latest solution found, and transforms it to a PointCollection, a collection of Points bound to a Polygon in the WPF main window (this post from Bea Stollnitz was very helpful in the process). Because I am lazy, I used the MVVMLight library to handle the WPF tedium - in this case, I leveraged the DispatcherHelper to update the UI thread with a solution that has been found outside of that thread:

private void SolutionFound(object sender, SolutionMessage<IList<City>> args)
{
    DispatcherHelper.CheckBeginInvokeOnUI(
        () =>
        {
            var points = args.Solution.Select(city => new Point(city.X, city.Y));
            this.Points = new PointCollection(points);
            this.Quality = args.Quality;
            this.DiscoveryTime = args.DateTime;
        });
}

That’s pretty much it, the rest is fairly standard. Below are two more videos; they are probably not going to make any waves on YouTube, but they show the algorithm in action, on a larger problem (500 cities), and on a few small ones. I noticed that the algorithm usually starts well, but gets stumped for sometimes very long periods once it reaches “decent” solutions with multiple good subsequences of cities. I have to play with different Mutate functions, to see if a different neighbor searches improves things, and to look into adding some path-crossing removal functions. On the other hand, I find the results pretty fun for such a small amount of search code!

10 minutes of search on a 500-cities problem

A few 25 cities problems