Такой подход, названный имитацией отжига, кажется интригующим способом привлечь физику к решению проблем. Но сработает ли он? Первоначальная реакция исследователей традиционной оптимизации заключалась в том, что они сочли весь этот подход в целом слишком… иносказательным. «Я не могу убедить математиков, что вся эта замороченная ерунда с температурами, все эти аналогии реальны! Математики привыкли не доверять интуиции».
Но все недоверие к методу на основе аналогии вскоре исчезло без следа: в IBM алгоритм имитации отжига Киркпатрика и Гелатта позволил делать лучшие раскладки микросхем, чем вышеупомянутый гуру. Вместо того чтобы держать в тайне свое секретное оружие и самим стать таинственными гуру, они опубликовали статью в Science и поделились методом со всеми. В течение нескольких последующих десятилетий эта статья цитировалась более 32 000 раз! На сегодняшний день имитация отжига остается одним из наиболее перспективных подходов к решению известных проблем оптимизации.
Случайность, эволюция и творчество
В 1943 году Сальвадор Лурия еще не подозревал, что стоит на пороге открытия, которое обеспечит ему Нобелевскую премию; он собирался посвятить себя танцам. Сбежав в США от режима Муссолини из Италии, где проживала его семья, Лурия исследовал, как бактерии вырабатывают иммунитет против вирусов. Но в тот момент исследования мало занимали его мысли, поскольку он начал посещать собрания преподавательского состава университета в загородном клубе недалеко от Индианского университета.
Лурия наблюдал, как один из его коллег играл в автоматы:
Не будучи азартным игроком по натуре, я подначивал его, предрекая неизбежный проигрыш, когда вдруг он внезапно сорвал джекпот (около трех долларов десятицентовыми монетками) окинул меня злобным взглядом и ушел. Именно тогда я задумался о подлинной нумерологии игровых автоматов; и в процессе до меня дошло, что игровые автоматы и мутации бактерий могут многому поучиться друг у друга.
В 1940-х годах не было точно известно, откуда и как возникает устойчивость бактерий к вирусам (и, если уж на то пошло, – к антибиотикам). Реакция ли это бактерий на вирусы или же просто мутации, которые случайно проявили устойчивость? Казалось, что не существует способа провести эксперимент и получить четкий ответ на данный вопрос, – до тех пор пока Лурия не увидел игровой автомат и его не осенило. Лурия понял, что, если он выведет несколько поколений различных колоний бактерий, а затем подвергнет последнее поколение воздействию вируса, он получит один из двух диаметрально противоположных результатов. Если сопротивление было ответной реакцией на вирус, то он мог бы ожидать появления примерно такого же количества резистентных бактерий в каждой из его бактериальных культур, независимо от их происхождения. С другой стороны, если резистентность возникла в результате случайных мутаций, то следовало ожидать чего-то еще более случайного и неравномерного – как выигрыш в автомате. Бактерии из большинства колоний не проявили бы никакой устойчивости к вирусу вообще; некоторые колонии дали бы единственное поколение «внучат», устойчивое к вирусу; и в редких случаях, если бы «правильная» мутация происходила с несколькими поколениями в «генеалогическом древе», это был бы джекпот: все «внуки» в колонии были бы резистентны. Лурия забросил танцы, как только появилась возможность провести данный эксперимент.