From: ob00@ns1.cc.lehigh.edu (OLCAY BOZ)
Subject: Summary: parallel genetic algorithm (references)
Organization: Lehigh University
Date: Tue, 13 Oct 1992 00:35:57 GMT

Thanks a lot to all who replied to my request for references on PGA's.
All the replies were appreciated very much. I hope others who are interested
in the same subjects find these references helpfull.
====================================================================

Date: Mon, 5 Oct 92 10:11:56 EDT
From: Gregory T. Byrd <gbyrd@ncsc.org>
To: ob00@Lehigh.EDU (OLCAY BOZ)
Cc:
Subject: Re: References on Parallel Genetic Algorithms


I found a tech report from Univ. Rochester.

Anonymous ftp to cs.rochester.edu -- look in
/pub/papers/systems.

...Greg Byrd             North Carolina Supercomputing Center
   gbyrd@ncsc.org        P.O. Box 12889
   (919)248-1439         Research Triangle Park, NC  27709-2889




From: levine@antares.mcs.anl.gov (David Levine)
Date: Mon, 5 Oct 92 11:02:40 CDT
To: OB00@Lehigh.EDU
Subject: parallel genetic algorithms



Here is some *in-progress* text from what I hope will be the first chapter of
my PhD thesis on Parallel Genetic Algorithms for Set Partitioning Problems.
Please don't post, publish, or quote!  (at least until I get my degree!)

--dave


David Levine  levine@mcs.anl.gov  (708)-252-6735   Fax: (708)-252-5986
MCS 221 C-216    Argonne National Laboratory   Argonne, Illinois 60439


\section{ \bf{Parallel Genetic Algorithms} }

Parallel implementations of genetic algorithms are attractive for two reasons.
First, genetic algorithms are notoriously slow, and parallel computers offer
an opportunity to speed them up since most genetic algorithm steps can be
executed in parallel.  Also, parallel computers usually have large memories
which can accommodate the large populations necessary for solving large
problems.

Second, distributed subpopulations, with their {\em local} rules and
interactions, are a more realistic model of species in nature than a single
large population.  In traditional GAs the expected number of offspring depends
on a string's fitness relative to {\em all} other strings in the population.
This situation implies a global ranking that is unlike the way natural
selection works.  Moreover, it can be difficult to parallelize.  Furthermore,
by analogy with natural selection, a population is typically many independent
subpopulations that occasionally interact.  The asynchronous behavior of
parallel GAs allows different populations to evolve at different speeds.

Parallel genetic algorithms (PGAs) can be classified according to the
granularity of the distributed population, {\em coarse grain} vs. {\em
fine grain}, and the manner in which the GA operators are applied
\cite{JoSuGu90}.  In a coarse-grain PGA the population is divided into several
subpopulations, each of which runs a traditional GA independently and in
parallel on its own subpopulation.  Occasionally, strings are allowed to
migrate from one subpopulation to another.  In some implementations migrant
strings may move only to geographically nearby subpopulations rather than to
any arbitrary subpopulation.

In a fine-grain PGA a single population is divided up so that a single string
is assigned to each processor.  Processors select from, crossover with, and
replace only strings in their {\em neighborhood}.  Since neighborhoods
overlap, fit strings will migrate throughout the population.

Although it has not been typically applied, a simple way to parallelize the
traditional GA is to parallelize the main time-step loop that creates the next
generation from the previous one.  Most of the steps (crossover, mutation,
local search, and replacement) can be done in parallel.  The selection step,
however, requires a global sum that may be a parallel bottleneck.  Also, the
traditional GA tends towards premature convergence, an effect which PGAs, with
their independent neighborhoods and subpopulations, seem to be able to
partially mitigate.

\subsection{ \bf{Coarse-Grain Parallel Genetic Algorithms} }

In a Coarse-grain parallel genetic algorithm (CgPGA) multiple processors
each run the traditional GA on their own subpopulation.  Processors exchange
strings from their subpopulations with other processors.  Some important
choices in the CgPGA are which other processors a processor communicates with,
how often processors communicate, how many strings processors exchange with
each other, and what strategy is used for string exchange (e.g., making copies
of the most fit strings to exchange, or exchanging the best strings
themselves).

Tanese \cite{Ta87} applied a CgPGA using a 64-processor Ncube computer to the
optimization of Walsh-like functions.  Periodically, fit strings are selected
and sent to neighboring processors for possible inclusion in their future
generations.  Exchanges take place only among a processor's neighbors in the
hypercube.  These exchanges vary over time, taking place over a different
dimension of the hypercube each time.  Tanese found that the CgPGA was able to
determine the global maximum of the function about as often as the sequential
GA.  He reports near-linear speedup of the CgPGA over the traditional GA for
runs of 1,000 generations.  Tanese's main metric, the average of which
generation the global maximum was found on, seemed to prefer eight as the
optimal number of subpopulations.  Tanese also experimented with variable
mutation and crossover rates among the subpopulations.  Tanese found these
results were at least as good as earlier results.

In \cite{Ta89} Tanese experimented with the {\em partitioned} genetic
algorithm (a CgPGA with no migration between processors allowed).  A total
population size of 256 was partitioned into various power-of-two subpopulation
sizes.  In all cases the partitioned GA found a better ``best fitness value''
than the traditional GA, even with small subpopulations sizes such as eight or
four.  However, the average fitness of the population at the last generation
was consistently worse than that calculated with the traditional algorithm.

Experiments {\em with} migration found that a higher average fitness could be
obtained if many migrants were sent infrequently or if only a few migrants
were sent more frequently.  Each processor generated extra offspring during a
migration generation and selected migrants uniformly from among the
``overfull'' population.  Often the partitioned GA found fitter strings than
the CgPGA with migration.  Best results were achieved with a migration rate
such as 20\% of each subpopulation migrating every 20 iterations.

In \cite{StWhMa91} Starkweather, Whitley, and Mathias describe another CgPGA.
Each processor sends {\em copies} of its best strings to one of its neighbors,
which replaces its worst string with these.  A ring topology is used where, on
iteration one, $p_0$ sends to $p_1$, $p_1$ sends to $p_2$, etc.  On iteration
two, $p_0$ sends to $p_2$, $p_1$ sends to $p_3$, etc.  All sends are done in
parallel.  In their tests the total population size was fixed, and they
experimented with various size partitions of the total population among the
processors.  When no mutation was used, performance improved for two of the
four problems as the number of subpopulations was increased, but degraded on
the other two.  When adaptive mutation was used, with the mutation
probability increasing to some predefined maximum as the similarity of the two
parents increased, the runs were more successful and had good results relative
to the serial runs.  The more distributed the GA, the more often adaptive
mutation is invoked, since smaller subpopulations converge more rapidly than
larger ones.  Their experiments also indicate that migrating strings too
often, or not often enough, degrades performance.

Cohoon, Martin, and Richards \cite{CoMaRi91} applied the CgPGA to the
$K$-partition problem using a 16-processor hypercube.  Each processor had its
own subpopulation of 80 strings and fifty iterations were run between
migrations.  An interesting feature of their work is the random choice of
scaling coefficient for the penalty term of their fitness function
\begin{equation}
c(x) + \lambda p(x).
\end{equation}
Here $c(x)$ is a cost term associated with string $x$ and $p(x)$ is a penalty
term which is zero if $x$ is a feasible solution and nonzero with a magnitude
depending on the size of the infeasibility.  The scaling factor $\lambda$
influences how much weight infeasibilities play in evaluating a string's
fitness.  Two experiments were done.  One used $\lambda = 1$ for each
subpopulation.  In the other, each processor chose a value for $\lambda$
uniformly on the interval (0,1).  When the metric ``best observed fitness''
was used on any of the 15 runs, the runs with uniformly distributed $\lambda$
were consistently better than those with $\lambda$ fixed at 1 in each
processor.

Kroger, Schwenderling, and Vornberger \cite{KrScVo91} used a CgPGA on a
network of 32 transputers to solve the two-dimensional bin packing problem.
At ``irregular intervals'' a processor receives strings from neighboring
processors.  A ``parallel elitist strategy'' is used whereby, whenever a
processor improves upon the best string in its population, it sends a copy of
that string to all other processors in its neighborhood.  The best results
were found with a ``medium size'' neighborhood and a local population of ten
strings.

Pettey, Leuze, and Grefenstette \cite{PeLeGr87} ran a CgPGA on an Intel iPSC
hypercube.  Each generation each processor sent its best strings to each
neighbor and received its neighbor's best strings.  These were then inserted
into each processor's subpopulation by using a replacement scheme.
Subpopulation size was fixed at 50 strings; and 1, 2, 4, 8, and 16 processors
were used.  They believe their results indicate an increased likelihood of
premature convergence.  This work is at an extreme from most CgPGAs, since
strings are exchanged every generation and always with the same neighbors.
This fact might explain the apparent increased likelihood of premature
convergence.

\subsection{ \bf{Fine-Grain Parallel Genetic Algorithms} }

In a fine-grain parallel genetic algorithm (FgPGA) exactly one string is
assigned to each processor.  In the FgPGA the model is of one population
in which the strings have only local interactions and neighborhoods, as
opposed to global ones.  Choices to be made include neighborhood size,
processor connection topology, and string replacement scheme.

Muhlenbein \cite{Mu91} applied a FgPGA to both the traveling salesperson
problem and the graph partitioning problem.  Each string selects a mate from
within a small neighborhood of its own processor.  Within its neighborhood
each processor performs selection, crossover, and mutation without any central
control.  In addition, each string may attempt to improve itself by applying a
local search heuristic.

Muhlenbein aims to avoid premature convergence by allowing only slow
propagation of highly fit strings across the full population.  This is
dependent on the topology of the processor's neighborhood which he calls the
{\em population structure}.  By choosing a population structure that takes a
long time to propagate strings throughout the population, Muhlenbein claims to
avoid premature convergence.  The topology used was a two-dimensional circular
{\em ladder} with two strings per ``step''.  A neighborhood size of eight is
used by each string.  There is some overlap among neighborhoods, enabling fit
strings to propagate through the population.

In \cite{LaMu91} a FgPGA is applied to the graph partitioning problem.
Strings were mapped to a 64-processor transputer system.  Selection is done
independently by each string within a small neighborhood of the
two-dimensional population structure.  The parent string is replaced if the
offspring is at least as good as the worst string in the neighborhood.  A
small neighborhood size in conjunction with a large population size gave the
best results.

In \cite{Sc91} Gorges-Schleuter implemented a FgPGA on a 64-processor Parsytec
transputer system using a sparse graph as the population topology.  An elitist
strategy was used whereby offspring are accepted for the next generation only
if they are more fit than the local parent.  A string's fitness is defined
relative to other strings in its neighborhood, and neighborhoods may overlap.
The algorithm was applied to the TSP problem, using a population size of 64
and a neighborhood size of eight.  Results show that, with a small
neighborhood size, communication is negligible and linear speedup is achieved.

\subsection{ \bf{Other Parallel Genetic Algorithms } }

In addition to coarse- and fine-grain parallel genetic algorithms, parallel
computers can also be applied directly to speed the solution of the
traditional ``sequential'' GA.  Of the major steps of the traditional GA
(selection, crossover, mutation, replacement, and evaluation) all but the
evaluation step can be done in parallel (evaluation requires synchronization
in order to calculate a global sum).  In addition, if a local improvement
heuristic is used, that too can be done in parallel.  The implementation can
be done on a shared-memory machine by using loop-level parallelism, or on a
distributed-memory machine under the control of a ``control'' processor.

Fogarty and Huang \cite{FoHu91} used a transputer array for the parallel
evaluation of a population of 250 strings applied to a real-time control
problem.  For this problem, evaluating the fitness of a member of the
population takes a relatively long time.  A host processor ran the main GA
program and distributed strings for evaluation to the other transputer
processors for evaluation.  Maximum speedups in the range of 25--27 were
obtained on 40--72 processors.  The incremental improvement in speedup was
slightly sublinear up to about 16--20 processors, but then fell off quickly.

Liepens and Baluja \cite{LiBa91} used a parallel GA with a central processor
phase.  In parallel, 15 subpopulations of ten strings each run a GA on their
own subpopulations.  Next, during the central processor phase, the most fit
string from each subpopulation is gathered along with an additional 15
randomly generated strings.  Under the control of the central processor a
recombination phase of these 30 strings occurs.  The best string is then
injected into the populations of one-third of the processors.  Commenting
about parallelism, Liepens and Baluja believe that smaller subpopulations
remain more heterogeneous.



@article{ArFeStTe69,
  author = "J. Arabeyre and J. Fearnley and F. Steiger and W. Teather",
  Title = "The {A}irline {C}rew {S}cheduling {P}roblem: A {S}urvey",
  Journal = "Transportation Science",
  Year = "1969",
  Volume = "3",
  Number = "2",
  Pages ="140--163"
  }

@article{BaFi81,
  author = "E. Baker and M. Fisher",
  Title = "Computational {R}esults for {V}ery {L}arge {A}ir {C}rew {S}cheduling
{P}roblems",
  Journal = "OMEGA",
  Year = "1981",
  Volume = "9",
  Number = "6",
  Pages ="613--618"
  }

@article{BaPa76,
  author = "E. Balas and M. Padberg",
  Title = "Set {P}artitioning: {A} {S}urvey",
  Journal = "SIAM Review",
  Year = "1976",
  Volume = "18",
  Number = "4",
  Pages ="710--760"
  }

@article{BaHu90,
  author = "J. Barutt and T. Hull",
  Title = "Airline {C}rew {S}cheduling: Supercomputers and {A}lgorithms",
  Journal = "SIAM News",
  Year = "1990",
  Volume = "23",
  Number = "6"
  }

@techreport{BiGrLuMaSh91,
   author = "R. Bixby and J. Gregory and I. Lustig and R. Marsten and D. Shanno"
,
   title = "Very {L}arge-{S}cale {L}inear {P}rogramming: A {C}ase {S}tudy in
{C}ombining {I}nterior {P}oint and {S}implex {M}ethods",
   year = "1991",
   institution = "Rice University",
   number = "CRPC"
   }

@inproceedings{BrHuSp89,
  author = "D. Brown and C. Huntley and A. Spillane",
  editor = "J. Schaffer",
  title = "A {P}arallel {G}enetic {H}euristic for the {Q}uadratic {A}ssignment {
P}roblem",
  booktitle = "Proceedings of the Third International Conference on Genetic
Algorithms",
  year = "1989",
  publisher = "Morgan Kaufmann",
  Pages ="406--415"
  }


@article{Ch79,
  author = "V. Chvatal",
  Title = "A {G}reedy {H}euristic for the {S}et {C}overing {P}roblem",
  Journal = "OMEGA",
  Year = "1979",
  Volume = "4",
  Number = "3",
  Pages ="233--235"
  }

@book{Ch83,
  author = "V. Chvatal",
  title = "Linear Programming",
  publisher = "W. H. Freeman and Company",
  address = "New York",
  year = "1983"
  }

@article{Fi85,
  author = "M. Fischer",
  Title = "An {A}pplications {O}riented {G}uide to {L}agrangian {R}elaxation",
  Journal = "INTERFACES",
  Year = "1985",
  Volume = "15",
  Number = "2",
  Pages ="10--21"
  }

@article{FiKe90,
  author = "M. Fischer and P. Kedia",
  Title = "Optimal {S}olution of {S}et {C}overing/{P}artitioning {P}roblems
using {D}ual {H}euristics",
  Journal = "Management Science",
  Year = "1990",
  Volume = "36",
  Number = "6",
  Pages ="674--688"
  }

@article{Fl72,
  author = "M. Flynn",
  Title = "Some Computer Organizations and Their Effectiveness",
  Journal = "IEEE Transactions on Computers",
  Year = "1972",
  Volume = "21",
  Pages ="948--960"
  }

@book{GaNe72,
  author =  "R. Garfinkel and G. Nemhauser",
  title = "Integer Programming",
  publisher = "John Wiley and Sons Inc.",
  year = "1972"
  }

@book{Go89,
  author =  "D. Goldberg",
  title = "{G}enetic {A}lgorithms in Search, Optimization and Machine
Learning",
  publisher = "Addison-Wesley Publishing Company, Inc.",
  year = "1989"
  }

@techreport{Go,
   author = "D. Goldberg",
   title = "Sizing Populations for Serial and Parallel Genetic Algorithms",
   year = "XX",
   institution = "The University of Alabama",
   number = "Technical Report"
   }

@inproceedings{SuGu,
  author = "J. Suh and D. Gucht",
  title = "Incorporating Heuristic Information into Genetic Search",
  booktitle = "XX",
  year = "XX",
  publisher = "XXXX",
  pages = "100--107"
  }

@book{Ho75,
  author =  "J. Holland",
  title = "Adaption in Natural and Artificial Systems",
  publisher = "The University of Michigan Press",
  year = "1975"
  }

@inproceedings{JoGu,
  author =  "P. Jog and D. Gucht",
  title = "Parallelisation of probabilistic Sequential Search Algorithms",
  booktitle = "XX",
  year = "XX",
  publisher = "XXXX",
  pages = "170--176"
  }

@techreport{JoSuGu90,
   author = "P. Jog and J. Suh and D. Gucht",
   title = "{P}arallel {G}enetic {A}lgorithms {A}pplied to the {T}raveling
{S}alesman {P}roblem",
   year = "1990",
   institution = "Indiana University",
   number = "No. 314"
   }

@techreport{LiHiPaMo,
   author = "G. Liepins and M. Hilliard and M. Palmer and M. Morrow",
   title = "Greedy Genetics",
   year = "XXXX",
   institution = "Oak Ridge National Laboratory",
   number = "Oak Ridge National Laboratory Technical Report"
   }

@inbook{LiHiRiPa,
   author = "G. Liepins and M. Hilliard and J. Richardson and M. Palmer",
   editor = "D. Brown and C. White",
   title = "{G}enetic {A}lgorithms {A}pplications to {S}et {C}overing and
{T}raveling {S}alesman {P}roblems",
   year = "19XX",
   booktitle = "OR/AI: The Integration of Problem Solving Strategies",
   publisher= "XXXX",
   address = "XXXX",
   pages = "29--57"
   }

@article{Li65,
  author = "S. Lin",
  Title = "Computer {S}olutions of the {T}raveling {S}alesman {P}roblem",
  Journal = "Bell System Technical Journal",
  Year = "1965",
  Volume = "44",
  Pages ="2245--2269"
  }

@article{LiKe73,
  author = "S. Lin and B. Kernighan",
  Title = "An {E}ffective {H}euristic {A}lgorithm for the {T}raveling
{S}alesman {P}roblem",
  Journal = "Operations Research",
  Year = "1973",
  Volume = "21",
  Pages ="498--516"
  }

@book{Lu87,
  author =  "E. Lusk, et al.",
  title = "Portable Programs for Parallel Processors",
  publisher = "Holt, Rinehart and Winston, Inc.",
  year = "1987"
  }

@article{Ma74,
  author = "R. Marsten",
  Title = "An {A}lgorithm for {L}arge {S}et {P}artitioning {P}roblems",
  Journal = "Management Science",
  Year = "1974",
  Volume = "20",
  Pages ="774--787"
  }

@article{MaSh81,
  author = "R. Marsten and F. Shepardson",
  Title = "Exact {S}olution of {C}rew {S}cheduling {P}roblems {U}sing the {S}et
{P}artitioning {M}odel: Recent {S}uccessful {A}pplications",
  Journal = "Networks",
  Year = "1981",
  Volume = "11",
  Pages ="165--177"
  }

@article{Mu91,
  author = "H. Muhlenbein",
  Title = "Parallel {G}enetic {A}lgorithms and {C}ombinatorial {O}ptimization",
  Journal = "SIAM Journal on Optimization",
  Year = "1991",
  Volume = "To appear",
  }

@book{PaSt82,
  author =  "C. Papadimitriou and K. Steiglitz",
  title = "Combinatorial Optimization Algorithms and Complexity",
  publisher = "Prentice-Hall Inc.",
  year = "1982"
  }

@article{Pi68,
  author = "J. Pierce",
  Title = "Application of {C}ombinatorial {P}rogramming to a {C}lass of
{A}ll-{Z}ero-{O}ne {I}nteger {P}rogramming {P}roblems",
  Journal = "Management Science",
  Year = "1968",
  Volume = "15",
  Pages ="191--209"
  }

@inproceedings{Ta89,
  author = "R. Tanese",
  editor = "J. Schaffer",
  title = "Distributed {G}enetic {A}lgorithms",
  booktitle = "Proceedings of the Third International Conference on Genetic
Algorithms",
  year = "1989",
  pages = "434--440",
  publisher = "Morgan Kaufmann"
  }

@misc{Gr91,
  author = "J. Gregory",
  title = "Private Communication",
  year = "1991",
  }

@misc{Lusk,
  author = "E. Lusk",
  title = "Online P4 release notes",
  year = "1991",
  }

@inproceedings{LaMu91,
  author = "G. von Laszewsski and H. Muhlenbein",
  title = "Partitioning a {G}raph with a {P}arallel {G}enetic {A}lgorithm",
  booktitle = "Parallel Problem Solving from Nature",
  editor = "H. Schwefel and R. Manner",
  year = "1991",
  publisher = "Springer-Verlag",
  pages = "165--169"
  }

@inproceedings{CoMaRi91,
  author = "J. Cohoon and W. Martin and D. Richards",
  title = "{G}enetic {A}lgorithms and {P}unctuated {E}quilibria in {VLSI}",
  booktitle = "Parallel Problem Solving from Nature",
  editor = "H. Schwefel and R. Manner",
  year = "1991",
  publisher = "Springer-Verlag",
  pages = "134--144"
  }

@inproceedings{Sc91,
  author = "M. Gorges-Schleuter",
  title = "Explicit {P}arallelism of {G}enetic {A}lgorithms through
{P}opulation {S}tructures",
  booktitle = "Parallel Problem Solving from Nature",
  editor = "H. Schwefel and R. Manner",
  year = "1991",
  publisher = "Springer-Verlag",
  pages = "150--159"
  }

@inproceedings{Ta87,
  author = "R. Tanese",
  editor = "J. Grefenstette",
  title = "{P}arallel {G}enetic {A}lgorithms for a {H}ypercube",
  booktitle = "Proceedings of the Second International Conference on Genetic
Algorithms and {T}heir Applications",
  publisher = "Lawrence Erlbaum Associates",
  year = "1987",
  pages = "177--183"
  }

@inproceedings{StWhMa91,
  author = "T. Starkweather and D. Whitley and K. Mathias",
  title = "Optimization {U}sing {D}istributed {G}enetic {A}lgorithms",
  booktitle = "Parallel Problem Solving from Nature",
  editor = "H. Schwefel and R. Manner",
  year = "1991",
  publisher = "Springer-Verlag",
  pages = "176--185"
  }


@inproceedings{FoHu91,
  author = "T. Fogarty and R. Huang",
  title = "Implementing the {G}enetic {A}lgorithm on {T}ransputer {B}Ased
{P}arallel {P}rocessing {S}ystems",
  booktitle = "Parallel Problem Solving from Nature",
  editor = "H. Schwefel and R. Manner",
  year = "1991",
  publisher = "Springer-Verlag",
  pages = "145--149"
  }


@inproceedings{KrScVo91,
  author = "B. Kroger and P. Schwenderling and O. Vornberger",
  title = "Parallel {G}enetic {P}acking of {R}ectangles",
  booktitle = "Parallel Problem Solving from Nature",
  editor = "H. Schwefel and R. Manner",
  year = "1991",
  publisher = "Springer-Verlag",
  pages = "160--164"
  }

@inproceedings{PeLeGr87,
  author = "C. Pettey and M. Leuze and J. Grefenstette",
  editor = "J. Grefenstette",
  title = "A {P}arallel {G}enetic {A}lgorithm",
  booktitle = "Proceedings of the Second International Conference on Genetic
Algorithms and {T}heir Applications",
  publisher = "Lawrence Erlbaum Associates",
  year = "1987",
  pages = "155--161"
  }


@techreport{LiBa91,
   author = "G. Liepins and S. Baluja",
   title = "{apGA}: An {A}daptive {P}arallel {G}enetic {A}lgorithm",
   year = "1991",
   institution = "Oak Ridge National Laboratory"
   }


@inproceedings{Da87,
  author =  "L. Booker",
  editor =  "L. Davis",
  title = "Improving {S}earch in {G}enetic {A}lgorithms",
  booktitle = "Genetic Algorithms and Simulated Annealing",
  publisher = "Pitman Publishing",
  address = "London",
  pages = "61-73",
  year = "1987"
  }

@book{Da91,
  author =  "L. Davis",
  title = "Handbook of Genetic Algorithms",
  publisher = "Van Nostrand Reinhold",
  address = "New York",
  year = "1991"
  }

@book{PaRa88,
  author =  "R. Parker and R. Rardin",
  title = "Discrete Optimization",
  publisher = "Academic Press",
  address = "San Diego",
  year = "1988"
  }

@inproceedings{CoDoMaXX,
  author = "A. Colorni and M. Dorigo and V. Maniezzo",
  title = "{G}enetic {A}lgorithms and {H}ighly {C}onstrained {P}roblems: the
{T}ime-table {C}ase",
  booktitle = "XXXX-XXXX",
  year = "XX",
  pages = "55--59"
  }

@inproceedings{RiPaLiHi89,
  author = "J. Richardson and M. Palmer and G. Liepins and M. Hilliard",
  editor = "J. Schaffer",
  title = "Some {G}uidelines for {G}enetic {A}lgorithms with {P}enalty
{F}unctions",
  booktitle = "Proceedings of the Third International Conference on Genetic
Algorithms",
  year = "1989",
  publisher = "Morgan Kaufmann",
  Pages ="191--197"
  }

@inproceedings{SiSk89,
  author = "Siedlecki and Sklansky",
  editor = "J. Schaffer",
  title = "Constrained {G}enetic {O}ptimization via {D}ynamic
{R}eward-{P}enalty {B}alancing and {I}ts {U}se in {P}attern {R}ecognition",
  booktitle = "Proceedings of the Third International Conference on Genetic
Algorithms",
  year = "1989",
  publisher = "Morgan Kaufmann",
  Pages ="141--150"
  }


@article{FoGrSt92,
  author = "I. Foster and W. Gropp and R. Stevens",
  Title = "The {P}arallel {S}sclability of the {S}pectral {T}ransform
{M}ethod",
  Journal = "Monthly Weather Review",
  Year = "1992",
  Volume = "To appear",
  }

From: ajsw@epcc.ed.ac.uk
Date: Mon, 5 Oct 92 19:12:11 BST
To: ob00@Lehigh.EDU
Subject: Re: References on Parallel Genetic Algorithms

Here are some references from our publications list; you may well find
postscript for many of these papers on our ftp site (epcc.ed.ac.uk) or
you could ask our secretary for them (email me and I'll ask :-)

Hope this is helpful,


Andrew J S Wilson
<ajsw@uk.ac.ed.epcc>         -=-        Edinburgh Parallel Computing Centre

@techreport{tec:norman:GeneAppTopOptMultiArch,
        author="Michael G Norman",
        title="A Genetic Approach to Topology Optimisation for
Multiprocessor Architectures",
        institution="Edinburgh Concurrent Supercomputer Project",
        year="1988",
                type="",
                number="",
                address="",
                month="",
                note="",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@article{art:radcliffe:EquClasAnalGenAlg,
        author="Nicholas J Radcliffe",
        title="Equivalence Class Analysis of Genetic Algorithms",
        journal="Complex Systems",
        year="1991",
                volume="5",
                number="2",
                pages="183-205",
                month="",
                note="EPCC-TR90-03",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@inproceedings{inp:radcliffe:FormaAnal,
        author="Nicolas J Radcliffe",
        title="Forma Analysis and Random Respectful Recombination",
        booktitle="Proc. of 4th International Conference on Genetic
        Algorithms",
        year="1991",
                editor="R K Belew and L B Booker",
                pages="222-229",
                organization="",
                publisher="Morgan Kaufmann",
                address="San Mateo",
                month="",
                note="EPCC-TR91-02",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@techreport{tec:radcliffe:GeneSetRecomb+Apps,
        author="Nicolas J Radcliffe",
        title="Genetic Set Recombination and its Application to Neural Network
        Topology Optimisation",
        institution="EPCC",
        year="1991",
                type="",
                number="TR91-21",
                address="",
                month="",
                note="to be published in Neural Computing and its
                Applications, Vol 1, no. 1",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@incollection{inc:radcliffe:GeneSetRecomb,
        author="Nicolas J Radcliffe",
        title="Genetic Set Recombination",
        booktitle="Foundations of Genetic Algorithms II",
        publisher=" M Kaufmann",
        year="1992",
                editor="D Whitley",
                chapter="",
                pages="",
                address="",
                month="",
                note="to be published, autumn",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@incollection{inc:radcliffe:Non-LinGeneReps,
        author="Nicolas J Radcliffe",
        title="Non-Linear Genetic Representations'",
        booktitle="Parallel Problem Solving from Nature II",
        publisher="Elsevier Science Publishers",
        year="1992",
                editor="",
                chapter="",
                pages="",
                address="",
                month="",
                note="to appear",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@techreport{tec:radcliffe:AlgGeneAlg,
        author="Nicolas J Radcliffe",
        title="The Algebra of Genetic Algorithms",
        institution="EPCC",
        year="1992",
                type="",
                number="TR92-11",
                address="",
                month="",
                note="in preparation",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@unpublished{unp:edwards:GenAlgOptProcPlan,
        author="Donald Edwards",
        title="Genetic Algorithms for the Optimisation of Process Planning",
        note="EPCC-SS90-09",
        month="",
        year="",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@unpublished{unp:russo:GenerFrameImpGenetAlg,
        author="Claudio Russo",
        title="A General Framework for Implementing Genetic Algorithms",
        note="EPCC-SS91-17",
        month="",
        year="",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}

@phdthesis{phd:radcliffe:GenNNMIMDComps,
        author="Nicolas J Radcliffe",
        title="Genetic Neural Networks on MIMD Computers",
        school="University of Edinburgh",
        year="1990",
                address="",
                month="",
                note="Physics PhD thesis",
        library="",
        category="",
        comment="",
        source="",
        keywords="",
        contact="",
        abstract="",
        review="",
}


Date: Tue, 6 Oct 92 07:54:04 WST
From: geoff@cs.uwa.edu.au (Geoff Sutcliffe)
To: ob00@Lehigh.EDU
Subject: Re: References on Parallel Genetic Algorithms

There's a book by Ackley which does lots of this. Can't remember the title
off-hand, but if no-one else gives it to you, mail me and I'll look it up.

Geoff

Geoff Sutcliffe
Department of Computer Science,       Email    : geoff@cs.uwa.edu.au
University of Western Australia,      Phone    : +61 9 380 2305
Stirling Highway,                     FAX      : +61 9 380 1089
Nedlands, Western Australia, 6009.


Date: Tue, 6 Oct 1992 12:26:38 -0400
From: "Quentin F. Stout" <qstout@eecs.umich.edu>
To: OB00@Lehigh.EDU
Subject: genetic algorithm

One reference you should acquire (through University Microfilms)
is the PhD Thesis "Distributed Genetic Algorithms for Function
Optimization", by Reiko Tanese, 1989, University of Michigan,
Electrical Engineering and Computer Science Department.

Quentin F. Stout   qstout@eecs.umich.edu




From: Guenther Rudolph <rudolph@lucky.informatik.uni-dortmund.de>
Date: Wed, 7 Oct 92 14:28:18 +0100
To: ob00@Lehigh.EDU
Subject: References on Parallel Genetic Algorithms

Hello Olcay,

concerning your question in newsgroup comp.parallel:

There are some articles on parallel Genetic Algorithms and
Evolution Strategies within the proceedings of the GA-conferences
(1985, 1987, 1989, 1991) and PPSN (Parallel Problem Solving from
Nature) conferences (1990, 1992). If you want more detailed
bibligraphic hints please contact me. Moreover, there is an
article of my colleague Frank Hoffmeister:

@conference{Hof91,
        CROSSREF        = {GP91},

        AUTHOR          = {Frank Hoffmeister},
        TITLE           = {Scalable Parallelism by Evolutionary Algorithms},
        PAGES           = {175--198}
        YEAR            = {1991}
}
@book{GP91,
        EDITOR          = {Grauer, M. and Pressmar, D.~B.},
        TITLE           = {Applied Parallel and Distributed Optimization},
        VOLUME          = {367},
        SERIES          = {Lecture Notes in Mathematical Systems
                           and Economics},
        PUBLISHER       = {Springer},
        ADDRESS         = {Berlin},
        YEAR            = {1991}
}

Moreover, subscribe to the GA-list via e-mail:

        GA-List-Request@AIC.NRL.NAVY.MIL

Best regards

        Guenter

------------------------------------------------------------------
Guenter Rudolph                 University of Dortmund
                                Computer Science Department, LS XI
Phone : +49-231-755-2637        P.O. Box 50 05 00
Fax   : +49-231-755-2047        W-4600 Dortmund 50
Telex : 822465 unido d          Germany

e-mail: rudolph@ls11.informatik.uni-dortmund.de
        rudolph@unido.uucp
------------------------------------------------------------------





Date: Wed, 7 Oct 92 08:05:02 MDT
From: bentson@cs.colostate.edu (Randolph Bentson)
To: ob00@Lehigh.EDU
Subject: Re: References on Parallel Genetic Algorithms

Write to Darrel Whitley (whitley@cs.colostate.edu) or Tim
Starkweather (starkwe@cs.colostate.edu).  They've been
doing lots of interesting GA work, including distributed
and parallel implementations.

--
    Randolph Bentson                 Colorado State University
    bentson@grieg.CS.ColoState.Edu   Computer Science Department
    303/491-5792                     Ft. Collins, CO 80523






Date: Wed, 7 Oct 92 17:23:28 +0100
From: marco@duteca.et.tudelft.nl (M. van Harsel)
To: OB00@Lehigh.EDU
Subject: Parallel Genetic Algorithms
Cc: marco@duteca.et.tudelft.nl


Dear Olcay Boz,


I am doing a literature investigation on genetic algorithms in instruction
 scheduling myself.

I found the following reference on Parallel Genetic Algorithms :

Proceedings Of The Third International Conference on Genetic Algorithms.
Morgan Kaufmann Publ. 1989, pages 398 to 441

on  Instruction Scheduling Using Genetic Algorithms :

S.J. Beaty. A Study of Instruction Scheduling Using Genetic Algorithms.
PhD thesis Mechanical Engineering Department, Colorado
State University Colorado 1991

Would you please send me the answers of the questions underneath?
My mail address is  marco@duteca.et.tudelft.nl.

 * Did you get any reactions on your question concerning my subject?
 * Do you have any software about instruction scheduling using genetic
   algorithms.

Beforehand thank you very much,

                              Marco van Harsel








Date: Wed, 7 Oct 92 16:15:56 MDT
From: whitley@cs.colostate.edu (darrell  whitley)
To: OB00@Lehigh.EDU
Subject: Parallel GAs


Someone forward email to me saying that you are looking
for references on parallel GAs.  there are dozens of papers.

For starters, you have probably looked into the GA conferences
(1987, 1989 and 1991), but the PPSN conferences
(Parallel Problems Solving from Nature) perhaps has
even more references on //-GAs. (1990 and 1991).

These are good places to start.

Darrell Whitley





Date: Wed, 7 Oct 92 18:44:15 EDT
From: lmerkle@afit.af.mil
To: ob00@Lehigh.EDU
Subject: Re: References on Parallel Genetic Algorithms

There are a host of references, mostly in the proceedings of the
four International Conferences on Genetic Algorithms.

In addition to those, Capt Andrew Dymek's MS Thesis here at AFIT
studied the effects of selection strategies and solution sharing
strategies on premature convergencs in PGAs.  My own thesis
extends Capt Dymek's work, and examines issues in the
parallelization of messy GAs.

Other work that may interest you are Reiko Tanese's thesis (from
the University of Michigan) and V. Kommu's dissertation (in
preparation at the University of Iowa).

This is just off the top of my head.  If you want more
information, please feel free to reply.

Larry Merkle
--
Laurence D. Merkle, CAPT, USAF    | The opinions expressed are
Student, Department of Electrical | my own, and do not necessarily
         and Computer Engineering | reflect those of AFIT, the USAF,
Air Force Institute of Technology | or the US Government







From: Talbi El-ghazali <ghazali@imag.fr>
Date: Sat, 10 Oct 1992 13:17:27 +0100
To: ob00@Lehigh.EDU
Subject: References on Parallel Genetic Algorithms

 see :
 1/ E-G.TALBI, P.BESSIERE, "A Parallel Genetic Algorithm for the graph
    partitioning problem", ACM Int. conf. on supercomputing, Cologne, Jul
1991.

 2/ E-G.TALBI, T.MUNTEAN, "A Parallel Genetic Algorithm for the process-
processors mapping", 2nd Symposium on high Performance Computing,
North-Holland, Montpellier, France, Oct 1991.

3/ J.M.Ahuactzin, E-G.Talbi, P.bessiere, E.mazer, "Using Genetic Algorithms
for Robot Motion Planning", European Conference on Artificial Intelligence
ECAI92, Austria, Aug 1992.

4/ E-G.TALBI, T.MUNTEAN, "Hill-climbing,simulated annealing and genetic
algorithms : a comparative study and their application to the mapping
problem", to appear in HICCS 93, Hawaii, Jun 1993.


--
**************************************************************************
  e-mail: ghazali@imag.fr
  TALBI GHAZALI
  Laboratoire de Genie Informatique / Institut IMAG
  BP 53X 38041 Grenoble France      Tel:76514600 Poste 5122

Engineers think theory approximates reality
Physicists think that reality approximates theory
Mathematicians never make the connection
**************************************************************************






From: tblach@daimi.aau.dk
Subject: Re: PGA-ref.
To: ob00@Lehigh.EDU
Date: Mon, 12 Oct 92 15:34:18 MET
Cc: cas@daimi.aau.dk (Claus A. S|rensen)



  HI!!

  A while ago you were asking about references on Parallel Genetic Algorithms.
  We are currently working on a project on PGA's as function optimizers.
  At the moment we're implementing a PGA on a transputer network with
  64 T800's, but are planning to try it out on a network with the i860
  processor which is faster. As you probably know; GA is a very popular
  topic at the moment, and there are several interesting articles around.

  Here is list of those that we found most interesting:

     Of course there is the proceedings from the 1.- 4. Int'l Conf.on GA's
     in all of them there is a section dedicated to PGA's

     There is also The Proceeding from the 'Workshop on Parallel problemsolving
     from Nature' Dortmund '90 Ed. H.P. Schwefel

     David E. Goldberg's book: GA in Search, Optimization and Machine learning
     contains a couple of examples on PGA.



   Here is a small list of articles. We can recommend the articles
   by Muhlenbein which we personally found very usefull:

     PGA's -Genetic Packing of Rectangles on Transputers
     Berthold Kroger - P. Schwenderling - O. Vornberger
     Transputng '91

     An investigation of several Parallel GA
     D. MacFarlane -I East
     Tools and Techniques for tranputer App. Ed S.J.Turner

     Parallel GA in optimization.
     E.J.Anderson - M.Ferris
     Proc. of the 4. SIAM Conf. on Parallel Processing for Scientific comp. '89

     Genitor II
     XXXXXXXXXXXX
     Journal of Theoretical and Experimental AI '91

     The PGA' as Function Optimizer.
     H. Muhlenbein - H.Schomich - J.Born
     Parallel Computing 17 '91

     Evolution in time and space The PGA
     H. Muhlenbein
     Foundations of GA.

  If you don't already know, there's an anonymous ftp-site:

                ftp.aic.nrl.navy.mil

  that contains lots of GA-stuff including a NCUBE-implementation of
  Goldbergs SGA, and this week there will be a Connection Machine imp.
  of Grefenstettes Genesis, called PARAGENESIS available.

  There is also the GA-mailing list: GA-Digest, read more about this
  at the ftp-site above.


  We hope that will find some of this usefull and will appreciate if
  you will mail back to us if you find anything interesting about
  PGA's and/or Function Optimization.

                             Claus Aggerholm Sorensen
                             Torben V. Blach

                             (email: tblach@daimi.aau.dk)




--
********************************************************
* Name : Torben V. Blach                               *
* Email: tblach@daimi.aau.dk                           *
*        Computer Science Department                   *
*        Aarhus University                             *
*        DENMARK                                       *
********************************************************

-- 


         -----------------------------------------------------------------
         |  OLCAY BOZ                     |  OB00@NS1.CC.LEHIGH.EDU      |
         |  LEHIGH UNIVERSITY             |                              |
         |  COMPUTER SCIENCE DEPARTMENT   |                              |
         |  Ph. D. Student                |  phone : (215) 758-1886      |

Newsgroups: comp.parallel