Глобальная оптимизация — это ветвь исследования операций, прикладной математики и численных методов, целью которой является поиск глобального минимума или максимума функции или набора функций на заданном множестве. Обычно она описывается как задача минимизации, поскольку максимизация вещественнозначной функции эквивалентна минимизации функции .
Если дана возможно нелинейная и невыпуклая непрерывная функция с глобальным минимумом и множеством всех глобальных минимизаторов в , стандартная задача может быть задана как
То есть, нахождение и глобального минимизатора в , где компактное (не обазательно выпуклое) множество, заданное неравенством .
Глобальная оптимизация отличается от локальной оптимизации тем, что фокусируется на поиске минимума или максимума на заданном множестве, в отличие от поиска локального минимума или максимума. Найти произвольный локальный минимум относительно просто, используя классические методы локальной оптимизации. Поиск глобального минимума функции является гораздо более сложной задачей — аналитические методы часто неприменимы, а применение численных стратегий решения нередко порождает весьма трудные проблемы.
Приложения Типичными примерами глобальной оптимизации являются: Предсказание структуры белка (минимизация функции энергии/свободной энергии) Вычислительная филогенетика (например, минимизация числа изменений признаков в дереве) Задача коммивояжёра и проектирование электрических цепей (минимизация длины пути) Химическая технология (например, анализ энергии Гиббса) Оценка безопасности, техника безопасности (например, механических конструкций, зданий)
Математические задачи (например, гипотеза Кеплера) Задачи упаковки объектов Начальная стадия многих моделирований молекулярной динамики состоит из первоначальной оптимизации энергии моделируемой системы. Спиновые стёкла Калибровка моделей распространения радиоволн и многих других моделей в науке и технике Подбор кривых, таких как и другие обобщения, используемые для подгонки параметров модели к экспериментальным данным в химии, физике, биологии, экономике, финансах, медицине, астрономии и инженерии. Планирование лучевой терапии с модуляцией интенсивности (IMRT)
Детерминированные методы
Наиболее успешные общие точные стратегии:
Внутренняя и внешняя аппроксимация В обеих этих стратегиях множество, над которым должна быть оптимизирована функция, аппроксимируется [полиэдр]ами (многомерными многогранниками). При внутренней аппроксимации полиэдры содержатся во множестве, тогда как при внешней аппроксимации полиэдры содержат множество.
Методы отсекающих плоскостей
Метод отсекающих плоскостей — это собирательный термин методов оптимизации, которые итеративно исправляют область допустимых решений или целевую функцию с помощью линейных неравенств, называемых отсечениями. Такие процедуры широко используются для нахождения целочисленных решений задач смешанного целочисленного линейного программирования, а также для решения общих, не обязательно дифференцируемых задач выпуклой оптимизации. Применение отсекающих плоскостей для решения задач смешанного целочисленного линейного программирования предложили Ральф Гомори и Вацлав Хватал.
Метод ветвей и границ
Метод ветвей и границ — это парадигма разработки алгоритма для дискретных и комбинаторнвых задач оптимизации. Алгоритм ветвей и границ состоит из систематического перечисления возможных решений, используя поиск в пространстве состояний. Множество потенциальных решений представляется в виде корневого дерева, где корень соответствует полному набору. Алгоритм исследует ветви этого дерева, которые представляют подмножества решений. Прежде чем перечислять возможные решения в конкретной ветви, она проверяется на соответствие верхним и нижним оценочным границам оптимального решения. Если ветвь не может дать решение лучше, чем лучшее из найденных алгоритмом на данный момент, она отбрасывается.
Интервальные методы
Интервальная арифметика, интервальная математика, интервальный анализ или интервальные вычисления — это метод , разработанный математиками в 1950-х и 1960-х годах как попытка установить границы ошибок округления и погрешностей измерения в математических вычислениях, тем самым создавая численные методы, дающие надёжные результаты. Интервальная арифметика помогает находить достоверные и гарантированные решения уравнений и задач оптимизации.
Методы на основе вещественной алгебраической геометрии
Вещественная алгебра — это раздел алгебры, имеющий отношение к вещественной алгебраической (и полуалгебраической) геометрии. Она в основном занимается изучением упорядоченных полей и упорядоченных колец (в частности, ) и их применением к исследованию положительных многочленов и . Её можно использовать в выпуклой оптимизации.
Стохастические методы
Существует несколько точных или неточных алгоритмов на основе метода Монте-Карло:
Прямая выборка Монте-Карло
В этом методе для поиска приближ`нного решения используются случайное моделирование.
Пример: Задача коммивояжёра, стандартная задача оптимизации. То есть, все необходимые для определения оптимального маршрута данные (расстояния между пунктами назначения) известны с абсолютной точностью, а цель состоит в переборе всех возможных вариантов перемещения для нахождения маршрута, который обеспечит наименьшее общее расстояние. Однако, предположим, что вместо минимизации общего пройденного расстояния для посещения всех желаемых пунктов, мы хотим минимизировать общее время для достижения каждого из них. Это выходит за рамки стандартной оптимизации, поскольку время в пути по своей природе точно не определено (пробки, время суток и т.д.). Как результат, для получения оптимального маршрута нам потребуется использовать имитационное моделирование с оптимизацией. Сначала мы поймем диапазон возможных времён, которые могут потребоваться для перемещения из одной точки в другую (в данном случае представленный вероятностным распределением, а не конкретным расстоянием) а затем оптимизируем наши решения о перемещении, чтобы определить наилучший маршрут, учитывая эту неопределённость.
Стохастическое туннелирование
Стохастическое туннелирование — это подход к глобальной оптимизации, основанный на методе Монте-Карло с дискретизацией минимизируемой функции. Функция нелинейно преобразуется, чтобы облегчить «туннелирование» между областями, содержащими минимумы функции. Такое облегчённое туннелирование ускоряет исследование пространства выборки и способствует более быстрому нахождению хорошего решения.
Параллельный отжиг
Параллельный отжиг, известный также как параллельные цепи с обменом () , — это метод имитации разработанный для улучшения динамических свойств моделирования методом Монте-Карло физических систем, а также более общих методов выборки марковских цепей Монте-Крло (МцМК). Метод обмена реплик был первоначально предложен Сведсеном, затем его расширил Гейер и развил позднее, среди прочих, Джорджо Паризи. Сугита и Окамото сформулировали версию параллельного отжига на основе молекулярной динамики, эта версия известна как молекулярная динамика с реплик-обменом.
Суть метода заключается в следующем: запускается N копий системы, каждая с произвольной начальной конфигурацией, при разных температурах. Затем, используя критерий Метрополиса, происходит обмен конфигурациями между системами с различными температурами. Идея метода — сделать конфигурации, полученные при высоких температурах, доступными для моделирования при низких температурах, и наоборот. Это приводит к очень устойчивому ансамблю, способному эффективно исследовать как низкоэнергетические, так и высокоэнергетические конфигурации. Таким образом, термодинамические свойства, например, теплоёмкость, которая обычно плохо рассчитывается в каноническом ансамбле, могут быть вычислены с высокой точностью.
Эвристика и метаэвристика
Другие подходы включают эвристические стратегии для более или менее интеллектуального поиска в пространстве поиска, в том числе: Алгоримт муравьиной колонии Алгоритм имитации отжига, общая вероятностная метаэвристика Поиск с запретами, расширение локального поиска способное выходить из локальных минимумов Эволюционные алгоритмы (например, генетические алгоритмы и эволюционные стратегии) Дифференциальная эволюция, метод, который оптимизирует задачу путём итеративного улучшения решения-кандидата относительно заданной меры качества Оптимизация на основе роевого интеллекта (например, оптимизация роем частиц, и алгоритм муравьиной колонии) Меметические алгоритмы, сочетающие глобальные и локальные стратегии поиска Реактивная оптимизация поиска (то есть интеграция субсимвольных методов машинного обучения в эвристику поиска) Постепенная оптимизация, которая пытается решить сложную задачу оптимизации, сначала решая значительно упрощенную задачу, а затем постепенно трансформируя эту задачу (в процессе оптимизации) до тех пор, пока она не станет эквивалентной исходной сложной задаче.
Подходы, основанные на методологии поверхности отклика Косвенная оптимизация , основанная на самоорганизации Байесовская оптимизация, последовательная стратегия для глобальной оптимизации функций «чёрного ящика» с использованием байесовской статистики
См. также Многокритериальная оптимизация Оптимизация (математика)
Примечания
Литература
Детерминированная глобальная оптимизация:
В настоящее время распространяется компанией Springer Science and Business Media, Нью-Йорк. Эта книга также обсуждает стохастические методы глобальной оптимизации.
Для имитации отжига:
Для оптимизации реактивного поиска:
Для стохастических методов:
Для параллельного отжига:
Для методов продолжения:
Для общих соображений о размерности области определения целевой функции:
Ссылки A. Neumaier’s page on Global Optimization Introduction to global optimization by L. Liberti Free e-book by Thomas Weise
Категория:Теория оптимизации