AI/Genetic programming/GPLib

GPLib - a generic library for genetic programming

Available as a darcs repository at: http://catenova.org/~awagner/GPLib

A wish-list for features:

1. Type system for GP trees.
   1. Tree generators should produce only well typed trees.

      Owner: Paul Berg.

   2. Monotype trees, as they exist in the current incarnation of the program should pose no issues as they are a trivial subset of polytypic trees.

      1. Owner: Paul Berg... to ensure this remains true.

   3. Multiple Type systems supported and selectable.
      1. HM typing

         Owner: Paul Berg.

      2. HM + infinite types

         Owned: Paul Berg

         Dependency: 2.A.a

      3. System F, Fc, Fw?

         May not be possible. Needs research.

      4. Subtyping.
      5. Existential Typing.

         May not be useful or possible. Needs Research.

2) Enhanced Evaluator.

 A) Support for statistics and actions based on those.
    a) Number of node applications, with bailout if
       user defined threshold exceeded.
       - Owned: Paul Berg
       - Dependency: 3.B
 B) Support for different function types.  Currently we
    only support nodes with a list of subnodes, returning
    a monotypic result.
    a) Application nodes.  Arity-2 nodes that apply functions.
       - Owner: Paul Berg
    b) Literal Int and Real nodes.
       - Owner: Paul Berg
    c) Char nodes?
    d) List nodes?
       - Can be done with no native support using 1.C.a + 2.B.a
 C) Selectable normal/applicative order.
    a) Dependency: 2.B.a

3) Support for pluggable configuration.

 A) Pluggable Fitness.
    a) Owner: Andrew Wagner
 B) Pluggable threshold values.
    a) Owner: Andrew Wagner
 c) Pluggable Crossover/Mutation Operators.

4) Support for Island Models.

 A) Hierarchical Competition model.
 B) Linear and Ring islands.
 C) Higher Dimensional (grid, cube island layouts)
 D) Cluster of Islands (no ordering).

5) Parallelization.

 A) Multi-computer evolution between islands.
 B) Parallelization on multi-core systems (STM?, ForkIO?)
 C) Multi-computer intra-island evaluation.

6) Cabalized Library distribution.

7) Multi-Parameter fitness (Pereto Front).

 A) Dependency: 3.A

8) Library of useful primitives.

 A) Primitive Nodes and Node generators, eg. random literal int
    generator.
    a) Should probably be split according to which type system(s)
       they can be imported under.
 B) Primitive crossover and mutation operators.
    a) Should probably be split according to which type system(s)
       they can be imported under.

9) Optimizer.

 A) Should be able to take a GP Tree and pre-evaluate everything
    possible, eg. (+ 1 2) should be simplified to a single node, 3
    if such a node is allowed by the primitives.
 B) Should be able to perform full tree reconstruction
    optimizations.  eg.:
      Given the node primitives:
        S = \x y z -> ((x z) (y z))
        K = \x y -> x
        B = \f g x -> (f (g x))
      Then:
        S (K x) y Simplifies to: B x y
 C) Optimizations should be available as mutation operators
    that optimize sub-trees.  These should not run on every
    tree by default as they can cause a premature loss of
    good genetic material.

10) Other genetic representations:

  A) Shared sub-tree directed graphs
  B) Linear representation
     a) Static length
     b) Variable length
  C) Mixed representation.
     a) Forest of trees (ADF's and ADM's)
     b) Mixed tree + ansulary linear data.
  D) Generalized graphs.
  E) Stacks.

11) Output to other language.

  A) Haskell when possible.
  B) Scheme for infinite types.

12) REPL

  A) Scheme-like input/output of trees.
     a) Owner: Paul Berg
  B) Type checking
     a) Owner: Paul Berg
  C) Evaluation
     a) Owner: Paul Berg
  D) Save/Load
  E) GP Parameter/Plug-in tweaking
  F) Run/Pause/Stop of GP runs.

13) GUI

  A) Statistics and Graph presentation
     a) Owner: Andrew Wagner
  B) Run/Pause/Stop of GP Runs
     a) Owner: Andrew Wagner
  C) Parameter/Plug-in tweaking.
  D) Embedded REPL.

14) Configuration file.

15) Saving/Loading of runs in progress at checkpoints.

16) Selectable RNG?

  A) Might not be wanted or needed, but the current one
     should be evaluated to see if it meets our needs at least.

17) First release to Hackage.

  A) We should create a list of features that should be complete
     for this to happen.

18) Problem Library.

  A) Sante fe Ant.
  B) Tartarus.
  C) Inverted Pendulum
  D) Traveling Salesman
  E) Chess
  F) Checkers

19) Tests.

  A) Basic library of sample runs for different problems.
  B) Quickcheck tests.