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

18th International Conference on Parallel Problem Solving from Nature (PPSN)

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

ISBN: (纸本)9783031700705;9783031700712

A class of metaheuristic techniques called estimation-of-distribution algorithms (EDAs) is employed in optimization as a more sophisticated substitute for traditional strategies like evolutionary algorithms. EDAs generally drive the search for the optimum by creating probabilistic models of potential candidate solutions through repeated sampling and selection from the underlying search space. Most theoretical research on EDAs has focused on pseudo-Boolean optimization. Jedidia et al. (GECCO 2023) introduced a framework for EDAs for optimizing problems involving multi-valued decision variables. In addition, they conduct a mathematical runtime analysis of a multi-valued UMDA on the r-valued LEADINGONES function. Using their framework, here we focus on the multi-valued compact genetic algorithm (r-cGA) and provide a first runtime analysis of a generalized OneMax function. To prove our results, we investigate the effect of genetic drift and progress of the probabilistic model towards the optimum. After finding the right algorithm parameters, we prove that the r-cGA solves this r-valued OneMax problem efficiently. We establish that the runtime bound is O(r(2) n log(2) r log(3) n) with high probability.

关键词： estimation-of-distribution algorithms multi-valued compact genetic algorithm genetic drift OneMax

来源：评论

学校读者我要写书评

暂无评论

Improving DSMGA-II Performance on Hierarchical Problems by Introducing Preservative Back Mixing 22

Improving DSMGA-II Performance on Hierarchical Problems by I...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Ngai, Chi-Meng Yu, Tian-Li Natl Taiwan Univ Dept Elect Engn Taiwan Evolutionary Intelligence Lab Taipei Taiwan

ISBN: (纸本)9781450392686

Inspired from the optimal mixing in the linkage tree gene-pool optimal mixing evolutionary algorithm, the dependent structure matrix genetic algorithm II (DSMGA-II) is one of the state-of-the-art model-building genetic algorithms. It obtains the patterns from successful restricted mixing and uses them during the back mixing (BM) to remove spurious linkage information such that the linkage information in need stands out. However, such techniques can be misled in hierarchical problems where the linkages in latter layers are mistreated as spurious in BM. There has been diversity preservation scheme developed for DSMGA-II by monitoring the entropy, but such technique impairs the exploration ability of DSMGA-II on plateau. To solve this issue, this paper proposes the preservative back mixing (PBM), a modified version of BM. Specifically, PBM features (i) the adaptive back mixing that automatically adjusts the power of BM and (ii) the linkage preservation that preserves the linkages among complementary patterns. This paper conducted several experiments to show that, PBM improves DSMGA-II greatly on hierarchical problems including the hierarchical trap and hierarchical exclusive-or while the NFE performances on other problems are not compromised by much.

关键词： Genetic algorithms estimation-of-distribution algorithms Optimal Mixing Linkage Learning Model Building

来源：评论

学校读者我要写书评

暂无评论

Theoretical Study of Optimizing Rugged Landscapes with the cGA 17th

Theoretical Study of Optimizing Rugged Landscapes with the c...

引用

17th International Conference on Parallel Problem Solving from Nature (PPSN)

作者： Friedrich, Tobias Koetzing, Timo Neumann, Frank Radhakrishnan, Aishwarya Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Adelaide Sch Comp Sci Adelaide SA Australia

ISBN: (纸本)9783031147210;9783031147203

estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the ONEMAX function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with n(1- epsilon) many ls, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with n(1/2 + o(1)) many 1s, even for noise with small variance.

关键词： estimation-of-distribution algorithms Compact genetic algorithm Random local search Evolutionary algorithms Run time analysis Theory

来源：评论

学校读者我要写书评

暂无评论

The Compact Genetic Algorithm Struggles on Cliff Functions

The Compact Genetic Algorithm Struggles on Cliff Functions

引用

Genetic and Evolutionary Computation Conference (GECCO)

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

ISBN: (纸本)9781450392372

The compact genetic algorithm (cGA) is a non-elitist estimation of distribution algorithm which has shown to be able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. In this paper, we investigate the cGA on the Cliff function for which it has been 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 around the Cliff. Our experimental results indicate that the cGA requires exponential time for all values of the update strength... 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.. where the expected optimization time drops from n Theta((n)) to 2 Theta((n)).

关键词： estimation-of-distribution algorithms compact genetic algorithm evolutionary algorithms running time analysis theory.

来源：评论

学校读者我要写书评

暂无评论

The Complex Parameter Landscape of the Compact Genetic Algorithm

引用

ALGORITHMICA 2021年第4期83卷 1096-1137页

作者： Lengler, Johannes Sudholt, Dirk Witt, Carsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Univ Sheffield Sheffield S1 4DP S Yorkshire England Tech Univ Denmark DTU Compute Lyngby Denmark

The compact Genetic Algorithm (cGA) evolves a probability distribution favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We study the intricate dynamics of the cGA on the test function OneMax, and how its performance depends on the hypothetical population size K, which determines how quickly decisions about promising bit values are fixated in the probabilistic model. It is known that the cGA and the Univariate Marginal distribution Algorithm (UMDA), a related algorithm whose population size is called lambda, run in expected time O(nlogn) when the population size is just large enough (K=Theta(nlogn) and lambda=Theta(nlogn) , respectively) to avoid wrong decisions being fixated. The UMDA also shows the same performance in a very different regime (lambda=Theta(logn), equivalent to K=Theta(logn) in the cGA) with much smaller population size, but for very different reasons: many wrong decisions are fixated initially, but then reverted efficiently. If the population size is even smaller (o(logn)), the time is exponential. We show that population sizes in between the two optimal regimes are worse as they yield larger runtimes: we prove a lower bound of omega(K1/3n+nlogn) for the cGA on OneMax for K=O(n/log2n). For K=omega(log3n) the runtime increases with growing K before dropping again to O(Kn+nlogn) for K=omega(nlogn) . This suggests that the expected runtime for the cGA is a bimodal function in K with two very different optimal regions and worse performance in between.

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

来源：评论

学校读者我要写书评

暂无评论

On the impact of linkage learning, gene-pool optimal mixing, and non-redundant encoding on permutation optimization

引用

SWARM AND EVOLUTIONARY COMPUTATION 2022年 70卷 101044-101044页

作者： Guijt, Arthur Ngoc Hoang Luong Bosman, Peter A. N. de Weerdt, Mathijs Delft Univ Technol Delft Netherlands Ctr Wiskunde Informat Amsterdam Netherlands VNU HCM Univ Informat Technol UIT Hanoi Vietnam

Gene-pool Optimal Mixing Evolutionary algorithms (GOMEAs) have been shown to achieve state-of-the-art results on various types of optimization problems with various types of problem variables. Recently, a GOMEA for permutation spaces was introduced by leveraging the random keys encoding, obtaining promising first results on permutation flow shop instances. A key cited strength of GOMEAs is linkage learning, i.e., the ability to determine and leverage, during optimization, key dependencies between problem variables. However, the added value of linkage learning was not tested in depth for permutation GOMEA. Here, we introduce a new version of permutation GOMEA, called qGOMEA, that works directly in permutation space, removing the redundancy of using random keys. We additionally consider various linkage information sources, including random noise, in both GOMEA variants, and compare performance with various classic genetic algorithms on a wider range of problems than considered before. We find that, although the benefits of linkage learning are clearly visible for various artificial benchmark problems, this is far less the case for various real-world inspired problems. Finally, we find that qGOMEA performs best, and is more applicable to a wider range of permutation problems.

关键词： Genetic algorithms estimation-of-distribution algorithms Permutation problems

来源：评论

学校读者我要写书评

暂无评论

From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm

From Understanding Genetic Drift to a Smart-Restart Paramete...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Doerr, Benjamin Zheng, Weijie Inst Polytech Paris Lab Informat LIX Ecole Polytech CNRS Palaiseau France Southern Univ Sci & Technol Guangdong Prov Key Lab Brain Inspired Intelligent Dept Comp Sci & Engn Shenzhen Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei Peoples R China

ISBN: (纸本)9781450371285

One of the key difficulties in using estimation-of-distribution algorithms is choosing the population sizes appropriately: Too small values lead to genetic drift, which can cause enormous difficulties. In the regime with no genetic drift, however, often the runtime is roughly proportional to the population size, which renders large population sizes inefficient. Based on a recent quantitative analysis which population sizes lead to genetic drift, we propose a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size without spending too much time in situations unfavorable due to genetic drift. We prove an easy mathematical runtime guarantee for this algorithm and conduct an extensive experimental analysis on four classic benchmark problems. The former shows that under a natural assumption, our algorithm has a performance similar to the one obtainable from the best population size. The latter confirms that missing the right population size can be highly detrimental and shows that our algorithm as well as a previously proposed parameter-less one based on parallel runs avoids such pitfalls. Comparing the two approaches, ours profits from its ability to abort runs which are likely to be stuck in a genetic drift situation.

关键词： estimation-of-distribution algorithms parameter-less algorithm empirical study theory

来源：评论

学校读者我要写书评

暂无评论

Upper Bounds on the Running Time of the Univariate Marginal distribution Algorithm on OneMax

引用

ALGORITHMICA 2019年第2期81卷 632-667页

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

The Univariate Marginal distribution Algorithm (UMDA) is a randomized search heuristic that builds a stochastic model of the underlying optimization problem by repeatedly sampling. solutions and adjusting the model according to the best mu samples. We present a running time analysis of the UMDA on the classical OneMax benchmark function for wide ranges of the parameters mu and lambda. If mu >= c log n for some constant c > 0 and lambda = (1+ Theta(1)) mu, we obtain a general bound O (mu n) on the expected running time. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval [1/n, 1 - 1/n]. If mu >= c' root n log n for a constant c' > 0 and lambda = (1 + Theta(1)) mu, the behavior of the algorithm changes and the bound on the expected running time becomes O(mu root n), which typically holds even if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound Omega (mu root n + n log n) by Krejca and Witt (Proceedings of FOGA 2017, ACM Press, New York, pp 65-79, 2017) and turn out to be tight for the two very different choices mu = c log n and mu = c' root n log n. They also improve the previously best known upper bound O(n log n log log n) by Dang and Lehre (Proceedings of GECCO ' 15, ACM Press, New York, pp 513-518, 2015) that was established for mu = c log n and lambda = (1+ Theta(1)) mu.

关键词： Randomized search heuristics estimation-of-distribution algorithms UMDA Running time analysis

来源：评论

学校读者我要写书评

暂无评论

GAMBIT: A Parameterless Model-Based Evolutionary Algorithm for Mixed-Integer Problems

引用

EVOLUTIONARY COMPUTATION 2018年第1期26卷 117-143页

作者： Sadowski, Krzysztof L. Thierens, Dirk Bosman, Peter A. N. Univ Utrecht Dept Comp Sci Utrecht Netherlands CWI Amsterdam Netherlands

Learning and exploiting problem structure is one of the key challenges in optimization. This is especially important for black-box optimization (BBO) where prior structural knowledge of a problem is not available. Existing model-based Evolutionary algorithms (EAs) are very efficient at learning structure in both the discrete, and in the continuous domain. In this article, discrete and continuous model-building mechanisms are integrated for the Mixed-Integer (MI) domain, comprising discrete and continuous variables. We revisit a recently introduced model-based evolutionary algorithm for the MI domain, the Genetic Algorithm for Model-Based mixed-Integer opTimization (GAMBIT). We extend GAMBIT with a parameterless scheme that allows for practical use of the algorithm without the need to explicitly specify any parameters. We furthermore contrast GAMBIT with other model-based alternatives. The ultimate goal of processing mixed dependences explicitly in GAMBIT is also addressed by introducing a new mechanism for the explicit exploitation of mixed dependences. We find that processing mixed dependences with this novel mechanism allows for more efficient optimization. We further contrast the parameterless GAMBIT with Mixed-Integer Evolution Strategies (MIES) and other state-of-the-art MI optimization algorithms from the General Algebraic Modeling System (GAMS) commercial algorithm suite on problems with and without constraints, and show that GAMBIT is capable of solving problems where variable dependences prevent many algorithms from successfully optimizing them.

关键词： Genetic algorithms estimation-of-distribution algorithms mixed-integer optimization

来源：评论

学校读者我要写书评

暂无评论

Medium Step Sizes are Harmful for the Compact Genetic Algorithm 18

Medium Step Sizes are Harmful for the Compact Genetic Algori...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Lengler, Johannes Sudholt, Dirk Witt, Carsten Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Univ Sheffield Dept Comp Sci Sheffield S Yorkshire England Tech Univ Denmark DTU Compute Lyngby Denmark

ISBN: (纸本)9781450356183

We study the intricate dynamics of the Compact Genetic Algorithm (cGA) on ONEMAX, and how its performance depends on the step size 1/K, that determines how quickly decisions about promising bit values are fixed in the probabilistic model. It is known that cGA and UMDA, a related algorithm, run in expected time O(n log n) when the step size is just small enough (K = Theta(root n log n) to avoid wrong decisions being fixed. UMDA also shows the same performance in a very different regime (equivalent to K = Theta(log n) in the cGA) with much larger steps sizes, but for very different reasons: many wrong decisions are fixed initially, but then reverted efficiently. We show that step sizes in between these two optimal regimes are harmful as they yield larger runtimes: we prove a lower bound Omega(K(1/3)n + n log n) for the cGA on ONEMAX for K = O(root n/log(2) n). For K = Omega(log(3) n) the runtime increases with growing K before dropping again to O(K root n + nlogn) for K = Omega(root n log n). This suggests that the expected runtime for cGA is a bimodal function in K with two very different optimal regions and worse performance in between.

关键词： estimation-of-distribution algorithms compact genetic algorithm evolutionary algorithms running time analysis theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：