0
$\begingroup$

While reading a book on introduction to GA, I stepped upon a chapter where some advantages and disadvantages of these algorithms were described. One of the mentioned disadvantages was "Cannot use gradients" but there was no further explanation why. What did the authors mean by that? I couldn't come with a better idea than that you cannot just use a gradient as a fitness function. Still, I don't know why that would be.

$\endgroup$

2 Answers 2

3
$\begingroup$

Let's think about what a gradient is and what it means to "use" a gradient as part of an optimization method.

A gradient is a partial derivative that specifies the rate of change in every direction from some point on a surface. With respect to optimization, that surface is the thing that we're looking for some extremum of. Often it might be something like an error function, such as the use of gradients in backpropagation for training a neural network. You compute the error function $f(d,w)$ where $d$ is the data, $w$ is the weights of the network, and $f$ is the error (the squared difference between what the network outputs and the desired target). The gradient with respect to $w$ gives us the rate of change of that error as we change the weights. And because we want the error to be small, we can just change the weights in the direction of the greatest decrease in the error. That's an example of "using" a gradient in optimization. It's a way of choosing an action based on knowing mathematically what will happen to your function for whatever move you make.

With a GA, how would this work? Now I want to minimize (or maximize, whatever) my fitness function $f$. The way a GA works is by creating a population of random candidate solutions and interatively using selection to choose fitter parents followed by operators like crossover and mutation to produce offspring that should be similar to their parents but usually not identical. The genetic operators create new search points, and selection serves to focus that creation into specific regions of the search space because it's always trying to favor fitter parents as starting points for those operators. Over time, we converge onto hopefully very fit individuals.

Where in that framework can I "use" a gradient? Again, using the gradient means from a given point, I just know a mathematical expression that tells me which direction is "downhill". So if I want to minimize my function, I just move in that direction. But the whole thing that defines a GA is the use of those genetic operators to determine where to sample next. If I put something in that just follows the gradient, I don't really have a GA anymore.

$\endgroup$
1
  • $\begingroup$ Nice explanation. I didn't think about it this way and that's why it confused me. Since gradients are just functions, I was wondering why you can't just assign them to a fitness function. But now I see it wouldn't make too much sense. $\endgroup$ Nov 3, 2022 at 10:21
1
$\begingroup$

To answer this question, you must first understand what a gradient is. This article "What Is a Gradient in Machine Learning?" offers a nice introductory explanation. In machine learning, gradients (which are essentially derivatives) are used to find the minimum of a loss function. Minimizing the loss function is effectively finding the optimal machine learning model (i.e., the model having weights that minimize the loss function). Gradient descent is a family of algorithms that use the gradient to minimize the loss function. The ability to use gradient descent to optimize models is a major advantage. The article "Introduction to Gradient Descent" can help in understanding gradient descent. Genetic algorithms do not employ a continuous function that can be differentiated and minimized (i.e., no gradient). Instead, the goal of genetic algorithms is to maximize fitness, but fitness is itself not a defined well-defined function, and no gradient can be calculated and gradient descent cannot be leveraged to optimize fitness. Rather, genetic algorithms use a distinct algorithm that employs selection, crossover, mutation, and evaluation in a recursive manner to maximize the fitness.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .