Re: [Haskell-cafe] ANNOUNCE: GA-1.0, a library for working with genetic algorithms
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
[Haskell-cafe] ANNOUNCE: GA-1.0, a library for working with genetic algorithms
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: GA-1.0, a library for working with genetic algorithms
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.ho...@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]
