16.8.   ДРУГИЕ ПРИЛОЖЕНИЯ

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

Другим приложением, которого мы не касались, является моделирование систем с дальнодействующими потенциалами, таких, как кулонов-ские системы. Для таких потенциалов необходимо разрабатывать методы учета взаимодействий частиц в центре ячейки с бесконечной системой периодических копий. Одно из наиболее свежих впечатляющих приложений метода Моите-Карло связано с анализом поведения теорий калибровки на решетках—теорий, на которые возлагаются большие надежды в деле понимания фундаментальных взаимодействий материи.

Данную главу мы завершаем обсуждением методов Моите-Карло применительно к задачам, которые, как могло бы показаться, имеют мало общего с типами задач, которые мы рассмотрели. Эти задачи называются многомерной или комбинаторной оптимизацией —модный способ сказать: «Как вы находите минимум функции, зависящей от многих параметров?». Мы объясняем сущность этого типа задач на примере, известном как задача о коммивояжере, которую мы будем называть задачей о коробейнике.

Задачу о коробейнике можно сформулировать следующим образом. Предположим, что некий коробейник хочет посетить Л' городов и следовать таким маршрутом, чтобы ни один город не посещать более одного раза, закончить поездку в том же пункте, откуда ои ее начал, и сократить общее пройденное расстояние до минимума. Какой маршрут является оптимальным? На рис. 16.6 показан пример Л' городов и один из возможных маршрутов. Задачи такого типа возникают во всех областях планирования и проектирования. Во всех известных точных методах определения оптимального пути требуемое машинное время растет как eN. Поэтому иа практике точное решение можно находить только для задач, насчитывающих несколько сотен городов или меньше. Задача о коробейнике принадлежит к большому классу задач, называемых NP-полнота — этим термином вы можете воспользоваться, чтобы произвести впечатле-

ние на своих приятелей. С помощью карандаша и бумаги отыщите оптимальный путь для случайного размещения восьми городов. Каково, по вашей оценке, предельное количество городов, которое целесообразно рассматривать, не прибегая к компьютеру?

Чтобы понять характер различных подходов к задаче о коробейнике, рассмотрим изображенную на рис. 16.7 «энергетическую» функцию Е(а). Мы можем связать Е(а) с длиной пути и интерпретировать а как параметр, отражающий порядок посещения городов. В общем случае функция Е(а) имеет несколько локальных минимумов и один абсолютный минимум. Имеется ли какой-нибудь хороший метод для отыскания абсолютного минимума функции Е(а)? Одни путь —это точный расчет, т.е. изменять а и находить значение Е везде. Этот метод соответствовал бы определению длины пути коробейника для каждого возможного маршрута, и очевидно, что такая задача непосильна, если число городов велико. Следовательно, нужно использовать какой-то эвристический метод, т.е. приближенный метод отыскания пути, близкого к абсолютному минимуму. Один из методов состоит в том, что выбирается некое значение а, те-

иерируется небольшое случайное число 8а и данное изменение принимается, если Е(а + 8а) ие превышает Е(а). Такая стратегия итерационного уточнения соответствует поиску шагов, которые ведут к спуску. Поскольку, как правило, этот поиск застревает в локальном, а не глобальном минимуме, обычно начинают с нескольких начальных вариантов а и оставляют самый лучший результат. Как можно было бы применить этот метод к задаче о коробейнике?

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

Каким образом можно применить метод отжига к задаче отыскания минимума Е(а)? Пусть выбрано некоторое значение а, сгенерировано небольшое случайное число 8а н вычислено Е(а + 8а). Если Е(а + 8а) меньше или равно Е(а), данное изменение, как и ранее, принимается. Однако если LE = Е(а + 8а) - Е(а) > 0, данное изменение принимается с вероятностью Р = exp (-LE/k^T), где Т—эффективная температура. Эта процедура является хорошо знакомым алгоритмом Метрополиса, причем температура играет здесь роль управляющего параметра. Процесс вынужденного отжига состоит из начального «расплавления» системы с последующим постепенным понижением температуры. При каждой температуре моделирование должно длиться достаточно долго, чтобы система достигала устойчивого состояния. Режим отжига, т.е. скорость понижения температуры, определяет качество решения.

Смысл метода модельного отжига понятен—чтобы попасть в долину, иногда нужно взбираться на горку. Первым применением метода модельного отжига было оптимальное проектирование компьютеров. Пожалуй, вам стоит подумать и о других приложениях. В задаче 16.20 этот метод используется в задаче о коробейнике.