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 []>()
   solver.FoundSolution.Add foundSomething

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