Ограниченная минимизация Используя генетический алгоритм

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

Ограниченная проблема минимизации

Для этой проблемы целевая функция, чтобы минимизировать является простой функцией 2D переменной x.

simple_objective(x) = (4 - 2.1*x(1)^2 + x(1)^4/3)*x(1)^2 + x(1)*x(2) + (-4 + 4*x(2)^2)*x(2)^2;

Эта функция известна как "бегунок", как описано в L.C.W. Диксон и Г.П. Сзего [1].

Кроме того, проблема имеет нелинейные ограничения и границы.

   x(1)*x(2) + x(1) - x(2) + 1.5 <= 0  (nonlinear constraint)
   10 - x(1)*x(2) <= 0                 (nonlinear constraint)
   0 <= x(1) <= 1                      (bound)
   0 <= x(2) <= 13                     (bound)

Закодируйте функцию фитнеса

Создайте файл MATLAB под названием simple_objective.m содержа следующий код:

type simple_objective
function y = simple_objective(x)
%SIMPLE_OBJECTIVE Objective function for PATTERNSEARCH solver

%   Copyright 2004 The MathWorks, Inc.  

x1 = x(1);
x2 = x(2);
y = (4-2.1.*x1.^2+x1.^4./3).*x1.^2+x1.*x2+(-4+4.*x2.^2).*x2.^2;

Решатели, такие как ga примите один вход x, где x имеет столько же элементов сколько количество переменных в проблеме. Целевая функция вычисляет скалярное значение целевой функции и возвращает его в ее одном выходном аргументе y.

Закодируйте ограничительную функцию

Создайте файл MATLAB под названием simple_constraint.m содержа следующий код:

type simple_constraint
function [c, ceq] = simple_constraint(x)
%SIMPLE_CONSTRAINT Nonlinear inequality constraints.

%   Copyright 2005-2007 The MathWorks, Inc.

c = [1.5 + x(1)*x(2) + x(1) - x(2); 
     -x(1)*x(2) + 10];

% No nonlinear equality constraints:
ceq = [];

Ограничительная функция вычисляет значения всех ограничений неравенства и ограничений равенства и возвращает векторы c и ceq, соответственно. Значение c представляет нелинейные ограничения неравенства, которые решатель пытается сделать меньше чем или равным нулю. Значение ceq представляет нелинейные ограничения равенства, которые решатель пытается сделать равным нулю. Этот пример не имеет никаких нелинейных ограничений равенства, таким образом, ceq = []. Для получения дополнительной информации смотрите Нелинейные Ограничения.

Минимизация Используя ga

Задайте целевую функцию как указатель на функцию.

ObjectiveFunction = @simple_objective;

Задайте проблемные границы.

lb = [0 0];   % Lower bounds
ub = [1 13];  % Upper bounds

Задайте нелинейную ограничительную функцию как указатель на функцию.

ConstraintFunction = @simple_constraint;

Задайте количество переменных задачи.

nvars = 2;

Вызовите решатель, запросив оптимальную точку x и значение функции в оптимальной точке fval.

rng default % For reproducibility
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],lb,ub,ConstraintFunction)
Optimization terminated: average change in the fitness value less than options.FunctionTolerance
 and constraint violation is less than options.ConstraintTolerance.
x = 1×2

    0.8122   12.3103

fval = 9.1268e+04

Добавьте визуализацию

Чтобы наблюдать прогресс решателя, задайте опции тот выбор две функции построения графика. Функция построения графика gaplotbestf строит лучшее значение целевой функции в каждой итерации и функцию построения графика gaplotmaxconstr строит максимальное нарушение ограничений в каждой итерации. Установите эти две функции построения графика в массиве ячеек. Кроме того, информация об отображении о прогрессе решателя в Командном окне путем установки Display опция к 'iter'.

options = optimoptions("ga",'PlotFcn',{@gaplotbestf,@gaplotmaxconstr}, ...
    'Display','iter');

Запустите решатель, включая options аргумент.

[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],lb,ub, ...
    ConstraintFunction,options)
Single objective optimization:
2 Variable(s)
2 Nonlinear inequality constraint(s)

Options:
CreationFcn:       @gacreationuniform
CrossoverFcn:      @crossoverscattered
SelectionFcn:      @selectionstochunif
MutationFcn:       @mutationadaptfeasible

                              Best       Max        Stall
Generation  Func-count        f(x)     Constraint  Generations
    1           2524       91986.8    7.786e-09      0
    2           4986       94677.4            0      0
    3          10362       96929.2            0      0
    4          16067       96006.3            0      0
    5          23405       91267.6    0.0009898      0
Optimization terminated: average change in the fitness value less than options.FunctionTolerance
 and constraint violation is less than options.ConstraintTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: 91264 Mean: 91268 contains 2 objects of type line. These objects represent Best fitness, Mean fitness. Axes object 2 with title Max constraint: 0.000989821 contains an object of type line.

x = 1×2

    0.8122   12.3103

fval = 9.1268e+04

С итеративным отображением, тем ga предоставляет подробную информацию о проблемном типе и создании, перекрестном соединении, мутации и операторах выбора.

Нелинейные ограничения вызывают ga решить много подпроблем в каждой итерации. Как показано и в графиках и в итеративном отображении, процесс решения имеет немного итераций. Однако Func-count столбец в итеративном отображении показывает много вычислений функции на итерацию.

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

ga использует мутацию и перекрестные функции, чтобы произвести новых индивидуумов при каждой генерации. Путем ga удовлетворяет линейные и связанные ограничения должен использовать мутацию и перекрестные функции, которые только генерируют допустимые точки. Например, в предыдущем вызове ga, функция мутации по умолчанию (для неограниченных проблем) mutationgaussian не удовлетворяет линейным ограничениям и так ga использует mutationadaptfeasible функционируйте вместо этого по умолчанию. Если вы обеспечиваете пользовательскую функцию мутации, эта пользовательская функция должна только сгенерировать точки, которые выполнимы относительно линейных и связанных ограничений. Все перекрестные функции в тулбоксе генерируют точки, которые удовлетворяют линейным ограничениям и границам.

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

Обеспечьте стартовую точку

Чтобы ускорить решатель, можно обеспечить начальную генеральную совокупность в InitialPopulationMatrix опция. ga использует начальную генеральную совокупность, чтобы запустить ее оптимизацию. Задайте вектор-строку или матрицу, где каждая строка представляет одну стартовую точку.

X0 = [0.8 12.5]; % Start point (row vector)
options.InitialPopulationMatrix = X0;
[x,fval] = ga(ObjectiveFunction,nvars,[],[],[],[],lb,ub, ...
    ConstraintFunction,options)
Single objective optimization:
2 Variable(s)
2 Nonlinear inequality constraint(s)

Options:
CreationFcn:       @gacreationuniform
CrossoverFcn:      @crossoverscattered
SelectionFcn:      @selectionstochunif
MutationFcn:       @mutationadaptfeasible

                              Best       Max        Stall
Generation  Func-count        f(x)     Constraint  Generations
    1           2500       91507.4            0      0
    2           4950       91270.4    0.0009621      0
    3           7400       91270.4    0.0009621      1
    4           9850       91269.2    0.0009958      0
    5          12300       91269.2    0.0009958      1
Optimization terminated: average change in the fitness value less than options.FunctionTolerance
 and constraint violation is less than options.ConstraintTolerance.

Figure Genetic Algorithm contains 2 axes objects. Axes object 1 with title Best: 91267.2 Mean: 91270.1 contains 2 objects of type line. These objects represent Best fitness, Mean fitness. Axes object 2 with title Max constraint: 0.000995771 contains an object of type line.

x = 1×2

    0.8122   12.3104

fval = 9.1269e+04

В этом случае обеспечение стартовой точки существенно не изменяет прогресс решателя.

Ссылки

[1] Диксон, L. C. W. и G.P. Szego (редакторы).. К глобальной оптимизации 2. Северная Голландия: Elsevier Science Ltd., Амстердам, 1978.

Похожие темы

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