The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Nikolaus Hansen - One of the best experts on this subject based on the ideXlab platform.
-
quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions
Theoretical Computer Science, 2020Co-Authors: Youhei Akimoto, Anne Auger, Nikolaus HansenAbstract:Quality gain is the expected relative improvement of the function value in a single step of a search algorithm. Quality gain analysis reveals the dependencies of the quality gain on the parameters of a search algorithm, based on which one can derive the optimal values for the parameters. In this paper, we investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive a bound for the quality gain and two limit expressions of the quality gain. From the limit expressions, we derive the optimal recombination weights and the optimal step-size, and find that the optimal recombination weights are independent of the Hessian of the objective function. Moreover, the dependencies of the optimal parameters on the dimension and the population size are revealed. Differently from previous works where the population size is implicitly assumed to be smaller than the dimension, our results cover the population size proportional to or greater than the dimension. Simulation results show the optimal parameters derived in the limit approximates the optimal values in non-asymptotic scenarios.
-
quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions
Foundations of Genetic Algorithms, 2017Co-Authors: Youhei Akimoto, Anne Auger, Nikolaus HansenAbstract:We investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive the asymptotic quality gain in the limit of the dimension to infinity, and derive the optimal recombination weights and the optimal step-size. This work is an extension of previous works where the asymptotic quality gain of evolution strategies with weighted recombination was derived on the infinite dimensional sphere function. Moreover, for a finite dimensional search space, we derive rigorous bounds for the quality gain on a general quadratic function. They reveal the dependency of the quality gain both in the eigenvalue distribution of the Hessian matrix and on the recombination weights. Taking the search space dimension to infinity, it turns out that the optimal recombination weights are independent of the Hessian matrix, i.e., the recombination weights optimal for the sphere function are optimal for convex quadratic functions.
-
quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions
arXiv: Optimization and Control, 2016Co-Authors: Youhei Akimoto, Anne Auger, Nikolaus HansenAbstract:Quality gain is the expected relative improvement of the function value in a single step of a search algorithm. Quality gain analysis reveals the dependencies of the quality gain on the parameters of a search algorithm, based on which one can derive the optimal values for the parameters. In this paper, we investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive a bound for the quality gain and two limit expressions of the quality gain. From the limit expressions, we derive the optimal recombination weights and the optimal step-size, and find that the optimal recombination weights are independent of the Hessian of the objective function. Moreover, the dependencies of the optimal parameters on the dimension and the population size are revealed. Differently from previous works where the population size is implicitly assumed to be smaller than the dimension, our results cover the population size proportional to or greater than the dimension. Numerical simulation shows that the asymptotically optimal step-size well approximates the empirically optimal step-size for a finite dimensional convex quadratic function.
-
On the Impact of a Small Initial Population Size in the IPOP Active CMA-ES with Mirrored Mutations on the Noiseless BBOB Testbed
2012Co-Authors: Dimo Brockhoff, Anne Auger, Nikolaus HansenAbstract:Active Covariance Matrix Adaptation and Mirrored Mutations have been independently proposed as improved variants of the well-known optimization algorithm Covariance Matrix Adaptation evolution strategy (CMA-ES) for numerical optimization. This paper investigates the impact of the algorithm's population size when both active covariance matrix adaptation and mirrored mutation are used in the CMA-ES. To this end, we compare the CMA-ES with standard population size $\lambda$, i.e., $\lambda = 4 + \lfloor 3\log(D) \rfloor$ with a version with half this population size where $D$ is the problem dimension.
-
local meta models for optimization using evolution strategies
Parallel Problem Solving from Nature, 2006Co-Authors: Stefan Kern, Nikolaus Hansen, Petros KoumoutsakosAbstract:We employ local meta-models to enhance the efficiency of evolution strategies in the optimization of computationally expensive problems. The method involves the combination of second order local regression meta-models with the Covariance Matrix Adaptation evolution strategy. Experiments on benchmark problems demonstrate that the proposed meta-models have the potential to reliably account for the ranking of the offspring population resulting in significant computational savings. The results show that the use of local meta-models significantly increases the efficiency of already competitive evolution strategies.
Anne Auger - One of the best experts on this subject based on the ideXlab platform.
-
quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions
Theoretical Computer Science, 2020Co-Authors: Youhei Akimoto, Anne Auger, Nikolaus HansenAbstract:Quality gain is the expected relative improvement of the function value in a single step of a search algorithm. Quality gain analysis reveals the dependencies of the quality gain on the parameters of a search algorithm, based on which one can derive the optimal values for the parameters. In this paper, we investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive a bound for the quality gain and two limit expressions of the quality gain. From the limit expressions, we derive the optimal recombination weights and the optimal step-size, and find that the optimal recombination weights are independent of the Hessian of the objective function. Moreover, the dependencies of the optimal parameters on the dimension and the population size are revealed. Differently from previous works where the population size is implicitly assumed to be smaller than the dimension, our results cover the population size proportional to or greater than the dimension. Simulation results show the optimal parameters derived in the limit approximates the optimal values in non-asymptotic scenarios.
-
quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions
Foundations of Genetic Algorithms, 2017Co-Authors: Youhei Akimoto, Anne Auger, Nikolaus HansenAbstract:We investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive the asymptotic quality gain in the limit of the dimension to infinity, and derive the optimal recombination weights and the optimal step-size. This work is an extension of previous works where the asymptotic quality gain of evolution strategies with weighted recombination was derived on the infinite dimensional sphere function. Moreover, for a finite dimensional search space, we derive rigorous bounds for the quality gain on a general quadratic function. They reveal the dependency of the quality gain both in the eigenvalue distribution of the Hessian matrix and on the recombination weights. Taking the search space dimension to infinity, it turns out that the optimal recombination weights are independent of the Hessian matrix, i.e., the recombination weights optimal for the sphere function are optimal for convex quadratic functions.
-
quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions
arXiv: Optimization and Control, 2016Co-Authors: Youhei Akimoto, Anne Auger, Nikolaus HansenAbstract:Quality gain is the expected relative improvement of the function value in a single step of a search algorithm. Quality gain analysis reveals the dependencies of the quality gain on the parameters of a search algorithm, based on which one can derive the optimal values for the parameters. In this paper, we investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive a bound for the quality gain and two limit expressions of the quality gain. From the limit expressions, we derive the optimal recombination weights and the optimal step-size, and find that the optimal recombination weights are independent of the Hessian of the objective function. Moreover, the dependencies of the optimal parameters on the dimension and the population size are revealed. Differently from previous works where the population size is implicitly assumed to be smaller than the dimension, our results cover the population size proportional to or greater than the dimension. Numerical simulation shows that the asymptotically optimal step-size well approximates the empirically optimal step-size for a finite dimensional convex quadratic function.
-
On the Impact of a Small Initial Population Size in the IPOP Active CMA-ES with Mirrored Mutations on the Noiseless BBOB Testbed
2012Co-Authors: Dimo Brockhoff, Anne Auger, Nikolaus HansenAbstract:Active Covariance Matrix Adaptation and Mirrored Mutations have been independently proposed as improved variants of the well-known optimization algorithm Covariance Matrix Adaptation evolution strategy (CMA-ES) for numerical optimization. This paper investigates the impact of the algorithm's population size when both active covariance matrix adaptation and mirrored mutation are used in the CMA-ES. To this end, we compare the CMA-ES with standard population size $\lambda$, i.e., $\lambda = 4 + \lfloor 3\log(D) \rfloor$ with a version with half this population size where $D$ is the problem dimension.
-
well placement optimization with the covariance matrix adaptation evolution strategy and meta models
Computational Geosciences, 2012Co-Authors: Zyed Bouzarkouna, Didier Yu Ding, Anne AugerAbstract:The amount of hydrocarbon recovered can be considerably increased by finding optimal placement of non-conventional wells. For that purpose, the use of optimization algorithms, where the objective function is evaluated using a reservoir simulator, is needed. Furthermore, for complex reservoir geologies with high heterogeneities, the optimization problem requires algorithms able to cope with the non-regularity of the objective function. In this paper, we propose an optimization methodology for determining optimal well locations and trajectories based on the covariance matrix adaptation evolution strategy (CMA-ES) which is recognized as one of the most powerful derivative-free optimizers for continuous optimization. In addition, to improve the optimization procedure, two new techniques are proposed: (a) adaptive penalization with rejection in order to handle well placement constraints and (b) incorporation of a meta-model, based on locally weighted regression, into CMA-ES, using an approximate stochastic ranking procedure, in order to reduce the number of reservoir simulations required to evaluate the objective function. The approach is applied to the PUNQ-S3 case and compared with a genetic algorithm (GA) incorporating the Genocop III technique for handling constraints. To allow a fair comparison, both algorithms are used without parameter tuning on the problem, and standard settings are used for the GA and default settings for CMA-ES. It is shown that our new approach outperforms the genetic algorithm: It leads in general to both a higher net present value and a significant reduction in the number of reservoir simulations needed to reach a good well configuration. Moreover, coupling CMA-ES with a meta-model leads to further improvement, which was around 20% for the synthetic case in this study.
David Corne - One of the best experts on this subject based on the ideXlab platform.
-
m paes a memetic algorithm for multiobjective optimization
Congress on Evolutionary Computation, 2000Co-Authors: Joshua Knowles, David CorneAbstract:A memetic algorithm for tackling multiobjective optimization problems is presented. The algorithm employs the proven local search strategy used in the Pareto archived evolution strategy (PAES) and combines it with the use of a population and recombination. Verification of the new M-PAES (memetic PAES) algorithm is carried out by testing it on a set of multiobjective 0/1 knapsack problems. On each problem instance, a comparison is made between the new memetic algorithm, the (1+1)-PAES local searcher, and the strength Pareto evolutionary algorithm (SPEA) of E. Zitzler and L. Thiele (1998, 1999).
-
approximating the nondominated front using the pareto archived evolution strategy
Evolutionary Computation, 2000Co-Authors: Joshua Knowles, David CorneAbstract:We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived evolution strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + λ) and (μ | λ) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.
-
the pareto archived evolution strategy a new baseline algorithm for pareto multiobjective optimisation
Congress on Evolutionary Computation, 1999Co-Authors: Joshua Knowles, David CorneAbstract:Most popular evolutionary algorithms for multiobjective optimisation maintain a population of solutions from which individuals are selected for reproduction. In this paper, we introduce a simpler evolution scheme for multiobjective problems, called the Pareto archived evolution strategy (PAES). We argue that PAES may represent the simplest possible non-trivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm is identified as being a (1+1) evolution strategy, using local search from a population of one but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. PAES is intended as a good baseline approach, against which more involved methods may be compared, and may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. The performance of the new algorithm is compared with that of a MOEA based on the niched Pareto GA on a real world application from the telecommunications field. In addition, we include results from experiments carried out on a suite of four test functions, to demonstrate the algorithm's general capability.
Hansgeorg Beyer - One of the best experts on this subject based on the ideXlab platform.
-
a covariance matrix self adaptation evolution strategy for optimization under linear constraints
IEEE Transactions on Evolutionary Computation, 2019Co-Authors: Patrick Spettel, Hansgeorg Beyer, Michael HellwigAbstract:This paper addresses the development of a covariance matrix self-adaptation evolution strategy (CMSA-ES) for solving optimization problems with linear constraints. The proposed algorithm is referred to as linear constraint CMSA-ES (lcCMSA-ES). It uses a specially built mutation operator together with repair by projection to satisfy the constraints. The lcCMSA-ES evolves itself on a linear manifold defined by the constraints. The objective function is only evaluated at feasible search points (interior point method). This is a property often required in application domains, such as simulation optimization and finite element methods. The algorithm is tested on a variety of different test problems revealing considerable results.
-
a matrix adaptation evolution strategy for constrained real parameter optimization
Congress on Evolutionary Computation, 2018Co-Authors: Michael Hellwig, Hansgeorg BeyerAbstract:By combination of successful constraint handling techniques known within the context of Differential evolution with the recently suggested Matrix Adaptation evolution strategy (MA-ES), a new evolution strategy for constrained optimization is presented. The novel MA - ES variant is applied to the benchmark problems specified for the CEC 2018 competition on constrained single objective real-parameter optimization. The algorithm is able to find feasible solutions on more than 80 % of the benchmark problems with high accuracy.
-
simplify your covariance matrix adaptation evolution strategy
IEEE Transactions on Evolutionary Computation, 2017Co-Authors: Hansgeorg Beyer, Bernhard SendhoffAbstract:The standard covariance matrix adaptation evolution strategy (CMA-ES) comprises two evolution paths, one for the learning of the mutation strength and one for the rank-1 update of the covariance matrix. In this paper, it is shown that one can approximately transform this algorithm in such a manner that one of the evolution paths and the covariance matrix itself disappear. That is, the covariance update and the covariance matrix square root operations are no longer needed in this novel so-called matrix adaptation (MA) ES. The MA-ES performs nearly as well as the original CMA-ES. This is shown by empirical investigations considering the evolution dynamics and the empirical expected runtime on a set of standard test functions. Furthermore, it is shown that the MA-ES can be used as a search engine in a bi-population (BiPop) ES. The resulting BiPop-MA-ES is benchmarked using the BBOB comparing continuous optimizers (COCO) framework and compared with the performance of the CMA-ES-v3.61 production code. It is shown that this new BiPop-MA-ES—while algorithmically simpler—performs nearly equally well as the CMA-ES-v3.61 code.
-
evolution under strong noise a self adaptive evolution strategy can reach the lower performance bound the pccmsa es
Parallel Problem Solving from Nature, 2016Co-Authors: Michael Hellwig, Hansgeorg BeyerAbstract:According to a theorem by Astete-Morales, Cauwet, and Teytaud, “simple evolution Strategies (ES)” that optimize quadratic functions disturbed by additive Gaussian noise of constant variance can only reach a simple regret log-log convergence slope \(\ge -1/2\) (lower bound). In this paper a population size controlled ES is presented that is able to perform better than the \(-1/2\) limit. It is shown experimentally that the pcCMSA-ES is able to reach a slope of \(-1\) being the theoretical lower bound of all comparison-based direct search algorithms.
-
covariance matrix adaptation revisited the cmsa evolution strategy
Parallel Problem Solving from Nature, 2008Co-Authors: Hansgeorg Beyer, Bernhard SendhoffAbstract:The covariance matrix adaptation evolution strategy (CMA-ES) rates among the most successful evolutionary algorithms for continuous parameter optimization. Nevertheless, it is plagued with some drawbacks like the complexity of the adaptation process and the reliance on a number of sophisticatedly constructed strategy parameter formulae for which no or little theoretical substantiation is available. Furthermore, the CMA-ES does not work well for large population sizes. In this paper, we propose an alternative --- simpler --- adaptation step of the covariance matrix which is closer to the "traditional" mutative self-adaptation. We compare the newly proposed algorithm, which we term the CMSA-ES, with the CMA-ES on a number of different test functions and are able to demonstrate its superiority in particular for large population sizes.
Joshua Knowles - One of the best experts on this subject based on the ideXlab platform.
-
m paes a memetic algorithm for multiobjective optimization
Congress on Evolutionary Computation, 2000Co-Authors: Joshua Knowles, David CorneAbstract:A memetic algorithm for tackling multiobjective optimization problems is presented. The algorithm employs the proven local search strategy used in the Pareto archived evolution strategy (PAES) and combines it with the use of a population and recombination. Verification of the new M-PAES (memetic PAES) algorithm is carried out by testing it on a set of multiobjective 0/1 knapsack problems. On each problem instance, a comparison is made between the new memetic algorithm, the (1+1)-PAES local searcher, and the strength Pareto evolutionary algorithm (SPEA) of E. Zitzler and L. Thiele (1998, 1999).
-
approximating the nondominated front using the pareto archived evolution strategy
Evolutionary Computation, 2000Co-Authors: Joshua Knowles, David CorneAbstract:We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived evolution strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + λ) and (μ | λ) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.
-
the pareto archived evolution strategy a new baseline algorithm for pareto multiobjective optimisation
Congress on Evolutionary Computation, 1999Co-Authors: Joshua Knowles, David CorneAbstract:Most popular evolutionary algorithms for multiobjective optimisation maintain a population of solutions from which individuals are selected for reproduction. In this paper, we introduce a simpler evolution scheme for multiobjective problems, called the Pareto archived evolution strategy (PAES). We argue that PAES may represent the simplest possible non-trivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm is identified as being a (1+1) evolution strategy, using local search from a population of one but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. PAES is intended as a good baseline approach, against which more involved methods may be compared, and may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. The performance of the new algorithm is compared with that of a MOEA based on the niched Pareto GA on a real world application from the telecommunications field. In addition, we include results from experiments carried out on a suite of four test functions, to demonstrate the algorithm's general capability.