BumblebeeSort in F#

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

open ClearLines.Bumblebee
open System

let Main = 

We’ll start with a random list of integers:

   let rng = new Random()
   let root = 
      [ for i in 0 .. 100 do yield 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.

   let generate = fun (rng: Random) -> root

   let mutate = fun (rng: Random, solution: int list) -> 
      let count = List.length solution
      let first = rng.Next(0, count)
      let second = rng.Next(0, count)
      if first = second then solution else
         List.permute (fun (i) -> 
            if i = first then second 
            elif i = second then first 
            else i) solution

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.

   let evaluate = fun (solution: int list) -> 
      let value (list: int list) =
         match list with
         | [] -> 0
         | _ -> List.sumBy (fun elem -> (if elem >= List.head list then 0 else -1)) (List.tail list)
      let rec listValue (list: int list) acc =
         match list with
         | [] -> acc
         | _ -> listValue (List.tail list) acc + value list
      listValue solution 0 |> (float)

We can now create a Problem and instantiate the Solver:

   let problem = new Problem<int list>(generate, mutate, evaluate)
   let solver = new Solver<int list>()

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:

   let displaySolution (solution: int list) = 
      List.iter (fun (i) -> Console.Write(i.ToString() + " ")) solution

   let foundSomething = fun (msg: SolutionMessage<int list>) -> 
      Console.WriteLine("New solution of quality {0} found at {1}", msg.Quality, msg.DateTime.TimeOfDay) 
      displaySolution(msg.Solution)
      Console.WriteLine()

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

   solver.FoundSolution.Add foundSomething
         
   solver.Search(problem) |> ignore

   Console.ReadLine() |> ignore

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:05 AM by mathiasb, version 3

Comments

No comments yet.