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

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

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

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

Полагают, что для адаптивного линейного сумматора является случайным вектором с

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

В табл. 8.1 приведены результаты анализа линейного алгоритма случайного поиска применительно к адаптивному линейному сумматору [16]. Эта таблица аналогична табл. 6.1. Как определено в гл. 5, N — число наблюдений, используемых для оценки СКО.

Таблица 8.1

Хотя линейный алгоритм случайного поиска основан на случайном изменении вектора весовых коэффициентов, он функционирует аналогично алгоритму наискорейшего спуска [16]. При случайном поиске весовые коэффициенты сходятся к W по закону геометрической прогрессии с такими же постоянными времени, как ,и при наискорейшем спуске. Из табл. 8.1 видно, что для обоих алгоритмов параметр имеет в действительности одну и ту же область устойчивости. При фиксированной скорости сходимости относительное среднее значение СКО для линейного алгоритма случайного поиска вдвое больше, чем для алгоритма наискорейшего спуска. Поэтому последний имеет преимущество. Однако первый алгоритм легко реализовать. Кроме того, он эффективен в качестве модели естественного отбора и при теоретических исследованиях развития биологических систем.

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

Линейный алгоритм случайного поиска состоит в том, что для проверки на каждой итерации выбирается случайное направление. В [17] для адаптивных систем разработан алгоритм проверки случайных точек в пространстве рабочих параметров. Это напоминает процесс деления и отбора клеток.

Рассмотрим работу этого алгоритма для одного весового коэффициента w. Прежде всего осуществляется выбор начального множества М значений w, равномерно распределенных в заданной области. Затем для каждого из этих Ж значений w находится и строится новое большее множество значений. В этом новом множестве М первоначальных значений w располагаются в обратной зависимости от соответствующих значений . Таким образом, если в первоначальном множестве содержатся значения , то в построенном множестве больше значений , чем . В целом объем множества равен N, причем некоторые значения w входят в него несколько раз.

Затем для второй выборки строится следующая последовательность. Выбираются случайным образом два значения w и производится склеивание двоичных представлений обоих значений. К первому сегменту одной двоичной последовательности присоединяется второй сегмент другой. Предположим, например, что w представлено 8 битами, т. е. имеется 256 возможных значений, и склеивание осуществляется в середине каждой последовательности. Тогда

двоичное представление значения ,

двоичное представление значения ,

двоичное представление последовательности: .

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

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