Моделирование обжига
Этот общий метод минимизации может быть очень полезен для приблизительного решения многих 'трудных' проблем минимизации, используя псевдослучайный поиск. Например NPC проблема известная как 'путешествующий продавец' может быть действительно 'решена', используя моделирование обжига, см.
[PRES92]. Метод находит вдохновение в способе, которым характер непосредственно достигает minimas. Имя исходит из процесса, где горячему металлу медленно позволяют охлаждать и заморозиться в минимальную энергетическую кристаллическую конфигурацию решетки.Функция, f - для минимизации называется целевой функцией. В нашем случае, f - стоимость пути. Метод начинается с начальным 'предполагаемым' решением. Например, мы могли бы использовать 'прямую линию' пути между источником, и адресатом (это может быть и не допустимый путь). Затем решение итерационно улучшено, применяя произвольные возмущения в пути. Возмущаемый путь принят как новое начальное решение с вероятностью: 
. Таким образом, имеется вероятность принятия некоторых возмущений, который фактически увеличивают целевую функцию. Это необходимо, чтобы избежать 'захвата' локальным minimas. Параметр T системы, часто называемый 'температурой', используется, чтобы управлять этой вероятностью и понижается, пока допустимое решение не было найдено. Очень трудно создать хорошую функцию возмущения. Она должно иметь свойство и, введения малых, произвольных, 'возможных' изменений и в то же самое время позволять всем возможным решениям быть достигнутым. Часто T также используется, чтобы непосредственно управлять 'масштабом' возмущений. Точно, как T управляется, и как определить, когда остановиться очень трудно. Некоторая эвристика или адаптивная логика управления часто использована. Как простой пример мы могли бы использовать фиксированный T до, скажем 100 итераций в строке, не сумевших производить лучшее решение. Затем T разделен на два, и мы продолжаем в том же самом режиме. Мы останавливаемся, когда масштаб возмущений (как функция T) достаточно мал, и лежит ниже желательной точности решения. Этим способом, крупномасштабная оптимизация вначале выполняется (большое T, дающие большие возмущения) и затем оптимизация выполняется на непрерывно более низких масштабах, пока в заключение не сделана 'локальная' оптимизация.
Итерационный характер является, и большой силой и большой слабостью для этого метода. Положительная сторона, если мы нашли путь за некоторое время, мы можем только прекратить итерации, когда мы хотим. Отрицательная сторона, мы не имеем никакого знания как быстро достиганется некоторая степень точности, если это когда-либо будет (в зависимости от того, насколько хорошая функция возмущения).
Для дальнейшей информации относительно моделирования обжига, см. [PRES92] или главу 4.1 [CSEP95]
7.2