This project is read-only.
The code sample below is a F# solution that uses Bumblebee to solve the following problem, which came from this StackOverflow question:

Given a group of n items, each with a distinct value V(i), what is the best way to divide the items into 3 groups so the group with the highest value is minimIzed? Give the value of this largest group.

The following is a F# implementation; to make the sample work, just create a F# Console app, add a reference to the Bumblebee dll (version 0.2), and paste in the following.

Check out this blog post for comments on the implementation!

open ClearLines.Bumblebee
open System

type Allocation = { Element: int; Group: int }

let Main = 
   
   let groups = 3
   let rng = new Random()
   let root = [ for i in 0 .. 1000 -> rng.Next(0, 100000) ]
               
   let generate = fun (rng: Random) ->
      List.map (fun e -> { Element = e; Group = rng.Next(0, groups) }) root

   let mutate = fun (rng: Random, solution: Allocation list) -> 
      let count = List.length solution
      let changed = rng.Next(0, count)      
      solution |> List.mapi (fun i e -> 
         if i = changed then 
            { Element = e.Element; Group = rng.Next(0, groups) } 
         else e)

   let evaluate = fun (solution: Allocation list) -> 
      let groupValues =
         [
            for g in 0 .. (groups - 1) -> 
            List.filter (fun e -> e.Group = g) solution 
            |> List.sumBy (fun e -> e.Element);
         ]
      List.min (groupValues) - List.max (groupValues) |> (float)

   let problem = new Problem<Allocation list>(generate, mutate, evaluate)
   let solver = new Solver<Allocation list>()

   let displaySolution (solution: Allocation list) = 
      [ 
         for g in 0 .. (groups - 1) -> 
            let group = List.filter (fun e -> e.Group = g) solution 
            Console.Write("Total group {0}: {1} // ", g, List.sumBy (fun e -> e.Element) group)
            //List.map (fun i -> Console.Write("<{0},{1}> ", i.Element, i.Group)) group |> ignore
            Console.WriteLine ()
      ] 

   let foundSomething = fun (msg: SolutionMessage<Allocation list>) -> 
      Console.WriteLine("New solution of quality {0} found at {1}", msg.Quality, msg.DateTime.TimeOfDay) 
      displaySolution(msg.Solution) |> ignore
      Console.WriteLine()

   solver.FoundSolution.Add foundSomething
         
   solver.Search(problem) |> ignore

   Console.ReadLine() |> ignore

Last edited Jan 6, 2012 at 9:28 PM by mathiasb, version 2

Comments

No comments yet.