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

[Kenneth Hoste]

Hi Thomas,

On 30 Sep 2011, at 03:42, Thomas DuBuisson wrote:

> This is neat - thanks for putting in the time and effort (and
> releasing the work to Hackage).  

My pleasure. :)
Happy to share the stuff I come up with during my daily commutes. ;-)

> 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).

It's more of a framework, you're right.

To be honest, I'm no GA-nerd. I've used genetic algorithms for some of 
the work I did for my PhD thesis, but I always applied GAs in a pragmatic
way, without bothering too much about whether or not I was using all the
right stuff as dictated by GA theory.

For now, the only way to use my GA library is to implement entity definition, 
scoring, crossover and mutation yourself. The current implementation only
does binary tournament selection, no other selection operators are available.

To be frank, I have no idea what those alternate fitness measures could be
used for, nor what encapsulation or over-selection is exactly, etc.
It does allow for elitism afaik, because you can specify how many of the best entities
so far (the archive) should be kept and combined with population entities 
(correct me if I'm wrong).

If you think some of these things could be useful to others, maybe we can try
and make that fit into what I currently have. Contact me if you're interested.

For me personally, I think the current version of the GA library will allow me to 
use it for my future GA-supported projects (compiler optimization like ACOVEA,
and genetic programming (evolving actual Haskell programs)).

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

I'm using Show/Read now, you're right, but using something like Binary or 
Serialize is a very good suggestion, thanks!

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

I haven't. What's so special about Mersenne? Is it just faster in generating random
values, or does it also have a different distribution?
For now, I don't really care about the specifics of my source of random values, 
but maybe I should...

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

Not really. I have little experience with making computations parallel in a 
portable way. I don't want to force users of the GA lib to always use their
full set of computing resources.
Currently, the only way to evaluate entities in parallel is to implement it yourself
through scorePop. 
I'm open for suggestions how to enable parallel evaluation of entities at the request
of the user.

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

It indicates that scoring of an entity failed. 
When you're evaluating entities in the IO Monad for example, that's very useful.

I should make that more clear in the documentation.

> 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.

I'm not sure I fully grasp what you were trying to do, but I can say I wasn't planning
on working on something like this. :)

However, it seems to have some overlap with some work I've been doing to try and
come up with a (again, pragmatic) way of evolving true Haskell programs, i.e.
implementing a genetic programming framework on top of my GA library.

I have something that kind of works to generate a list of (partial) functions that
try and transform a value of a given type in a value of another type according to
some goal (for example, to determine the median value of a list of values).
Currently, it's *really* messy (so I'm keeping it to myself for now ;)), but I hope I can
get some answers on how to work with function types as 'values' and other related
stuff. Maybe you're the man to ask, since you seem to have some experience in
that direction, and have interesting in genetic algorithms. :)

K.

> 
> 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
>>