Алгоритмические методы оптимизации и адаптации

Итеративные методы для решения задач оптимизации аналитическими методами. Регулярные алгоритмы в задачах на безусловный и условный экстремумы. Поисковые и беспоисковые алгоритмы. Алгоритмы стохастической аппроксимации как вероятностные алгоритмы.

Рубрика Математика
Вид лекция
Язык русский
Дата добавления 22.07.2015
Размер файла 281,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Лекция. Алгоритмические методы оптимизации и адаптации

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

обозначены векторы искомых управлений или параметров.

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

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

J (С) = Q ( X, С);(1)

J (С) = Мх {Q ( X, С)},(2)

где X - вектор координат состояния; Мх - символ математического ожидания по множеству реализаций вектора X.

Для эргодических стационарных процессов вместо (2) можно использовать критерий качества, основанный на усреднении по времени:

(3)

Если функционал J(С) допускает дифференцирование по вектору С, то он достигает экстремума при таких значениях вектора С°, для которых

(4)

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

Для решения уравнений (4) и определения вектора используют различные итеративные методы. Физический смысл их состоит в замене алгебраических уравнений (4) относительно компонент вектора С разностными или дифференциальными уравнениями относительно этого же вектора С. Решение разностных или дифференциальных уравнений определяет искомый вектор С°, но не дает явного решения уравнений (4); оно характеризует алгоритмы, определяющие последовательность действий (операций), выполнение которых приводит к искомому решению. Поэтому итеративные методы, используемые в задачах оптимизации и адаптации, называют алгоритмическими методами.

Регулярные алгоритмы в задачах на безусловный экстремум. Основная идея решения уравнений (4) итеративными методами состоит в следующем. Уравнение (4) записывается в виде

(5)

где - некоторый скаляр.

На основании (5) вектор С°, соответствующий минимуму J (С), ищется с помощью последовательных приближений или итераций вида

(6)

Значение определяет величину очередного шага по градиенту и в общем случае зависит от номера шага k и векторов С (m), где

т = k - 1, k - 2, ..., 0.

Если выполняются условия сходимости, то для любого начального вектора С (0) получим

(7)

Начальное значение С(0) однозначно предопределяет последовательности С(k) для детерминированных задач [см. критерий (1)], поэтому итеративные методы, определяемые рекуррентным соотношением (6), называют регулярными. Формы регулярных итеративных методов различны в зависимости от .

Беспоисковые алгоритмы. Если рекуррентное соотношение (6) используют для определения оптимального вектора С° в задачах оптимизации, то его называют - алгоритмом оптимизации в рекуррентной форме. Введем первую разность вектора С

С(k - 1) = С(k) - С(k - 4),

после чего вместо (6) запишем разностное уравнение

(8)

которое называют алгоритмом оптимизации в разностной форме. Просуммируем обе части уравнения (8) от 0 до k, тогда получим уравнение

(9)

называемое алгоритмом оптимизации в суммарной форме.

Для увеличения скорости сходимости алгоритмов оптимизации вместо скаляра вводят матрицу

При этом уравнение (8) принимает вид

(10)

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

Алгоритмы оптимизации (10) различают в зависимости от формы матрицы Г(k):

Если

Г(k) = Г = const,

то получаем алгоритм оптимизации с постоянным шагом, или стационарный алгоритм;

если Г(k) зависит от k, то получаем алгоритм оптимизации с переменным шагом, или нестационарный алгоритм;

если

Г(k + k0) = Г(k),

то матрица Г(k) периодична и алгоритм оптимизации является циклическим.

В общем случае Г(k) может зависеть от вектора С(т), где

т = k - 1, k - 2, ..., 0,

тогда алгоритм оптимизации (10) имеет «нелинейный» шаг. В зависимости от формы матрицы Г(k,С) различают алгоритмы с нелинейным шагом:

Если

Г(k, С) = I(k, С),

где I - единичная матрица, (k, С) - скаляр, то алгоритм оптимизации называют градиентным;

если

Г(k, С) = (k, С)

-скаляр, выбираемый на каждом шаге из условия минимума функции

(11)

то алгоритм оптимизации называют алгоритмом наискорейшего спуска.

Дискретному алгоритму в разностной форме (10) соответствует дискретная замкнутая система, блок-схема которой представлена на рис. 1, где МУ - матричный усилитель, определяемый выражением Г(k); ДИ - дискретный интегратор (дигратор); НП - нелинейный преобразователь, определяющий градиент критерия качества В соответствии с уравнением первой разности запишем

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

Алгоритмы оптимизации (6), (8), (9) и (10) относятся к одношаговым алгоритмам и являются алгоритмами первого порядка, так как представляются в виде векторного разностного уравнения первого порядка.

Если функционал J (С) имеет несколько экстремумов, то одношаговые алгоритмы позволяют определить только локальные экстремумы. Поэтому необходимо выполнить расчеты при различных начальных векторах Сi (0) и полученные J (Ci°) сравнить, чтобы определить вектор С° , соответствующий глобальному (абсолютному) экстремуму.

алгоритм оптимизация экстремум

Рис. 1

Рис. 2

Для нахождения глобального экстремума можно применить многошаговые алгоритмы, например алгоритм вида

(12)

Где

,

который при

s = s1 = 1

вырождается в одно шаговый алгоритм (10).

Выбирая ат (k), am (k) и Г (/г), можно добиться того, чтобы алгоритм (12) был малочувствительным к локальным экстремумам. Применение многошагового алгоритма (12) в задачах оптимизации, когда J (С) имеет единственный экстремум, позволяет повысить помехоустойчивость и ускорить сходимость при определении С0.

Дискретным алгоритмам оптимизации можно поставить в соответствие непрерывные алгоритмы. Если, например, в (10) заменить k на t, а разности на производные, то при предельном переходе получим непрырывный алгоритм оптимизации первого порядка в виде векторного дифференциального уравнения первого порядка относительно вектора С (t):

. (13)

Непрерывному алгоритму (13) соответствует непрерывная замкнутая система; ее условная схема аналогична схеме, изображенной на рис. 1, в которой следует заменить Г (k) на Г (t) и дигратор на непрерывный матричный интегратор. Непрерывный алгоритм (13) можно реализовать на АВМ.

Для определения глобального экстремума и улучшения процессово пределения С° в случае единственного экстремума функционала J (С) можно применить непрерывные алгоритмы высшего порядка в виде векторного дифференциального уравнения s-гo порядка относительно вектора С (t):1

(14)

где - коэффициенты, которые выбирают так, чтобы обеспечить желаемое качество процесса определения Сo. Алгоритмы высшего порядка (14) могут быть реализованы на АВМ.

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

При поисковых алгоритмах измеряют функционал или какие-либо величины, косвенно оценивающие градиент . Введем векторы, компонентами которых являются значения функционала при измененных значениях вектора С (k) на величину «пробного шага» g:

(15)

где - базисные векторы:

е1 = [1 0 ... 0]T; е2 = [0 1 0... 0]T; еn = [00 ...0 1]T.

Введем также вектор, компонентами которого являются значения функционала при неизменных значениях вектора С (k):

.(16)

Тогда градиент можно оценить по формулам при поиске с односторонним «пробным шагом»

(17)

с двусторонними «пробными шагами»

, (18)

где - символ оценки градиента по вектору С.

Поисковый алгоритм оптимизации на основании уравнения (18) с учетом (16) запишется как

(19)

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

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

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

Если указанные ограничения представлены в виде равенств

g(С) = 0,

то в соответствии с методом множителей Лагранжа записывается функционал

(20)

В этом случае условием минимума являются равенства

(21)

Где

матрица размерности ; = 1, 2, … , n; = 1, 2, ..., п.

Алгоритмы оптимизации в задачах на условный экстремум, определяющие Сo и °, на основании (21) запишутся как

(22)

Алгоритмам (22) можно поставить в соответствие непрерывные алгоритмы, записать многошаговые алгоритмы типа (12) и поисковые алгоритмы типа (19).

Алгоритмам (22) соответствует дискретная замкнутая система, схема которой в отличие от схемы, изображенной на рис. 1, будет иметь дополнительный контур для определения вектора (k - 1), необходимого для вычисления .

Если ограничения представлены в виде неравенств

g(С) ? 0,

то условия минимума (21) записывают в соответствии с теоремой Куна - Таккера, после чего составляют алгоритмы оптимизации.

Вероятностные алгоритмы. Для вероятностных задач оптимизации критерий качества является статистической оценкой функционала Q(X, С) в виде его среднего значения по множеству реализаций [см. (2)] или по времени [см. (3)]. Уравнения ограничений для таких объектов также представляют средними значениями

h (С) = Мх {g (X, С)} ? 0.(23)

Задача оптимизации в этом случае состоит в том, чтобы подобрать такой оптимальный вектор С0, при котором среднее значение функционала имеет минимум.

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

Рис. 3

Условие оптимальности (4) для стохастических объектов записывается уравнением

(24)

в котором неизвестен градиент , а известны лишь реализации .

Если выбрать надлежащим образом матрицу Г(k), то вероятностный алгоритм оптимизации можно представить подобно регулярным алгоритмам в рекуррентной, разностной и суммарной формах соответственно:

(25)

(26)

(27)

Вероятностные алгоритмы называют алгоритмами стохастической аппроксимации.

Существенным отличием вероятностных алгоритмов от регулярных является то, что при

С = Сo

,(28)

в то время как для регулярных алгоритмов

.

Из-за этой особенности матрицу Г(k) необходимо выбирать так, чтобы обеспечить сходимость вероятностных алгоритмов. В простейших вероятностных алгоритмах ее выбирают в виде диагональной

(29)

В частных случаях принимают одинаковые компоненты:

.

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

(30)

Алгоритму (30) соответствует дискретная замкнутая система, блок-схема которой представлена на рис. 3.

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

Размещено на Allbest.ru

...

Подобные документы

  • Развитие численных линейных методов решения задач линейного программирования. Знакомство с методами поиска целевой функции: равномерный симплекс, методы Коши, Ньютона, сопряжённого градиенты, квазиньютоновский метод. Алгоритмы нахождения экстремума.

    курсовая работа [716,1 K], добавлен 12.07.2012

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

    учебное пособие [340,6 K], добавлен 02.03.2010

  • История слова "алгоритм", понятие, свойства, виды. Алгоритм Евклида, решето Эратосфена; математические алгоритмы при действии с числами и решении уравнений. Требования к алгоритмам: формализация входных данных, память, дискретность, детерминированность.

    реферат [1,1 M], добавлен 14.05.2015

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

    курсовая работа [1,1 M], добавлен 23.11.2010

  • Математическое программирование - область математики, в которой изучаются методы решения задач условной оптимизации. Основные понятия и определения в задачах оптимизации. Динамическое программирование – математический метод поиска оптимального управления.

    презентация [112,6 K], добавлен 23.06.2013

  • Методы условной и безусловной нелинейной оптимизации. Исследование функции на безусловный экстремум. Численные методы минимизации функции. Минимизация со смешанными ограничениями. Седловые точки функции Лагранжа. Использование пакетов MS Excel и Matlab.

    лабораторная работа [600,0 K], добавлен 06.07.2009

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

    курсовая работа [393,2 K], добавлен 18.06.2011

  • Решение дифференциальных уравнений в частных производных. Метод минимальных невязок, минимальных поправок, скорейшего спуска, сопряженных градиентов. Алгоритмы и блок-схемы решения. Руководство пользователя программы. Решение системы с матрицей.

    курсовая работа [380,3 K], добавлен 21.01.2014

  • Собственные значения и вектора матрицы. Применение итерационного метода вращений Якоби для решения симметричной полной проблемы собственных значений эрмитовых матриц. Алгоритмы решения задач и их реализация на современных языках программирования.

    курсовая работа [321,6 K], добавлен 15.11.2015

  • Теоретические основы и предмет преподавания математики. Понятие и сущность индукции, дедукции и аналогии. Алгоритмы решения математических задач. Методика введения отрицательных, дробных и действительных чисел. Характеристика алгебраических выражений.

    курс лекций [728,4 K], добавлен 30.04.2010

  • Некоторые математические вопросы теории обслуживания сложных систем. Организация обслуживания при ограниченной информации о надёжности системы. Алгоритмы безотказной работы системы и нахождение времени плановой предупредительной профилактики систем.

    реферат [1,4 M], добавлен 19.06.2008

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

    контрольная работа [1,4 M], добавлен 16.08.2010

  • Преимущества и недостатки параметрических методов оценки. Процедура Роббинса-Монро, алгоритмы Литвакова и Кестена. Исследование стохастических аппроксимаций непараметрического типа. Непараметрическая оценка плотности вероятности и кривой регрессии.

    реферат [470,6 K], добавлен 22.04.2014

  • Метод потенциальных функций, его использование для решения задач обучения машин распознаванию образов. Основные понятия: признаки объекта, пространство рецепторов. Алгоритмы, основанные на методе потенциалов. Потенциалы в пространстве рецепторов.

    презентация [123,8 K], добавлен 30.10.2013

  • Поиск оптимальных значений некоторых параметров в процессе решения задачи оптимизации. Сравнение двух альтернативных решений с помощью целевой функции. Теорема Вейерштрасса. Численные методы поиска экстремальных значений функций. Погрешность решения.

    презентация [80,6 K], добавлен 18.04.2013

  • Математические методы распознавания (классификации с учителем) и прогноза. Кластеризация как поиск оптимального разбиения и покрытия. Алгоритмы распознавания и интеллектуального анализа данных. Области практического применения систем распознавания.

    учебное пособие [2,1 M], добавлен 14.06.2014

  • Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.

    курсовая работа [541,3 K], добавлен 08.10.2015

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

    дипломная работа [462,8 K], добавлен 09.01.2009

  • Проектирование методов математического моделирования и оптимизации проектных решений. Использование кусочной интерполяции при решении задач строительства автомобильных дорог. Методы линейного программирования. Решение специальных транспортных задач.

    методичка [690,6 K], добавлен 26.01.2015

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

    курсовая работа [414,1 K], добавлен 20.01.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.