Esta página se ha traducido mediante traducción automática. Haga clic aquí para ver la última versión en inglés.

Optimización global y local con ga

Búsqueda de un mínimo global

A veces, el objetivo de una optimización es encontrar el mínimo o máximo global de una función, un punto donde el valor de la función es menor o mayor en cualquier otro punto del espacio de búsqueda. Sin embargo, los algoritmos de optimización a veces devuelven un mínimo local: un punto donde el valor de la función es menor que en los puntos cercanos, pero posiblemente mayor que en un punto distante en el espacio de búsqueda. El algoritmo genético a veces puede superar esta deficiencia con la configuración adecuada.

Como ejemplo, considere la siguiente función.

$$f(x)=\{\begin{array}{ll}-\exp \left(-{\left(\frac{x}{100}\right)}^2\right)& forx\le 100,\\ -\exp (-1)+(x-100)(x-102)& forx>100.\end{array}$$

Represente la función.

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

La función tiene dos mínimos locales, uno en $$x=0$$, donde el valor de la función es –1, y el otro en $$x=101$$, donde el valor de la función es $$–1–1/e$$. Dado que el último valor es menor, el mínimo global se produce en $$x=101$$.

Ejecutar ga utilizando parámetros predeterminados

El código para la función auxiliar two_min está al final de este ejemplo. Ejecute ga con los parámetros predeterminados para minimizar la función two_min. Utilice la función auxiliar gaplot1drange (incluida al final de este ejemplo) para representar el rango de la población ga en cada iteración.

rng default % For reproducibility
options = optimoptions('ga','PlotFcn',@gaplot1drange);
[x,fval] = ga(@two_min,1,[],[],[],[],[],[],[],options)

ga stopped because the average change in the fitness value is less than options.FunctionTolerance.

x = 
-0.0688

fval = 
-1.0000

El algoritmo genético devuelve un punto muy cercano al mínimo local en $$x=0$$. Tenga en cuenta que todos los individuos se encuentran entre -60 y 60. La población nunca explora puntos cercanos al mínimo global en $$x=101$$.

Aumentar el rango inicial

Una forma de hacer que el algoritmo genético explore un rango más amplio de puntos (es decir, aumentar la diversidad de las poblaciones) es aumentar el rango inicial. El rango inicial no tiene que incluir el punto x = 101, pero debe ser lo suficientemente grande para que el algoritmo genere individuos cerca de x = 101. Establezca la opción InitialPopulationRange en [-10;90] y vuelva a ejecutar el solucionador.

options.InitialPopulationRange = [-10;90];
[x,fval] = ga(@two_min,1,[],[],[],[],[],[],[],options)

ga stopped because it exceeded options.MaxGenerations.

x = 
100.9783

fval = 
-1.3674

Esta vez, la gráfica personalizada muestra una gama mucho más amplia de individuos. Hay individuos cercanos a 101 desde el principio, y la media poblacional comienza a converger a 101.

Funciones auxiliares

Este código crea la función auxiliar two_min.

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

Este código crea la función auxiliar gaplot1drange.

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

Consulte también

Temas

• ¿Qué es la optimización global?
• Population Diversity
• Isolated Global Minimum