More Web Proxy on the site http://driver.im/

Article

Evaluation relaxation using substructural information and linear estimation

Authors:

Claudio F. Lima,

David E. GoldbergAuthors Info & Claims

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Pages 419 - 426

https://doi.org/10.1145/1143997.1144074

Published: 08 July 2006 Publication History

Abstract

The paper presents an evaluation-relaxation scheme where a fitness surrogate automatically adapts to the problem structure and the partial contributions of subsolutions to the fitness of an individual are estimated efficiently and accurately. In particular, the probabilistic model built by extended compact genetic algorithm is used to infer the structural form of the surrogate and a least squares method is used to estimate the coefficients of the surrogate. Using the surrogate avoids the need for expensive fitness evaluation for some of the solutions, and thereby yields significant efficiency enhancement. Results show that a surrogate, which automatically adapts to problem knowledge mined from probabilistic models, yields substantial speedup (1.75--3.1) on a class of boundedly-difficult additively-decomposable problems with and without additive Gaussian noise. The speedup provided by the surrogate increases with the number of substructures, substructure complexity, and noise-to-signal ratio.

References

[1]

D. H. Ackley. A connectionist machine for genetic hill climbing. Kluwer Academic Publishers, 1987.

[2]

J.-F. M. Barthelemy and R. T. Haftka. Approximation concepts for optimum structural design - a review. Structural Optimization, 5:129--144, 1993.

[3]

D. P. Bertsekas. Incremental least squares methods and the extended Kalman filter. SIAM Journal on Optimization, 6(3):807--822, 1996.

Digital Library

[4]

Å. Björk. Numerical method for least squares problems. SIAM, Philadelphia, PA, 1996.

[5]

K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms, 2:93--108, 1992. (Also IlliGAL Report No. 91009).

[6]

J. E. Dennis and V. Torczon. Managing approximate models in optimization. In N. M. Alexandrov and M. Y. Hussaini, editors, Multidisciplinary Design Optimization: State-of-the-Art, pages 330--347, Philadelphia, PA, 1997. SIAM.

[7]

N. R. Draper and H. Smith. Applied regression analysis. John Wiley & Sons, New York, USA, 1966.

[8]

D. E. Goldberg. Genetic algorithms and Walsh functions: Part I, a gentle introduction. Complex Systems, 3:129--152, 1989.

[9]

D. E. Goldberg. Design of innovation: Lessons from and for competent genetic algorithms. Kluwer Academic Publishers, Boston, MA, 2002.

Digital Library

[10]

J. J. Grefenstette and J. M. Fitzpatrick. Genetic search with approximate function evaluations. Proceedings of the International Conference on Genetic Algorithms and Their Applications, pages 112--120, 1985.

Digital Library

[11]

G. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Urbana, IL, 1999.

[12]

S. Haykin. Adaptive filter theory. Prentice Hall, 1996.

Digital Library

[13]

Y. Jin. A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing Journal, 9(1):3--12, 2005.

Digital Library

[14]

T. Kailath, A. H. Sayed, and B. Hassibi. Linear estimation. Prentice-Hall, Upper Saddle River, NJ, 2000.

[15]

P. Larrañaga and J. A. Lozano, editors. Estimation of distribution algorithms. Kluwer Academic Publishers, Boston, MA, 2002.

[16]

C. F. Lima, K. Sastry, D. E. Goldberg, and F. G. Lobo. Combining competent crossover and mutation operators: A probabilistic model building approach. Proceedings of the Genetic and Evolutionary Computation Conference, pages 735--742, 2005.

Digital Library

[17]

X. Llorà, K. Sastry, D. E. Goldberg, A. Gupta, and L. Lakshmi. Combating user fatigue in iGAs: Partial ordering, support vector machines, and synthetic fitness. Proceedings of the Genetic and Evolutionary Computation Conference, pages 1363--1370, 2005.

Digital Library

[18]

M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithm. Springer Verlag, Berlin, 2005.

[19]

M. Pelikan and K. Sastry. Fitness inheritance in the Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference, 2:48--59, 2004. (Also IlliGAL Report No. 2004009).

[20]

C. R. Rao and H. Toutenburg. Linear models: Least squares and alternatives. Springer, Berlin, 1999.

Digital Library

[21]

J. J. Rissanen. Stochastic complexity in statistical inquiry. World Scientific Publishing Co., Singapore, 1989.

Digital Library

[22]

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, General Engineering Department, Urbana, IL, 2001.

[23]

K. Sastry, H. A. Abbass, D. E. Goldberg, and D. D. Johnson. Sub-structural niching in estimation of distribution algorithms. Proceedings of the Genetic and Evolutionary Computation Conference, pages 671--678, 2005. (Also IlliGAL Report No. 2005003).

Digital Library

[24]

K. Sastry and D. E. Goldberg. Designing competent mutation operators via probabilistic model building of neighborhoods. Proceedings of the Genetic and Evolutionary Computation Conference, 2:114--125, 2004. Also IlliGAL Report No. 2004006.

[25]

K. Sastry, D. E. Goldberg, and M. Pelikan. Don't evaluate, inherit. Proceedings of the Genetic and Evolutionary Computation Conference, pages 551--558, 2001. (Also IlliGAL Report No. 2001013).

[26]

K. Sastry, M. Pelikan, and D. E. Goldberg. Efficiency enhancement of genetic algorithms via building-block-wise fitness estimation. Proceedings of the IEEE International Conference on Evolutionary Computation, pages 720--727, 2004.

[27]

R. Smith, B. Dike, and S. Stegmann. Fitness inheritance in genetic algorithms. In Proceedings of the ACM Symposium on Applied Computing, pages 345--350, New York, NY, USA, 1995. ACM.

Digital Library

[28]

T.-L. Yu, K. Sastry, and D. E. Goldberg. Online population size adjusting using noise and substructural measurements. Proceedings of the IEEE Congress on Evolutionary Computation, 3:2491--2498, 2005. (Also IlliGAL Report No. 2005017).

Cited By

Liaw RTing C(2021)Enhancing covariance matrix adaptation evolution strategy through fitness inheritance2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744027(1956-1963)Online publication date: 11-Mar-2021
https://dl.acm.org/doi/10.1109/CEC.2016.7744027
Liaw RTing C(2020)Evolution of biocoenosis through symbiosis with fitness approximation for many-tasking optimizationMemetic Computing10.1007/s12293-020-00317-212:4(399-417)Online publication date: 26-Oct-2020
https://doi.org/10.1007/s12293-020-00317-2
Santana RMendiburu ALozano J(2016)A review of message passing algorithms in estimation of distribution algorithmsNatural Computing: an international journal10.1007/s11047-014-9473-215:1(165-180)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s11047-014-9473-2
Show More Cited By

Index Terms

Evaluation relaxation using substructural information and linear estimation

Recommendations

Entropy-based evaluation relaxation strategy for Bayesian optimization algorithm
IEA/AIE'10: Proceedings of the 23rd international conference on Industrial engineering and other applications of applied intelligent systems - Volume Part II

Bayesian Optimization Algorithm (BOA) belongs to the advanced evolutionary algorithms (EA) capable of solving problems with multivariate interactions. However, to attain wide applicability in realworld optimization, BOA needs to be coupled with various ...
Network crossover performance on NK landscapes and deceptive problems
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Practitioners often have some information about the problem being solved, which may be represented as a graph of dependencies or correlations between problem variables. Similar information can also be obtained automatically, for example by mining the ...
Entropy-based efficiency enhancement techniques for evolutionary algorithms

This paper introduces the notion of an entropy measurement for populations of candidate solutions in evolutionary algorithms, developing both conditional and joint entropy-based algorithms. We describe the inherent characteristics of the entropy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

July 2006

2004 pages

ISBN:1595931864

DOI:10.1145/1143997

General Chair:
Mike Cattolico
Tiger Mountain Scientific, Inc., USA

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

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO06

Sponsor:

GECCO06: Genetic and Evolutionary Computation Conference

July 8 - 12, 2006

Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
14
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liaw RTing C(2021)Enhancing covariance matrix adaptation evolution strategy through fitness inheritance2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744027(1956-1963)Online publication date: 11-Mar-2021
https://dl.acm.org/doi/10.1109/CEC.2016.7744027
Liaw RTing C(2020)Evolution of biocoenosis through symbiosis with fitness approximation for many-tasking optimizationMemetic Computing10.1007/s12293-020-00317-212:4(399-417)Online publication date: 26-Oct-2020
https://doi.org/10.1007/s12293-020-00317-2
Santana RMendiburu ALozano J(2016)A review of message passing algorithms in estimation of distribution algorithmsNatural Computing: an international journal10.1007/s11047-014-9473-215:1(165-180)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s11047-014-9473-2
Martins JDelbem A(2014)Efficiency enhancement of estimation of distribution algorithms by a compressed tournament selectionJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.5555/2656674.265671426:5(2537-2545)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.5555/2656674.2656714
Brownlee AMcCall JZhang Q(2013)Fitness Modeling With Markov NetworksIEEE Transactions on Evolutionary Computation10.1109/TEVC.2013.228153817:6(862-879)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1109/TEVC.2013.2281538
Brownlee ARegnier-Coudert OMcCall JMassie SStulajter S(2013)An application of a GA with Markov network surrogate to feature selectionInternational Journal of Systems Science10.1080/00207721.2012.68444944:11(2039-2056)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.1080/00207721.2012.684449
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
Mendiburu ASantana RLozano J(2012)Fast Fitness Improvements in Estimation of Distribution Algorithms Using Belief PropagationMarkov Networks in Evolutionary Computation10.1007/978-3-642-28900-2_9(141-155)Online publication date: 2012
https://doi.org/10.1007/978-3-642-28900-2_9
Brownlee AMcCall JShakya S(2012)The Markov Network Fitness ModelMarkov Networks in Evolutionary Computation10.1007/978-3-642-28900-2_8(125-140)Online publication date: 2012
https://doi.org/10.1007/978-3-642-28900-2_8
Shakya SMcCall JBrownlee AOwusu G(2012)DEUM - Distribution Estimation Using Markov NetworksMarkov Networks in Evolutionary Computation10.1007/978-3-642-28900-2_4(55-71)Online publication date: 2012
https://doi.org/10.1007/978-3-642-28900-2_4
Show More Cited By

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