research-article

An efficient evolutionary algorithm for solving incrementally structured problems

Authors:

Saman Amarasinghe,

Una-May O'ReillyAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 1699 - 1706

https://doi.org/10.1145/2001576.2001805

Published: 12 July 2011 Publication History

Abstract

Many real world problems have a structure where small problem instances are embedded within large problem instances, or where solution quality for large problem instances is loosely correlated to that of small problem instances. This structure can be exploited because smaller problem instances typically have smaller search spaces and are cheaper to evaluate. We present an evolutionary algorithm, INCREA, which is designed to incrementally solve a large, noisy, computationally expensive problem by deriving its initial population through recursively running itself on problem instances of smaller sizes. The INCREA algorithm also expands and shrinks its population each generation and cuts off work that doesn't appear to promise a fruitful result. For further efficiency, it addresses noisy solution quality efficiently by focusing on resolving it for small, potentially reusable solutions which have a much lower cost of evaluation. We compare INCREA to a general purpose evolutionary algorithm and find that in most cases INCREA arrives at the same solution in significantly less time.

References

[1]

Akiko N. Aizawa and Benjamin W. Wah. Scheduling of genetic algorithms in a noisy environment. Evolutionary Computation, 2(2):97--122, 1994.

Digital Library

[2]

Ayaz Ali, Lennart Johnsson, and Jaspal Subhlok. Scheduling FFT computation on SMP and multicore systems. In Proceedings of the ACM/IEEE Conference on Supercomputing, pages 293--301, New York, NY, USA, 2007. ACM.

Digital Library

[3]

Jason Ansel, Cy Chan, Yee Lok Wong, Marek Olszewski, Qin Zhao, Alan Edelman, and Saman Amarasinghe. Petabricks: A language and compiler for algorithmic choice. In ACM SIGPLAN Conference on Programming Language Design and Implementation, Dublin, Ireland, Jun 2009.

Digital Library

[4]

Dirk V. Arnold and Hans-Georg Beyer. On the benefits of populations for noisy optimization. Evolutionary Computation, 11(2):111--127, 2003.

Digital Library

[5]

Thomas Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, New York NY, 1996.

Digital Library

[6]

Jeff Bilmes, Krste Asanovic, Chee-Whye Chin, and Jim Demmel. Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology. In Proceedings of the ACM/IEEE Conference on Supercomputing, pages 340--347, New York, NY, USA, 1997. ACM.

Digital Library

[7]

Jurgen Branke. Creating robust solutions by means of evolutionary algorithms. In Agoston Eiben, Thomas Baeck, Marc Schoenauer, and Hans-Paul Schwefel, editors, Parallel Problem Solving from Nature, PPSN V, volume 1498 of Lecture Notes in Computer Science, pages 119--. Springer Berlin / Heidelberg, 1998.

Digital Library

[8]

Jurgen Branke, Christian Schmidt, and Hartmut Schmec. Efficient fitness estimation in noisy environments. In Proceedings of Genetic and Evolutionary Computation, pages 243--250, 2001.

[9]

Erick Cantu-Paz. Adaptive sampling for noisy problems. In Genetic and Evolutionary Computation, GECCO 2004, volume 3102 of Lecture Notes in Computer Science, pages 947--958. Springer Berlin / Heidelberg, 2004.

[10]

Matteo Frigo and Steven G. Johnson. The design and implementation of FFTW3. Proceedings of the IEEE, 93(2):216--231, February 2005. Invited paper, special issue on "Program Generation, Optimization, and Platform Adaptation".

[11]

Steven M. Gustafson and William H. Hsu. Layered learning in genetic programming for a co-operative robot soccer problem. In Julian F. Miller, Marco Tomassini, Pier Luca Lanzi, Conor Ryan, Andrea G. B. Tettamanzi, and William B. Langdon, editors, Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, pages 291--301, Lake Como, Italy, 18--20 April 2001. Springer-Verlag.

Digital Library

[12]

Eun-jin Im and Katherine Yelick. Optimizing sparse matrix computations for register reuse in SPARSITY. In Proceedings of the International Conference on Computational Science, pages 127--136. Springer, 2001.

Digital Library

[13]

Carol A. Markowski and Edward P. Markowski. Conditions for the effectiveness of a preliminary test of variance. 1990.

[14]

Markus Püschel, José M. F. Moura, Bryan Singer, Jianxin Xiong, Jeremy R. Johnson, David A. Padua, Manuela M. Veloso, and Robert W. Johnson. Spiral: A generator for platform-adapted libraries of signal processing alogorithms. IJHPCA, 18(1):21--45, 2004.

Digital Library

[15]

Peter Stone and Manuela Veloso. Layered learning. In Ramon Lopez de Montaras and Enric Plaza, editors, Machine Learning: ECML 2000, volume 1810 of Lecture Notes in Computer Science, pages 369--381. Springer Berlin / Heidelberg, 2000.

Digital Library

[16]

Astro Teller and David Andre. Automatically choosing the number of fitness cases: The rational allocation of trials. In John R. Koza, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max Garzon, Hitoshi Iba, and Rick L. Riolo, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 321--328, Stanford University, CA, USA, 13--16 July 1997. Morgan Kaufmann.

[17]

Richard Vuduc, James W. Demmel, and Katherine A. Yelick. OSKI: A library of automatically tuned sparse matrix kernels. In Proceedings of the Scientific Discovery through Advanced Computing Conference, Journal of Physics: Conference Series, San Francisco, CA, USA, June 2005. Institute of Physics Publishing.

[18]

Richard Clint Whaley and Jack J. Dongarra. Automatically tuned linear algebra software. In ACM/IEEE Conference on Supercomputing, pages 1--27, Washington, DC, USA, 1998. IEEE Computer Society.

Digital Library

Cited By

Roy RPatel TGadepally VTiwari DFreund SYahav E(2021)Bliss: auto-tuning complex applications using a pool of diverse lightweight learning modelsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454109(1280-1295)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454109
Ding YAnsel JVeeramachaneni KShen XO’Reilly UAmarasinghe S(2015)Autotuning algorithmic choice for input sensitivityACM SIGPLAN Notices10.1145/2813885.273796950:6(379-390)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737969
Ding YAnsel JVeeramachaneni KShen XO’Reilly UAmarasinghe SGrove DBlackburn S(2015)Autotuning algorithmic choice for input sensitivityProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737969(379-390)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737969
Show More Cited By

Index Terms

An efficient evolutionary algorithm for solving incrementally structured problems
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. Context specific languages

Recommendations

Configuring two-algorithm-based evolutionary approach for solving dynamic economic dispatch problems

A dynamic economic dispatch (DED) problem is a complex constrained optimization problem that has the objective of economically allocating power demands to the available generators for a certain period. Although, over the last few decades, different ...
A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search ...
A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
160
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roy RPatel TGadepally VTiwari DFreund SYahav E(2021)Bliss: auto-tuning complex applications using a pool of diverse lightweight learning modelsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454109(1280-1295)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454109
Ding YAnsel JVeeramachaneni KShen XO’Reilly UAmarasinghe S(2015)Autotuning algorithmic choice for input sensitivityACM SIGPLAN Notices10.1145/2813885.273796950:6(379-390)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737969
Ding YAnsel JVeeramachaneni KShen XO’Reilly UAmarasinghe SGrove DBlackburn S(2015)Autotuning algorithmic choice for input sensitivityProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737969(379-390)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737969
Ansel JKamil SVeeramachaneni KRagan-Kelley JBosboom JO'Reilly UAmarasinghe SAmaral JTorrellas J(2014)OpenTunerProceedings of the 23rd international conference on Parallel architectures and compilation10.1145/2628071.2628092(303-316)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2628071.2628092
Tartara MCrespi Reghizzi S(2013)Continuous learning of compiler heuristicsACM Transactions on Architecture and Code Optimization10.1145/2400682.24007059:4(1-25)Online publication date: 20-Jan-2013
https://dl.acm.org/doi/10.1145/2400682.2400705
Tartara MCrespi Reghizzi SFedak GFox GDelamare S(2012)Parallel iterative compilationProceedings of third international workshop on MapReduce and its Applications Date10.1145/2287016.2287023(33-40)Online publication date: 18-Jun-2012
https://dl.acm.org/doi/10.1145/2287016.2287023

View Options

Get Access

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