1
$\begingroup$

When it comes to optimizing objective functions belonging to Statistical and Machine Learning Models, there seems to be a general rule:

High dimensional objective functions with many parameters are "computationally expensive" to optimize As such, there tends to be two general types of algorithms that are used to optimize objective functions:

  • Gradient Descent: Gradient Descent tries to find the minimum point (i.e. "optimize") of these objective functions by repeatedly calculating the derivatives of these objective functions, and moving in the direction of these derivatives.

  • Evolutionary Algorithms: Evolutionary Algorithms (e.g. Genetic Algorithm) also try to find the minimum point of these objective functions, but instead of repeatedly evaluating the derivatives of the function, they work by "randomly moving in many directions at the same time, and probabilistically moving more in those directions that are producing lesser values of the function". This is called "mutation and crossover" - I have greatly simplified the process.

My Question: As the number of dimensions in the objective function increases, it becomes more and more computationally expensive to repeatedly evaluate the derivatives of the objective function- since Evolutionary Algorithms do not need to repeatedly evaluate these derivatives, they are said to be "computationally cheaper" compared to Gradient Based Methods. Although there have been no major results established on the convergence of Evolutionary Algorithms (whereas many theoretical results have been established on the convergence of Gradient Based Methods) : For the exact same objective function - do we know precisely how much cheaper "Crossover and Mutation" costs us compared to "Evaluating Second Derivatives"?

There still seems to be some costs associated with "Crossover and Mutation" (e.g. randomly storing, sorting and permuting well-performing "chromosomes" i.e. past solutions) - but do we know how much cheaper this costs us compared to evaluating derivatives (e.g. can we bound this using some Big-O Landau Notation or using Linear vs. Polynomial Time)?

Thanks!

Extra: Comparison of Gradient Descent and Genetic Algorithm for Optimizing the Rastrign Function using the R Programming language

1) Genetic Algorithm

library(GA)

start.time <- Sys.time()



  #define function to be optimized
Rastrigin <- function(x1, x2)
{
  20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
}

x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)

#run optimization through the genetic algorithm (with constraints)
GA <- ga(type = "real-valued", 
         fitness =  function(x) -Rastrigin(x[1], x[2]),
         lower = c(-5.12, -5.12), upper = c(5.12, 5.12), 
         popSize = 50, maxiter = 1000, run = 100)

end.time <- Sys.time()
time.taken <- end.time - start.time

Results:

 time.taken

Time difference of 1.266233 secs

GA@solution
                x1          x2
[1,] -4.947186e-06 3.72529e-07

2) Gradient Descent

library(pracma)

start.time <- Sys.time()

Rastrigin <- function(x)
    {
        return(20 + x[1]^2 + x[2]^2 - 10*(cos(2*pi*x[1]) + cos(2*pi*x[2])))
    }

 steep_descent(c(1, 1), Rastrigin)

end.time <- Sys.time()
    time.taken <- end.time - start.time
    
    time.taken

Results:

time.taken
Time difference of 0.01959896 secs

$xmin
[1] 0.9949586 0.9949586

$fmin
[1] 1.989918

$niter
[1] 3

References:

$\endgroup$

1 Answer 1

2
$\begingroup$

I think this is an overgeneralization. For cases with very expensive objective functions (i.e. multiphysics simulations), genetic algorithms are basically unusable and they use the adjoint method to get the sensitivities at a cost independent of the number of design variables. We can also use the direct adjoint method for second derivatives at reduced cost. I would hesitate to use a smooth and cheap function as the basis of a more general comparison between genetic and gradient based methods.

$\endgroup$
3
  • $\begingroup$ With a gradient based method all you can do is find the nearest local minimum while for genetic algorithms you can do better in terms of approaching the global minimum. And it is not necessarily true that for the objective function based on multi-physics simulations genetic algorithms are unusable, there are counter-examples. Also, note that there are optimization algorithms that are not gradient based but are not in the genetic optimization class either, e.g., check out the Amoeba algorithm in the Numerical Recipes. $\endgroup$ Feb 22, 2022 at 4:46
  • $\begingroup$ Thank you everyone for your replies! I appreciate the discussion! $\endgroup$
    – stats_noob
    Feb 22, 2022 at 4:55
  • $\begingroup$ @MaximUmansky I have seen MDO with genetic (or global non-gradient based) algorithms only with reduced order models. Do you have a reference for high-fidelity MDO with genetic algorithms. And yes, I agree the benefit of the global approach is the ability to find the global minimum as opposed the gradient-based which can only find the local. $\endgroup$
    – EMP
    Feb 22, 2022 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.