Bumblebee

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 a list of Cities, we will generate new solutions by shuffling the initial list, and mutate solutions by swapping a random pair of cities. 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

// define a City by ites name and 2 coordinates
[<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

   let swapper (first, second) index =
      if index = first then second
      elif index = second then first
      else index

   // randomly swap 2 items in a list
   let swap set (rng: Random) =
      let last = List.length set
      let first = rng.Next(last)
      let second = rng.Next(last)
      List.permute (fun i -> swapper (first, second) i) set

   // Fisher-Yates random list shuffle 
   let shuffle (rng: Random) set  =
      let rec shuffleIt max set =
         match max with
         | 0 -> set
         | _ ->
            let index = rng.Next(max + 1)
            List.permute (fun i -> swapper (index, max) i) set
            |> shuffleIt (max - 1)
      shuffleIt (List.length set - 1) set

   // overall length of the list of cities
   let quality (list: City list) =
      seq {
         for i in 0 .. (List.length list - 1) -> list.[i]
         yield List.head list }
      |> Seq.pairwise 
      |> Seq.map distance 
      |> Seq.sum     

   // create a list of cities alphabetically ordered
   // around a circle, so that the shortest circuit
   // corresponds to the alphabetical order, or 
   // reversed alphabetical order   
   let testRoute radius points = 
      let angle = Math.PI * 2.0 / (double)points
      List.append ['A'..'Z'] ['a'..'z']
      |> Seq.take points |> Seq.toList 
      |> List.mapi (fun i l -> 
         {  Name = (string)l; 
            X = Math.Cos(angle * (double) i) * radius; 
            Y = Math.Sin(angle * (double) i) * radius})

   // generate a list of 40 cities
   let rng = Random.rng()
   let root = testRoute 10.0 40 |> shuffle rng

   // define the problem via 3 functions
   let generator = fun (rng: Random) -> shuffle rng root
   let mutator = fun ((rng: Random), (circuit: City list)) -> swap circuit rng
   let evaluator = fun (circuit: City list) -> - quality circuit
   
   let problem = new Problem<City list>(generator, mutator, evaluator)

   let displaySolution (circuit: City list) = 
      List.iter (fun (c) -> Console.Write(c.Name)) circuit

   // handler to display best solution identified
   let foundSomething = fun (msg: SolutionMessage<City list>) -> 
      Console.WriteLine("{0}, {1}, {2}", displaySolution(msg.Solution), msg.DateTime.TimeOfDay, msg.Quality)

   // create solver and hook handler to event      
   let solver = new Solver<City list>()
   solver.FoundSolution.Add foundSomething

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

   // start the 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")