Abstract
In this paper we investigate the design of highly parallel Genetic Algorithms. The Traveling Salesman Problem is used as a case study to evaluate and compare different implementations. To fix the various parameters of Genetic Algorithms to the case study considered, the Holland sequential Genetic Algorithm, which adopts different population replacement methods and crossover operators, has been implemented and tested. Both fine-grained and coarse-grained parallel GAs which adopt the selected genetic operators have been designed and implemented on a 128-node nCUBE 2 multicomputer. The fine-grained algorithm uses an innovative mapping strategy that makes the number of solutions managed independent of the number of processing nodes used. Complete performance results showing the behaviour of Parallel Genetic Algorithms for different population sizes, number of processors used, migration strategies are reported.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bianchini, R., Brown, C.M.: Parallel genetic algorithm on distributed-memory architectures. Technical Report TR 436, Computer Sciences Department University of Rochester (1993)
Cohoon, S., Hedge, J., Martin, S., Richards, D.: Punctuated equilibria: a parallel genetic algorithm. IEEE Transaction on CAD 10(4), 483–491 (1991)
Cantu-Paz, E.: A summary of research on parallel genetic algoritms. Technical Report 95007, University of Illinois at Urbana-Champaign, Genetic Algoritms Lab. (IlliGAL) (July 1995), http://gal4.ge.uiuc.edu/illigal.home.html
Cohoon, S., Hedge, J., Martin, S., Richards, D.: Punctuated equilibria: a parallel genetic algorithm. IEEE Transaction on CAD 10(4), 483–491 (1991)
Dorigo, M., Maniezzo, V.: Parallel genetic algorithms: Introduction and overview of current research. In: Parallel Genetic Algorithms, pp. 5–42. IOS Press, Amsterdam (1993)
Garey, M.R., Jonshon, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Goldberg, D., Lingle, R.: Alleles, loci, and the tsp. In: Proc. of the First International Conference on Genetic Algorithms, pp. 154–159 (1985)
Gorges-Schleuter, M.: Explicit parallelism of genetic algorithms through population structures. In: Schwefel, H.-P., Männer, R. (eds.) PPSN 1990. LNCS, vol. 496, pp. 398–406. Springer, Heidelberg (1991)
Gorges-Schleuter, M.: Genetic Algoritms and Population Structure. PhD thesis, University of Dortmund (1991)
Grosso, P.: Computer Simulations of Genetic Adaptation: Parallel Subcomponent Interaction in a Multilocus Model. PhD thesis, University of Michigan (1985)
Holland, J.: Adaptation in Natural and Artificial Systems. Univ. of Mitchigan Press (1975)
Holland, J.H.: Algoritmi genetici. Le Scienze 289, 50–57 (1992)
De Jong, K.A.: An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan (1975)
Manderick, B., Spiessens, P.: Fine-grained parallel genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 428–433. Morgan Kaufmann Publishers, San Francisco (1989)
Muhlenbein, H.: Parallel genetic algorithms, population genetic and combinatorial optimization. In: Schwefel, H.-P., Männer, R. (eds.) PPSN 1990. LNCS, vol. 496, pp. 407–417. Springer, Heidelberg (1991)
Muhlenbein, H., Schomisch, M., Born, J.: The parallel genetic algorithm as function optimizer. Parallel Computing 17, 619–632 (1991)
nCUBE Corporation. ncube2 processor manual (1990)
Pettey, C., Lenze, M., Grefenstette, J.: A parallel genetic algorithm. In: Proceedings of the Second International Conference on Genetic Algorithms, pp. 155–161. L. Erlbaum Associates, Mahwah (1987)
Schwehm, M.: Implementation of genetic algorithms on various interconnections networks. Parallel Computing and Transputer applications, 195–203 (1992)
Tanese, R.: Parallel genetic algorithms for a hypercube. In: Proceedings of the Second International Conference on Genetic Algorithms, pp. 177–183. L. Erlbaum Associates, Mahwah (1987)
Tanese, R.: Distributed genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, pp. 434–440. M. Kaufmann, San Francisco (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baraglia, R., Perego, R. (1999). Parallel Genetic Algorithms for Hypercube Machines. In: Hernández, V., Palma, J.M.L.M., Dongarra, J.J. (eds) Vector and Parallel Processing – VECPAR’98. VECPAR 1998. Lecture Notes in Computer Science, vol 1573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10703040_52
Download citation
DOI: https://doi.org/10.1007/10703040_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66228-0
Online ISBN: 978-3-540-48516-2
eBook Packages: Springer Book Archive
Keywords
- Genetic Algorithm
- Travelling Salesman Problem
- Travel Salesman Problem
- Crossover Operator
- Point Crossover
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.