[БЕЗ_ЗВУКА] Давайте продолжим знакомиться с методами оптимизации. В этом видео мы будем обсуждать метод имитации отжига. Это один из методов глобальной оптимизации, которому совершенно не важно, обладает ли функция свойством гладкости, это один из вариантов случайного поиска, и также вы можете встретить его под названием «алгоритм Метрополиса» по имени автора. Алгоритм был придуман достаточно просто. Зачем нам самим выдумывать какой-то сложный алгоритм? Мы можем подсмотреть какую-то хорошую идею у природы. И вот действительно, есть такой хороший физический процесс, который наблюдается при отжиге металлов, в котором атомы оказываются в ситуации, когда они уже заняли какие-то свои положения в кристаллической решётке, но в то же время всё ещё возможны небольшие переходы из одной ячейки в другую. При этом температура падает, с падением температуры вероятность переходов тоже падает, ну и, кроме того, решётка стремится принять состояние, в котором энергия атомов будет минимальной. Ну то есть это некоторая естественная оптимизация, которую мы можем наблюдать в природе. Поэтому переходы атомов происходят тогда, когда энергия атомов от этого перехода уменьшится. Вот давайте и мы начнём в некоторой случайной точке, зададим начальное значение температуры и дальше попробуем как-то случайно выбрать следующую точку недалеко от предыдущей. Ну чтобы мы не выбивались слишком сильно из уже хороших найденных точек. Если эта точка подходит нам больше, то есть значение функции в ней меньше, если мы решаем задачу минимизации, то тогда сразу переходим в неё. Если же значение функции в этой точке больше, то мы всё равно можем перейти в неё, это обеспечит нам возможность выбираться из каких-то локальных минимумов, но давайте это делать с некоторой вероятностью, указанной на слайде. Обратите внимание: с ростом температуры эта вероятность становится всё меньше. После завершения шага давайте обновим значение температуры, уменьшив его, и будем продолжать шаги до тех пор, пока температура продолжает падать или пока мы не нашли хорошее решение, из которого никуда не уходим. Что мы ещё не обсуждали? Мы не обсуждали, как выбирать кандидата на роль следующей точки, мы просто сказали как-то «случайно», но не оговаривали дополнительно распределение. И мы не обсуждали, находит ли этот алгоритм минимум. Вы можете удивиться: «Ну что значит, находит или нет? Это же алгоритм оптимизации. В этом же его задача». На самом деле, когда мы говорим об алгоритмах оптимизации, не всегда подразумевается, что мы хотим найти именно минимум. Бывают ситуации, когда мы просто хотим найти значение функции поменьше, чем то, которое мы уже знаем. Ну и понятна практическая польза этого. Если мы, например, оптимизируем какую-нибудь рекламную кампанию или оптимизируем затраты на какой-нибудь процесс, понятно, что меньшие затраты — это тоже некоторый позитивный результат. И нам необязательно знать, что нельзя сделать ещё меньше. И вот оказывается, нахождение минимума и выбор следующей точки — достаточно тесно связанные между собой вещи. При некоторых способах выбора следующей точки можно гарантировать, что алгоритм уж по крайней мере будет находить какую-нибудь точку получше начального приближения (разумеется, если она есть). Реализацию метода имитации отжига вы можете взять в библиотеке SkiPy в модуле optimize функцию anneal. Подведём итог. Мы познакомились с методом имитации отжига, который вы можете использовать в случае, если нужно оптимизировать какую-то достаточно сложную и достаточно плохую функцию, для которой не получится применить градиентные методы.