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

research-article

On empirical memory design, faster selection of bayesian factorizations and parameter-free gaussian EDAs

Author:

Peter A.N. BosmanAuthors Info & Claims

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

Pages 389 - 396

https://doi.org/10.1145/1569901.1569956

Published: 08 July 2009 Publication History

Abstract

Often, Estimation-of-Distribution Algorithms (EDAs) are praised for their ability to optimize a broad class of problems. EDA applications are however still limited. Often heard criticism is that a large population size is required and that distribution estimation takes long. Here we look at possibilities for improvements in these areas. We first discuss the use of a memory to aggregate information over multiple generations and reduce the population size. The approach we take, empirical risk minimization to perform non-linear regression of memory parameters, may well be generalizable to other EDAs. We design a memory this way for a Gaussian EDA and observe smaller population size requirements and fewer evaluations used. We also speed up the selection of Bayesian factorizations for Gaussian EDAs by sorting the entries in the covariance matrix. Finally, we discuss parameter-free Gaussian EDAs for real-valued single-objective optimization. We propose to not only increase the population size in subsequent runs, but to also divide it over parallel runs across the search space. On some multimodal problems improvements are thereby obtained.

References

[1]

]]A. Auger and N. Hansen. A restart CMA evolution strategy with increasing population size. In D. Corne et al., editors, Proceedings of the IEEE Congress on Evolutionary Computation -- CEC'2005, pages 1769--1776, Piscataway, New Jersey, 2005. IEEE Press.

[2]

]]S. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithm. In A. Prieditis and S. Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning, pages 38--46, Madison, Wisconsin, 1995. Morgan Kauffman.

[3]

]]P. A. N. Bosman, J. Grahl, and D. Thierens. Enhancing the performance of maximum-likelihood Gaussian EDAs using anticipated mean shift. In G. Rudolph et al., editors, Parallel Problem Solving from Nature -- PPSN X, pages 133--134, Berlin, 2008. Springer-Verlag.

[4]

]]P. A. N. Bosman and D. Thierens. The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 7(2):174--188, 2003.

Digital Library

[5]

]]J. Branke. Evolutionary Optimization in Dynamic Environments. Kluwer, Norwell, Massachusetts, 2001.

Digital Library

[6]

]]J. Branke, T. Kaußler, C. Schmidt, and H. Schmeck. A multi-population approach to dynamic optimization problems. In I.C. Parmee, editor, Adaptive Computing in Design and Manufacture -- ACDM 2000, pages 299--308, Berlin, 1999. Springer-Verlag.

[7]

]]K. Deb. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, Chichester, 2001.

Digital Library

[8]

]]T. S. P. C. Duque, D. E. Goldberg, and K. Sastry. Improving the efficiency of the extended compact genetic algorithm. In C. Ryan et al., editors, Proceedings of the Genetic and Evolutionary Comp. Conf. -- GECCO'2008, pages 467--468, New York, New York, 2008. ACM Press.

Digital Library

[9]

]]N. Hansen, S. D. Muller, and P. Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1):1--18, 2003.

Digital Library

[10]

]]G. Harik and F. Lobo. A parameter-less GA. In W. Banzhaf et al., editors, Proc. of the Genetic and Evol. Comp. Conf. -- GECCO'1999, pages 258--265, San Francisco, California, 1999. Morgan Kaufmann.

[11]

]]J. A. Lozano, P. Larranaga, I. Inza, and E. Bengoetxea. Towards a New Evolutionary Computation. Advances in Estimation of Distribution Algorithms. Springer-Verlag, Berlin, 2006.

Digital Library

[12]

]]M. Pelikan and T.-K. Lin. Parameter-less hierarchical BOA. In K. Deb et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference -- GECCO-2004, pages 24--35, Berlin, 2004. Springer-Verlag.

[13]

]]M. Pelikan, K. Sastry, and E. Cantu-Paz. Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Springer-Verlag, Berlin, 2006.

Digital Library

[14]

]]M. Pelikan, K. Sastry, and D. E. Goldberg. iBOA: the incremental Bayesian optimization algorithm. In C. Ryan et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference -- GECCO-2008, pages 455--462, New York, New York, 2008. ACM Press.

Digital Library

[15]

]]R. Ros and N. Hansen. A simple modification in CMA-ES achieving linear time and space complexity. In G. Rudolph et al., editors, Parallel Problem Solving from Nature -- PPSN X, pages 296--305, Berlin, 2008. Springer-Verlag.

[16]

]]S. Rudlof and M. Koppen. Stochastic hill climbing with learning by vectors of normal distributions. In T. Furuhashi, editor, Proceedings of the First Online Workshop on Soft Computing -- WSC1, pages 60--70, Nagoya, 1996. Nagoya University.

[17]

]]G. Schwarz. Estimating the dimension of a model. Annals of Statistics, 6(2):461--464, 1978.

[18]

]]M. Sebag and A. Ducoulombier. Extending population-based incremental learning to continuous search spaces. In A. E. Eiben et al., editors, Parallel Problem Solving from Nature -- PPSN V, pages 418--427, Berlin, 1998. Springer-Verlag.

Digital Library

[19]

]]V. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, Berlin, 1995.

Digital Library

Cited By

Andreadis GAlderliesten TBosman PLi XHandl J(2024)Fitness-based Linkage Learning and Maximum-Clique Conditional Linkage Modelling for Gray-box Optimization with RV-GOMEAProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654103(647-655)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654103
Rodriguez CBosman PAlderliesten T(2024)Balancing Between Time Budgets and Costs in Surrogate-Assisted Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_20(322-339)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70068-2_20
Rodriguez Cde Boer SBosman PAlderliesten T(2023)Bi-objective optimization of organ properties for the simulation of intracavitary brachytherapy applicator placement in cervical cancerMedical Imaging 2023: Image-Guided Procedures, Robotic Interventions, and Modeling10.1117/12.2647129(16)Online publication date: 3-Apr-2023
https://doi.org/10.1117/12.2647129
Show More Cited By

Index Terms

On empirical memory design, faster selection of bayesian factorizations and parameter-free gaussian EDAs

Recommendations

Backtracking Search Optimization Algorithm for numerical optimization problems

This paper introduces the Backtracking Search Optimization Algorithm (BSA), a new evolutionary algorithm (EA) for solving real-valued numerical optimization problems. EAs are popular stochastic search algorithms that are widely used to solve non-linear, ...
Modified differential evolution with self-adaptive parameters method

The differential evolution algorithm (DE) is a simple and effective global optimization algorithm. It has been successfully applied to solve a wide range of real-world optimization problem. In this paper, the proposed algorithm uses two mutation rules ...
Use of the q-Gaussian mutation in evolutionary algorithms
Special issue on advances in computational intelligence and bioinformatics

This paper proposes the use of the q-Gaussian mutation with self-adaptation of the shape of the mutation distribution in evolutionary algorithms. The shape of the q-Gaussian mutation distribution is controlled by a real parameter q. In the proposed ...

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

20
Total Citations
View Citations
141
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Andreadis GAlderliesten TBosman PLi XHandl J(2024)Fitness-based Linkage Learning and Maximum-Clique Conditional Linkage Modelling for Gray-box Optimization with RV-GOMEAProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654103(647-655)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654103
Rodriguez CBosman PAlderliesten T(2024)Balancing Between Time Budgets and Costs in Surrogate-Assisted Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70068-2_20(322-339)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70068-2_20
Rodriguez Cde Boer SBosman PAlderliesten T(2023)Bi-objective optimization of organ properties for the simulation of intracavitary brachytherapy applicator placement in cervical cancerMedical Imaging 2023: Image-Guided Procedures, Robotic Interventions, and Modeling10.1117/12.2647129(16)Online publication date: 3-Apr-2023
https://doi.org/10.1117/12.2647129
Chinnasami SRamachandran MVidhya P(2021)Study of Evaluation Based on Distance from Average Solution on Moyamoya Disease and Energy applicationREST Journal on Emerging trends in Modelling and Manufacturing10.46632/7/4/37:4(117-124)Online publication date: 1-Dec-2021
https://doi.org/10.46632/7/4/3
Xu QLiu AYuan XSong YZhang CLi Y(2021)Random mask-based estimation of the distribution algorithm for stacked auto-encoder one-step pre-trainingComputers and Industrial Engineering10.1016/j.cie.2021.107400158:COnline publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.cie.2021.107400
Bouter AMaree SAlderliesten TBosman PCoello Coello C(2020)Leveraging conditional linkage models in gray-box optimization with the real-valued gene-pool optimal mixing evolutionary algorithmProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390225(603-611)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390225
Sanyang MKabán A(2019)Large-Scale Estimation of Distribution Algorithms with Adaptive Heavy Tailed Random Projection EnsemblesJournal of Computer Science and Technology10.1007/s11390-019-1973-134:6(1241-1257)Online publication date: 22-Nov-2019
https://doi.org/10.1007/s11390-019-1973-1
Kabán ABootkrajang JDurrant R(2016)Toward large-scale continuous edaEvolutionary Computation10.1162/EVCO_a_0015024:2(255-291)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1162/EVCO_a_00150
Sanyang MKabán A(2016)REMEDA: Random Embedding EDA for Optimising Functions with Intrinsic DimensionParallel Problem Solving from Nature – PPSN XIV10.1007/978-3-319-45823-6_80(859-868)Online publication date: 31-Aug-2016
https://doi.org/10.1007/978-3-319-45823-6_80
de Bokx RThierens DBosman PEsparcia-Alcázar A(2015)In Search of Optimal Linkage TreesProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2764679(1375-1376)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2764679
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