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

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

Преодолеть локальный максимум

Один из таких способов – улучшить ваше восхождение на холм с помощью того, что называется «дрожание»: если вы чувствуете, что застряли на месте, попробуйте немного перемешать все планы. Внесите несколько случайных незначительных изменений (даже если они будут к худшему), а затем снова вернитесь к восхождению на холм. Возможно, вы очутитесь на более высокой вершине.

Другой вариант – полностью перетасовать все планы, как только мы достигнем локального максимума, и начать восхождение на холм заново с этой новой случайно выбранной отправной точки. Этот алгоритм имеет подходящее название «случайный перезапуск восхождения», или – еще более красочно – «восхождение наугад». Такая стратегия оказывается весьма эффективной, когда в задаче несколько локальных максимумов. Например, компьютерщики пользуются ею при дешифровке кодов, поскольку всегда есть много способов начать дешифровку, которые выглядят многообещающе, а в итоге заводят в тупик. Если в ходе дешифровки у вас получается текст, отдаленно напоминающий нормальный русский язык, это еще не значит, что вы на правильном пути. Так что порой лучше не привязываться к изначально выбранному направлению, каким бы правильным оно вам ни казалось, и начать все с нуля.

Но есть еще и третий способ: вместо того чтобы полностью положиться на волю случая, когда ты зашел в тупик, прибегайте к помощи случайности в каких-то мелочах каждый раз, когда принимаете решение. Эта техника, придуманная все той же командой из Лос-Аламоса, которая разработала метод Монте-Карло, получила название «алгоритм Метрополиса». Алгоритм Метрополиса, так же как и «восхождение на холм», работает за счет мелких перестановок в решении, но с одним большим отличием: в любой заданной точке он может принять плохие перестановки наравне с хорошими.

Давайте попробуем применить этот метод к планированию нашего отпуска. Мы снова попробуем скорректировать маршрут, меняя местами разные города. Если получившаяся случайным образом перестановка приводит к улучшению маршрута, мы принимаем ее и продолжаем процесс дальше с этой точки. Но, если изменение приводит к небольшому ухудшению, все равно остается шанс, что мы примем его (хотя чем хуже изменение, тем меньше этот шанс). Таким образом, мы не застреваем в одном локальном максимуме надолго: в конце концов, мы испробуем другое решение, пусть это и окажется немного дороже, и продолжим нашу работу по созданию нового и лучшего плана.

Не важно, будет ли это «дрожание», случайный перезапуск или готовность к временному ухудшению, случайность остается невероятно полезным способом избегать локальных максимумов. Шанс – это не только конкурентоспособный метод решения жестких проблем оптимизации; во многих случаях он играет решающую роль. Но некоторые вопросы еще остаются открытыми. Какой процент случайности нужно использовать? И когда? И – учитывая, что такие стратегии, как алгоритм Метрополиса, могут менять наш маршрут до бесконечности, – как вообще понять, что можно заканчивать? Окончательный ответ на эти вопросы немедленно даст исследователям, работающим над вопросом оптимизации, новую пищу для размышлений.

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

В конце 1970-х – начале 1980-х годов Скотт Киркпатрик считался физиком, а не специалистом в области информатики. В частности, его интересовала статистическая физика, в которой случайностью объяснялись некоторые явления природы, например физика отжига – то, как материалы меняют свое состояние в процессе нагрева или охлаждения. Пожалуй, самой интересной характеристикой отжига является скорость охлаждения вещества, которая оказывает огромное влияние на его конечную структуру. Как писал Киркпатрик:

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

Киркпатрик в то время работал в компании IBM, где самой сложной и важной проблемой было нанесение электросхем на чипы, производимые компанией. Проблема была громоздкой и труднорешаемой: существовало множество путей решения, и при этом имелись некоторые сложные ограничения. Так, например, в общем и целом стоило располагать элементы близко друг к другу, но не слишком, чтобы оставалось место для соединения. И каждый раз, как что-то сдвигалось, приходилось по новой рассчитывать, как все соединения будут работать при гипотетическом новом расположении.