Глобальная оптимизация

1.

ГЛОБАЛЬНАЯ ОПТИМИЗАЦИЯ

2.

ПОНЯТИЕ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ
В широком смысле, глобальная оптимизация — это
поиск состояния некоторой системы (технической,
производственной, бизнес-системы), который
обеспечит её наилучшее функционирование
(максимизирует прибыль, минимизирует
издержки), а также комплекс мероприятий,
направленных на достижение этого состояния.
В анализе данных глобальная оптимизация — это
раздел прикладной математики и численного
анализа, который занимается проблемами
поиска глобальных экстремумов функций. В
большинстве случаев решается задача
минимизации, поскольку максимизация
эквивалентна поиску обратного функционала для
задачи минимизации.

3.

МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА

4.

МЕТОДЫ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ
Глобальная оптимизация намного сложнее,
чем локальная, поскольку аналитические методы
неприменимы, а численные в большинстве
случаев приводят к очень сложным решениям.
Методы глобальной оптимизации делятся на:
детерминированные — линейное и нелинейное
программирование, алгебраические методы,
метод ветвей и границ и др.;
стохастические — методы Монте-Карло;
эвристические — алгоритм муравьиной
колонии, эволюционные алгоритмы, метод роя
частиц и др.

5.

ДЕТЕРМИНИРОВАННЫЕ МЕТОДЫ
Внутреннее и внешнее приближение В обеих этих стратегиях набор, по
которому должна быть оптимизирована функция, аппроксимируется
многогранниками. Во внутреннем приближении многогранники содержатся в
множестве, а во внешнем приближении многогранники содержат множество.
Методы секущей плоскости Метод секущей плоскости является общим
термином для методов оптимизации, которые итеративно уточняют допустимый
набор или целевую функцию с помощью средства линейных неравенств,
называемые разрезами. Такие процедуры обычно используются для поиска
целочисленных решений задач смешанного целочисленного линейного
программирования (MILP), а также для решения общих, не обязательно
дифференцируемых задач выпуклой оптимизации .
Методы ветвления и границы Ветвление и граница (BBили B&B ) - это
парадигма проектирования алгоритма для дискретных и задач комбинаторной
оптимизации . Алгоритм ветвей и границ состоит из систематического
перечисления возможных решений с помощью поиска в пространстве состояний
: набор возможных решений рассматривается как формирование корневого
дерева с полным установить в корень. Алгоритм исследует ветви этого дерева,
которые представляют собой подмножества множества решений. Перед
перечислением возможных решений ветви, ветвь проверяется на соответствие
верхней и нижней оценкам оптимального решения и отбрасывается, если она не
может дать лучшее решение, чем лучшее, найденное алгоритмом на данный
момент

6.

ДЕТЕРМИНИРОВАННЫЕ МЕТОДЫ
Интервальная арифметика , интервальная
математика , интервальный анализ или интервальное
вычисление - это метод, разработанный математики с
1950-х и 1960-х годов как подход к ограничению ошибок
округления и ошибок измерения в математических
вычислениях и, таким образом, разработки численных
методов дающие надежные результаты. Интервальная
арифметика помогает находить надежные и
гарантированные решения уравнений и задач
оптимизации.
Методы, основанные на реальной алгебраической
геометрии. Реальная алгебра - это часть алгебры,
имеющая отношение к реальной алгебраической (и
полуалгебраической) геометрии. В основном это связано
с изучением упорядоченных полей и упорядоченных
колец (в частности, вещественных замкнутых полей ) и
их приложений к изучению положительных
многочленов. и суммы квадратов многочленов . Его
можно использовать в выпуклой оптимизации

7.

СТОХАСТИЧЕСКИЕ МЕТОДЫ
Прямая выборка Монте-Карло
В этом методе для поиска приближенного решения используется
случайное моделирование. Пример: задача коммивояжера - это то,
что называется обычной задачей оптимизации. То есть все факты
(расстояния между каждой точкой назначения), необходимые для
определения оптимального пути, по которому следует следовать,
известны с уверенностью, и цель состоит в том, чтобы просмотреть
возможные варианты путешествия, чтобы найти путь с
наименьшим общим расстоянием. Однако давайте предположим,
что вместо того, чтобы минимизировать общее расстояние,
пройденное для посещения каждого желаемого пункта
назначения, мы хотели минимизировать общее время,
необходимое для достижения каждого пункта назначения. Это
выходит за рамки обычной оптимизации, поскольку время в пути
по своей сути неопределенно (пробки, время суток и т. Д.). В
результате, чтобы определить наш оптимальный путь, мы хотели
бы использовать моделирование - оптимизацию, чтобы сначала
понять диапазон потенциального времени, которое может
потребоваться, чтобы перейти от одной точки к другой
(представленной в данном случае распределением вероятностей, а
не конкретным расстоянием). а затем оптимизировать наши
решения о поездках, чтобы определить лучший путь, по которому
следует идти, с учетом этой неопределенности.

8.

СТОХАСТИЧЕСКИЕ МЕТОДЫ
Стохастическое туннелирование
Стохастическое туннелирование (STUN) - это подход к глобальной оптимизации,
основанный на методе Монте-Карло - выборке функции, которая будет
объективно минимизированный, в котором функция нелинейно преобразуется,
чтобы упростить туннелирование между областями, содержащими минимумы
функции. Более простое туннелирование позволяет быстрее исследовать
пространство для образца и быстрее найти хорошее решение.

9.

СТОХАСТИЧЕСКИЕ МЕТОДЫ
Параллельный отпуск
Параллельный отпуск , также известный как выборка MCMC с
обменом реплик , представляет собой метод моделирования ,
направленный на улучшение динамических свойств Метод МонтеКарло в целом. Метод обмена репликами был первоначально
разработан Свендсеном, затем расширен Гейером и позже разработан,
среди прочего, Джорджио Паризи . Сугита и Окамото
сформулировали молекулярную динамику версию параллельного
темперирования: это обычно известно как молекулярная динамика с
обменом реплик или REMD. По сути, запускается N копий системы,
инициализированных случайным образом, при разных температурах.
Затем, исходя из критерия Метрополиса, происходит обмен
конфигурациями при разных температурах. Идея этого метода состоит
в том, чтобы сделать конфигурации при высоких температурах
доступными для моделирования при низких температурах и наоборот.
В результате получается очень надежный ансамбль, который может
выполнять выборку конфигураций как с низкой, так и с высокой
энергией. Таким образом, термодинамические свойства, такие как
удельная теплоемкость, которая, как правило, плохо вычисляется в
каноническом ансамбле, могут быть вычислены с большой точностью.

10.

ЭВРИСТИКА И МЕТАЭВРИСТИКА
В информатике и математической оптимизации метаэвристика -
это процедура более высокого уровня или эвристика ,
предназначенная для поиска, генерации или выбора эвристики
(частичный алгоритм поиска ), которая может обеспечивают
достаточно хорошее решение проблемы оптимизации , особенно с
неполной или несовершенной информацией или ограниченной
вычислительной мощностью.
Метаэвристика выбирает подмножество решений, которое в
противном случае было бы слишком большим, чтобы его можно
было полностью перечислить или исследовать иным образом.
Метаэвристика может делать относительно мало
предположений о решаемой задаче оптимизации и поэтому
может использоваться для множества задач.
По сравнению с алгоритмами оптимизации и итерационными
методами , метаэвристика не гарантируют, что глобально
оптимальное решение может быть найдено для некоторого класса
проблем. Многие метаэвристики реализуют ту или иную форму
стохастической оптимизации , так что найденное решение
зависит от сгенерированного набора случайных величин .

11.

ГИБРИДИЗАЦИЯ И МЕМЕТИЧЕСКИЕ
АЛГОРИТМЫ
Гибридная метаэвристика - это метод, который
объединяет метаэвристику с другими подходами к
оптимизации, такими как алгоритмы из
математического программирования ,
программирования ограничений и машинное
обучение . Оба компонента гибридной
метаэвристики могут работать одновременно и
обмениваться информацией, чтобы направлять
поиск.С другой стороны, меметические алгоритмы
представляют собой синергию эволюционного или
популяционного подхода с отдельными
процедурами индивидуального обучения или
локального улучшения для поиска проблем.
Пример меметического алгоритма - использование
алгоритма локального поиска вместо базового
оператора мутации в эволюционных алгоритмах.

12.

ПАРАЛЛЕЛЬНАЯ МЕТАЭВРИСТИКА
параллельная метаэвристика - это
метаэвристика, использующая методы
параллельного программирования для
параллельного выполнения нескольких
метаэвристических поисков; они могут
варьироваться от простых схем
распределенных до параллельных поисковых
прогонов, которые взаимодействуют друг с
другом для улучшения общего решения.

13.

МЕТАЭВРИСТИКА НА ОСНОВЕ ПРИРОДЫ
И МЕТАФОР
Очень активная область исследований - это разработка
метаэвристики, вдохновленной природой. Многие
недавние метаэвристики, особенно алгоритмы,
основанные на эволюционных вычислениях,
вдохновлены естественными системами. Природа
выступает в качестве источника концепций, механизмов
и принципов для проектирования искусственных
вычислительных систем для решения сложных
вычислительных задач. Такие метаэвристики включают
в себя моделирование отжига , эволюционные
алгоритмы , оптимизацию муравьиной колонии и
оптимизацию роя частиц . Большое количество более
поздних метаэвристических методов, основанных на
метафорах, начали привлекать критику в
исследовательском сообществе за то, что они скрывали
отсутствие новизны за сложной метафорой.

14.

МЕТАЭВРИСТИКА НА ОСНОВЕ ПРИРОДЫ
И МЕТАФОР
Очень активная область исследований - это разработка
метаэвристики, вдохновленной природой. Многие
недавние метаэвристики, особенно алгоритмы,
основанные на эволюционных вычислениях,
вдохновлены естественными системами. Природа
выступает в качестве источника концепций, механизмов
и принципов для проектирования искусственных
вычислительных систем для решения сложных
вычислительных задач. Такие метаэвристики включают
в себя моделирование отжига , эволюционные
алгоритмы , оптимизацию муравьиной колонии и
оптимизацию роя частиц . Большое количество более
поздних метаэвристических методов, основанных на
метафорах, начали привлекать критику в
исследовательском сообществе за то, что они скрывали
отсутствие новизны за сложной метафорой.

15.

ПРИЛОЖЕНИЯ МЕТАЭВРИСТИЧЕСКИХ
АЛГОРИТМОВ
Метаэвристика используется для комбинаторной оптимизации , в
которой оптимальное решение ищется в дискретном пространстве
поиска . Примером проблемы является задача коммивояжера , где
пространство поиска возможных решений растет быстрее, чем ,
экспоненциально по мере увеличения размера задачи, что делает
исчерпывающий поиск для оптимального решения неосуществимо.
Кроме того, многомерные комбинаторные проблемы, включая
большинство проблем проектирования в инженерии , таких как
поиск формы и поведение, страдают от проклятия размерности ,
что также делает их невозможными для исчерпывающего поиска
или аналитические методы .
Метаэвристика также широко используется для планирования
работы цехов и задач выбора работы. Популярные метаэвристики
для комбинаторных задач включают моделирование отжига
Киркпатрика и др., генетические алгоритмы Холланда и др.,
Поиск по разбросу и запретный поиск Гловера.

16.

АЛГОРИМЫ МЕТАЭВРИСТИКИ
Оптимизация колонии муравьев (ACO)
Моделирование отжига , обобщенная вероятностная метаэвристика
Табу-поиск , расширение локального поиска , способное выходить из
локальных минимумов
Эволюционные алгоритмы (например, генетические алгоритмы и
стратегии эволюции ) Дифференциальная эволюция , метод, который
оптимизирует проблему, итеративно пытаясь улучшить возможное
решение в отношении данного показателя качестваалгоритмы
оптимизации на основе роя (например, оптимизация роя частиц ,
социальная когнитивная оптимизация , оптимизация множества роя и
оптимизация колонии муравьев )
Меметические алгоритмы , объединяющие стратегии глобального и
локального поиска
Оптимизация реактивного поиска (т.е. интеграция субсимвольных
методов машинного обучения в поисковую эвристику) Постепенная
оптимизация , метод, который пытается решить сложную проблему
оптимизации путем первоначального решения значительно упрощенной
задачи и постепенного преобразования этой проблемы (при оптимизации)
до тех пор, пока эквивалентно сложной задаче оптимизации.

17.

ПОДХОДЫ НА ОСНОВЕ МЕТОДОЛОГИИ
ПОВЕРХНОСТИ ОТКЛИКА
IOSO Косвенная оптимизация на основе
самоорганизации
Байесовская оптимизация , стратегия
последовательного проектирования для
глобальной оптимизации функций черного
ящика с использованием байесовской
статистики

18.

IOSO (КОСВЕННАЯ ОПТИМИЗАЦИЯ НА
ОСНОВЕ САМООРГАНИЗАЦИИ )
Технология IOSO основана на ответе s Методология urface подход. На
каждой итерации IOSO внутренне построенная модель поверхности
отклика для цели оптимизируется в пределах текущей области
поиска. За этим шагом следует прямой вызов реальной
математической модели системы для определения оптимальной
точки, полученной в результате оптимизации модели внутренней
поверхности отклика. Во время работы IOSO информация о
поведении системы сохраняется для точек в окрестности экстремума,
так что модель поверхности отклика становится более точной для
этой области поиска.
При переходе от одной итерации IOSO к другой выполняются
следующие шаги:
изменение плана эксперимента;
адаптивная настройка текущей области поиска; выбор типа
функции (глобальный или средний диапазон) для модели
поверхности отклика;
настройка модели поверхности отклика;
модификация как параметров, так и структуры алгоритмов
оптимизации; при необходимости,
выбор новых перспективных точек в области поиска.

19.

БАЙЕСОВСКАЯ ОПТИМИЗАЦИЯ
Поскольку целевая функция неизвестна, байесовская
стратегия состоит в том, чтобы рассматривать ее как
случайную функцию и помещать перед ней
предшествующий . Априор фиксирует представления о
поведении функции. После сбора оценок функции, которые
обрабатываются как данные, априорное значение
обновляется для формирования апостериорного
распределения по целевой функции. Апостериорное
распределение, в свою очередь, используется для
построения функции сбора данных (часто также
называемой критерием выборки заполнения), которая
определяет следующую точку запроса.
Существует несколько методов, используемых для
определения априорного / апостериорного распределения по
целевой функции. Два наиболее распространенных метода
используют гауссовские процессы в методе, называемом
кригинг . Другой менее затратный метод использует
оценщик дерева Парзена для построения двух
распределений для «высокой» и «низкой» точек, а затем
находит место, которое максимизирует ожидаемое
улучшение.

20.

МЕТОДЫ
ИМИТАЦИИ
ОТЖИГА

21.

ФИЗИЧЕСКИЕ ОСНОВЫ МЕТОДА
За основу взят процесс кристаллизации вещества, который
в свою очередь «приручили» хитрые металлурги, для
повышения однородности металла. У каждого металла
есть кристаллическая решетка, Совокупность позиций
всех атомов будем называть состоянием системы, каждому
состоянию соответствует определенный уровень энергии.

22.

Цель отжига – привести систему в состояние с
наименьшей энергией. Чем ниже уровень энергии,
тем «лучше» кристаллическая решетка, т.е. тем
меньше у нее дефектов и прочнее металл. В ходе
«отжига» металл сначала нагревают до некоторой
температуры, что заставляет атомы
кристаллической решетки покинуть свои позиции.
Затем начинается медленное и контролируемое
охлаждение. Атомы стремятся попасть в состояние
с меньшей энергией, однако, с определенной
вероятностью они могут перейти и в состояние с
большей. Эта вероятность уменьшается вместе с
температурой. Переход в худшее состояние, как ни
странно, помогает в итоге отыскать состояние с
энергией меньшей, чем начальная. Процесс
завершается, когда температура падает до заранее
заданного значения.

23.

СВОЙСТВА МЕТАЭВРИСТИК
Метаэвристика - это стратегии, которые
направляют процесс поиска.
Цель состоит в том, чтобы эффективно
исследовать пространство поиска, чтобы найти
почти оптимальные решения.
Методы, составляющие метаэвристические
алгоритмы, варьируются от простой локальный
поиск процедуры для сложных процессов
обучения.
Метаэвристические алгоритмы являются
приблизительными и обычно
недетерминированными.
Метаэвристика не связана с конкретной
проблемой.

24.

25.

Цель достигается за счет принятия не только
изменений параметров, приводящих к
уменьшению значения функции, но и некоторых
изменений, увеличивающих ее значение, в
зависимости от т.н. температуры характеристики
моделируемого процесса. Чем выше температура,
тем больше “ухудшающие” изменения допустимы,
и больше их вероятность.
В условиях нехватки вычислительных ресурсов для
нахождения глобального минимума, метод отжига,
как правило, выдает весьма неплохое решение. Л.
Ингбером показано, что метод отжига и его
модификации являются одним из наиболее
эффективных методов случайного поиска
оптимального решения для большого класса задач.
К настоящему времени разработано множество
различных вариантов метода отжига, как общих
так и их специализаций для конкретных задач.

26.

Пороговые алгоритмы
Алгоритм имитации отжига относится к классу пороговых алгорит
мов. На каждом шаге в окрестности текущего решения