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

Article

Adaptive variance scaling in continuous multi-objective estimation-of-distribution algorithms

Authors:

Peter A. N. Bosman,

Dirk ThierensAuthors Info & Claims

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

Pages 500 - 507

https://doi.org/10.1145/1276958.1277067

Published: 07 July 2007 Publication History

Abstract

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 convergence. In this paper we argue thatthe same holds for multi-objective optimization.Our aim in this paper is to transfer a solutioncalled Adaptive Variance Scaling (AVS) from thesingle-objective case to the multi-objectivecase. To this end, we zoom in on an existing EDAfor continuous multi-objective optimization, theMIDEA, which employs mixturedistributions. We propose a means to combine AVSwith the normal mixture distribution, as opposedto the single normal distribution for which AVS wasintroduced. In addition, we improve the AVS schemeusing the Standard-Deviation Ratio(SDR) trigger. Intuitively put, variance scalingis triggered by the SDR trigger only ifimprovements are found to be far awayfrom the mean. For the multi-objective case,this addition is important to keep the variancefrom being scaled to excessively large values.From experiments performed on five well-knownbenchmark problems, the addition of SDR andAVS is found to enlarge the class of problems thatcontinuous multi-objective EDAs can solve reliably.

References

[1]

M. Abramowitz and I. Stegun. Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables. Dover Publications, New York, New York, 1972.

Digital Library

[2]

Th. Bäck and H.-P. Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1--23, 1993.

Digital Library

[3]

P. A. N. Bosman and E. D. de Jong. Combining gradient techniques for numerical multi-objective evolutionary optimization. In W. B. Langdon et al., editors, Proc. of the Genetic and Evolutionary Comp. Conf. - GECCO-2006, pages 627--634, New York, New York, 2006. ACM.

Digital Library

[4]

P. A. N. Bosman and D. Thierens. Advancing continuous IDEAs with mixture distributions and factorization selection metrics. In M. Pelikan and K. Sastry, editors, Proceedings of the Optimization by Building and Using Probabilistic Models OBUPM Workshop at the Genetic and Evolutionary Comp. Conf. GECCO-2001, pages 208--212, San Francisco, California, 2001. Morgan Kaufmann.

[5]

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

Digital Library

[6]

P. A. N. Bosman and D. Thierens. Multi-objective optimization with the naive MIDEA. In J. A. Lozano et al., editors, Towards a New Evolutionary Computation. Advances in Estimation of Distribution Algorithms., pages 123--157. Springer, Berlin, 2006.

[7]

K. Deb. Multi-objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, 7(3):205--230, 1999.

Digital Library

[8]

K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In M. Schoenauer et al., editors, Par. Prob. Solving from Nature - PPSN VI, pages 849--858. Springer, 2000.

Digital Library

[9]

C. M. Fonseca and P. J. Fleming. An overview of evolutionary algorithms in multiobjective optimization. Evol. Computation, 3(1):1--16, 1995.

Digital Library

[10]

D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, 1989.

Digital Library

[11]

J. Grahl, P. A. N. Bosman, and F. Rothlauf. The correlation-triggered adaptive variance scaling idea. In M. Keijzer et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference - GECCO-2006, pages 397--404, New York, New York, 2006. ACM Press.

Digital Library

[12]

J. Grahl, S. Minner, and F. Rothlauf. Behaviour of UMDAc with truncation selection on monotonous functions. In Proc. of the Congress on Evol. Comp. - CEC-2005, pages 2553--2559, Piscataway, New Jersey, 2005. IEEE Press.

[13]

N. Hansen, S. D. Mller, and P. Koumoutsakos. Reducing the time complexiy of the derandomized evolution strategy with covariance matrix adaption. Evolutionary Computation, 11(1):1--18, 2003.

Digital Library

[14]

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

Digital Library

[15]

J. Knowles and D. Corne. On metrics for comparing non-dominated sets. In Proceedings of the 2002 Congress on Evol. Computation - CEC-2002, pages 666--674, Piscataway, New Jersey, 2002. IEEE Press.

[16]

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

Digital Library

[17]

M. Laumanns, L. Thiele, K. Deb, and E. Zitzler. Combining convergence and diversity in evolutionary multi-objective optimization. Evol. Comp., 10(3):263--282, 2002.

Digital Library

[18]

S. L. Lauritzen. Graphical Models. Clarendon Press, Oxford, 1996.

[19]

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

Digital Library

[20]

H. Mühlenbein and T. Mahnig. FDA - a scalable evolutionary algorithm for the optimization of additively decomposed functions. Evol. Comp., 7:353--376, 1999.

Digital Library

[21]

J. Ocenasek, S. Kern, N. Hansen, and P. Koumoutsakos. A mixed bayesian optimization algorithm with variance adaptation. In X. Yao et al., editors, Parallel Problem Solving from Nature - PPSN VIII, pages 352--361, Berlin, 2004. Springer-Verlag.

[22]

M. Pelikan and D. E. Goldberg. Genetic algorithms, clustering, and the breaking of symmetry. In M. Schoenauer et al., editors, Par. Prob. Solving from Nature - PPSN VI, pages 385--394. Springer, 2000.

Digital Library

[23]

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

Digital Library

[24]

D. Thierens. Scalability problems of simple genetic algorithms. Evol. Computation, 7(4):331--352, 1999.

Digital Library

[25]

D. Thierens and P. A. N. Bosman. Multi-objective mixture-based iterated density estimation evolutionary algorithms. In L. Spector et al., editors, Proc. of the Genetic and Evolutionary Computation Conference - GECCO-2001, pages 663--670, San Francisco, California, 2001. Morgan Kaufmann.

[26]

E. Zitzler, K. Deb, and L. Thiele. Comparison of multiobjective evolutionary algorithms: Empirical results. Evol. Computation, 8(2):173--195, 2000.

Digital Library

[27]

E. Zitzler, M. Laumanns, L. Thiele, C. M. Fonseca, and V. Grunert da Fonseca. Why quality assessment of multiobjective optimizers is difficult. In W. B. Langdon et al., editors, Proc. of the Genetic and Evolutionary Computation Conference - GECCO-2002, pages 666--674, San Francisco, California, 2002. Morgan Kaufmann.

Cited By

Hou YHao GZhang YGu FXu W(2022)A multi-objective discrete particle swarm optimization method for particle routing in distributed particle filtersKnowledge-Based Systems10.1016/j.knosys.2021.108068240:COnline publication date: 15-Mar-2022
https://dl.acm.org/doi/10.1016/j.knosys.2021.108068
Gao WWang YLiu LHuang L(2021)A Gradient-Based Search Method for Multi-objective Optimization ProblemsInformation Sciences10.1016/j.ins.2021.07.051578(129-146)Online publication date: Nov-2021
https://doi.org/10.1016/j.ins.2021.07.051
Liu TLi XTan LSong S(2021)An incremental-learning model-based multiobjective estimation of distribution algorithmInformation Sciences10.1016/j.ins.2021.04.011569(430-449)Online publication date: Aug-2021
https://doi.org/10.1016/j.ins.2021.04.011
Show More Cited By

Index Terms

Adaptive variance scaling in continuous multi-objective estimation-of-distribution algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Philosophical/theoretical foundations of artificial intelligence
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

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 ...
Genetic diversity as an objective in multi-objective evolutionary algorithms

A key feature of an efficient and reliable multi-objective evolutionary algorithm is the ability to maintain genetic diversity within a population of solutions. In this paper, we present a new diversity-preserving mechanism, the Genetic Diversity ...
Multi-objective modified differential evolution algorithm with archive-base mutation for solving multi-objective $$p$$p-xylene oxidation process

Maximizing the diversity of the obtained objective vectors and increasing the convergence speed to the true Pareto front are two important issues in the design of multi-objective evolutionary algorithms (MOEAs). To solve complex multi-objective ...

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

19
Total Citations
View Citations
228
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hou YHao GZhang YGu FXu W(2022)A multi-objective discrete particle swarm optimization method for particle routing in distributed particle filtersKnowledge-Based Systems10.1016/j.knosys.2021.108068240:COnline publication date: 15-Mar-2022
https://dl.acm.org/doi/10.1016/j.knosys.2021.108068
Gao WWang YLiu LHuang L(2021)A Gradient-Based Search Method for Multi-objective Optimization ProblemsInformation Sciences10.1016/j.ins.2021.07.051578(129-146)Online publication date: Nov-2021
https://doi.org/10.1016/j.ins.2021.07.051
Liu TLi XTan LSong S(2021)An incremental-learning model-based multiobjective estimation of distribution algorithmInformation Sciences10.1016/j.ins.2021.04.011569(430-449)Online publication date: Aug-2021
https://doi.org/10.1016/j.ins.2021.04.011
Wang XHan TZhao H(2020)An Estimation of Distribution Algorithm With Multi-Leader SearchIEEE Access10.1109/ACCESS.2020.29754688(37383-37405)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2975468
Sun JZhang HZhou AZhang QZhang KTu ZYe K(2019)Learning From a Stream of Nonstationary and Dependent Data in Multiobjective Evolutionary OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.286549523:4(541-555)Online publication date: Aug-2019
https://doi.org/10.1109/TEVC.2018.2865495
Lin TZhang HZhang KTu ZCui N(2017)An adaptive multiobjective estimation of distribution algorithm with a novel Gaussian sampling strategySoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2323-721:20(6043-6061)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s00500-016-2323-7
Martí LGarcía JBerlanga AMolina J(2016)MONEDAJournal of Global Optimization10.1007/s10898-016-0415-766:4(729-768)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s10898-016-0415-7
Karshenas HSantana RBielza CLarranaga P(2014)Multiobjective Estimation of Distribution Algorithm Based on Joint Modeling of Objectives and VariablesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2013.228152418:4(519-542)Online publication date: Aug-2014
https://doi.org/10.1109/TEVC.2013.2281524
Martí LSanchez-Pi NVellasco M(2014)Understanding the Treatment of Outliers in Multi-Objective Estimation of Distribution AlgorithmsAdvances in Artificial Intelligence -- IBERAMIA 201410.1007/978-3-319-12027-0_29(359-370)Online publication date: 12-Nov-2014
https://doi.org/10.1007/978-3-319-12027-0_29
Shim VTan KCheong CChia J(2013)Enhancing the scalability of multi-objective optimization via restricted Boltzmann machine-based estimation of distribution algorithmInformation Sciences10.1016/j.ins.2013.06.037248(191-213)Online publication date: Nov-2013
https://doi.org/10.1016/j.ins.2013.06.037
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