Алгоритмы для жизни: Простые способы принимать верные решения - [92]

В те времена процессом руководил своего рода тайный гуру компании IBM. Киркпатрик вспоминает: «Тот парень мог напихать на чип больше всего микросхем… и у него был весьма загадочный способ объяснять, что он делает. Он реально не любил об этом рассказывать».

Друг и коллега Киркпатрика Дэн Гелатт проявил живой интерес к этой проблеме и увлек ею и самого Скотта, с которым случилось внезапное прозрение. «Способ изучения [физических систем] заключался в том, чтобы нагреть их, затем охладить и дать системе возможность самоорганизоваться. С данной точки зрения, это выглядело совершенно естественным способом решения всех типов проблем оптимизации, как если бы количество степеней свободы, которые вы пытаетесь организовать, были бы маленькими атомами, спинами или чем там еще».

В физике то, что мы называем температурой, на самом деле является скоростью – хаотичное движение частиц на молекулярном уровне. Это очень похоже, рассуждал Киркпатрик, на хаотичное «дрожание», которое может применяться вместе с алгоритмом восхождения на холм, чтобы иногда отказываться от лучших решений в пользу худших. На самом деле алгоритм Метрополиса был изначально создан, чтобы моделировать хаотичное поведение частиц в физических системах (конкретно в том случае моделировались ядерные взрывы). И что же случится, вопрошал Киркпатрик, если вы попробуете решить проблему оптимизации как проблему отжига – сперва «нагреете» ее, а затем медленно «охладите»?

Возвращаясь к задачке с десятью городами, мы могли бы начать с «высокой температуры», выстраивая первый маршрут полностью случайным образом, выбирая один из множества возможных вариантов решения независимо от цены. После этого мы можем медленно «остужать» наши поиски, бросая кубик каждый раз, когда рассматриваем изменение последовательности посещения городов. Выбор лучших вариантов всегда обоснован, но мы будем выбирать худшие, когда нам выпадает, скажем, два очка или больше. Через какое-то время мы еще немного «снизим температуру», выбирая более дорогие варианты, если на кубике выпадет 3 или больше – а потом 4, а потом 5. В конечном итоге мы практически взойдем на холм, отступая назад только иногда, когда выпадет 6. Наконец мы начали бы идти только в гору и остановились бы, достигнув следующего локального максимума.

Такой подход, названный имитацией отжига, кажется интригующим способом привлечь физику к решению проблем. Но сработает ли он? Первоначальная реакция исследователей традиционной оптимизации заключалась в том, что они сочли весь этот подход в целом слишком… иносказательным. «Я не могу убедить математиков, что вся эта замороченная ерунда с температурами, все эти аналогии реальны! Математики привыкли не доверять интуиции».

Но все недоверие к методу на основе аналогии вскоре исчезло без следа: в IBM алгоритм имитации отжига Киркпатрика и Гелатта позволил делать лучшие раскладки микросхем, чем вышеупомянутый гуру. Вместо того чтобы держать в тайне свое секретное оружие и самим стать таинственными гуру, они опубликовали статью в Science и поделились методом со всеми. В течение нескольких последующих десятилетий эта статья цитировалась более 32 000 раз! На сегодняшний день имитация отжига остается одним из наиболее перспективных подходов к решению известных проблем оптимизации.

Случайность, эволюция и творчество

В 1943 году Сальвадор Лурия еще не подозревал, что стоит на пороге открытия, которое обеспечит ему Нобелевскую премию; он собирался посвятить себя танцам. Сбежав в США от режима Муссолини из Италии, где проживала его семья, Лурия исследовал, как бактерии вырабатывают иммунитет против вирусов. Но в тот момент исследования мало занимали его мысли, поскольку он начал посещать собрания преподавательского состава университета в загородном клубе недалеко от Индианского университета.

Лурия наблюдал, как один из его коллег играл в автоматы:

Не будучи азартным игроком по натуре, я подначивал его, предрекая неизбежный проигрыш, когда вдруг он внезапно сорвал джекпот (около трех долларов десятицентовыми монетками) окинул меня злобным взглядом и ушел. Именно тогда я задумался о подлинной нумерологии игровых автоматов; и в процессе до меня дошло, что игровые автоматы и мутации бактерий могут многому поучиться друг у друга.

В 1940-х годах не было точно известно, откуда и как возникает устойчивость бактерий к вирусам (и, если уж на то пошло, – к антибиотикам). Реакция ли это бактерий на вирусы или же просто мутации, которые случайно проявили устойчивость? Казалось, что не существует способа провести эксперимент и получить четкий ответ на данный вопрос, – до тех пор пока Лурия не увидел игровой автомат и его не осенило. Лурия понял, что, если он выведет несколько поколений различных колоний бактерий, а затем подвергнет последнее поколение воздействию вируса, он получит один из двух диаметрально противоположных результатов. Если сопротивление было ответной реакцией на вирус, то он мог бы ожидать появления примерно такого же количества резистентных бактерий в каждой из его бактериальных культур, независимо от их происхождения. С другой стороны, если резистентность возникла в результате случайных мутаций, то следовало ожидать чего-то еще более случайного и неравномерного – как выигрыш в автомате. Бактерии из большинства колоний не проявили бы никакой устойчивости к вирусу вообще; некоторые колонии дали бы единственное поколение «внучат», устойчивое к вирусу; и в редких случаях, если бы «правильная» мутация происходила с несколькими поколениями в «генеалогическом древе», это был бы джекпот: все «внуки» в колонии были бы резистентны. Лурия забросил танцы, как только появилась возможность провести данный эксперимент.