research-article

A measure-theoretic analysis of stochastic optimization

Authors:

Alan J. Lockett,

Risto MiikkulainenAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 105 - 118

https://doi.org/10.1145/2460239.2460250

Published: 16 January 2013 Publication History

Abstract

This paper proposes a measure-theoretic framework to study iterative stochastic optimizers that provides theoretical tools to explore how the optimization methods may be improved. Within this framework, optimizers form a closed, convex subset of a normed vector space, implying the existence of a distance metric between any two optimizers and a meaningful and computable spectrum of new optimizers between them. It is shown how the formalism applies to evolutionary algorithms in general. The analytic property of continuity is studied in the context of genetic algorithms, revealing the conditions under which approximations such as meta-modeling or surrogate methods may be effective. These results demonstrate the power of the proposed analytic framework, which can be used to propose and analyze new techniques such as controlled convex combinations of optimizers, meta-optimization of algorithm parameters, and more.

References

[1]

A. Auger and O. Teytaud. Continuous lunches are free! In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO-2007), New York, 2007. ACM Press.

Digital Library

[2]

P. Billingsley. Probability and Measure. John Wiley, 1986.

[3]

D. Cohn. Measure Theory. Birkhauser, Boston, MA, 1980.

[4]

M. El-Beltagy, P. B. Nair, and A. J. Keane. Metamodeling techniques for evolutionary optimization of computationally expensive problems: Promises and limitations. In GECCO'99, pages 196--203, 1999.

[5]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.

Digital Library

[6]

P. Halmos. Measure Theory. Springer-Verlag, New York, NY, 1974.

[7]

Y. Jin. Surrogate-assisted evolutionary computation: Recent advances and future challenges. Swarm and Evolutionary Computation, 1(2):61--70, 2011.

[8]

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598), 1983.

[9]

J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2), 2011.

Digital Library

[10]

A. Lockett and R. Miikkulainen. Real-space evolutionary annealing. In Proceedings of the 2011 Genetic and Evolutionary Computation Conference (GECCO-2011), 2011.

Digital Library

[11]

A. J. Lockett. General-Purpose Optimization Through Information Maximization. PhD thesis, University of Texas at Austin, 2012.

[12]

J. R. Munkres. Topology. Prentice Hall, Upper Saddle River, NJ, 2000.

[13]

N. Radcliffe and P. D. Surry. Fundamental limitations on search algorithms: Evolutionary computing in perspective. In LECTURE NOTES IN COMPUTER SCIENCE 1000, pages 275--291. Springer-Verlag, 1995.

[14]

J. E. Rowe, M. D. Vose, and A. H. Wright. Reinterpreting no free lunch. Evolutionary Computation, 17(1), 2009.

Digital Library

[15]

T. Schaul, Y. Sun, D. Wierstra, F. Gomez, and J. Schmidhuber. Curiosity-Driven Optimization. In IEEE Congress on Evolutionary Computation (CEC), 2011.

[16]

C. Schumacher, M. D. Vose, and L. D. Whitley. The no free lunch and problem description length. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001, pages 565--570. Morgan Kaufmann, 2001.

[17]

M. Vose. The Simple Genetic Algorithm. MIT Press, Cambridge, Massachusetts, 1999.

Digital Library

[18]

M. D. Vose. Random heuristic search. Theoretical Computer Science, 229:103--142, 1999.

Digital Library

[19]

D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 1997.

Digital Library

Cited By

Lockett AMiikkulainen R(2017)A probabilistic reformulation of no free lunchEvolutionary Computation10.1162/evco_a_0019625:3(503-528)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1162/evco_a_00196
Lockett AHe JJansen TOchoa GZarges C(2015)Insights From Adversarial Fitness FunctionsProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725501(25-39)Online publication date: 17-Jan-2015
https://dl.acm.org/doi/10.1145/2725494.2725501
Lockett AArnold D(2014)Model-optimal optimization by solving bellman equationsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598306(1407-1414)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598306
Show More Cited By

Index Terms

A measure-theoretic analysis of stochastic optimization
1. Computing methodologies
  1. Machine learning

Recommendations

Center particle swarm optimization

Center particle swarm optimization algorithm (CenterPSO) is proposed where a center particle is incorporated into linearly decreasing weight particle swarm optimization (LDWPSO). Unlike other ordinary particles in LDWPSO, the center particle has no ...
A theoretical and empirical analysis of convergence related particle swarm optimization

In this paper an extensive theoretical and empirical analysis of recently introduced Particle Swarm Optimization algorithm with Convergence Related parameters (CR-PSO) is presented. The convergence of the classical PSO algorithm is addressed in detail. ...
Using quantum-behaved particle swarm optimization algorithm to solve non-linear programming problems
Distributed Algorithms in Science and Engineering

In this paper, we focus on solving non-linear programming (NLP) problems using quantum-behaved particle swarm optimization (QPSO). After a brief introduction to the original particle swarm optimization (PSO), we describe the origin and development of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Copyright © 2013 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: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
97
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lockett AMiikkulainen R(2017)A probabilistic reformulation of no free lunchEvolutionary Computation10.1162/evco_a_0019625:3(503-528)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1162/evco_a_00196
Lockett AHe JJansen TOchoa GZarges C(2015)Insights From Adversarial Fitness FunctionsProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725501(25-39)Online publication date: 17-Jan-2015
https://dl.acm.org/doi/10.1145/2725494.2725501
Lockett AArnold D(2014)Model-optimal optimization by solving bellman equationsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598306(1407-1414)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598306
Lockett A(2013)Measure-theoretic analysis of performance in evolutionary algorithms2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557806(2012-2019)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557806

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.

Figures

Tables

Media

View Table of Conten