Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 26. December 2011 11:04

Last week I posted some screen captures of Bumblebee in action on the Traveling Salesman Problem. One thing was bugging me, though – the algorithm didn’t seem to handle crossings very well. I ended up adding a de-crossing routing, which ended up speeding up the process quite a bit. The full C# demo, illustrating how to use Bumblebee from C#, has been pushed as version 0.2 to CodePlex.

Below is an illustration of the algorithm in action, in a nice seasonal color scheme. Santa needs to travel through 200 random cities: starting from a terrible initial route, the algorithm progressively disentangles them and ends up with a pretty good-looking solution under 2 minutes, significantly reducing the carbon footprint of those reindeers:

TSP with 200 cities running for 2 minutes

So what was the issue with line crossings? Consider the following route, in perfect order:

image

Now imagine that while searching, the algorithm discovers the following path:

image

More...

by Mathias 22. May 2011 14:26

In our previous installments, we laid the groundwork of our Bee Colony Algorithm implementation. Today, it’s time to put the bees to work, searching for an acceptable solution to the Traveling Salesman problem.

We will approach the search as a Sequence: starting from an initial hive and solution, we will unfold it, updating the state of the hive and the current best solution at each step. Let’s start with the hive initialization. Starting from an initial route, we need to create a pre-defined number of each Bee type, and provide them with an initial destination:

let Initialize nScouts nActives nInactives cities (rng : Random) =
   [    
      for i in 1 .. nScouts do 
         let solution = Evaluate(Shuffle rng cities)
         yield Scout(solution)
      for i in 1 .. nActives do
         let solution = Evaluate(Shuffle rng cities)
         yield Active(solution, 0)
      for i in 1 .. nActives do
         let solution = Evaluate(Shuffle rng cities)
         yield Inactive(solution)
   ]

There is probably a more elegant way to do this, but this is good enough: we use a simple List comprehension to generate a list on the fly, yielding the appropriate number of each type of bees, and assigning them a shuffled version of the starting route.

More...

by Mathias 8. May 2011 19:43

This is our third episode in attempting to convert a C# bee colony algorithm into an F# equivalent. In our previous posts, we created functions to randomly shuffle lists of cities, and to measure the length of the corresponding path. Today, it’s time to get the bees to work, bringing us new solutions to the hive.

The algorithm distinguishes 3 types of bees: Scout, Active and Inactive. Each bee type has a different role in the algorithms: Scouts keep searching for new solutions, Active bees explore around known solutions for improvements until their potential is exhausted, and Inactive bees wait for new information, and replace Active bees when they turn Inactive.

Let’s start there, and define a Bee discriminated union:

type Bee = Scout | Active | Inactive

In the original C# implementation I am starting from, the algorithm works by iteration: each bee of the hive is processed and its state in the Hive updated (see “The Solve Method” in the article), with 3 steps: the bee

  • finds a new solution and evaluates its quality,
  • shares that information with the inactive bees of the Hive by performing a Waggle Dance,
  • becomes re-allocated as Active or Inactive for the next iteration.

Rather than follow strictly the existing implementation, where all three steps are happening in one single method for a bee, I decided to re-organize it a bit, and separate each of these operations, in part to make the code easier to follow, and in part with an eye to making it run in parallel later.

In that frame, let’s begin with the first step, where bee searches for a new solution. Every bee has a current solution in memory, and after searching, they will come up with a new target solution if it is an improvement. Let’s first define for convenience what a Solution will be:

type Solution = { Route: List<City>; Cost: float }
let Evaluate (route: List<City>) = { Route = route; Cost = CircuitCost route }

A Solution wraps in a Record the Route – the ordered list of Cities travelled – and its Cost, measured by its length. We also define a convenience function Evaluate, which takes in a Route and returns the corresponding solution, with the original Route and its Cost, computed using the function we wrote in our last post.

More...

by Mathias 28. April 2011 16:35

In my last post, I began my attempt at replicating a Bee Colony implementation from C# to F#, generating random solutions by permuting Cities in the Traveling Salesman circuit. Today, we’ll look at another ingredient of the problem: the evaluation of solutions. We need to be able to compare the quality of solutions to determine whether they constitute an improvement.

In our case, we will represent each City by 2 coordinates in the plane, and simply use the Euclidean distance as our cost measure – so our goal is to minimize the total distance travelled.

Let’s model a City as a record:

type City = { X: float; Y: float; }

We can now create list of cities, which will represent solutions:

> type City = { X: float; Y: float; }
let c1 = { X = 0.0; Y = 0.0}
let c2 = { X = 3.0; Y = 0.0}
let c3 = { X = 0.0; Y = 4.0};;

type City =
  {X: float;
   Y: float;}
val c1 : City = {X = 0.0;
                 Y = 0.0;}
val c2 : City = {X = 3.0;
                 Y = 0.0;}
val c3 : City = {X = 0.0;
                 Y = 4.0;}

> let cities = [c1; c2; c3];;

val cities : City list = [{X = 0.0;
                           Y = 0.0;}; {X = 3.0;
                                       Y = 0.0;}; {X = 0.0;
                                                   Y = 4.0;}]

More...

by Mathias 24. April 2011 11:44

April 2011’s issue of MSDN Magazine had an interesting piece on Bee Colony Algorithms by Dr. James McCaffrey, explaining the concepts and providing an example, applying the algorithm to the Traveling Salesman Problem. In a nutshell, the algorithm is a meta-heuristic, that is, a method that is not guaranteed to produce an optimal solution, but will search for “decent” solutions in a large space. In a real-life bee hive,  bees scout for areas rich with food, keep visiting them until they are exhausted, and tell other bees about good spots so that more bees come search that area. By analogy, the algorithm uses scout bees, which search for new random solutions, and recruit inactive bees which become active and start searching for improved solutions around their current solution.

I found the algorithm intriguing, and thought it would be a good learning exercise to try and adapt it to F#.

Disclaimer: I am still learning the ropes in F#, so take the code that follows with a grain of salt. I’ll gladly take advice and criticism to make this better – my intent is to share my learning experience with the language, not to teach you best practices. 

In the case of the Traveling Salesman Problem, the goal is to find the shortest (or some other cost measure) closed route connecting a list of cities. In order to do this, we need to be able to create random solutions, as well as solutions in the neighborhood of an existing solution.

Assuming we begin with an initial list of Cities (the cities our salesman needs to visit), we can generate random solutions by shuffling that list, using the Fisher-Yates shuffle algorithm. We can generate the sequence of index pairs that need to be swapped with the following

let SwapIndexPairs list =  
   let random = new Random()
   seq { 
      for i in (List.length list - 1) .. -1 .. 1 do 
      yield (i, random.Next(i + 1)) }

Running this in the interactive window produces the following:

> open System;;
> let SwapIndexPairs list =  
   let random = new Random()
   seq { 
      for i in (List.length list - 1) .. -1 .. 1 do 
      yield (i, random.Next(i + 1)) };;

val SwapIndexPairs : 'a list -> seq<int * int>

> let i = SwapIndexPairs [0;1;2;3;4;5] |> Seq.toList;;

val i : (int * int) list = [(5, 0); (4, 0); (3, 2); (2, 1); (1, 1)]

More...

Comments

Comment RSS