[Haskell-cafe] ANNOUNCE: GA-1.0, a library for working with genetic algorithms

[Thomas DuBuisson]

This is neat - thanks for putting in the time and effort (and
releasing the work to Hackage).  A few questions:

* What GA-nerdy things does this do under the hood (I haven't looked
  at the source)?  It looks like it's a GA framework almost more than
  the actual algorithm itself.  I see crossover and mutation can be
  defined by the user and understand there are limitations to what the
  GA package can do (seeing as it is so polymorphic), but certainly it
  could provide alternate fitness measures (adjusted, normalized,
  standard), over-selection, elitism, automatically defined functions
  (sometimes called encapsulation), and optimization (I think this is
  referred to as "editing" by Koza).

* Have you considered using Binary or Serialize to make the
  checkpointing? (I assume checkpointing is using the Show and Read
  instances right now)

* Have you considered alternate random sources (Mersenne)?  Perhaps
  I'm being silly as most GAs are computationally dominated by the
  fitness measurement.

* Is there a plan for parallel computations?  Beyond what I can do
with scorePop?

* What does it mean if a score returns 'Nothing'?

On a related note, I've recently put some work into using the Typeable
and Dynamic modules to build a GA system in which the primitives could
hold heterogeneous types.  I'll describe it below incase you are 1)
interested in doing it yourself, but actually completeing it (unlike
me) or 2) are already doing it so I won't be tempted to revisit the
work and duplicate effort.  From the look of your package, this would
be just an special instance of your Entity class.

The basic idea was to allow the use of arbitrary Haskell types to be
lifted into a generic genetic algorithm:

{- BEGIN CODE -}
evolveSolution = do
  let funcs = [mkPrim (:), mkPrim lookup, mkPrim delete, mkPrim
insert] ++ map mkPrim [0..100] ++ map mkPrim [(+),(*),(-)]
      allFuncs = funcs ++ primsForContainersPackage -- my package
should have eventually provided such collections
      fitness f = f 503 == 0
      gaConf = mkGA funcs (mkPrim fitness) defaultConfig
  in evolve gaConf
{- END CODE -}

In the system each individual is an operator and a list of arguments,
each contained in their own Dynamic type.  All individuals include 1)
a mapping from type to sub-trees that are of that type and 2) a
mapping of types to functions that will construct the same individual
(that is: Map typ (typ -> Individual)).  The union of the domain of
these to mappings show what, if any, opportunities for crossover exist
between any two individuals.

The global configuration maintains all the primitives needed to
generate new individuals, which means sub-trees can also be generated
to allow mutation.

The main two issues that made me stop (read: I didn't recognize these
as the core issue till I'd already hacked around without thinking
about why what I'm doing wasn't quite right) were:

1) I didn't have a good way to dynamically safely coerce one type,
ty1, into another type, ty2.  For example, when given "t_1 -> t_2 ->
... -> t_n -> r" and needed "b_1 -> b_2 -> ... -> b_m -> r" where m <
n and there was a injective mapping between the b, t type variables I
still had bugs in the actual coercion.

A more concrete example of this point: given "Int -> Float -> Float",
I wanted to coerce it into a function of type "Float -> Int -> Float"
or "Float -> Float" or "Int -> Float".  Usually my solution worked,
but I think a bug lingered (needs testing, which I don't have time
for now).

2) Generation of individuals in "highly heterogenious" configurations
was basically non-terminating without special effort.  I was going to
make a routine to compute the minimum depth given any particular
primitive, then removed any primitive from consideration if the
minimum depth put me over the maximum depth for the individual.

So a bit long winded, but that was the effort in a nutshell.  If
nothing else I hope it was entertaining.  I'm sure it's doable but I
haven't the time of focus to do it properly, and won't for a while.

Cheers,
Thomas


On Thu, Sep 29, 2011 at 12:45 PM, Kenneth Hoste <kenneth.hoste at gmail.com> wrote:
> Hello,
>
> I'm proud to announce the v1.0 release of GA [1], my library for working with genetic algorithms in Haskell.
> Source repo is available on github. [2]
>
> This is a major version bump compared to the previous v0.2 release, because the library is pretty mature now in my view.
>
> Major features:
>
> * flexible user-friendly API for working with genetic algorithms
> * Entity type class to let user define entity definition, scoring, etc.
> * abstraction over monad, resulting in a powerful yet simple interface
> * support for scoring entire population at once
> * support for checkpointing each generation, and restoring from last checkpoint
> * convergence detection, as defined by user
> * also available: random searching, user-defined progress output
> * illustrative toy examples included
>
> I'm happy to take any questions or suggestions that you might have.
>
> [1] http://hackage.haskell.org/package/GA
> [2] https://github.com/boegel/GA
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>