CodePlexProject Hosting for Open Source Software

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

Last edited Dec 29, 2011 at 4:05 AM by mathiasb, version 3