Skip to main content
SpringerLink
Log in

Improving flexibility and efficiency by adding parallelism to genetic algorithms

  • Published:
Statistics and Computing Aims and scope Submit manuscript

Abstract

In this paper we develop a study on several types of parallel genetic algorithms (PGAs). Our motivation is to bring some uniformity to the proposal, comparison, and knowledge exchange among the traditionally opposite kinds of serial and parallel GAs. We comparatively analyze the properties of steady-state, generational, and cellular genetic algorithms. Afterwards, this study is extended to consider a distributed model consisting in a ring of GA islands. The analyzed features are the time complexity, selection pressure, schema processing rates, efficacy in finding an optimum, efficiency, speedup, and resistance to scalability. Besides that, we briefly discuss how the migration policy affects the search. Also, some of the search properties of cellular GAs are investigated. The selected benchmark is a representative subset of problems containing real world difficulties. We often conclude that parallel GAs are numerically better and faster than equivalent sequential GAs. Our aim is to shed some light on the advantages and drawbacks of various sequential and parallel GAs to help researchers using them in the very diverse application fields of the evolutionary computation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adamidis P. 1994. Review of parallel genetic algorithms bibliography (v1.0). T.R., Aristotle University of Thessaloniki. available at http://www.control,ee.auth.gr/∼panos/papers/pga_review.ps.gz).

  • Adamidis P. and Petridis V. 1996. Co-operating populations with different evolution behavior. In: Proceedings of the Second IEEE Conference on Evolutionary Computation. pp. 188-191

  • Akl S.G. 1992. The Design and Analysis of Parallel Algorithms. Prentice Hall, Englewood Cliffs, NJ.

    Google Scholar 

  • Alba E., Aldana J.F., and Troya J.M. 1993. Genetic algorithms as heuristics for optimizing ANN design. In: Albrecht R.F., Reeves C.R., and Steele N.C. (Eds.), Artificial Neural Nets and Genetic Algorithms. Springer-Verlag, Berlin, pp. 683-690.

    Google Scholar 

  • Alba E., Aldana J.F., and Troya J.M. 1995. A genetic algorithm for load balancing in parallel query evaluation for deductive relational databases. In: Pearson D.W., Steele N.C., and Albrecht R.F. (Eds.), Artificial Neural Nets and Genetic Algorithms. Springer-Verlag, Berlin, pp. 479-482

    Google Scholar 

  • Alba E., Cotta C., and Troya J.M. 1996. Type-constrained genetic programming for rule-base definition in fuzzy logic controllers. In: Koza J.R., Goldberg D.E., Fogel D.B., and Riolo R.L. (Eds.), Proceedings of the First Annual Conference on Genetic Programming. MIT Press, Cambridge, MA, pp. 255-260

    Google Scholar 

  • Alba E., Cotta C., and Troya J.M. 2000. On the importance of the grid shape in 2D spatially structured GAs. Journal of Evolutionary Optimization, to appear.

  • Alba E. and Troya J.M. 1996. Genetic algorithms for protocol validation. In: Voigt H.M., Ebeling W., Rechenberg I., and Schwefel H.P. (Eds.), Proceedings of the Parallel Problem Solving from Nature IV. Springer-Verlag, Berlin, pp. 870-879.

    Google Scholar 

  • Alba E. and Troya J.M. 1999. A survey of parallel distributed genetic algorithms. Complexity 4(4): 31-52.

    Google Scholar 

  • Alba E. and Troya J.M. 2000a. Influence of the migration policy in parallel distributed GAs with structured and panmictic populations. Applied Intelligence 12(3): 163-181.

    Google Scholar 

  • Alba E. and Troya J.M. 2000b. Cellular evolutionary algorithms: Evaluating the influence of ratio. In: Schoenauer M. et al. (Eds.), Proceedings of the Parallel Problem Solving from Nature VI, Springer-Verlag, Berlin, pp. 29-38.

    Google Scholar 

  • Alba E. and Troya J.M. 2001. Analyzing synchronous and asynchronous parallel distributed genetic algorithms. Future Generation Computer Systems, FGCS 17(4): 451-465.

    Google Scholar 

  • Alba E. 2002. Parallel evolutionary algorithms can achieve super-linear performance. Information Processing Letters, Elsevier 82(1): 7-13.

    Google Scholar 

  • Antonisse J. 1989. A new interpretation of schema notion that overturns the binary encoding constraint. In: Schaffer J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 86-91.

    Google Scholar 

  • Bäck T. 1996. Evolutionary Algorithms in Theory and Practice. Oxford University Press, London. Bäck T., Fogel D.,and Michalewicz Z. (Eds.) 1997. Handbook of Evolutionary Computation. Oxford University Press, London.

    Google Scholar 

  • Bäck T., Graaf J.M., Kok J.N., and Kosters W.A. 1997. Theory of genetic algorithms. Bulletin of the European Association for Theoretical Computer Science 63: 161-192.

    Google Scholar 

  • Bäck T., Hammel U., and Schwefel H.P. 1997. Evolutionary computation: Comments on the history and currrent state. IEEE Transactions on Evolutionary Computation 1(1): 3-17.

    Google Scholar 

  • Baker, J.E. 1987. Reducing bias and inefficiency in the selection algorithm. In: Grefenstette J.J. (Ed.), Proceedings of the Second International Conference on Genetic Algorithms. Lawrence Erlbaum Associates Publishers, pp. 14-21.

  • Baluja S. 1993. Structure and performance of fine-grain parallelism in genetic search. In: Forrest S. (Ed.), Proceedings of the Fith International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 155-162.

    Google Scholar 

  • Belding T.C. 1995. The distributed genetic algorithm revisited. In: Eshelman L.J. (Ed.), Proceedings of the Sixth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo,CA, pp. 114-121.

    Google Scholar 

  • Cammarata G., Cavalieri S., Fichera A., and Marletta L. 1993. Noise prediction in urban traffic by a neural approach. In: Mira J., Cabestany J., and Prieto A. (Eds.), Procedings of the International Workshop on Artificial Neural Networks. Springer-Verlag, Berlin, pp. 611-619.

    Google Scholar 

  • CantÚ-Paz E. 1997. A survey of parallel GAs. IlliGAL R. 97003.A revised version of 1995. Asummary of research on parallel genetic algorithms. TR#95007.

  • CantÚ-Paz E. and Goldberg D.E. 1997. Predicting speedups of idealized bounding cases of parallel genetic algorithms. In: Bäck T. (Ed.), Proceedings of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 113-120.

    Google Scholar 

  • Davidor Y. 1991. A naturally occurring niche & species phenomenon: The model and first results. In: Belew R.K. and Booker L.B. (Eds.), Procs. of the 4th ICGA, pp. 257-263.

  • Deb K. and Spears W.M. 1997. Speciation methods. In: Bäck T., Fogel D.B., and Michalewicz Z. (Eds.), Handbook of Evolutionary Computation. Oxford University Press, London, pp. C6.2: 1-C6.2:5.

    Google Scholar 

  • De Jong K.A., Potter M.A., and Spears W.M. 1997. Using problem generators to explore the effects of epistasis. In: Bäck T. (Ed.), Proceedings of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo,CA, pp. 338-345.

    Google Scholar 

  • De Jong K. and Sarma J. 1995. On decentralizing selection algorithms. In: Eshelman L.J. (Ed.), Proceedings of the Sixth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 17-23.

    Google Scholar 

  • East I.R. and Mcfarlane D. 1993. Implementation in occam of parallel genetic algorithms on transputer networks. In: Stender J. (Ed.), Parallel Genetic Algorithms. IOS Press, pp. 43-63.

  • Erickson J.A., Smith R.E., and Goldberg D.E. 1991. SGA-Cube, a simple genetic algorithm for ncube 2 hypercube parallel computers. TCGA Report #91005. The University of Alabama.

  • Goldberg D.E. 1989a. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA.

    Google Scholar 

  • Goldberg D.E. 1989b. Sizing populations for serial and parallel genetic algorithms. In: Schaffer J.D. (Ed.), Proceedings of the Third Inter-national Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 70-79.

    Google Scholar 

  • Goodman E.D. 1996. 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.

    Google Scholar 

  • Gordon V.S. and Whitley D. 1993. Serial and parallel genetic algorithms as function optimizers. In: Forrest S. (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 177-183.

    Google Scholar 

  • Gorges-Schleuter M. 1989. ASPARAGOS an asynchronous parallel genetic optimisation strategy. In: Schaffer J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 422-427.

    Google Scholar 

  • Hart W.E., Baden S., Belew R.K., and Kohn S. 1997. Analysis of the numerical effects of parallelism on a parallel genetic algorithm. Proceedings of the Workshop on Solving Combinatorial Optimization Problems in Parallel. IEEE (Ed.), CD-ROM IPPS97.

  • Herrera F. and Lozano M. 2000. Gradual distributed real-coded genetic algorithms. IEEE Transactions on Evolutionary Computation 4(1): 43-63.

    Google Scholar 

  • Holland J. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.

    Google Scholar 

  • Kung S.Y. 1993. Digital Neural Networks. Prentice Hall, Englewood Cliffs, NJ.

    Google Scholar 

  • Levine D. 1994. A parallel genetic algorithm for the set partitioning problem. TR#ANL-94/23. Argonne National Laboratory, Mathematics and Computer Science Division.

  • Levine D. 1996. Users guide to the PGAPack parallel genetic algorithm library. TR# ANL-95/18.

  • Levine D. 1997. Genetic algorithms: A practitioner's view. INFORMS Journal of Computing 9(3): 256-259.

    Google Scholar 

  • Lin S., Punch W.F., and Goodman E.D. 1994. Coarse-grain parallel genetic algorithms: Categorization and new approach. Sixth IEEE SPDP, pp. 28-37.

  • Maruyama T., Hirose T., and Konagaya A. 1993. Afine-grained parallel genetic algorithm for distributed parallel systems. In: Forrest S. (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 184-190.

    Google Scholar 

  • Mejía-Olvera M. and CantÚ-Paz E. 1994. DGENESIS-software for the execution of distributed genetic algorithms. In Proceedings of the XX Latinoamerican Conference on Computer Science. Monterrey, México. pp. 935-946.

    Google Scholar 

  • Menke R. 1997. A revision of the schema theorem. TR#14/97. University of Dortmund.

  • Michalewicz Z. 1992. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin.

    Google Scholar 

  • Mühlenbein H., Schomisch M., and Born J. 1991. The parallel genetic algorithm as function optimizer. Parallel Computing 17: 619-632.

    Google Scholar 

  • Munetomo M., Takai Y., and Sato Y. 1993. An efficient migration scheme for subpopulation-based asynchronously parallel GAs. TR#HIER-IS-9301. Hokkaido University.

  • Poli R. 1999. Probabilistic schema theorems without expectation, left-to-right convergence and population sizing in genetic algorithms. TR#CSRP-99-3. University of Birmingham, School of Computer Science.

  • Potts J.C., Giddens T.D., and Yadav S.B. 1994. The development and evaluation of an improved genetic algorithm based on migration and artificial selection. IEEE Transactions on Systems, Man, and Cybernetics 24(1): 73-86.

    Google Scholar 

  • Radcliffe N.J. and Surry P.D. 1994. The reproductive plan language RPL2: Motivation, architecture and applications. In: Stender J., Hillebrand E., and Kingdon J. (Eds.), Genetic Algorithms in Optimisation, Simulation and Modelling. IOS Press.

  • Reeves C.R. (Ed.), 1993. Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications, Oxford.

    Google Scholar 

  • Ribeiro Filho J.L., Alippi C., and Treleaven P. 1993. Genetic algorithm programming environments. In: Stender J. (Ed.), Parallel GAs: Theory & Applications, IOS Press.

  • Robbins G. 1992. EnGENEer—The evolution of solutions. In Proceedings of the 5th Annual Seminar on Neural Networks and Genetic Algorithms.

  • Rogers A. and Prügel-Bennett A. 1999. Genetic drift in genetic algorithm selection schemes. IEEE Transactions on Evolutionary Computation 3(4): 298-303.

    Google Scholar 

  • Sarma J. and De Jong K.A. 1996. An analysis of the effects of neigh-borhood size and shape on local selection algorithms. In: Voigt H.M., Ebeling W., Rechenberg I., and Schwefel H.P. (Eds.), Parallel Problem Solving from Nature IV. Springer-Verlag, Berlin, pp. 236-244.

    Google Scholar 

  • Sarma J. and De Jong K. 1997. An analysis of local selection algorithms in a spatially structured evolutionary algorithm. In: Bäck T. (Ed.), Proceedings of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 181-186.

    Google Scholar 

  • Shonkwiler R. 1993. Parallel genetic algorithms. In: Forrest S. (Ed.), Proceedings of the Fifth ICGA. Morgan Kaufmann, San Mateo, CA, pp. 199-205.

    Google Scholar 

  • Spiessens P. and Manderick B. 1991. A massively parallel genetic algorithm. In: Belew R.K. and Booker L.B. (Eds.), Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 279-286.

    Google Scholar 

  • Stender J. (Ed.), 1993. Parallel Genetic Algorithms: Theory and Applications. IOS Press.

  • Syswerda G. 1991. A study of reproduction in generational and steady-state genetic algorithms. In: Rawlins G.J.E. (Ed.), Foundations of Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 94-101.

    Google Scholar 

  • Tanese R. 1989. Distributed genetic algorithms. In: Schaffer J.D. (Ed.), Proceedings of the 3rd International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA, pp. 434-439.

    Google Scholar 

  • Voigt H.M., Santibáñez-Koref I. and Born J. 1992. Hierarchically structured distributed genetic algorithms. In: Männer R. and Manderick B. (Eds.), Proceedings of the International Conference Parallel Problem Solving from Nature 2. North-Holland, Amsterdam, pp. 155-164.

    Google Scholar 

  • Whitley D. 1993. A Genetic Algorithm Tutorial. TR#CS-93-103 (re-vised version). Department of Computer Science, Colorado State University.

  • Whitley D. and Schaffer J.D. (Eds.), 1992. Proceedings of COGANN-92: International Workshop on Combinations of Genetic Algorithms and Neural Networks. IEEE Computer Society Press.

  • Whitley D. and Starkweather T. 1990. GENITOR II: A distributed genetic algorithm. Journal Expt. Theory Artificial Intelligence 2: 189-214.

    Google Scholar 

  • Wolpert D.H. and Macready W.G. 1997. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1(1): 67-82.

    Google Scholar 

Download references

Authors
  1. Enrique Alba
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José M. Troya
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Alba, E., Troya, J.M. Improving flexibility and efficiency by adding parallelism to genetic algorithms. Statistics and Computing 12, 91–114 (2002). https://doi.org/10.1023/A:1014803900897

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1014803900897

Search

Navigation