Главная > Интеллектуальные системы > Адаптация сложных систем
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.6.1. «Набросовые» алгоритмы

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

3.6.1.1. Случайный наброс с локальным поиском

На каждом этапе из случайной начальной точки делается локальный спуск в ближайший минимум любым локальным методом поиска. За глобальный минимум принимается тот, для которого показатель качества минимален, т. е.

Очевидно, что при вероятность того, что является положением глобального минимума, стремится к единице, т. е.

При конечном вероятность утери глобального экстремума, т. е. не равна нулю.

Однако использование локального поиска совершенно необязательно при работе набросовых алгоритмов. Это скорее дань локальному поиску. Рассмотрим другие алгоритмы.

3.6.1.2. Адаптивный набросовый алгоритм

Этот алгоритм связан с адаптивным изменением плотности распределения наброса. Пусть — плотность

распределения, параметры которого определяются вектором равным, математическому ожиданию случайного вектора

и — некоторой скалярной мерой рассеяния этого распределения (типа среднеквадратичного отклонения), такой, что при распределение вырождается в -функцию и имеем а с увеличением а область наброса расширяется пропорциональна а по всем направлениям пространства Алгоритм поиска заключается в генерировании последовательности случайных точек; и выборе точки с наименьшим значением показателя качества аналогично (3.6.1):

При этом параметры и а распределения адаптируются, например, следующим образом:

является лучшей из всех предыдущих точек, и

где параметры могут выбираться исходя из различных соображений.

В случае т. е. при расширении зоны поиска с каждой удачей и сужении — с неудачей, получаем локализирующийся алгоритм, который стремится «стянуть» наброс вокруг лучшей точки. Темп такого стягивания определяет степень глобальности алгоритма. Если стягивание происходит быстро, то, очевидно, будет найден ближайший локальный экстремум; если же медленно, то шансы найти экстремум лучше ближайшего, локального повышаются.

В случае вероятность отыскания глобального экстремума, при стремится к единице (при этом еще необходимо, чтобы для любой точки, т. е. чтобы плотность вероятности появления любой допустимой точки не была равна нулю).

Возможен и иной подход к выбору параметров Если логику адаптации (3.6.6) как бы «вывернуть наизнанку», т. е. положить то получим несходящуюся процедуру, которая расширяет зону поиска при неулучшении и сужает ее

при отыскании лучших точек. Оба подхода обладают своими достоинствами и недостатками. Применение их связано с учетом конкретных свойств объекта.

3.6.1.3. Набросовый алгоритм глобального поиска с идентификацией распределений

Этот интересный алгоритм связан с восстановлением (идентификацией) плотности распределения значений минимизируемой функции в случайных точках равномерно распределенных в области поиска Если область поиска произвольно разделить на две части и в каждой определить плотность то наиболее перспективной для изучения будет та область, для которой левый «хвост» распределения (напомним, что рассматривается случай минимизации) простирается дальше. Для широкого класса сложных объектов в качестве такого распределения можно воспользоваться логнормальным распределением, левый «хвост» которого ограничен. Наименьшая из оценок этих границ и решает вопрос о выборе наиболее перспективной зоны для дальнейшего аналогичного исследования. Таким образом, рассекая область поиска последовательно на измельчающиеся зоны, можно выйти в район глобального экстремума и определить его любым локальным методом.

<< Предыдущий параграф Следующий параграф >>
Оглавление