| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
Moo.GeneticAlgorithm.Binary
Contents
Description
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.
Synopsis
- module Moo.GeneticAlgorithm.Types
- encodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> b -> [Bool]
- decodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b
- encodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> b -> [Bool]
- decodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b
- encodeGrayReal :: RealFrac a => (a, a) -> Int -> a -> [Bool]
- decodeGrayReal :: RealFrac a => (a, a) -> Int -> [Bool] -> a
- bitsNeeded :: (Integral a, Integral b) => (a, a) -> b
- splitEvery :: Int -> [a] -> [[a]]
- getRandomBinaryGenomes :: Int -> Int -> Rand [Genome Bool]
- rouletteSelect :: Int -> SelectionOp a
- stochasticUniversalSampling :: Int -> SelectionOp a
- tournamentSelect :: ProblemType -> Int -> Int -> SelectionOp a
- withPopulationTransform :: (Population a -> Population a) -> SelectionOp a -> SelectionOp a
- withScale :: (Objective -> Objective) -> SelectionOp a -> SelectionOp a
- rankScale :: ProblemType -> Population a -> Population a
- withFitnessSharing :: (Phenotype a -> Phenotype a -> Double) -> Double -> Double -> ProblemType -> SelectionOp a -> SelectionOp a
- hammingDistance :: (Eq a, Num i) => [a] -> [a] -> i
- bestFirst :: ProblemType -> Population a -> Population a
- onePointCrossover :: Double -> CrossoverOp a
- twoPointCrossover :: Double -> CrossoverOp a
- uniformCrossover :: Double -> CrossoverOp a
- noCrossover :: CrossoverOp a
- doCrossovers :: [Genome a] -> CrossoverOp a -> Rand [Genome a]
- doNCrossovers :: Int -> [Genome a] -> CrossoverOp a -> Rand [Genome a]
- pointMutate :: Double -> MutationOp Bool
- asymmetricMutate :: Double -> Double -> MutationOp Bool
- constFrequencyMutate :: Real a => a -> MutationOp Bool
- module Moo.GeneticAlgorithm.Random
- module Moo.GeneticAlgorithm.Random
- module Moo.GeneticAlgorithm.Run
Types
module Moo.GeneticAlgorithm.Types
Encoding
encodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> b -> [Bool] Source #
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.
decodeGray :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b Source #
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.
encodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> b -> [Bool] Source #
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.
decodeBinary :: (FiniteBits b, Bits b, Integral b) => (b, b) -> [Bool] -> b Source #
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.
encodeGrayReal :: RealFrac a => (a, a) -> Int -> a -> [Bool] Source #
Encode a real number in the range (from, to) (inclusive)
with n equally spaced discrete values in binary Gray code.
decodeGrayReal :: RealFrac a => (a, a) -> Int -> [Bool] -> a Source #
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).
bitsNeeded :: (Integral a, Integral b) => (a, a) -> b Source #
How many bits are needed to represent a range of integer numbers
(from, to) (inclusive).
splitEvery :: Int -> [a] -> [[a]] Source #
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.
Initialization
getRandomBinaryGenomes Source #
Generate n random binary genomes of length len.
Return a list of genomes.
Selection
rouletteSelect :: Int -> SelectionOp a Source #
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.
stochasticUniversalSampling Source #
Arguments
| :: Int | how many genomes to select |
| -> 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.
Arguments
| :: ProblemType | type of the optimization problem |
| -> Int | size of the tournament group |
| -> Int | how many tournaments to run |
| -> SelectionOp a |
Performs tournament selection among size individuals and
returns the winner. Repeat n times.
Scaling and niching
withPopulationTransform :: (Population a -> Population a) -> SelectionOp a -> SelectionOp a Source #
Apply given scaling or other transform to population before selection.
withScale :: (Objective -> Objective) -> SelectionOp a -> SelectionOp a Source #
Transform objective function values before seletion.
rankScale :: ProblemType -> Population a -> Population a Source #
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.
Arguments
| :: (Phenotype a -> Phenotype a -> Double) | distance function |
| -> Double | niche radius |
| -> Double | niche compression exponent |
| -> ProblemType | type of the optimization problem |
| -> SelectionOp a -> SelectionOp 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..
hammingDistance :: (Eq a, Num i) => [a] -> [a] -> i Source #
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.
Sorting
bestFirst :: ProblemType -> Population a -> Population a Source #
Reorders a list of individual solutions, by putting the best in the head of the list.
Crossover
Discrete operators
onePointCrossover :: Double -> CrossoverOp a Source #
Select a random point in two genomes, and swap them beyond this point.
Apply with probability p.
twoPointCrossover :: Double -> CrossoverOp a Source #
Select two random points in two genomes, and swap everything in between.
Apply with probability p.
uniformCrossover :: Double -> CrossoverOp a Source #
Swap individual bits of two genomes with probability p.
noCrossover :: CrossoverOp a Source #
Don't crossover.
Application
doCrossovers :: [Genome a] -> CrossoverOp a -> Rand [Genome a] Source #
Crossover all available parents. Parents are not repeated.
Arguments
| :: Int |
|
| -> [Genome a] |
|
| -> CrossoverOp a |
|
| -> Rand [Genome a] |
Produce exactly n offsprings by repeatedly running the crossover
operator between randomly selected parents (possibly repeated).
Mutation
pointMutate :: Double -> MutationOp Bool Source #
Flips a random bit along the length of the genome with probability p.
With probability (1 - p) the genome remains unaffected.
Arguments
| :: Double | probability of a |
| -> Double | probability of a |
| -> MutationOp Bool |
Flip 1s and 0s with different probabilities. This may help to control
the relative frequencies of 1s and 0s in the genome.
Arguments
| :: Real a | |
| => a | average number of bits to change |
| -> MutationOp Bool |
Flip m bits on average, keeping the relative frequency of 0s
and 1s in the genome constant.
Control
module Moo.GeneticAlgorithm.Random
module Moo.GeneticAlgorithm.Random
module Moo.GeneticAlgorithm.Run