检索结果-内蒙古大学图书馆

Genetic and Evolutionary Computation Conference (GECCO)

作者： Ben Jedidia, Firas Doerr, Benjamin Krejca, Martin S. Inst Polytech Paris Ecole Polytech Palaiseau France Inst Polytech Paris Ecole Polytech CNRS Lab Informat LIX Palaiseau France

ISBN: (纸本)9798400701191

With apparently all research on estimation-of-distribution algorithms (EDAs) concentrated on pseudo-Boolean optimization and permutation problems, we undertake the first steps towards using EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems. To this aim, we propose a natural way to extend the known univariate EDAs to such variables. Different from a naive reduction to the binary case, it avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued variables. Roughly speaking, when the variables take r different values, the time for genetic drift to become critical is r times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen r times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the.. -valued LeadingOnes problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in O (r log(r)(2) n(2) log(n)) function evaluations. Overall, our work shows that EDAs can be adjusted to multi-valued problems and gives advice on how to set their parameters.

关键词： estimation-of-distribution algorithms univariate marginal distribution algorithm evolutionary algorithms genetic drift LeadingOnes benchmark

来源：评论

学校读者我要写书评

暂无评论

estimation-of-distribution algorithms for multi-valued decision variables

引用

THEORETICAL COMPUTER SCIENCE 2024年 1003卷

作者： Ben Jedidia, Firas Doerr, Benjamin Krejca, Martin S. Ecole Polytech Inst Polytech Paris F-91120 Palaiseau France Ecole Polytech Inst Polytech Paris Lab Informat LIX CNRS 1 Rue Honore Estienne Orves F-91120 Palaiseau France

The majority of research on estimation -of -distribution algorithms (EDAs) concentrates on pseudoBoolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a na & iuml;ve reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi -valued, categorical variables. Roughly speaking, when the variables take r different values, the time for genetic drift to become significant is r times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen r times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the r -valued L EADING O NES problem. We prove that with the right parameters, the multi -valued UMDA solves this problem efficiently in O ( r ln( r ) 2 n 2 ln( n )) function evaluations. This bound is nearly tight as our lower bound Omega( r ln( r ) n 2 ln( n )) shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi -valued setting, and it gives advice on how to set the main parameters of multi -values EDAs.

关键词： estimation-of-distribution algorithms Univariate marginal distribution algorithm Evolutionary algorithms Genetic drift LeadingOnes benchmark

来源：评论

学校读者我要写书评

暂无评论

The importance of implementation details and parameter settings in black-box optimization: a case study on Gaussian estimation-of-distribution algorithms and circles-in-a-square packing problems

引用

SOFT COMPUTING 2018年第4期22卷 1209-1223页

作者： Bosman, Peter A. N. Gallagher, Marcus Peter AN Bosman Ctr Wiskunde & Informat CWI POB 94079 NL-1090 GB Amsterdam Netherlands Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia

We consider a scalable problem that has strong ties with real-world problems, can be compactly formulated and efficiently evaluated, yet is not trivial to solve and has interesting characteristics that differ from most commonly used benchmark problems: packing n circles in a square (CiaS). Recently, a first study that used basic Gaussian EDAs indicated that typically suggested algorithmic parameter settings do not necessarily transfer well to the CiaS problem. In this article, we consider also AMaLGaM, an enhanced Gaussian EDA, as well as arguably the most powerful real-valued black-box optimization algorithm to date, CMA-ES, which can also be seen as a further enhanced Gaussian EDA. We study whether the well-known performance on typical benchmark problems extends to the CiaS problem. We find that although the enhancements over a basic Gaussian EDA result in superior performance, the further efficiency enhancements in CMA-ES are not highly impactful. Instead, the most impactful features are how constraint handling is performed, how large the population size is, whether a full covariance matrix is used and whether restart techniques are used. We further show that a previously published version of AMaLGaM that does not require the user to set the the population size parameter is capable of solving the problem and we derive the scalability of the required number of function evaluations to solve the problem up to 99.99 % of the known optimal value for up to 30 circles.

关键词： Black-box optimization Evolutionary computation estimation-of-distribution algorithms Parameter tuning Constraint handling Circles-in-a-square packing

来源：评论

学校读者我要写书评

暂无评论

On the Choice of the Update Strength in estimation-of-distribution algorithms and Ant Colony Optimization

引用

ALGORITHMICA 2019年第4期81卷 1450-1489页

作者： Sudholt, Dirk Witt, Carsten Univ Sheffield Sheffield S1 4DP S Yorkshire England Tech Univ Denmark DTU Compute Lyngby Denmark

Probabilistic model-building Genetic algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size1/K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of (Knlogn) and (logn) both algorithms efficiently optimize OneMax in expected time (nlogn). Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.

关键词： Ant colony optimization estimation-of-distribution algorithms Genetic algorithms Probabilistic model-building Genetic algorithms Runtime analysis Theory of randomized search heuristics

来源：评论

学校读者我要写书评

暂无评论

Matching inductive search bias and problem structure in continuous estimation-of-distribution algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第3期185卷 1246-1264页

作者： Bosman, Peter A. N. Grahl, Jorn Ctr Math & Comp Sci NL-1090 GB Amsterdam Netherlands Univ Mannheim Dept Logist D-68131 Mannheim Germany

Research into the dynamics of Genetic algorithms (GAs) has led to the field of estimation-of-distribution algorithms (EDAs). For discrete search spaces, EDAs have been developed that have obtained very promising results on a wide variety of problems. In this paper we investigate the conditions under which the adaptation of this technique to continuous search spaces fails to perform optimization efficiently. We show that without careful interpretation and adaptation of lessons learned from discrete EDAs, continuous EDAs will fail to perform efficient optimization on even some of the simplest problems. We reconsider the most important lessons to be learned in the design of EDAs and subsequently show how we can use this knowledge to extend continuous EDAs that were obtained by straightforward adaptation from the discrete domain so as to obtain an improvement in performance. Experimental results are presented to illustrate this improvement and to additionally confirm experimentally that a proper adaptation of discrete EDAs to the continuous case indeed requires careful consideration. (C) 2006 Elsevier B.V. All rights reserved.

关键词： estimation-of-distribution algorithms numerical optimization normal distribution convergence dynamics adaptive variance

来源：评论

学校读者我要写书评

暂无评论

On Crossing Fitness Valleys with Majority-Vote Crossover and estimation-of-distribution algorithms 21

On Crossing Fitness Valleys with Majority-Vote Crossover and...

引用

16th ACM/SIGEVO Conference on Foundations of Genetic algorithms (FOGA)

作者： Witt, Carsten Tech Univ Denmark DTU Compute Lyngby Denmark

ISBN: (纸本)9781450383523

The benefits of using crossover in crossing fitness gaps have been studied extensively in evolutionary computation. Recent runtime results show that majority-vote crossover is particularly efficient at optimizing the well-known JUMP benchmark function that includes a fitness gap next to the global optimum. Also estimation-of-distribution algorithms (EDAs), which use an implicit crossover, are much more efficient on JUMP than typical mutation-based algorithms. However, the allowed gap size for polynomial runtimes with EDAs is at most logarithmic in the problem dimension n. In this paper, we investigate variants of the JUMP function where the gap is shifted and appears in the middle of the typical search trajectory. Such gaps can still be overcome efficiently in time O (n log n) by majority-vote crossover and an estimation-of-distribution algorithm, even for gap sizes almost root n. However, if the global optimum is located in the gap instead of the usual all-ones string, majority-vote crossover would nevertheless approach the all-ones string and be highly inefficient. In sharp contrast, an EDA can still find such a shifted optimum efficiently. Thanks to a general property called fair sampling, the EDA will with high probability sample from almost every fitness level of the function, including levels in the gap, and sample the global optimum even though the overall search trajectory points towards the all-ones string. Finally, we derive limits on the gap size allowing efficient runtimes for the EDA.

关键词： randomized search heuristics crossover estimation-of-distribution algorithms jump function multimodal functions runtime analysis

来源：评论

学校读者我要写书评

暂无评论

Bivariate estimation-of-distribution algorithms Can Find an Exponential Number of Optima

Bivariate Estimation-of-Distribution Algorithms Can Find an ...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Doerr, Benjamin Krejca, Martin S. Inst Polytech Paris Lab Informat LIX CNRS Ecole Polytech Palaiseau France Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9781450371285

Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms (EAs) typically converge only to a single solution. While this can be counteracted by applying niching strategies, the number of optima is nonetheless trivially bounded by the population size. estimation-of-distribution algorithms (EDAs) are an alternative, maintaining a probabilistic model of the solution space instead of an explicit population. Such a model is able to implicitly represent a solution set that is far larger than any realistic population size. To support the study of how optimization algorithms handle large sets of optima, we propose the test function EQUALBLOCKS-ONEMAX (EBOM). It has an easy to optimize fitness landscape, however, with an exponential number of optima. We show that the bivariate EDA mutual-information-maximizing input clustering (MIMIC), without any problem-specific modification, quickly generates a model that behaves very similarly to a theoretically ideal model for that function, which samples each of the exponentially many optima with the same maximal probability.

关键词： estimation-of-distribution algorithms probabilistic model building empirical study

来源：评论

学校读者我要写书评

暂无评论

From Understanding Genetic Drift to a Smart-Restart Mechanism for estimation-of-distribution algorithms

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2023年第1期24卷 1−40-1−40页

作者： Zheng, Weijie Doerr, Benjamin Harbin Inst Technol Int Res Inst Artificial Intelligence Sch Comp Sci & Technol Shenzhen 518055 Peoples R China Inst Polytech Paris Ecole Polytech Lab Informat LIX CNRS F-91120 Palaiseau France

estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). Too small values lead to the undesired effect of genetic drift, while larger values slow down the process. Building on a quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter regimes. Via a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. For many situations where the optimal parameter values are known, this shows that the restart scheme automatically finds these optimal values, leading to the asymptotically optimal performance. We also conduct an extensive experimental analysis. On four classic benchmarks, the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. We also conduct experiments with PBIL (cross-entropy algorithm) on the max-cut problem and the bipartition problem. Again, the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance.

关键词： estimation-of-distribution algorithms genetic drift restart strategy ran-domized search heuristics theory of computing

来源：评论

学校读者我要写书评

暂无评论

From understanding genetic drift to a smart-restart mechanism for estimation-of-distribution algorithms

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2023年第1期24卷 13884-13923页

作者： Weijie Zheng Benjamin Doerr School of Computer Science and Technology International Research Institute for Artificial Intelligence Harbin Institute of Technology Shenzhen China Laboratoire d'Informatique (LIX) École Polytechnique CNRS Institut Polytechnique de Paris PalaiseauFrance

estimation-of-distribution algorithms (EDAs) are optimization algorithms that learn a distribution from which good solutions can be sampled easily. A key parameter of most EDAs is the sample size (population size). Too small values lead to the undesired effect of genetic drift, while larger values slow down the *** on a quantitative analysis of how the population size leads to genetic drift, we design a smart-restart mechanism for EDAs. By stopping runs when the risk for genetic drift is high, it automatically runs the EDA in good parameter *** a mathematical runtime analysis, we prove a general performance guarantee for this smart-restart scheme. For many situations where the optimal parameter values are known, this shows that the restart scheme automatically finds these optimal values, leading to the asymptotically optimal *** also conduct an extensive experimental analysis. On four classic benchmarks, the smart-restart scheme leads to a performance close to the one obtainable with optimal parameter values. We also conduct experiments with PBIL (cross-entropy algorithm) on the max-cut problem and the bipartition problem. Again, the smart-restart mechanism finds much better values for the population size than those suggested in the literature, leading to a much better performance.

关键词： estimation-of-distribution algorithms genetic drift restart strategy randomized search heuristics theory of computing

来源：评论

学校读者我要写书评

暂无评论

The Compact Genetic Algorithm Struggles on Cliff Functions

引用

ALGORITHMICA 2025年第4期87卷 507-536页

作者： Neumann, Frank Sudholt, Dirk Witt, Carsten Univ Adelaide Sch Comp & Math Sci Optimisat & Logist Adelaide SA 5005 Australia Univ Passau Fac Comp Sci & Math D-94032 Passau Germany Tech Univ Delnmark DTU Compute DK-2800 Lyngby Denmark

estimation of distribution algorithms (EDAs) are general-purpose optimizers that maintain a probability distribution over a given search space. This probability distribution is updated through sampling from the distribution and a reinforcement learning process which rewards solution components that have shown to be part of good quality samples. The compact genetic algorithm (cGA) is a non-elitist EDA able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. We investigate the cGA on the Cliff function for which it was shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the Cliff function and investigate its dynamics both experimentally and theoretically. Our experimental results indicate that the cGA requires exponential time for all values of the update strength 1/K. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for K where the expected optimization time drops from n Theta(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n<^>{\Theta (n)}$$\end{document} to 2 Theta(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2<^>{\Theta (n)}$$\end{document}.

关键词： estimation-of-distribution algorithms Compact genetic algorithm Evolutionary algorithms Running time analysis Theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：