Содержание к диссертации
Введение
Глава I. Основы теории полиэдральной оптимизации 26
1.1. Элементы полиэдрального анализа 26
1.2. Элементы полиэдрального программирования 44
1.2.1. Постановка и особенности общей задачи полиэдрального программирования 44
1.2.2. Постановка и редукция основных типовых задач полиэдрального программирования к задачам линейного программирования 51
1.2.3. Редукция общей задачи полиэдрального программирования к задаче безусловной полиэдральной оптимизации методом точных полиэдральных штрафов 62
1.3. Элементы полиэдрального исчисления и условия полиэдрального экстремума 73
Выводы по главе 1 86
Глава 2. Численные методы безусловной полиэдральной оптимизации 87
2.1. Задача безусловной полиэдральной оптимизации и современные технологии «жестких» и «мягких» вычислений 87
2.2. Непрямой метод «жестких вычислений»: субградиентный метод оптимизации 93
2.2.1. Основные положения и традиционная вычислительная реализация субградиентного метода оптимизации 93
2.2.2. Нейросетевая реализация субградиентного метода оптимизации 99
2.3. Прямой метод «мягких вычислений»: эволюционный метод оптимизации 105
2.3.1. Стохастическая парадигма оптимизации и концепция эволюционных вычислений 106
2.3.2. Основные положения и алгоритмическая реализация эволюционного метода оптимизации 117
2.3.3. Настройка параметров и тестирование алгоритма эволюционной оптимизации 130
Выводы по главе 2 140
Глава 3. Формализация задач полиэдральной оптимизации дискретньгх процессов управления 141
3.1. Постановка общей задачи оптимизации дискретных процессов управления 141
3.2. Проблема выбора критерия качества и критика парадигмы квадратичной оптимизации 145
3.3. Полиэдральные критерии качества процессов управления 151
3.4. Полиэдральные цели и ограничения процесса управления 160
3.5. Постановка общей задачи полиэдральной оптимизации дискретных процессов управления 165
Выводы по главе 3 166
Глава 4. Полиэдральная стратегия дискретного упреждающего управления 168
4.1. Ретроспектива и современное состояние проблемы упреждающего управления 168
4.2. Идея и особенности полиэдральной стратегии дискретного упреждающего управления 173
4.3. Обоснование полиэдральной стратегии дискретного упреждающего управления 179
4.4. Обобщение полиэдральной стратегии дискретного упреждающего управления на нелинейные объекты 183
4.5. Алгоритмизация полиэдральной стратегии дискретного упреждающего управления 187
Выводы по главе 4 194
Глава 5. Полиэдральный подход к дискретным задачам стабилизации 195
5.1. Задачи предельного быстродействия 195
5.2. Метод полиэдральных функций Ляпунова и задачи стабилизации 204
5.2.1. Полиэдральные функции Ляпунова и узловое условие устойчивости 206
5.2.2. Синтез и оптимизация стабилизирующего управления 212
5.3. Задачи барьерного управления 214
5.3.1. Автомат ограничений и полиэдральная методология барьерного управления 216
5.3.2. Стратегия упреждающего барьерного управления 219
Выводы по главе 5 224
Глава 6. Задачи и методы полиэдральной оптимизации дискретных процессов управления и наблюдения в условиях неопределенности 225
6.1. Драматическая смена парадигм неопределенности и принцип гарантированного результата 225
6.2. Экстремальные возмущающие факторы 236
6.3. Гарантированное и робастное управление в условиях полиэдральной неопределенности 244
6.3.1. Гарантированная позиционная стратегия управления в условиях начальной полиэдральной неопределенности 244
6.3.2. Робастная стратегия упреждающего управления в условиях параметрической полиэдральной неопределенности 250
6.4. Конфликтное управление противоборствующими объектами в условиях преследования 259
6.4.1. Полиэдральные дискретные динамические игры преследования 261
6.4.2. Полиэдральная стратегия преследования на основе принципа гарантированного прогнозируемого промаха 264
6.5. Полиэдральная методология в задачах наблюдения 269
6.5.1. Стохастический и детерминистический подходы к задачам наблюдения 270
6.5.2. Задача дискретного наблюдения состояния системы и дискретное равномерное приближение функций 274
6.5.3. Наблюдение состояния свободной системы 276
6.5.4. Совместное наблюдение состояния системы и внешней среды 279
Выводы по главе 6 282
Заключение 284
Список литературы 287
- Постановка и особенности общей задачи полиэдрального программирования
- Задача безусловной полиэдральной оптимизации и современные технологии «жестких» и «мягких» вычислений
- Постановка общей задачи оптимизации дискретных процессов управления
- Ретроспектива и современное состояние проблемы упреждающего управления
Введение к работе
В современной автоматике на первый план выдвигаются задачи оптимизации процессов управления [24, 149, 176, 317, 324, 330, 368, 439, 443, 452, 465, 571, 649, 673, 706, 754, 772, 800, 802], причем интерес к ним неизбежно будет возрастать в соответствии с манифестом Я.З.Цыпкина [590, с. 116]: «Оптимизировать есе, что оптимизируется, а что не оптимизируется, сделать оптимизируемым». Необходимо отметить, что вследствие прогрессирующего усложнения динамических моделей управляемых объектов и ужесточения требований качества управления большинство оптимизационных задач не поддается точному аналитическому решению и требует применения приближенных численных методов с использованием ЭВМ.
Интенсивные исследования по созданию численных методов решения задач оптимального управления начались в конце 50-х - начале 60-х гг. прошлого столетия и связаны с работами: Д.Е.Охоцимского и Э.Т.Энеева; Л.И.Шатровс-кого; Н.Н.Красовского; И.А.Крылова и Ф.Л.Черноусько; Н.Н.Моисеева; Б.Н. Пшеничного; Н.Е.Кирина; В.Ф.Демьянова; Р.П.Федоренко; Брайсона (А.Е.Вгу-son) и n,eHxeMa(W.F.Denham); Келли (HJ.Kelley); Миеле (A.Miele); Балакриш-нана (A.V.Balakrishnan); Нейштадта (L.W.Neustadt); Итона (J.H.Eaton). К настоящему времени в данной области насчитывается значительное число публикаций, включая известные книги: И.В.Бейко [50]; Н.Е.Кирина [237, 238]; Даера (P.Dyer) и МакРейнольдса (S.McReynolds) [677]; Полака(Е.РоІак) и др. [385, 653]; Н.Н.Моисеева [340]; Брайсона (A.E.Bryson) и Ю-Ши (HoYu-Chi) [77]; Ф.Л.Черноусько и др. [599, 601]; А.И.Пропоя [398]; В.Г.Болтянского [71]; Б.М. Будака и Ф.П.Васильева [82]; Табака (D.Tabak) и Kyo (В.С.Кио) [464]; Р.П.Федоренко [485]; Ю.М.Ермольева, В.П.Гуленко и Т.И.Царенко [202]; В.С.Миха-левича и В.Л.Волковича [331]; И.А.Орурка и др. [22]; Л.Т.Ащепкова, В.П.Булатова и др. [34]; Сингха (M.G.Singh) и Титли (A.Titli) [431]; В.Н.Козлова и др.
[245, 247, 248]; Кларка (F.Clarke) [241]; М.В.Азанова и др. [4]; В.В.Дикусара и А.А.Милютина [174]; В.Ф.Кротова и др. [360]; В.А.Срочко и др. [325, 453, 454]; Р.Габасова, Ф.М.Кирилловой и А.И.Тятюшкина [116, 480]; Н.Д.Егупова и др. [399, 475]; И.Г.Черноруцкого [598]; Ю.Г.Евтушенко и В.Г.Жадана [182, 184] и др.
Численные методы решения задач оптимального управления, в зависимости от непосредственного использования или не использования в них необходимых и/или достаточных условий оптимальности, принято условно разделять на «непрямые» и «прямые» соответственно. «Непрямые» методы оптимизации получили широкое распространение в теоретических исследованиях и оказались малоэффективными для решения практических задач оптимального управления с фазовыми ограничениями: условия оптимальности здесь принимают сложный вид и приводят к неприемлемым с точки зрения вычислительной реализации решениям [28]. Напротив, «прямые» методы оптимизации позволяют достаточно просто учесть фазовые ограничения, причем результаты сравнения и анализа общей тенденции их развития позволяют констатировать, что наиболее эффективным и перспективным средством решения задач оптимального управления с ресурсными и фазовыми ограничениями являются «прямые» методы, основанные на использовании аппарата математического программирования (МП). Как утверждают Табак (D.Tabak) и Kyo (В.С.Кио), «для большого класса задач оптимального управления МП является наиболее эффективным подходом, а в ряде случаев и единственным, фактически применимым на практике».
Среди первых работ, посвященных редукции задачи оптимального управления к задаче МП следует отметить работы Хо (Y.C.Ho) и Брентани (Р.В.Вге-ntani) [725]; Л.С.Гноенского и С.М.Мовшовича [133]; Хензона (M.A.Hanson) [716]; Ю.М.Ермольева и В.П.Гуленко [201]; А.И.Пропоя [395]; А.А.Первозва-нского [370]; Б.М.Будака, Е.М.Берковича и Е.Н.Соловьевой [81]; И.О.Мельца [319]; Табака (D.Tabak) и Куо (В.С.Кио) [801] и др. В настоящее время методы оптимального управления на базе МП прочно вошли в золотой фонд теории оптимального управления и составляют важный раздел современной теории автоматического управления [294, 3.8; 324,т.4,гл.5; 368, гл.9,п.7.3; 465, п. 18.2.5].
И все же, приходится констатировать, что разрабатываемые численные методы оптимизации процессов управления в недостаточной мере используют огромный потенциал аппарата МП.
В последние годы в развитии методов оптимального управления на базе МП наметилась тенденция унификации, связанная с поиском единого универсального метода решения общего класса оптимизационных задач. Однако, еще Курант (R.Courant) и Роббинс (G.Robbins) убедительно подчеркивали, что «занимаясь той или иной научной проблемой, лучше исходить из ее индивидуальных особенностей, чем полагаться на общие методы», а А.Н.Тихонов и Д.П. Костомаров, рассуждая о перспективах развития методов оптимизации отмечали, что «конкретизация задачи, выделение определенных классов функций и областей позволяют провести более глубокое исследование и разработать специальные методы, которые решают задачу исчерпывающим образом». Поскольку современная теория оптимального управления объемлет весьма широкий класс оптимизационных задач с большим разнообразием специфических свойств, можно заключить, что все большую актуальность и практическую і{енность приобретает тенденция спецификации, связанная с выделением отдельных классов оптимизационных задач и поиском методов решения на базе аппарата МП, учитывающего их специфику. В настоящей диссертации выделен такой конкретный и вместе с тем достаточно широкий класс оптимизационных задач, для которых удается получить весьма простые и вместе с тем эффективные алгоритмические решения.
Диссертация посвящена теоретическому исследованию нового класса оптимизационных задач - задач полиэдральной оптимизации дискретных процессов управления динамическими объектами в условиях ресурсных и фазовых ограничений. Полиэдральная оптимизация основывается на аппарате полиэдрального программирования - специального раздела МП, изучающего оптимизационные задачи полиэдральной структуры.
Следует подчеркнуть, что материал диссертации ограничен рассмотрением дискретных задач управления, которые имеют в теории и практике автоматического управления несравненно более важное значение, чем непрерывные
задачи управления. Действительно, задачи дискретного управления возникают в двух случаях: когда процесс управления по своей сути является дискретным и когда для управления непрерывным процессом используется дискретное управляющее устройство, например, ЭВМ. Действительно, все процессы управления социальными и экономическими системами, а также многие процессы управления техническими объектами по своей природе являются дискретными: в них контроль состояния объекта и управление им осуществляется в дискретные моменты времени. Особенно важное значение данные процессы приобрели в связи с внедрением в практику управления средств вычислительной техники. Наконец, решаемые задачи дискретного управления часто являются дискретной формой исходной непрерывной задачи управления, причем, как подчеркивает Полак (E.Polak): «Во многих случаях формулировка задачи оптимального управления в дискретном виде предпочтительнее, чем в непрерывном», поскольку «любой численный метод решения задач непрерывного оптимального управления предполагает ту или иную форму дискретизации задачи».
Тема диссертации - полиэдральная оптимизация дискретных процессов управления: теория и применения.
Объектом диссертационного исследования являются дискретные процессы управления конечномерными динамическими объектами с учетом ресурсных и фазовых ограничений.
Предметом диссертационного исследования является проблематика полиэдральной оптимизации дискретных процессов управления.
Актуальность темы диссертации продиктована теоретическими и практическими аспектами развития современной автоматики и, в частности, необходимостью исследования следующих проблем:
проблемы управления динамическими объектами в условиях фазовых и ресурсных ограничений, уровень теоретической проработки которой не отвечает требованиям практики;
проблемы развития техники классических прямых показателей качества процессов управления в рамках формализма пространства состояний;
проблемы разработки прогностических стратегий управления, продиктованной закономерной сменой классической парадигмы позиционного управления;
проблемы разработки алгоритмов робастного управления в условиях параметрической неопределенности динамики объекта и внешней среды.
Целью диссертационного исследования является разработка теоретических основ и изучение прикладных аспектов полиэдральной оптимизации дискретных процессов управления динамическими объектами.
В диссертации также затронуты вопросы наблюдения состояния управляемых объектов и внешней среды, органично связанные с информационно-измерительными аспектами технической реализации процессов управления.
В соответствии с поставленной целью основными задачами исследования диссертации являются:
Разработка теоретических основ и численных методов полиэдральной оптимизации.
Разработка полиэдральной критериальной базы для дискретных задач управления динамическими объектами с учетом фазовых и ресурсных ограничений.
Постановка и решение на полиэдральной основе ряда ключевых задач оптимизации дискретных процессов управления и наблюдения.
Применение полиэдрального подхода в задачах алгоритмизации управления терминальным маневром летательных аппаратов.
Современное состояние темы диссертации. Ограничимся библиографическим анализом двух фундаментальных составляющих диссертационного исследования - полиэдрального программирования и задачи полиэдральной оптимизации процессов управления.
Обратимся сначала к предыстории полиэдрального программирования. Современное МП состоит из ряда разделов, рассматривающих специальные типы экстремальных задач, различающихся видом целевой и ограничивающих функций. В процессе развития численных методов оптимизации процессов
управления большие надежды возлагались на использование аппарата линейного программирования (ЛП), как наиболее зрелого и развитого раздела МП, обеспеченного мощным арсеналом алгоритмов и программных средств [72, 90, 111, 132, 385, 397, 464, 485, 646, 653, 659, 666, 683, 684, 713, 753, 758, 783, 803, 806, 816]. Однако, данные надежды не оправдались из-за линейной структуры задач ЛП - линейности целевых и ограничивающих функций. Класс задач оптимизации процессов управления, который может быть формализован в терминах ЛП, оказался слишком узким и часто не соответствующим потребностям практических приложений.
По сравнению с ЛП, более перспективным является использование в задачах оптимизации процессов управления полиэдрального программирования (ПП) [536, 545] - нового раздела МП, объектом исследования которого является класс экстремальных задач с полиэдральной структурой, т.е. полиэдральными целевыми и ограничивающими функциями. Полиэдральная методология применима к большинству прикладных оптимизационных задач, причем многие возникающие на практике оптимизационные задачи либо изначально удается формализовать в терминах ПП, либо допускают применение полиэдральной аппроксимации. Важно подчеркнуть, что ключевые конструкции ПП - полиэдральные множества, функции, нормы и метрики, - открывают новые возможности с точки зрения формализации постановки и содержательной интерпретации прикладных задач оптимизации дискретных процессов управления динамическими объектами в условиях ресурсных и фазовых ограничений.
ПП, введенное впервые в работе [505], занимает «промежуточное» место между линейным и выпуклым программированиями, являясь обобщением первого и частным случаем второго. Более точно ПП можно рассматривать как современную трактовку, развитие и обобщение так называемого кусочно-линейного программирования (КЛП) [435, с.517; 619, с.231-232], в задачах которого целевая и ограничивающие функции являются выпуклыми кусочно-линейными функциями. Основные положения КЛП были сформулированы еще в 60-х гг. прошлого столетия в известных книгах Е.Г.Голыптейна, Д.Б.Юдина [136, гл.7] и С.И.Зуховицкого, Л.И.Авдеевой [217, гл.V]. Среди немногочисленных иссле-
дований, так или иначе затрагивающих вопросы КЛП, можно выделить работы: Агхара (W.G.Aghar) и Уэйлеса (T.D.Walace) [624]; С.И.Зуховицкого [216]; В.И. Мудрова [345]; Бен-Исраэля (A. Ben-Israel) и Чарнеса (A. Charnes) [640], Е.Г. Гольштейна [134, с.31]; В.П.Булатова [90,с.24]; Р.П.Федоренко [485, с. 431-436]; Е.П.Волокитина [107]; Р.Габасова и Ф.М.Кирилловой [110,с.341-346]; Е.И.Шилкиной [609], С.В.Плотникова [383, с.83-118]; Мельцера (D.Meltzer) [760]; Крифганза(А.Кгірґапг) и Шульца (R.Schulze) [746]; Бенчекроуна (В. Benchekroun) [639]; Гороховика (V.V.Gorokhovick) и Зорко (O.I.Zorko) [710]; В.Н.Козлова [245, с. 136-137; 246]; И.И.Еремина [193, 196]).
Несмотря на 40-летнюю историю своего существования, КЛП практически отсутствует в современной учебной и монографической литературе по МП, а задачи КЛП именуются нестандартными, либо специальными задачами ЛП. В связи с этим введение автором специального самостоятельного раздела МП под названием «полиэдральное программирование» является принципиальным и вполне оправданным. Данный термин более адекватно отражает существо рассматриваемых задач, позволяет избежать терминологическую путаность и привнести необходимую строгость в общую классификацию разделов МП. Кстати, словосочетание «полиэдральное программирование» (точнее «сепарабельное полиэдральное выпуклое программирование»), впервые встречается в 1992 г. в монографии А.Д.Гвишиани и В.А.Гурвича [122], а те или иные полиэдральные категории (объектами которых являются полиэдры), связанные с задачами оптимизации и управления, в последнее десятилетие все чаще встречаются в отечественной научной и учебной литературе. Здесь можно указать работы: И.И. Еремина, Р.Габасова, А.Б.Куржанского, Н.А.Кузнецова, Б.П.Дербеневой, А.В. Лотова, Г.К.Каменева, Р.В.Ефремова, Е.К.Костоусовой, С.Б.Пельцвергера, Л.И. Микулича, А.С.Беленького, Е.В.Гончарова и др., в которых используются такие выражения, как: полиэдральное оценивание и полиэдральная аппроксимация областей достижимости систем, полиэдральная оптимизация и оптимизация в полиэдральной норме, полиэдральные множества допустимых стратегий, алгоритмы полиэдральной аппроксимации в задачах фильтрации, оптимизация систем управления с полиэдральными ограничениями, полиэдральные методы в
задачах управления и т.п.
Следует отметить, что к разработке теоретических основ 1111 наиболее близки работы И.И.Еремина последнего десятилетия [192, 193, 196], связанные с исследованием задач КЛП.
Обратимся теперь к предыстории задач полиэдральной оптимизации процессов управления. Критериальная база задач оптимального управления основана на формализации представлений о качестве процессов управления. Проблема качества процессов управления составляет один из наиболее консервативных (по Я.З.Цыпкину «вечно юных») и слабо развивающихся разделов современной теории автоматического управления. В большинстве работ, связанных с выбором критерия качества оптимизируемых автоматических систем, утрачена преемственность с интуитивно ясными и содержательными классическими представлениями о качестве процессов управления, выработанными отечественной автоматикой еще в 40-60-е гг. прошлого столетия. В результате, сегодня в теории и практике оптимизации автоматических систем «безраздельно господствуют» квадратичные критерии качества и порождаемые ими задачи квадратичной оптимизации, именуемые задачами аналитического конструирования оптимальных регуляторов (АКОР). Несмотря на чрезвычайную популярность, концептуальные основы АКОР неоднократно подвергались резкой критике известными отечественными и зарубежными учеными, включая В.В.Со-лодовникова, Н.Н.Моисеева, Я.З.Цыпкина, А.М.Баткова, С.В.Емельянова, С.К. Коровина, А.А.Первозванского, А.А.Колесникова, В.Н.Букова, Беллмана (R.E. Bellman), Уонэма (W.M. Wonham), а также самих основоположников теории АКОР А.М.Летова и Калмана (R.E.Kalman). Данная критика обусловлена отсутствием ясного физического смысла оптимизируемых квадратичных критериев, невозможностью учесть локальные свойства переходных процессов и установить прямые ограничения на фазовые переменные. Кроме того, инженерную ценность методологии АКОР ставят под сомнение результаты решения обратной задачи АКОР, согласно которой любая асимптотически устойчивая замкнутая автоматическая система (даже со сколь угодно неудовлетворительными прямыми показателями качества переходных процессов) является оптимальной
в смысле некоторого квадратичного критерия качества.
В потоке работ, посвященных проблеме качества процессов управления, имеется также и цикл работ автора, отражающих ее идейную эволюцию [444 -451, 491, 492, 494-497, 500, 501, 507, 508, 511, 514, 518, 520, 521, 526, 529, 530, 531, 533, 535, 538, 539, 540, 541, 547-549, 552-555, 558, 559, 565, 566, 688, 689]. В этих работах проведено систематическое исследование проблемы качества для широкого класса конечномерных динамических объектов: линейных и нелинейных, стационарных и нестационарных, одноканальных и многоканальных. Результаты исследований, в частности, затронули критериальные основы теории АКОР и послужили толчком к разработке альтернативной к ней теории полиэдральной оптимизации процессов управления.
Еще Беллман (R.E.Bellman) подчеркивал, что в теории АКОР исходную задачу «заменяют менее важной задачей минимизации квадратичного функционала, потому что она, в противоположность первой, более реалистичной задаче, поддается изучению с помощью классических методов». Напротив к реалистичным задачам, максимально приближенным к практическим нуждам автоматики, правомерно относить задачи полиэдральной оптимизации дискретных процессов управления, сформулированные впервые в работах автора [532, 536, 542 -545]. Отличительной особенностью данных задач является их полиэдральная структура: все ключевые элементы задачи - цель управления, ограничения и критерии качества - являются полиэдральными.
Обращаясь к ретроспективе полиэдральных критериев качества процессов управления, следует отметить, что отдельные их виды имеют давнюю историю и в период зарождения не могли интерпретироваться с позиций полиэдрального анализа. Это касается, прежде всего, известного критерия равномерного приближения Чебышева, впервые введенного в теорию и практику автоматических систем сначала Б.В.Булгаковым в конце 1930-х гг. для задач накопления возмущений [91], а затем в 1953 г. В.В.Солодовниковым [441] и А.А.Фе-льдбаумом [488] для общего класса задач управления как универсального прямого критерия качества процессов управления - максимального отклонения или перерегулирования. Важность данного критерия качества в теории и практике
автоматических систем подчеркивали: Беллман (R.E.Bellman), Гликсберг (I.Gli-cksburg), Гросс (О.Gross), Дрейфус (S.E.Dreyfus), Джонсон (C.D.Johnson), Варга (J.Warga), Куликовский (R.Kulikowski), Нейштадт (L.W.Neustad), Портер (W.A. Porter), Далех (M.A.Dahleh), Пирсон (J.B.Pearson), Е.А.Барбашин, Н.Н.Красовс-кий, Н.Н.Моисеев, Ф.Л.Черноусько, А.Б.Куржанский, Ю.С.Осипов, Я.З.Цып-кин, В.А.Якубович, А.Я.Дубовицкий, А.А.Милютин, В.Ф.Демьянов, Г.М.Уланов, Р.Габасов, Ф.М.Кириллова, Р.П.Федоренко, К.А.Лурье, В.А.Троицкий; А.И.Субботин, А.Г.Ченцов, В.М.Кейн, А.Е.Барабанов, И.В.Бейко, В.А.Бесеке-рский, А.А.Колесников, А.А.Первозванский, Ю.М.Астапов, В.П.Куропаткин, М.З.Коловский, В.В.Гурецкий, В.Ф.Кудин, Б.Г.Питтель, В.В.Григорьев, О.Н. Граничин, Н.Н.Макаров, А.В.Шавров и др. (см., напр., [368, с.475; 317, с.21; 465, с. 143]). Однако, несмотря на ясный физический смысл, практическую значимость и давнюю историю, чебышевский критерий качества, из-за отсутствия конструктивных методов решения порождаемых им оптимизационных задач оказался в забвении во многом благодаря широкому распространению идеологии АКОР. В связи с этим один из последовательных сторонников чебышевско-го критерия качества А.А.Первозванский подчеркивал: «Значение такого критерия вряд ли оспоримо, однако в практических расчетах он почти не используется. Это обстоятельство связано, в первую очередь, с неразработанностью соответствующих аналитических и вычислительных приемов». Одна из частных целей диссертационного исследования заключается в возрождении интереса к чебышевскому критерию качества процессов управления на основе полиэдральной методологии.
Следует отметить, что те или иные полиэдральные конструкции фрагментарно встречаются в литературе в постановках ряда задач оптимального управления при формализации либо цели управления, либо ограничений, либо критериев качества. Это касается, прежде всего, задач минимаксного управления динамическими объектами (см., напр., работы Джонсона (C.D.Johnson) [170, 729], IIlBenne(F.C.Schweppe) [794], А.Б.Куржанского [291], Н.Ф.Кириченко [80, 240], В.А.Якубовича [574,3.2], В.М.Кейна [236], Далеха (M.A.Dahleh) [666, 667], А.Е.Барабанова [40], Э.Я.Рапопорта [406, 407], А.Ф.Шорикова [616]). Од-
нако, все эти задачи не относятся к рассматриваемому в диссертации классу задач с полиэдральной структурой. К полиэдральной методологии оптимизации процессов управления наиболее близки работы А.А.Первозванского второй половины 1960-хгг. [367; 368, с.475-478; 369, 371], связанные с равномерной оптимизацией систем управления.
Методы исследования базируются на активном использовании положений современной теории управления и методов математического программирования. Для вывода, обоснования и доказательства основных теоретических результатов применялся математический аппарат теории разностных уравнений, теории матриц, теории оптимизации и выпуклого анализа. Подтверждение теоретических результатов проводилось компьютерными экспериментами в инструментальной среде MATLAB с использованием современных технологий жестких и мягких вычислений.
Научная новизна. В диссертации, по существу, сформировано новое научное направление в теории автоматического управления, связанное с применением аппарата полиэдрального анализа, полиэдрального исчисления и полиэдрального программирования к задачам дискретного управления динамическими объектами.
На защиту выносятся следующие новые результаты, полученные в диссертации в соответствии с поставленной целью и решением основных задач исследования:
Теоретические основы полиэдральной оптимизации, фундаментальными составляющими которой являются полиэдральный анализ, полиэдральное программирование и полиэдральное исчисление.
Методы редукции задач полиэдральной оптимизации к задачам безусловной полиэдральной оптимизации и к задачам линейного программирования.
Численные методы безусловной полиэдральной оптимизации: субградиентный метод, реализующий непрямую схему «жестких вычислений», и эволюционный метод в виде комбинации эволюционных стратегий и генетических алгоритмов, реализующий прямую схему «мягких вычислений».
Полиэдральная методология формализации задач оптимального управления динамическими объектами с учетом фазовых и ресурсных ограничений на процессы управления.
Полиэдральная стратегия дискретного упреждающего управления динамическими объектами в условиях ресурсных ограничений.
Полиэдральная методология постановки и решения ряда дискретных задач анализа и синтеза систем управления динамическими объектами с учетом фазовых и ресурсных ограничений - в условиях неопределенности, в штатных, конфликтных и критических ситуациях:
предельного быстродействия;
исследования устойчивости и стабилизирующего управления;
экстремального накопления возмущений;
гарантированного управления в условиях начальной полиэдральной неопределенности;
робастного управления в условиях параметрической полиэдральной неопределенности;
конфликтного управления противоборствующими объектами;
барьерного управления в критических ситуациях;
идентификации состояния системы и внешней среды в условиях полиэдральной параметрической неопределенности возмущающих факторов.
Решение прикладной задачи алгоритмизации управления посадочным
маневром пассажирского самолета.
Достоверность и обоснованность научных положений, результатов, выводов и рекомендаций диссертации обусловлены использованием апробированных научных методов и средств, полнотой и корректностью исходных посылок, строгостью и непротиворечивостью математических выкладок, подтверждаются результатами вычислительных экспериментов, а также апробацией и обсуждением полученных результатов на научных конференциях и экспертизой научных статей при публикации в ведущих научных изданиях.
Практическая ценность. Полученные в диссертации теоретические результаты и методические рекомендации ориентированы на разработку эффективных дискретных систем автоматического управления с учетом разнообразных условий функционирования, включая условия параметрической неопределенности, действия возмущающих факторов, возможность конфликтных и критических ситуаций.
Основными достоинствами полиэдральной методологии оптимизации процессов управления как эффективного инженерного инструмента решения широкого круга теоретико-прикладных задач являются:
общность математического формализма, обусловленная использованием полиэдральных конструкций в постановке и содержательной интерпретации широкого класса задач управления;
аппроксимативные аспекты полиэдрального формализма, связанные с возможностью приближения любых выпуклых функций и множеств соответственно полиэдральными функциями и множествами;
ясный инженерный смысл полиэдральных критериев динамического качества процессов управления, простота формализации полиэдральных целей управления, а также полиэдральных фазовых и ресурсных ограничений;
простота колтьютерной реализации алгоритмов полиэдральной оптимизации с использованием доступных и апробированных вычислительных технологий и стандартного программного обеспечения.
Результаты теоретических исследований, разработанные методы полиэдральной оптимизации и полиэдральные алгоритмы управления могут найти широкое применение в задачах автоматизации технических объектов и технологических процессов в промышленности, энергетике и на транспорте.
Использование, внедрение и реализация результатов. Диссертационная работа выполнялась в МГТУ им. Н.Э.Баумана и МГУПИ в рамках плановых госбюджетных научно-исследовательских работ и конкурсных проектов, включая: фундаментальную программу Минобразования РФ «Интеллектуальные системы» (1998 г.), подпрограмму «Научные исследования высшей школы
в области транспорта» (2001 г.), конкурсный проект РФФИ по отделу математики, информатики и механики «Исследование алгоритмов решения терминальных задач» (2000-2002 гг.).
Результаты диссертационного исследования использовались в научно-исследовательской и проектно-конструкторской деятельности четырех предприятий:
ОАО «Туполев» в 1998-2000 гг. при разработке научно-методического, алгоритмического и программного обеспечения системы компьютерной сертификации динамики посадочных маневров пассажирских самолетов (среднема-гистрального Ту-204 и сверхзвуковой летающей лаборатории Ту-144ЛЛ);
ФГУП «НПО машиностроения» в 2000-2003 гг. при разработке перспективных алгоритмов управления стартовым маневром автоматических аэродинамических высокоманевренных летательных аппаратов;
ОАО «Пензенское КБ моделирования» в 2009 г. при разработке цифровых динамических моделей авиационного тренажера для пассажирского самолета Ту-204;
ГУП «Пилотажно-исследовательский центр» в 2009 г. при разработке и верификации алгоритмического обеспечения бортовых информационно-управляющих комплексов.
Предложенные решения позволяют значительно сократить сроки разработки и верификации алгоритмов управления, а также повысить качество процессов управления маневрами ЛА. При этом техническая целесообразность применения и эффективность разработанных алгоритмов управления обусловлены возможностью учета реальных динамических свойств аппарата, требований к качеству маневра, а также ресурсных и фазовых ограничений.
Основные теоретические результаты диссертации вошли в пятитомный учебник по методам классической и современной теории автоматического управления, использованы в учебном процессе при подготовке инженеров по направлению «Системы управления и навигации», магистров и бакалавров по направлению «Автоматизация и управление» в МГТУ им. Н.Э.Баумана и «МА-
ТИ»-РГТУ им. К.Э.Циолковского, а также при подготовке аспирантов в МГТУ им. Н.Э.Баумана и PhD-студента в Де Монтфортском университете (г.Лейстер, Великобритания).
Апробация работы. Основные теоретические и практические результаты диссертационного исследования докладывались и обсуждались на более, чем 110-ти международных и отечественных научных конференция, симпозиумах и семинарах, включая:
Конференции и семинары в России и е ближнем зарубежье: Моск. гор. шк.-семин. мол. учен. «Алгоритмизация и программирование задач управления» (Москва, 1978, 1984); I и II Всесоюз. межвуз. науч.-техн. конф. «Математическое, алгоритмическое и техническое обеспечение АСУ ТП» (Ленинград, 1978; Ташкент, 1980); III Всесоюз. совещ. по автоматизации проектирования САУ и АСУ ТП (Иваново, 1981); Республ. конф. «Вычислительная математика в современном научно-техническом прогрессе» (Киев, 1982); 1-я Всесоюз. на-уч.-техн. конф. «Синтез и проектирование многоуровневых систем управления» (Барнаул, 1982); X и XI Всесоюз. науч.-техн. совещ. «Создание и внедрение систем автоматического и автоматизированного управления ТП» (Алма-Ата, 1983; Новгород, 1986); V Всесоюз. совещ. «Управление многосвязными системами» (Москва, 1984); Республ. науч.-техн. конф. «Опыт создания и пути повышения эффективности функционирования АСУПиТП» (Минск, 1985); V-VI Всесоюз. совещ.-семин. мол. учен. «Современные проблемы автоматического управления» (Пушкино, 1985; 1987); III и IV Всесоюз. науч.-техн. конф. «Программное, алгоритмическое и техническое обеспечение АСУ» (Ташкент, 1985, 1988); Всесоюз. науч. конф. «Декомпозиция и координация в сложных системах» (Челябинск, 1986); 5-я Всесоюз. Четаевская конф. «Аналитическая механика, устойчивость и управление движением» (Казань, 1987); Респ. науч.-техн. конф. «Методологические проблемы автоматизированного проектирования и исследования систем» (Севастополь, 1987); III Республ. науч.-техн. конф. «Новые достижения в области приборостроения» (Ереван, 1987); 1-2-я Всесоюз. науч.-техн. конф. мол. учен, и спец. с междунар. участием «Контроль, управление и автоматизация в современном производстве» (Москва, 1988, 1990); X Всесо-
юз. совещ. по проблемам управления (Москва, 1989); Всесоюз. науч.-техн. совет,. «Теоретические и прикладные проблемы создания систем управления ТП» (Челябинск, 1990); Науч.-техн. конф. «165 лет МГТУ им. Н.Э.Баумана» (Москва, 1995); 1-6-й междунар. симп. «Интеллектуальные системы» (Махачкала, 1994; С.-Петербург, 1996; Псков, 1998; Москва, 2000; Калуга, 2002; Саратов, 2004); VI-VIII и XI междунар. науч.-техн. семин. «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 1997-1999,2002); 1-я междунар. конф. «Новые технологии управления движением технических объектов» (Ставрополь, 1999); The Third Russian-Korean Internat. Sympos. on Science and Technology (Novosibirsk, 1999); 4th и 5th Internat. Conf. on Actual Problems of Electronic Instrument Engineering (Novosibirsk, 1998, 2000); VI междунар. семин. «Устойчивость и колебания нелинейных систем управления» (Москва, 2000); Конф. по теории колебаний и управлению, посвящ. 100-летию Б.В.Булгакова (Москва, 2000); Междунар. конф. «Континуальные логико-алгебраические исчисления и нейроматематика в науке, технике и экономике» (Ульяновск, 2001); Науч.-практ. семин. «Проблемы синтеза и проектирования систем автоматического управления» (Новосибирск, 2001); Всеросс. науч.-техн. конф. «Аэрокосмические технологии» (Реутов, 2002, 2003, 2004); 2, 3 и 5-я междунар. науч.-техн. конф. «Инженерно-физич. проблемы авиац. и космич. техники (Чкаловские чтения)» (Егорьевск, 1997, 1999, 2004); XXVI-XXVIII академ. чтения по космонавтике (Москва, 2002-2004); 2-3-я Всеросс. науч. конф. «Управление и информационные технологии» (Пятигорск, 2004; С.-Петербург, 2005); 1-2-я Всеросс. науч.-техн. конф. с междунар. участ. «Мехатроника, автоматизация, управление» (Владимир, 2004; Уфа, 2005); 1-2-я междунар. науч. конф. «Аналитическая теория автоматического управления и ее приложения» (Саратов, 2000, 2005); Всеросс. научно-техн. конф. «Информационные технологии» (Воронеж, 2005); Ist и 2nd Internat. Conf. «Dynamical System Modeling and Stability Investigation» (Kyiv, 2003, 2005).
Конференции в ближнем и дальнем зарубежье: Научна сесия ВМЕИ «Ленин» (Болгария, София, 1989); Трета-Пета Национ. млад. шк. с междунар. уч. «Системи за автоматизация на инженерния труд и научните изследвания»
(Болгария, София, 1989-1991); 9th, 10th, 13-17m Intemat. Conf. «Systems for Automation of Engineering and Research» (Bulgaria, Varna, 1995, 1996, 1999-2003).
Семинары в: МГТУ им. Н.Э.Баумана, «МАТИ»-РГТУ им. К.Э.Циолковского, МИФИ (ТУ), МГУ им. М.В.Ломоносова, Саратовском ГУ, Киевском ГУ, Софийском ГУ (Болгария), Де Монфортском университете (Великобритания).
Публикации. По теме диссертационного исследования опубликовано самостоятельно и в соавторстве более 160 печатных работ, включая: одну монографию, две главы в пятитомном учебнике, учебное пособие, 27 статей, опубликованных в центральных отечественных и зарубежных журналах, а также 27 статей, опубликованных в рецензируемых сборниках научных трудов. В периодических изданиях, рекомендованных ВАК РФ опубликована 21 статья. Публикации в полной мере отражают основное содержание диссертации.
Личный вклад автора. В работах, выполненных в соавторстве, автору принадлежат результаты, относящиеся к разработке теории 1111 и ее применения в задачах оптимизации процессов управления и наблюдения. В работах с соавторами (В.В.Солодовниковым и А.Б.Филимоновым) автору принадлежит ведущая роль в постановке задач, выборе и обосновании методов их решения, а также в объяснении и интерпретации полученных результатов. В работах, выполненных совместно с аспирантами А.Н.Бабичем, М.Н.Деменковым и И.В.Бе-лоусовым, автор осуществлял непосредственное научное руководство.
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка литературы из 821 наименований и двух приложений. Общий объем работы - 393 с, включая: 286 с. основного содержания исследований (26 рис. и 4 табл.), 40 с. приложений и 67 с. списка литературы.
Краткая характеристика содержания работы. Диссертация включает
шесть глав и два приложения.
Постановка и особенности общей задачи полиэдрального программирования
Многие прикладные задачи оптимизации в различных областях человеческой деятельности изначально связаны с понятием полиэдральности: специфика данных задач находит формальное выражение в свойствах полиэдральности соответствующих математических конструкций (полиэдральность множеств, функций, неравенств, норм и метрик). К задачам ПП естественным образом приводится широкий класс задач управления, проектирования и планирования. Так, например, к задачам ПП сводится ряд экономических и технических задач, начиная от задач календарного планирования производства, некоторых транспортных задач, задач целераспределения и кончая задачами выбора рациональной системы допусков в машиностроении, построения надежных схем из ненадежных элементов, синтеза формальных нейронов, проектирования автоматических систем, решения задач оптимального управления. Кроме того, многие задачи ЛП для уменьшения количества переменных и ограничений целесообразно переформулировать в терминах 1111, а любую задачу выпуклого программирования всегда можно точно или приближенно свести к задаче ПП путем кусочно-линейной аппроксимации фигурирующих в задаче нелинейных функций. В работе [505] приведены примеры формализации в терминах ПП некоторых задач вычислительной математики и обработки информации: ? задача решения системы линейных алгебраических уравнений; ? задача наилучшего приближения функций; ? задачи вычислительной геометрии; ? задача многокритериального линейного программирования; ? задачи распознавания и классификации образов; ? задача параметрической оптимизации технических объектов по критерию запаса работоспособности. Особенности общей задачи полиэдрального программирования. Прежде всего, отметим принципиальную особенность задач 1111, отличающую их от ряда других задач МП, включая задачи линейного программирования: если задача максимизации целевой функции в них автоматически сводится к задаче минимизации инверсной целевой функции, то между задачами 1111 на максимум и минимум целевой функции имеются существенные различия, обусловленные тем, что полиэдральные целевые функции являются выпуклыми. Дело в том, что выпуклая функция, вообще говоря, может иметь кроме глобального еще ряд локальных максимумов на выпуклом множестве. Этот факт крайне неприятен с вычислительной точки зрения, поскольку, как подчеркивает Рокафеллар (R.T. Rokafellar), «даже зная некоторый локальный максимум, мы не располагаем никакой локальной информацией, позволяющей перейти в локальный максимум более высокого уровня. В частности, не существует никаких локальных критериев, содержащих ответ на вопрос, является ли данный локальный максимум глобальным или нет» [423, с. 355].
Анализ теории и практики оптимизации показывает, что сложность любой оптимизационной задачи и выбор численных методов ее решения определяются специфическими свойствами целевой функции и области допустимых решений, задаваемой ограничивающими функциями [98, 119]. Здесь речь идет о локальных и глобальных свойствах функции, причем основным ее глобальным свойством является свойство выпуклости, а основным ее локальным свойством - свойство гладкости.
Поскольку полиэдральные функции относятся к классу выпуклых кусочно-линейных функций, то общая задача относится к классу задач выпуклой негладкой оптимизации [126, 184, 771]. Выпуклость играет фундаментальную роль в теории и численных методах оптимизации, существенно облегчая решение задачи 1111 - придавая ей два простых, но очень важных свойства: любой локальный минимум минимизационной задачи ПП является также глобальным, абсолютным минимумом; необходимые условия оптимальности задачи ПП являются также и достаточными. Негладкость, т.е. недифференцируемость, напротив, существенно затрудняет решение задачи ПП. Действительно, как подчеривает Р.П.Федоренко: «С точки зрения вычислительной математики трудность задачи определяется не ее формой, а дифференциальными свойствами входящих в задачу функций». При этом так называемая «необязательная» негладкость целевой и ограничивающих функций в задачах МП, хотя и несущественна, но естественна, поскольку «машинная версия» любой функции разрывна по своей природе: результаты вычислений с конечной точностью никогда не составят непрерывные функции; к тому же обычное математическое определение непрерывности, включающее произвольные малые приращения функции и ее аргумента, при операциях над конечным множеством чисел, представимых в формате с плавающей запятой, просто неприменимо. Источниками, порождающими негладкости целевой и ограничивающих функций в задачах ПП, являются операции взятия максимума max и абсолютной величины . . Следует отметить, что негладкие функции естественным образом возникают в различных прикладных оптимизационных задачах, в частности, они появляются в методах решения задач, содержащих помимо указанных математических операций такие механизмы порождения негладкостей, как использование приемов декомпозиции, точных негладких штрафов, двойственности, возмущений и т.п.
До недавнего времени негладкость, естественным образом появляясь в математике и ее приложениях, все же представляла собой чаще всего экзотику, исключение, подтверждающее «гладкие правила». При этом многие специалисты считали ее «незаконным» ребенком в царстве чистой Математики, относили ее к так называемым «трансцендентным» свойствам функций, определяемым сложностью их топографии (топологии), и просто отказывались иметь с ней дело. Здесь уместно заметить, что математику негладких функций классики именовали «тератологией» функций (наукой об уродствах функций), и напомнить весьма резкие высказывания в адрес негладких функций главы французской математики XIX в. Эрмита (Ch.Hermite), который в письме Стилтьесу (TJ. Stieltjes) писал, что он «с ужасом и отвращением отворачивается от этой раз-растающей язвы функций, не имеющих производной».
В последнее время негладкость все более настойчиво вторгается в практику: негладкие функции все чаще встречаются в математических моделях реальных технических, социально-экономических и экологических процессов. Более того, многие специалисты провозглашают нынешнее столетие веком негладкости. В частности, современная теория управления все более склоняется к освобождению от традиционных предположений о гладкости, которые были заложены при ее разработке. При этом попытки ослабить требования гладкости обусловлены практическими потребностями. Так, задачи оптимального управления уже в первоначальных (даже простейших) постановках относятся к классу негладких экстремальных задач за счет наличия нефункциональных фазовых (ограничения на переменные состояния) и ресурсных (ограничения на переменные управления) ограничений, а также критериев оптимальности, которые в общем случае могут быть негладкими [165, 664].
Задача безусловной полиэдральной оптимизации и современные технологии «жестких» и «мягких» вычислений
Как известно, численные методы решения какой-либо оптимизацинной задачи - это методы точного или приближенного ее решения, основанные на построении конечной последовательности действий над конечным множеством чисел. Очевидно, что в силу полиэдральности целевой функции задачу (2.1) можно решать точными конечношаговыми методами ЛП, гарантирующими нахождение решения за конечное число шагов. Для этого достаточно воспользоваться описанными в 1.2.2, методом введения дополнительной переменной, мажорирующей целевую функцию, либо методами ограничивающих или разности переменных. Однако, в случае высокой размерности п задачи и большой струк турной сложности ее целевой функции f(x) реализация методов ЛП может встретить значительные вычислительные трудности. Тогда менее трудоемкими могут оказаться специальные приближенные бесконечношаговые методы выпуклого программирования, гарантирующие нахождение решения оптимизационной задачи в пределе.
Применение к задаче (2.1) традиционных методов выпуклой гладкой оптимизации требует либо изменения ее исходной постановки путем исключения причин возникновения негладкостей, либо использования различных приемов сглаживания целевой функции f(x). Идея сглаживания, или усреднения, для целей негладкой оптимизации довольно плодотворно используется в вычислительной математике начиная с работ А.М.Гупала [152] и В.Я.Катковника [234], поскольку позволяет устранить мелкие локальные экстремумы, сохраняя общую картину рельефа целевой функции. При этом минимизация сглаженной функции дает шанс проскочить локальные экстремумы исходной целевой функции и попасть в район глобального минимума. Однако использование сглаживания часто приводит к плохой обусловленности матрицы Гессе сглаженной функции, что соответственно ухудшает вычислительную устойчивость даже таких эффективных методов гладкой минимизации, как квазинъютоновские методы и методы сопряженных градиентов. В связи с этим особую актуальность приобрела проблема разработки специальных методов негладкой оптимизации, конкурентоспособных как по надежности, так и по времени счета и точности результатов с наиболее эффективными методами решения гладких плохо обусловленных оптимизационных задач. К настоящему времени разработан широкий спектр численных методов решения выпуклых экстремальных задач, включая специальные методы, ориентированные на задачи недифференцируемой оптимизации и, в частности, на задачи дискретного минимакса [6, 51, 65, 98, 112, 126, 164, 184, 254, 359, 381, 387, 615, 635, 642, 648, 686, 724, 757, 771, 771, 785]. При этом все существующие эффективные методы недифференцируемой оптимизации основываются на идеях целесообразного спуска, отсечения и штрафа.
В последние годы, наряду с традиционными вычислительными технологиями решения экстремальных задач, все большее распространение получают вычислительные технологии, имитирующие поведение и воспроизводящие мышление человека. Данные вычислительные технологии составляют ядро бурно развивающегося в рамках теории искусственного интеллекта нового научного направления, прогвозглашенного в 1994 г. Заде (L.A.Zadeh) и получившего название «Мягкие вычисления» или «Вычислительный интеллект» [213, 650].
Мягкие вычисления (Soft Computing) положены в основу многочисленных программ («Real World Computing», «New Information Processing Technology» и др.) разработки и создания адаптивных, эволюционирующих, сверхвысокопроизводительных вычислительных машин шестого поколения и, в отличие от традиционных жестких вычислений (Hard Computing), нацелены на максимальное приспособление к реальной действительности. Основополагающим принципом мягких вычислений является «терпимость к неточности, неопределенности и частичной истинности для достижения удобства манипулирования, робастнос-ти, низкой стоимости решения и лучшего согласия с реальностью». Концепция мягких вычислений включает в качестве основных составляющих такие нетрадиционные методы вычислений, как нечеткие, нейронные и эволюционные вычисления. Несмотря на большие возможности каждой данной составляющей в отдельности, все они не конкурируют между собой, а являются взаимодополняющими, обеспечивая: толерантность по отношению к неточности и неопределенности (нечеткие вычисления), гибкость и адаптацию (нейронные вычисления), а также высокопроизводительную реализацию (эволюционные вычисления) вычислительного процесса. Характерным примером такого взаимодополнения является использование нечеткой логики при проектировании нейронных сетей и их оптимизация с помощью эволюционных вычислений.
Итак, современная теория и практика оптимизации располагает богатым арсеналом методов жестких и мягких вычислений, которые можно использовать для решения негладких оптимизационных задач и, в частности, задачи безусловной полиэдральной оптимизации (2.1). При этом имеются ввиду как «прямые» методы (именуемые также методами нулевого порядка), в которых поиск решения осуществляется на основе сопоставления значений целевой функции в пробных точках, так и «непрямые» методы, в которых для поиска решения ис пользуются необходимые и достаточные условия экстремума целевой функции. Говорить о наилучшем во всех отношениях методе не приходится, поскольку, как подчеркивают ведущие отечественные специалисты в области вычислительной математики Ф.П.Васильев и Ю.Г.Евтушенко, «такого универсального метода пока нет, и вряд ли такой метод существует». Действительно, универсальные методы, ориентированные на решение более широких классов задач обычно уступают по эффективности специализированным методам, использующим определенные специфические свойства конкретно решаемой задачи.
Постановка общей задачи оптимизации дискретных процессов управления
Среди существующих направлений развития ЭВ наибольшее распростра-нение в практике оптимизации получили генетические алгоритмы (ГА), для построения которых разработано большое число различных подходов и модификаций [45, 46, 106, 108, 128, 140, 224, 225, 287, 358, 433, 703, 708, 715, 718, 723, 761, 762, 776, 782, 811], а также эволюционные стратегии (ЭС), обладающие высоким вычислительным потенциалом [419, 748, 780, 791] и незаслуженно обделенные вниманием отечественных исследователей.
ГА и ЭС имитируют эволюцию виртуальной популяции особей на различном уровне абстракции: в ГА моделируется эволюция на уровне генотипа, а в ЭС - на уровне фенотипа. Здесь под генотипом понимается генетический код особи, т.е. совокупность генов, находящихся в ее хромосомах, а под фенотипом - физическая реализация генетического кода особи, т.е. совокупность характеризующих ее признаков и свойств, причем фенотип особи однозначно соответствует ее генотипу и наоборот. В результате, по терминологии Фогеля (L.J.Fo-gel), ГА и ЭС реализуют два подхода к задачам оптимизации: первый моделирует эволюцию популяции особей как восходящий процесс, оптимизирующий гены особи, а второй - как нисходящий процесс, оптимизирующий ее поведениє. При этом в качестве генотипа выступает закодированное в генетическом представлении, а в качестве фенотипа - декодированное из генетического представления множество альтернативных решений задачи.
Схема эволюционного поиска в ГА и ЭС достаточно проста: предварительно формируется начальная «родительская» популяция особей в виде исходного множества альтернативных решений задачи и затем запускается многоступенчатый итерационный процесс ее эволюции. При этом на каждой текущей итерации эволюционный поиск включает следующую последовательность операций: сначала посредством селекции производится отбор наиболее приспособленных текущих родительских решений; далее посредством рекомбинации и мутации производится синтез текущих дочерних решений; затем посредством селекции формируются новые родительские решения для следующей итерации. Основываясь на сравнительном анализе ГА и ЭС [438, 632, 702, 774, 790, 798], можно выделить следующие их характерные особенности: ГА ориентированы на решение задач дискретной оптимизации, а ЭС -на решение задач непрерывной оптимизации; альтернативные решения задачи в ГА кодируются в некотором конечном алфавите (бинарное представление в виде битовой строки) и поиск осуществляется в кодовом (хемминговом) пространстве искомых переменных, а в ЭС они представляются в явном виде вещественными числами и поиск осуществляется в действительном пространстве искомых переменных; разнообразие множества альтернативных решений задачи в ГА и ЭС достигается за счет генетических (поисковых) операторов мутации и рекомбинации, причем в ГА во главу угла ставится оператор рекомбинации, а в ЭС -оператор мутации, причем мутация в ГА реализуется при бинарном кодировании решения через инверсию случайно определенного бита, а в ЭС - путем добавления к решению случайных нормально распределенных величин; рекомбинация в ГА производит двух потомков, а в ЭС - одного потомка; селекция в ГА является стохастической и производится по функции приспособленности, которая выбирается в зависимости от целевой функции и типа задачи, а в ЭС - жесткой детерминированной и осуществляется напрямую по целевой функции задачи. С теоретической точки зрения ГА используют процесс эволюции как механизм развития и комбинации полезных поисковых схем из генетического материала, а ЭС используют процесс эволюции для изучения способности особи приспосабливаться к изменяющимся условиям. При этом главное отличие оригинальных (первоначальных) версий ГА и ЭС заключается в том, что в ГА особи для селекции выбираются пропорционально значениям их функции приспособленности и новая популяция формируется из предыдущей равновероятно, а в ЭС, наоборот, особи для селекции выбираются с равными вероятностями, а формирование новой популяции базируется на значениях функции приспособленности. По мере развития ГА и ЭС наблюдается их взаимное проникновение, сращивание в единую концепцию ЭВ, что вполне естественно, поскольку они являются «двумя сторонами одной и той же медали», и, как показывают вычислительные эксперименты, дают эквивалентные результаты решения оптимизационных задач [235]. В итоге, к настоящему времени изначальные различия между ГА и ЭС в организации эволюционного поиска (операторов селекции, мутации и рекомбинации) практически исчезли; осталось единственное существенное различие между ними - это способы представления (кодовый и явный) альтернативных решений задачи. Какой из двух подходов ГА или ЭС целесообразнее использовать для решения задачи безусловной полиэдральной оптимизации (2.1) сказать сложно. Однако, можно утверждать, что в данном случае наиболее целесообразна интеграция, симбиоз обоих подходов. В работах автора [58-60, 560] предложен эффективный эволюционный метод оптимизации, сочетающий преимущества обоих подходов и являющийся быстродействующей модификацией комбинированной схемы ЭС и ГА, разработанной Ю.В.Федотовым в работах [56, 57]. Выделим следующие принципиальные особенности предложенного эволюционного метода оптимизации: в качестве особи принимается вектор искомых переменных, т.е. используется явное представление альтернативных решений, характерное для ЭС; размер популяции особей фиксирован и не меняется в процессе поиска решения; поиск решения осуществляется парой родительских особей, формируемой на основе панмиксии с нормальным законом распределения; разнообразие популяции особей достигается за счет стандартных генетических операторов - универсальной равномерной рекомбинации, характерной для ГА, и абсолютной аддитивной мутации, характерной для ЭС; используется элитная селекция с вытеснением, осуществляемая по целевой функции исходя из репродукционной популяции «предки + мутанты»; для ускорения процесса поиска решения предусмотрена адаптация вероятности мутации, характерная для ЭС.
Ретроспектива и современное состояние проблемы упреждающего управления
Специализация эволюционных алгоритмов - это выбор, точнее настройка, основных параметров схемы эволюционного поиска для конкретного класса оптимизационных задач, позволяющая сократить время поиска и/или повысить качество решения. Действительно, успех практического применения эволюционного алгоритма, как и любого эвристического алгоритма прямого поиска «полностью определяется тем, насколько хорошо удалось подобрать значения его параметров» [126, с. 125]. Именно, неправильный выбор параметров эволюционных алгоритмов часто не позволяет получить ожидаемого результата и порождает к ним скептическое отношение. При этом, несмотря на существующие различные методики выбора параметров эволюционных алгоритмов (см., напр., методику выбора параметров ГА [712]), каких-либо универсальных рекомендаций не существует: данный выбор является произвольным, находится на интуитивном уровне пользователя и осуществляется посредством численного эксперимента. В результате, экспериментируя с алгоритмом при одних параметрах и получив неудовлетворительные результаты, необходимо опробовать его при других параметрах.
В Приложении к настоящей работе в качестве прикладных задач полиэдральной оптимизации рассматриваются задачи параметрической оптимизации алгоритмов управления терминальными маневрами аэродинамических летательных аппаратов (ЛА). Каковы же особенности данного класса оптимизационных задач с точки зрения специализации предложенной схемы эволюционного поиска?
Прежде всего, заметим, что в решаемых далее оптимизационных задачах искомыми являются, как правило, более 10-и параметров, достаточной точностью определения которых являются три значащие цифры. При кодовом представлении искомых параметров с использованием бинарного кодирования длина особи (альтернативного решения) составит более 100 бит, что сопряжено с весьма громоздким представлением решений и создает слишком большие области их поиска. Исследования показывают, что поиск в кодовом пространстве искомых параметров эффективен при длине особи не более 70-80 бит. Следовательно, искомые параметры алгоритма управления терминальным маневром ЛА целесообразно представлять в явном виде вещественными числами и осуществлять поиск в исходном пространстве искомых параметров.
Принципиальной особенностью данных оптимизационных задач является алгоритмическое задание целевой функции. Дело в том, что здесь в качестве активных функциональных ограничений выступают уравнения связи, представляющие собой нелинейные неавтономные дифференциальные уравнения высокого порядка (-20), описывающие динамику маневра ЛА как объекта управления. Исследования показали, что целесообразно эти ограничения не включать в целевую функцию в виде «штрафных слагаемых», а учитывать их непосредственно при расчете целевой функции путем численного решения уравнений связи. В этом случае существенно увеличиваются временные затраты ( 1 с на процессоре типа Athlon 1.2 ГГц) на оценку приспособленности каждой особи, причем использование больших (300-500) популяций особей приводит к практически недопустимо большому времени поиска решения, а использование малых (20-40) популяций особей, приводит к преждевременному вырождению популяции и к ухудшению качества решения.
Итак, специализация предложенной схемы эволюционного поиска заключается в проведении вычислительных экспериментов по выбору ее параметров, учитывающему особенности решаемого далее класса прикладных задач полиэдральной оптимизации и обеспечивающему сокращение времени поиска приемлемого решения. Для проведения соответствующих исследований необходимо располагать быстродействующим и гибким программно-инструментальным средством, позволяющим в интерактивном режиме конструировать различные конфигурации схемы эволюционного поиска с последующей их апробацией на тестовых задачах. При этом эффективность конфигурации схемы поиска определяется скоростью и качеством поиска.
При настройке параметров эволюционного поиска в качестве целевых функций тестовых задач используются функции с заранее известными экстремумами и не требующие большого времени вычисления. Типовой набор тестовых оптимизационных задач для сравнения методов оптимизации приведен в [581, 722], а наиболее представительный набор тестовых целевых функций предложен в сборнике «Towards Global Optimization» (North Holland, 1978, V.2) международного конкурса эффективности алгоритмов глобальной оптимизации. В практике эволюционной оптимизации наибольшее распространение получили следующие тестовые целевые функции: ступенчатая функция, функция с нормально распределенными искажениями, функция «Волна», двумерная экспоненциальная функция, функция Растригина, функция Розенброка (H.H.Ro-senbrock), семейство функций ДеДжонга(К.А.Бе Jong), функция Гринвака(А. Grienwank), функция Пауэлла (М.J.D.Powell) и функция Швефеля (Н.-Р.Schwe-fel). Все эти функции обладают следующими свойствами, характерными для целевых функций задач полиэдральной оптимизации алгоритмов управления терминальными маневрами ЛА: многоэкстремальность, разрывность и овражность с незначительным различием значений функции в точках локальных экстремумов и узкими зонами их притяжения.
В последние годы появилось множество специализированных и универсальных программных средств, реализующих эволюционные вычисления [96, 128, 255, 657, 662, 707, 715]. Наиболее популярными являются следующие программные средства, ориентированные на оптимизацию с применением ГА: ЕМ (Technical University Berlin), Escapade (University of Portmund), Genesis (The Software Partnership), EnGENEr (Logica), Game (University College London), GA Workbench (Cambridge Consultants), MicroGA (Emergent Behavior), Splicer (NASA Johnson & Metre Corporat), GeneHunter (Ward Systems Group), Evolver (Palisade), Genitor, GALOPPS, Genie и т.д.
Похожие диссертации на Полиэдральная оптимизация дискретных процессов управления: теория и применение
