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

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

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].

Примечание

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

Совет

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

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

Скрипт Open Live Script

Этот пример показывает, как найти минимум функции Рэстриджина ограниченным, таким образом, первый компонент x является целым числом. Компоненты x далее ограничиваются, чтобы быть в области $5 π \leq x (1) \leq 20 π, - 20 π \leq x (2) \leq - 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)

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 = []. Для возможного обходного решения не смотрите Ограничения Равенства.
Никакие нелинейные ограничения равенства. Любая нелинейная ограничительная функция должна возвратить [] для нелинейного ограничения равенства. Для возможного обходного решения смотрите Пример: Целочисленное программирование с Нелинейным Ограничением Равенства.
Только тип генеральной совокупности doubleVector.
Никакая пользовательская функция создания (опция CreationFcn), перекрестно соедините функцию (опция CrossoverFcn), функция мутации (опция MutationFcn), или начальные очки (опция InitialScoreMatrix). Если вы предоставляете какой-либо из них, ga заменяет их настройки.
ga использует только бинарную функцию выбора турнира (опция SelectionFcn) и заменяет любую другую установку.
Никакая гибридная функция. ga заменяет любую установку опции HybridFcn.
ga игнорирует ParetoFraction, DistanceMeasureFcn, InitialPenalty и опции PenaltyFactor.

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

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

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

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

3x1 – 2x2 = 5,

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

3x1 – 2x2 ≤ 5
3x1 – 2x2 ≥ 5.

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

– 3x1 + 2x2 ≤ –5.

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

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

Пример: Целочисленное программирование с Нелинейным Ограничением Равенства. Этот пример пытается определить местоположение минимума функции Ackley в пяти размерностях с этими ограничениями:

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

Функцию Ackley, описанную кратко в Возобновлении ga От Итоговой Генеральной совокупности, трудно минимизировать. Добавление целого числа и ограничений равенства увеличивает трудность.

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

Запишите выражению   norm(x) = 4 как два “меньше, чем нулевые” неравенства:
  norm(x) - 4 ≤ 0
  -(norm(x) - 4) ≤ 0.
Позвольте маленький допуск в неравенствах:
norm(x) - 4 - tol ≤ 0
-(norm(x) - 4) - tol ≤ 0.
Запишите нелинейную функцию ограничения неравенства, которая реализует эти неравенства:
```
function [c, ceq] = eqCon(x)

ceq = [];
rad = 4;
tol = 1e-3;
confcnval = norm(x) - rad;
c = [confcnval - tol;-confcnval - tol];
```
Установка опций:
- MaxStallGenerations = 50 — Позвольте решателю пробовать некоторое время.
- FunctionTolerance = 1e-10 — Задайте более строгий критерий остановки чем обычно.
- MaxGenerations = 300 — Позвольте больше поколений, чем значение по умолчанию.
- PlotFcn = @gaplotbestfun — Наблюдайте оптимизацию.
```
opts = optimoptions('ga','MaxStallGenerations',50,'FunctionTolerance',1e-10,...
    'MaxGenerations',300,'PlotFcn',@gaplotbestfun);
```
Установите нижние и верхние границы помогать решателю:
```
nVar = 5;
lb = -5*ones(1,nVar);
ub = 5*ones(1,nVar);
```

Решите проблему:

rng(1,'twister') % for reproducibility
[x,fval,exitflag] = ga(@ackleyfcn,nVar,[],[],[],[], ...
    lb,ub,@eqCon,[1 3 5],opts);

Optimization terminated: stall generations limit exceeded
and constraint violation is less than options.ConstraintTolerance.

Исследуйте решение:
```
x,fval,exitflag,norm(x)

x =

   -3.0000    0.8233    1.0000   -1.1503    2.0000


fval =

    5.1119


exitflag =

     3


ans =

    4.0001
```
Нечетные компоненты x являются целыми числами, как задано. Нормой x является 4, к в данном относительном допуске 1e-3.
Несмотря на положительный выходной флаг, решение не является глобальным оптимумом. Запустите проблему снова и исследуйте решение:
```
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 =

   -1.0000   -0.9959   -2.0000    0.9960    3.0000


fval2 =

    4.2359


exitflag2 =

     1


ans =

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

Эффективное целое число `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 или выше.

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

Целочисленный алгоритм `ga`

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

Специальное создание, перекрестное соединение и функции мутации осуществляют переменные, чтобы быть целыми числами. Для получения дополнительной информации смотрите Глубоко и др. [2].
Генетический алгоритм пытается минимизировать функцию штрафа, не функцию фитнеса. Функция штрафа включает термин для infeasibility. Эта функция штрафа объединена с бинарным выбором турнира, чтобы выбрать людей для последующих поколений. Значение функции штрафа члена генеральной совокупности:
- Если участник выполним, функция штрафа является функцией фитнеса.
- Если участник неосуществим, функция штрафа является максимальной функцией фитнеса среди выполнимых членов генеральной совокупности плюс сумма ограничительных нарушений (неосуществимой) точки.
Для получения дополнительной информации функции штрафа, смотрите Деб [1].
ga не осуществляет линейные ограничения, когда существуют целочисленные ограничения. Вместо этого ga включает линейные ограничительные нарушения в функцию штрафа.

Ссылки

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

[2] Глубоко, Kusum, Кришна Пратап Сингх, М.Л. Кэнсэл и К. Мохэн. Действительный закодированный генетический алгоритм для решения целого числа и смешанных целочисленных задач оптимизации. Прикладная математика и Вычисление, 212 (2), стр 505–518, 2009.

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