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

Scatter Search in software testing, comparison and collaboration with estimation of distribution algorithms

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2006年第2期169卷 392-412页

作者： Sagarna, R Lozano, JA Univ Basque Country Dept Comp Sci & Artificial Intelligence San Sebastian 20018 Guipuzcoa Spain

One of the main tasks software testing includes is the generation of the test cases to be used during the test. Due to its expensive cost, the automatization of this task has become one of the key issues in the area. The field of Evolutionary Testing deals with this problem by means of metaheuristic search techniques. An Evolutionary Testing based approach to the automatic generation of test inputs is presented. The approach developed involves different possibilities of the usage of two heuristic optimization methods, namely, Scatter Search and estimation of distribution algorithms. The possibilities comprise pure Scatter Search options and Scatter Search-estimation of distribution Algorithm collaborations. Several experiments were conducted in order to evaluate and compare the approaches presented with those in the literature. The analysis of the experimental results raises interesting conclusions, showing these alternatives as a promising option to tackle this problem. (c) 2004 Elsevier B.V. All rights reserved.

关键词： evolutionary computations software testing branch coverage Scatter Search estimation of distribution algorithms

来源：评论

学校读者我要写书评

暂无评论

Triangulation of Bayesian networks with recursive estimation of distribution algorithms

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2009年第3期50卷 472-484页

作者： Romero, Txomin Larranaga, Pedro Donostia Int Phys Center Guipuzcoa 20018 Spain Univ Basque Country Dept Comp Sci & Artificial Intelligence Bilbao Spain Univ Politecn Madrid Dept Inteligencia Artificial E-28040 Madrid Spain

Bayesian networks can be used as a model to make inferences in domains with intrinsic uncertainty, that is, to determine the probability distribution of a set of variables given the instantiation of another set. The inference is an NP-hard problem. There are several algorithms to make exact and approximate inference. One of the most popular, and that is also an exact method. is the evidence propagation algorithm of Lauritzen and Spiegelhalter [S.L. Lauritzen, D.J. Spiegelhalter, Local computations with probabilities on graphical structures and their application on expert systems, journal of the Royal Statistical Society B 50 (2) (1988) 157-224], improved later by Jensen et al. [F.V. Jensen, S.L. Lauritzen, K.G. Olesen, Bayesian updating in causal probabilistic networks by local computations, In Computational Statistics Quaterly 4 (1990) 269-282]. This algorithm needs an ordering of the variables in order to make the triangulation of the moral graph associated with the original Bayesian network structure. The effectiveness of the inference depends on the variable ordering. In this paper, we will use a new paradigm for evolutionary computation, the estimation of distribution algorithms (EDAs), to get the optimal ordering of the variables to obtain the most efficient triangulation. We will also present a new type of evolutionary algorithm, the recursive EDAs (REDAs). We will prove that REDAs improve the behaviour of EDAs in this particular problem, and that their results are competitive with other triangulation techniques. (C) 2008 Elsevier Inc. All rights reserved.

关键词： Bayesian networks estimation of distribution algorithms Triangulation Inference Junction tree

来源：评论

学校读者我要写书评

暂无评论

A review of message passing algorithms in estimation of distribution algorithms

引用

NATURAL COMPUTING 2016年第1期15卷 165-180页

作者： Santana, Roberto Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Intelligent Syst Grp Paseo Manuel Lardizabal 1 San Sebastian 20080 Spain

Message passing algorithms (MPAs) have been traditionally used as an inference method in probabilistic graphical models. Some MPA variants have recently been introduced in the field of estimation of distribution algorithms (EDAs) as a way to improve the efficiency of these algorithms. Multiple developments on MPAs point to an increasing potential of these methods for their application as part of hybrid EDAs. In this paper we review recent work on EDAs that apply MPAs and propose ways to further extend the useful synergies between MPAs and EDAs. Furthermore, we analyze some of the implications that MPA developments can have in their future application to EDAs and other evolutionary algorithms.

关键词： Message passing algorithms Propagation estimation of distribution algorithms Hybridization

来源：评论

学校读者我要写书评

暂无评论

Comprehensive characterization of the behaviors of estimation of distribution algorithms

引用

THEORETICAL COMPUTER SCIENCE 2015年 598卷 64-86页

作者： Echegoyen, Carlos Santana, Roberto Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Intelligent Syst Grp San Sebastian 20018 Spain

estimation of distribution algorithms (EDAs) are a successful example of how to use machine learning techniques for designing robust and efficient heuristic search algorithms. Understanding the relationship between EDAs and the space of optimization problems is a fundamental issue for the successful application of this type of algorithms. A step forward in this matter is to create a taxonomy of optimization problems according to the different behaviors that an EDA can exhibit. This paper substantially extends previous work in the proposal of a taxonomy of problems for univariate EDAs, mainly by generalizing those results to EDAs that are able to deal with multivariate dependences among the variables of the problem. Through the definition of an equivalence relation between functions, it is possible to partition the space of problems into equivalence classes in which the algorithm has the same behavior. We provide a sufficient and necessary condition to determine the equivalence between functions. This condition is based on a set of matrices which provides a novel encoding of the relationship between the function and the probabilistic model used by the algorithm. The description of the equivalent functions belonging to a class is studied in depth for EDAs whose probabilistic model is given by a chordal Markov network. Assuming this class of factorization, we unveil the intrinsic connection between the behaviors of EDAs and neighborhood systems defined over the search space. In addition, we carry out numerical simulations that effectively reveal the different behaviors of EDAs for the injective functions defined over the search space (0, 1}(3). Finally, we provide a novel approach to extend the analysis of equivalence classes to non-injective functions. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Heuristic optimization Machine learning estimation of distribution algorithms Factorizations Equivalence classes Neighborhood systems

来源：评论

学校读者我要写书评

暂无评论

Extending a class of continuous estimation of distribution algorithms to dynamic problems

引用

OPTIMIZATION LETTERS 2008年第3期2卷 433-443页

作者： Yuan, Bo Orlowska, Maria Sadiq, Shazia Tsinghua Univ Grad Sch Shenzhen Div Informat Shenzhen 518055 Peoples R China Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia

In this paper, a class of continuous estimation of distribution algorithms (EDAs) based on Gaussian models is analyzed to investigate their potential for solving dynamic optimization problems where the global optima may change dramatically during time. Experimental results on a number of dynamic problems show that the proposed strategy for dynamic optimization can significantly improve the performance of the original EDAs and the optimal solutions can be consistently located.

关键词： Evolutionary algorithms Global optimization estimation of distribution algorithms Dynamic optimization

来源：评论

学校读者我要写书评

暂无评论

Runtime Analyses of the Population-Based Univariate estimation of distribution algorithms on LeadingOnes

引用

ALGORITHMICA 2021年第10期83卷 3238-3280页

作者： Lehre, Per Kristian Nguyen, Phan Trung Hai Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England Univ Exeter Dept Comp Sci Exeter EX4 4QJ Devon England

We perform rigorous runtime analyses for the univariate marginal distribution algorithm (UMDA) and the population-based incremental learning (PBIL) Algorithm on LeadingOnes. For the UMDA, the currently known expected runtime on the function is O(n lambda log lambda + n(2)) under an offspring population size lambda = Omega(log n) and a parent population size mu <= lambda/(e(1 + delta)) for any constant delta > 0 (Dang and Lehre, GECCO 2015). There is no lower bound on the expected runtime under the same parameter settings. It also remains unknown whether the algorithm can still optimise the LeadingOnes function within a polynomial runtime when mu >= lambda/(e(1+delta)). In case of the PBIL, an expected runtime of O(n(2+c)) holds for some constant c is an element of(0,1) (Wu, Kolonko and Mohring, IEEE TEVC 2017). Despite being a generalisation of the UMDA, this upper bound is significantly asymptotically looser than the upper bound of O(n(2) of the UMDA for lambda=Omega(log n) boolean AND O. Furthermore, the required population size is very large, i.e., lambda=Omega(n(1+c)). Our contributions are then threefold: (1) we show that the UMDA with mu=Omega(log n) and lambda <= mu e(1-epsilon)/(1+delta) for any constants epsilon is an element of(0,1) and 0 < delta <= e(1-epsilon)-1 requires an expected runtime of e(Omega(mu)) on LEADINGONES, (2) an upper bound of O(n lambda log lambda + n(2)) is shown for the PBIL, which improves the current bound O(n(2+c)) by a significant factor of Theta(n(c)), and (3) we for the first time consider the two algorithms on the LeadingOnes function in a noisy environment and obtain an expected runtime of O(n(2)) for appropriate parameter settings. Our results emphasise that despite the independence assumption in the probabilistic models, the UMDA and the PBIL with fine-tuned parameter choices can still cope very well with variable interactions.

关键词： estimation of distribution algorithms Running time analysis Level-based analysis Noisy optimisation Theory of randomised search heuristics

来源：评论

学校读者我要写书评

暂无评论

Analysis of Computational Time of Simple estimation of distribution algorithms

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2010年第1期14卷 1-22页

作者： Chen, Tianshi Tang, Ke Chen, Guoliang Yao, Xin Univ Sci & Technol China Nat Inspired Computat & Applicat Lab Sch Comp Sci & Technol Hefei 230027 Anhui Peoples R China Univ Birmingham Ctr Excellence Res Computat Intelligence & Applic Sch Comp Sci Birmingham B15 2TT W Midlands England

estimation of distribution algorithms (EDAs) are widely used in stochastic optimization. Impressive experimental results have been reported in the literature. However, little work has been done on analyzing the computation time of EDAs in relation to the problem size. It is still unclear how well EDAs (with a finite population size larger than two) will scale up when the dimension of the optimization problem (problem size) goes up. This paper studies the computational time complexity of a simple EDA, i.e., the univariate marginal distribution algorithm (UMDA), in order to gain more insight into EDAs complexity. First, we discuss how to measure the computational time complexity of EDAs. A classification of problem hardness based on our discussions is then given. Second, we prove a theorem related to problem hardness and the probability conditions of EDAs. Third, we propose a novel approach to analyzing the computational time complexity of UMDA using discrete dynamic systems and Chernoff bounds. Following this approach, we are able to derive a number of results on the first hitting time of UMDA on a well-known unimodal pseudo-boolean function, i.e., the LeadingOnes problem, and another problem derived from LeadingOnes, named BVLeadingOnes. Although both problems are unimodal, our analysis shows that LeadingOnes is easy for the UMDA, while BVLeadingOnes is hard for the UMDA. Finally, in order to address the key issue of what problem characteristics make a problem hard for UMDA, we discuss in depth the idea of "margins" (or relaxation). We prove theoretically that the UMDA with margins can solve the BVLeadingOnes problem efficiently.

关键词： Computational time complexity estimation of distribution algorithms first hitting time heuristic optimization univariate marginal distribution algorithms

来源：评论

学校读者我要写书评

暂无评论

Side chain placement using estimation of distribution algorithms

引用

ARTIFICIAL INTELLIGENCE IN MEDICINE 2007年第1期39卷 49-63页

作者： Santana, Roberto Larranaga, Pedro Lozano, Jose A. Univ Basque Country Dept Comp Sci & Artificial Intelligence Donostia San Sebastian 20080 Spain

Objective: This paper presents an algorithm for the solution of the side chain placement problem. Methods and materials: The algorithm combines the application of the Goldstein elimination criterion with the univariate marginal distribution algorithm (UMDA), which stochastically searches the space of possible solutions. The suitability of the algorithm to address the problem is investigated using a set of 425 proteins. Results: For a number of difficult instances where inference algorithms do not converge, it has been shown that UMDA is able to find better structures. Conclusions: The results obtained show that the algorithm can achieve better structures than those obtained with other state-of-the-art methods like inference-based techniques. Additionally, a theoretical and empirical analysis of the computationat cost of the algorithm introduced has been presented. (C) 2006 Elsevier B.V. All rights reserved.

关键词： protein folding estimation of distribution algorithms protein structure prediction rotamers

来源：评论

学校读者我要写书评

暂无评论

Drift and scaling in estimation of distribution algorithms

引用

EVOLUTIONARY COMPUTATION 2005年第1期13卷 99-123页

作者： Shapiro, JL Univ Manchester Dept Comp Sci Manchester M13 9PL Lancs England

This paper considers a phenomenon in estimation of distribution algorithms (EDA) analogous to drift in population genetic dynamics. Finite population sampling in selection results in fluctuations which get reinforced when the probability model is updated. As a consequence, any probability model which can generate only a single set of values with probability 1 can be an attractive fixed point of the algorithm. To avoid this, parameters of the algorithm must scale with the system size in strongly problem-dependent ways, or the algorithm must be modified. This phenomenon is shown to hold for general EDAs as a consequence of the lack of ergodicity and irreducibility of the Markov chain on the state of probability models. It is illustrated in the case of UMDA, in which it is shown that the global optimum is only found if the population size is sufficiently large. For the needle-in-a haystack problem, the population size must scale as the square-root of the size of the search space. For the one-max problem, the population size must scale as the square-root of the problem size.

关键词： estimation of distribution algorithms probability building genetic algorithms Markov chain analysis convergence analysis needle-in-a-haystack problem counting-ones problem

来源：评论

学校读者我要写书评

暂无评论

The effectiveness of mutation operation in the case of estimation of distribution algorithms

引用

BIOSYSTEMS 2007年第2-3期87卷 243-251页

作者： Handa, Hisashi Okayama Univ Fac Engn Dept Informat Technol Okayama 7008530 Japan

The estimation of distribution algorithms are a class of evolutionary algorithms which adopt probabilistic models to reproduce individuals in the next generation, instead of conventional crossover and mutation operators. In this paper, mutation operators are incorporated into estimation of distribution algorithms in order to maintain the diversities in EDA populations. Two kinds of mutation operators are examined: a bitwise mutation operator and a mutation operator taking account into the probabilistic model. In experiments, we do not only compare the proposed methods with conventional EDAs on a few fitness functions but also analyze sampled probabilistic models by using KL-divergence. The experimental results shown in this paper elucidate that the mutation operator taking account into the probabilistic model improve the search ability of EDAs. (c) 2006 Elsevier Ireland Ltd. All rights reserved.

关键词： estimation of distribution algorithms mutation operation KL-divergence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：