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

A mathematical analysis of EDAs with distance-based exponential models

MEMETIC COMPUTING 2022年第3期14卷 305-334页

作者： Unanue, Imanol Merino, Maria Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Lardizabal Ibilbidea 1 Gipuzkoa 20018 Spain Univ Basque Country UPV EHU Dept Math Barrio Sarriena S-N Leioa 48940 Spain Basque Ctr Appl Math BCAM Alameda Mazarredo 14 Bilbao 48009 Bizkaia Spain

estimation of distribution algorithms have been successfully used to solve permutation-based Combinatorial Optimization Problems. In this case, the algorithms use probabilistic models specifically designed for codifying probability distributions over permutation spaces. One class of these probability models are distance-based exponential models, and one example of this class is the Mallows model. In spite of its practical success, the theoretical analysis of estimation of distribution algorithms for permutation-based Combinatorial Optimization Problems has not been developed as extensively as it has been for binary problems. With this motivation, this paper presents a first mathematical analysis of the convergence behavior of estimation of distribution algorithms based on Mallows models. The model removes the randomness of the algorithm in order to associate a dynamical system to it. Several scenarios of increasing complexity with different fitness functions and initial probability distributions are analyzed. The obtained results show: a) the strong dependence of the final results on the initial population, and b) the possibility to converge to non-degenerate distributions even in very simple scenarios, which has not been reported before in the literature.

关键词： estimation of distribution algorithms Permutation-based Combinatorial Optimization Problems Mathematical Modeling Dynamical Systems Mallows Model

来源：评论

学校读者我要写书评

暂无评论

Sporadic model building for efficiency enhancement of the hierarchical BOA

引用

GENETIC PROGRAMMING AND EVOLVABLE MACHINES 2008年第1期9卷 53-84页

作者： Pelikan, Martin Sastry, Kumara Goldberg, David E. Univ Missouri Dept Math & Comp Sci Missouri Estimat Distribut Algorithm Lab St Louis MO 63121 USA Univ Illinois Dept Ind & Enterprise Syst Engn Illinois Genet Algorithm Lab Urbana IL 61801 USA

Efficiency enhancement techniques - such as parallelization and hybridization - are among the most important ingredients of practical applications of genetic and evolutionary algorithms and that is why this research area represents an important niche of evolutionary computation. This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other estimation of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure of the probabilistic model is updated once in every few iterations (generations), whereas in the remaining iterations, only model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization problems, sporadic model building leads to a significant model-building speedup, which decreases the asymptotic time complexity of model building in hBOA by a factor of Theta(n(0.26)) to Theta(n(0.5)) where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence;nonetheless, if model building is the bottleneck, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building. The paper also presents a dimensional model to provide a heuristic for scaling the structure-building period, which is the only parameter of the proposed sporadic model-building approach. The paper then tests the proposed method and the rule for setting the structure-building period on the problem of finding ground states of 2D and 3D Ising spin glasses.

关键词： Bayesian optimization algorithm hierarchical BOA estimation of distribution algorithms efficiency enhancement sporadic model building

来源：评论

学校读者我要写书评

暂无评论

Chaotic synchronization using PID control combined with population based incremental learning algorithm

引用

EXPERT SYSTEMS WITH APPLICATIONS 2010年第7期37卷 5347-5352页

作者： Coelho, Leandro dos Santos Grebogi, Rafael Bartnik Pontif Catholic Univ Parana PUCPR Ind & Syst Engn Grad Program LAS PPGEPS BR-80215901 Curitiba Parana Brazil

Evolutionary algorithms (EAs) refer to a broad class of optimization algorithms, which take some inspiration from evolutionary systems in the natural world. In recent years, a new class of EAs called estimation of distribution algorithms (EDAs) has emerged based on probabilistic modeling of the search space. Instances of EDAs include population based incremental learning (PBIL) algorithm. The PBIL algorithm is an easy to understand heuristic optimization technique that is inspired by the genetic algorithm and the competitive learning paradigm. PBIL includes many of the features from the genetic algorithm such as binary string representation, the notion of individuals, fitness measures and mutations. Contrary to the genetic algorithm it does not maintain a population of individuals but instead PBIL contains a probability vector. At each generation a new population of individuals is sampled according to the probabilities specified in the probability vector. The population is evaluated and the probability vector is updated by dragging it towards the best individual in the population. In recent years, the investigation of synchronization of chaotic systems has attracted much attention of researchers. Chaos synchronization has been applied in many fields such as secure communication, chemical, engineering, and biological systems, among others. This paper presents the synchronization of two identical discrete chaotic systems subject the different initial conditions by designing a proportional-integral-derivative (PID) controller. In addition, the tuning of the PID controller based on a modified PBIL algorithm using similarity analysis is also investigated in this paper. Simulation results show the good performance of the modified PBIL algorithm for synchronization of chaotic systems. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Evolutionary algorithms Optimization Chaotic synchronization estimation of distribution algorithms Control system

来源：评论

学校读者我要写书评

暂无评论

Improved sampling using loopy belief propagation for probabilistic model building genetic programming

引用

SWARM AND EVOLUTIONARY COMPUTATION 2015年 23卷 1-10页

作者： Sato, Hiroyuki Hasegawa, Yoshihiko Bollegala, Danushka Iba, Hitoshi Univ Tokyo Grad Sch Engn Tokyo 1138654 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138654 Japan Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

In recent years, probabilistic model building genetic programming (PMBGP) for program optimization has attracted considerable interest. PMBGPs generally use probabilistic logic sampling (PLS) to generate new individuals. However, the generation of the most probable solutions (MPSs), i.e., solutions with the highest probability, is not guaranteed. In the present paper, we introduce loopy belief propagation (LBP) for PMBGPs to generate MPSs during the sampling process. We selected program optimization with linkage estimation (POLE) as the foundation of our approach and we refer to our proposed method as POLE-BP. We apply POLE-BP and existing methods to three benchmark problems to investigate the effectiveness of LBP in the context of PMBGPs, and we describe detailed examinations of the behaviors of LBP. We find that POLE-BP shows better search performance with some problems because LBP boosts the generation of building blocks. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Genetic programming estimation of distribution algorithms Loopy belief propagation Probabilistic model building GP

来源：评论

学校读者我要写书评

暂无评论

A hybrid genetic algorithm for the repetition free longest common subsequence problem

引用

OPERATIONS RESEARCH LETTERS 2013年第6期41卷 644-649页

作者： Castelli, Mauro Beretta, Stefano Vanneschi, Leonardo Univ Nova Lisboa ISEGI P-1070312 Lisbon Portugal Univ Milano Bicocca DISCo I-20126 Milan Italy CNR Inst Biomed Technol I-20090 Segrate Italy

Computing the longest common subsequence of two sequences is one of the most studied algorithmic problems. In this work we focus on a particular variant of the problem, called repetition free longest common subsequence (RF-LCS), which has been proved to be NP-hard. We propose a hybrid genetic algorithm, which combines standard genetic algorithms and estimation of distribution algorithms, to solve this problem. An experimental comparison with some well-known approximation algorithms shows the suitability of the proposed technique. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Repetition free longest common subsequence Heuristics Genetic algorithms estimation of distribution algorithms

来源：评论

学校读者我要写书评

暂无评论

Initial approaches to the application of islands-based parallel EDAs in continuous domains

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第8期66卷 991-1001页

作者： delaOssa, Luis Gamez, Jose A. Puerta, Jose A. Univ Castilla La Mancha Dept Sistemas Informat Albacete 02071 Spain

estimation of distribution algorithms (EDAs) are a wide-ranging family of evolutionary algorithms whose common feature is the way they evolve by learning a probability distribution from the best individuals in a population and sampling it to generate the next one. Although they have been widely applied to solve combinatorial optimization problems, there are also extensions that work with continuous variables. In this paper [this paper is an extended version of delaOssa et al. Initial approaches to the application of islands-based parellel EDAs in continuous domains, in: Proceedings of the 34th International Conference on Parallel Processing Workshops (ICPP 2005 Workshops), Oslo, 2005, pp. 580-587] we focus on the solution of the latter by means of island models. Besides evaluating the performance of traditional island models when applied to EDAs, our main goal consists in achieving some insight about the behavior and benefits of the migration of probability models that this framework allow. (C) 2006 Elsevier Inc. All rights reserved.

关键词： parallel evolutionary algorithms estimation of distribution algorithms numerical optimization

来源：评论

学校读者我要写书评

暂无评论

Level-Based Analysis of the Univariate Marginal distribution Algorithm

引用

ALGORITHMICA 2019年第2期81卷 668-702页

作者： Duc-Cuong Dang Lehre, Per Kristian Phan Trung Hai Nguyen Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

estimation of distribution algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal distribution Algorithm (UMDA)-a simple population-based EDA assuming independence between decision variables-the optimisation time on the linear problem OneMaxwas until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound O(n lambda log lambda + n(2))on the LeadingOnes and BinVal problems for population sizes lambda > mu = Omega(log n), where mu and lambda are parameters of the algorithm. We also prove that the UMDA with population sizes mu is an element of O (root n) boolean AND Omega (log n) optimises OneMax in expected time O(lambda n), and for larger population sizes mu = Omega(root n log n), in expected time O (lambda root n) The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.

关键词： estimation of distribution algorithms Runtime analysis Level-based analysis Anti-concentration

来源：评论

学校读者我要写书评

暂无评论

Fitness Modeling With Markov Networks

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2013年第6期17卷 862-879页

作者： Brownlee, Alexander E. I. McCall, John A. W. Zhang, Qingfu Loughborough Univ Technol Sch Civil & Bldg Engn Loughborough LE11 3TU Leics England Robert Gordon Univ IDEAS Res Inst Aberdeen AB10 1FR Scotland Univ Essex Sch Comp Sci & Elect Engn Colchester CO4 3SQ Essex England

Fitness modeling has received growing interest from the evolutionary computation community in recent years. With a fitness model, one can improve evolutionary algorithm efficiency by directly sampling new solutions, developing hybrid guided evolutionary operators or using the model as a surrogate for an expensive fitness function. This paper addresses several issues on fitness modeling of discrete functions, particularly how modeling quality and efficiency can be improved. We define the Markov network fitness model in terms of Walsh functions. We explore the relationship between the Markov network fitness model and fitness in a number of discrete problems, showing how the parameters of the fitness model can identify qualitative features of the fitness function. We define the fitness prediction correlation, a metric to measure fitness modeling capability of local and global fitness models. We use this metric to investigate the effects of population size and selection on the tradeoff between model quality and complexity for the Markov network fitness model.

关键词： estimation of distribution algorithms graphical models Markov random fields

来源：评论

学校读者我要写书评

暂无评论

Univariate marginal distribution algorithm dynamics for a class of parametric functions with unitation constraints

引用

INFORMATION SCIENCES 2011年第11期181卷 2340-2355页

作者： Lozada-Chang, Li-Vang Santana, Roberto Univ Basque Country Intelligent Syst Grp Dept Comp Sci & Artificial Intelligence San Sebastian Spain Univ Politecn Madrid E-28660 Madrid Spain Univ Havana Fac Math & Computat Havana Cuba

In this paper, we introduce a mathematical model for analyzing the dynamics of the univariate marginal distribution algorithm (UMDA) for a class of parametric functions with isolated global optima. We prove a number of results that are used to model the evolution of UMDA probability distributions for this class of functions. We show that a theoretical analysis can assess the effect of the function parameters on the convergence and rate of convergence of UMDA. We also introduce for the first time a long string limit analysis of UMDA. Finally, we relate the results to ongoing research on the application of the estimation of distribution algorithms for problems with unitation constraints. (C) 2011 Elsevier Inc. All rights reserved.

关键词： estimation of distribution algorithms Univariate marginal distribution algorithm Convergence analysis Evolutionary algorithms Long string limit analysis

来源：评论

学校读者我要写书评

暂无评论

Evolutionary optimization with Markov random field prior

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2004年第6期8卷 567-579页

作者： Wang, X Wang, H Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

This paper discusses an evolutionary algorithm in which the constituent variables of a solution are modeled by a Markov random field (MRF). We maintain a population of potential solutions. at every generation and for each solution a fitness value is calculated. The evolution, however, is not achieved through genetic recombination. Instead, each variable in a solution will be updated by sampling from its probability distribution. According to the MRF prior, local exploitation is encoded in the conditional probabilities. For evolutionary exploration, we estimate the probabilities as fitness-weighted statistics. These two kinds of search are combined smoothly in our algorithm. We compare it with two representative algorithms [iterated conditional modes (ICM) and simulated annealing (SA)] on noisy and textured image segmentation. Remarkable performance is observed.

关键词： combinatorial optimization estimation of distribution algorithms evolutionary computation genetic algorithms (GAs) hybrid search algorithm image segmentation Markov random fields (MRF)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：