Поиск глобального минимума

Иногда целью оптимизации является поиск глобального минимума или максимума функции - точки, где значение функции меньше или больше в любой другой точке пространства поиска. Однако алгоритмы оптимизации иногда возвращают локальный минимум - точку, где значение функции меньше, чем в соседних точках, но возможно больше, чем в удаленной точке в пространстве поиска. Генетический алгоритм иногда может преодолеть этот недостаток с правильными настройками.

В качестве примера рассмотрим следующую функцию.

Постройте график функции.

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

Функция имеет два локальных минимума, один при $$x = 0$$, где значение функции равно -1, а другой при $$x = \mathrm{}\mathrm{}101$$, где значение функции равно $$-\mathrm{1-1/е} \mathrm{}$$. Поскольку последнее значение меньше, глобальный минимум имеет значение $$x = \mathrm{}\mathrm{}101$$.

Управляемый ga Использование параметров по умолчанию

Код для two_min вспомогательная функция находится в конце этого примера. Управляемый ga с параметрами по умолчанию для минимизации two_min функция. Используйте gaplot1drange вспомогательная функция (включенная в конце этого примера) для построения графика диапазона ga заполнение на каждой итерации.

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.

x = -0.0688

fval = -1.0000

Генетический алгоритм возвращает точку, очень близкую к локальному минимуму при $$x = 0$$. Отметим, что все особи лежат между -60 и 60. Население никогда не исследует точки вблизи глобального минимума при $$x = \mathrm{}\mathrm{}101$$.

Увеличить начальный диапазон

Одним из способов заставить генетический алгоритм исследовать более широкий спектр точек - то есть увеличить разнообразие популяций - является увеличение начального диапазона. Начальный диапазон не должен включать точку x = 101, но он должен быть достаточно большим, чтобы алгоритм генерировал индивидов вблизи x = 101. Установите InitialPopulationRange опция для [-10;90] и повторно запустите решатель.

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

Optimization terminated: maximum number of generations exceeded.

x = 100.9783

fval = -1.3674

На этот раз заказной сюжет показывает гораздо более широкий круг особей. Есть особи около 101 с самого начала, и население в среднем начинает сходиться к 101.

Вспомогательные функции

Этот код создает 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

Этот код создает 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