IV.

MODELS FOR THE PARALLELIZATION OF GENETIC ALGORITHMS 

 

Contents of this chapter

IV.1 Need of Parallelization
IV.2 Fine and Coarse Grain Models
IV.3 A Global Vision of the Existing Parallel GA Software
IV.4 Object Orientation and Parallelism
IV.3 Applications and Relationships with the Sequential Models
 


IV.1 Need of Parallelization

Sequential GAs have many succesfull applications to very different domains but there exists a number of drawbacks in their utilization, namely:
  • They are usually inefficient.
  • Evaluations are very time-consuming.
  • Populations need to be large for a numerous number of problems.
  • In order to solve these shortcomings and also in order to study new models of higher efficiency and efficacy, parallel models of GAs and in general of EAs have been devised and used. Parallel GAs are not only an extension of the traditional GA sequential model but they represent a new class of algorithms in that they make a different search work. Thus we do not only expect a Parallel Genetic Algorithm (PGA) to be more efficient but also to need a smaller number of evaluations of the target function.

    Many different approaches to PGAs exist and they differ in many aspects. It follows one possible classification of parallel GAs attending to three concepts: the parallel model, the distribution of the population and the implementation. This is not the sole classification one can made for PGAs because it is very normal that the existing PGAs combine several caracteristics from these apparently disjoin models.


    IV.2 Fine and Coarse Grain Models

    In the beginning of the parallelization of these algorithms the well-known farming method was used. In this way a central processor performs the selection operations while the associated slave processors perform the recombination, mutation and the evaluation of the fitness function. The last operation (evaluation) usually represent the most time-consuming load of the genetic algorithm.

    However, One of the most accepted classification for parallel GAs divide them attending to their parallel grain, that is, the relationship between computation and communication. Thus we can distinguish among coarse and fine grain models.

    Typical coarse grain models consist in a set of parallel subpopulations that evolve independently from each other and that periodically exchange individuals among them. The topology for the exchanges is usually a ring or else some similar disposition. The subpopulations undergo exactly the same genetic operations on the same kind of genotype and the result is the best individual found in the overall population.

    When dealing with a distributed GA some additional parameters need to be defined. If migration of individuals has to take place then the rate for the migrations and the number of individuals to migrate come into scene. We also need to decide which individuals are going to migrate. Finally the decision on the target subpopulation determines the global topology of the distributed system. Traditionally, the topology is a ring, one individual -the best or a random individual- migrates in every migration step and migrations take place at some predefined and periodic moments (althought some criteria for more controlled migrations have been considered in this field, usually performing migrations when some condition holds -the standard deviation falls below a given bottom limit, etc...-).

    The migration scheme is very suited for a implementation in a network of workstations. The existing UNIX networks with TCP/IP communication protocols are the preferred for many researchers due to its relatively easy used and also to the existence of many communication tools: socket interface, PVM, etc...

    On the other hand cellular (also known as massively parallel GAs) genetic algorithms use a spatial disposition for the individuals of one single population. Genetic operations take place in parallel for every node of the population but every individual interacts only with its neighborhood. Hence the selection, crossover and mutation take place by only considering the adjacent strings. The replacement policy destroys the considered individual by overwriting it with the newly computed string.

    Cellular GAs have been implemented on multiprocessors due to the close similarities between the model and the physical disposition of CPUs. OCCAM and different versions of C have been used in the implementation. At present, multiprocessors machines like Transputers are being shifted to applications in which we need to execute a sequential algorithm with high speed. However cellular GAs on multiprocessors are not very frequent because the parallel market has plenty of local area network (cheaper, very fast, resources sharing, ...). One intermediate approach could be the simulation of a fine-grained GA in a network of workstations.

    In cellular GAs, the isolation by distance property allows a high diversity and the selection pressure is alse weaker due to the local selection operator. The appearance of new species of solution in the grid (for example) and the refinement of existing solutions are both allowed and desired. The exploitation/exploration balance is then in many applications quite well developed by a parallel cellular GA.


    IV.3 A Global Vision of the Existing Parallel GA Software

    In this section we make a survey of the algorithms and software more readily accessible in this area. Let us begin with a temporal review of parallel GAs (PGAs). The most well-known cgpGAs and their main characteristics
    sorted by date of referred appearance are:
    TABLE I. OVERVIEW OF PARALLEL GAs BY YEAR
    cgpGA
    Ref.
    Year
    Main Characteristics
    PGA
    [55]
    1987
    Generational cgpGA on an Intel iPSC hypercube (8 CPUs). Migrate the best. Dynamic Top.
    dGA
    [68]
    1989
    Distributed populations. Good results with 20% of population migrants every 20 generats.
    GENITOR II
    [73]
    1990
    Steady-State islands with ranked selection and reduced surrogate crossover
    PGA
    [51]
    1991
    Sub-populations in a circular ladder-like 2-D topology. Migrate the best, local hill-climbing
    SGA-cube
    [23]
    1991
    Made for nCUBE2. This is the parallel extension of the well known simple GA of Goldberg
    PARAGENESIS
    ---
    1992
    Made for the CM-200. This places one individual in every CPU
    PeGAsuS
    [59]
    1993
    Targeted for MIMD machines and written in a very high and flexible description language
    GAMAS
    [56]
    1994
    Uses 4 very heterogeneous species (islands) and quite specialized migrations and genotyp.
    iiGA
    [44]
    1994
    Injection island GA with hierarchical heterogeneous nodes and asynchronous migrations
    SP1-GA
    [42]
    1994
    128 steady-state islands on an IBM SP1 machine of 128 nodes. 2-D toroidal mesh. mr=1
    DGENESIS
    [47]
    1994
    Free topology, migration and policies for selection. Implemented with sockets and UDP
    GALOPPS
    [30]
    1996
    Very flexible. Implemented with PVM and comprising a large number of operators
    GDGA
    [45]
    1996
    Synchronous. Simulated on one processor. Generational. Fuzzy crossover and FP genes
    CoPDEB
    [2]
    1996
    Every island uses its own probabilities for mutation & crossover and specialized operators
     

    Of course this list is not complete, but it gives us a feeling of the evolution of cgpGAs over recent years. We will
    offer more details about these and other algorithms in the following tables.

    There has been a tendency towards making PGAs that run on clusters of machines paying a great attention to
    their portability. Old systems like transputer machines do not support recent implementations. Also, new
    developments in JAVA are appearing as a confirmation of these tendencies.

    In order to complete our historical and application overview we give an original classification of sequential and parallel  GAs into three major categories [59] according to their specific objectives:

    · Application Oriented: These are black-box systems designed to hide the details of GAs and help the user in developing applications for specific domains. Some of these are useful for different purposes such as scheduling or telecommunications (e.g. PC/BEAGLE). Some others are much more application oriented (like OMEGA for finance). Usually they are menu-driven and easily parameterizable.

    · Algorithm Oriented: Based on specific algorithms. The source code is available in order to provide their easy incorporation into new applications. This class may be further sub-divided into:

  • Algorithm Specific: They contain one single GA (e.g. GENESIS). Their users are system developers (for making applications) or else researchers in this field (interested in extensions).
  • Algorithm Libraries: They support a group of algorithms in a library format (e.g. OOGA). They are highly parameterized and contain many different operators to help future applications.
  • · Tool Kits: These are flexible environments for programming a range of different GAs and applications. They can be sub-divided into:
  • Educational: Used for introducing GA concepts to novice users (e.g. GA Workbench). The basic techniques to track executions and results during the evolution are easily managed.
  • General Purpose: Useful for modifying, developing and supervising a wide range of operators, algorithms and applications (e.g. Splicer).
  • We present some detailed tables with a classification of algorithms, and mark this classification with the above labels. Also, we use the PROP label for distinguishing between commercial and proprietary systems. We have also opened the contents of this table to non-cgpGAs to offer a better view of the global achievements of this class of evolutionary algorithms. See the following tables.
    TABLE II. OVERVIEW OF SOME UP-TO-DATE EXISTING SEQUENTIAL AND PARALLEL GENETIC ALGORITHMS
    Genetic Algorithm
    Ref.
    Lang.
    OS/Machine
    Kind of GA
    Algorithm
    Seq/Par
    Evolution
    HOW TO GET IT!
    ASPARAGOS
    [32]
    C
    64 T800 transp
    Algorithm Specific
    Single / No pop.
    PAR
    Local
    ---
    CoPDEB
    [2]
    C
    UNIX
    Algorithm Specific
    Single / No prop.
    PAR
    Gen.
    adamidis@it.teithe.gr
    DGENESIS 1.0
    [47]
    C
    UNIX
    Algorithm Specific
    Single / No Prop.
    PAR
    Percentage
    ftp.aic.nrl.navy.mil
    ECO-GA
    [21]
    C?
    UNIX?
    Algorithm Specific
    Single / No Prop.
    PAR
    Local
    yuval@wisdom.weizmann.ac.il
    EM 2.1
    [69]
    C
    DOS
    Algorithm Library
    Algrthm. Library
    SEQ
    Gen. / S. S.
    [130.149.192.50]/W 
    EnGENEer
    [60]
    C
    UNIX
    General Purpose
    Algrthm. Library
    SEQ/par
    Gen. / S. S.
    ---
    ESCAPADE 1.2
    [35]
    ---
    ---
    Algorithm Specific
    Single / No Prop.
    ---
    E. S.
    ls11.informatik.uni-dortmund.de
    EVOLVER 2.0
    ---
    C++
    DOS & MAC
    Application Orient.
    Single / Prop.
    SEQ
    ---
    Axcélis (used in a spread sheet)
    GA Workbench
    [37]
    C
    DOS
    Educational
    Algrthm. Library
    SEQ
    Percentage
    camcon.co.uk
    GAGA
    [8]
    C
    UNIX
    Algorithm Specific
    Single / No Prop.
    SEQ
    ---
    cs.ucl.ac.uk/darpa/gaga.shar
    GAGS
    [48]
    C++
    UNIX & DOS
    General Purpose
    Algrthm. Library
    SEQ
    Gen.
    http://kal-el.ugr.es/GAGS
    GAlib
    [71]
    C++
    UNIX
    Algorithm Specific
    Algrthm. Library
    SEQ
    Gen.
    lancet.mit.edu/pub/ga/galib242.tar.gz
    GALOPPS 3.1
    [30]
    C
    UNIX & DOS
    Algorithm Specific
    Single / No Prop.
    PAR
    Gen.
    isl.msu.edu/pub/GA
    GAMAS
    [56]
    C?
    UNIX
    Algorithm Specific
    Single / No Prop
    PAR
    Gen.
    ---
    GAME
    [66]
    C++
    UNIX & DOS
    General Purpose
    Algrthm. Library
    SEQ/par
    Gen. / S. S.
    bells.cs.ucl.ac.uk/papagena/game
    GAucsd 1.2 / 1.4
    [61]
    C
    UNIX, DOS ...
    Algorithm Specific
    Single / No Prop.
    SEQ
    Gen.
    http://www.aic.nrl.navy.mil/galist/src/GAucsd14.sh.Z
    GDGA
    [45]
    C
    UNIX
    Algorithm Specific
    Single / No Prop.
    SEQ/par
    Gen.
    lozano@decsai.ugr.es
    GENESIS 5.0
    [33]
    C
    UNIX, DOS ...
    Algorithm Specific
    Single / No Prop.
    SEQ
    Percentage
    http://www.aic.nrl.navy.mil/galist/src/genesis.tar.Z
    GENEsYs 1.0
    ---
    C
    UNIX
    Algorithm Specific
    Single / No Prop.
    SEQ
    Percentage
    [129.217.36.140]/pub/GA/src/GENEsYs-1.0.tar.Z
    GENITOR I - II
    [73]
    C
    UNIX
    Algorithm Specific
    Single / No Prop.
    SEQ-PAR
    S. S. / Rank
    */genitor
    HSDGA
    [70]
    C
    HELIOS
    Algorithm Specific
    Single / No Prop.
    PAR
    Local
    ---
    LibGA
    [18]
    C
    UNIX
    Algorithm Specific
    Single / No Prop.
    SEQ
    Gen. / S. S.
    */libga
    OMEGA
    [66]
    ---
    ---
    Application Orient.
    Prop.
    SEQ
    ---
    KiQ Limited (used in business applications)
    OOGA
    [22]
    CLOS
    any LISP
    Algorithm Library
    No Prop.
    SEQ
    Gen. / S. S.
    TSP, P.O. Box 991, Melrose, MA 02176-USA
    PARAGENESIS
    ---
    C*
    CM-200
    Algorithm Specific
    Single / No Prop
    PAR
    Percentage
    [192.26.18.74]/pub/galist/src/ga/paragenesis.tar.Z
    PC/BEAGLE
    [59]
    ---
    DOS
    Application Orient.
    Prop.
    SEQ
    S. S.
    Pathway Research Ltd. (used in machine learning)
    PeGAsuS
    [59]
    C
    UNIX, ...
    General Purpose
    Algrthm. Library
    PAR
    Gen. / S. S.
    ---
    PGA 2.5
    ---
    C
    UNIX & DOS
    Algorithm Specific
    Single / No Prop
    PAR
    Gen.?
    http://www.aic.nrl.navy.mil/galist/src /pga-2.5.tar.Z
    PGAPack
    [43]
    C
    UNIX, ...
    Algorithm Library
    Algrthm. Library
    PAR
    Gen. / S. S.
    http://www.mcs.anl.gov/pgapack.html
    RPL2
    [57]
    C
    UNIX, ...
    General Purpose
    Prop. Library
    PAR
    Gen. / S. S.
    http://www.quadstone.co.uk/~rpl2
    SGA
    [26]
    C
    UNIX
    Algorithm Specific
    Single / No Prop
    SEQ
    Gen.
    [192.26.18.56] ... sgac_94m.tgz
    SGA-Cube
    [23]
    C
    nCUBE 2
    Algorithm Specific
    Single / No Prop
    PAR
    Gen.
    [192.26.18.56] ... sgacub94.tgz
    SPLICER 1.0
    [54]
    C
    UNIX & MAC
    General Purpose
    Algrthm. Library
    SEQ
    Gen.
    galileo.jsc.nasa.gov
    SUGAL 2.0
    [38]
    C
    UNIX, DOS, ...
    Algorithm Library
    Algrthm. Library
    SEQ
    Gen. / S. S.
    http://osiris.sund.ac.uk/ahu/sugal/home.html
    TOLKIEN
    ---
    C++
    UNIX
    General Purpose
    Algrthm. Library
    SEQ
    Gen.?
    */tolkien
    XpertRule GenAsys
    ---
    ---
    ---
    Application Orient.
    Prop.
    SEQ
    ---
    Attar Software (used in design and scheduling)
     
    TABLE III. MEANING OF THE SYMBOLS IN TABLE II
    Symbol
    Meaning of the Symbol
    Local The algorithm performs operations on every string by interactions with only its neighboring strings
    Gen. Generational: The basic algorithmic step is a full generation of individuals
    S. S. Steady-State: the basic algorithmic step is the computation of a very low number of individuals (usually one)
    Percentage GAP: The algorithm works and replaces only a given percentage of the whole population of individuals
    Rank The individuals are sorted according to increasing fitness and the selection uses the ‘position’ in the rank (and not the fitness itself)
    par Parallel version is not available yet
    SEQ/PAR The algorithm is able to work either in sequential and in parallel
    * http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/genetic/ga/systems
    W  pub/software/Evolution_Machine/em_tc.exe
     
    TABLE IV. CLASSIFICATION OF THE GENETIC SYSTEMS
    Application
    Algorithm Oriented
    Tool Kits
    Oriented
    Algorithm Specific
    Algorithm Libraries
    Educational
    General Purpose
     
    ASPARAGOS
         
     
    CoPDEB
    EM 2.1
       
    EVOLVER 2.0
    DGENESIS 1.0
       
    EnGENEer
     
    ECO-GA
         
     
    ESCAPADE 1.2
       
    GAGS
     
    GAGA
    OOGA
       
     
    GAlib
       
    GAME
    OMEGA
    GALOPPS 3.1
         
     
    GAMAS
       
    PeGAsuS
     
    GAucsd 1.2 / 1.4
     
    GA Workbench
     
     
    GDGA
    PGAPack
     
    RPL2
     
    GENESIS 5.0 - GENEsYs 1.0
         
    PC/BEAGLE
    GENITOR I Y II
       
    Splicer 1.0
     
    HSDGA
         
     
    libGA
       
    TOLKIEN
     
    PGA 2.5
    SUGAL 2.0
       
     
    PARAGENESIS
         
    XpertRule GenAsys
    SGA
         
     
    SGA-Cube
         
     
    TABLE V. DETAILS OF THE PARALLEL GAs
    Parallel GA
    Kind of Parallelism
    Topology
    Present Applications
    ASPARAGOS
    Fine grain. Applies Hill-Climbing if no improvement Ladder TSP
    CoPDEB
    Coarse grain. Every sub-pop. applies different operators Full Connected Func. Opt. and ANN’s
    DGENESIS 1.0
    Coarse grain with migrations among sub-populations Any Desired Function Optimization
    ECO-GA
    Fine grain. One of the first of its class Grid Function Optimization
    EnGENEer
    Global parallelization (parallel evaluations) Master / Slave Very Different
    GALOPPS 3.1
    Coarse grain. A very portable software Any Desired Func. Opt. and Transport
    GAMAS
    Coarse grain. Uses 4 species of strings (nodes) Fixed Hierarchy ANN, Func. Opt., ...
    GAME
    Parallel version not available yet. Object Oriented Any Desired TSP, Func. Opt., ...
    GDGA
    Coarse Grain. Admits explicit exploration/exploitation Hypercube Func. Opt. (floating p.)
    GENITOR II
    Coarse grain. Interesting crossover operator Ring Func. Opt. and ANN’s
    HSDGA
    Hierarchical coarse and fine grain GA. Uses E. S. Ring, Tree, Star, ... Function Optimization
    PARAGENESIS
    Coarse grain. Made for the CM-200 (1 ind. - 1 CPU) Multiple Function Optimization
    PeGAsuS
    Coarse or fine grain. High-level programming. MIMD Multiple Teaching and Func. Opt.
    PGA 2.5
    Coarse grain. Makes migrations among sub-populations Multiple Knapsack and Func. Opt.
    PGAPack
    Global parallelization (parallel evaluations) Master / Slave Function Optimization
    RPL2
    Coarse grain. Very flexible and open to new models Any Desired Research and Business
    SGA-Cube
    Coarse Grain. Made for the nCUBE 2 Hypercube Function Optimization
     


    IV.4 Object Orientation and Parallelism

    (Alba, Troya, 1997)

    Traditional imperative languages like C or PASCAL endow the implementation with a high computational speed. However, more actual technologies such as object oriented design can have an outstanding impact on the quality of the implementation. Among the benefits of using the OO methodology for a PGA implementation, the following ones can be mentioned:

    An object oriented implementation of a PGA can also help experimenting and combining different granularities, topologies, operators, hybridization, competition or cooperation with other techniques and offers many other added facilities to create new models of evolution.

    Two actual implementations that follow the OO methodology in C++ are described in this section. We call them dGANN and dGAME. The high parameterization of parallel GAs, their combinations, comparisons and development have been largely enhanced by using the OO design. We discuss a general methodology for building a parallel GA system with high flexibility and then present the two mentioned actual models.

    IV.4.1 PGA Models and OO Implementation

    This section discusses the architecture of a PGA. For that purpose, some ideas on parallel models and the use of object orientation are presented.

    From an algorithmic point of view, useful existing techniques must be examined for inclusion in the PGA. Hybridization and theoretical background are needed to improve existing models or proposing new PGAs.

    The figure below represents the elements we should consider when developing an OO parallel GA (or EA).

    Figure 6. Proposal of working environment for a PGA software system.

    Two mixed levels are shown in the figure. The design level is related to the study of existing approaches, the concrete parallel model, how to perform hybridization and the need of evaluating the PGA on a real-world testbed.

    On the other hand, the implementation level is related to internal details of the system. We propose an object oriented design for several reasons we will justify later in this section. The way of achieving parallelism is also important for the resulting PGA system.

    We strongly believe that any parallel model should help to efficiently solve real complex problems. You can use almost any sequential or parallel system for the study of theoretical issues, but both efficiency and multiple ways of expressing one or more parallel models are required for addressing real problems . Changing or adding operators (static or dynamically during the search) should be made in a structured (and not in a problem-dependent) form.

    Parallel algorithms do not usually run in massively parallel computers since LANs are much more popular. Some present types of LAN technologies as Fast Ethernet or ATM make communication delays as small as hard disk accesses. Hence massive parallelism should be simulated in the local network (Maruyama, Hirose, Konagaya, 1993).

    When simulating parallelism in one processor you must choose between having a process that encapsulates the parallel model directly or using threads (if possible, kernel threads). Sometimes a model could work as different UNIX processes running in the same machine, but might become very inefficient in a distributed environment.

    IV.4.2 The Benefits of Using an OO Design

    The traditional aspect of a GA (see figure 7) can drastically change by means of an OO design and implementation.
    Figure 7. Traditional imperative pseudocode of a GA.
    Figure 8. The shape and semantics of this GA differ from implementations built with imperative languages. For example, explicit initialization of the GA could be helpful for controlling its execution in a parallel platform.

    With practically the same amount of effort we can both specify an imperative pseudocode or else a concrete-working code for a problem in terms of object orientation. The last solution is much more flexible and rich in the data structures it uses and also in the performed operations (as well as in future extensions to other problems).

    Object orientation is not just a new style for implementations. It represents a new form of conceiving the design of a software tool.

    Thus, not only we can express in a new manner a PGA but we can also add new features such as new schemes of evolution, genotypes, lists of operators, parallel models and parameters in almost a straightforward way.

    IV.4.3 The Two Proposed Systems

    In this subsection we want to propose two separated systems that incorporate the main ideas we outlined in the previous sections on PGAs and OO.

    In order to create objects suited for structured addition of operators you need to completely separate the class of individuals and the class of the operator pool. The operator pool is a list of operators that can dynamically accept or reject new operators, and of course change their list of parameters. The idea of an ordered list of operators to be applied each one with its own list of parameters (and not just its application rate) can be very helpful in controlling and enhancing the PGA performance.

    The individuals also must be separated from their contents in the sense that the kind of genotype must be a different class in order to allow an independent manipulation. Hence a problem class must exist to separate the full software system from the actual problem we are trying to solve with it.

    Finally we need communication classes for transferring data among processors and we need also some classes for expressing parallel interactions among GAs. A central monitor is normally needed in order to deal with the user (get global and particular statistics and status, kill a process, save and load populations on line, etc...). In some models it should be interesting the central monitor to make also algorithmic work for the PGA.

    Figure 9. Proposal of a hierarchy of dGA classes (dGANN).

    Figure 9 shows the class hierarchy for the dGA system we call dGANN. This proposal deals with fault tolerance in the sense that if a genetic process dies the system is able to keep on running. We propose asynchronous exchanges of information (like in (Gorges, 1989) or (Munetomo, 1993)), because this will ease the fault tolerance aspect (synchronous communication would be too slow).

    A socket interface has been initially considered the faster and more compatible way of implementing a distributed PGA. Classes for exchanging messages are needed and also for controlling the integrity of the system during execution. New genotypes can be easily added to this class hierarchy.

    In order to have a good general parallel model we think that the implementation could take into account (of course the experience of other existing models and) the benefits of using C++. You can use another OO languages as Eiffel, Ada or Smalltalk but C++ is the most widely accepted.

    Despite its advantages, C++ do not provide parallel support. Thus if we want to parallelize an OO model we need some kind of communication services for the implementation. Parallelization is specially easy and flexible with OO.

    The drawback is that cellular GAs cannot be easily derived from this hierarchy since the object that represents one individual should run in parallel with the rest.

    Cellular GAs (or mpGAs) have many points in common with distributed GAs (dGAs):

    Figure 10. The dGAME model. Merging of models can yield more robust searches. There exist two levels of search: a dGA of mpGAs.

    In the above example the low monitors exchange individuals in a ring topology (much like a migration dGA scheme). Each L-monitor controls a population with a given cellular (mpGA) disposition of individuals.

    With these considerations we are ready to think in a unified parallel model that can be implemented in the same software system and that additionally opens new questions relating the merging and cooperation among different submodels. This is good if we can capture in a given parallel model the advantages of the combined submodels (trying to minimize their associated drawbacks). Our dGAME extension of the GAME (Stender, 1993) environment is the first step in this sense.

    Besides these new ideas, cooperation or competition among different kind of GAs or even different algorithms can be achieved. Such an OO distributed GA could deal with most of requirements of existing problems.

    Most of these concepts can be found in our dGAME environment. An OO design, combinations of topologies and merging of arbitrary dGA-mpGA models are the more important characteristics of dGAME.


    IV.5 Applications and Relationships with the Sequential Models

    From a different point of view we present in table IV a set of representative applications of PGAs in order to
    show the wide spectrum of their successful applications (i. e. robustness).
     
    TABLE VI. SOME APPLICATIONS OF PARALLEL GAs
    Reference
    Application Domain
    [7]
    Parallel training of artificial neural networks. Hybridized and pure cgpGAs
    [19]
    Synthesis of VLSI circuits
    [31]
    Function optimization
    [42]
    Set partitioning problem
    [44]
    Graph partitioning problem
    [49]
    Constraint Optimization, reordering problems, ...
    [51]
    Traveling salesperson problem (TSP), function optimization
    [53]
    Distributing the computing load onto a set of processing nodes
    [56]
    The file allocation problem, XOR neural network, sine envelope sine wave function
    [66]
    Systems modelling, protein tertiary structure prediction and two-dimensional bin packing problems
    [68]
    Walsh polynomials
    [73]
    Optimization of the connection weights of neural networks (XOR, bin-adder, ...) and function optimization
     

    There exist many other applications in very interesting domains such as frequency assignment problems, market
    predictions, game theory, filters, graphic transformations, etc. Some of these applications motivated the need for
    new classes of genotypes that can be thought of consisting in strings of arbitrary symbols. A further extension led to the mentioned genetic programming paradigm [40] in which the individuals are trees of symbols representing computer programs, fuzzy controllers, or many other kinds of high-level concepts. This is a new and important research area in
    which PGAs are developing quickly. Also new genotypes and operators are being developed for dealing with
    constraint problems and combinatorial optimization.

    Besides that, the importance of parallel and distributed GAs is growing due to recent studies in which no parallel
    hardware is needed but still the search is enhanced due to neighborhoods similar to [32], [46] or [51].
     

    References

    1. P. Adamidis. "Review of Parallel Genetic Algorithms Bibliography". Internal T.R., Aristotle University of Thessaloniki, November (http://www.control,ee.auth.gr/~panos/papers/pga_review.ps.gz). 1994.
    2. P. Adamidis, V. Petridis. "Co-operating Populations with Different Evolution Behavior". Proceedings of the Second IEEE Conference on Evolutionary Computation, pp 188-191. 1996.
    3. E. Alba, J. F. Aldana, J. M. Troya. "Load Balancing and Query Optimization in Dataflow Parallel Evaluation of Datalog Programs". Proceedings of the International Conference on Parallel and Distributed Systems, Lionel M. Ni (ed.). IEEE Computer Society Press, pp 682-688. 1994.
    4. E. Alba, J. F. Aldana, J. M. Troya. "A Genetic Algorithm for Load Balancing in Parallel Query Evaluation for Deductive Relational Databases". Procs. of the I. C. on ANNs and GAs, D.W. Pearson, N.C. Steele, R.F. Albrecht (eds.), pp 479-482. Springer-Verlag. 1995.
    5. E. Alba, C. Cotta, J. M. Troya. "Type-Constrained Genetic Programming for Rule-Base Definition in Fuzzy Logic Controllers". Proceedings of the First Annual Conference on Genetic Programming, J. R. Koza, D. E. Goldberg, D. B. Fogel & R. L. Riolo (eds.), Stanford Univ., Cambridge, MA. The MIT Press, pp 255-260. 1996.
    6. E. Alba, J. M. Troya. "Genetic Algorithms for Protocol Validation". Proceedings of the PPSN IV I.C., H. M. Voigt, W. Ebeling, I. Rechenberg & H. P. Schwefel (eds.), Berlin. Springer-Verlag, pp 870-879. 1996.
    7. E. Alba, C. Cotta. "Evolution of Complex Data Structures". Informática y Automática, 30(3), pp 42-60. September, 1997.
    8. C. Alippi, P. Treleaven. "GAME: A Genetic Algorithms Manipulation Environment". Internal Report Department of Computer Science, UCL. 1991.
    9. J. Antonisse. "A New Interpretation of Schema Notion that Overturns the Binary Encoding Constraint". Proceedings of the 3rd ICGA, J. D. Schaffer (ed.), Morgan Kaufmann, pp 86-91. 1989.
    10. T.Bäck, D. Fogel, Z. Michalewicz (eds.) Handbook of Evolutionary Computation (Oxford University Press). 1997.
    11. T. Bäck, H. P. Schwefel. "An Overview of Evolutionary Algorithms for Parameter Optimization". Evolutionary Computation, 1 (1), pp 1-23, The MIT Press. 1993.
    12. J. E. Baker. "Adaptive Selection Methods for Genetic Algorithms". Proceedings of the First International Conference on Genetic Algorithms and Their Applications, J. J. Grefenstette (ed.), Lawrence Erlbaum Associates, Publishers, pp 101-111. 1985.
    13. J. E. Baker. "Reducing Bias and Inefficiency in the Selection Algorithm". Proceedings of the Second International Conference on Genetic Algorithms, J. J. Grefenstette (ed.), Lawrence Erlbaum Associates, Publishers, pp 14-21. 1987.
    14. T. C. Belding. "The Distributed Genetic Algorithm Revisited". Proceedings of the 6th International Conference on GAs, L. J. Eshelman (ed.), Morgan Kaufmann, pp 122-129. 1995.
    15. E. Cantú-Paz. "Parallel Genetic Algorithms in Distributed Memory Architectures". Master Thesis Dissertation, Instituto Tecnológico Autónomo de México. May 1994.
    16. E. Cantú-Paz. "A Summary of Research on Parallel Genetic Algorithms". R. 95007, July 1995. Also revised version, IlliGAL R. 97003. May 1997.
    17. A. Chipperfield, P. Fleming. "Parallel Genetic Algorithms". Parallel and Distributed Computing Handbook, A. Y. H. Zomaya (ed.), MacGraw-Hill , pp 1118-1143. 1996.
    18. A. L. Corcoran, R. L. Wainwright. "LibGA: A User-Friendly Workbench for Order-Based Genetic Algorithm Research". Proceedings of the 1993 ACM/SIGAPP Symposium on Applied Computing, ACM Press. 1993.
    19. F. Corno, P. Prinetto, M. Rebaudengo, M. Sonza-Reorda. "Exploiting Competing Subpopulations for Automatic Generation of Test Sequences for Digital Circuits". Procs. of the PPSN IV I.C., H. M. Voigt, W. Ebeling, I. Rechenberg, H. P. Schwefel (eds.), Springer-Verlag, pp 792-800. 1996.
    20. C. Cotta, E. Alba, J. M. Troya. "Evolutionary Design of Fuzzy Logic Controllers". IEEE Catalog N. 96CH35855, Proceedings of the ISISC’96 Conference, Dearborn, MI pp 127-132. 1996.
    21. Y. Davidor. "A Naturally Occurring Niche & Species Phenomenon: The Model and First Results". Procs. of the 4th ICGA, R. K Belew, L. B. Booker (eds.), pp 257-263. 1991.
    22. L. Davis, J. J. Grefenstette. "Concerning GENESIS and OOGA". Handbook of Genetic Algorithms, L. Davis (ed.), New York: Van Nostrand Reinhold, pp 374-376. 1991.
    23. J. A. Erickson, R. E. Smith, D. E. Goldberg. "SGA-Cube, A Simple Genetic Algorithm for nCUBE 2 Hypercube Parallel Computers". TCGA Report No. 91005, The Univ. of Alabama. 1991.
    24. L. J. Fogel, A. J. Owens, M. J. Walsh. Artificial Intelligence Through Simulated Evolution. John Wiley, New York. 1966.
    25. A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam. PVM: Parallel Virtual Machine. A Users’ Guide and Tutorial for Networked Parallel Computing. The MIT Press. 1994.
    26. D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning; Addison-Wesley. 1989.
    27. D. E. Goldberg. "Sizing Populations for Serial and Parallel Genetic Algorithms". Proceedings of the 3rd ICGA, J. D. Schaffer (ed.), Morgan Kaufmann, pp 70-79. 1989.
    28. D. E. Goldberg, K. Deb, B. Korb. "Don’t Worry, Be Messy". Proceedings of the Fourth International Conference on Genetic Algorithms, R. K. Belew and L. B. Booker (eds.), Morgan Kaufmann, San Mateo, CA, pp 24-30. 1991.
    29. D. E. Goldberg, et al. "Critical Deme Size for Serial and Parallel Genetic Algorithms". IlliGAL Report No. 95002. January 1995.
    30. E. D. Goodman. An Introduction to GALOPPS v3.2. TR#96-07-01, GARAGe, I. S. Lab., Dpt. of C. S. and C. C. C. A. E. M., Michigan State University, East Lansing. 1996.
    31. V. S. Gordon, D. Whitley. "Serial and Parallel Genetic Algorithms as Function Optimizers". Procs. of the 5th ICGA, S. Forrest (ed.), Morgan Kaufmann, pp 177-183. 1993.
    32. M.Gorges-Schleuter. "ASPARAGOS An Asynchronous Parallel Genetic Optimisation Strategy". Procs. of the 3rd ICGA, J. D. Schaffer (ed.), Morgan Kaufmann, pp. 422-427. 1989.
    33. J. J. Grefenstette. "GENESIS: A System for Using Genetic Search Procedures". Proceedings of the 1984 Conference on Intelligent Systems and Machines, pp. 161-165. 1984.
    34. F. Herrera, M. Lozano, J. L. Verdegay. "Tackling Fuzzy Genetic Algorithms". Genetic Algorithms in Engineering and Computer Science, G. Winter, J. Périaux, M. Galán, P. Cuesta (eds.), John Wiley & Sons, pp 167-189. 1995.
    35. F. Hoffmeister. "The User’s Guide to ESCAPADE 1.2 A Runtime Environment for Evolution Strategies". Department of Computer Science, University of Dortmund, Germany. 1991.
    36. J. H. Holland. Adaptation in Natural and Artificial Systems. Univ. of Michigan Press, Ann Arbor, MI. 1975.
    37. M. Hughes. "Genetic Algorithm Workbench Documentation", Cambridge Consultants Ltd. 1989.
    38. A. Hunter. "Sugal Programming Manual v2.0". T. R. in Univ. Sunderland, U.K.. July 1995.
    39. B. A. Juslstrom. "What Have You Done for Me Lately? Adapting Operator Probabilities in a Steady-State Genetic Algorithm". Proceedings of the 6th International Conference on Genetic Algorithms, L. J. Eshelman (ed.), Morgan Kaufmann, pp 81-87. 1995.
    40. J. R. Koza. Genetic Programming. The MIT Press. 1992.
    41. T. Kuo, S. Y. Hwang. "A Genetic Algorithm with Disruptive Selection". Proceedings of the 5th International Conference on GAs, S. Forrest (ed.), Morgan Kaufmann, pp 65-69. 1993.
    42. D. Levine. "A Parallel Genetic Algorithm fot the Set Partitioning Problem". T. R. No. ANL-94/23, Argonne National Laboratory, Mathematics and Computer Science Division. 1994.
    43. D. Levine. "Users Guide to the PGAPack Parallel Genetic Algorithm Library". T. R. ANL-95/18, January 31. 1996.
    44. S. Lin, W. F. Punch and E. D. Goodman. "Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach". Parallel & Distributed Processing. October 1994.
    45. M. Lozano. "Application of Fuzzy Logic Based Techniques for Improving the Behavior of GAs with Floating Point Encoding". Ph.D. Th., Dpt. of C. S. and A.I., Univ. Granada. July 1996.
    46. B. Manderick, P. Spiessens. "Fine-Grained Parallel Genetic Algorithms". Procs. of the 3rd I. C. on Genetic Algorithms, J. D. Schaffer (ed.), Morgan Kaufmann, pp 428- 433. 1989.
    47. M. Mejía-Olvera, E. Cantú-Paz. "DGENESIS-Software for the Execution of Distributed Genetic Algorithms". Proceedings of the XX Conferencia Latinoamericana de Informática, pp 935-946, Monterrey, México. 1994.
    48. J. J. Merelo, A. Prieto. GAGS, "A Flexible Object-Oriented Library for Evolutionary Computation". Procs. of MALFO, D. Borrajo, P. Isasi (eds.), pp 99-105. 1996.
    49. Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag. 1992.
    50. H. Mühlenbein. "Evolution in Time and Space - The Parallel Genetic Algorithm". Foundations of Genetic Algorithms, G. J. E. Rawlins (ed.), Morgan Kaufmann, pp 316-337. 1991.
    51. H. Mühlenbein, M. Schomisch, J. Born. "The Parallel Genetic Algorithm as Function Optimizer". Parallel Computing, 17, pp 619-632. September 1991.
    52. M. Munetomo, Y. Takai, Y. Sato. "An Efficient Migration Scheme for Subpopulation-Based Asynchronously Parallel GAs". HIER-IS-9301, Hokkaido University. July 1993.
    53. T. Muntean, E. G. Talbi. "A Parallel Genetic Algorithm for Process-Processors Mapping". Proceedings of the Second Symposium II. High Performance Computing, M. Durán, E. Dabaghi (eds.), pp 71-82. Montpellier, France: F. Amsterdam, Amsterdam. 1991.
    54. NASA - Johnson Space Center. "Splicer - A Genetic Tool for Search and Optimization". Genetic Algorithm Digest, Vol 5, Issue 17. 1991.
    55. C. C. Pettey, M. R. Leuze, J. Grefenstette. "A Parallel Genetic Algorithm". Proceedings of the 2nd ICGA, J. Grefenstette (ed.), Lawrence Erlbraum Associates, pp 155-161. 1987.
    56. J. C. Potts, T. D. Giddens, S. B. Yadav. "The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial Selection". IEEE Transactions on Systems, Man, and Cybernetics, 24 (1), pp 73-86. January 1994.
    57. N. J. Radcliffe, P. D. Surry. "The Reproductive Plan Language RPL2: Motivation, Architecture and Applications". Genetic Algorithms in Optimisation, Simulation and Modelling, J. Stender, E. Hillebrand, J. Kingdon (eds.), IOS Press. 1994
    58. I. Rechenberg. Evolutionstrategie: Optimierung Technisher Systeme nach Prinzipien der Biologischen Evolution. Fromman-Holzboog Verlag, Sttutg. 1973.
    59. J. L. Ribeiro Filho, C. Alippi, P. Treleaven. "Genetic Algorithm Programming Environments". Parallel Genetic Algorithms: Theory & Applications, J. Stender (ed.), IOS Press. 1993.
    60. G. Robbins. "EnGENEer - The Evolution of Solutions". Proceedings of the 5th Annual Seminar on Neural Networks and Genetic Algorithms. 1992.
    61. N. N. Schraudolp, J. J. Grefenstette. "A User’s Guide to GAUCSD 1.2". T. R. Computer Science & Engineering Department, University of California, San Diego. 1991.
    62. H. P. Schwefel. Numerical Optimization of Computer Models. Wiley, Chichester. 1981.
    63. W. M. Spears, K. A. De Jong. "An Analysis of Multi-Point Crossover". Foundations of Genetic Algorithms, G. J. E. Rawlins (ed.), Morgan Kaufmann, pp 301-315. 1991.
    64. W. M. Spears. "Crossover or Mutation?". Proceedings of the Foundations of Genetic Algorithms Workshop, D. Whitley (ed.), Morgan Kaufmann, pp 221-237. 1992.
    65. P. Spiessens, B. Manderick. "A Massively Parallel Genetic Algorithm". Proceedings of the 4th International Conference on Genetic Algorithms, R. K. Belew, L. B. Booker (eds.), Morgan Kaufmann, pp 279-286. 1991.
    66. J. Stender (ed.). Parallel Genetic Algorithms: Theory and Applications. IOS Press. 1993.
    67. G. Syswerda. "A Study of Reproduction in Generational and Steady-State Genetic Algorithms"; Foundations of GAs, G. J. E. Rawlins (ed.), Morgan Kaufmann, pp 94-101. 1991.
    68. R. Tanese. "Distributed Genetic Algorithms". Proceedings of the 3rd International Conference on Genetic Algorithms, J. D. Schaffer (ed.), Morgan Kaufmann, pp 434-439. 1989.
    69. H. M. Voigt, J. Born, J. Treptow. "The Evolution Machine Manual - V 2.1". T. R. in the Institute for Informatics and Computing Techniques, Berlin. 1991.
    70. H. M. Voigt, I. Santibáñez-Koref, J. Born. "Hierarchically Structured Distributed Genetic Algorithms". Proceedings of the International Conference Parallel Problem Solving from Nature, 2, R. Männer, B. Manderick (eds.), North-Holland, Amsterdan, pp 155-164. 1992.
    71. M.Wall. "Overview of Matthew’s Genetic Algorithm Library". http://lancet.mit.edu/ga. 1995.
    72. D. Whitley. "The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best". Proceedings of the 3rd. International Conference on Genetic Algorithms, J. D. Schaffer (ed.), Morgan Kaufmann, pp 116-121. 1989.
    73. D. Whitley, T. Starkweather. "GENITOR II: a Distributed Genetic Algorithm". J. Expt. theor. Artif. Intelligence 2, pp 189-214. 1990.
     


    This page was last updated on 6-May-98