Minimal GA implementation in F# per TinyGA rules

tinyga.fs

// TinyGA experimental F# implementation
// SSG 11/27/2008
#light

open System // for random generator

print_endline "TinyGAFS v1.0 - SSG\n"

// check command line 
if Array.length Sys.argv <> 7 then 
    print_endline "Usage: FSGA len popsize generations crossover_prob pmut randseed"
    exit 1
    
// read command line parameters     
let len, popsize, generations, crossover_prob, mutation_prob, rndseed = 
    int(Sys.argv.[1]), int(Sys.argv.[2]), int(Sys.argv.[3]), float(Sys.argv.[4]), float(Sys.argv.[5]), int(Sys.argv.[5+1])
// fitness function (number of bits in array)
let fitness(ar) = 
    ar |> Array.sum_by (fun a -> if a then 1 else 0)

// init random generator
let rnd = if rndseed = 0 then new Random() else new Random(rndseed)

// 50% random
let really() = rnd.Next(2) = 1

// show population stats
let showPopStats pop f generation =
    let maxf = Array.max f
    let bestc = Array.zip pop f |> Array.find (fun (p, f) -> f = maxf) 
                |> fst |> Array.map (fun a -> if a then '1' else '0')
    let avgf = f |> Array.map float |> Array.average    
    printf "Generation #%d - Avg=%2.1f Best=%d (%s)\n" generation avgf maxf (new String(bestc))
    if maxf = len then 
        print_endline "*** Target fitness reached - exiting ***"
        exit 0
    
// generation iteration code    
let rec genetic_iterate generation pop =
    if generation <= generations then 
        assert (popsize = Array.length pop)
        // calculate fitnesses
        let f = Array.init popsize (fun ni -> fitness(pop.[ni])) 
        // cumulative fitness array
        let fcum = Array.sub (f |> Array.scan_left (+) 0) 1 f.Length
        // total fitness
        let totalf = f |> Array.sum
        showPopStats pop f generation
        // do fitness proportionate selection
        let doselection pop = 
            pop |> Array.map (fun c -> 
                Array.zip pop fcum |> Array.find (fun (p, f) -> rnd.Next(totalf) >= f) |> fst)
        // crossover chromosome
        let docrossover pop = 
            pop |> Array.map (fun c ->                 
                if rnd.NextDouble() <= crossover_prob then 
                    Array.map2 (fun a b -> if really() then a else b) pop.[rnd.Next(popsize)] c
                else c)
        // mutate chromosome
        let domutation pop = 
            pop |> Array.map (fun c -> c |> Array.map (fun a -> 
                match rnd.NextDouble() with
                    | n when n <= mutation_prob -> not a
                    | n -> a))
        // build and process new population                            
        pop |> doselection |> docrossover |> domutation |> genetic_iterate (generation + 1)

// start genetic iteration with a random initial population
Array.init popsize (fun n -> Array.init len (fun i -> really())) |> genetic_iterate 1