Главная arrow Поиск arrow Непрерывные пространства
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Локальный поиск в непрерывных пространствах Печать
Было описано различие между дискретными и непрерывными вариантами среды, а также указано, что большинство реальных вариантов среды являются непрерывными. Но еще ни один из описанных выше алгоритмов не способен действовать в непрерывных пространствах состояний, поскольку в этих алгоритмах в большинстве случаев функция определения преемника возвращала бы бесконечно большое количество состояний! В настоящем разделе приведено очень краткое введение в некоторые методы локального поиска, предназначенные для нахождения оптимальных решений в непрерывных пространствах. Литература по этой теме весьма обширна; многие из этих основных методов впервые были созданы в XVII веке после разработки первых математических исчислений Ньютоном и Лейбницем. Применение данных методов рассматривается в нескольких главах настоящей книги, включая главы, касающиеся обучения, машинного зрения и робототехники. Короче говоря, эти методы касаются всего, что связано с реальным миром.

Начнем изложение этой темы с примера. Предположим, что где-то в Румынии требуется найти место для размещения трех новых аэропортов таким образом, чтобы сумма квадратов расстояний от каждого города на карте до ближайшего к нему аэропорта была минимальной. В таком случае пространство состояний определено координатами аэропортов: (х11), (х22) и (х33). Это — шестимерное пространство; иными словами можно выразить данную мысль так, что состояния определяются шестью переменными. (Вообще говоря, состояния определяются n-мерным вектором переменных, х.) Перемещение в этом пространстве соответствует переносу одного или нескольких из этих аэропортов в другое место на карте. Целевую функцию f(х1, у1, х2, у2, х3, y3) после определения ближайших городов можно вычислить довольно легко, но гораздо сложнее составить общее выражение, соответствующее искомому решению.

Один из способов предотвращения необходимости заниматься непрерывными задачами состоит в том, чтобы просто дискретизировать окрестности каждого состояния. Например, можно предусмотреть перемещение одновременно только одного аэропорта в направлении либо x, либо у на постоянную величину ±Δ. При наличии шести переменных это соответствует двенадцати возможным преемникам для каждого состояния. После этого появляется возможность применить любой из алгоритмов локального поиска, описанных выше. Кроме того, алгоритмы стохастического поиска с восхождением к вершине и поиска с эмуляцией отжига можно применять непосредственно, без дискретизации этого пространства. Такие алгоритмы выбирают преемников случайным образом, что может быть осуществлено путем формирования случайным образом векторов с длиной Δ.

Имеется также много методов, в которых при осуществлении попыток найти максимум используется градиент ландшафта. Градиент целевой функции представляет собой вектор Vf, позволяющий определить величину и направление наиболее крутого склона. Для рассматриваемой задачи справедливо следующее соотношение:


 

 

В некоторых случаях можно найти максимум, решая уравнение Vf = 0. (Это можно сделать, например, при размещении только одного аэропорта; решение представляет собой арифметическое среднее координат всех городов.) Но во многих случаях это уравнение не может быть решено в замкнутой форме. Например, при наличии трех аэропортов выражение для градиента зависит от того, какие города являются ближайшими к каждому аэропорту в текущем состоянии. Это означает, что мы можем вычислить этот градиент локально, но не глобально. Даже в таком случае остается возможность выполнять поиск с восхождением к вершине по самому крутому склону, обновляя текущее состояние с помощью следующей формулы:

x <- x + αVf(x)

За фразой «α — небольшая константа» скрывается огромное разнообразие методов определения значения а. Основная проблема состоит в том, что если значение а слишком мало, то требуется слишком много этапов поиска, а если слишком велико, то в поиске можно проскочить максимум. Попытка преодолеть эту дилемму предпринимается в методе линейного поиска, который предусматривает продолжение поиска в направлении текущего градиента (обычно путем повторного удвоения α) до тех пор, пока f не начнет снова уменьшаться. Точка, в которой это происходит, становится новым текущим состоянием. Сформировалось несколько научных школ, в которых доминируют разные взгляды на то, каким образом в этой точке следует выбирать новое направление.

Для многих задач наиболее эффективным алгоритмом является почтенный метод Ньютона-Рафсона. Это— общий метод поиска корней функций, т.е. метод решения уравнений в форме g(x) = 0. Этот алгоритм действует на основе вычисления новой оценки для корня x в соответствии с формулой Ньютона:

x <- x – g(x)/g`(x)

Чтобы найти максимум или минимум f, необходимо найти такое значение x, для которого градиент равен нулю (т.е. Vf(x) = 0). Поэтому функция g(x) в формуле Ньютона принимает вид Vf(x), и уравнение обновления состояния может быть записано в матрично-векторной форме следующим образом:

x <- x – H-1f(x)Vf(x)

где Hf(x) — представляет собой гессиан (матрицу вторых производных), элементы которого Hij задаются выражением d2f/dxidxj. Поскольку гессиан имеет n2 элементов, то метод Ньютона-Рафсона в многомерных пространствах становится дорогостоящим, поэтому было разработано множество способов приближенного решения этой задачи.

Локальные максимумы, хребты и плато создают затруднения в работе методов локального поиска не только в дискретных пространствах состояний, но и в непрерывных пространствах состояний. Для преодоления этих затруднений могут применяться алгоритмы с перезапуском случайным образом и с эмуляцией отжига, которые часто оказываются достаточно полезными. Тем не менее многомерные непрерывные пространства характеризуются очень большим объемом, в котором легко потеряться.

Последней темой, с которой необходимо кратко ознакомиться, является оптимизация с ограничениями. Задача оптимизации называется задачей оптимизации с ограничениями, если решения в ней должны удовлетворять некоторым жестким ограничениям на значения каждой переменной. Например, в рассматриваемой задаче с размещением аэропортов можно ввести ограничения, чтобы места для аэропортов находились в пределах Румынии, причем на суше (а не, допустим, на середине  озера). Сложность задач оптимизации с ограничениями зависит от характера ограничений и от целевой функции. Наиболее широко известной категорией таких задач являются задачи линейного программирования, в которых ограничения должны представлять собой линейные неравенства, образующие выпуклую область, а целевая функция также является линейной. Задачи линейного программирования могут быть решены за время, полиномиально зависящее от количества переменных. Кроме того, проводились исследования задач с другими типами ограничений и целевых функций: квадратичное программирование, коническое программирование второго порядка и т.д.