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

Article

Cross entropy and adaptive variance scaling in continuous EDA

Authors:

Peifa JiaAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 609 - 616

https://doi.org/10.1145/1276958.1277081

Published: 07 July 2007 Publication History

Abstract

This paper deals with the adaptive variance scaling issue incontinuous Estimation of Distribution Algorithms. A phenomenon is discovered that current adaptive variance scaling method in EDA suffers from imprecise structure learning. A new type of adaptation method is proposed to overcome this defect. The method tries to measure the difference between the obtained population and the prediction of the probabilistic model, then calculate the scaling factor by minimizing the cross entropy between these two distributions. This approach calculates the scaling factor immediately rather than adapts it incrementally. Experiments show that this approach extended the class of problems that can be solved, and improve the search efficiency in some cases. Moreover, the proposed approach features in that each decomposed subspace can be assigned an individual scaling factor, which helps to solve problems with special dimension property.

References

[1]

C. Ahn, R. Ramakrishna, and D. Goldberg. Real-coded bayersian optimization algorithm:bringing the strength of boa into the continuous world. In Proceedings of the GECCO-2004 Conference on Genetic and Evolutionary Computation, pages 840--851. Springer Verlag, 2004.

[2]

A. Berny. Statistical Machine Learning and Combinatorial Optimization. In Theoretical Aspects of Evolutionary Computation, pages 287--306. Springer Verlag, 2001.

Digital Library

[3]

P. Bosman and J. Grahl. Matching inductive search bias and problem structure in continuous estimation of distribution algorithms. Technical Report 03/2005, Dept. of Logistics, Mannheim Business School, 2005.

[4]

P. Bosman and D. Thierens. Expanding from Discrete to Continuous Estimation of Distribution Algorithms: The IDEA. In Parallel Problem Solving from Nature -- PPSN VI, pages 767--776, Paris, France, Sep. 2000. Springer-Verlag.

Digital Library

[5]

Y. Cai, X. Sun, and P. Jia. Probabilistic Modeling for Continuous EDA with Boltzmann Selection and Kullback-Leibeler Divergence. In Proceedings of the 8th Conference on Genetic and Evolutionary Computation, pages 389--396. ACM Press, 2006.

Digital Library

[6]

T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 1991.

Digital Library

[7]

M. Gallagher and M. Frean. Population-Based Continuous Optimization, Probabilistic Modelling and Mean Shift. Evolutionary Computation, 13(1):29--42, 2005.

Digital Library

[8]

C. González, J. Lozano, and P. Larrañaga. Mathematical Modelling of UMDAc Algorithm with Tournament Selection: Behaviour on Linear and Quadratic Functions. International Journal of Approximate Reasoning, 31(2):313--340, 2002.

[9]

J. Grahl, P. Bosman, and F. Rothlauf. The Correlation-Triggered Adaptive Variance Scaling IDEA. In Proceedings of the 8th Conference on Genetic and Evolutionary Computation, pages 397--404. ACM Press, 2006.

Digital Library

[10]

J. Grahl, S. Minner, and F. Rothlauf. Behaviour of UMDAc with Truncation Selection on Monotonous Functions. In The 2005 IEEE Congress on Evolutionary Computation, pages 2553--2559, Edinburgh, Scotland, 2005. IEEE.

[11]

N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolutionary strategiess. Evolutionary Computation, 9(2):159--195, 2001.

Digital Library

[12]

P. Larrañaga, R. Etxeberria, J. A. Lozano, and J. M. Peña. Optimization in Continuous Domains by Learning and Simulation of Gaussian Networks. In Proceedings of the GECCO-2000 Workshop in Optimization by Building and Using Probabilistic Models, pages 201--204, San Francisco, CA, USA, 2001. Morgan Kaufmann.

[13]

P. Larrañaga and J. Lozano. Estimation of Distribution Algorithms, A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.

[14]

P. Larrañaga, J. A. Lozano, and E. Bengoetxea. Estimation of Distribution Algorithms based on Multivariate Normal and Gaussian Networks. Technical Report EHU-KZAA-IK-1-01, University of the Basque Country, 2001.

[15]

J. Lozano, P. Larrañaga, I. Inza, and E. Bengoetxea. Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms. Springer, 2006.

Digital Library

[16]

H. Mühlenbein. The Equation for Response to Selection and Its Use for Prediction. Evolutionary Computation, 5(3):303--346, 1997.

Digital Library

[17]

H. Mühlenbein and R. Höns. The Estimation of Distributions and the Minimum Relative Entropy Principle. Evolutionary Computation, 13(1):1--27, 2005.

Digital Library

[18]

J. Oceanasek and J. Schwarz. Estimation of Distribution Algorithm for Mixed Continuous-Discrete Optimization Problems. In 2nd Euro-International Symposium on Computational Intelligence, pages 227--232, Kosice, Slowakia, 2002. IOS Press.

[19]

J. Ocenasek, S. Kern, N. Hansen, S. Müller, and P. Koumoutsakos. A Mixed Bayesian Optimization Algorithm with Variance Adaptation. In Parallel Problem Solving from Nature -- PPSN VIII, pages 352--361. Springer Verlag, 2004.

[20]

A. Ostermeier, A. Gawelczyk, and N. Hansen. A derandomized approach to self adaptation of evolution strategies. Evolutionary Computation, 2(4):369--380, 1994.

Digital Library

[21]

M. Pelikan, D. Goldberg, and S. Tsutsui. Getting the Best of Both Worlds: Discrete and Continuous Genetic and Evolutionary Algorithms in Concert. Information Sciences, 156(3--4):147--171, 2003.

Digital Library

[22]

M. Pelikan, S. K., and C.-P. E. Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Springer, 2006.

Digital Library

[23]

I. Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, 1973.

[24]

S. Rudolf and M. Köppen. Stochastic Hill Climbing by Vectors of Normal Distributions. In Proceedings of the First Online Workshop on Soft Computing, Nagoya, Japan, 1996.

[25]

K. S. Information theory and statistics. John Wiley and Sons, 1959.

[26]

H.-P. Schwefel. Numerical Optimization of Computer Models. Wiley, 1981.

Digital Library

[27]

M. Sebag and A. Ducoulombier. Extending Population-Based Incremental Learning to Continuous Search Spaces. In Parallel Problem Solving from Nature -- PPSN V., pages 418--427, Amsterdam, Netherlands, Sep. 1998. Springer-Verlag.

Digital Library

[28]

S. Shin and B.-T. Zhang. Bayesian Evolutionary Algorithms for Continuous Function Optimization. In Proc. 2001 Congress on Evolutionary Computation, pages 508--515. IEEE, 2001.

[29]

B. Yuan and M. Gallagher. On the Importance of Diversity Maintenance in Estimation of Distribution Algorithms. In Proceedings of the 7th Conference on Genetic and Evolutionary Computation, pages 719--726. ACM Press, 2005.

Digital Library

Cited By

Dębski RDreżewski R(2024)Multi-Objective Ship Route Optimisation Using Estimation of Distribution AlgorithmApplied Sciences10.3390/app1413591914:13(5919)Online publication date: 6-Jul-2024
https://doi.org/10.3390/app14135919
Wang XLi YLiang YWu BXuan Y(2023)A novel ensemble estimation of distribution algorithm with distribution modification strategiesComplex & Intelligent Systems10.1007/s40747-023-00975-y9:5(5377-5416)Online publication date: 20-Mar-2023
https://doi.org/10.1007/s40747-023-00975-y
Li YYang QGao XLu ZZhang JWagner M(2022)A layered learning estimation of distribution algorithmProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3528904(399-402)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3528904
Show More Cited By

Index Terms

Cross entropy and adaptive variance scaling in continuous EDA
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

The correlation-triggered adaptive variance scaling IDEA
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

It has previously been shown analytically and experimentally that continuous Estimation of Distribution Algorithms (EDAs) based on the normal pdf can easily suffer from premature convergence. This paper takes a principled first step towards solving this ...
Adaptive variance scaling in continuous multi-objective estimation-of-distribution algorithms
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Recent research into single-objective continuous Estimation-of-Distribution Algorithms (EDAs)has shown that when maximum-likelihood estimationsare used for parametric distributions such as thenormal distribution, the EDA can easily suffer frompremature ...
Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems
Special Issue on scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems

This paper presents a novel algorithm based on generalized opposition-based learning (GOBL) to improve the performance of differential evolution (DE) to solve high-dimensional optimization problems efficiently. The proposed approach, namely GODE, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

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

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
212
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dębski RDreżewski R(2024)Multi-Objective Ship Route Optimisation Using Estimation of Distribution AlgorithmApplied Sciences10.3390/app1413591914:13(5919)Online publication date: 6-Jul-2024
https://doi.org/10.3390/app14135919
Wang XLi YLiang YWu BXuan Y(2023)A novel ensemble estimation of distribution algorithm with distribution modification strategiesComplex & Intelligent Systems10.1007/s40747-023-00975-y9:5(5377-5416)Online publication date: 20-Mar-2023
https://doi.org/10.1007/s40747-023-00975-y
Li YYang QGao XLu ZZhang JWagner M(2022)A layered learning estimation of distribution algorithmProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3528904(399-402)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3528904
Zhao FZhu BWang LXu TZhu NJonrinaldi J(2022)An offline learning co-evolutionary algorithm with problem-specific knowledgeSwarm and Evolutionary Computation10.1016/j.swevo.2022.10114875(101148)Online publication date: Dec-2022
https://doi.org/10.1016/j.swevo.2022.101148
Yang QLi YGao XMa YLu ZJeon SZhang J(2021)An Adaptive Covariance Scaling Estimation of Distribution AlgorithmMathematics10.3390/math92432079:24(3207)Online publication date: 11-Dec-2021
https://doi.org/10.3390/math9243207
Liang YRen ZYao XFeng ZChen AGuo W(2020)Enhancing Gaussian Estimation of Distribution Algorithm by Exploiting Evolution Direction With ArchiveIEEE Transactions on Cybernetics10.1109/TCYB.2018.286956750:1(140-152)Online publication date: Jan-2020
https://doi.org/10.1109/TCYB.2018.2869567
Wang XZhao HHan TWei ZLiang YLi Y(2019)A Gaussian Estimation of Distribution Algorithm With Random Walk Strategies and Its Application in Optimal Missile Guidance Handover for Multi-UCAV in Over-the-Horizon Air CombatIEEE Access10.1109/ACCESS.2019.29082627(43298-43317)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2908262
Yongsheng Liang Zhigang Ren Wang LBei Pang Hossain M(2017)Inferior solutions in Gaussian EDA: Useless or useful?2017 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2017.7969327(301-307)Online publication date: Jun-2017
https://doi.org/10.1109/CEC.2017.7969327
Ren ZHe CZhong DHuang SLiang Y(2016)Enhance continuous estimation of distribution algorithm by variance enlargement and reflecting sampling2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744225(3441-3447)Online publication date: Jul-2016
https://doi.org/10.1109/CEC.2016.7744225
Hernandez EValdez SCeccarelli MHernandez ABotello S(2014)Design optimization of a cable-based parallel tracking system by using evolutionary algorithmsRobotica10.1017/S026357471400048433:3(599-610)Online publication date: 5-Mar-2014
https://doi.org/10.1017/S0263574714000484
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