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

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

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

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

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

Алгоритм поиска можно записать в следующем рекуррентном виде:

а — величина шага смещения; — случайный единичный вектор;

На рис. 11.9 представлена блок-схема алгоритма (11.40). В начальный момент система делает шаг в случайном направлении из исходного состояния причем в памяти уже находится значение функции качества для этого состояния. Затем определяется новое значение функции качества которое сравнивается с запомненным . В случае уменьшения функции качества вновь делается случайный шаг и запоминаются его компоненты. В случае. увеличения функции качества система делает обратный шаг — компоненты которого были запомнены раньше. Функция качества в этом состоянии определяется вновь и запоминается, после чего делается новый шаг в случайном направлении. Алгоритм эффективен даже в случае нестационарных функций качества, изменяющихся во времени по тем или иным причинам.