Comparing the Uni-Modal Scaling Performance of Global and Local Selection in a Mutation-Only Differential Evolution Algorithm

Published 22 September 2006

Kenneth V. Price, Jani Rönkkönen

DOI10.1109/cec.2006.1688557

Citations22

TL;DR

Abstract

This paper benchmarks the scaling performance of two mutation-only Differential Evolution algorithms with the goal of discovering why large population sizes are often needed to support optimizations with small scale factors. The algorithms differ only in how the base vector is selected. We determined the computational efficiency of both base vector selection methods with a test bed consisting of three convex and one non-convex uni-modal functions. Our experiments revealed the best control parameter combinations and their dependence on the objective function's dimension. In addition, results demonstrate the extent to which stretching, rotating and making the objective function landscape non-convex impact the performance of the differential mutation operator.

Keywords

Computer Science

Journal of Global OptimizationDifferential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces

28,706 Citations1997Rainer Storn, Kenneth V. Price

It is demonstrated that the new heuristic approach for minimizing possibly nonlinear and non-differentiable continuous spacefunctions Converges faster and with more certainty than manyother acclaimed global optimization methods.

Differential Evolution - A simple and efficient adaptive scheme for global optimization over continuous spaces

3,354 Citations2004Kenneth V. Price

A new heuristic approach for minimizing possibly nonlinear and non differentiable continuous space functions is presented and it will be demonstrated that the new method converges faster and with more certainty than Adaptive Simulated Annealing as well as the Annealed Nelder&Mead approach.

Foundations of genetic algorithmsA Comparative Analysis of Selection Schemes Used in Genetic Algorithms

2,400 Citations1991David E. Goldberg, Kalyanmoy Deb

A number of selection schemes commonly used in modern genetic algorithms are compared on the basis of solutions to deterministic difference or differential equations, verified through computer simulations to provide convenient approximate or exact solutions and useful convergence time and growth ratio estimates.

Evolutionary ComputationAn Overview of Evolutionary Algorithms for Parameter Optimization

2,110 Citations1993Thomas Bäck, Hans–Paul Schwefel

Three main streams of evolutionary algorithms (EAs), probabilistic optimization algorithms based on the model of natural evolution, are compared in this article: evolution strategies (ESs), evolutionary programming (EP), and genetic algorithms (GAs).

Statistical ScienceOptimal scaling for various Metropolis-Hastings algorithms

1,090 Citations2001Gareth O. Roberts, Jeffrey S. Rosenthal

Statistics and ComputingA Markov Chain Monte Carlo version of the genetic algorithm Differential Evolution: easy Bayesian computing for real parameter spaces

946 Citations2006Cajo J. F. ter Braak

The essential ideas of DE and MCMC are integrated, resulting in Differential Evolution Markov Chain (DE-MC), a population MCMC algorithm, in which multiple chains are run in parallel, showing simplicity, speed of calculation and convergence, even for nearly collinear parameters and multimodal densities.

Evolutionary ComputationA Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization

612 Citations2002Kalyanmoy Deb, Ashish Anand +1 more

The proposed generic parent-centric recombination operator (PCX) and a steady-state, elite-preserving, scalable, and computationally fast population-alteration model (G3 model) are proposed and found to consistently and reliably perform better than all other methods used in the study.

BiosystemsRe-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms

481 Citations1996Ralf Salomon

The theoretical analysis presented in this paper shows that most of the widely-used test functions have n independent parameters and that, when optimizing such functions, many GAs scale with an O(n ln n) complexity.