Moo.GeneticAlgorithm.Types

Data structures

type Genome a = [a]

A genetic representation of an individual solution.

type Objective = Double

A measure of the observed performance. It may be called cost for minimization problems, or fitness for maximization problems.

type Phenotype a = (Genome a, Objective)

A genome associated with its observed Objective value.

type Population a = [Phenotype a]

An entire population of observed Phenotypes.

class GenomeState gt a where

takeGenome extracts a raw genome from any type which embeds it.

Methods

takeGenome :: gt -> Genome a

Instances

~ * a1 a2 => GenomeState (Phenotype a1) a2

~ * a1 a2 => GenomeState (Genome a1) a2

~ * a1 a2 => GenomeState (MultiPhenotype a1) a2

takeObjectiveValue :: Phenotype a -> Objective

GA operators

data ProblemType

A type of optimization problem: whether the objective function has to be miminized, or maximized.

Constructors

Minimizing

Maximizing

Instances

Eq ProblemType

Show ProblemType

class ObjectiveFunction f a where

A function to evaluate a genome should be an instance of ObjectiveFunction class. It may be called a cost function for minimization problems, or a fitness function for maximization problems.

Some genetic algorithm operators, like rouletteSelect, require the Objective to be non-negative.

Methods

evalObjective :: f -> [Genome a] -> Population a

Instances

~ * a1 a2 => ObjectiveFunction ([Genome a1] -> [(Genome a1, Objective)]) a2

Evaluate fitness (cost) of all genomes, possibly changing their order.

~ * a1 a2 => ObjectiveFunction ([Genome a1] -> [Objective]) a2

Evaluate all fitness (cost) values at once.

~ * a1 a2 => ObjectiveFunction (Genome a1 -> Objective) a2

Evaluate fitness (cost) values genome per genome.

type SelectionOp a = Population a -> Rand (Population a)

A selection operator selects a subset (probably with repetition) of genomes for reproduction via crossover and mutation.

type CrossoverOp a = [Genome a] -> Rand ([Genome a], [Genome a])

A crossover operator takes some parent genomes and returns some children along with the remaining parents. Many crossover operators use only two parents, but some require three (like UNDX) or more. Crossover operator should consume as many parents as necessary and stop when the list of parents is empty.

type MutationOp a = Genome a -> Rand (Genome a)

A mutation operator takes a genome and returns an altered copy of it.

Dummy operators

noMutation :: MutationOp a

Don't mutate.

noCrossover :: CrossoverOp a

Don't crossover.

Life cycle

type StepGA m a

Arguments

 = Cond a

stop condition

-> PopulationState a

population of the current generation

-> m (StepResult (Population a))

population of the next generation

A single step of the genetic algorithm. See also nextGeneration.

data Cond a

Iterations stop when the condition evaluates as True.

Constructors

Generations Int

stop after n generations

IfObjective ([Objective] -> Bool)

stop when objective values satisfy the predicate

forall b . Eq b => GensNoChange

terminate when evolution stalls

Fields

c'maxgens :: Int

max number of generations for an indicator to be the same

c'indicator :: [Objective] -> b

stall indicator function

c'counter :: Maybe (b, Int)

a counter (initially Nothing)

Or (Cond a) (Cond a)

stop when at least one of two conditions holds

And (Cond a) (Cond a)

stop when both conditions hold

type PopulationState a = Either [Genome a] [Phenotype a]

On life cycle of the genetic algorithm:

   [ start ]
       |
       v
   (genomes) --> [calculate objective] --> (evaluated genomes) --> [ stop ]
       ^  ^                                       |
       |  |                                       |
       |  `-----------.                           |
       |               \                          v
   [ mutate ]        (elite) <-------------- [ select ]
       ^                                          |
       |                                          |
       |                                          |
       |                                          v
   (genomes) <----- [ crossover ] <-------- (evaluted genomes)

PopulationState can represent either genomes or evaluated genomed.

data StepResult a

A data type to distinguish the last and intermediate steps results.

Constructors

StopGA a

ContinueGA a

Instances

Show a => Show (StepResult a)