In their recent work, Lehre and Nguyen (2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem....
详细信息
In their recent work, Lehre and Nguyen (2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by the choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most lambda(n/2+2e ln n) fitness evaluations. Since an offspring population size lambda of order nlogn can prevent genetic drift, the UMDA can solve the DLB problem with O(n(2) log n) fitness evaluations. In contrast, for classic evolutionary algorithms no better runtime guarantee than O(n(3)) is known (which we prove to be tight for the (1+1) EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than many classic evolutionary algorithms;such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) pro...
详细信息
ISBN:
(数字)9783030436803
ISBN:
(纸本)9783030436797;9783030436803
In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most lambda(n(2) +2e ln n) fitness evaluations. Since an offspring population size lambda of order n log n can prevent genetic drift, the UMDA can solve the DLB problem with O(n(2) log n) fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than O(n(3)) is known, so our result rather suggests that the UMDA can cope well with deception and epistatis. Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.
We perform a rigorous runtime analysis for the univariate marginal distribution algorithm on the LEADINGONES function, a wellknown benchmark function in the theory community of evolutionary computation with a high cor...
详细信息
ISBN:
(纸本)9781450361118
We perform a rigorous runtime analysis for the univariate marginal distribution algorithm on the LEADINGONES function, a wellknown benchmark function in the theory community of evolutionary computation with a high correlation between decision variables. For a problem instance of size n, the currently best known upper bound on the expected runtime is O (n lambda log lambda + n(2)) (Dang and Lehre, GECCO 2015), while a lower bound necessary to understand how the algorithm copes with variable dependencies is still missing. Motivated by this, we show that the algorithm requires a e(Omega(mu)) runtime with high probability and in expectation if the selective pressure is low;otherwise, we obtain a lower bound of Omega/(n lambda/log(lambda-mu) on the expected runtime. Furthermore, we for the first time consider the algorithm on the function under a prior noise model and obtain an O (n(2)) expected runtime for the optimal parameter settings. In the end, our theoretical results are accompanied by empirical findings, not only matching with rigorous analyses but also providing new insights into the behaviour of the algorithm.
We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the univariate marginal distribution algorithm (UMDA) in the presence of epistasis and deception. We show t...
详细信息
ISBN:
(纸本)9781450362542
We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the univariate marginal distribution algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary algorithms (EAs) outperform the UMDA unless the selective pressure mu/lambda is extremely high, where mu and lambda are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of mu = Q (log n) has an expected runtime of e(Omega(mu)) on the DLB problem assuming any selective pressure mu/lambda >= 14/1000, as opposed to the expected runtime of O (n lambda log lambda + n(3)) for the non-elitist (mu, lambda) EA with mu/lambda <= 1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.
In this paper, a univariate marginal distribution algorithm in continuous domain (UMDA (C) ) based on extreme elitism (EEUMDA (C) ) is proposed for solving the inverse displacement problem (IDP) of robotic manipulator...
详细信息
In this paper, a univariate marginal distribution algorithm in continuous domain (UMDA (C) ) based on extreme elitism (EEUMDA (C) ) is proposed for solving the inverse displacement problem (IDP) of robotic manipulators. This algorithm highlights the effect of a few top best solutions to form a primary evolution direction and obtains a fast convergence rate. Then it is implemented to determine the IDP of a 4-degree-of-freedom (DOF) Barrett WAM robotic arm. After that, the algorithm is combined with differential evolution (EEUMDA (C) -DE) to solve the IDP of a 7-DOF Barrett WAM robotic arm. In addition, three other heuristic optimization algorithms (enhanced leader particle swarm optimization, intersect mutation differential evolution, and evolution strategies) are applied to find the IDP solution of the 7-DOF arm and their performance is compared with that of EEUMDA (C) -DE.
Detecting diseases associated SNPs is the central goal of genetics and molecular biology. However, high throughput techniques often provide long lists of disease SNPs candidates, and the identification of disease SNPs...
详细信息
ISBN:
(纸本)9781538630136
Detecting diseases associated SNPs is the central goal of genetics and molecular biology. However, high throughput techniques often provide long lists of disease SNPs candidates, and the identification of disease SNPs among the candidates set remains timeconsuming and expensive. In addition, contrasting to the number of SNPs involved, the available datasets (samples) generally have fairly small sample size and the datasets used in these studies are often imbalanced (the number of cases and controls are not equal). Therefore, it is necessary to develop a robust tool to identify the disease associated SNPs. In this paper, we proposed a modified univariate marginal distribution algorithm (MUMDA) taking into account the imbalanced ratios of case/control for selecting the associated SNPs. In addition, the sparse vector encoding method was used in this paper. We illustrated the effectiveness of our algorithm using Crohn's disease (CD) dataset which includes 144 cases and 243 controls (each one has 103 SNPs). Our observations suggested that the proposed method could capture important features of the genetic architecture of CD and our algorithm outperformed other current methods.
This paper presents a new approach for dynamic economic dispatch (DED) problem in power system by using a hybrid univariate marginal distribution algorithm (HUMDA). The DED problem with valve-point effects and ramp ra...
详细信息
This paper presents a new approach for dynamic economic dispatch (DED) problem in power system by using a hybrid univariate marginal distribution algorithm (HUMDA). The DED problem with valve-point effects and ramp rate limits is a nonliner constrained optimization problem with non-convex and non-smooth characteristics. In the proposed method, a two-stage adaptive mechanism is devised to control parameters of the univariate marginal distribution algorithm in continuous domains (UMDAc) dynamically and lead the algorithm with better search efficiency;a chaotic local search operator is integrated with UMDAc to effectively avoid premature convergence. Moreover, a constraint handle according to the two-stage adaptive mechanism is proposed, and the results show that the strategy can handle constraints effectively. Finally, the efficiency of the proposed method is validated on two test systems consisting of 5, 10 and 30 thermal units. The results show the superiority of the proposed method while it is compared with other works in the area. Copyright (c) 2013 John Wiley & Sons, Ltd.
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a vital unifying model for combinatorial optimization problems, and (meta-)heuristic approaches are commonly used to solve them due to their NP-hard na...
详细信息
ISBN:
(纸本)9798400701207
Quadratic Unconstrained Binary Optimization (QUBO) has emerged as a vital unifying model for combinatorial optimization problems, and (meta-)heuristic approaches are commonly used to solve them due to their NP-hard nature. Scatter Search (SS), a populationbased metaheuristic framework, is one such method that has shown promising results for QUBO problems. Generating new solutions from more promising ones is a crucial operation in SS. Path Relinking (PR) based SS has been previously used to solve challenging QUBO problems with high-quality solutions. This paper introduces two new variants of the SS algorithm. The first is the (Multi) Uniform Crossover (MUC) based SS while the second is the univariate marginal distribution algorithm (UMDA) based SS. MUC and UMDA are well-known operators in Genetic algorithms and Estimation of distributionalgorithms respectively. When compared to the existing PR based SS, this work shows that more promising results can be achieved when the newly proposed MUC and UMDA-based SS are applied to QUBO formulations of the Quadratic Knapsack Problem (QKP) instances.
With apparently all research on estimation-of-distributionalgorithms (EDAs) concentrated on pseudo-Boolean optimization and permutation problems, we undertake the first steps towards using EDAs for problems in which ...
详细信息
ISBN:
(纸本)9798400701191
With apparently all research on estimation-of-distributionalgorithms (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.
The majority of research on estimation -of -distributionalgorithms (EDAs) concentrates on pseudoBoolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables c...
详细信息
The majority of research on estimation -of -distributionalgorithms (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.
暂无评论