Хайкин С. - Нейронные сети (778923), страница 142
Текст из файла (страница 142)
Например,его можно сгенерировать с помощью правила обучения Больцмаиа (9). Это правило мы рассмотрим в разделе 11.7. 11.5. Метод иоделирования отжига Теперь займемся поисюм системы с низкой энергией, состояния которой упорядочены в цепь Марюва. Из выражения (11.11) видно, что при достижении температурой Т нуля свободная энергия системы Г достигает среднего значения энергии (Е).
При Š— (Е) из принципа минимума свободной энергии видно, что распределение Гиббса, являющееся стационарным распределением в цепи Маркова, разрушается в точке глобального минимума средней энергии при Т вЂ” О. Другими словами, упо- 708 Глава 11. Стохастические машиныи их аппроксимацннв статистической механике рядоченные состояния с низкой энергией более предпочтительны прн низких температурах. Все эти наблюдения приводят к следующему вопросу: "Почему нельзя напрямую применить алгоритм Метрополиса для генерации популяций представителей конфигурации стохастических систем при очень низких температурах?" Автор не советует использовать эту стратегию, так как скорость сходимостн цепи Маркова к точке термального равновесия при малых температурах чрезвычайно низка. Вместо этого для достижения вычислительной эффективности рекомендуется работать со стохастическими системами при высоких температурах, где скорость сходимости к точке равновесия велика, после чего работать уже в точке равновесия с системой при более низких температурах.
Таким образом, будем использовать комбинацию двух связанных составляющих. ° Расписание, определяющее уровень, на котором температуру следует понизить. ° Алгоритм, подобный алгоритму Метрополиса, итеративно определяющий равновесное распределение для каждой новой температуры из расписания, используя конечное состояние системы при предыдущей температуре в качестве точки начала работы с более низкой температурой. Описанная двухшаговая схема лежит в основе широко используемого метода стохастической релаксации (51осЬазвс ге1ахайоп), называемого моделированием отжига (гйпш1а[ед аппеа1[пй)з 1560).
Свое название этот подход получил по аналогии с процессами в физике или химии, где процесс начинается при более высокой температуре, которая затем понижается до достижения точки температурного равновесия. т Идея введения температуры и моделирования отжига в задачах комбннаторной оптимизации появияась независимо в [1791 и [5601. В контексте физики отжиг является очень тонким процессом.
В [5бб) обсуждалось понятие "плавки" твердого тела, которое включало в себя поднятие температуры ло максимального значения, при кгпорой все части этою тела переходили в жидкую фюу, т.е. Рюмешались случайным обрюом. После ягою температура понижалась, позволяя всем частям организоваться в иизкоэнергетическом состоянии "земли" соответствующей решетки. Если охлаждение происходило слишком быстро (т.е.
у твердого тела ие хватало времени для достижения термального равновесия на каждом температурном значении), полученный кристалл имел массу лефектов или субстанция могла сформировать стекло с отсутствием «ристаялического порядка и метаустойчивой локально оптимальной структурой.
Понятие "отжига" юрошо иллюстрируется процессом нзпповления стекла и явлвется в некотором контексте задачей комбинаторной оптимизации. Однако оно может ввести в заблуждение при рассмотрении многих других областей применения [1151. Например, если поднять "температуру" при обработке изображений до такого уровня, что все части организуются случайным образом, мы попросту потеряем само изображение — оио станет равномерно серым. В соответствующем контексте металлургии при отжнге железа или мели необходимо сохранять температуру отжита ниже температуры отжига металла, в противном случае заготовка будет разрушена. Существует ряд важных параметров, характерных для процесса отжига в металлургии. температура отжита [аппеайпя гешрегашге) — температура, до которой нагревается металл или сплав. Время отжига [аппеайпя г)ше) — продолжительность времени, в течение которого поддерживается повышенная температура.
Расписание охлаждения (соойпя яскебп)е) — определяет скорость понижения температуры. Эти параметры имеют свои аналоги в молелировании отжита, что и будет описано в соответствующем подразделе. 11.5. Метод моделирования отжив 709 Основной целью моделирования отжига является поиск глобального минимума функции стоимости, которая характеризует большую и сложную системуз. Этот метод является мощным инструментом решения невыпуклых задач оптимизации. Он объясняется одной достаточно простой идеей. ]зри оптимизаг(ии очень больших и сложных систем (т.е. систем с множеством степеней свободы) вместо постоянного движения вниз по склону старайтесь двигаться по сгслону вниз большую часть времени. Моделирование отжига отличается от обычных итеративных алгоритмов оптимизации двумя важными аспектами. ° Этот алгоритм ис "стопорится", так как выход из точки локального минимума всегда возможен при работе системы в условиях ненулевой температуры.
° Моделирование отжига является адаптивным. Большая часть основных свойств конечного состояния системы уже проявляются при высоких температурах, в то время как при более низких их состояние только уточняется. Расписание отжига Как уже говорилось ранее, алгоритм Метрополиса является основой процесса моделирования отжига, направленного иа медленное понижение температуры Т. Это значит, что сама температура Т выступает в роли параметра управления. Процесс моделирования отжига будет сходиться к конфигурации с минимальной энергией при условии, что температура будет понижаться не быстрее, чем логарифмически.
К сожалению, такое расписание отжига чрезвычайно медленно — настолько медленно, что вряд ли применимо на практике. На практике необходимо прибегнуть к аппроксимаг(ии на конечнолг интервале времени (бп[(е-(ппе арргохппайоп). Однако за это придется заплатить большую цену — алгоритм ие будет гарантированно сходиться к точке глобального минимума с вероятностью 1.
Тем не менее получаемая приближенная форма в большинстве практических приложений этого алгоритма способна привести к точке, достаточно близкой к оптимальному решению. Для того чтобы реализовать приближение на конечном интервале времени алгоритма моделирования отжига, необходимо определить множество параметров, управляющих его сходимостью. Эти параметры объединяются в так называемое расписание отжига (аппеа[[пя зс))е([п[е) или расписание охлаждения (соойпд асЬес[п!е).
Это расписание представляет собой конечную последовательность значений температу- з Уравнение Ланжевена (сапает(п) (с температурой, зависящей от времени) является основой еше одного важного алгоригма глобальной оптимизации, который был предложен в [384) и впоследствии проанализирован в [350]. Уравнение ланжевена, = — то(г) -~- Г((), где о(() -- скоросгь частиц с массой т, погруженныл в а (г) жилкость; т — константа, равная частному от деления козффнциента трения на массу гп; Г(() — удельная сила колебаний (на единицу массы) Уравнение Лангевина было первым математическим соотношением, которое описывало неравновесную зермолинамику.
710 Глава 11. Стохастические машиныи их алпроксимациив статистической механике ры и конечное число пробных переходов для каждой из этих температур. В [560) интересующие параметры определяются следующим образом4. ° Канальное значение температуры. Начальное значение Т1, выбирается достаточно высоким для того, чтобы для алгоритма моделирования отжига были доступны все предлагаемые переходы. ° Понижение температуры. Обычно охлаждение осуществляется экспоненциально, а изменения, применяемые к температуре, являются небольшими. В частности, функцию убывания (4[есгешеп[ бшс[топ) можно определить следуюшим образом: Ть — — аТь „ lс = 1,2,..., (11.34) где а — константа, меньшая единицы, но достаточно близкая к последней. Как правило, значения этой константы выбираются в диапазоне от 0,8 до 0,99.
Прн каждой из температур предпринимается достаточно много попыток перехода, так чтобы среднее их количество не опускалось ниже 10 принятых переходов(ассергее[ 1гапгййоп). ° Конечное значение температуры. Система постепенно охлаждается и отжиг останавливается, когда требуемое количество принятых переходов не достигается при трех последовательных температурах. Последний критерий можно переопределить следующим образом: коэффициент пропускания (ассер1апсе табо), определяемый как количество принятых переходов, деленное на количество предложенных переходов, становится меныпе некоторого наперед заданного значения [516]. Модепироаание отжига для комбинаторной оптимизации Моделирование отжига хорошо подходит, в частности, для решения задач комбинаторной оптимизации.
Целью комбинаторной оптимизации (сошЬ[па[опа! орбппкабоп) является минимизация функции стоимости конечной дискретной системы, характеризуемой большим количеством возможных решений. В своей основе моделирование отжига использует алгоритм Метрополиса для генерации последовательности решений, с привлечением аналогии между физическими многочастичными (шапурагбс!е) системами и задачей комбинаторной оптимизации. 4 Более сложные и теоретически оаоснованные расписания отжита описаны в [1], [10791.
11.6. Распределение Гиббса 711 ТАБЛИЦА 11.1. Соответствия между терминологией статистической физики и ком- бннаторной оптимизации Статистическая физика Комбинаторная оптимизация Пример (зашр]е) Оптимальная конфигурация (орй- ша[ сопййпгат[оп) При моделировании отжига энергия Ег в распределении Гиббса (11.5) интерпретируется как числовая стоимость, а температура Т вЂ” как параметр управления.
Эта числовая стоимость ставит в соответствие каждой из конфигураций задачи комбинаторной оптимизации некоторое скалярное значение, которое отражает приемлемость данной конфигурации для решения. Следующий вопрос моделирования отжига сводится к следующему; как идентифицировать конфигурации и локально генерировать новые конфигурации нз уже имеющихся.
Именно в этом вопросе алгоритм Метрополиса играет особо важную роль. В табл. 11.1 приведены соответствия между терминологией статистической физики и комбннаторной оптимизации [115]. Подобно алгоритму Метрополиса, схема квантования Гиббсаз (ОтЬЬз зашр[ег) генерирует цепь Маркова с распределением Гиббса, выступающим в роли равновесного распределения. Однако вероятности перехода, связанные с квантованием Гиббса, не являются стационарными (343). При окончательном анализе выбор между квантованием Гиббса и алгоритмом Метрополиса зависит от технических деталей рассматриваемой задачи. Для того чтобы приступить к описанию этой схемы квантования, рассмотрим К-мерный случайный вектор Х, состоящий из компонентов Х„Х2,..., Хк.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
