-- 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 <a>Rand</a> monad and <a>PureMT</a>
--   random number generator.
module Moo.GeneticAlgorithm.Random

-- | Yield a new randomly selected value of type <tt>a</tt> in the range
--   <tt>(lo, hi)</tt>. See <a>randomR</a> for details.
getRandomR :: Random a => (a, a) -> Rand a

-- | Yield a new randomly selected value of type <tt>a</tt>. See
--   <a>random</a> 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 <tt>sampleSize</tt> numbers in the range from <tt>0</tt> to
--   <tt>(populationSize-1)</tt>. The function works best when
--   <tt>sampleSize</tt> is much smaller than <tt>populationSize</tt>.
randomSampleIndices :: Int -> Int -> Rand [Int]

-- | Randomly reorder the list.
shuffle :: [a] -> Rand [a]

-- | Modify value with probability <tt>p</tt>. Return the unchanged value
--   with probability <tt>1-p</tt>.
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
--   <a>liftRand</a>.)
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.
--   
--   <ul>
--   <li><pre><a>evalRand</a> m s = fst (<a>runRand</a> m s)</pre></li>
--   </ul>
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
--   <a>runRand</a>.)
liftRand :: (g -> (a, g)) -> Rand g a
type Rand = Rand PureMT

-- | The class of types for which random values can be generated. Most
--   instances of <a>Random</a> will produce values that are uniformly
--   distributed on the full range, but for those types without a
--   well-defined "full range" some sensible default subrange will be
--   selected.
--   
--   <a>Random</a> exists primarily for backwards compatibility with
--   version 1.1 of this library. In new code, use the better specified
--   <a>Uniform</a> and <a>UniformRange</a> instead.
class Random a

-- | <a>PureMT</a>, 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 <a>Objective</a> value.
type Phenotype a = (Genome a, Objective)

-- | An entire population of observed <a>Phenotype</a>s.
type Population a = [Phenotype a]

-- | <a>takeGenome</a> 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
--   <a>ObjectiveFunction</a> class. It may be called a cost function for
--   minimization problems, or a fitness function for maximization
--   problems.
--   
--   Some genetic algorithm operators, like <tt>rouletteSelect</tt>,
--   require the <a>Objective</a> 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 <i>parent</i> genomes and returns some
--   <i>children</i> 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
--   <tt>nextGeneration</tt>.
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 <tt>True</tt>.
data Cond a

-- | stop after <tt>n</tt> generations
Generations :: Int -> Cond a

-- | stop when objective values satisfy the <tt>predicate</tt>
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 <tt>Nothing</tt>)
[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:
--   
--   <pre>
--   [ start ]
--       |
--       v
--   (genomes) --&gt; [calculate objective] --&gt; (evaluated genomes) --&gt; [ stop ]
--       ^  ^                                       |
--       |  |                                       |
--       |  `-----------.                           |
--       |               \                          v
--   [ mutate ]        (elite) &lt;-------------- [ select ]
--       ^                                          |
--       |                                          |
--       |                                          |
--       |                                          v
--   (genomes) &lt;----- [ crossover ] &lt;-------- (evaluted genomes)
--   </pre>
--   
--   PopulationState can represent either <tt>genomes</tt> or <tt>evaluated
--   genomed</tt>.
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.Classes.Eq Moo.GeneticAlgorithm.Types.ProblemType
instance GHC.Show.Show Moo.GeneticAlgorithm.Types.ProblemType
instance GHC.Show.Show a => GHC.Show.Show (Moo.GeneticAlgorithm.Types.StepResult a)
instance (a1 GHC.Types.~ a2) => Moo.GeneticAlgorithm.Types.ObjectiveFunction (Moo.GeneticAlgorithm.Types.Genome a1 -> Moo.GeneticAlgorithm.Types.Objective) a2
instance (a1 GHC.Types.~ a2) => Moo.GeneticAlgorithm.Types.ObjectiveFunction ([Moo.GeneticAlgorithm.Types.Genome a1] -> [Moo.GeneticAlgorithm.Types.Objective]) a2
instance (a1 GHC.Types.~ a2) => Moo.GeneticAlgorithm.Types.ObjectiveFunction ([Moo.GeneticAlgorithm.Types.Genome a1] -> [(Moo.GeneticAlgorithm.Types.Genome a1, Moo.GeneticAlgorithm.Types.Objective)]) a2
instance (a1 GHC.Types.~ a2) => Moo.GeneticAlgorithm.Types.GenomeState (Moo.GeneticAlgorithm.Types.Genome a1) a2
instance (a1 GHC.Types.~ 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 <a>Rand</a> 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 <a>IO</a> monad.
runIO :: Rand [Genome a] -> (IORef PureMT -> [Genome a] -> IO (Population a)) -> IO (Population a)

-- | Construct a single step of the genetic algorithm.
--   
--   See <a>Moo.GeneticAlgorithm.Binary</a> and
--   <a>Moo.GeneticAlgorithm.Continuous</a> 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 <tt>n</tt> worst solutions are replaced with newly
--   born children.
--   
--   See <a>Moo.GeneticAlgorithm.Binary</a> and
--   <a>Moo.GeneticAlgorithm.Continuous</a> 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 <a>nextGeneration</a> and <a>nextSteadyState</a>.
makeStoppable :: (ObjectiveFunction objectivefn a, Monad m) => objectivefn -> (Population a -> m (Population a)) -> StepGA m a

-- | Run strict iterations of the genetic algorithm defined by
--   <tt>step</tt>. Return the result of the last step. Usually only the
--   first two arguments are given, and the result is passed to
--   <a>runGA</a>.
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
--   <a>runGA</a>.
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 <a>runIO</a>.
loopIO :: [IOHook a] -> Cond a -> StepGA Rand a -> IORef PureMT -> [Genome a] -> IO (Population a)

-- | Iterations stop when the condition evaluates as <tt>True</tt>.
data Cond a

-- | stop after <tt>n</tt> generations
Generations :: Int -> Cond a

-- | stop when objective values satisfy the <tt>predicate</tt>
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 <tt>Nothing</tt>)
[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 <tt>n</tt>th 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 <tt>n</tt>th 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 <tt>t</tt> 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 <tt>n</tt> uniform random genomes with individual genome
--   elements bounded by <tt>ranges</tt>. This corresponds to random
--   uniform sampling of points (genomes) from a hyperrectangle with a
--   bounding box <tt>ranges</tt>.
getRandomGenomes :: (Random a, Ord a) => Int -> [(a, a)] -> Rand [Genome a]

-- | Generate at most <tt>popsize</tt> genomes uniformly distributed in
--   <tt>ranges</tt>.
uniformGenomes :: Int -> [(Double, Double)] -> [Genome Double]

-- | Objective-proportionate (roulette wheel) selection: select <tt>n</tt>
--   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 <tt>size</tt> individuals and
--   returns the winner. Repeat <tt>n</tt> 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 <tt>n</tt>, a genome with the best value of
--   objective function has rank <tt>n' &lt;= n</tt>, and a genome with the
--   worst value of objective function gets rank <tt>1</tt>.
--   
--   <a>rankScale</a> may be useful to avoid domination of few
--   super-genomes in <a>rouletteSelect</a> or to apply
--   <a>rouletteSelect</a> 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., &amp; 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: <tt>sum |x_i - y-i|</tt>.
distance1 :: Num a => [a] -> [a] -> a

-- | 2-norm distance: <tt>(sum (x_i - y_i)^2)^(1/2)</tt>.
distance2 :: Floating a => [a] -> [a] -> a

-- | Infinity norm distance: <tt>max |x_i - y_i|</tt>.
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 <tt>x</tt> and <tt>y</tt> 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 <tt>L = min (x,y) - alpha *
--   d</tt>, <tt>U = max (x,y) + alpha * d</tt>, and <tt>d = abs (x -
--   y)</tt>. <tt>alpha</tt> 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 <tt>sigma_xi = 0.5</tt>, <tt>sigma_eta =
--   0.35/sqrt(n)</tt>, where <tt>n</tt> 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 <tt>sigma_xi^2 = 0.25</tt>. 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 <a>unimodalCrossover</a> 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 <tt>n &gt; 0</tt>, 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 <tt>p</tt>.
onePointCrossover :: Double -> CrossoverOp a

-- | Select two random points in two genomes, and swap everything in
--   between. Apply with probability <tt>p</tt>.
twoPointCrossover :: Double -> CrossoverOp a

-- | Swap individual bits of two genomes with probability <tt>p</tt>.
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 <tt>n</tt> offsprings by repeatedly running the
--   <tt>crossover</tt> operator between randomly selected parents
--   (possibly repeated).
doNCrossovers :: Int -> [Genome a] -> CrossoverOp a -> Rand [Genome a]

-- | For every variable in the genome with probability <tt>p</tt> replace
--   its value <tt>v</tt> with <tt>v + sigma*N(0,1)</tt>, where
--   <tt>N(0,1)</tt> is a normally distributed random variable with mean
--   equal 0 and variance equal 1. With probability <tt>(1 - p)^n</tt>,
--   where <tt>n</tt> 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 <a>.&lt;.</a>, <a>.&lt;=.</a>, <a>.&gt;.</a>,
--   <a>.&gt;=.</a>, and <a>.==.</a> operators, with a
--   <a>ConstraintFunction</a> on the left hand side.
--   
--   For double inequality constraints use pairs of <a>.&lt;</a>,
--   <a>&lt;.</a> and <a>.&lt;=</a>, <a>&lt;=.</a> respectively, with a
--   <a>ConstraintFunction</a> in the middle.
--   
--   Examples:
--   
--   <pre>
--   function .&gt;=. lowerBound
--   lowerBound .&lt;= function &lt;=. upperBound
--   </pre>
data Constraint a b

-- | Returns <tt>True</tt> if a <tt>genome</tt> represents a feasible
--   solution, i.e. satisfies all <tt>constraints</tt>.
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 <tt>n</tt> feasible random genomes with individual genome
--   elements bounded by <tt>ranges</tt>.
getConstrainedGenomes :: (Random a, Ord a, Real b) => [Constraint a b] -> Int -> [(a, a)] -> Rand [Genome a]

-- | Generate <tt>n</tt> 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., &amp; 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 <a>withDeathPenalty</a>.
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 <tt>0</tt> if the
--   solution is feasible.
numberOfViolations :: Real b => [Constraint a b] -> Genome a -> Int

-- | An estimate of the degree of (in)feasibility.
--   
--   Given <tt>f_j</tt> is the excess of <tt>j</tt>-th constraint function
--   value, return <tt>sum |f_j|^beta</tt>. For strict inequality
--   constraints, return <tt>sum (|f_j|^beta + eta)</tt>. Return
--   <tt>0.0</tt> 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 <a>evalAllObjectives</a> to restore individual
--   objective values.
--   
--   Reference: Deb, K., Pratap, A., Agarwal, S., &amp; 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
--   <a>stepNSGA2bt</a> (or <a>stepNSGA2</a> with <a>tournamentSelect</a>
--   <tt>Minimizing 2 n</tt>, where <tt>n</tt> 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 <a>stepNSGA2</a>.
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 <tt>i</tt> is said to constrain-dominate a solution
--   <tt>j</tt>, if any of the following is true: 1) Solution <tt>i</tt> is
--   feasible and <tt>j</tt> is not. 2) Solutions <tt>i</tt> and <tt>j</tt>
--   are both infeasible but solution <tt>i</tt> has a smaller overall
--   constraint violation. 3) Solutions <tt>i</tt> and <tt>j</tt> are
--   feasible, and solution <tt>i</tt> dominates solution <tt>j</tt>.”
--   
--   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 <a>stepConstrainedNSGA2</a>.
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., &amp; 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 (<a>encodeGrayReal</a> and
--   <a>decodeGrayReal</a>). Another approach is to use continuous genetic
--   algorithms, see <a>Moo.GeneticAlgorithm.Continuous</a>.
--   
--   To encode more than one variable, just concatenate their codes.
module Moo.GeneticAlgorithm.Binary

-- | Encode an integer number in the range <tt>(from, to)</tt> (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
--   <tt>(from, to)</tt> (inclusive). This is an inverse of
--   <a>encodeGray</a>. Actual value returned may be greater than
--   <tt>to</tt>.
decodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b

-- | Encode an integer number in the range <tt>(from, to)</tt> (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 <tt>(from,
--   to)</tt> (inclusive). This is an inverse of <a>encodeBinary</a>.
--   Actual value returned may be greater than <tt>to</tt>.
decodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b

-- | Encode a real number in the range <tt>(from, to)</tt> (inclusive) with
--   <tt>n</tt> 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
--   <tt>(from, to)</tt>, assuming it was discretized with <tt>n</tt>
--   equally spaced values (see <a>encodeGrayReal</a>).
decodeGrayReal :: RealFrac a => (a, a) -> Int -> [Bool] -> a

-- | How many bits are needed to represent a range of integer numbers
--   <tt>(from, to)</tt> (inclusive).
bitsNeeded :: (Integral a, Integral b) => (a, a) -> b

-- | Split a list into pieces of size <tt>n</tt>. 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 <tt>n</tt> random binary genomes of length <tt>len</tt>.
--   Return a list of genomes.
getRandomBinaryGenomes :: Int -> Int -> Rand [Genome Bool]

-- | Objective-proportionate (roulette wheel) selection: select <tt>n</tt>
--   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 <tt>size</tt> individuals and
--   returns the winner. Repeat <tt>n</tt> 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 <tt>n</tt>, a genome with the best value of
--   objective function has rank <tt>n' &lt;= n</tt>, and a genome with the
--   worst value of objective function gets rank <tt>1</tt>.
--   
--   <a>rankScale</a> may be useful to avoid domination of few
--   super-genomes in <a>rouletteSelect</a> or to apply
--   <a>rouletteSelect</a> 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., &amp; 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 <tt>x</tt> and <tt>y</tt> is the number of
--   coordinates for which <tt>x_i</tt> and <tt>y_i</tt> 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 <tt>p</tt>.
onePointCrossover :: Double -> CrossoverOp a

-- | Select two random points in two genomes, and swap everything in
--   between. Apply with probability <tt>p</tt>.
twoPointCrossover :: Double -> CrossoverOp a

-- | Swap individual bits of two genomes with probability <tt>p</tt>.
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 <tt>n</tt> offsprings by repeatedly running the
--   <tt>crossover</tt> 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
--   <tt>p</tt>. With probability <tt>(1 - p)</tt> the genome remains
--   unaffected.
pointMutate :: Double -> MutationOp Bool

-- | Flip <tt>1</tt>s and <tt>0</tt>s with different probabilities. This
--   may help to control the relative frequencies of <tt>1</tt>s and
--   <tt>0</tt>s in the genome.
asymmetricMutate :: Double -> Double -> MutationOp Bool

-- | Flip <tt>m</tt> bits on average, keeping the relative frequency of
--   <tt>0</tt>s and <tt>1</tt>s in the genome constant.
constFrequencyMutate :: Real a => a -> MutationOp Bool


-- | A library for custom genetic algorithms.
--   
--   <pre>
--   -----------
--   Quick Start
--   -----------
--   </pre>
--   
--   Import
--   
--   <ul>
--   <li>either <a>Moo.GeneticAlgorithm.Binary</a></li>
--   <li>or <a>Moo.GeneticAlgorithm.Continuous</a></li>
--   </ul>
--   
--   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 <i>population</i> of candidate
--   solutions. Each candidate solution is represented with a
--   <a>Genome</a>. On every iteration the best genomes are <i>selected</i>
--   (<a>SelectionOp</a>). The next generation is produced through
--   <i>crossover</i> (recombination of the parents, <a>CrossoverOp</a>)
--   and <i>mutation</i> (a random change in the genome, <a>MutationOp</a>)
--   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 <a>Objective</a>, which can be minimized as
--   well as maximized.
--   
--   <pre>
--   --------------------------------
--   How to write a genetic algorithm
--   --------------------------------
--   </pre>
--   
--   <ol>
--   <li>Provide an encoding and decoding functions to convert from model
--   variables to genomes and back. See <i>How to choose encoding</i>
--   below.</li>
--   <li>Write a custom objective function. Its type should be an instance
--   of <a>ObjectiveFunction</a> <tt>a</tt>. Functions of type <tt>Genome a
--   -&gt; Objective</tt> are commonly used.</li>
--   <li>Optionally write custom selection (<a>SelectionOp</a>), crossover
--   (<a>CrossoverOp</a>) and mutation (<a>MutationOp</a>) operators or
--   just use some standard operators provided by this library. Operators
--   specific to binary or continuous algorithms are provided by
--   <a>Moo.GeneticAlgorithm.Binary</a> and
--   <a>Moo.GeneticAlgorithm.Continuous</a> modules respectively.</li>
--   <li>Use <a>nextGeneration</a> or <a>nextSteadyState</a> to create a
--   single step of the algorithm, control the iterative process with
--   <a>loop</a>, <a>loopWithLog</a>, or <a>loopIO</a>.</li>
--   <li>Write a function to generate an initial population; for random
--   uniform initialization use <a>getRandomGenomes</a> or
--   <a>getRandomBinaryGenomes</a>.</li>
--   </ol>
--   
--   Library functions which need access to random number generator work in
--   <a>Rand</a> monad. You may use a high-level wrapper <a>runGA</a> (or
--   <a>runIO</a> if you used <a>loopIO</a>), 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 <a>Moo.GeneticAlgorithm.Constraints</a>).
--   
--   To solve multi-objective optimization problems, use NSGA-II algorithm
--   (see <a>Moo.GeneticAlgorithm.Multiobjective</a>).
--   
--   <pre>
--   ----------------------
--   How to choose encoding
--   ----------------------
--   </pre>
--   
--   <ul>
--   <li>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 <tt>Bool</tt> values (<tt>[Bool]</tt>). To build a binary
--   genetic algorithm, import <a>Moo.GeneticAlgorithm.Binary</a>.</li>
--   <li>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 <tt>Double</tt> or <tt>Float</tt> values. Special crossover
--   and mutation operators should be used. To build a continuous genetic
--   algorithm, import <a>Moo.GeneticAlgorithm.Continuous</a>.</li>
--   </ul>
--   
--   <pre>
--   --------
--   Examples
--   --------
--   </pre>
--   
--   Minimizing Beale's function:
--   
--   <pre>
--   import Moo.GeneticAlgorithm.Continuous
--   
--   
--   beale :: [Double] -&gt; 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 -&gt; (minimum values) &lt; tolerance)
--   initialize = getRandomGenomes popsize [(-4.5, 4.5), (-4.5, 4.5)]
--   
--   
--   main = do
--     population &lt;- runGA initialize (loop stop step)
--     print (head . bestFirst Minimizing $ population)
--   </pre>
--   
--   See <tt>examples/</tt> folder of the source distribution for more
--   examples.
module Moo.GeneticAlgorithm
