[concurrency-interest] Parallel Genetic Algorithms on Multi-core Processors

Doug Lea dl at cs.oswego.edu
Mon Jan 21 09:09:07 EST 2008


> Hi everyone,
>
> I'm  building an AI engine for games, simulations, animations, etc.  One
> of the features I would like to have in my AI engine is a genetic
> algorithm library that would allow the AI programmer to build simple and
> parallel genetic algorithms (PGAs). But most PGAs are done with
> multiprocessor systems and not multicore systems. If you read some of the
> papers on PGAs, the researcher are using multi-processor systems and the
> number of populations (population per processor) can be massive.
>
> Is it practical to allow the AI developer to build PGAs on one machine
> using a multi-core processor?
>

The differences between shared caches (multicore) versus
separate ones (multiprocessor) versus mixtures (MPs of multicores)
do show up in some applications but not others, so it is hard to
give a good answer. There's some research showing that some of
of these effects can be reduced by using different task scheduling
algorithms across the different cases (which BTW may show up
someday in forkjoin framework). But even so, there seem to
be many (perhaps most) applications where it doesn't make
a huge difference -- caches are neither overly polluted
nor overly contended to make enough difference to address.
I don't know if the kinds of parallel genetic algorithms
you are looking at fall into this category or not.

Relatedly, Bill Scherer and I put together a PGA demo
using the updated Java6 version of Exchanger. See
TSPExchangerTest in
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/loops/
(We haven't put together a lightweight FJ version
of Exchanger yet, but it is a thought...)

-Doug




More information about the Concurrency-interest mailing list