12.4. Поисковые системы экстремального управления

В поисковых СЭУ задача поиска экстремума разбивается на два этапа: определение градиента; движение к точке экстремума (поиск экстремума) подачей соответствующих управляющих воздействий Для решения как первой, так и второй задачи разработано много способов. Обычно для определения градиента используются пробные воздействия, а для движения к экстремуму — рабочие движения.

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

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

После определения частных производных (величины и направления градиента) в системе организуется рабочее движение к экстремуму (поиск экстремума). Методы поиска экстремума подразделяются на детерминированные и методы случайного поиска. К детерминированным методам относятся метод градиента, метод наискорейшего спуска, метод Гаусса — Зейделя и др.

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

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

Рис. 12.13. Метод градиента: а — непрерывное движение к экстремуму; б - движение шагами.

Рис. 12.14. Методы поиска экстремума: а — иаискорейшего спуска; б — Гаусса — Зейделя.

к линии уровня). Величина этого шага пропорциональна модулю градиента.

Метод наискорейшего спуска (подъема). В начальной точке (рис. 12.14, а) определяется направление градиента (нормаль к линии а затем осуществляется движение в этом направлении до тех пор, пока не прекратится увеличение I (в случае поиска максимума), т. е. не обратится в нуль производная от по принятому направлению движения. Шаг заканчивается в точке касания траектории движения с линией . В точке снова измеряется градиент и движение осуществляется по новому направлению, перпендикулярному предыдущему, и т. д. Метод наискорейшего спуска во многих случаях позволяет значительно сократить время поиска экстремума.

Метод Гаусса — Зайделя (метод покоординатной оптимизации). Из начальной точки (рис. 12.14, б) сперва осуществляется движение по одной координате (в результате изменения до тех пор, пока не будет достигнут экстремум (точка по этой координате. Затем изменяется управляющее воздействие до достижения экстремума и т. д. Техническая реализация метода проста, но требуется длительное время на поиск.

Метод случайного поиска. Из начальной точки делается случайных пробных шагов. При каждом пробном шаге замеряется приращение критерия оптимальности. Шаг с наилучшим результатом запоминается и рабочий шаг делается в направлении вектора, давшего лучший результат. В новой точке опять делается пробных шагов и выбирается «лучший» вектор и т. д. Такой метод поиска называется методом статистического градиента. Если в найденном

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

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

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

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