Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

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

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

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

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

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

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

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

После нескольких дней напряженного беспокойного ожидания Лурия вернулся в лабораторию проведать свои колонии бактерий. Джекпот.

Открытие Лурии свидетельствовало о силе случая; оно демонстрировало, как случайные беспорядочные мутации могут привести к устойчивости к вирусам. Но и состоялось оно, по крайней мере отчасти, благодаря случайности. Он оказался в нужном месте в нужное время, когда игровой автомат подал ему новую идею. Многие великие открытия часто рождаются подобным образом: вспомните яблоко Ньютона (возможно, вымышленное); архимедово «Эврика!» в ванне; заброшенную чашку Петри, в которой выросла плесень Penicillium. На самом деле это настолько распространенный феномен, что для его обозначения было придумано специальное слово: в 1754 году Хорас Уолпол ввел термин «серендипность», основываясь на сказке о приключениях трех принцев из Серендипа (старинное название острова Шри-Ланка). Благодаря случайностям и смекалке они постоянно совершали открытия, которых совершать не собирались.

Эта двойная роль случайности – ключевая часть биологии, ключевая часть открытия – неоднократно привлекала внимание психологов, стремящихся найти объяснение творческим способностям человека. Ранним примером этой идеи послужил Уильям Джеймс. В 1880 году, будучи недавно назначенным ассистентом профессора психологии в Гарварде (спустя 10 лет после публикации эпохальных «Принципов психологии»), Джеймс написал статью в Atlantic Monthly «Великие люди и их окружение». Статья начинается с его тезиса:

В период написания статьи идея зоологической эволюции была еще свежа: «Происхождение видов» вышла в 1859 году, и сам Дарвин еще был жив. Джеймс рассуждал, как эволюционные идеи можно применить к различным составляющим человеческого общества, и в конце статьи обратился к эволюции идей: