§ 3.3. Алгоритмы случайного поиска

3.3.1. Структура поискового метода

Метод (алгоритм) решения задачи оптимизации и адаптации представляет собой последовательную процедуру, имеющую рекуррентный характер [149]. Это означает, что процесс поиска состоит из повторяющихся этапов, каждый из которых определяет переход от одного решения к другому, лучшему, что и образует процедуру последовательного улучшения решения:

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

Здесь смысл знака предпочтения может быть разным. Например, если то (3.2.2) может быть связано со значениями критерия, т. е. Если то предпочтение (3.3.2) естественно связать с выполнением

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

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

В чем состоит специфика алгоритма и почему его называют поисковым? Дело в том, что информации в точке совершенно недостаточно для перехода в другую, лучшую точку Необходимо хотя бы иметь представление, как изменяется оптимизируемая функция и как ведут себя ограничения в области точки этого нельзя составить разумный алгоритм обеспечивающий условие улучшения (3.3.2). Именно поэтому алгоритм определения нового решения состоит обычно из двух частей. На первую возлагается задача получения информации о поведении функции и ограничений т. е. производится поиск информации. Вторая часть алгоритма должна принимать решение, какое состояние следует рекомендовать в качестве исходного для следующего этапа поиска.

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

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

Приведем пример алгоритма случайного поиска, в котором указанные части выделены явно. Это так называемый алгоритм случайного поиска с парными пробами, применяемый обычно для решения задач без ограничений, т. е. при . В нем процедура сбора информации сводится к выбору случайного направления и определению значения показателя качества в двух точках — единичный случайный вектор) (рис. 3.3.1).

Решение, которое принимается на базе этой информации, заключается в том, чтобы сделать шаг величиной а в направлении уменьшения (а в случае максимизации — в сторону увеличения) функции (см. рис. 3.3.1), т. е.

Рис. 3.3.1. Организация рабочего шага алгоритма случайного поиска с парными пробами.

Рис. 3.3.2. Шаг поиска в пространстве параметров.

где знак шага зависит от значений функции качества в точках А и В (так, на рис. 3.3.1 ).

В целом такой алгоритм записывается в виде

где — функция знака:

Как видно, здесь на первом этапе собирается информация о поведении функции качества в области точки для чего оценивается ее приращение в случайном направлении Радиус определяет сферу сбора информации (на рис. 3.3.1 показана пунктиром). Сферу радиуса а естественно назвать сферой принимаемого решения (заметим, что величина рабочего шага а может быть и меньше, чем пробного что характерно для окончания процесса оптимизации). Свое название этот алгоритм случайного поиска получил от двух проб в точках А и В, доставляющих информацию, необходимую для принятия решения.

Продолжим рассмотрение случайного поиска как метода решения оптимизационных задач. Удобно алгоритм поиска представлять в виде правила вычисления приращения (шага) на каждом этапе поиска:

(рис. 3.3.2). Алгоритм поиска в этом случае определяет один шаг перехода от одного решения к другому, следующему за ним:

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

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

Естественно подразделить все возможные алгоритмы поиска на два класса:

— детерминированные, регулярные алгоритмы поиска обладающие указанным свойством однозначности;

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

Легко показать, что

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

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