Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 47
Текст из файла (страница 47)
4.4. ЛОКАЛЪНЫЙ ПОИСК В НЕПРЕРЫВНЫХ ПРОСТРАНСТВАХ В главе 2 было описано различие между дискретными и непрерывными вариантами среды, а также указано, что большинство реальных вариантов среды являются непрерывными. Но еьце ни олин из описанных выше алгоритмов не способен действовать в непрерывных пространствах состояний, поскольку в этих алгоритмах в большинстве случаев функция определения преемника возвращала бы бесконечно большое количество состояний! В настоящем разделе приведено очень краткое введение в некоторые методы локального поиска, предназначенные для нахождения оптимальных решений в непрерывных пространствах. Литература по этой теме весьма обширна; многие из этих основных методов впервые были созданы в ХтП веке после разработки первых математических исчислений Ньютоном и Лейбницем".
Применение данных методов рассматривается в нескольких главах настоящей книги, включая главы, касающиеся обучения, машинного зрения и робототехники. Короче говоря, эти методы касаются всего, что связано с реальным миром. Начнем изложение этой темы с примера. Предположим, что где-то в Румынии требуется найти место для размеьцения трех новых аэропортов таким образом, чтобы сумма квадратов расстояний от каждого города на карте (см. рис. 3.1) до ближайшего к нему аэропорта была минимальной. В таком случае пространство состояний определено координатами аэропортов: (х,,у,), (х,,у,) и (х,,у,) .
Это — шестимерное пространство) иными словами можно выразить данную мысль так, что состояния определяются шестью переменными. (Вообще говоря, состояния определяются пмерным вектором переменных, ж.) Перемещение в этом пространстве соответствует переносу одного или нескольких нз этих аэропортов в другое место на карте.
!1елевую функцию Г(х„у„х,, у,, х,, у,) после определения ближайших городов можно вычислить довольно легко, но гораздо сложнее составить общее выражение, соответствующее искомому решению. Один из способов предотвращения необходимости заниматься непрерывными задачами состоит в том, чтобы просто дискретизировать окрестности каждого состояния. Например, можно предусмотреть перемещение одновременно только одного аэропорта в направлении либо х, либо у на постоянную величину +гз.
При наличии шести переменных это соответствует двенадцати возможным преемникам для каждого состояния. После этого появляется возможность применить любой нз алгоритмов локального поиска, описанных выше. Кроме того, алгоритмы стохастиче- ~з для чтения этого раздела желательно обдавать элементарными знаниями о системах исчисления а многомерном пространстве и векторной арифметике. Часть 11. Решение проблем ского поиска с восхождением к вершине и поиска с эмуляцией отжига можно применять непосредственно, без дискретизации этого пространства. Такие алгоритмы выбирают преемников случайным образом, что может быть осуществлено путем формирования случайным образом векторов с длиной гг.
Имеется также много методов, в которых при осуществлении попыток найти максимум используется Ъ. градиент ландшафта. Градиент целевой функции представляет собой вектор ус", позволяющий определить величину и направление наиболее крутого склона. Для рассматриваемой задачи справедливо следуюшее соотношение: ('дг де дг де дг де'') [,дх ' ду ' дхг дуг дхг дуг) В некоторых случаях можно найти максимум, решая уравнение )7 с= О. (Это можно сделать, например, при размешении только одного аэропорта; решение представляет собой арифметическое среднее координат всех городов.) Но во многих случаях это уравнение не может быть решено в замкнутой форме.
Например, при наличии трех аэропортов выражение для градиента зависит от того, какие города являются ближайшими к каждому аэропорту в текущем состоянии. Это означает, что мы можем вычислить этот градиент локально, но не глобально. Даже в таком случае остается возможность выполнять поиск с восхождением к вершине по самому крутому склону, обновляя текушее состояние с помошью следуюшей формулы: х г — х + а))Г(х) гле а — небольшая константа.
В других случаях целевая функция в дифференцируемой форме может оказаться вообше не доступной, например, значение конкретного множества местонахождений аэропортов может быть определено в результате вызова на выполнение какого-то пакета крупномасштабного экономического моделирования. В таких случаях можно определить так называемый 'в. эмпирический градиент, оценивая отклик на небольшие увеличения и уменьшения каждой координаты. Поиск по эмпирическому градиенту является аналогичным поиску с восхождением к вершине по самому крутому склону в дискретизированной версии данного пространства состояний. За фразой "а — небольшая константа" скрывается огромное разнообразие методов определения значения а.
Основная проблема состоит в том, что если значение а слишком мало, то требуется слишком много этапов поиска, а если слишком велико, то в поиске можно проскочить максимум. Попытка преодолеть эту дилемму предпринимается в методе 'ъ линейного поиска, который предусматривает продолжение поиска в направлении текущего градиента (обычно путем повторного удвоения а) до тех пор, пока Г не начнет снова уменьшаться.
Точка, в которой это происходит, становится новым текущим состоянием. Сформировалось несколько научных школ, в которых доминируют разные взгляды на то, каким образом в этой точке следует выбирать новое направление. Для многих задач наиболее эффективным алгоритмом является почтенный метод ;ъ. Ньютона-Рафсоиа [! 132[, [!266). Это — общий метод поиска корней функций, т.е. метод решения уравнений в форме д(х) =О. Этот алгоритм действует на основе вычисления новой оценки для корня ж в соответствии с формулой Ньютона: х г — х — д(х) /д' (х) Глава 4.
Информированный поиск и исследование пространства состояний (89 Чтобы найти максимум или минимум б, необходимо найти такое значение х. для которого градиент равен нулю (т.е. Уг (к) =О). Поэтому функция д(х) в формуле Ньютона принимает вид Уб (ж), и уравнение обновления состояния может быть записано в матрично-векторной форме следующим образом: х ь- х — И г'(х)хг(х) где н, (х) — представляет собой;ъ. гессиан (матрицу вторых производных), элементы которого им задаются выражением д'бУдхгдхм Поскольку гессиан имеет и' элементов, то метод Ньютона — Рафсона в многомерных пространствах становится дорогостоящим, поэтому было разработано множество способов приближенного решения этой задачи.
Локальные максимумы, хребты и плато создают затруднения в работе методов локального поиска не только в дискретных пространствах состояний, но и в непрерывных пространствах состояний. Для преодоления этих затруднений могут применяться алгоритмы с перезапуском случайным образом и с эмуляцией отжига, которые часто оказываются достаточно полезными. Тем не менее многомерные непрерывные пространства характеризуются очень большим объемом, в котором легко потеряться. Последней темой, с которой необходимо кратко ознакомиться, является гъ. оптимизация с ограничениями.
Задача оптимизации называется задачей оптимизации с ограничениями, если решения в ней должны удовлетворять некоторым жестким ограничениям на значения каждой переменной. Например, в рассматриваемой залаче с размещением аэропортов можно ввести ограничения, чтобы места для аэропортов находились в пределах Румынии, причем на суше (а не, допустим, на середине озера).
Сложность задач оптимизации с ограничениями зависит от характера ограничений и от целевой функции. Наиболее широко известной категорией таких задач являются задачи билинейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область, а целевая функция также является линейной. Задачи линейного программирования мокн ут быть решены за время, полиномиально зависящее от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций: квадратичное программирование, коническое программирование второго порядка и т.д.
4.5. ПОИСКОВЫЕ АГЕНТЫ, ДЕЙСТВУЮЩИЕ В ОП ЕРАТИВНОМ РЕЖИМЕ, И НЕИЗВЕСТНЪ|Е ВАРИАНТЫ СРЕДЪ| До сих пор в данной книге изложение было сосредото ~ено на описании агентов, в которых используются алгоритмы Ъ. поиска в автономном режиме. Эти агенты вычисляют полное решение, прежде чем ступить в реальный мир (см. листинг 3.)), азатем выполняют это решение, не обращаясь к данным своих восприятий. В отличие от этого любой агент, выполняющий 'в. поиск в оперативном режиме", и В компьютерных науках термин "работающий в оперативном режиме'* обычно используется по отношению к алгоритмам, которые лолжны обрабатывать вхолныс данные по марс их получения, а нс ожилать, пока станет лоступным всс множество вхолных данных. 190 Час гь 1!.
Решение проблем функционирует по методу чередования вычислений и действий: вначале предпринимает действие, затем обозревает среду и вычисляет следующее действие. Поиск в оперативном режил~е целесообразно применять в динамических или полудинамических проблемных областях; таковыми являются проблемные области, в которых назначается штраф за то, что агент велет себя пассивно и вычисляет свои действия слишком долго. Еше более оправданным является использование поиска в оперативном режиме в стохастических проблемных областях. Вообще говоря, результаты любого поиска в автономном режиме должны сопровождаться экспоненциально большим планом действий в непредвиденных ситуациях, в котором учитываются все возможные варианты развития событий, тогда как при поиске в оперативном режиме необходимо учитывать лишь то, что действительно происходит.
Например, агент, играющий в шахматы, должен быть настолько хорошо проконсультирован, чтобы мог слелать свой первый ход задолго до того, как станет ясен весь ход игры. Применение поиска в оперативном режиме является необходимым при решении любой ех задачи исследования, в которой агенту не известны состояния и действия. Агент, находящийся в таком положении полного неведения, должен использовать свои действия в качестве экспериментов для опрелеления того, что делать дальше, и поэтому вынужден череповать вычисления и действия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
