Разнообразие населения

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

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

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

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

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

По умолчанию 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.

Figure Genetic Algorithm contains 2 axes. Axes 1 with title Best: 1.99002 Mean: 2.1698 contains 2 objects of type line. These objects represent Best fitness, Mean fitness. Axes 2 with title Average Distance Between Individuals contains an object of type line.

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.

Figure Genetic Algorithm contains 2 axes. Axes 1 with title Best: 4.08885 Mean: 2915.48 contains 2 objects of type line. These objects represent Best fitness, Mean fitness. Axes 2 with title Average Distance Between Individuals contains an object of type line.

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.

Figure Genetic Algorithm contains 2 axes. Axes 1 with title Best: 0.00111749 Mean: 5.66579 contains 2 objects of type line. These objects represent Best fitness, Mean fitness. Axes 2 with title Average Distance Between Individuals contains an object of type line.

x = 1×2

    0.0013    0.0020

fval = 0.0011

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

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

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

Функция фитнеса

Функция фитнеса lincontest6, в комплекте с вашим программным обеспечением. Это квадратичная функция двух переменных:

$$f(x) = \frac{x_1^2}{2} + x_2^2 - x_1 x_2 - 2x_1 - 6x_2.$$

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

Сохраните следующий код в файл по пути MATLAB ® с именем gaplotshowpopulation2.

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

Пользовательская функция построения графика строит графики линий, представляющих линейные неравенства и связанные ограничения, строит графики уровней функции соответствия и строит графики населения по мере ее развития. Эта функция построения графика рассчитывает иметь не только обычные входы (options,state,flag), но также указатель на функцию соответствия, @lincontest6 в этом примере. Чтобы сгенерировать кривые уровня, пользовательской функция построения графика нужна функция соответствия.

Ограничения задачи

Включите ограничения и линейные ограничения.

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

Опции для включения функции построения графика

Установите опции, чтобы включить функцию построения графика при ga выполняется.

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.

ga быстро сходится к одной точке, решению.

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

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

Примечание

Вы должны задать Population size, чтобы быть, по крайней мере, значением Number of variables, так что индивидуумы в каждом населении охватывают искомое пространство.

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

Похожие темы