Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Как правило, в качестве функции h(AE; Т) выбирается либо точное значение соответствующей физической величине Вторая формула используется наиболее часто. При ее использовании h(AE; Т) оказывается больше единицы в случае АЕ < 0, и тогда соответствующая вероятность считается равной 1. Таким образом, если новое состояние дает лучшее значение оптимизируемой функции, то переход в это состояние произойдет в любом случае. Итак, конкретная схема метода отжига задается следующими пара­ метрами: • выбором закона изменения температуры Т(к). где к — номер шага; • выбором порождающего семейства распределений g(x; Г); • выбором функции вероятности принятия варианта h(AE; Т). При некоторых комбинациях вышеперечисленных параметров могут получаться алгоритмы, эффективные при определенных условиях. Некоторые из таких комбинаций образуют схемы отжига. Ниже перечислены некоторые из них: • больцмановский отжиг; • отжиг Коши (быстрый отжиг); • сверхбыстрый отжиг; • алгоритм Ксин-Яо. Методы тушения Далеко не всегда хватает вычислительных ресурсов на поиск глоба­ льного минимума. Кроме того, зачастую достаточно достигнуть не глобально оптимального решения задачи, а достаточно близкого к нему. Методы тушения (simulated quenching) не гарантируют нахождения глобального минимума, но, как правило, быстро находят близкое решение, а на практике зачастую и сам оптимум. Основная идея этих методов заключается в том, чтобы скомби­ нировать семейство распределений G одного из предыдущих четырех методов с более быстрым законом убывания температуры. Например, можно рассматривать нормальные распределения g из больц- мановского отжига, но при этом уменьшать температуру по закону Как правило, в этом случае с выбирается между 0.7 и 0.99. Такой метод очень быстро сходится, и для конкретных задач может в условиях реального времени давать весьма неплохое решение, близкое к оптимальному. Некоторые из методов тушения рассмотрены в [4, 5]. Зачастую они основаны либо на нормальном распределении, либо на распределении для сверхбыстрого отжига. Кроме того, встречаются специальные распределения, подобранные опытным путем для решения конкретных задач. ( 2 ) либо приближенное значение АЕ h(AE;T) = е Т . ( 3 ) 64