[math] Genetic Algorithms

[Phil Steitz <ph...@gmail.com>]

I would like to start work on a GA framework.  This has been on the
WishList for some time and I now have a TLS type problem that I am
working on that is enough motivation for me personally to get things
rolling.  Here are some rough ideas on what I have in mind.  As
always, feedback / suggestions / patches appreciated.

0) Scope - a framework for implementing genetic algorithms, as
described in e.g. [1], [2].
1) Usage / what the framework provides - user classes should implement
minimally encoding and objective functions.  Stock mutation, crossover
and selection functions operating on binary encodings should be
provided by the framework, as well as execution of the algorithm, but
user classes should be able to plug in custom encoding, mutation,
crossover, and selection.  Objective and other functions should also
be allowed to have parameters, which the framework will somehow gather
and pass in to them.
2) Other - the framework should not require that populations be stored
in memory and it should support parallelization of population
processing functions
3) Package - o.a.c.math.genetic  (I am open to putting this inside
optimization, but think flatter might be better here).
4) Structure straw man:
Chromosomes - Chromosome interface includes mutate(),
crossover(Chromosome) and fitness().  AbstractBinaryChromosome
includes stock implementations of mutate and crossover for binary
encodings.
Populations - Population interface provides a Chromosome Iterator,
select(long), add(Chromosome), delete(Chromosome).  Abstract classes
provide Roulette, Tournament, other select implementations for
Populations backed / not backed by in memory collections and I/O /
storage management.
GeneticAlgorithm - implements GA (following "canonical algorithm" as
described in [2]) given initial Population and configured sampling
rate and stopping criteria (maximum iterations, convergence criteria).
 Population and Chromosome classes determine the heuristics.  Should
(eventually at least) support parallel execution by worker threads of
breeding operations.

This may be naive and I may find that out as I start playing with real
code.  As I said, feedback / patches welcome. One thing I don't have a
clean idea for is how to make optional parameters available to all
methods mentioned above.

Phil

[1] http://en.wikipedia.org/wiki/Genetic_algorithm
[2] http://samizdat.mines.edu/ga_tutorial/ga_tutorial.ps

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org

Re: [math] Genetic Algorithms

[Phil Steitz <ph...@gmail.com>]

On Tue, Apr 1, 2008 at 3:41 PM, Ramiro Pereira de Magalhaes
<rp...@yahoo.com.br> wrote:
> As my CS graduation I wrote a GA framework to help me solve the problem I
> was proposing. It is implemented, may need some improvements with a less
> naive and optimized code, but it works fine. I wrote less interfaces but I
> really liked Brent's initial interface set and seems to me the idea will
> work fine as well. I'd like to make some contributions and help you somehow.
>

You are certainly most welcome to contribute.  I also like Brett's
interfaces and would like to see if we can add some implementation and
test code to build out a small framwork along the lines that we have
been discussing on this thread.

The best way to get started is to post any questions / comments that
you have here and attach code contributions (including test cases) to
JIRA tickets.  Please do not hesitate to ask if you need help getting
started with subversion, Maven, etc.  There are some instructions
here:
http://commons.apache.org/math/developers.html.  Thanks in advance!

Phil

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org

Re: [math] Genetic Algorithms

[Ramiro Pereira de Magalhaes <rp...@yahoo.com.br>]

As my CS graduation I wrote a GA framework to help me solve the problem 
I was proposing. It is implemented, may need some improvements with a 
less naive and optimized code, but it works fine. I wrote less 
interfaces but I really liked Brent's initial interface set and seems to 
me the idea will work fine as well. I'd like to make some contributions 
and help you somehow.

RPM



Phil Steitz wrote:
> I would like to start work on a GA framework.  This has been on the
> WishList for some time and I now have a TLS type problem that I am
> working on that is enough motivation for me personally to get things
> rolling.  Here are some rough ideas on what I have in mind.  As
> always, feedback / suggestions / patches appreciated.
>
> 0) Scope - a framework for implementing genetic algorithms, as
> described in e.g. [1], [2].
> 1) Usage / what the framework provides - user classes should implement
> minimally encoding and objective functions.  Stock mutation, crossover
> and selection functions operating on binary encodings should be
> provided by the framework, as well as execution of the algorithm, but
> user classes should be able to plug in custom encoding, mutation,
> crossover, and selection.  Objective and other functions should also
> be allowed to have parameters, which the framework will somehow gather
> and pass in to them.
> 2) Other - the framework should not require that populations be stored
> in memory and it should support parallelization of population
> processing functions
> 3) Package - o.a.c.math.genetic  (I am open to putting this inside
> optimization, but think flatter might be better here).
> 4) Structure straw man:
> Chromosomes - Chromosome interface includes mutate(),
> crossover(Chromosome) and fitness().  AbstractBinaryChromosome
> includes stock implementations of mutate and crossover for binary
> encodings.
> Populations - Population interface provides a Chromosome Iterator,
> select(long), add(Chromosome), delete(Chromosome).  Abstract classes
> provide Roulette, Tournament, other select implementations for
> Populations backed / not backed by in memory collections and I/O /
> storage management.
> GeneticAlgorithm - implements GA (following "canonical algorithm" as
> described in [2]) given initial Population and configured sampling
> rate and stopping criteria (maximum iterations, convergence criteria).
>  Population and Chromosome classes determine the heuristics.  Should
> (eventually at least) support parallel execution by worker threads of
> breeding operations.
>
> This may be naive and I may find that out as I start playing with real
> code.  As I said, feedback / patches welcome. One thing I don't have a
> clean idea for is how to make optional parameters available to all
> methods mentioned above.
>
> Phil
>
> [1] http://en.wikipedia.org/wiki/Genetic_algorithm
> [2] http://samizdat.mines.edu/ga_tutorial/ga_tutorial.ps
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org