This project is read-only.
Project Description
Bumblebee is an Artificial Bee Colony (ABC) algorithm developed in F#. The algorithm is a randomized search method that mimics the behavior of bee hives: it dispatches "bees" to search for new solutions or explore the neighborhood of known solutions, and allocates new searches based on the quality of the results returned so far.

The Solver will search for a solution to a problem, defined by 3 functions:
• a generator which returns new solutions,
• a mutator which returns solutions close to an existing solution,
• an evaluator, which evaluates the quality of a solution as a float.

The solver dispatches bees to search in parallel (Scout Bees for new solutions, Active Bees for improvements around a known solution), and fires events every time an improved solution is found, until the search is stopped.

The algorithm in action: Traveling Salesman Problem

The project includes a C# WPF application, which shows the algorithm working in real-time trying to find the shortest route between a list of randomly generated cities. The video below shows the bee busy on a 200-cities route:

Illustration: Traveling Salesman Problem

The objective is to find the shortest closed path connecting a list of cities. Starting with an array of Cities, we will generate new solutions by shuffling the initial list, and mutate solutions by either swapping a random pair of cities, or trying to remove crossings in the current solution. The Quality of a solution will be the negative of the distance, so that shorter distances have a higher quality than longer ones.

```open System
open System.Diagnostics
open ClearLines.Bumblebee

[<DebuggerDisplay("{Name}")>]
type City = { Name: string; X: float; Y: float }

let Main =

// Euclidean distance between cities
let distance (C1, C2) =
(  (C1.X - C2.X) ** 2.0 +
(C1.Y - C2.Y) ** 2.0) ** 0.5

// Permutation function:
// swaps items at first and second index
let swap (first: int, second) index =
if index = first then second
elif index = second then first
else index

// Swap 2 random elements in an Array
let randomSwap (rng: Random) items =
let last = Array.length items
let first = rng.Next(last)
let second = rng.Next(last)
Array.permute (fun i -> swap (first, second) i) items

// Fisher-Yates shuffle
let shuffle (rng: Random) items =
let rec shuffleTo (indexes: int[]) upTo =
match upTo with
| 0 -> indexes
| _ ->
let fst = rng.Next(upTo)
let temp = indexes.[fst]
indexes.[fst] <- indexes.[upTo]
indexes.[upTo] <- temp
shuffleTo indexes (upTo - 1)
let length = Array.length items
let indexes = [| 0 .. length - 1 |]
let shuffled = shuffleTo indexes (length - 1)
Array.permute (fun i -> shuffled.[i]) items

// Compute the total distance,
// summing distances between consecutive cities
let quality (circuit: City []) =
let length = Array.length circuit
[|
for i in 0 .. (length - 1) ->
distance(circuit.[i], circuit.[(i + 1) % length])
|]
|> Array.sum

// determines if 2 pairs of cities intersect
// see http://stackoverflow.com/a/3842157/114519
let intersects (city1, city2) (city3, city4) =
let det1 = (city1.X - city3.X) * (city2.Y - city3.Y) - (city2.X - city3.X) * (city1.Y - city3.Y)
let det2 = (city1.X - city4.X) * (city2.Y - city4.Y) - (city2.X - city4.X) * (city1.Y - city4.Y)
let det3 = (city3.X - city1.X) * (city4.Y - city1.Y) - (city4.X - city1.X) * (city3.Y - city1.Y)
let det4 = (city3.X - city2.X) * (city4.Y - city2.Y) - (city4.X - city2.X) * (city3.Y - city2.Y)
(det1 * det2 <= 0.0) && (det3 * det4 <= 0.0)

// Pick a random city in the circuit
// and look for an intersection afterwards.
// If an intersection is found, remove the crossing
let decross (rng: Random) (circuit: City []) =
let length = Array.length circuit

if length < 4
then circuit
else
let i = rng.Next(length - 3)
let c1, c2 = circuit.[i], circuit.[i + 1]

let intersection =
seq { i + 2 .. length - 2 }
|> Seq.tryFind (fun i -> intersects (c1, c2) (circuit.[i], circuit.[i+1]))

match intersection with
| None -> circuit
| Some(j) ->
let permutation x =
if x > i && x <= j then i + j + 1 - x
else x
Array.permute permutation circuit

// create an Array of cities on a circle:
// that way, we know the best length is about 2*Pi*R
let testRoute radius points =
let angle = Math.PI * 2.0 / (double)points
[|
for i in 1 .. points ->
{  Name = i.ToString();
X = Math.Cos(angle * (double) i) * radius;
Y = Math.Sin(angle * (double) i) * radius }
|]

let rng = RNG.create()

let root = testRoute 10.0 100 |> shuffle rng

let generator = fun (rng: Random) -> shuffle rng root
let mutator = fun (rng: Random) (circuit: City []) ->
let p = rng.NextDouble()
if ( p < 0.1 )
then decross rng circuit
else randomSwap rng circuit

let evaluator = fun (circuit: City []) -> - quality circuit

let problem = new Problem<City []>(generator, mutator, evaluator)

let displaySolution (circuit: City []) =
Array.iter (fun (c) -> Console.Write(c.Name + " ")) circuit

let foundSomething = fun (msg: SolutionMessage<City []>) ->
Console.WriteLine("{0}, {1}", msg.DateTime.TimeOfDay, msg.Quality)
// Console.WriteLine(displaySolution(msg.Solution))
Console.WriteLine()

let solver = new Solver<City []>()

Console.WriteLine("Press [Enter] to start")
let wait = Console.ReadLine()
Console.WriteLine("Starting: press [Enter] to stop search")

solver.Search problem |> ignore

let wait = Console.ReadLine()
solver.Stop()
Console.WriteLine("Search stopped: press [Enter] to close")

let wait = Console.ReadLine()
Console.WriteLine("Done")
```

Last edited Jun 7, 2012 at 4:14 AM by mathiasb, version 9