Алгоритмы нелинейного решателя ограничений

Дополненный Лагранжианский Генетический Алгоритм

По умолчанию генетический алгоритм использует Дополненный Лагрангианский Генетический Алгоритм (ALGA), чтобы решить нелинейные ограниченные задачи без целочисленных ограничений. Задача оптимизации, решенная алгоритмом ALGA,

$\min_{x} f (x)$

таким, что

$\begin{matrix} c_{i} (x) \leq 0, i = 1 \dots m \\ c e q_{i} (x) = 0, i = m + 1 \dots m t \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b, \end{matrix}$

где c (x) представляет нелинейные ограничения неравенства, ceq (x) представляет ограничения равенства, m является количеством нелинейных ограничений неравенства, и mt является общим количеством нелинейных ограничений.

Augmented Lagrangian Genetic Algorithm (ALGA) пытается решить нелинейную задачу оптимизации с нелинейными ограничениями, линейными ограничениями и границами. В этом подходе ограничения и линейные ограничения обрабатываются отдельно от нелинейных ограничений. Подпрограмма сформулирована путем объединения функции соответствия и нелинейной ограничительной функции с помощью параметров Лагранжа и штрафа. Последовательность таких задач оптимизации приблизительно минимизируется с помощью генетического алгоритма, так что выполняются линейные ограничения и ограничения.

Формулировка подформулировка задачи определяется как

$Θ (x, λ, s, ρ) = f (x) - \sum_{i = 1}^{m} λ_{i} s_{i} \log (s_{i} - c_{i} (x)) + \sum_{i = m + 1}^{m t} λ_{i} c e q_{i} (x) + \frac{ρ}{2} \sum_{i = m + 1}^{m t} c e q_{i} {(x)}^{2},$

где

Компоненты _λi векторных λ неотрицательны и известны как оценки множителя Лагранжа
Элементы _si векторных s являются неотрицательными сдвигами
ρ является положительным параметром штрафа.

Алгоритм начинается с использования начального значения для параметра штрафа (InitialPenalty).

Генетический алгоритм минимизирует последовательность подпрограмм, каждая из которых является приближением исходной задачи. Каждая подпрограмма имеет фиксированное значение λ, s и ρ. Когда подпрограмма минимизируется до необходимой точности и удовлетворяет условиям выполнимости, оценки Лагранжа обновляются. В противном случае параметр штрафа увеличивается на коэффициент штрафа (PenaltyFactor). Это приводит к новой формулировке подформулировки задачи и проблеме минимизации. Эти шаги повторяются до тех пор, пока не будут достигнуты критерии остановки.

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

Выберите алгоритм Аугментированного Лагранжа путем установки NonlinearConstraintAlgorithm опция для 'auglag' использование optimoptions.

Полное описание алгоритма смотрите в следующих ссылках:

Ссылки

[1] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. Глобально сходимый дополненный алгоритм Лагранжа для оптимизации с общими ограничениями и простыми границами, SIAM Journal по численному анализу, том 28, номер 2, страницы 545-572, 1991.

[2] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. «Глобально сходимый дополненный лагрангийский барьерный алгоритм для оптимизации с общими ограничениями неравенства и простыми границами», Математика расчетов, том 66, число 217, страницы 261-288, 1997.

Алгоритм штрафа

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

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

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

Выберите алгоритм штрафа путем установки NonlinearConstraintAlgorithm опция для 'penalty' использование optimoptions. Когда вы делаете этот выбор, ga решает ограниченную задачу оптимизации следующим образом.

ga по умолчанию - @gacreationnonlinearfeasible функция создания. Эта функция пытается создать допустимое население относительно всех ограничений. ga создает достаточное количество индивидуумов, чтобы соответствовать PopulationSize опция. Для получения дополнительной информации смотрите Алгоритм штрафа.
ga переопределяет выбор функции выбора и использует @selectiontournament с двумя индивидуумами на турнир.
ga протекает в соответствии с How the Genetic Algorithm Works, используя функцию штрафа в качестве меры соответствия.

Ссылки

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

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