Документация

Важность разнообразия населения

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

В этом разделе объясняется, как управлять разнообразием путем установки начальной области значений населения. Установка количества мутации описывает, как количество мутации влияет на разнообразие.

В этом разделе также объясняется, как задать размер населения.

Установите начальную область значений

По умолчанию ga создает случайную начальную генеральную совокупность с помощью функции создания. Можно задать область значений векторов в начальную генеральную совокупность в InitialPopulationRange опция.

Примечание: Начальная область значений ограничивает область значений точек в начальной генеральной совокупности, задавая нижнюю и верхнюю границы. Последующие поколения могут содержать точки, значения которых не находятся в начальной области значений. Установите верхнюю и нижнюю границы для всех поколений, используя lb и ub входные параметры.

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

Этот пример показывает, как начальная область значений влияет на эффективность генетического алгоритма. В примере используется функция Растригина, описанная в Функции Минимизации Растригина. Минимальное значение функции 0, которое происходит в источник.

rng(1) % For reproducibility
fun = @rastriginsfcn;
nvar = 2;
options = optimoptions('ga','PlotFcn',{'gaplotbestf','gaplotdistance'},...
    'InitialPopulationRange',[1;1.1]);
[x,fval] = ga(fun,nvar,[],[],[],[],[],[],[],options)

Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

x = 1×2

    0.9942    0.9950

fval = 1.9900

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

Затем попробуйте задать InitialPopulationRange по [1; 100]. На этот раз результаты являются более переменными. Текущая настройка случайных чисел вызывает довольно типичный результат.

options.InitialPopulationRange = [1;100];
[x,fval] = ga(fun,nvar,[],[],[],[],[],[],[],options)

Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

x = 1×2

    0.9344   -1.0792

fval = 4.0889

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

Теперь установите InitialPopulationRange по [1; 2]. Эта настройка хорошо подходит для задачи.

options.InitialPopulationRange = [1;2];
[x,fval] = ga(fun,nvar,[],[],[],[],[],[],[],options)

Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

x = 1×2

    0.0013    0.0020

fval = 0.0011

Подходящее разнообразие обычно вызывает ga для получения лучшего результата, чем в двух предыдущих случаях.

Пользовательские функции построения графика и линейные ограничения в ga

Этот пример показывает, как @gacreationlinearfeasibleфункция создания по умолчанию для линейно ограниченных задач создает население для ga. Население хорошо рассеивается и смещена, чтобы лежать на границах ограничений. В примере используется пользовательская функция построения графика.

function state = gaplotshowpopulation2(~,state,flag,fcn)
%gaplotshowpopulation2 Plots the population and linear constraints in 2-d.
%   STATE = gaplotshowpopulation2(OPTIONS,STATE,FLAG) plots the population
%   in two dimensions.
%
%   Example:
%     fun = @lincontest6;
%     options = gaoptimset('PlotFcn',{{@gaplotshowpopulation2,fun}});
%     [x,fval,exitflag] = ga(fun,2,A,b,[],[],lb,[],[],options);

% This plot function works in 2-d only
if size(state.Population,2) > 2
    return;
end
if nargin < 4
    fcn = [];
end
% Dimensions to plot
dimensionsToPlot = [1 2];

switch flag
    % Plot initialization
    case 'init'
        pop = state.Population(:,dimensionsToPlot);
        plotHandle = plot(pop(:,1),pop(:,2),'*');
        set(plotHandle,'Tag','gaplotshowpopulation2')
        title('Population plot in two dimension','interp','none')
        xlabelStr = sprintf('%s %s','Variable ', num2str(dimensionsToPlot(1)));
        ylabelStr = sprintf('%s %s','Variable ', num2str(dimensionsToPlot(2)));
        xlabel(xlabelStr,'interp','none');
        ylabel(ylabelStr,'interp','none');
        hold on;
       
        % plot the inequalities
        plot([0 1.5],[2 0.5],'m-.') %  x1 + x2 <= 2
        plot([0 1.5],[1 3.5/2],'m-.'); % -x1 + 2*x2 <= 2
        plot([0 1.5],[3 0],'m-.'); % 2*x1 + x2 <= 3
        % plot lower bounds
        plot([0 0], [0 2],'m-.'); % lb = [ 0 0];
        plot([0 1.5], [0 0],'m-.'); % lb = [ 0 0];
        set(gca,'xlim',[-0.7,2.2])
        set(gca,'ylim',[-0.7,2.7])
        axx = gcf;
        % Contour plot the objective function
        if ~isempty(fcn)
            range = [-0.5,2;-0.5,2];
            pts = 100;
            span = diff(range')/(pts - 1);
            x = range(1,1): span(1) : range(1,2);
            y = range(2,1): span(2) : range(2,2);

            pop = zeros(pts * pts,2);
            values = zeros(pts,1);
            k = 1;
            for i = 1:pts
                for j = 1:pts
                    pop(k,:) = [x(i),y(j)];
                    values(k) = fcn(pop(k,:));
                    k = k + 1;
                end
            end
            values = reshape(values,pts,pts);
            contour(x,y,values);
            colorbar
        end
        % Show the initial population
        ax = gca;
        fig = figure;
        copyobj(ax,fig);colorbar
        % Pause for three seconds to view the initial plot, then resume
        figure(axx)
        pause(3);
    case 'iter'
        pop = state.Population(:,dimensionsToPlot);
        plotHandle = findobj(get(gca,'Children'),'Tag','gaplotshowpopulation2');
        set(plotHandle,'Xdata',pop(:,1),'Ydata',pop(:,2));
end

A = [1,1;-1,2;2,1];
b = [2;2;3];
lb = zeros(2,1);

options = optimoptions('ga','PlotFcns',...
{{@gaplotshowpopulation2,@lincontest6}});

rng default % for reproducibility
[x,fval] = ga(@lincontest6,2,A,b,[],[],lb,[],[],options);

Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

Установка размера населения

Поле Population size в Population опциях определяет размер населения для каждой генерации. Увеличение размера населения позволяет генетическому алгоритму искать больше точек и, таким образом, получать лучший результат. Однако, чем больше размер населения, тем больше генетического алгоритма требуется для вычисления каждой генерации.

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