Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
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;}]


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)]



Comment RSS