Обзор методов поиска новых технических решений

 

где а — знак наклона регулярной составляющей f(x) в точке (для минимума «+», для максимума «—»); а — постоянная, определяющая наклон аппроксимированной прямой к f(x).

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

 

                              (15)

 

где — интервал оценки производной, то поиск экстремума функции сводится к поиску корня функции регрессии регулярной части в соответствии с процедурой Кифера—Вольфовица:

 

                   (16)

 

Где a=

 

В случайном поиске по статистическому градиенту из исходного состояния х{ делается т случайных пробных шагов: a В новых точках i=1,2,…, m, вычисляют значения функции качества  ,i=1,2,…,m, и соответствующие приращения функции качества:

 

                           (17)

 

После этого вычисляется вектор статистической оценки градиента в точке , т. е.

 

        (18)

 

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

 

Рис.6

 

 

 

                       (19)

 

где -норма вектора статистического градиента; а — величина рабочего шага.

Таким образом, в случайном поиске по статистическому градиенту число точечных измерений статистической оценки градиента может быть меньше по сравнению с методами стохастической аппроксимации (т < п).

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

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

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

 

      (20)

Где - это i-е пробное состояния, выбранное случайно и сохраненное в памяти в случае удачной пробы; – вычисленное в i-м пробном состоянии значение функции качества и сохраненное в памяти в случае удачной пробы; -пробный шаг; J()-значение функции качества на i-м пробном шаге.

При равномерной плотности распределения пробных шагов поиск разделяется на к этапов из пробных шагов, где j = 1. 2..... к.

Каждый пробный этап осуществляется внутри гиперпараллелепипеда в пространстве состояний X, т. е.

 

, i=1,2,…, n,                 ( 21)

 

причем стороны гиперпараллелепипеда с каждым j-м этапом уменьшаются в     с > 1 раз по сравнению с (j — 1)-м этапом в соответствии с формулой:

 

    (22)

 

где   — точка, соответствующая пробному шагу с наименьшим значением функции качества из всех проб на (j — 1)-м этапе.

Несмотря на равномерную плотность распределения пробных шагов внутри каждого этапа, происходит увеличение плотности распределения от этапа к этапу за счет уменьшения зоны поиска (23), т. е.

 

 (23)

 

где — плотность распределения пробных шагов на j-м этапе;

  — объем гиперпараллелепипеда на j-м этапе.

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

Иногда целесообразно пробные шаги на каждом последующем этапе распределять не равномерно, а по нормальному закону, например

(24)

 — исходная дисперсия; 0 < < q < 1.

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

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

 

2.Примеры поисковых самонастраивающихся систем

 

Самонастраивающаяся система с поиском по методу градиента. Блок-схема системы представлена на рис. 10. Система работает по принципу синхронного детектирования с модуляцией, основанному на методе градиента.

На рабочее движение системы накладывается гармоническое поисковое движение с небольшой амплитудой, вырабатываемое генератором Г и устройством формирования опорного сигнала УОС, т. е.

 

     (25)

 

На выходе объекта колебательная составляющая функции качества J(x) изменяет фазу в зависимости ст текущего положения рабочей точки относительно экстремума (рис. 11).

 

 

Рис. 7

 

С помощью синхронного детектора фазы ДФ осуществляется перемножение сигнала У (х) и опорного сигнала с генератора:

 (11.66)

После отфильтрования переменной составляющей с помощью фильтра Ф получают сигнал, пропорциональный производной функции качества по х, т. е.dJ(x)/dx, поступающий на исполнительное устройство ИУ. В точке экстремума этот добавочный сигнал равен нулю.

2.1.Многоканальный статистический оптимизатор со случайным поиском. Схема и принципы работы самонастраивающейся системы со случайным поиском описаны в 121. В системе реализован ряд шаговых алгоритмов поиска, например поиск с возвратом, поиск с пересчетом и т. д. Система состоит из одинаковых, параллельно работающих каналов, выбранных по числу оптимизируемых параметров объекта. Блок-схема одного из каналов представлена на рис. 12(а)

 

Рис.8

 

Рис. 9

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

 

 

 

 

 

 

 

Сигнал измеряют следующим образом:

 

 

Значение определяют так:

 

     (26)

 

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

Состояния блока команд пронумерованы следующим образом: / — определение знака приращения показателя качества ДУ (х)\ 2 — запоминание показателя качества; 3 — обратный шаг; 5 — сброс памяти генератора случайных сигналов; 6 — запуск генератора случайных сигналов; 7 — рабочий шаг; 8 — установление функции качества на выходе объекта.

 

 

3.Простейшие алгоритмы направленного случайного поиска

 

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

 

Рис. 10

 

Координаты вершин гиперквадрата на -м этапе определяются соотношениями

,  ,         (27)

где – наилучшая точка в гиперквадрате на -м этапе.

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

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

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

 

,  .           (28)

 

Хорошо выбранное правило регулировки стороны гиперквадрата приводит к достаточно эффективному алгоритму поиска.

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

 

3.2.Алгоритм парной пробы. В данном алгоритме четко разделены пробный и рабочий шаги. Пусть – найденное на -м шаге наименьшее значение минимизируемой функции . По равномерному закону генерируется случайный единичный вектор и по обе стороны от исходной точки делаются две пробы: проводим вычисление функции в точках , где -величина пробного шага. Рабочий шаг делается в направлении наименьшего значения целевой функция. Очередное приближение определяется соотношением

.

Рис.11

 

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

 

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

С увеличением числа проб выбранное направление приближается к направлению .

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

Рис.12

 

3.4.Метод статистического градиента. Из исходного состояния делается независимых проб и вычисляются соответствующие значения минимизируемой функции в этих точках. Для каждой пробы запоминаем приращения функции

.

После этого формируем векторную сумму . В пределе при она совпадает с направлением градиента целевой функции. При конечном вектор представляет собой статистическую оценку направления градиента. Рабочий шаг делается в направлении . Очередное приближение определяется соотношением

.

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

Рис.13

 

3.5.Алгоритмы глобального поиска. Случайный поиск приобретает решающее значение при оптимизации многоэкстремальных задач и объектов. В общем случае решение многоэкстремальных задач без элемента случайности практически невозможно.

 

 

 

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

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

Рис.14

 

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

 

Алгоритм 2. Пусть получена некоторая точка локального экстремума . После этого переходим к ненаправленному случайному поиску до получения точки такой, что .

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

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

Поиск прекращается, если при генерации некоторого предельного числа новых случайных точек не удается найти лучшей, чем предыдущий локальный экстремум, который и принимается в качестве решения.

 

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