research-article

Achieving COSMOS: a metric for determining when to give up and when to reach for the stars

Authors:

Lee SpectorAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Pages 417 - 424

https://doi.org/10.1145/2330784.2330848

Published: 07 July 2012 Publication History

Abstract

The utility of current metrics used in genetic programming (GP) systems, such as computational effort and mean-best-fitness, varies depending upon the problem and the resource that needs to be optimized. Inferences about the underlying system can only be made when a sufficient number of runs are performed to estimate the relevant metric within some confidence interval. This paper proposes a new algorithm for determining the minimum number of independent runs needed to make inferences about a GP system. As such, we view our algorithm as a meta-metric that should be satisfied before any inferences about a system are made. We call this metric COSMOS, as it estimates the number of independent runs needed to achieve the Convergence Of Sample Means Of the Order Statistics. It is agnostic to the underlying GP system and can be used to evaluate extant performance metrics, as well as problem difficulty. We suggest ways for which COSMOS may be used to identify problems for which GP may be uniquely qualified to solve.

References

[1]

P. J. Angeline. An investigation into the sensitivity of genetic programming to the frequency of leaf selection during subtree crossover. In Proceedings of the First Annual Conference on Genetic Programming, GECCO '96, pages 21--29, Cambridge, MA, USA, 1996. MIT Press.

Digital Library

[2]

D. F. Barrero, B. Castano, M. D. R-Moreno, and D. Camacho. Statistical distribution of generation-to-success in gp: application to model accumulated success probability. In Proceedings of the 14th European conference on Genetic programming, EuroGP'11, pages 154--165, Berlin, Heidelberg, 2011. Springer-Verlag.

Digital Library

[3]

G. Casella and R. L. Berger. Statistical Inference. Duxbury Press, 2nd edition, June 2001.

[4]

D. Costelloe and C. Ryan. On improving generalisation in genetic programming. In Proceedings of the 12th European Conference on Genetic Programming, EuroGP '09, pages 61--72, Berlin, Heidelberg, 2009. Springer-Verlag.

Digital Library

[5]

J. M. Daida, D. S. Ampy, M. Ratanasavetavadhana, H. Li, and O. A. Chaudhri. Challenges with verification, repeatability, and meaningful comparison in genetic programming: Gibson's magic. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 2 of GECCO '99, pages 1851--1858, Orlando, FL, USA, 1999. Morgan Kaufmann.

[6]

J. M. Daida, R. R. Bertram, S. A. Stanhope, J. C. Khoo, S. A. Chaudhary, O. A. Chaudhri, and J. A. I. Polito. What makes a problem gp-hard? analysis of a tunably difficult problem in genetic programming. Genetic Programming and Evolvable Machines, 2(2):165--191, June 2001.

Digital Library

[7]

R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification (2nd Edition). Wiley-Interscience, 2nd edition, Nov. 2001.

Digital Library

[8]

B. Efron. Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1):1--26, 1979.

[9]

J. R. Koza. Genetic programming: On the programming of computers by means of natural selection. Complex adaptive systems. MIT Press, 1993.

Digital Library

[10]

S. Luke. Ecj : An evolutionary computation research system in java.

[11]

S. Luke. When short runs beat long runs. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 74--80, San Francisco, California, USA, 7--11 July 2001. Morgan Kaufmann.

[12]

S. Luke and L. Panait. Is the perfect the enemy of the good? In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '02, pages 820--828, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.

Digital Library

[13]

J. Niehaus and W. Banzhaf. More on computational effort statistics for genetic programming. In Proceedings of the 6th European conference on Genetic programming, EuroGP'03, pages 164--172, Berlin, Heidelberg, 2003. Springer-Verlag.

Digital Library

[14]

N. Paterson and M. Livesey. Performance comparison in genetic programming. In Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, pages 253--260, Las Vegas, Nevada, USA, 2000.

[15]

N. P. Troutman, B. E. Eskridge, and D. F. Hougen. Is "best-so-far" a good algorithmic performance metric? In Proceedings of the 10th annual conference on Genetic and evolutionary computation, GECCO '08, pages 1147--1148, New York, NY, USA, 2008. ACM.

Digital Library

[16]

M. Walker, H. Edwards, and C. Messom. Confidence intervals for computational effort comparisons. In Genetic Programming. Proceedings of the 10th European Conference, EuroGP 2007, 2007.

Digital Library

[17]

M. Walker, H. Edwards, and C. Messom. The reliability of confidence intervals for computational effort comparisons. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, GECCO '07, pages 1716--1723, New York, NY, USA, 2007. ACM.

Digital Library

[18]

M. Walker, H. Edwards, and C. Messom. Success effort and other statistics for performance comparisons in genetic programming. In Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pages 4631--4638, September 2007.

Cited By

Harrington KSpector LPollack JO'Reilly UMoore J(2012)Autoconstructive evolution for structural problemsProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330797(75-82)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330797

Index Terms

Achieving COSMOS: a metric for determining when to give up and when to reach for the stars
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
    2. Machine learning approaches
      1. Markov decision processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

Comparison of a crossover operator in binary-coded genetic algorithms

Genetic algorithms (GAs) represent a method that mimics the process of natural evolution in effort to find good solutions. In that process, crossover operator plays an important role. To comprehend the genetic algorithms as a whole, it is necessary to ...
Application of genetic algorithm for solving university timetabling problems: a case study of Thai universities
SMO'07: Proceedings of the 7th WSEAS International Conference on Simulation, Modelling and Optimization

There are many problems in university timetabling derived from various limitations and constraints. They comprise congruence and relation among group of students, subjects, lecturers, rooms, periods and time space. Genetic Algorithm (GA) was applied to ...
HMXT-GP: an information-theoretic approach to genetic programming that maintains diversity
SAC '11: Proceedings of the 2011 ACM Symposium on Applied Computing

This paper applies a recent information--theoretic approach to controlling Genetic Algorithms (GAs) called HMXT to tree--based Genetic Programming (GP). HMXT, in a GA domain, requires the setting of selection thresholds in a population and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

July 2012

1586 pages

ISBN:9781450311786

DOI:10.1145/2330784

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 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: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
40
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Harrington KSpector LPollack JO'Reilly UMoore J(2012)Autoconstructive evolution for structural problemsProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330797(75-82)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330797

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