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

Genetic and Evolutionary Computation Conference (GECCO)

作者： Bosman, Peter A. N. Ngoc Hoang Luong Thierens, Dirk CWI POB 94079 NL-1090 GB Amsterdam Netherlands Univ Utrecht Dept Comp Sci POB 80089 NL-3508 TB Utrecht Netherlands

ISBN: (纸本)9781450342063

The recently introduced Gene-pool Optimal Mixing Evelutionary Algorithm (GOMEA) family, which includes the Linkage Tree Genetic Algorithm (LICA), has been shown to scale excellently on a variety of discrete, Cartesian-space, optimization problems. This paper shows that GOMEA can quite straightforwardly also be used to solve permutation optimization problems by employing the random keys encoding of permutations. As a test problem, we consider permutation flowshop scheduling, minimizing the total flow time an 120 different problem :instances (Taillard benchmark). The performance of GOMEA is compared with the recently published generalized Mallows estimation of distribution algorithm (GM-EDA). Statistical tests show that results of GOMEA variants are almost always significantly better than results of GM-EDA. Moreover, even without using local search, the new GOMEA variants obtained the best-known solution for 30 instances in every run and even new upper bounds for several instances. Finally, the time complexity per solution for building a dependency model to drive variation is an order of complexity less for GOMEA than for GM-FDA, al together suggesting that GOMEA also holds much promise for permutation optimization.

关键词： Genetic algorithms estimation-of-distribution algorithms Linkage learning Optimal Mixing Pennutation Problems Random Keys Scheduling

来源：评论

学校读者我要写书评

暂无评论

Update Strength in EDAs and ACO: How to Avoid Genetic Drift 16

Update Strength in EDAs and ACO: How to Avoid Genetic Drift

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Sudholt, Dirk Witt, Carsten Univ Sheffield Dept Comp Sci Sheffield S Yorkshire England Tech Univ Denmark DTU Compute Lyngby Denmark

ISBN: (纸本)9781450342063

We provide a rigorous runtime analysis concerning the update strength, a vital parameter in probabilistic model-building GAs such as the step size 1/K in the compact Genetic Algorithm (cGA) and the evaporation factor rho in ACO. While a large update strength is desirable for exploitation, there is a general trade-off : too strong updates can lead to genetic drift and poor performance. We demonstrate this trade-off for the cGA and a simple MMAS ACO algorithm on the OneMax function. More precisely, we obtain lower bounds on the expected runtime of Omega(K root n + n log n) and Omega(root n/rho + n log n), respectively, showing that the update strength should be limited to 1/K, rho = O (1/(root n log n)). In fact, choosing 1/K, rho similar to 1/(root n log n) both algorithms efficiently optimize OneMax in expected time O (n log n). Our analyses provide new insights into the stochastic behavior of probabilistic model-building GAs and propose new guidelines for setting the update strength in global optimization.

关键词： Ant Colony Optimization estimation-of-distribution algorithms Iteration-Best Update Genetic Drift Runtime Analysis Theory

来源：评论

学校读者我要写书评

暂无评论

A Novel Population-based Multi-Objective CMA-ES and the Impact of Different Constraint Handling Techniques 14

A Novel Population-based Multi-Objective CMA-ES and the Impa...

引用

16th Genetic and Evolutionary Computation Conference (GECCO)

作者： Rodrigues, Silvio Bauer, Pavol Bosman, Peter A. N. Delft Univ Technol TUDelft Delft Netherlands CWI Amsterdam Netherlands

ISBN: (纸本)9781450326629

The Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) is a well-known, state-of-the-art optimization algorithm for single-objective real-valued problems, especially in black-box settings. Although several extensions of CMAES to multi-objective (MO) optimization exist, no extension incorporates a key component of the most robust and general CMA-ES variant: the association of a population with each Gaussian distribution that drives optimization. To achieve this, we use a recently introduced framework for extending population-based algorithms from single- to multi-objective optimization. We compare, using six well-known benchmark problems, the performance of the newly constructed MO-CMA- ES with existing variants and with the estimation of distribution algorithm (EDA) known as iMAMaLGaM, that is also an instance of the framework, extending the single- objective EDA iAMaLGaM to MO. Results underline the advantages of being able to use populations. Because many real-world problems have constraints, we also study the use of four constraint-handling techniques. We find that CMA-ES is typically less robust to these techniques than iAMaLGaM. Moreover, whereas we could verify that a penalty method that was previously used in literature leads to fast convergence, we also find that it has a high risk of finding only nearly, but not entirely, feasible solutions. We therefore propose that other constraint-handling techniques should be preferred in general.

关键词： algorithms Performance Experimentation CMA-ES estimation-of-distribution algorithms Mixture distributions Multi-Objective Optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Benchmarking Parameter-Free AMaLGaM on Functions With and Without Noise

引用

EVOLUTIONARY COMPUTATION 2013年第3期21卷 445-469页

作者： Bosman, Peter A. N. Grahl, Joern Thierens, Dirk Ctr Wiskunde & Informat NL-1090 GB Amsterdam Netherlands Johannes Gutenberg Univ Mainz Dept Informat Syst & Business Adm D-55128 Mainz Germany Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

We describe a parameter-free estimation-of-distribution algorithm (EDA) called the adapted maximum-likelihood Gaussian model iterated density-estimation evolutionary algorithm (AMaLGaM-IDEA, or AMaLGaM for short) for numerical optimization. AMaLGaM is benchmarked within the 2009 black box optimization benchmarking (BBOB) framework and compared to a variant with incremental model building (iAMaLGaM). We study the implications of factorizing the covariance matrix in the Gaussian distribution, to use only a few or no covariances. Further, AMaLGaM and iAMaLGaM are also evaluated on the noisy BBOB problems and we assess how well multiple evaluations per solution can average out noise. Experimental evidence suggests that parameter-free AMaLGaM can solve a wide range of problems efficiently with perceived polynomial scalability, including multimodal problems, obtaining the best or near-best results among all algorithms tested in 2009 on functions such as the step-ellipsoid and Katsuuras, but failing to locate the optimum within the time limit on skew Rastrigin-Bueche separable and Lunacek bi-Rastrigin in higher dimensions. AMaLGaM is found to be more robust to noise than iAMaLGaM due to the larger required population size. Using few or no covariances hinders the EDA from dealing with rotations of the search space. Finally, the use of noise averaging is found to be less efficient than the direct application of the EDA unless the noise is uniformly distributed. AMaLGaM was among the best performing algorithms submitted to the BBOB workshop in 2009.

关键词： estimation-of-distribution algorithms Gaussian distribution maximum likelihood adaptive computation optimization black box optimization benchmarking

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Problem Solving with the Linkage Tree Genetic Algorithm 13

Hierarchical Problem Solving with the Linkage Tree Genetic A...

引用

15th Genetic and Evolutionary Computation Conference (GECCO)

作者： Thierens, Dirk Bosman, Peter A. N. Univ Utrecht Utrecht Netherlands CWI Amsterdam Netherlands

ISBN: (纸本)9781450319638

Hierarchical problems represent an important class of nearly decomposable problems. The concept of near decomposability is central to the study of complex systems. When little a priori information is available, a black box problem solver is needed to optimize these hierarchical problems. The solver should be able to learn linkage information, and to preserve and test partial solutions at different levels in the hierarchy. Two well known benchmark functions - shuffled Hierarchical If-And-Only-If (HIFF) and shuffled Hierarchical Trap (HTRAP) functions - exemplify the challenges posed by hierarchical problems. Standard genetic algorithms are unable to solve these problems, and specific methods, like SEAM and hBOA, have been designed to address them. In this paper, we investigate how the recently developed Linkage Tree Genetic Algorithm (LTGA) performs on these hierarchical problems. We compare LTGA with SEAM and hBOA on HIFF and HTRAP functions. Results show that, although LTGA is a simple algorithm compared to SEAM and hBOA, it nevertheless is a very efficient, reliable, and scalable algorithm for solving the randomly shuffled versions of HIFF and HTRAP, two hard, hierarchical problems.

关键词： Evolutionary Computation estimation-of-distribution algorithms Hierarchical Problems Linkage Learning Optimal Mixing Linkage Tree Genetic Algorithm

来源：评论

学校读者我要写书评

暂无评论

More Concise and Robust Linkage Learning by Filtering and Combining Linkage Hierarchies 13

More Concise and Robust Linkage Learning by Filtering and Co...

引用

15th Genetic and Evolutionary Computation Conference (GECCO)

作者： Bosman, Peter A. N. Thierens, Dirk CWI POB 94079 NL-1090 GB Amsterdam Netherlands Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands

ISBN: (纸本)9781450319638

Genepool Optimal Mixing Evolutionary algorithms (GOMEAs) were recently proposed as a new way of designing linkage-friendly, efficiently-scalable evolutionary algorithms (EAs). GOMEAs combine the building of linkage models with an intensive, greedy mixing procedure. Recent results indicate that the use of hierarchical linkage models in GOMEAs lead to the most robust and efficient performance. Two of such GOMEA instances are the Linkage Tree Genetic Algorithm (LTGA) and the Multi-scale Linkage Neighbors Genetic Algorithm (MLNGA). The linkage models in these GOMEAs have their individual merits and drawbacks. In this paper, we propose enhancement techniques targeted at filtering out superfluous linkage sets from hierarchical linkage models and we consider a way to construct a linkage model that combines the strengths of different linkage models. We then propose a new GOMEA instance, called the Linkage Trees and Neighbors Genetic Algorithm (LTNGA), that combines the models of LTGA and MLNGA. LTNGA performs comparable or better than the best of either LTGA or MLNGA on various problems, including typical linkage benchmark problems and instances of the well-known combinatorial problem MAXCUT, especially when the proposed filtering techniques are used.

关键词： Genetic algorithms estimation-of-distribution algorithms Linkage learning Optimal Mixing

来源：评论

学校读者我要写书评

暂无评论

Model-based evolutionary algorithms

Model-based evolutionary algorithms

引用

15th Annual Conference on Genetic and Evolutionary Computation, GECCO 2013

作者： Thierens, Dirk Bosman, Peter A.N. Department of Information and Computing Sciences Utrecht University Utrecht Netherlands Centrum Wiskunde and Informatica - CWI Amsterdam Netherlands

来源：评论

学校读者我要写书评

暂无评论

Predetermined versus Learned Linkage Models 12

Predetermined versus Learned Linkage Models

引用

14th International Conference on Genetic and Evolutionary Computation Conference (GECCO)

作者： Thierens, Dirk Bosman, Peter A. N. Univ Utrecht Inst Informat & Comp Sci NL-3508 TC Utrecht Netherlands

ISBN: (纸本)9781450311779

The linkage tree genetic algorithm (LTGA) learns, each generation, a linkage model by building a hierarchical cluster tree. The LTGA is an instance of the more general gene-pool optimal mixing evolutionary algorithm (GOMEA) that uses a family of subsets (FOS) linkage model. We compare the performance of the linkage model learning LTGA with several predetermined FOS linkage models applied by GOMEA. The predetermined models are matched to the underlying problem structure off our benchmark functions: onemax, deceptive trap functions, maximal overlapping nearest-neighbor NK-landscapes, and weighted MAXCUT problems. Although the a priori fixed models are specifically designed to capture the interactions between the problem variables, experimental results show that - for problems with intricate interaction structure - they are actually less efficient than LTGA that dynamically learns a hierarchical tree model. Some of these observations were unexpected and raise the question of what exactly is the optimal linkage structure for a given problem as used by GOMEA. In the case of the NK-problem a linkage model that is an accurate description of the underlying additively decomposable fitness structure is clearly not an optimal linkage model. Being able to rebuild the linkage model each generation has clear benefits above using fixed, predetermined linkage models.

关键词： Evolutionary Computation Genetic algorithms estimation-of-distribution algorithms Linkage Learning Optimal Mixing Algorithm

来源：评论

学校读者我要写书评

暂无评论

Linkage Neighbors, Optimal Mixing and Forced Improvements in Genetic algorithms 12

Linkage Neighbors, Optimal Mixing and Forced Improvements in...

引用

14th International Conference on Genetic and Evolutionary Computation Conference (GECCO)

作者： Bosman, Peter A. N. Thierens, Dirk CWI NL-1090 GB Amsterdam Netherlands

ISBN: (纸本)9781450311779

Recently, the Linkage Tree Genetic Algorithm (LTGA) was introduced as one of the latest developments in a line of EA research that studies building models to capture and exploit linkage information between problem variables. LTGA was reported to exhibit excellent performance on several linkage benchmark problems, mainly attributed to use of the LT linkage model. In this paper we consider a technique called Forced Improvements (FI), that allows LTGA to converge to a single solution without requiring an explicit, diversity-reducing, selection step. We further consider a different linkage model, called Linkage Neighbors (LN), that is more flexible, yet can be learned equally efficiently from data. Even with the simplest learning approach for configuring the LN, better results are obtained on the linkage benchmark problems than when the LT model is used However, on weighted MAXCUT (a combinatorial optimization problem), very poor results are obtained and a more involved multiscale LN variant is required to obtain a performance near that of LTGA. Our results underline the advantage of processing linkage in a single model on multiple scales as well as the importance of also considering problems other problems than common linkage benchmark problems when judging the merits of linkage learning techniques.

关键词： Genetic algorithms estimation-of-distribution algorithms Linkage learning Optimal Mixing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：