ЛОКАЛЬНЫЙ ПОИСК В НЕПРЕРЫВНЫХ ПРОСТРАНСТВАХ
ского поиска с восхождением к вершине и поиска с эмуляцией отжига можно применять непосредственно, без дискретизации этого пространства. Такие алгоритмы выбирают преемников случайным образом, что может быть осуществлено путем формирования случайным образом векторов с длиной А.
Имеется также много методов, в которых при осуществлении попыток найти максимум используется градиент ландшафта. Градиент целевой функции представляет собой вектор Vf, позволяющий определить величину и направление наиболее крутого склона. Для рассматриваемой задачи справедливо следующее соотношение.
В некоторых случаях можно найти максимум, решая уравнение Vf=0. (Это можно сделать, например, при размещении только одного аэропорта; решение представляет собой арифметическое среднее координат всех городов.) Но во многих случаях это уравнение не может быть решено в замкнутой форме. Например, при наличии трех аэропортов выражение для градиента зависит от того, какие города являются ближайшими к каждому аэропорту в текущем состоянии. Это означает, что мы можем вычислить этот градиент локально, но не глобально. Даже в таком случае остается возможность выполнять поиск с восхождением к вершине по самому крутому склону, обновляя текущее состояние с помощью следующей формулы:
х 4- х + ocVf(x)
где а — небольшая константа. В других случаях целевая функция в дифференцируемой форме может оказаться вообще не доступной, например, значение конкретного множества местонахождений аэропортов может быть определено в результате вызова на выполнение какого-то пакета крупномасштабного экономического моделирования. В таких случаях можно определить так называемый эмпирический градиент, оценивая отклик на небольшие увеличения и уменьшения каждой координаты. Поиск по эмпирическому градиенту является аналогичным поиску с восхождением к вершине по самому крутому склону в дискретизированной версии данного пространства состояний.
За фразой "а — небольшая константа" скрывается огромное разнообразие методов определения значения а. Основная проблема состоит в том, что если значение а слишком мало, то требуется слишком много этапов поиска, а если слишком велико, то в поиске можно проскочить максимум. Попытка преодолеть эту дилемму предпринимается в методе линейного поиска, который предусматривает продолжение поиска в направлении текущего градиента (обычно путем повторного удвоения а) до тех пор, пока f не начнет снова уменьшаться. Точка, в которой это происходит, становится новым текущим состоянием. Сформировалось несколько научных школ, в которых доминируют разные взгляды на то, каким образом в этой точке следует выбирать новое направление.
Для многих задач наиболее эффективным алгоритмом является почтенный метод Ньютона-Рафсона [1132], [1266]. Это — общий метод поиска корней функций, т.е. метод решения уравнений в форме д(х) =0. Этот алгоритм действует на основе вычисления новой оценки для корня х в соответствии с формулой Ньютона:
х <— х - д(х) /д' (х)
Чтобы найти максимум или минимум f, необходимо найти такое значение х, для которого градиент равен нулю (т.е. Vf (х) =0). Поэтому функция д(х) в формуле Ньютона принимает вид Vf (х), и уравнение обновления состояния может быть записано в матрично-векторной форме следующим образом:
х <- х - H"jHx)Vf(x)
где Hf (х) — представляет собой гессиан (матрицу вторых производных), элементы которого #ij задаются выражением d2f /dxLdxj. Поскольку гессиан имеет п2 элементов, то метод Ньютона-Рафсона в многомерных пространствах становится дорогостоящим, поэтому было разработано множество способов приближенного решения этой задачи.
Локальные максимумы, хребты и плато создают затруднения в работе методов локального поиска не только в дискретных пространствах состояний, но и в непрерывных пространствах состояний. Для преодоления этих затруднений могут применяться алгоритмы с перезапуском случайным образом и с эмуляцией отжига, которые часто оказываются достаточно полезными. Тем не менее многомерные непрерывные пространства характеризуются очень большим объемом, в котором легко потеряться.
Последней темой, с которой необходимо кратко ознакомиться, является оптимизация с ограничениями. Задача оптимизации называется задачей оптимизации с ограничениями, если решения в ней должны удовлетворять некоторым жестким ограничениям на значения каждой переменной. Например, в рассматриваемой задаче с размещением аэропортов можно ввести ограничения, чтобы места для аэропортов находились в пределах Румынии, причем на суше (а не, допустим, на середине озера). Сложность задач оптимизации с ограничениями зависит от характера ограничений и от целевой функции. Наиболее широко известной категорией таких задач являются задачи линейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область, а целевая функция также является линейной. Задачи линейного программирования могут быть решены за время, полиномиально зависящее от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций: квадратичное программирование, коническое программирование второго порядка и т.д.
До сих пор в данной книге изложение было сосредоточено на описании агентов, в которых используются алгоритмы поиска в автономном режиме. Эти агенты вычисляют полное решение, прежде чем ступить в реальный мир (см. листинг 3.1), а затем выполняют это решение, не обращаясь к данным своих восприятий. В отличие от этого любой агент, выполняющий поиск в оперативном режиме14,