методы случайного поиска

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

Отмеченный  недостаток можно устранить, применяя методы случайного поиска, иначе — вероятностные методы. Их преимущества проявляется, прежде всего, в случае  большого числа параметров, по которым проводится оптимизация.

Методы случайного поиска

Рассмотрим один из алгоритмов, реализующий случайный поиск  экстремума.  Предлагаемый алгоритм  носит название алгоритма «наилучшей пробы»

 Алгоритм «наилучшей пробы»

1.                    Выберем две случайные точки в пространстве параметров изменяемых компонентов, свяжем их прямой и найдем локальный экстремум на полученной прямой одним из известных методов одномерной минимизации.

2.                    Повторим операцию для двух следующих случайных точек.

3.                    Будем искать локальный  минимум на прямой, проходящей через точки локальных экстремумов, полученные ранее.

4.                    Выполним этап 1 и перейдем к этапу 3.

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

Определение: Для данной симметричной матрицы А порядка m направления  S1,S2….Sr (r<m)  называются сопряженными, если Siлинейно независимы  и

SiTА   Sj= 0 для всех ij                                              (3)

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

Пусть задана квадратичная функция вида

Ф(Р)=Вт Р+0,5РтАР                                                  (4)

где А — положительно определенная симметричная матрица, и m сопряженных направлений S1,S2 ….Sm.. Проведя минимизацию Ф(Р) по каждому из направлений S1,S2 ….Sm. (как положительному ,так и отрицательному), найдем минимум квадратичной функции, зависящий от mпараметров. Минимум может быть найден не более чем за mитераций.

Ссылка на основную публикацию
Adblock detector