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 компонента.
Этот пример показывает, как найти минимум функций Растригина, ограниченных, поэтому первый компонент x является целым числом. Компоненты x дополнительно ограничены в области .
Установите границы для вашей задачи
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 может решить, когда вы включаете целочисленные ограничения:
Нет линейных ограничений равенства. Должно быть, у вас есть 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. Без допуска нелинейное ограничение равенства никогда не выполняется, и решатель не понимает, когда у него есть возможное решение.
Напишите выражение 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(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.
Исследуйте решение:
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.
Несмотря на положительный выходной флаг, решение не является глобальным оптимумом. Еще раз запустите задачу и исследуйте решение:
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.