Комбинаторная оптимизация

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

Поиск оптимального решения в дискретном и конечном множестве — простая теоретическая задача: достаточно перепробовать все решения и сравнить их качества, чтобы выбрать лучшее. Однако комбинаторный взрыв возможных решений некоторых математических задач не позволяет получить решение за «человеческое» время.

Некоторые задачи комбинаторной оптимизации могут быть решены (точно) за полиномиальное время, например, с помощью алгоритма динамическое программирование или показав, что проблема может быть сформулирована как задача линейной оптимизации в реальных переменных. В большинстве случаев задача является Np-сложной и для ее решения необходимо использовать подходящие алгоритмы.

На практике физически приемлемая сложность часто бывает только полиномиальной. Тогда нас удовлетворяет наличие наилучшего приближенного решения, полученного с помощью эвристики или метаэвристики. Важно отметить, что некоторые из этих методов обеспечивают глобальные оптимумы, отличие от точных методов заключается в отсутствии каких-либо формальных доказательств (математических или доказательств окончательности) его глобальной оптимальности.

Дерево решений

То есть Е все решения проблем. Предполагается, что оно дискретно и конечно. Перечисление решений представлено дерево. Все элементы Е разделены на нет непересекающееся непустое подмножество, каждое из которых содержит часть множества решений. Например, множество можно разделить на два в задаче рюкзак независимо от того, берем ли мы элемент x_к в сумке.

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

Корень дерева Е, сыновья являются подмножествами и т. д. как показано на следующей диаграмме:

Методы решения

Точный

Эти методы дают гарантию найти оптимальное решение для экземпляра конечного размера за ограниченное время и доказать его оптимальность.

Эвристика

Когда сложность проблемы экспоненциальна или демонстрирует комбинаторный взрыв, рекомендуется использовать эвристики. Это метод, который быстро обеспечивает «хорошее» решение проблемы. Это приближенное решение может затем стать отправной точкой для использования точного метода (например, северо-западный угол в транспортной задаче). Все жадные и наивные алгоритмы являются эвристиками.

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

1. Качество результата: эвристика сталкивается с полученные результаты оптимальный для набора значений данной задачи (мы говорим об эталоне). Качество решения может быть либо расстоянием до оптимального решения, либо вероятностью его достижения.
2. Стоимость эвристики: сложность во времени и пространстве.
3. Область применения: область допустимости всех переменных.

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

Метаэвристика

Метаэвристика имеет более высокий уровень абстракции, чем эвристика, поскольку это методы, которые можно адаптировать к данной проблеме. Таким образом, методы могут быть применены к различным задачам (в виде черного ящика) без изменения их функционирования. Мы также говорим об общей эвристике.

Есть два вида метаэвристики: с населением (имеет) или в пути (б). Большинство алгоритмов не имеют определенной популяции, тогда можно использовать алгоритм для курса или популяции.

Оба типа работают с одним и тем же четырехэтапным процессом:

1. район : окрестность решения - это подмножество решений, достижимых преобразованием исходного решения (путем перестановки, расширения, изменения, исключения и т. д.).
2. Исследование : разведка состоит из сбора данных обо всей округе.
3. Операция : эксплуатация использует собранную информацию для определения «интересных» областей пространства поиска, образованных соседством.
4. Память : память учитывает обучение и позволяет определить области, в которых может быть глобальный оптимум. Если новые решения или критерии остановки больше не позволяют улучшить решение, алгоритм останавливается. В противном случае вернитесь к шагу 1. Некоторые алгоритмы работают только с критериями остановки, тогда мы говорим о метаэвристике без памяти.