Global vs. Local Minima Using ga

Searching for a Global Minimum

Sometimes the goal of an optimization is to find the global minimum or maximum of a function—a point where the function value is smaller or larger at any other point in the search space. However, optimization algorithms sometimes return a local minimum—a point where the function value is smaller than at nearby points, but possibly greater than at a distant point in the search space. The genetic algorithm can sometimes overcome this deficiency with the right settings.

As an example, consider the following function

$f (x) = {\begin{array}{l} - \exp (- {(\frac{x}{100})}^{2}) & for x \leq 100, \\ - \exp (- 1) + (x - 100) (x - 102) & for x > 100. \end{array}$

The following figure shows a plot of the function.

Code for generating the figure

The function has two local minima, one at x = 0, where the function value is –1, and the other at x = 101, where the function value is –1 – 1/e. Since the latter value is smaller, the global minimum occurs at x = 101.

Running the Genetic Algorithm on the Example

To run the genetic algorithm on this example,

Copy and paste the following code into a new file in the MATLAB^® Editor.

function y = two_min(x)
if x <= 100
    y = -exp(-(x/100).^2);
else
    y = -exp(-1) + (x-100)*(x-102);
end

Save the file as two_min.m in a folder on the MATLAB path.
In the Optimization app,
- Set Fitness function to @two_min.
- Set Number of variables to 1.
- Click Start.

The genetic algorithm returns a point very close to the local minimum at x = 0.

The following custom plot shows why the algorithm finds the local minimum rather than the global minimum. The plot shows the range of individuals in each generation and the population mean.

Code for Creating the Figure

Note that all individuals lie between –70 and 70. The population never explores points near the global minimum at x = 101.

To run this problem using command-line functions:

options = optimoptions('ga','PlotFcn',@gaplot1drange);
x = ga(@two_min,1,[],[],[],[],[],[],[],options)

One way to make the genetic algorithm explore a wider range of points—that is, to increase the diversity of the populations—is to increase the Initial range. The Initial range does not have to include the point x = 101, but it must be large enough so that the algorithm generates individuals near x = 101. Set Initial range to [-10;90] as shown in the following figure.

Then click Start. The genetic algorithm returns a point very close to 101.

This time, the custom plot shows a much wider range of individuals. There are individuals near 101 from early on, and the population mean begins to converge to 101.

To run this problem using command-line functions:

options = optimoptions('ga','PlotFcn',@gaplot1drange,...
    'InitialPopulationRange',[-10;90]);
x = ga(@two_min,1,[],[],[],[],[],[],[],options)

Documentation