BumblebeeSort in C#

Our goal is to sort a list of integers in increasing order, using Bumblebee. First, let's create a Console application in C#, add a reference to the Bumblebee dll and FSharp.Core 4.0, and create our Main method.

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

namespace BumbleBeeSort.CSharp
{
   using ClearLines.Bumblebee;
   using Microsoft.FSharp.Control;
   using Random = System.Random;

   class Program
   {
      static void Main(string[] args)
      {

We’ll start with a random list of integers:

         var rng = new Random();
         var root = new List<int>();
         for (var i = 0; i < 100; i++)
         {
            root.Add(rng.Next(0, 100));
         }

The type of solution we expect is a list of integers, therefore the problem will be a Problem<int list>.

We need to define the Problem in a way that can be handled by Bumblebee. Bumblebee requires 3 functions to operate: a function to generate new solutions, a function to mutate an existing list, and a function to evaluate the quality of a solution.
Our approach will be to simply permute random elements in the list, without worrying about generating new solutions. In other words, we will just use Active bees to explore starting from the initial root solution, without Scouting for new solutions.

         var generate = new Func<Random, List<int>>(
            (random) => root);

         var mutate = new Func<Tuple<Random, List<int>>, List<int>>
            (tuple =>
                {
                   var random = tuple.Item1;
                   var list = tuple.Item2;
                   var count = list.Count();
                   var first = random.Next(0, count);
                   var second = random.Next(0, count);

                   if (first == second)
                   {
                      return list;
                   }

                   var copy = new List<int>(list);
                   var firstElement = copy[first];
                   var secondElement = copy[second];
                   copy[second] = firstElement;
                   copy[first] = secondElement;

                   return copy;
                });

The third element we need is an evaluation function, which will measure the quality of a list. In order to do this, for each element in the list, we will count how many items after that element are smaller (i.e. incorrectly sorted), and add a penalty of -1 for each.

         var evaluate = new Func<List<int>, double>
            (list =>
                {
                   var count = list.Count();
                   var value = 0;
                   for (var i = 0; i < count; i++)
                   {
                      var head = list[i];
                      var subList = list.GetRange(i + 1, count - 1 - i);
                      value -= subList.Count(it => it < head);
                   }

                   return (double)value;
                });

We can now create a Problem and instantiate the Solver:

         var problem = new Problem<List<int>>(generate, mutate, evaluate);
         var solver = new Solver<List<int>>();

Finally, we need to subscribe to the FoundSolution event that is fired by the Solver every time an improvement is found. We will write to the Console the current list of integers, as well as the time the solution was found and its quality:

         var displaySolution = new Action<SolutionMessage<List<int>>>(
            (message) =>
            {
               foreach (var i in message.Solution)
               {
                  Console.Write(i.ToString() + " ");
               }

               Console.WriteLine();
            });

         var foundSomething = new FSharpHandler<SolutionMessage<List<int>>>(
            (sender, message) =>
            {
               Console.WriteLine("New solution of quality {0} found at {1}",
                  message.Quality,
                  message.DateTime.TimeOfDay);
               displaySolution(message);
            });

We can now subscribe to the event, and launch the search.

         solver.FoundSolution += foundSomething;

         solver.Search(problem);

         Console.ReadLine();

BumbleBeeSort is now ready to run: the Console will show the initial list of random numbers, being sorted as improved solutions are found by the bees. The solver will keep on running, until Enter is pressed.

Last edited Dec 29, 2011 at 4:10 AM by mathiasb, version 1

Comments

No comments yet.