Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 45
Текст из файла (страница 45)
Это — хорошая стратегия, если любое состояние имеет большое количество преемников (измеряеьгое тысячалги). В упр. 4.! б предлагается исследовать этот алгоритм. Алгоритмы с восхождением к вершине, описанные выше, являются неполными, поскольку часто оказываются неспособными найти цель, притом что она существует, из-за топ), что могут зайти в тупик, достигнув локалы|ого максимума.
'ж Поиск с восхождением к вершине и перезапуском случайнььм образом руководствуется широко известной рекомендацией: "Если первая попьпка оказалась неудачной. пробуйте снова и снова". Вэтом алгоритме предусмотрено проведение ряда поисков из сформированных случайным образом начальных состояний' и останов после достижения цели. Он является полным с вероятностью, достигающей 1, даже по той тривиальнои причине, что в нем в конечном итоге в качестве начального состояния формируется олно из целевых состояний. Если вероятность успеха каждого поиска с восхождением к вершине равна р, то ожидаемое количество требуемых перезапусков составляет 1гр.
Для экземпляров задачи с восемью ферзями, если не разрешено движение в сторону, )~=0 . 14, поэтому для нахождения цели требуется приблизительно 7 итераций (б неудачных и 1 успешная). Ожидаемое количество этапов решения равно стоимости одной успешной итерации, которая складывается с увеличенной в (1-р) гр раз стоимостью неудачи, или составляет приблизительно 22 этапа. Если разрешено движение в сторону, то в среднем требуется 1/0.94=1. 06 итераций и (1х21) + 10.
06/О 94) х64=25 этапов. Поэтому алгоритм поиска с восхождением к вершине и перезапуском случаиным образом действительно является очень эффективным применительно к задаче с восемью ферзями. Даже для варианта с тремя миллионами ферзей этот подход позволяет находить решения меньше чем за минуту'. Успех поиска с восхождением к вершине в значительной степени зависит от формы ландшафта пространства состояний: если в нем есть лишь немного локальных максимумов и плато, то поиск с восхождением к вершине и перезапуском случайным образом позволяет очень быстро найти хорошее решение.
С другой стороны, многие реальные задачи имеют ландшафт, который больше напоминает семейство дикобразов на плоском полу, где на вершине иглы каждого дикобраза живут другие миниатюрные дикобразы и т.д., до бесконечности. )х)Р-трудные задачи обычно имеют экспоненциальное количество локальных максимумов, способных завести ' Может оказаться трудной лаже сама задача формирования случайным образом некоторого состояния из неявно заданного пространства состояний.
з В !958! доказано, что в некоторых случаях лучше всего осуществлять перезапуск рандомизированного алгоритма поиска по истечении конкретной, постоянной продолжительности времени и что такой подход может оказаться гораздо более эффективным по сравнению с тем, когда разрешено продолжать каждый поиск до бесконечности. Примером такого подхода является глюке запрещение или ограничение количества движений в сторону. Часть 11.
Решение проблем 180 алгоритм в тупик. Несмотря на это, часто существует возможность найти достаточно хороший локальный максимум после небольшого количества перезапусков. Поиск с эмуляцией отжигя Для любого алгоритма с восхождением к вершине, который никогда не выполняет движения "вниз по склону", к состояниям с более низкой оценкой (или более высокой стоимостью), гарантируется, что он окажется неполным, поскольку такой ачгоритм всегда способен зайти в тупик, достигнув локального максимума. В отличие от этого алгоритм с чисто случайным блужданием (т.с, с перемещением к преемнику, выбираемому на равных правах случайным образом из множества преемников) является полным, но чрезвычайно неэффективным. Поэтому представляется разумной попытка скомбинировать каким-то образом восхождение к вершине со случайным блужданием, что позволит обеспечить и эффективность, и полноту.
Алгоритмом такого типа является алгоритм с 'ъ. эмуляцией отжита. В мета~ыургии отжитом называется процесс, применяемый ддя отпуска металла и стекла путем нагревания этих материалов до высокой температуры, а затем постепенного охлаждения, что позволяет перевести обрабатываемый материал в ннзкоэнергетнческое кристаллическос состояние. Чтобы понять суть эмуляции отжига, переведем наше внимание с восхождения к вершине на Ж градиентный спуск (т.с. минимизацию стоимости) и представим себе, что наше задание — загнать теннисный шарик в самую глубокую лунку на неровной поверхности. Если бы мы просто позволили шарику катиться по этой поверхности, то он застрял бы в одном из локальных минимумов.
А встряхивая поверхность, можно вытолкнуть шарик из локального минимума. Весь секрет состоит в том, что поверхность нужно трясти достаточно сильно, чтобы шарик можно было вытолкнуть из локальных минимумов, но не настолько сильно, чтобы он вылетел из глобального минимума. Процесс поиска решения с эмуляцией отжига заключается в том, что вначале происходит интенсивное встряхнвание (аналогичное нагреву до высокой температуры), после чего интенсивность встряхивания постепенно уменьшается (что можно сравнить с понижением температуры). Самый внутренний цикл алгоритма с эмуляцией отжита (листинг 4.3) полностью аналогичен циклу алгоритма с восхождением к вершине, но в нем вместо наилучшего хода выполняется случайно выбранный ход.
Если этот ход улучшает ситуацию, то всегда принимается. В противном случае алгоритм принимает данный ход с некоторой вероятностью, меньшей 1. Эта вероятность уменьшается экспоненциально с "ухудшением" хода — в зависимости от величины Лд; на которую ухудшается его оценка. Кроме того, вероятность уменьшается по мере снижения "температуры" т.
"плохие" ходы скорее всего могут быть разрешены в начале, когда температура высока, но становятся менее вероятными по мере снижения ~. Можно доказать, что если в графике яс)зеоц2 е предусмотрено достаточно медленное снижение т, то данный алгоритм позволяет найти глобальный оптимум с вероятностью, приближающейся к 1.
На первых порах, в начале !980-х годов, поиск с эмуляцией отжига широко использовался для решения задач компоновки СВИС. Кроме того, этот алгоритм нашел широкое применение при решении задач планирования производства и других крупномасштабных задач оптимизации. В упр. 4.1б предлагается сравнить его производительность с производительностью поиска с восхождением к вершине и перезапуском случайным образом при решении задачи с п ферзями. Глава 4.
Информированный поиск и исследование пространства состояний 181 Листвяг 4.3. Алгоритм поиска с эмуляцией отжита, который представляет собой одну из версий алгоритма стохасгпческого поиска с восхождением к вершние, в которой разрешены некоторые ходы вапз. Ходы вниз принимаются к исполнению с большей вероятностью яа ранних этапах выаолиеаив графика отжита, а затем, ао мере того как проходит время, выполвяются менее часто. Входной параметр войесзпзе определяет значение температуры т как функции от времени Епповьоп Яьтц1аСеб-ядпеа11цд(ргосзеп, яслеои2е) кеьпкпв состояние ремеиия 1прпсв: ргоь1ет, задача вс)зес)цзе, отображение между временем и "температурой" 1ооа1 уак1пЬ1ев: сиггепс, узел пехс, узел т, "температура", от которой зависит вероятность шагов вниз сиггепс ч — Маке-небе(1пьсьа1-Ясасе[ргоь1ет)) Еок С < — 1 Со Ссо т ч- ясьес)и1е[С) 1Е т = О сЬеп кеспкп сцгсепс пехС Ь- случайно выбранный преемник состояния сцггепС ЬЕ ч — Ча1це[пехС) — Ча1це[сцггепС) 1Е ЬЕ > О Сьев сиггепС <- пехС е1ве сцггепС ь- пехС с вероятностью только е ьест Локальный лучевой поиск Стремление преодолеть ограничения, связанные с нехваткой памяти, привело к тому, что в свое время предпочтение отдавалось алгоритмам, предусматривающим хранение в памяти только одного узла, но, как оказалось, такой подход часто является слишком радикальным способом экономии памяти.
В алгоритме Ъ. локального лучевого поиска" предусмотрено отслеживание )с состояний, а не только одного состояния. Работа этого алгоритма начинается с формирования случайным образом )с состояний. На каждом этапе формируются все преемники всех )с состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
