-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Genetic algorithm library
--
-- Moo library provides building blocks to build custom genetic
-- algorithms in Haskell. They can be used to find solutions to
-- optimization and search problems.
--
-- Variants supported out of the box: binary (using bit-strings) and
-- continuous (real-coded). Potentially supported variants: permutation,
-- tree, hybrid encodings (require customizations).
--
-- Binary GAs: binary and Gray encoding; point mutation; one-point,
-- two-point, and uniform crossover. Continuous GAs: Gaussian mutation;
-- BLX-α, UNDX, and SBX crossover. Selection operators: roulette,
-- tournament, and stochastic universal sampling (SUS); with optional
-- niching, ranking, and scaling. Replacement strategies: generational
-- with elitism and steady state. Constrained optimization: random
-- constrained initialization, death penalty, constrained selection
-- without a penalty function. Multi-objective optimization: NSGA-II and
-- constrained NSGA-II.
@package moo
@version 1.2
-- | Some extra facilities to work with Rand monad and PureMT
-- random number generator.
module Moo.GeneticAlgorithm.Random
-- | Yield a new randomly selected value of type a in the range
-- (lo, hi). See randomR for details.
getRandomR :: Random a => (a, a) -> Rand a
-- | Yield a new randomly selected value of type a. See
-- random for details.
getRandom :: Random a => Rand a
-- | Yield two randomly selected values which follow standard normal
-- distribution.
getNormal2 :: Rand (Double, Double)
-- | Yield one randomly selected value from standard normal distribution.
getNormal :: Rand Double
-- | Take at most n random elements from the list. Preserve order.
randomSample :: Int -> [a] -> Rand [a]
-- | Select sampleSize numbers in the range from 0 to
-- (populationSize-1). The function works best when
-- sampleSize is much smaller than populationSize.
randomSampleIndices :: Int -> Int -> Rand [Int]
-- | Randomly reorder the list.
shuffle :: [a] -> Rand [a]
-- | Modify value with probability p. Return the unchanged value
-- with probability 1-p.
withProbability :: Double -> (a -> Rand a) -> a -> Rand a
getBool :: Rand Bool
getInt :: Rand Int
getWord :: Rand Word
getInt64 :: Rand Int64
getWord64 :: Rand Word64
getDouble :: Rand Double
-- | Unwrap a random monad computation as a function. (The inverse of
-- liftRand.)
runRand :: () => Rand g a -> g -> (a, g)
-- | Evaluate a random computation with the given initial generator and
-- return the final value, discarding the final generator.
--
--
evalRand :: () => Rand g a -> g -> a
-- | Create a new PureMT generator, using the clocktime as the base for the
-- seed.
newPureMT :: IO PureMT
-- | Construct a random monad computation from a function. (The inverse of
-- runRand.)
liftRand :: () => (g -> (a, g)) -> Rand g a
type Rand = Rand PureMT
-- | With a source of random number supply in hand, the Random class
-- allows the programmer to extract random values of a variety of types.
--
-- Minimal complete definition: randomR and random.
class Random a
-- | PureMT, a pure mersenne twister pseudo-random number generator
data PureMT
-- | Basic statistics for lists.
module Moo.GeneticAlgorithm.Statistics
-- | Average
average :: (Num a, Fractional a) => [a] -> a
-- | Population variance (divided by n).
variance :: Floating a => [a] -> a
-- | Compute empirical qunatiles (using R type 7 continuous sample
-- quantile).
quantiles :: (Real a, RealFrac a) => [a] -> [a] -> [a]
-- | Median
median :: (Real a, RealFrac a) => [a] -> a
-- | Interquartile range.
iqr :: (Real a, RealFrac a) => [a] -> a
module Moo.GeneticAlgorithm.Types
-- | A genetic representation of an individual solution.
type Genome a = [a]
-- | A measure of the observed performance. It may be called cost for
-- minimization problems, or fitness for maximization problems.
type Objective = Double
-- | A genome associated with its observed Objective value.
type Phenotype a = (Genome a, Objective)
-- | An entire population of observed Phenotypes.
type Population a = [Phenotype a]
-- | takeGenome extracts a raw genome from any type which embeds it.
class GenomeState gt a
takeGenome :: GenomeState gt a => gt -> Genome a
takeObjectiveValue :: Phenotype a -> Objective
-- | A type of optimization problem: whether the objective function has to
-- be miminized, or maximized.
data ProblemType
Minimizing :: ProblemType
Maximizing :: ProblemType
-- | 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.
class ObjectiveFunction f a
evalObjective :: ObjectiveFunction f a => f -> [Genome a] -> Population a
-- | A selection operator selects a subset (probably with repetition) of
-- genomes for reproduction via crossover and mutation.
type SelectionOp a = Population a -> Rand (Population 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 CrossoverOp a = [Genome a] -> Rand ([Genome a], [Genome a])
-- | A mutation operator takes a genome and returns an altered copy of it.
type MutationOp a = Genome a -> Rand (Genome a)
-- | Don't mutate.
noMutation :: MutationOp a
-- | Don't crossover.
noCrossover :: CrossoverOp a
-- | A single step of the genetic algorithm. See also
-- nextGeneration.
type StepGA m a = Cond a " stop condition
" -> PopulationState a " population of the current generation
" -> m (StepResult (Population a)) " population of the next generation
"
-- | Iterations stop when the condition evaluates as True.
data Cond a
-- | stop after n generations
Generations :: Int -> Cond a
-- | stop when objective values satisfy the predicate
IfObjective :: ([Objective] -> Bool) -> Cond a
-- | terminate when evolution stalls
GensNoChange :: Int -> ([Objective] -> b) -> Maybe (b, Int) -> Cond a
-- | max number of generations for an indicator to be the same
[c'maxgens] :: Cond a -> Int
-- | stall indicator function
[c'indicator] :: Cond a -> [Objective] -> b
-- | a counter (initially Nothing)
[c'counter] :: Cond a -> Maybe (b, Int)
-- | stop when at least one of two conditions holds
Or :: Cond a -> Cond a -> Cond a
-- | stop when both conditions hold
And :: Cond a -> Cond a -> Cond 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.
type PopulationState a = Either [Genome a] [Phenotype a]
-- | A data type to distinguish the last and intermediate steps results.
data StepResult a
StopGA :: a -> StepResult a
ContinueGA :: a -> StepResult a
instance GHC.Show.Show a => GHC.Show.Show (Moo.GeneticAlgorithm.Types.StepResult a)
instance GHC.Classes.Eq Moo.GeneticAlgorithm.Types.ProblemType
instance GHC.Show.Show Moo.GeneticAlgorithm.Types.ProblemType
instance (a1 Data.Type.Equality.~ a2) => Moo.GeneticAlgorithm.Types.ObjectiveFunction (Moo.GeneticAlgorithm.Types.Genome a1 -> Moo.GeneticAlgorithm.Types.Objective) a2
instance (a1 Data.Type.Equality.~ a2) => Moo.GeneticAlgorithm.Types.ObjectiveFunction ([Moo.GeneticAlgorithm.Types.Genome a1] -> [Moo.GeneticAlgorithm.Types.Objective]) a2
instance (a1 Data.Type.Equality.~ a2) => Moo.GeneticAlgorithm.Types.ObjectiveFunction ([Moo.GeneticAlgorithm.Types.Genome a1] -> [(Moo.GeneticAlgorithm.Types.Genome a1, Moo.GeneticAlgorithm.Types.Objective)]) a2
instance (a1 Data.Type.Equality.~ a2) => Moo.GeneticAlgorithm.Types.GenomeState (Moo.GeneticAlgorithm.Types.Genome a1) a2
instance (a1 Data.Type.Equality.~ a2) => Moo.GeneticAlgorithm.Types.GenomeState (Moo.GeneticAlgorithm.Types.Phenotype a1) a2
-- | Helper functions to run genetic algorithms and control iterations.
module Moo.GeneticAlgorithm.Run
-- | Helper function to run the entire algorithm in the Rand monad.
-- It takes care of generating a new random number generator.
runGA :: Rand [Genome a] -> ([Genome a] -> Rand b) -> IO b
-- | Helper function to run the entire algorithm in the IO monad.
runIO :: Rand [Genome a] -> (IORef PureMT -> [Genome a] -> IO (Population a)) -> IO (Population a)
-- | Construct a single step of the genetic algorithm.
--
-- See Moo.GeneticAlgorithm.Binary and
-- Moo.GeneticAlgorithm.Continuous for the building blocks of the
-- algorithm.
nextGeneration :: ObjectiveFunction objectivefn a => ProblemType -> objectivefn -> SelectionOp a -> Int -> CrossoverOp a -> MutationOp a -> StepGA Rand a
-- | Construct a single step of the incremental (steady-steate) genetic
-- algorithm. Exactly n worst solutions are replaced with newly
-- born children.
--
-- See Moo.GeneticAlgorithm.Binary and
-- Moo.GeneticAlgorithm.Continuous for the building blocks of the
-- algorithm.
nextSteadyState :: ObjectiveFunction objectivefn a => Int -> ProblemType -> objectivefn -> SelectionOp a -> CrossoverOp a -> MutationOp a -> StepGA Rand a
-- | Wrap a population transformation with pre- and post-conditions to
-- indicate the end of simulation.
--
-- Use this function to define custom replacement strategies in addition
-- to nextGeneration and nextSteadyState.
makeStoppable :: (ObjectiveFunction objectivefn a, Monad m) => objectivefn -> (Population a -> m (Population a)) -> StepGA m a
-- | Run strict iterations of the genetic algorithm defined by
-- step. Return the result of the last step. Usually only the
-- first two arguments are given, and the result is passed to
-- runGA.
loop :: Monad m => Cond a -> StepGA m a -> [Genome a] -> m (Population a)
-- | GA iteration interleaved with the same-monad logging hooks. Usually
-- only the first three arguments are given, and the result is passed to
-- runGA.
loopWithLog :: (Monad m, Monoid w) => LogHook a m w -> Cond a -> StepGA m a -> [Genome a] -> m (Population a, w)
-- | GA iteration interleaved with IO (for logging or saving the
-- intermediate results); it takes and returns the updated random number
-- generator via an IORef. Usually only the first three arguments are
-- given, and the result is passed to runIO.
loopIO :: [IOHook a] -> Cond a -> StepGA Rand a -> IORef PureMT -> [Genome a] -> IO (Population a)
-- | Iterations stop when the condition evaluates as True.
data Cond a
-- | stop after n generations
Generations :: Int -> Cond a
-- | stop when objective values satisfy the predicate
IfObjective :: ([Objective] -> Bool) -> Cond a
-- | terminate when evolution stalls
GensNoChange :: Int -> ([Objective] -> b) -> Maybe (b, Int) -> Cond a
-- | max number of generations for an indicator to be the same
[c'maxgens] :: Cond a -> Int
-- | stall indicator function
[c'indicator] :: Cond a -> [Objective] -> b
-- | a counter (initially Nothing)
[c'counter] :: Cond a -> Maybe (b, Int)
-- | stop when at least one of two conditions holds
Or :: Cond a -> Cond a -> Cond a
-- | stop when both conditions hold
And :: Cond a -> Cond a -> Cond a
-- | Logging to run every nth iteration starting from 0 (the first
-- parameter). The logging function takes the current generation count
-- and population.
data LogHook a m w
[WriteEvery] :: (Monad m, Monoid w) => Int -> (Int -> Population a -> w) -> LogHook a m w
-- | Input-output actions, interactive and time-dependent stop conditions.
data IOHook a
-- | action to run every nth iteration, starting from 0; initially
-- (at iteration 0) the objective value is zero.
DoEvery :: Int -> (Int -> Population a -> IO ()) -> IOHook a
[io'n] :: IOHook a -> Int
[io'action] :: IOHook a -> Int -> Population a -> IO ()
-- | custom or interactive stop condition
StopWhen :: IO Bool -> IOHook a
-- | terminate iteration after t seconds
TimeLimit :: Double -> IOHook a
[io't] :: IOHook a -> Double
-- | Continuous (real-coded) genetic algorithms. Candidate solutions are
-- represented as lists of real variables.
module Moo.GeneticAlgorithm.Continuous
-- | Generate n uniform random genomes with individual genome
-- elements bounded by ranges. This corresponds to random
-- uniform sampling of points (genomes) from a hyperrectangle with a
-- bounding box ranges.
getRandomGenomes :: (Random a, Ord a) => Int -> [(a, a)] -> Rand [Genome a]
-- | Generate at most popsize genomes uniformly distributed in
-- ranges.
uniformGenomes :: Int -> [(Double, Double)] -> [Genome Double]
-- | Objective-proportionate (roulette wheel) selection: select n
-- random items with each item's chance of being selected is proportional
-- to its objective function (fitness). Objective function should be
-- non-negative.
rouletteSelect :: Int -> SelectionOp a
-- | Stochastic universal sampling (SUS) is a selection technique similar
-- to roulette wheel selection. It gives weaker members a fair chance to
-- be selected, which is proportinal to their fitness. Objective function
-- should be non-negative.
stochasticUniversalSampling :: Int -> SelectionOp a
-- | Performs tournament selection among size individuals and
-- returns the winner. Repeat n times.
tournamentSelect :: ProblemType -> Int -> Int -> SelectionOp a
-- | Apply given scaling or other transform to population before selection.
withPopulationTransform :: (Population a -> Population a) -> SelectionOp a -> SelectionOp a
-- | Transform objective function values before seletion.
withScale :: (Objective -> Objective) -> SelectionOp a -> SelectionOp a
-- | Replace objective function values in the population with their ranks.
-- For a population of size n, a genome with the best value of
-- objective function has rank n' <= n, and a genome with the
-- worst value of objective function gets rank 1.
--
-- rankScale may be useful to avoid domination of few
-- super-genomes in rouletteSelect or to apply
-- rouletteSelect when an objective function is not necessarily
-- positive.
rankScale :: ProblemType -> Population a -> Population a
-- | A popular niching method proposed by D. Goldberg and J. Richardson in
-- 1987. The shared fitness of the individual is inversely protoptional
-- to its niche count. The method expects the objective function to be
-- non-negative.
--
-- An extension for minimization problems is implemented by making the
-- fitnes proportional to its niche count (rather than inversely
-- proportional).
--
-- Reference: Chen, J. H., Goldberg, D. E., Ho, S. Y., & Sastry, K.
-- (2002, July). Fitness inheritance in multiobjective optimization. In
-- Proceedings of the Genetic and Evolutionary Computation Conference
-- (pp. 319-326). Morgan Kaufmann Publishers Inc..
withFitnessSharing :: (Phenotype a -> Phenotype a -> Double) -> Double -> Double -> ProblemType -> SelectionOp a -> SelectionOp a
-- | 1-norm distance: sum |x_i - y-i|.
distance1 :: Num a => [a] -> [a] -> a
-- | 2-norm distance: (sum (x_i - y_i)^2)^(1/2).
distance2 :: Floating a => [a] -> [a] -> a
-- | Infinity norm distance: max |x_i - y_i|.
distanceInf :: Real a => [a] -> [a] -> a
-- | Reorders a list of individual solutions, by putting the best in the
-- head of the list.
bestFirst :: ProblemType -> Population a -> Population a
-- | Blend crossover (BLX-alpha) for continuous genetic algorithms. For
-- each component let x and y be its values in the
-- first and the second parent respectively. Choose corresponding
-- component values of the children independently from the uniform
-- distribution in the range (L,U), where L = min (x,y) - alpha *
-- d, U = max (x,y) + alpha * d, and d = abs (x -
-- y). alpha is usually 0.5. Takahashi in
-- [10.1109/CEC.2001.934452] suggests 0.366.
blendCrossover :: Double -> CrossoverOp Double
-- | Unimodal normal distributed crossover (UNDX) for continuous genetic
-- algorithms. Recommended parameters according to [ISBN
-- 978-3-540-43330-9] are sigma_xi = 0.5, sigma_eta =
-- 0.35/sqrt(n), where n is the number of variables
-- (dimensionality of the search space). UNDX mixes three parents,
-- producing normally distributed children along the line between first
-- two parents, and using the third parent to build a supplementary
-- orthogonal correction component.
--
-- UNDX preserves the mean of the offspring, and also the covariance
-- matrix of the offspring if sigma_xi^2 = 0.25. By preserving
-- distribution of the offspring, /the UNDX can efficiently search in
-- along the valleys where parents are distributed in functions with
-- strong epistasis among parameters/ (idem).
unimodalCrossover :: Double -> Double -> CrossoverOp Double
-- | Run unimodalCrossover with default recommended parameters.
unimodalCrossoverRP :: CrossoverOp Double
-- | Simulated binary crossover (SBX) operator for continuous genetic
-- algorithms. SBX preserves the average of the parents and has a spread
-- factor distribution similar to single-point crossover of the binary
-- genetic algorithms. If n > 0, then the heighest
-- probability density is assigned to the same distance between children
-- as that of the parents.
--
-- The performance of real-coded genetic algorithm with SBX is similar to
-- that of binary GA with a single-point crossover. For details see
-- Simulated Binary Crossover for Continuous Search Space (1995) Agrawal
-- etal.
simulatedBinaryCrossover :: Double -> CrossoverOp Double
-- | Select a random point in two genomes, and swap them beyond this point.
-- Apply with probability p.
onePointCrossover :: Double -> CrossoverOp a
-- | Select two random points in two genomes, and swap everything in
-- between. Apply with probability p.
twoPointCrossover :: Double -> CrossoverOp a
-- | Swap individual bits of two genomes with probability p.
uniformCrossover :: Double -> CrossoverOp a
-- | Don't crossover.
noCrossover :: CrossoverOp a
-- | Crossover all available parents. Parents are not repeated.
doCrossovers :: [Genome a] -> CrossoverOp a -> Rand [Genome a]
-- | Produce exactly n offsprings by repeatedly running the
-- crossover operator between randomly selected parents
-- (possibly repeated).
doNCrossovers :: Int -> [Genome a] -> CrossoverOp a -> Rand [Genome a]
-- | For every variable in the genome with probability p replace
-- its value v with v + sigma*N(0,1), where
-- N(0,1) is a normally distributed random variable with mean
-- equal 0 and variance equal 1. With probability (1 - p)^n,
-- where n is the number of variables, the genome remains
-- unaffected.
gaussianMutate :: Double -> Double -> MutationOp Double
module Moo.GeneticAlgorithm.Constraints
type ConstraintFunction a b = Genome a -> b
-- | Define constraints using .<., .<=., .>.,
-- .>=., and .==. operators, with a
-- ConstraintFunction on the left hand side.
--
-- For double inequality constraints use pairs of .<,
-- <. and .<=, <=. respectively, with a
-- ConstraintFunction in the middle.
--
-- Examples:
--
--
-- function .>=. lowerBound
-- lowerBound .<= function <=. upperBound
--
data Constraint a b
-- | Returns True if a genome represents a feasible
-- solution, i.e. satisfies all constraints.
isFeasible :: (GenomeState gt a, Real b) => [Constraint a b] -> gt -> Bool
(.<.) :: Real b => ConstraintFunction a b -> b -> Constraint a b
(.<=.) :: Real b => ConstraintFunction a b -> b -> Constraint a b
(.>.) :: Real b => ConstraintFunction a b -> b -> Constraint a b
(.>=.) :: Real b => ConstraintFunction a b -> b -> Constraint a b
(.==.) :: Real b => ConstraintFunction a b -> b -> Constraint a b
data LeftHandSideInequality a b
(.<) :: Real b => b -> ConstraintFunction a b -> LeftHandSideInequality a b
(.<=) :: Real b => b -> ConstraintFunction a b -> LeftHandSideInequality a b
(<.) :: Real b => LeftHandSideInequality a b -> b -> Constraint a b
(<=.) :: Real b => LeftHandSideInequality a b -> b -> Constraint a b
-- | Generate n feasible random genomes with individual genome
-- elements bounded by ranges.
getConstrainedGenomes :: (Random a, Ord a, Real b) => [Constraint a b] -> Int -> [(a, a)] -> Rand [Genome a]
-- | Generate n feasible random binary genomes.
getConstrainedBinaryGenomes :: Real b => [Constraint Bool b] -> Int -> Int -> Rand [Genome Bool]
-- | Kill all infeasible solutions after every step of the genetic
-- algorithm.
--
-- “Death penalty is very popular within the evolution strategies
-- community, but it is limited to problems in which the feasible search
-- space is convex and constitutes a reasonably large portion of the
-- whole search space,” -- (Coello 1999).
--
-- Coello, C. A. C., & Carlos, A. (1999). A survey of constraint
-- handling techniques used with evolutionary algorithms. Lania-RI-99-04,
-- Laboratorio Nacional de Informática Avanzada.
withDeathPenalty :: (Monad m, Real b) => [Constraint a b] -> StepGA m a -> StepGA m a
-- | Kill all infeasible solutions once after the last step of the genetic
-- algorithm. See also withDeathPenalty.
withFinalDeathPenalty :: (Monad m, Real b) => [Constraint a b] -> StepGA m a -> StepGA m a
-- | Modify objective function in such a way that 1) any feasible solution
-- is preferred to any infeasible solution, 2) among two feasible
-- solutions the one having better objective function value is preferred,
-- 3) among two infeasible solution the one having smaller constraint
-- violation is preferred.
--
-- Reference: Deb, K. (2000). An efficient constraint handling method for
-- genetic algorithms. Computer methods in applied mechanics and
-- engineering, 186(2), 311-338.
withConstraints :: (Real b, Real c) => [Constraint a b] -> ([Constraint a b] -> Genome a -> c) -> ProblemType -> SelectionOp a -> SelectionOp a
-- | A simple estimate of the degree of (in)feasibility.
--
-- Count the number of constraint violations. Return 0 if the
-- solution is feasible.
numberOfViolations :: Real b => [Constraint a b] -> Genome a -> Int
-- | An estimate of the degree of (in)feasibility.
--
-- Given f_j is the excess of j-th constraint function
-- value, return sum |f_j|^beta. For strict inequality
-- constraints, return sum (|f_j|^beta + eta). Return
-- 0.0 if the solution is feasible.
degreeOfViolation :: Double -> Double -> [Constraint a Double] -> Genome a -> Double
module Moo.GeneticAlgorithm.Multiobjective
type SingleObjectiveProblem fn = (ProblemType, fn)
type MultiObjectiveProblem fn = [SingleObjectiveProblem fn]
-- | An individual with all objective functions evaluated.
type MultiPhenotype a = (Genome a, [Objective])
-- | Calculate multiple objective per every genome in the population.
evalAllObjectives :: forall fn gt a. (ObjectiveFunction fn a, GenomeState gt a) => MultiObjectiveProblem fn -> [gt] -> [MultiPhenotype a]
takeObjectiveValues :: MultiPhenotype a -> [Objective]
-- | A single step of the NSGA-II algorithm (Non-Dominated Sorting Genetic
-- Algorithm for Multi-Objective Optimization).
--
-- The next population is selected from a common pool of parents and
-- their children minimizing the non-domination rank and maximizing the
-- crowding distance within the same rank. The first generation of
-- children is produced without taking crowding into account. Every
-- solution is assigned a single objective value which is its sequence
-- number after sorting with the crowded comparison operator. The smaller
-- value corresponds to solutions which are not worse the one with the
-- bigger value. Use evalAllObjectives to restore individual
-- objective values.
--
-- Reference: Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M.
-- T. (2002). A fast and elitist multiobjective genetic algorithm:
-- NSGA-II. Evolutionary Computation, IEEE Transactions on, 6(2),
-- 182-197.
--
-- Deb et al. used a binary tournament selection, base on crowded
-- comparison operator. To achieve the same effect, use
-- stepNSGA2bt (or stepNSGA2 with tournamentSelect
-- Minimizing 2 n, where n is the size of the
-- population).
stepNSGA2 :: forall fn a. ObjectiveFunction fn a => MultiObjectiveProblem fn -> SelectionOp a -> CrossoverOp a -> MutationOp a -> StepGA Rand a
-- | A single step of NSGA-II algorithm with binary tournament selection.
-- See also stepNSGA2.
stepNSGA2bt :: forall fn a. ObjectiveFunction fn a => MultiObjectiveProblem fn -> CrossoverOp a -> MutationOp a -> StepGA Rand a
-- | A single step of the constrained NSGA-II algorithm, which uses a
-- constraint-domination rule:
--
-- “A solution i is said to constrain-dominate a solution
-- j, if any of the following is true: 1) Solution i is
-- feasible and j is not. 2) Solutions i and j
-- are both infeasible but solution i has a smaller overall
-- constraint violation. 3) Solutions i and j are
-- feasible, and solution i dominates solution j.”
--
-- Reference: (Deb, 2002).
stepConstrainedNSGA2 :: forall fn a b c. (ObjectiveFunction fn a, Real b, Real c) => [Constraint a b] -> ([Constraint a b] -> Genome a -> c) -> MultiObjectiveProblem fn -> SelectionOp a -> CrossoverOp a -> MutationOp a -> StepGA Rand a
-- | A single step of the constrained NSGA-II algorithm with binary
-- tournament selection. See also stepConstrainedNSGA2.
stepConstrainedNSGA2bt :: forall fn a b c. (ObjectiveFunction fn a, Real b, Real c) => [Constraint a b] -> ([Constraint a b] -> Genome a -> c) -> MultiObjectiveProblem fn -> CrossoverOp a -> MutationOp a -> StepGA Rand a
-- | Calculate the hypervolume indicator using WFG algorithm.
--
-- Reference: While, L., Bradstreet, L., & Barone, L. (2012). A fast
-- way of calculating exact hypervolumes. Evolutionary Computation, IEEE
-- Transactions on, 16(1), 86-95.
hypervolume :: forall fn a. ObjectiveFunction fn a => MultiObjectiveProblem fn -> [Objective] -> [MultiPhenotype a] -> Double
-- | Binary genetic algorithms. Candidates solutions are represented as
-- bit-strings.
--
-- Choose Gray code if sudden changes to the variable value after a point
-- mutation are undesirable, choose binary code otherwise. In Gray code
-- two successive variable values differ in only one bit, it may help to
-- prevent premature convergence.
--
-- To apply binary genetic algorithms to real-valued problems, the real
-- variable may be discretized (encodeGrayReal and
-- decodeGrayReal). Another approach is to use continuous genetic
-- algorithms, see Moo.GeneticAlgorithm.Continuous.
--
-- To encode more than one variable, just concatenate their codes.
module Moo.GeneticAlgorithm.Binary
-- | Encode an integer number in the range (from, to) (inclusive)
-- as binary sequence of minimal length. Use of Gray code means that a
-- single point mutation leads to incremental change of the encoded
-- value.
encodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> b -> [Bool]
-- | Decode a binary sequence using Gray code to an integer in the range
-- (from, to) (inclusive). This is an inverse of
-- encodeGray. Actual value returned may be greater than
-- to.
decodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b
-- | Encode an integer number in the range (from, to) (inclusive)
-- as a binary sequence of minimal length. Use of binary encoding means
-- that a single point mutation may lead to sudden big change of the
-- encoded value.
encodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> b -> [Bool]
-- | Decode a binary sequence to an integer in the range (from,
-- to) (inclusive). This is an inverse of encodeBinary.
-- Actual value returned may be greater than to.
decodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b
-- | Encode a real number in the range (from, to) (inclusive) with
-- n equally spaced discrete values in binary Gray code.
encodeGrayReal :: RealFrac a => (a, a) -> Int -> a -> [Bool]
-- | Decode a binary sequence using Gray code to a real value in the range
-- (from, to), assuming it was discretized with n
-- equally spaced values (see encodeGrayReal).
decodeGrayReal :: RealFrac a => (a, a) -> Int -> [Bool] -> a
-- | How many bits are needed to represent a range of integer numbers
-- (from, to) (inclusive).
bitsNeeded :: (Integral a, Integral b) => (a, a) -> b
-- | Split a list into pieces of size n. This may be useful to
-- split the genome into distinct equally sized “genes” which encode
-- distinct properties of the solution.
splitEvery :: Int -> [a] -> [[a]]
-- | Generate n random binary genomes of length len.
-- Return a list of genomes.
getRandomBinaryGenomes :: Int -> Int -> Rand [Genome Bool]
-- | Objective-proportionate (roulette wheel) selection: select n
-- random items with each item's chance of being selected is proportional
-- to its objective function (fitness). Objective function should be
-- non-negative.
rouletteSelect :: Int -> SelectionOp a
-- | Stochastic universal sampling (SUS) is a selection technique similar
-- to roulette wheel selection. It gives weaker members a fair chance to
-- be selected, which is proportinal to their fitness. Objective function
-- should be non-negative.
stochasticUniversalSampling :: Int -> SelectionOp a
-- | Performs tournament selection among size individuals and
-- returns the winner. Repeat n times.
tournamentSelect :: ProblemType -> Int -> Int -> SelectionOp a
-- | Apply given scaling or other transform to population before selection.
withPopulationTransform :: (Population a -> Population a) -> SelectionOp a -> SelectionOp a
-- | Transform objective function values before seletion.
withScale :: (Objective -> Objective) -> SelectionOp a -> SelectionOp a
-- | Replace objective function values in the population with their ranks.
-- For a population of size n, a genome with the best value of
-- objective function has rank n' <= n, and a genome with the
-- worst value of objective function gets rank 1.
--
-- rankScale may be useful to avoid domination of few
-- super-genomes in rouletteSelect or to apply
-- rouletteSelect when an objective function is not necessarily
-- positive.
rankScale :: ProblemType -> Population a -> Population a
-- | A popular niching method proposed by D. Goldberg and J. Richardson in
-- 1987. The shared fitness of the individual is inversely protoptional
-- to its niche count. The method expects the objective function to be
-- non-negative.
--
-- An extension for minimization problems is implemented by making the
-- fitnes proportional to its niche count (rather than inversely
-- proportional).
--
-- Reference: Chen, J. H., Goldberg, D. E., Ho, S. Y., & Sastry, K.
-- (2002, July). Fitness inheritance in multiobjective optimization. In
-- Proceedings of the Genetic and Evolutionary Computation Conference
-- (pp. 319-326). Morgan Kaufmann Publishers Inc..
withFitnessSharing :: (Phenotype a -> Phenotype a -> Double) -> Double -> Double -> ProblemType -> SelectionOp a -> SelectionOp a
-- | Hamming distance between x and y is the number of
-- coordinates for which x_i and y_i are different.
--
-- Reference: Hamming, Richard W. (1950), “Error detecting and error
-- correcting codes”, Bell System Technical Journal 29 (2): 147–160, MR
-- 0035935.
hammingDistance :: (Eq a, Num i) => [a] -> [a] -> i
-- | Reorders a list of individual solutions, by putting the best in the
-- head of the list.
bestFirst :: ProblemType -> Population a -> Population a
-- | Select a random point in two genomes, and swap them beyond this point.
-- Apply with probability p.
onePointCrossover :: Double -> CrossoverOp a
-- | Select two random points in two genomes, and swap everything in
-- between. Apply with probability p.
twoPointCrossover :: Double -> CrossoverOp a
-- | Swap individual bits of two genomes with probability p.
uniformCrossover :: Double -> CrossoverOp a
-- | Don't crossover.
noCrossover :: CrossoverOp a
-- | Crossover all available parents. Parents are not repeated.
doCrossovers :: [Genome a] -> CrossoverOp a -> Rand [Genome a]
-- | Produce exactly n offsprings by repeatedly running the
-- crossover operator between randomly selected parents
-- (possibly repeated).
doNCrossovers :: Int -> [Genome a] -> CrossoverOp a -> Rand [Genome a]
-- | Flips a random bit along the length of the genome with probability
-- p. With probability (1 - p) the genome remains
-- unaffected.
pointMutate :: Double -> MutationOp Bool
-- | Flip 1s and 0s with different probabilities. This
-- may help to control the relative frequencies of 1s and
-- 0s in the genome.
asymmetricMutate :: Double -> Double -> MutationOp Bool
-- | Flip m bits on average, keeping the relative frequency of
-- 0s and 1s in the genome constant.
constFrequencyMutate :: Real a => a -> MutationOp Bool
-- | A library for custom genetic algorithms.
--
--
-- -----------
-- Quick Start
-- -----------
--
--
-- Import
--
--
--
-- Genetic algorithms are used to find good solutions to optimization and
-- search problems. They mimic the process of natural evolution and
-- selection.
--
-- A genetic algorithm deals with a population of candidate
-- solutions. Each candidate solution is represented with a
-- Genome. On every iteration the best genomes are selected
-- (SelectionOp). The next generation is produced through
-- crossover (recombination of the parents, CrossoverOp)
-- and mutation (a random change in the genome, MutationOp)
-- of the selected genomes. This process of selection -- crossover --
-- mutation is repeated until a good solution appears or all hope is
-- lost.
--
-- Genetic algorithms are often defined in terms of minimizing a cost
-- function or maximizing fitness. This library refers to observed
-- performance of a genome as Objective, which can be minimized as
-- well as maximized.
--
--
-- --------------------------------
-- How to write a genetic algorithm
-- --------------------------------
--
--
--
-- - Provide an encoding and decoding functions to convert from model
-- variables to genomes and back. See How to choose encoding
-- below.
-- - Write a custom objective function. Its type should be an instance
-- of ObjectiveFunction a. Functions of type Genome a
-- -> Objective are commonly used.
-- - Optionally write custom selection (SelectionOp), crossover
-- (CrossoverOp) and mutation (MutationOp) operators or
-- just use some standard operators provided by this library. Operators
-- specific to binary or continuous algorithms are provided by
-- Moo.GeneticAlgorithm.Binary and
-- Moo.GeneticAlgorithm.Continuous modules respectively.
-- - Use nextGeneration or nextSteadyState to create a
-- single step of the algorithm, control the iterative process with
-- loop, loopWithLog, or loopIO.
-- - Write a function to generate an initial population; for random
-- uniform initialization use getRandomGenomes or
-- getRandomBinaryGenomes.
--
--
-- Library functions which need access to random number generator work in
-- Rand monad. You may use a high-level wrapper runGA (or
-- runIO if you used loopIO), which takes care of creating
-- a new random number generator and running the entire algorithm.
--
-- To solve constrained optimization problems, modify initialization and
-- selection operators (see Moo.GeneticAlgorithm.Constraints).
--
-- To solve multi-objective optimization problems, use NSGA-II algorithm
-- (see Moo.GeneticAlgorithm.Multiobjective).
--
--
-- ----------------------
-- How to choose encoding
-- ----------------------
--
--
--
-- - For problems with discrete search space, binary (or Gray) encoding
-- of the bit-string is usually used. A bit-string is represented as a
-- list of Bool values ([Bool]). To build a binary
-- genetic algorithm, import Moo.GeneticAlgorithm.Binary.
-- - For problems with continuous search space, it is possible to use a
-- vector of real variables as a genome. Such a genome is represented as
-- a list of Double or Float values. Special crossover
-- and mutation operators should be used. To build a continuous genetic
-- algorithm, import Moo.GeneticAlgorithm.Continuous.
--
--
--
-- --------
-- Examples
-- --------
--
--
-- Minimizing Beale's function:
--
--
-- import Moo.GeneticAlgorithm.Continuous
--
--
-- beale :: [Double] -> Double
-- beale [x, y] = (1.5 - x + x*y)**2 + (2.25 - x + x*y*y)**2 + (2.625 - x + x*y*y*y)**2
--
--
-- popsize = 101
-- elitesize = 1
-- tolerance = 1e-6
--
--
-- selection = tournamentSelect Minimizing 2 (popsize - elitesize)
-- crossover = unimodalCrossoverRP
-- mutation = gaussianMutate 0.25 0.1
-- step = nextGeneration Minimizing beale selection elitesize crossover mutation
-- stop = IfObjective (\values -> (minimum values) < tolerance)
-- initialize = getRandomGenomes popsize [(-4.5, 4.5), (-4.5, 4.5)]
--
--
-- main = do
-- population <- runGA initialize (loop stop step)
-- print (head . bestFirst Minimizing $ population)
--
--
-- See examples/ folder of the source distribution for more
-- examples.
module Moo.GeneticAlgorithm