Главная arrow книги arrow Копия Глава 4. arrow Локальный поиск в непрерывных пространствах
Локальный поиск в непрерывных пространствах

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

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

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