CodePlexProject Hosting for Open Source Software

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.

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