Main Content

Global vs. Local Optimization 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)={-exp(-(x100)2)forx100,-exp(-1)+(x-100)(x-102)forx>100.

Plot the function.

t = -10:.1:103;
for ii = 1:length(t)
    y(ii) = two_min(t(ii));
end
plot(t,y)

Figure contains an axes object. The axes object contains an object of type line.

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.

Run ga Using Default Parameters

The code for the two_min helper function is at the end of this example. Run ga with default parameters to minimize the two_min function. Use the gaplot1drange helper function (included at the end of this example) to plot the range of the ga population at each iteration.

rng default % For reproducibility
options = optimoptions('ga','PlotFcn',@gaplot1drange);
[x,fval] = ga(@two_min,1,[],[],[],[],[],[],[],options)
Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

Figure Genetic Algorithm contains an axes object. The axes object with title Range of Population, Mean contains an object of type errorbar.

x = -0.0688
fval = -1.0000

The genetic algorithm returns a point very close to the local minimum at x = 0. Note that all individuals lie between –60 and 60. The population never explores points near the global minimum at x = 101.

Increase Initial Range

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 the InitialPopulationRange option to [-10;90] and rerun the solver.

options.InitialPopulationRange = [-10;90];
[x,fval] = ga(@two_min,1,[],[],[],[],[],[],[],options)
Optimization terminated: maximum number of generations exceeded.

Figure Genetic Algorithm contains an axes object. The axes object with title Range of Population, Mean contains an object of type errorbar.

x = 100.9783
fval = -1.3674

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.

Helper Functions

This code creates the two_min helper function.

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

This code creates the gaplot1drange helper function.

function state = gaplot1drange(options,state,flag)
%gaplot1drange Plots the mean and the range of the population.
%   STATE = gaplot1drange(OPTIONS,STATE,FLAG) plots the mean and the range
%   (highest and the lowest) of individuals (1-D only).  
%
%   Example:
%   Create options that use gaplot1drange
%   as the plot function
%     options = optimoptions('ga','PlotFcn',@gaplot1drange);

%   Copyright 2012-2014 The MathWorks, Inc.

if isinf(options.MaxGenerations) || size(state.Population,2) > 1
    title('Plot Not Available','interp','none');
    return;
end
generation = state.Generation;
score = state.Population;
smean = mean(score);
Y = smean;
L = smean - min(score);
U = max(score) - smean;

switch flag

    case 'init'
        set(gca,'xlim',[1,options.MaxGenerations+1]);
        plotRange = errorbar(generation,Y,L,U);
        set(plotRange,'Tag','gaplot1drange');
        title('Range of Population, Mean','interp','none')
        xlabel('Generation','interp','none')
    case 'iter'
        plotRange = findobj(get(gca,'Children'),'Tag','gaplot1drange');
        newX = [get(plotRange,'Xdata') generation];
        newY = [get(plotRange,'Ydata') Y];
        newL = [get(plotRange,'Ldata') L];
        newU = [get(plotRange,'Udata') U];       
        set(plotRange,'Xdata',newX,'Ydata',newY,'Ldata',newL,'Udata',newU);
end
end

Related Topics