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...

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...

In my last post, I looked into running a simple simulation using F# sequences; our model mapped a sequence of random numbers to 2 states, Rainy and Sunny.

What if we wanted to model something a bit more realistic, like a system where the weather tomorrow depends on the weather today? Let’s say, for instance, that if the weather is Sunny today, there is a 60% chance that it’s still Sunny tomorrow, but if it’s Rainy today, we have a 70% chance that tomorrow is Rainy.

Technicality: we will also assume that if we know today’s weather, what happened yesterday brings us no additional information on the probability of rain or sun tomorrow.

Let’s start like last time, and define first a Weather type, with 2 states, Rainy and Sunny, and represent the transitions from state to state, using pattern matching:

type Weather = Sunny | Rainy

let NextDay today proba =
    match today with
    | Rainy -> if proba < 0.7 then Rainy else Sunny
    | Sunny -> if proba < 0.6 then Sunny else Rainy

Armed with this, starting from an initial state, we want to generate the next state, based on the current state and the next probability coming from the sequence of random numbers. This part got me stumped for a while. Using a Sequence map is clearly not going to work, because, unlike in the previous post, we can’t determine the Weather based on the probability alone, we need both the probability and the previous Weather. Conversely, Sequence unfold has the opposite problem: it generates a sequence of states based on the previous State, but doesn’t take in another Sequence as input.

More...

One of my initial goals for 2011 was to get my feet wet with Python, but after the last (and excellent) San Francisco F# user group meetup, dedicated to F# for Python developers, I got all excited about F# again, and dug back my copy of Programming F#.

The book contains a Sequence example which I found inspiring:

open System

let RandomSequence =
  let random = new Random()
  seq { 
    while true do
    yield random.NextDouble() }

What’s nice about this is that it is a lazy sequence; each element of the Sequence will be pulled in memory “on demand”, which makes it possible to work with Sequences of arbitrary length without running into memory limitation issues.

This formulation looks a lot like a simulation, so I thought I would explore that direction. What about modeling the weather, in a fictional country where 60% of the days are Sunny, and the others Rainy?

Keeping our weather model super-simple, we could do something along these lines: we define a Weather type, which can be either Sunny or Rainy, and a function WeatherToday, which given a probability, returns the adequate Weather.

type Weather = Sunny | Rainy

let WeatherToday probability =
  if probability < 0.6 then Sunny
  else Rainy

More...

In my last post I explored how ExcelDNA can be used to write high-performance UDFs for Excel, calling .Net code without the overhead of VSTO. Using .Net instead of VBA for intensive computations already yields a nice improvement. Still, I regretted that ExcelDNA supports .Net up to 3.5 only, which puts the Task Parallel Library off limits – and is too bad  because the TPL is just totally awesome to leverage the power of multi-cores.

As it turned out, this isn’t totally correct. Govert  Van Drimmelen (the man behind ExcelDNA) and Jon Skeet (the Chuck Norris of .Net) pointed that while the Task Parallel Library is a .Net 4.0 library, the Reactive Extensions for .Net 3.5 contains an unsupported 3.5 version of the TPL – which means that it should be possible to get parallelism to work with ExcelDNA.

This isn’t a pressing need of mine, so I thought I would leave that alone, and wait for the 4.0 version of ExcelDNA. Yeah right. Between my natural curiosity, Ross McLean’s comment (have fun at the Excel UK Dev Conference!), and the fact that I really want to know if I could get the Walkenbach test to run under 1 second, without too much of an effort, I had to check. And the good news is, yep, it works.

Last time we saw how to turn an average PC into a top-notch performer; let’s see how we can inject some parallelism to get a smoking hot calculation engine.

More...