Генетический алгоритм

В данной заметке мы рассмотрим применение генетического алгоритма для задачи поиска экстремума функции.

Постановка задачи

Пусть дана следующая функция, z(x,y) = x/(x^2+2*y^2+1), требуется найти глобальный минимум функции. Решение задачи осложняется наличием двух переменных. Для решения этой задачи воспользуемся генетическим алгоритмом.

Ход решения

#1 Возьмем некоторые (случайные) пары (x,y):

x -2 -1 0 2
y 0 -2 -1 1

#2 Вычислим значения функции z(x,y) от выбранных пар:

z -0.4 -0.1 0 0.2857

#3 Воспользуемся следующей схемой для создания нового поколения, таким образом отсеем одно решение.

#4 Получим новые пары (x,y):

x -1 0 2 2
y 1 1 -2 -1

#5 Повторив шаг 2,3 получим новое приближение.

Алгоритм решения

Ниже приведен запрограммированный генетический алгоритм на языке MATLAB.

z = @(x,y) x./(x.^2+2.*y.^2+1);
%
X = [-2, -1, 0, 2];
Y = [0, -2, -1, 1];
Z = 1:4;
% 
step_count = 10; % количество шагов
for step=1:step_count;
    % Вектор значений
    for i=1:length(X)
        Z(i) = z(X(i),Y(i));
    end;
    % Максимальное значение
    index = find(Z == max(Z(:)));
    % Минимальное значение
    min_value = min(Z);
    % Новое поколение
    XX = 1:3;
    YY = 1:3;
    ii = 1;
    for i=1:length(X)
        if (i==index)
            continue;
        end;
        XX(ii) = X(i);
        YY(ii) = Y(i);
        ii = ii + 1;
    end;
    % (используется заданная схема)
    X = [ XX(2), XX(3), XX(1),XX(1) ];
    Y = [ YY(1), YY(1), YY(2),YY(3) ];
end;
% ответ
disp(min_value);

Заключение

Данный пример рассматривает упрощенный генетический алгоритм, в котором отсутствует очень важный этап - мутация. Те мы не вносили хаос в систему, который бы привет нас к новым результатам.

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 24.11.17)