rgenoud (version 1.18)

genoud: GENetic Optimization Using Derivatives

Description

GENOUD is a function that combines evolutionary algorithm methods with a derivative-based, quasi-Newton method to solve difficult unconstrained optimization problems. GENOUD is made to solve 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. Multiple local optima may exist, so that there is no guarantee that a derivative-based method will converge to the global optimum. On the other hand, algorithms that do not use derivative information (such as pure GAs) are for many problems needlessly poor at local hill climbing. Most statistical problems are regular in the neighborhood of the solution. Therefore, for some portion of the search space derivative information is useful.

Usage

genoud
  (fn, nvars, max=FALSE, pop.size=100, max.generations=100, wait.generations=10,
   hard.generation.limit=TRUE, starting.values=NULL, MemoryMatrix=NULL, Debug=FALSE, 
   Domains=NULL, default.domains=10,
   gradient.check=TRUE, boundary.enforcement=2,
   solution.tolerance=0.001, BFGS=TRUE, data.type.int=FALSE, hessian=FALSE,
   unif.seed=812821, int.seed=53058,
   print.level=2, share.type=0, instance.number=0,
   output.path="stdout", output.append=FALSE, project.path="genoud.pro",
   P1=50, P2=50, P3=50, P4=50, P5=50, P6=50, P7=50, P8=50, P9=0)

Arguments

fn

The function to be minimized by default (or maximized if max=T), with first argument the vector of parameters over which minimizing is to take place. It should return a scalar result. For example, say we wish to maximize the sin()<

nvars

This is the number of variables the function to be minimized (or maximized) takes.

max

Maximization (True) or Minimizing (False). This variable tells GENOUD if it is to minimize or maximize the objective function.

pop.size

Population Size. This is the number of individuals GENOUD uses to solve the optimization problem. There are several restrictions on what the value of this number can be. These constraints originate in what is required by several of the oper

max.generations

Maximum Generations. This is the maximum number of generations that GENOUD will run when attempting to optimize a function. This is a soft limit. The maximum generation limit will be binding for GENOUD only if hard.generation

wait.generations

If there is no improvement in the objective function of wait.generations number of generations, GENOUD will think that it has found the optimum. If the gradient.check trigger has been turned on, GENOUD will only start countin

hard.generation.limit

By default the max.generations variable is a binding constraint for GENOUD. But it fails to be binding if the hard.generation.limit is set to FALSE. Please see MemoryMatrix for some interesting interactions with mem

starting.values

This is a vector contains the starting values that GENOUD will use at startup. The starting.values vector is a way for the user to insert one individual into the starting population. GENOUD will randomly create the other individuals

MemoryMatrix

This variable controls how aggressive GENOUD is in saving memory. The variable my be $T$ or $F$. If it is $F$ GENOUD will be aggressive in conserving memory. The most significant implication of this variable being set to $F$ is that

Debug

This variable turns on some debugging information. This variable my be $T$ or $F$.

Domains

This is a nvars $\times 2$ matrix. The fist column is the lower bound, and the second column is the upper bound. None of GENOUD's starting population will be outside of the bounds. But some of the operators may generate childre

default.domains

If Domains, GENOUD will create a Domains matrix by setting the lower bound for all of the parameters equal to -1 $\times$ default.domains and the upper bound equal to default.domains.

gradient.check

If this variable is $T$, GENOUD will not start counting wait.generations unless the gradients are zero or solution.tolerance close to zero. This variable has not effect if the max.generations limit i

boundary.enforcement

This variable determines the degree to which GENOUD obeys the boundary constraints. Notwithstanding the value of the variable, none of GENOUD's starting population will be outside of the bounds. But some of the operators may gen

Value

• GENOUD returns a list with 7 objects. 8 objects are returned if the user as requested the hessian to be calculated at the solution---see the hessian variable. They are:
• value
  This variable contains the fitness value at the solution.
• generations
  This variables contains the number of generations GENOUD ran for.
• peakgeneration
  This variables contains the generation number at which GENOUD found the solution.
• pop.size
  This variable contains the population size that GENOUD actually used. See pop.size for why this value may differ from the population size the user requested.
• par
  This vector contains the parameter values found at the solution.
• gradients
  This vector contains the gradients found at the solution. If no gradients were calculated, they are reported to by $-1.0$.
• operators
  This vector reports the actual number of operators (of each type) GENOUD used. Please see the Operators Section for details.
• hessian
  If the user has requested the hessian matrix to be returned---via the hessian flag, the hessian at the solution will be returned. The user may use this matrix to calculate standard errors.

item

• solution.tolerance
• BFGS
• data.type.int
• hessian
• unif.seed
• int.seed
• print.level
• share.type
• instance.number
• output.path
• output.append
• project.path
• P1
• P2
• P3
• P4
• P5
• P6
• P7
• P8
• P9

code

print.level

eqn

$T$

emph

• Use of the integer data type is supported only as a beta feature.
• very

cr

• When the integer type is used, GENOUD never uses derivative information. This implies that the BFGS quasi-Newton optimizer is never used---i.e., the BFGS flag is false. It also implies that Operator 9 (Local-Minimum Crossover) is set to zero and that gradient checking (as a convergence criterion) is turned off. No matter what the values of these other variables is, the value of data.type.int takes precedence---i.e., if GENOUD is told that its is searching over an integer parameter space all everything that requires gradient information is turned off. There is no option to mix the two types of data. If one wants to mix the two, it is suggested that the user pick integer type and in her objective function map a particular integer range into a floating point number range. For example, tell GENOUD to search from 0 to 100 and divide by 100 to obtain a search grid of 0 to 1.0 (by .1).
• If the Project File contains a smaller population than the current GENOUD run, GENOUD will randomly create the necessary individuals. If the Project File contains a larger population than the current GENOUD run, GENOUD will kill the necessary individuals using exponential selection. If the number of variables (see nvars) reported in the Project File is different from the current GENOUD run, GENOUD does not use the Project File (regardless of the value of share.type) and generates the necessary starting population at random.
• For the R version of GENOUD, this variable is of greatly limited use. It is basically there in case GENOUD is being used to optimize GENOUD.

Operators

GENOUD has nine operators that it uses. The integer values which are assigned to each of these operators (P1$\cdots$P9) are weights. GENOUD calculates the sum of $s = P1+P2+\cdots+P9$. Each operator is assigned a weight equal to $W_{n} = \frac{s}{P_{n}}$. The number of times an operator is called usually equals $c_{n} = W_{n} \times pop.size$. Operators 5 (Polytope Crossover), 6 (Multiple Point Simple Crossover) and 8 (Heuristic Crossover) require an even number of individuals to work on---i.e., they require two parents. Therefore, the pop.size variable and the operators sets must be such that these three operators have an even number of individuals to work with. If this does not occur, GENOUD (upwardly) adjusts the population size to make this constraint hold. Strong uniqueness checks have been built into the operators to help ensure that the operators produce offspring different from their parents, but this does not always happen! Note that GENOUD always keeps the best individual each generation. GENOUD's 9 operators are:

• 1

{Cloning} 2{Uniform Mutation} 3{Boundary Mutation} 4{Non-Uniform Crossover} 5{Polytope Crossover} 6{Multiple Point Simple Crossover} 7{Whole Non-Uniform Mutation} 8{Heuristic Crossover} 9{Local-Minimum Crossover: BFGS}

References

Sekhon, Jasjeet Singh and Walter R. Mebane, Jr. 1998. ``Genetic Optimization Using Derivatives: Theory and Application to Nonlinear Models.'' Political Analysis 7: 187-210. HTTP://jsekhon.fas.harvard.edu/genoud

See Also

optim.

Examples

#maximize the sin function
 sin1 <- genoud(sin, nvars=1, max=TRUE);

#minimize the sin function
 sin2 <- genoud(sin, nvars=1, max=FALSE);

#maximimize a univariate normal mixture which looks like a claw
claw <- function(xx) {
  Nd <- function(x, mu, sigma) {
    w <- (1.0/sqrt(2.0*pi*sigma*sigma)) ;
    z <- (x-mu)/sigma;
    w <- w*exp(-0.5*z*z) ;
    as.double(w);
  }
  x <- xx[1];
  y <- (0.46*(Nd(x,-1.0,2.0/3.0) + Nd(x,1.0,2.0/3.0)) +
	   (1.0/300.0)*(Nd(x,-0.5,.01) + Nd(x,-1.0,.01) + Nd(x,-1.5,.01)) +
	   (7.0/300.0)*(Nd(x,0.5,.07) + Nd(x,1.0,.07) + Nd(x,1.5,.07))) ;
  as.double(y);
}
 claw1   <- genoud(claw, nvars=1,P9=100,max=TRUE);

#maximimize a bivariate normal mixture which looks like a claw
biclaw <- function(xx) {
  mNd2 <- function(x1, x2, mu1, mu2, sigma1, sigma2, rho)
    {
      z1 <- (x1-mu1)/sigma1;
      z2 <- (x2-mu2)/sigma2;
      w <- (1.0/(2.0*pi*sigma1*sigma2*sqrt(1-rho*rho))) ;
      w <- w*exp(-0.5*(z1*z1 - 2*rho*z1*z2 + z2*z2)/(1-rho*rho)) ;
      as.double(w);
    }
  x1 <- xx[1]+1;
  x2 <- xx[2]+1;
  
  y <- (0.5*mNd2(x1,x2,0.0,0.0,1.0,1.0,0.0) +
	    0.1*(mNd2(x1,x2,-1.0,-1.0,0.1,0.1,0.0) +
		 mNd2(x1,x2,-0.5,-0.5,0.1,0.1,0.0) +
		 mNd2(x1,x2,0.0,0.0,0.1,0.1,0.0) +
		 mNd2(x1,x2,0.5,0.5,0.1,0.1,0.0) +
		 mNd2(x1,x2,1.0,1.0,0.1,0.1,0.0)));

  as.double(y);
}
 biclaw1 <- genoud(biclaw, nvars=2,P9=100,max=TRUE);