Prototyping a Small Genetic Algorithms Library inHaskell (2019)

This article discusses the creation of a small genetic algorithms library in Haskell, using recursion schemes and monadic computations. The author assumes familiarity with genetic algorithms, recursion schemes, and related terminology. The full source code can be found in a provided repository. The article begins by outlining the context in which the genetic algorithm should operate, including the need for a configuration containing various parameters such as mutation and selection methods, a random number generator for generating and mutating individuals, and logging of intermediate data.

The RWS monad is suggested as the ideal candidate to meet these requirements. The article then covers the use of the PureMT random number generator, referencing a configuration with ask, and logging data with tell. A hall of fame is introduced as a min-heap to keep track of the most-fit individuals; a snapshot data type is also defined to track the best individuals over time.

The configuration parameters that will be referenced in the GAContext computations are defined in a new data type. The genetic algorithm evolves candidate solutions over a fixed number of generations, with each generation determined by a step function. This step function takes the current snapshot, configuration, and performs selection, crossover, mutation, and updating the hall of fame.

The monadic hylomorphism is used to generate and mutate children in a single pass. The anamorphic half of the transformation generates new individuals using the user-defined crossover function, while the catamorphic half folds the mutated children into a vector of the same type. The hall of fame is updated with better-fit individuals from the latest population, and a fixed initial population is created using the defined data structures.