Subject: Re: 615 final project -- more specifics

From: Geoffrey Fox <[email-masked]>
Date: Fri, 21 Apr 2000 11:36:41 -0400

Genetic algorithms have a (possible) feature that is not present in other cases
Namely the natural parallel version is a different algorithm from the sequential version
So I suggest you look at parallel speed up from 2 points of view
a) "Communication/load balancing overhead". This should be small
b) Algorithm effectiveness -- does 4 environmennts work 4 times faster than 1?

Your approach is excellent as 

Quant Marjorie V 2dLt AFRL/IFSB wrote:
> 
> Professor Fox,
> 
> Steve and I have a solid start on the final project.  We wanted to discuss
> our approach with you to make sure it was still a viable option.  We had
> told you that we wanted to model an ecological system.  We were not sure
> what specific system we were going to model.  We decided on modeling sexual
> vs. asexual reproduction.
> 
> We have a working genetic algorithm to model these systems.  Our next step
> will be to parallelize the algorithm and run the program on 4 separate nodes
> to represent 4 separate environments.  We will use message passing every ten
> generations to represent migration of five individuals to a parallel (and
> random) environment.  The final outcome of this algorithm will be to show
> which environment and what type of reproduction are best suited for each
> other.  Attached is an explanation of our motivation for this project.
> 
> We are not sure of how much parallelism and complexity of the message
> passing you would like to see in the final project.  We are using a parallel
> system to divide the workload and save time while comparing 4+ environments,
> and we are passing five individuals every ten generations between each of
> the nodes.  Should we try to implements more MP?
> 
> 
> Marjorie Quant
> Steven M. Alexander
> 
>   ------------------------------------------------------------------------------------------------------------------------
>                        Name: explanation.html
>    explanation.html    Type: Hypertext Markup Language (text/html)
>                    Encoding: quoted-printable

---

From: Saleh Elmohamed <[email-masked]>
Date: Fri, 21 Apr 2000 12:16:59 -0400 (EDT)

Hi,

Here are few comments form an algorithmic point of view...

GA is a parallel random search with centralized control. This centralized
part is the selection schedule with needs the average fitness of the
population. This gives you a highly synchronized algorithm which can be
difficult to implement efficiently on parallel computers... To mend this,
a distributed selection scheme is used and achieved as follows: each
individual does the selection by itself, then looks for a partner in
its neighborhood only. The set of neighborhoods defines a spatial
population structure.
The other thing to take care of in order to have a parallel version is
that each individual is active and not acted on. It may improve its
fitness during its lifetime by performing a local search... So the
parallel version will look something like this:

 1. define a genetic representation of the problem.
 2. create an initial population and its population structure.
 3. each individual does local hill climbing.
 4. each individual selects a partner for mating in its neighborhood.
 5. an offspring is created using genetic operators like recombination and
    mutation.
 6. the offspring does local hill climbing. it replaces the parent if it
    is better than some criterion (acceptance).
 7. if not done go to step 4.

notice that each individual may use a different local hill-climbing
method, and this is important for problems where the efficiency of a
particular hill-climbing method depends on the problem instance. Also
notice that the info exchange within the whole population is sort of a
diffusion process because neighborhoods of individuals overlap. All of the
decisions are made by the individuals themselves, so the algorithm is 
totally distributed without any central control... This models the natural
evolution process which organizes itself.