Marcus Cuda

We’ve added a continuous, single objective function genetic algorithm (GA) to Xaye.  The GA provides the selection, mating, and mutations methods discussed in chapter 2 and 3 of “Practical Genetic Algorithms” by Haupt and Haupt. The code is extensible so users can add their own routines.

The simplest way to use the Xaye GA is use the solve method. It only requires a cost/fitness function and bounds on the variables of the cost function. For an example, lets minimize:       for -10 < x < 10

let cost = fun (x:float[]) ->(x.[0]*x.[0]+x.[0]) * Math.Cos(x.[0])
let bound = {lower = -10.0; upper = 10.0}
let bounds = [| bound; |]
let status = solve cost bounds
printfn "%A" status
{Iteration = 69;
 Best = ([|9.620350903|], -100.2237551);
 NoImprovement = 25;
 Termination = NoImprovement;}

The solve function returns a Status record that contains the number of iterations, best solution found, how many iterations since we found the best solution (NoImprovement), and why the optimization terminated. In this case, solve needed 69 iterations to find the minimum and it terminated early because it was no longer improving on the best solution (we default to a maximum of a 1000 iterations and stop if we there was no  improvement after 25 iterations). It uses the our defaultMate function (top x chromosome selection, pairing parents using a rank squared weighted roulette, and a heuristic blend crossover), the uniformMutate function, and generates a random starting population of 20. These defaults work well for relatively simple functions.

Lets try a little more difficult cost function:      for -10 < x < 10.  The minimum is at x,y=0.

let cost = fun (x:float[]) ->
   let x0 = Math.Abs(x.[0])
   let x1 = Math.Abs(x.[1])
   x0 - 10.0*Math.Cos(Math.Sqrt(10.0*x0)) + x1 - 10.0*Math.Cos(Math.Sqrt(10.0*x1))
let bound = {lower = -10.0; upper = 10.0}
let bounds = [| bound; |]
let status = solve cost bounds
printfn "%A" status
{Iteration = 41;
 Best = ([|3.510642794; 0.007216450758|], -15.48906593);
 NoImprovement = 25;
 Termination = NoImprovement;}

We got stuck at a local minimum. Instead of using the solve function, we can use the defaultEvolve function. This uses the same default mating and mutation methods as solve, but allows us tweak the optimization options. Lets increase the size of the population, decrease the selection rate (the percentage of the current generation to use for mating and to copy into the next generation), and increase the number of no improvement iterations. We will now sample more of the solution space but at a cost of a longer running time. As you can see below, we now find the global minimum.

let options = {DefaultOptions with PopulationSize=1000; SelectionRate=0.1; NoImprovement=50 }
let status = defaultEvolve options cost bounds
printfn "%A" status
{Iteration = 92;
 Best = ([|1.585990353e-17; -4.292601412e-18|], -20.0);
 NoImprovement = 50;
 Termination = NoImprovement;}

We also have a fully customizable evolve function that allows users to build any type of GA.

type Fitness = float
type Gene = float
type Chromosome = Gene[]
type Population = Chromosome[]
type EvaluatedPopulation = (Chromosome*Fitness)[]
type Parents = Chromosome*Chromosome
type Cost = Chromosome -> Fitness
type Mate = EvaluatedPopulation -> Population
type Mutate =  Population -> Population
type Convergence = Options -> Status -> EvaluatedPopulation -> bool
evolve : Options -> Cost -> Mate -> Mutate -> Convergence -> Population -> Status

For example, to create a GA where we replace the full population each generation, use Haupt’s extrapolation crossover, a 3 chromosome tournament for selecting parents, and use a normally distributed mutation method (gene + random normal(0,1) ), we’d:

let cost = fun (x:float[]) ->
   let x0 = Math.Abs(x.[0])
   let x1 = Math.Abs(x.[1])
   x0 - 10.0*Math.Cos(Math.Sqrt(10.0*x0)) + x1 - 10.0*Math.Cos(Math.Sqrt(10.0*x1))
let bound = {lower = -10.0; upper = 10.0}
let bounds = [| bound; bound; |]
let replaceAll (options:Options) (bounds:Bounds[]) (population:EvaluatedPopulation) : Population =
   let pairs = options.PopulationSize/2
   let pairing = pairTournament3 options.Random pairs
   let crossover = extrapolationCrossover options.Random
   population |> pairing |> crossover

use norm = new Normal01()
let mutation = mutateNormal options norm bounds
let initial = generateInitial options bounds
let status = evolve DefaultOptions cost mate mutation defaultConvergence initial

defaultConvergence just checks to see if we’ve reached the maximum number of iterations or that the best solution hasn’t improved in options.NoImprovement number of iterations.

Next we’ll implements parts of chapter 5: hybrid GA (mix the GA with a local optimizer), multiple objective functions, and a parallel GA . And tweak the current implementation to make it more “functional” – still getting the hang of functional programming.