Genetic Optimization Using Derivatives

By Jasjeet S. Sekhon, Walter R. Mebane Jr.. Political Analysis, 2011

653 citations recorded by the source corpus.

We describe a new computer program that combines evolutionary algorithm methods with a derivative-based, quasi-Newton method to solve difficult unconstrained optimization problems. The program, called GENOUD (GENetic Optimization Using Derivatives), effectively solves problems that are nonlinear or perhaps even discontinuous in the parameters of the function to be optimized. When a statistical model's estimating function (for example, a log-likelihood) is nonlinear in the model's parameters, the function to be optimized will usually not be globally concave and may contain irregularities such as saddlepoints or discontinuous jumps. Optimization methods that rely on derivatives of the objective function may be unable to find any optimum at all. Or multiple local optima may exist, so that there is no guarantee that a derivative-based method will converge to the global optimum. We discuss the theoretical basis for expecting GENOUD to have a high probability of finding global optima. We conduct Monte Carlo experiments using scalar Normal mixture densities to illustrate this capability. We also use a system of four simultaneous nonlinear equations that has many parameters and multiple local optima to compare the performance of GENOUD to that of the Gauss-Newton algorithm in SAS's PROC MODEL.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c23d2cf2235fc5831daaa374388c73be08f9d6a1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Using Indicator Species to Predict Species Richness of Multiple Taxonomic Groups (2005, methodology): “We implemented a genetic algorithm by using the R statistical programming software (R Development Core Team 2003; Sekhon & Mebane 1998) to search for Poisson models with low BIC values for each of the nine combinations of response and predictor variables.”
A Robust Method for Estimating Optimal Treatment Regimes (2012, methodology): “Accordingly, we used two approaches to maximization of these quantities: a grid search, as described in Web Appendix C, and the genetic algorithm discussed by Goldberg (1989) and implemented in the rgenoud package in R (Mebane and Sekhon, 2011).”
Do UN Interventions Cause Peace? Using Matching to Improve Causal Inference (2008, methodology): “neighbor matching was preformed with GenMatch (Sekhon forthcoming), which uses a genetic search algorithm to determine the weight each confounding factor should receive in order to obtain optimal balance (Sekhon 2006b, Sekhon and Mebane 1998 ).”
DiceKriging, DiceOptim: Two R Packages for the Analysis of Computer Experiments by Kriging-Based Metamodeling and Optimization (2012, methodology): “…we have selected a quasi-Newton Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm (function optim) and the hybrid algorithm genoud from package rgenoud (Mebane and Sekhon 2011), taking advantage of both the global search provided by a genetic algorithm and the local search based on gradients.”
fitdistrplus: An R Package for Fitting Distributions (2015, methodology): “Many extensions of the ﬁtdistrplus package are planned in the future: we target to extend to censored data some methods for the moment only available for non-censored data, especially concerning goodness-of-ﬁt evaluation and ﬁtting methods.”
Newspaper Closures Polarize Voting Behavior (2018, methodology): “We use the Matching (Sekhon, 2011) and rgenoud (Mebane & Sekhon, 2011) packages in the R programming language to construct these weights (R Core Team, 2016).”
Surrogate-Assisted Learning of Neural Networks (2017, methodology): “• rgenoud [11, 17] is an R-package which provides and implementation of a so-called hybrid algorithm.”
A benchmark of kriging-based infill criteria for noisy optimization (2013, methodology): “Here, we chose to optimize the infill criteria using the genoud algorithm (GENetic Optimization Using Derivatives, [36]), which implements a hybrid of evolutionary algorithms and gradient descent.”
Robust estimation of optimal dynamic treatment regimes for sequential treatment decisions (2013, methodology): “To carry out the maximizations, we used a genetic algorithm discussed by Goldberg (1989), implemented in the rgenoud package in R (Mebane & Sekhon, 2011); see §7 of the Supplementary Material for details.”