Имитация отжига
В конце 1970-х – начале 1980-х годов Скотт Киркпатрик считался физиком, а не специалистом в области информатики. В частности, его интересовала статистическая физика, в которой случайностью объяснялись некоторые явления природы, например физика отжига – то, как материалы меняют свое состояние в процессе нагрева или охлаждения. Пожалуй, самой интересной характеристикой отжига является скорость охлаждения вещества, которая оказывает огромное влияние на его конечную структуру. Как писал Киркпатрик:
Выращивание монокристалла из расплава происходит путем аккуратного отжига, когда вещество сперва расплавляют, а затем медленно понижают температуру, долгое время удерживая ее в области точки замерзания. Если этого не сделать и позволить веществу выйти из равновесного состояния, то у полученного кристалла будет множество дефектов или вещество вовсе превратится в стекло без какой-либо кристаллической структуры.
Киркпатрик в то время работал в компании IBM, где самой сложной и важной проблемой было нанесение электросхем на чипы, производимые компанией. Проблема была громоздкой и труднорешаемой: существовало множество путей решения, и при этом имелись некоторые сложные ограничения. Так, например, в общем и целом стоило располагать элементы близко друг к другу, но не слишком, чтобы оставалось место для соединения. И каждый раз, как что-то сдвигалось, приходилось по новой рассчитывать, как все соединения будут работать при гипотетическом новом расположении.
В те времена процессом руководил своего рода тайный гуру компании IBM. Киркпатрик вспоминает: «Тот парень мог напихать на чип больше всего микросхем… и у него был весьма загадочный способ объяснять, что он делает. Он реально не любил об этом рассказывать».
Друг и коллега Киркпатрика Дэн Гелатт проявил живой интерес к этой проблеме и увлек ею и самого Скотта, с которым случилось внезапное прозрение. «Способ изучения [физических систем] заключался в том, чтобы нагреть их, затем охладить и дать системе возможность самоорганизоваться. С данной точки зрения, это выглядело совершенно естественным способом решения всех типов проблем оптимизации, как если бы количество степеней свободы, которые вы пытаетесь организовать, были бы маленькими атомами, спинами или чем там еще».
В физике то, что мы называем температурой, на самом деле является скоростью – хаотичное движение частиц на молекулярном уровне. Это очень похоже, рассуждал Киркпатрик, на хаотичное «дрожание», которое может применяться вместе с алгоритмом восхождения на холм, чтобы иногда отказываться от лучших решений в пользу худших. На самом деле алгоритм Метрополиса был изначально создан, чтобы моделировать хаотичное поведение частиц в физических системах (конкретно в том случае моделировались ядерные взрывы). И что же случится, вопрошал Киркпатрик, если вы попробуете решить проблему оптимизации как проблему отжига – сперва «нагреете» ее, а затем медленно «охладите»?
Возвращаясь к задачке с десятью городами, мы могли бы начать с «высокой температуры», выстраивая первый маршрут полностью случайным образом, выбирая один из множества возможных вариантов решения независимо от цены. После этого мы можем медленно «остужать» наши поиски, бросая кубик каждый раз, когда рассматриваем изменение последовательности посещения городов. Выбор лучших вариантов всегда обоснован, но мы будем выбирать худшие, когда нам выпадает, скажем, два очка или больше. Через какое-то время мы еще немного «снизим температуру», выбирая более дорогие варианты, если на кубике выпадет 3 или больше – а потом 4, а потом 5. В конечном итоге мы практически взойдем на холм, отступая назад только иногда, когда выпадет 6. Наконец мы начали бы идти только в гору и остановились бы, достигнув следующего локального максимума.
Такой подход, названный имитацией отжига, кажется интригующим способом привлечь физику к решению проблем. Но сработает ли он? Первоначальная реакция исследователей традиционной оптимизации заключалась в том, что они сочли весь этот подход в целом слишком… иносказательным. «Я не могу убедить математиков, что вся эта замороченная ерунда с температурами, все эти аналогии реальны! Математики привыкли не доверять интуиции».
Но все недоверие к методу на основе аналогии вскоре исчезло без следа: в IBM алгоритм имитации отжига Киркпатрика и Гелатта позволил делать лучшие раскладки микросхем, чем вышеупомянутый гуру. Вместо того чтобы держать в тайне свое секретное оружие и самим стать таинственными гуру, они опубликовали статью в Science и поделились методом со всеми. В течение нескольких последующих десятилетий эта статья цитировалась более 32 000 раз! На сегодняшний день имитация отжига остается одним из наиболее перспективных подходов к решению известных проблем оптимизации.
