Bumblebee is an Artificial Bee Colony solver, written in F#. The main class of Bumblebee is the Solver, and its purpose is to search for solutions to a generic Problem with the highest Quality possible. The Solver exposes two main methods, and an event: Search, Stop and FoundSolution.

Search, Stop, and FoundSolution

Given a generic problem of type T (T being a Solution to the problem), Search will begin searching for improved solutions, and continue searching until Stop is called, which will interrupt the Search. Whenever a solution that is better than the current best is encountered, the Solver will raise the FoundSolution event, which returns a SolutionMessage containing the Solution, its Quality measurement, and the time the solution was found.

It is impossible for the Solver to determine whether a Solution is optimal; therefore, the caller is responsible to decide when to terminate the Search by calling Stop. That call could be based on observing no improvement for a certain length of time, or on the rate of improvement between solutions, for instance.

Defining the Problem

Defining the Problem is the complex part of the exercise. The Search method requires a Problem for the Solver to operate on:

F#: Search(problem: Problem<’a>)
C#: Search(Problem<T> problem)

A Problem is a generic class, and requires three functions: Generate, Mutate and Evaluate.

Evaluate takes a solution and returns a float, which measures the Quality of the solution:

F#: 'a -> float
C#: Func<T, float>

Evaluate should be increasing with the Quality of the Solution, that is, if a solution is better than another, the value returned by Evaluate should be greater. The Solver will use that function to decide whether a new Solution is an improvement.

Generate takes in a Random, and returns a Solution:

F#: Random -> ‘a
C#: Func<Random, T>

The purpose of Generate is to produce new Solutions, regardless of what solutions have been identified by the Solver thus far. In terms of Bees activity, this represents a Bee exploring for new territory.

Mutate takes in a Tuple consisting of a Random and a known Solution, and returns a Solution:

F#: (Random * ‘a) -> ‘a
C#: Func<<Tuple<Random, T>, T>

The purpose of Mutate is to produce a Solution in the neighborhood of a known Solution. In terms of Bees activity, this represents a Bee exploring around a known territory, looking for potential improvements.

Last edited Jan 7, 2012 at 3:21 AM by mathiasb, version 2

Comments

No comments yet.