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

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

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

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

Этот раздел также объясняет, как установить численность населения.

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

По умолчанию, 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. Население хорошо рассеивается и смещается, чтобы лечь на границы ограничений. Пример использует пользовательскую функцию построения графика.

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

Функцией фитнеса является 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, которые возвращают хорошие результаты, не занимая препятствующее количество времени, чтобы запуститься.

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте