Имитация отжига

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

. При этом среднее значение состояния нейрона также будет лежать в допустимом интервале

Положительная роль температуры заключается в том, что шум позволяет системе покидать локальные минимумы энергии и двигаться в сторону более глубоких энергетических минимумов. Соответствующий (не нейросетевой) алгоритм оптимизации был предложен в 1953 г. и получил название имитации отжига (Metropolis et al., 1953). Этот термин происходит от названия способа выжигания дефектов в кристаллической решетке. Атомы, занимающие в ней неправильное место, при низкой температуре не могут сместиться в нужное положение - им не хватает кинетической энергии для преодоления потенциального барьера. При этом система в целом находится в состоянии локального энергетического минимума. Для выхода из него металл нагревают до высокой температуре, а затем медленно охлаждают, позволяя атомам занять правильные положения в решетке, соответствующее глобальному минимуму энергии.

Субоптимальное решение некоторой задачи оптимизации, например, задачи коммивояжера, также может рассматриваться как решение в котором имеются дефекты - неправильные части маршрута. Лин и Кернигэн (Lin & Kernigan, 1973) ввели элементарные операции изменения текущего решения, такие как перенос (часть маршрута вырезается и вставляется в другое место) и обращение (выбирается фрагмент маршрута и порядок прохождения городов в нем меняется на обратный). При применении одной из этих операций происходит изменение маршрута с

на

, и значение минимизируемого функционала меняется на

. В соответствии с принципами термодинамики, это изменение принимается с вероятностью

где

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

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

Содержание раздела