research-article

Data-intensive computing for competent genetic algorithms: a pilot study using meandre

Author:

Xavier LloràAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 1387 - 1394

https://doi.org/10.1145/1569901.1570087

Published: 08 July 2009 Publication History

Abstract

Data-intensive computing has positioned itself as a valuable programming paradigm to efficiently approach problems requiring processing very large volumes of data. This paper presents a pilot study about how to apply the data-intensive computing paradigm to evolutionary computation algorithms. Two representative cases (selectorecombinative genetic algorithms and estimation of distribution algorithms) are presented, analyzed, and discussed. This study shows that equivalent data-intensive computing evolutionary computation algorithms can be easily developed, providing robust and scalable algorithms for the multicore-computing era. Experimental results show how such algorithms scale with the number of available cores without further modification.

References

[1]

Alba, E., Ed. Parallel Metaheuristics. Wiley, 2007.

[2]

Amdahl, G. Validity of the single processor approach to achieving large-scale computing capabilities. In AFIPS Conference Proceedings (1967), pp. 483--485.

Digital Library

[3]

Beckett, D. RDF/XM Syntax Specification (Revised). W3C Recommendation 10 February 2004, The World Wide Web Consortium, 2004.

[4]

Beynon, M.D., Kurc, T., Sussman, A., and Saltz, J. Design of a framework for data-intensive wide-area applications. In HCW '00: Proceedings of the 9th Heterogeneous Computing Workshop (Washington, DC, USA, 2000), IEEE Computer Society, p. 116.

Digital Library

[5]

Brickley, D., and Guha, R. RDF Vocabulary Description Language 1.0: RDF Schema. W3C Recommendation 10 February 2004, The World Wide Web Consortium, 2004.

[6]

Cantú-Paz, E. Efficient and Accurate Parallel Genetic Algorithms. Springer, 2000.

Digital Library

[7]

De Jong, K., and Sarma, J. On decentralizing selection algorithms. In Proceedings of the Sixth International Conference on Genetic Algorithms (1995), Morgan Kaufmann, pp. 17--23.

Digital Library

[8]

Dean, J., and Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters. In OSDI'04: Sixth Symposium on Operating System Design and Implementation (2004).

Digital Library

[9]

Foster, I. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison Wesley, 1995.

Digital Library

[10]

Foster, I. The virtual data grid: A new model and architecture for data-intensive collaboration. In in the 15th International Conference on Scientific and Statistical Database Management (2003), pp. 11--.

Digital Library

[11]

Giacobini, M., Tomassini, M., and Tettamanzi, A. Takeover time curves in random and small-world structured populations. In GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary computation (New York, NY, USA, 2005), ACM, pp. 1333--1340.

Digital Library

[12]

Goldberg, D.E. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, MA, 1989.

Digital Library

[13]

Goldberg, D.E. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, 2002.

Digital Library

[14]

Goldberg, D.E., Deb, K., and Clark, J.H. Genetic algorithms, noise, and the sizing of populations. Complex Systems 6 (1992), 333--362.

[15]

Goldberg, D.E., Korb, B., and Deb, K. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems 3, 5 (1989), 493--530.

[16]

Harik, G.R., Lobo, F.G., and Sastry, K. Linkage learning via probabilistic modeling in the ECGA. In Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, M. Pelikan, K. Sastry, and E. Cantú-Paz, Eds. Springer, Berlin, in press, ch. 3.

[17]

Larrañaga, P., and Lozano, J.A., Eds. Estimation of Distribution Algorithms. Kluwer Academic Publishers, Boston, MA, 2002.

[18]

Llorà, X. E2K: evolution to knowledge. SIGEVOlution 1, 3 (2006), 10--17.

Digital Library

[19]

Llorà, X. Genetic Based Machine Learning using Fine-grained Parallelism for Data Mining. PhD thesis, Enginyeria i Arquitectura La Salle. Ramon Llull University, Barcelona, February, 2002.

[20]

Llorà, X., Ács, B., Auvil, L., Capitanu, B., Welge, M., and Goldberg, D. E. Meandre: Semantic-driven data-intensive flows in the clouds. In Proceedings of the 4th IEEE International Conference on e-Science (2008), IEEE press, pp. 238--245.

Digital Library

[21]

Mattmann, C.A., Crichton, D.J., Medvidovic, N., and Hughes, S. A software architecture-based framework for highly distributed and data intensive scientific applications. In ICSE '06: Proceedings of the 28th international conference on Software engineering (New York, NY, USA, 2006), ACM, pp. 721--730.

Digital Library

[22]

Morrison, J.P. Flow-Based Programming: A New Approach to Application Development. Van Nostrand Reinhold, 1994.

[23]

Pelikan, M., Goldberg, D.E., and Cantú-Paz, E. Linkage learning, estimation distribution, and Bayesian networks. Evolutionary Computation 8, 3 (2000), 314--341.

Digital Library

[24]

Pelikan, M., Lobo, F., and Goldberg, D.E. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications 21 (2002), 5--20. (Also IlliGAL Report No. 99018).

Digital Library

[25]

Sarma, J., and De Jong, K. An analysis of local selection algorithms in a spatially structured evolutionary algorithm. In Proceedings of the Seventh International Conference on Genetic Algorithms (1997), Morgan Kaufmann, pp. 181--186.

[26]

Sarma, J., and De Jong, K. Selection pressure and performance in spatially distributed evolutionary algorithms. In Proceedings of the World Congress on Computatinal Intelligence (1998), IEEE Press, pp. 553--557.

[27]

Sastry, K., and Goldberg, D.E. Designing competent mutation operators via probabilistic model building of neighborhoods. Proceedings of the Genetic and Evolutionary Computation Conference 2 (2004), 114--125.

[28]

Sywerda, G. Uniform crossover in genetic algorithms. In Proceedings of the third international conference on Genetic algorithms (San Francisco, CA, USA, 1989), Morgan Kaufmann Publishers Inc., pp. 2--9.

Digital Library

[29]

Uysal, M., Kurc, T.M., Sussman, A., and Saltz, J. A performance prediction framework for data intensive applications on large scale parallel machines. In 4th Wkshp. on Languages, Compilers and Run-time Systems for Scalable Computers, Lecture Notes in Computer Science No 1511 (1998), Springer-Verlag, pp. 243--258.

Digital Library

[30]

Weibel, S., Kunze, J., Lagoze, C., and Wolf, M. Dublin Core Metadata for Resource Discovery. Tech. Rep. RFC2413, The Dublin Core Metadata Initiative, 2008.

Digital Library

[31]

Welge, M., Auvil, L., Shirk, A., Bushell, C., Bajcsy, P., Cai, D., Redman, T., Clutter, D., Aydt, R., and Tcheng, D. Data to Knowledge (D2K). Tech. rep., Technical Report Automated Learning Group, National Center for Supercomputing Applications, UIUC, 2003.

Cited By

Merelo JMora AFernandes CEsparcia-Alcázar A(2013)Designing and testing a pool-based evolutionary algorithmNatural Computing: an international journal10.1007/s11047-012-9338-512:2(149-162)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s11047-012-9338-5
Bacardit JLlorí X(2013)Large-scale data mining using genetics-based machine learningWiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery10.1002/widm.10783:1(37-61)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1002/widm.1078
Merelo JFernandes CMora AEsparcia AMoore J(2012)SofEAProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330802(109-116)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330802
Show More Cited By

Index Terms

Data-intensive computing for competent genetic algorithms: a pilot study using meandre
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Data flow languages

Recommendations

Neural network crossover in genetic algorithms using genetic programming
Abstract
The use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...
Using messy genetic algorithms for solving the winner determination problem
GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

The paper presents a study on the application of messy genetic algorithms for the winner determination problem in the combinatorial auction realm. Messy genetic algorithms operate explicitly on building blocks in order to obtain good solutions. Since ...
Genetic algorithms for task scheduling problem

The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several genetic algorithms have been developed to solve this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
221
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Merelo JMora AFernandes CEsparcia-Alcázar A(2013)Designing and testing a pool-based evolutionary algorithmNatural Computing: an international journal10.1007/s11047-012-9338-512:2(149-162)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s11047-012-9338-5
Bacardit JLlorí X(2013)Large-scale data mining using genetics-based machine learningWiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery10.1002/widm.10783:1(37-61)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1002/widm.1078
Merelo JFernandes CMora AEsparcia AMoore J(2012)SofEAProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330802(109-116)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330802
Verma ALlora XVenkataraman SGoldberg DCampbell R(2010)Scaling eCGA model building via data-intensive computingIEEE Congress on Evolutionary Computation10.1109/CEC.2010.5586468(1-8)Online publication date: Jul-2010
https://doi.org/10.1109/CEC.2010.5586468
Verma ALlorà XGoldberg DCampbell R(2009)Scaling Genetic Algorithms Using MapReduceProceedings of the 2009 Ninth International Conference on Intelligent Systems Design and Applications10.1109/ISDA.2009.181(13-18)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.1109/ISDA.2009.181

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents