moo: Genetic algorithm library

[ ai, algorithms, bsd3, library, optimisation, optimization ] [ Propose Tags ]

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, and tournament; with optional niching 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.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 1.0, 1.2
Dependencies array, base (>=4 && <5), gray-code (>=0.2.1), mersenne-random-pure64, monad-mersenne-random, mtl (>=2), random (>=0.1), random-shuffle (>=0.0.2), time [details]
License BSD-3-Clause
Author Sergey Astanin <s.astanin@gmail.com>
Maintainer Sergey Astanin <s.astanin@gmail.com>
Category AI, Algorithms, Optimisation, Optimization
Home page http://www.github.com/astanin/moo/
Source repo head: git clone git://github.com/astanin/moo.git
Uploaded by SergeyAstanin at 2013-05-21T16:34:03Z
Distributions
Reverse Dependencies 2 direct, 0 indirect [details]
Downloads 13673 total (20 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for moo-1.0

[back to package description]

Moo

 ------------------------------------------------
< Moo. Breeding Genetic Algorithms with Haskell. >
 ------------------------------------------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Features

|                       | Binary GA            | Continuous GA            |
|-----------------------+----------------------+--------------------------|
|Encoding               | binary bit-string    | sequence of real values  |
|                       | Gray bit-string      |                          |
|-----------------------+----------------------+--------------------------|
|Initialization         |            random uniform                       |
|                       |            constrained random uniform           |
|                       |            arbitrary custom                     |
|-----------------------+-------------------------------------------------|
|Objective              |            minimization and maximiation         |
|                       |            optional scaling                     |
|                       |            optional ranking                     |
|                       |            optional niching (fitness sharing)   |
|-----------------------+-------------------------------------------------|
|Selection              |            roulette                             |
|                       |            stochastic universal sampling        |
|                       |            tournament                           |
|                       |            optional elitism                     |
|                       |            optionally constrained               |
|                       |            custom non-adaptive ^                |
|-----------------------+-------------------------------------------------|
|Crossover              |            one-point                            |
|                       |            two-point                            |
|                       |            uniform                              |
|                       |            custom non-adaptive ^                |
|                       +----------------------+--------------------------|
|                       |                      | BLX-α (blend)            |
|                       |                      | SBX (simulated binary)   |
|                       |                      | UNDX (unimodal normally  |
|                       |                      | distributed)             |
|-----------------------+----------------------+--------------------------|
|Mutation               | point                | Gaussian                 |
|                       | asymmetric           |                          |
|                       | constant frequency   |                          |
|                       +----------------------+--------------------------|
|                       |            custom non-adaptive ^                |
|-----------------------+-------------------------------------------------|
|Replacement            |            generational with elitism            |
|                       |            steady state                         |
|-----------------------+-------------------------------------------------|
|Stop                   |            number of generations                |
|condition              |            values of objective function         |
|                       |            stall of objective function          |
|                       |            custom or interactive (`loopIO`)     |
|                       |            time limit (`loopIO`)                |
|                       |            compound conditions (`And`, `Or`)    |
|-----------------------+-------------------------------------------------|
|Logging                |            pure periodic (any monoid)           |
|                       |            periodic with `IO`                   |
|-----------------------+-------------------------------------------------|
|Constrainted           |            constrained initialization           |
|optimization           |            constrained selection                |
|                       |            death penalty                        |
|-----------------------+-------------------------------------------------|
|Multiobjective         |            NSGA-II                              |
|optimization           |            constrained NSGA-II                  |

^ non-adaptive: any function which doesn't depend on generation number

There are other possible encodings which are possible to represent with list-like genomes (type Genome a = [a]):

  • permutation encodings (a being an integer, or other Enum type)
  • tree encodings (a being a subtree type)
  • hybrid encodings (a being a sum type)

Contributing

There are many ways you can help developing the library:

  • I'm not a native speaker of English. If you are, please proof-read and correct the comments and the documentation.

  • Moo is designed with possibility of implementing custom genetic operators in mind. If you write new operators (SelectionOp, CrossoverOp, MutationOp) or replacement strategies (StepGA), consider contributing them to the library. In the comments please give a reference to an academic work which introduces or studies the method. Explain when or why it should be used. Provide tests and examples if possible.

  • Implementing some methods (like adaptive genetic algorithms) will require to change some library types. Please discuss your approach first.

  • Contribute examples. Solutions of known problems with known optima and interesting properties. Try to avoid examples which are too contrived.

An example

Minimizing Beale's function (optimal value f(3, 0.5) = 0):

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)

For more examples, see examples/ folder.