Смешанное целое число ga Оптимизация

Решение смешанного целого числа Задач оптимизации

ga может решить проблемы, когда определенные переменные являются целочисленными. Дайте IntCon, вектор компонентов x, которые являются целыми числами:

[x,fval,exitflag] = ga(fitnessfcn,nvars,A,b,[],[],...
    lb,ub,nonlcon,IntCon,options)

IntCon является вектором положительных целых чисел, который содержит x компоненты, которые являются целочисленными. Для примера, если вы хотите ограничить x(2) и x(10) чтобы быть целыми числами, задайте IntCon на [2,10].

surrogateopt решатель также принимает целочисленные ограничения.

Примечание

Существуют ограничения на типы проблем, которые ga может решить с целочисленными переменными. В частности, ga не принимает никаких ограничений равенства, когда существуют целочисленные переменные. Для получения дополнительной информации смотрите Характеристики Целочисленного Решателя ga.

Совет

ga решает целочисленные задачи лучше всего, когда вы обеспечиваете нижние и верхние границы для каждого x компонента.

Смешанная целочисленная оптимизация функции Растригина

Открыть Live Script

Этот пример показывает, как найти минимум функций Растригина, ограниченных, поэтому первый компонент x является целым числом. Компоненты x дополнительно ограничены в области 5π≤x(1)≤20π,-20π≤x(2)≤-4π .

Установите границы для вашей задачи

lb = [5*pi,-20*pi];
ub = [20*pi,-4*pi];

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

opts = optimoptions('ga','PlotFcn',@gaplotbestf);

Вызовите решатель ga, где x (1) имеет целочисленные значения

rng(1,'twister') % for reproducibility
IntCon = 1;
[x,fval,exitflag] = ga(@rastriginsfcn,2,[],[],[],[],...
    lb,ub,[],IntCon,opts)

Figure Genetic Algorithm contains an axes. The axes with title Best: 424.136 Mean: 424.368 contains 2 objects of type line. These objects represent Best penalty value, Mean penalty value.

Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance
and constraint violation is less than options.ConstraintTolerance.

x = 1×2

   16.0000  -12.9325


fval = 424.1355

exitflag = 1

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

Характеристики целочисленного решателя ga

Существуют некоторые ограничения на типы проблем, которые ga может решить, когда вы включаете целочисленные ограничения:

  • Нет линейных ограничений равенства. Должно быть, у вас есть   Aeq = [] и   beq = []. Для возможного обходного пути смотрите No Equality Constraints.

  • Нет нелинейных ограничений равенства. Любая нелинейная функция ограничения должна вернуться [] для нелинейного ограничения равенства. Для возможного обходного пути смотрите Пример: Целочисленное программирование с нелинейным ограничением равенства.

  • Только doubleVector тип населения.

  • Нет пользовательской функции создания (CreationFcn опция), функция кроссовера (CrossoverFcn опция), функция мутации (MutationFcn опция) или начальные счета (InitialScoreMatrix опция). Если вы поставляете что-либо из этого, ga переопределяет их настройки.

  • ga использует только двоичную функцию выбора турнира (SelectionFcn опция) и переопределяет любую другую настройку.

  • Гибридная функция отсутствует. ga переопределяет любой параметр HybridFcn опция.

  • ga игнорирует ParetoFraction, DistanceMeasureFcn, InitialPenalty, и PenaltyFactor опции.

Перечисленные ограничения в основном являются естественными, а не произвольными. Для примера:

  • Гибридных функций, поддерживающих целочисленные ограничения, нет. Так ga не использует гибридные функции, когда существуют целочисленные ограничения.

  • Чтобы получить целочисленные переменные, ga использует специальные функции создания, кроссовера и мутации.

Никаких ограничений равенства

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

3 <reservedrangesplaceholder1> 1 - 2 <reservedrangesplaceholder0> 2 = 5,

создать два ограничения неравенства:

3 <reservedrangesplaceholder1> 1 - 2 <reservedrangesplaceholder0> 2  5
3 <reservedrangesplaceholder1> 1 - 2 <reservedrangesplaceholder0> 2  5.

Чтобы записать эти ограничения в форму  A x ≤ b, умножить второе неравенство на -1:

– 3 <reservedrangesplaceholder1> 1 + 2 <reservedrangesplaceholder0> 2 -5.

Можно попытаться включить ограничение равенства с помощью A = [3,-2;-3,2] и b = [5;-5].

Помните, что эта процедура может быть неудачной; ga испытывает трудности с одновременными целыми числами и ограничениями равенствами.

Пример: Целочисленное программирование с нелинейным ограничением равенства.  Этот пример пытается найти минимум функции Ackley (включенной в ваше программное обеспечение) в пяти размерностях с этими ограничениями:

  • x(1), x(3), и x(5) являются целыми числами.

  • norm(x) = 4.

Функцию Ackley трудно минимизировать. Добавление целого числа и ограничений равенства увеличивает сложность.

Чтобы включить нелинейное ограничение равенства, задайте небольшой допуск tol что позволяет использовать норму x быть внутри tol от 4. Без допуска нелинейное ограничение равенства никогда не выполняется, и решатель не понимает, когда у него есть возможное решение.

  1. Напишите выражение   norm(x) = 4 как два неравенства «меньше нуля»:

      norm(x) - 4 ≤ 0
      -(norm(x) - 4) ≤ 0.

  2. Допустим небольшой допуск в неравенствах:

        norm(x) - 4 - tol ≤ 0
        -(norm(x) - 4) - tol ≤ 0.

  3. Напишите нелинейную функцию ограничения неравенства, которая реализует эти неравенства:

    function [c, ceq] = eqCon(x)

ceq = [];
rad = 4;
tol = 1e-3;
confcnval = norm(x) - rad;
c = [confcnval - tol;-confcnval - tol];

  4. Установите опции:

    • MaxStallGenerations = 50 - Разрешить решателю попробовать некоторое время.

    • FunctionTolerance = 1e-10 - Задайте более строгий критерий остановки, чем обычно.

    • MaxGenerations = 300 - Разрешить больше поколений, чем по умолчанию.

    • PlotFcn = @gaplotbestfun - Наблюдайте за оптимизацией.

    opts = optimoptions('ga','MaxStallGenerations',50,'FunctionTolerance',1e-10,...
    'MaxGenerations',300,'PlotFcn',@gaplotbestfun);

  5. Установите нижнюю и верхнюю границы, чтобы помочь решателю:

    nVar = 5;
lb = -5*ones(1,nVar);
ub = 5*ones(1,nVar);

  6. Решите задачу:

    rng(0,'twister') % for reproducibility
[x,fval,exitflag] = ga(@ackleyfcn,nVar,[],[],[],[], ...
    lb,ub,@eqCon,[1 3 5],opts);
    Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance
and constraint violation is less than options.ConstraintTolerance.

  7. Исследуйте решение:

    x,fval,exitflag,norm(x)

x =

         0   -1.7367   -3.0000   -0.0000   -2.0000


fval =

    5.2303


exitflag =

     1


ans =

    4.0020

    Нечетная x компоненты являются целыми числами, как задано. Норма x является 4, в пределах заданной относительной погрешности 1e-3.

  8. Несмотря на положительный выходной флаг, решение не является глобальным оптимумом. Еще раз запустите задачу и исследуйте решение:

    opts = optimoptions('ga',opts,'Display','off');
[x2,fval2,exitflag2] = ga(@ackleyfcn,nVar,[],[],[],[], ...
    lb,ub,@eqCon,[1 3 5],opts);

    Исследуйте второе решение:

    x2,fval2,exitflag2,norm(x2)

    x2 =

   -2.0000    2.8930         0   -1.9095         0


fval2 =

    4.5520


exitflag2 =

     0


ans =

    4.0020

    Второй запуск дает лучшее решение (более низкое значение функции соответствия). Снова, нечетная x компоненты являются целыми числами и нормой x2 является 4, в пределах заданной относительной погрешности 1e-3.

Помните, что эта процедура может быть неудачной; ga испытывает трудности с одновременными целыми числами и ограничениями равенствами.

Эффективное целое число ga

Использовать ga наиболее эффективно при целочисленных задачах, следуйте этим рекомендациям.

  • Связать каждый компонент так плотно, как вы можете. Эта практика дает ga наименьшее пространство поиска, разрешающее ga наиболее эффективно искать.

  • Если вы не можете связать компонент, задайте соответствующую начальную область значений. По умолчанию ga создает начальную генеральную совокупность с областью значений [-1e4,1e4] для каждого компонента. Меньший или больший начальный область значений может дать лучшие результаты, когда значение по умолчанию неуместно. Чтобы изменить начальную область значений, используйте InitialPopulationRange опция.

  • Если у вас больше 10 переменных, задайте размер населения, который больше, чем по умолчанию, используя PopulationSize опция. Значение по умолчанию является 200 для шести или более переменных. Для большой численности населения:

    • ga может занять много времени, чтобы сойтись. Если вы достигаете максимального количества поколений (выходной флаг 0), увеличить значение MaxGenerations опция.

    • Уменьшите скорость мутации. Для этого увеличьте значение CrossoverFraction опция от ее значения по умолчанию 0.8 на 0.9 или выше.

    • Увеличьте значение EliteCount опция от ее значения по умолчанию 0.05*PopulationSize на 0.1*PopulationSize или выше.

Для получения информации об опциях смотрите ga options входной параметр.

Целое число ga Алгоритм

Целочисленное программирование с ga включает несколько модификаций базового алгоритма (см. «Как работает генетический алгоритм»). Для целочисленного программирования:

  • Специальные функции создания, кроссовера и мутации приводят переменные в исполнение как целые числа. Для получения дополнительной информации см. Deep et al. [2].

  • Генетический алгоритм пытается минимизировать штрафную функцию, а не функцию соответствия. Функция штрафа включает термин недопустимости. Эта функция штрафа сочетается с выбором двоичных турниров, чтобы выбрать индивидуумов для последующих поколений. Значение штрафной функции представителя из населения является:

    • Если представитель допустим, функция штрафа является функцией соответствия.

    • Если представитель недопустим, функция штрафа является максимально допустимой функцией соответствия среди допустимых представителей населения плюс сумма нарушений ограничений (недопустимых) точек.

    Для получения дополнительной информации о функции штрафа см. Deb [1].

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

Ссылки

[1] Дэб, Калянмой. Эффективный метод обработки ограничений для генетических алгоритмов. Компьютерные методы в прикладной механике и технике, 186 (2-4), стр. 311-338, 2000 .

[2] Deep, Kusum, Crishna Pratap Singh, M.L. Kansal, and C. Mohan. Действительный кодированный генетический алгоритм для решения целочисленных и смешанных целочисленных задач оптимизации. Прикладная математика и расчеты, 212 (2), стр. 505-518, 2009.

Похожие темы

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

Поддержка

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