Содержание
Содержание
Содержание
Поиск эффективных решений задачи оптимизации всегда был одним из наиболее приоритетных направлений прикладной математики. Высокая заинтересованность результатами данной области прикладной математики обусловлена как наличием в природе естественных оптимизационных процессов, так и стремлением человека к наилучшей организации своей деятельности. Таким образом оптимизация является важным инструментом при исследование рзличных физических систем и при принятии решений. Целью данной работы является исследование подходов, базирующихся на использование локально-детерминистических методов, к решению различных оптимизационных задач, которые возникают при моделировании сложных динамических систем, а также построение эффективных локально-детерминистических алгоритмов оптимизации для решения этих задач. Для достижения поставленных целей в данной работе анализируется специфика, характерные черты и различные способы постановки наиболее важных в моделировании сложных динамических систем оптимизационных задач, а также изучаются известные алгоритмы для решения оптимизационных задач и реализующие их программные пакеты. Практическим результатом работы является разработка подсистемы оптимизации и внедрение её в моделирующую среду Diana , на базе которой и проводятся дальнейшие исследования. Предполагается, что в рамках данной работы будет разработан новый эффективный алгоритм оптимизации или группа алгоритмов , ориентированный на решение специфических задач, возникающих при моделировании сложных динамических систем. Детальное рассмотрение всевозможных оптимизационных задач, возникающиих при моделировании СДС, позволяет разбить их на две группы. К первой группе относятся задачи, в которых целевая функция и функции ограничения задаются формулами в явном виде. Подобные задачи обычно возникают в качестве подзадач других более крупных задач моделирования. Они характеризуются незначительной ценой вычисления целевой функции, а также малым либо средним числом неизвестных. Градиент для таких задач вычисляется зачастую с использованием конечноразностных схем отдельно от целевой функции. Наиболее часто область допустимых значений для задач первой группы полностью определяется функциональными ограничениями. Решение таких задач, в основном, не требует больших временных затрат и может быть найдено с использованием классических оптимизационных схем. Ко второй группе относятся задачи, в которых целевая функция задаётся в виде суперпозиции некоторой функции и функции-решения системы дифференциальных уравнений ДУ , описываюшей модель. Если модель описывается системой ДУ вида: Число неизвестных в данных задачах не велико и редко превышает В связи с необходимостью интегрирования траектории при расчёте значения целевой функции, ее вычисление требует больших вычислительных затрат. Поскольку большинство специализированных интеграторов выполняют интегрирование траектории и анализ чувствительностей одновременно, то расчёт целевой функции и её градиента либо якобиана её составляющих могут быть выполнены также одновременно с минимальными дополнительными вычислительными издержками. Возможные случаи несходимости алгоритмов решения ДУ и невычислимости некоторых выражений, входящих в состав модельных уравнений, обуславливают появление прямых ограничений, которые на практике сложно или невозможно заменить эквивалентными функциональными ограничениями. Целевая функция в таких задачах зачастую характеризуется высокой нелинейностью и имеет множество локальных минимумов, что требует применения особых методов до начала использования локально-детермического алгоритма, обеспечивающих хорошее начальное приближение, а следовательно и глобализацию сходимости. Часто данные задачи плохо масштабируемы. Из перечисленных особенностей следует, что задачи, принадлежащие ко второй группе, требуют значительной переработки классических алгоритмов оптимизации, ориентируя данные алгоритмы на как можно меньшее число вычислений целевой функции и учёт возникающих прямых ограничений. Ко второй группе задач относится, в частности, задача оценки параметров модели. Постановка данной задачи может быть произведена следующим образом [6, 8, 13, 14]. Дана модель, описываемая системой ДУ 1. В то же время известна матрица замеров Y , описывающая экспериментальные данные. Элементы матрицы Y являются замерами переменных состояния, с учётом функций наблюдения, в дискретные моменты времени и описываются уравнением: Целью является оценка вектора искомых параметров, исходя из экспериментальных данных. Обычно для решения этой задачи используют принцип максимального правдоподобия. Тогда в случае распределения шума наблюдения по закону Гаусса задача принимает вид: Доверительные интервалы для оцениваемых величин определяются посредством использования информационно матрицы Фишера [6, 12, 14] или других схожих методов [8]. Важной проблемой при использовании локально-детерминистических методов в данном случае является выбор начальной точки. Существует два подхода к решению этой проблемы. Первый из них называется подходом с оценкой начальной точки initial-value approach [8]. Он заключается в том, что после подходящего выбора начального приближения модельные уравнения интегрируются на всём временном промежутке оценки параметров, а затем вычисляется функция по формуле 1. Данный подход требует использования на начальном этапе метода, обеспечивающего грубое приближение к глобальному минимуму. Наиболее простым выходом из этой ситуации является использование некоторого глобального стохастического оптимизатора. В данной работе в качестве такового выбран генетический алгоритм оптимизации. Существует и альтернативный подход, именуемый методом множественных стрельб ММС [6, 8, 13, 14], впервые предложенный ван Домселааром и Хемкером и теоретически обоснованный Боком , Данный подход заключается в следующем. Каждому из подинтервалов ставится в соответствие свой кусок интегрируемой траектории с собственными неизвестными начальными значениями переменных состояния x 0 k. В каждый интервал должна попадать по крайней мере одна экспериментальная точка. Поскольку результирующая траектория не должна иметь разрывов, к результирующим ограничениям добавляется ряд ограничений, обеспечивающих непрерывность результирующей траектории в момент переходов между интервалами. Окончательно задача принимает следующий вид: Несмотря на значительный рост числа неизвестных в ММС, данная схема обладает рядом преимуществ [13]: Упрощается учёт априорной информации о переменных состояния, определяемой по значениям замеров, при выборе начального приближения. Подходящий выбор начальной точки обычно позволяет избежать выхода на локальный минимум задачи. Данный метод является численно устойчивым и позволяет решать задачу оценки параметров даже для нестабильных и хоатических систем. Особая структура целевой функции позволяет упростить реализацию параллельных алгоритмов её подсчёта. Существует несколько альтернативных подходов к классификации локально-детерминистических алгоритмов оптимизации рис. Критерием разделения алгоритмов на группы в первом подходе является класс оптимизационных задач , которые позволяет решить алгоритм [1, 2, 3, 5]. Поскольку наиболее важными частными случаями задачи математического программирования являются задача безусловной оптимизации, задача оптимизации с прямыми ограничениями на переменные, задача условной оптимизации с ограничениями-равенствами, задача условной оптимизации со смешанными ограничениями и задача минимизации функций нелинейных квадратов, то согласно этому критерию выделяют следующие группы алгоритмов: Второй подход основывается на учёте различных критериев, которые определяют характерные черты реализации алгоритмов [4, 11]. Согласно одному из таких критериев методы оптимизации делятся на активные последовательные и пассивные. В пассивных методах все точки для дальнейшего анализа выбираются одновременно до начала вычислений. В активных методах точки выбираются последовательно, выбор каждой последующей точки зависит от значений предыдущих. Другим критерием классификации является информация о функции, которую требует алгоритм. Если для успешного выполнения алгоритма достаточно лишь информации о значение функции в точке, то такой алгоритм относится к алгоритмам нулевого порядка метод Гаусса, симплексный метод Недлера-Мида, методы поворота системи координат Хука-Дживса, классический Розенброка, метод Пауэлла и т. Если дополнительно требуется знание о градиенте, то алгоритм относится к алгоритмам первого порядка. Алгоритмы второго порядка кроме знания значение функции в точке и её градиента, нуждаются также в информации о матрице Гессе метод Ньютона, классические SQP-схемы. Среди локально-детерминистических методов оптимизации наиболее представительную группу составляют методы спуска , которые в свою очередь базируются на двух моделях. Первую модель образуют методы линейного поиска , в которых на каждой итерации направление спуска определяется однозначно, а оцениванию подлежит длина шага. Вторую модель образуют методы доверительных областей trust-region , в которых наоборот на каждой итерации оценивается направление спуска. Среди методов спуска первого порядка можно выделить такие группы методов [1, 9]: На сегодняшний день разработано множество оптимизационных программ, реализующих локально детерминистические алгоритмы. Многие из этих кодов распространяется под лицензией GPL, часть напротив является платной либо частично платной. Условно всё оптимизационное ПО можно разбить на три группы рис. Часть из известных оптимизационных пакетов ориентирована на решение только одного класса оптимизационных задач, но некоторые пакеты способны эффективно решать несколько классов задач. Характерной чертой пакетов для решения задачи оптимизации с прямыми ограничениями на переменные является то, что они достаточно эффективно справляются с задачей безусловной оптимизации. Большинство оптимизационных пакетов реализованы на языке Fortran. Наиболее известными из них являются LANCELOT и MERLIN. Именно с эффективностью реализованных в них процедур обычно производится сравнение эффективности новых алгоритмов. LANCELOT является одной из наиболее мощных библиотек оптимизационных алгоритмов, ориентированных прежде всего на решение задач большой размерности. Язык реализации библиотеки — ANSI Fortran Хотя недавно вышла адаптация пакета LANCELOT на Fortran На данный момент LANCELOT разработкой занимается Council for the Central Laboratory of the Research Councils CCLRC. Пакет MERLIN был разработан в университете г. Иоаннина Греция и первоначально предназначался для решения задачи оптимизации с прямыми ограничениями на переменные. Сейчас функциональность пакета значительно расширилась. Одним из наиболее известных пакетов для решения задач безусловной оптимизации и оптимизации с прямыми ограничениями на переменные на сегодня является пакет L-BFGS-B, разработанный в Северо-Западном университете США. Численные библиотеки NAG, HSL и IMSL среди прочих неспециализированных численных библиотек выделяются наиболее развитой системой алгоритмов оптимизации. В библиотеке NAG алгоритмы оптимизации собраны в папку E Разработкой библиотеки занимается The Numerical Algorithms Group Ltd. На данный момент доступны реализации библиотеки на Fortran и C, в недавнем прошлом сушествовали только Fortran77 и Algol68 версии библиотеки. Библиотека HSL Harwell Subroutine Library разрабатывается CCLRC в деревушке Харвел неподалёку от Оксфордшира. На данный моент библиотека HSL реализована только на ISO Fortran. Последний известный релиз библиотеки состоялся в сентябре Алгоритмы оптимизации библиотеки IMSL собраны в главу 8 её реализации на языке ANSI Fortran. Реализация библиотеки на C содержит только часть этих алгоритмов. Доступны также ограниченные реализации этой библиотеке на Java и C. Разработкой библиотеки занимается компания Visual Numerics Inc. Системы оптимизации и моделирующие среды обычно представляют из себя развитый законченый продукт и имеют встроенный собственный либо стандартизированный язык моделирования, позволяющий достаточно просто формулировать оптимизационные задачи. Обычно такие системы и среды предоставляют интерфейс для подключения внешних пакетов, реализованных на Fortrn и C. Более того, моделирующая среда GAMS, разработанная GAMS Development Corporation, не имеет собственных оптимизационных кодов, а лишь предоставляет интерфейс для подключения пакета MINOS. Системы оптимизации Speakeasy также имеет интерфейс для подключения внешней библиотеки NAG, но в то же время в ней содержатся и "родные" пакеты, такие как EISPACK и FFTPACK. AMPL представляет из себя специализированный достаточно гибкий язык моделирования для постановки и решения задач математического программирования. Matlab является наиболее известной системой из вышеперечисленных. В данной системе реализованы квазиньютоновские алгоритмы, метод Недлера-Мида, метод Ньютона, метод Левенберга-Маркарда и т. Существуют также пакеты, ориентированные на решение задачи оценки параметров. К ним следует отнести пакеты EASY-FIT, разработанный в университете г. Бейрут под руководством проф. Шитковского, и пакет PAREST, разработанный в Мюнхенском техническом университете. Причём в пакете PAREST реализован метод множественных стрельб. К оптимизационному ПО стоит также отнести библиотеку тестовых оптимизационных задач CUTEr, разработанную Н. Данная библиотека, по сути, является стандартом для тестирования алгоритмов оптимизации. Ежегодно появляются десяки публикаций, посвящённых оптимизационным задачам, возникающих при моделировании СДС, и в частности вопросам оценки параметров моделеи. Не смотря на то, что сушествует множество основательных трудов в области оценки параметров [19, 20], метод множественных стрельб достаточно слабо освещён в литературе. Бока, в которых проведено обоснование и доказательство практической ценности ММС, из-за малого тиража практически недоступны. Статей посвящённых ММС также относительно не много. В большинстве из них производится только обзор метода, а также способов его реализации. Анализ сходимости и другие важные вещи там отсутствуют. Существует множество книг и статей, посвящённых локально-детерминистическим методам оптимизации. В части из них авторы пытаются охватить весь круг известных на данный момент локально-детерминистическим алгоритмов оптимизации, в некоторых работах авторы освещают лишь отдельный выбранный алгоритм либо группу методов. Поскольку в данной работе в первую очередь планируется реализовать модификацию БФГШ-метода для решения задачи оптимизации с прямыми ограничениями на переменные, то в дальнейшем здесь будут рассматриваться только публикации, в которых описывается БФГШ-метод. Метод Бройдена-Флетчера-Голдфарба-Шэнно БФГШ был предложен в году [] как развитие общей идеи квазиньютоновских методов, предложенной Давидоном. На сегодняшний день этот метод является наиболее эффективным квазиньютоновским методом. Ноцедалем была предложена модификация БФГШ-алгоритма, требующая небольших затрат оперативной памяти и известная под названием LBFGS-метода [1, 7, 21], а в году им же в соавторстве с Р. Бёрдом был предложен L-BFGS-B-метод, позволяющий решать не только задачи безусловной оптимизации, но и задачи оптимизации с прямыми ограничениями на переменные [7]. В году появился пакет, реализующий LBFGS-B-алгоритм на языке Fortran. В году вышел последний релиз этого пакета. В дальнейшем публикации, касающиеся LBFGS появлялись ежегодно, но принципиально новых идей по модификацие LBFGS-алгоритма в них не было. В данной работе для решения оптимизационных задач, возникающих при моделировании СДС, используется подход с оценкой начальной точки см. При этом начальное приближение к глобальному минимуму отыскивается с помощью генетического алгоритма оптимизации. В случае задачи оценки параметров дополнительно применяется метод множественных стрельб см. В качестве основного алгоритма оптимизации на данном этапе используется LBFGS-B-метод [7]. Направление в данном методе ищется согласно формуле 4. Для учёта ограничений в LBFGS-B-алгоритме используется схема, идентичная той, которая применяется в методе проекции градиента. Классический LBFGS-B-алгоритм использует при выборе длины шага процедуру "бэктрэкинга" "backtracking". В данной работе планируется несколько улучшить классическую схему LBFGS-B-метода путём использования в нём при выборе длины шага интерполяционной процедуры. В данной работе были кратко рассмотрены основные классы оптимизационных задач, выделены их особенности и рассмотрены подходы, позволяющие находить их решения. Также здесь приведен краткий обзор алгоритмов оптимизации, существующего оптимизационного ПО и литературы по данной тематике. На текущий момент в рамках работы разработаны и внедрены в моделирующую среду Diana интерфейсы основных оптимизационных задач и решателей данных задач. Был дополнительно реализован простой градиентный алгоритм алгоритм с модификацией Армихо [9], но в связи с тем, что данный алгоритм не справлялся с решением плохо масштабированных задач, от дальнейших исследований в данном направление пришлось отказаться. Вместо этого в моделирующую среду Diana мной был имплементирован код LBFGS-B-алгоритма, разработанный П. Навигация Библиотека Ссылки Поиск Автобиография Дневник. Содержание Введение Задачи оптимизации, возникающие при моделировании СДС Особенности оптимизационных задач, возникающих при моделировании СДС Задача оценки параметров модели. Метод множественных стрельб Алгоритмы оптимизации Классификация алгоритмов оптимизации Обзор существующего оптимизационного ПО Обзор публиуаций по теме Краткое описание используемых алгоритмов Выводы Список использованной литературы. Разработал Sergiy Gogolenko Май
Данный раздел Стандартные алгоритмы представляет собой введение в простановку задач различных методов оптимизации и включает в себя описание алгоритмов средней размерности то есть стандартных алгоритмов , используемых в данном тулбоксе. Указанные алгоритмы были выбраны вследствие их достаточно высокой устойчивости и итерационной эффективности. Выбор постановки задачи например, без наличия ограничений, метод наименьших квадратов, при наличии ограничений, задача минимакса, многоцелевая задача или задача достижения цели определяется сущностью решаемой задачи и требуемой эффективностью решения. В разделе содержится представление оптимизации как метода поиска некоего набора параметров, которые можно будет в неком смысле считать оптимальными. Обсуждается применение квазиньютоновского метода и метода линейного поиска для оптимизации без ограничений. Так же приводятся детали выполнения коррекции матрицы Гессе и этапов линейного поиска в квазиньютоновском алгоритме применительно к функции fminunc. Обсуждается применение метода Ньютона-Гаусса и метода Левенберга-Маркварда для нелинейной оптимизации с применением метода наименьших квадратов LS. Так же приводятся детали реализации методов Ньютона-Гаусса и Левенберга-Маркварда применительно к подпрограмм нелинейной оптимизации методом наименьших квадратов при использовании функций lsqnonlin и lsqcurvefit. Обсуждается применение метода Ньютона-Гаусса, метода Ньютона и метода ломаных доверительных областей для решения систем нелинейных уравнений. Так же приводятся детали реализации методов Ньютона-Гаусса и метода ломаных доверительных областей применительно к функции fsolve. Обсуждается применение уравнений Куна-Таккера KT как некой базы метода Последовательного Квадратичного Программирования SQP. Так же приводятся детали реализации методов корректировки матрицы Гессе, решения задач квадратичного программирования, а так же линейного поиска и этапы расчета по алгоритму SQP применительно к функциям fmincon, fminimax, fgoalattain иfseminf. Приводится введение в многоцелевую оптимизацию, а также обсуждаются стратегии обращения с конкурирующими целями. Кроме того приводятся детали реализации метода Достижения цели и предлагается их посдедующее улучшение посредством SQP метода применительно к данной задаче. Приводится список литературы в обоснование использованных методов применительно к алгоритмам средней размерности. Термин средней размерности не является общестандартным термином и используется только как для введения отличия используемых алгоритмов от алгоритмов большой размерности, представленных в разделе "Алгоритмы большой размерности". В более широком смысле эта формулировка представляет собой минимизацию или максимизацию целевой функции, f x , при наличии ограничений в форме. Общая формулировка GP задачи параметрической оптимизации представляется следующим образом: Эффективность и точность решений данной задачи зависит как от числа параметров и ограничений, так и от вида целевой функции. При линейных ограничениях и линейной целевой функции приведенная задача оптимизации называется задачей линейного программирования LP. Задача квадратичного программирования QP представляет собой минимизацию или максимизацию квадратичной по аргументам целевой функции при наличии ограничений линейного вида. Постановки задач типа LP и QP представляют собой достаточно реалистически достижимыми задачами. Более сложной является обобщающая задача нелинейного программирования NP , когда целевая функция и ограничения представляют собой некие нелинейные функции от исходных аргументов. NP , в общем случае, решается с помощью итерационных методов с коррекцией направления поиска на каждой итерации. Существующие алгоритмы оптимизации без наличия ограничений могут быть разделены на две группы - алгоритмы, базирующиеся на использовании производных минимизируемой функции градиентные и методы второго порядка , и алгоритмы, использующие только значения функции безградиентные. Безградиентные методы например, симплексный метод Нелдера-Мида [32] более пригодны для задач, где минимизируемая функция является существенно нелинейной функцией или имеет разрывы. Градиентные методы методы первого порядка обычно эффективны в случаях целевых функций, непрерывных вместе с первыми производными. Методы второго порядка, такие как метод Ньютона, применяются реже, поскольку требуют больших вычислительных затрат для расчета матриц вторых производных. Градиентные методы используют информацию о наклоне функции для выбора направления поиска экстремума. В одном из таких методов - наискорейшего спуска - на каждой итерации движение к точке минимума осуществляется в направлении где - вектор-градиент целевой функции f x. Этот метод весьма неэффективен в ситуациях, когда поверхность целевой функции имеет узкие "овраги", как, например, у известной функции Розенброка. Минимальное значение данной функции, как нетрудно видеть, равно нулю при. Графическое представление изолиний данной функции приведено на Рис. Оптимизация была прервано после итераций, хотя все еще на значительном расстоянии от точки минимума. Пунктиром представлены области, где согласно данному методу проходит непрерывный зигзагообразный переход с одной стороны оврага на другую. Отметим, что при направлении к центру данного графика число увеличенных шагов отмечается в случае, когда они лежат точно в центре оврага. Эту функцию из-за своеобразной формы линий равного уровня часто называют "банановой" функцией и используют как тестовую при проверке различных методов оптимизации. Изолинии представлены с экспоненциальным приращением вследствие резкого изменения наклона для U-образных оврагов. Copyright — Softline Co. Стандартные алгоритмы Данный раздел Стандартные алгоритмы представляет собой введение в простановку задач различных методов оптимизации и включает в себя описание алгоритмов средней размерности то есть стандартных алгоритмов , используемых в данном тулбоксе. Данный раздел включает в себя следующие пункты.
Универсальный справочник прораба
Как вырастить ананас в домашних условиях подробное
Интернет через точку доступа
Круглый стол на тему проблем
Ура ру новости тиу