Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

Чипига А.Ф., Колков Д.А.

Основным методом случайного поиска глобального экстремума многомерных функций является мультистарт [1, 2]. При его использовании из множества X случайно или детерминировано выбирается некоторое подмножество из N точек. На каждом i-том подмножестве из случайной начальной точки Ui делается локальный спуск в ближайший минимум Ui* любым локальным методом поиска. За глобальный минимум U** принимается тот, для которого показатель качества минимален, т.е.:

f.

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

f.

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

Мультистарт - это обобщенный подход: большинство эффективных методов глобальной оптимизации основано на идее метода мультистарта - запуска стандартных локальных алгоритмов из множества точек, равномерно распределенных на множестве X. Таким образом, метод мультистарта можно назвать прототипом таких методов.

Адаптивный набросовый алгоритм [3, 4] связан с адаптивным изменением плотности распределения наброса (случайное распределение пробных состояний объекта). Пусть f - плотность распределения, параметры которого определяются вектором W, равным математическому ожиданию случайного вектора U:

f,

и σ - некоторой скалярной мерой рассеяния этого распределения (типа среднеквадратичного отклонения), такой, что при σ = 0 распределение вырождается в δ-функцию, и имеем U=W, а с увеличением σ область наброса расширяется пропорциональна σ по всем направлениям пространства {U}. Алгоритм поиска заключается в генерировании последовательности случайных точек U1,..., UN,... и выборе точки с наименьшим значением показателя качества:

f.

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

f

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

f

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

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

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

Возможен и иной подход к выбору параметров  f и f. Если логику адаптации как бы «вывернуть наизнанку», т.е. положить  f >1, а  f<1, то получим несходящуюся процедуру, которая расширяет зону поиска при неулучшении и сужает ее при отыскании лучших точек. Оба подхода обладают своими достоинствами и недостатками. Применение их связанно с конкретными свойствами объекта.

Наиболее простой алгоритм поиска экстремума методом сканирования [5, 6] ("поиск на сетке переменных") заключается в том, что по каждой независимой переменной задаются приращения в соответствующем порядке, обеспечивающем "заполнение" всей исследуемой области равномерной и достаточно густой сеткой. Из значений функции в узлах сетки выбирается оптимальное значение.

Объем вычислений при использовании метода сканирования можно оценить по следующей формуле:

f,

где D - точность определения экстремума, n - количество независимых переменных.

Модификации метода сканирования применяются в основном для сокращения объема вычислений. При сканировании с переменным шагом вначале задается достаточно большой шаг (DU > e) и выполняется "грубый" поиск, который локализует область существования глобального экстремума (P). После того, как область определена, производится поиск с меньшим шагом только в пределах найденной области (s). Можно организовать ряд таких процедур последовательного уточнения положения оптимума (s).

При использовании данного алгоритма объем вычислений существенно сокращается и может быть определен по формуле:

f,

где r - число этапов уточнения поиска, на котором шаг уменьшался в К раз, n - число независимых переменных; D - точность определения экстремума.

Начальный шаг сетки переменных в данном случае определяется формулой:

f.

Методы случайного поиска глобальных экстремумов многомерных функций дают высокую вероятность достижения поставленной цели.

СПИСОК ЛИТЕРАТУРЫ

  1. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.
  2. Орлянская И.В. Современные подходы к построению методов глобальной оптимизации, МГУ, факультет ВМиК.
  3. Растригин Л.А.. Адаптация сложных систем. Рига «Зинатне» 1981.
  4. Справочник по теории автоматического управления. 1987 г. «Наука».
  5. Сидоров Б.Н., Никулин А.М. Методы безусловной оптимизации функции одной переменной. Москва, 1999 г.
  6. http://www.opu.odessa.ua/konsp/MMXTP/RAZDEL5/glava576.htm.