Metal Gear

Метод моделирования отжига представляет собой еще о,іщн простой и относительно эффективный метод поиска решения задачи оптимизации. В отличие от предыдущих методов, в этом методе не учитываются градиенты, хотя на практике для повышения эффективности метода может использоваться информация о наклоне кривой.
Метод моделирования отжига разработан по аналогии с физическим процессом, который происходит в структуре металла во время медленного охлаждения (в ходе этого кристаллическая решетка металла принимает форму, характеризующуюся наличием в ней минимального запаса энергии). Этот процесс называется отжигом^ а его моделирование позволяет решать задачи оптимизации; отсюда и название метода — моделирование отжига.
Концептуально этот метод основан на случайном выборе. Дело в том, что в процессе решения задачи оптимизации выбор следующей итерации всегда остается не обоснованным до конца (поскольку глобальный минимум пока еще остается неизвестным). При этом такое положение сохраняется независимо от того, насколько хорошо изучена нами функция к текущему моменту (поскольку решение еще не найдено). Так почему бы не ввести сознательно в этот процесс элемент случайности, чтобы избавиться от проблем обоснованного выбора значения следующего шага? В методе моделирования отжига такая задача решается с помощью механизма случайной выработки следующего шага, который стохастически выбирает новую оценку в окрестностях текущей оценки. Применяемый механизм случайной выработки следующего шага зависит от типа оптимизируемых переменных, поскольку для успешной выработки оценок в окрестности необходимо обладать знаниями об используемом представлении. В случае применения вещественных чисел такая выработка оценок может осуществляться с применением случайных смещений (т.е. путем суммирования текущего значения и небольшого приращения).
При отжиге металла температура уменьшается вначале относительно быстро, а затем относительно медленно. Так же происходит изменение шага в методе моделирования отжига. Если новая оценка шага лучше, то всегда используется именно она, а не текущая оценка. С другой стороны, если применение новой оценки приводит к худшим результатам, то решение о том, следует ли ее использовать, принимается с учетом температуры. В методе моделирования отжига температурой называется величина, обозначаемая как т, от которой зависит вероятность р принятия положительного изменения Af в функции f при осуществлении новой оценки:
р = exp(-j^)
Приведенное выше уравнение известно под названием распределения Больцмана. В этом уравнении к представляет собой константу, позволяющую изменять масштаб представления температуры. Процедуру постепенного снижения температуры принято называть графиком охлаждения. На практике применение алгоритма моделирования отжига начинается с очень высоких значений температуры, которые постепенно снижаются. Теория, лежащая в основе метода моделирования отжига, показывает, что процесс оптимизации в ходе снижения температуры должен достичь глобального минимума.
Метод моделирования отжига имеет ряд преимуществ и недостатков; в некоторых случаях этот метод может действовать успешно при оптимизации функций, но в других случаях он может характеризоваться чрезвычайно низким быстродействием, которое обусловлено стохастическим характером данного метода. Одним из наиболее существенных критических замечаний в ащ)ес метода моделирования отжига является то, что он по существу представляет собой жадный метод восхождения к вершине (т.е. принимающий первое же из наиболее пощхоцмщих значений), при котором вероятность р = О (иными
словами, в методе моделирования отжига всегда выбираются лучшие из соседних значений). Учитывая указанные недостатки, можно понять, почему так важен правильный выбор графика охлаждения и по каким причинам до сих пор моделирование отжига остается областью, в которой могут преуспеть лишь специалисты, познавшие некоторые скрытые от посторонних закономерности.