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

В методах случайного поиска в процедуру поиска преднамеренно вводится элемент случайности.

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

Метод базируется на предположении, что случайный выбор содержит все решения, в том числе и то, которое приводит к достижению цели. Рассмотрим некоторые виды случайного поиска.

§ Локальный случайный поиск с возвратом

Вначале производится фиксированный шаг в случайно выбранном направлении. Если при этом

т.е. выбор оказался неудачным, то происходит возврат в исходное состояние х₁, а затем совершается новый шаг. Если

то следующий шаг делается из точки и т.д.

Обычно используют рекуррентную процедуру вида

(3.6)

где

Здесь N– номер шага;

а – величина шага смещения;

– случайный единичный вектор .

§ Локальный случайный поиск с пересчетом

В отличие от предыдущего метода возврат назад при неудачном шаге не происходит, а делается следующий шаг, но с учетом исходного состояния.

В рекуррентной формулу (3.6) поправка находится в соответствии с алгоритмом

Здесь т.е. наименьшее значение функции качества за N предыдущих шагов.

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

Существует множество других методов и их модификации. Например, локальный случайный поиск по наилучшей пробе: делается m пробных шагов и выбирается наилучший, если . Если – следует повтор. Отметим, что, в зависимости от задачи, следует искать . Тогда вышеприведенные формулы следует соответствующим образом изменить.

Дата добавления: 2015-07-26; просмотров: 274; Нарушение авторских прав

Мы поможем в написании ваших работ!