Monday, August 9, 2010

Genetic Algorithm with F# - Chromosome

Genetic Algorithm (GA) is my hobby. Let us define the chromosome structure first using F#. As a long time imperative programmer, I am still comfortable to use class.

First I define some random functions, it drives the GA's stochastic searching process. I would like to vision these function as a sequence of numbers rather than a single function. These random numbers is the driving force behind some chromosome-structure identifies on their way find the solution. We call these chromosome-structures population.

    let random = new System.Random((int)System.DateTime.Now.Ticks)
    let randomF() = random.Next()
    let randomFloatF() = random.NextDouble()

Now let us define the chromosome type in GA.

type ChromosomeType(f, size, ?converters) = 
    let initialF = f
    let mutable genos = [for i in 1..size do yield f()]
    let mutable genoPhenoConverters = converters
    member this.Clone() =
        let newValue =
            match (converters) with
                | Some(converters) -> new ChromosomeType(initialF, size, converters)
                | None -> new ChromosomeType(initialF, size)
        newValue.Genos <- this.Genos
    member this.Fitness(fitnessFunction) = this.Pheno |> fitnessFunction
    member this.Genos
        with get() = genos
        and set(value) = genos <- value
    member this.Pheno
        with get() =
            match genoPhenoConverters with
                | Some(genoPhenoConverters) -> genoPhenoConverters genos |> (fun (f,value) -> f value)                  
                | None -> this.Genos
    member this.Mutate(?mutationF) =
        let location = random.Next(Seq.length this.Genos)
        let F =
            match mutationF with
                | Some(mutationF) -> mutationF
                | None -> f
        let transform i v =
            match i with
                | _ when i=location -> F()
                | _ -> v
        this.Genos <- List.mapi transform this.Genos

Most of the GA implementation only has one chromosome representation, my implementation has two

  1. geno types are values, usually this is an integer array
  2. pheno types are values computed from geno types.

I want to design the structure flexible enough so that I can put new mutation function any time I like. The good part about this structure is that you do not have to specify the type, again, the human language does not have type, neither does my program.

No comments: