Диссертация (Модели и алгоритмы определения приоритетного направления движения воздушного судна по заданным маршрутам), страница 2

Алгоритм оптимального программного управления на основеобобщѐнного квадратичного показателя качества с учетом действующихвозмущений.Степень достоверности и апробация результатов. Достоверностьполученныхрезультатовапробированногоподтверждаетсяматематическогокорректнымаппаратаиспользованиемтеорииуправления,непротиворечивостью результатов моделирования, полученных на основеизвестных и разработанных моделей и алгоритмов.10Апробация работы.1.Результатыпроведенныхисследованийдокладывалисьиполучили одобрение на XXXIV Межведомственной научно-техническойконференции «Проблемы обеспечения эффективности и устойчивостифункционирования сложных технических систем» - Серпухов 2015 г.; VВсероссийскойнаучно-практическойконференции«Современноенепрерывное образование и инновационное развитие» – Серпухов 2015 г.;2.Результаты работы: модель управления ВС, модель реализациитерминального управления летательного аппарата с учѐтом действующихвозмущений опубликованы в сборнике «Информатика, вычислительнаятехника и управление» ИТМиВТ РАН, 2014.По результатам выполненных исследований опубликовано 11 печатныхработ, в том числе 3 в научных изданиях, рекомендуемых ВАК МинобрнаукиРФ.В публикациях, написанных в соавторстве, лично автору принадлежатрезультаты: анализа предметной области [33 , 67]; формулировки постановкизадачи [28, 29]; построения и анализа модели и алгоритмов, выносимых назащиту [29, 30, 31, 32]; результаты оценки эффективности использованиямоделей [33].3.Основныеположениядиссертационныхисследованийиспользованы в НИР кафедры систем автоматического и интеллектуальногоуправления МАИ, реализованы в учебном процессе.Диссертациясостоитизвведения,трехглав,заключения,библиографического списка и приложений.

Диссертация содержит 122страниц машинописного текста, 33 рисунка, 13 таблиц, 2 приложения.Библиографический список содержит 82 наименования.Основные результаты исследования соответствуют п. 3 и 10 паспортаспециальности 05.13.01 – Системный анализ, управление и обработкаинформации (Авиационная и ракетно-космическая техника)(техническиенауки).11Работа выполнена в рамках приоритетных научных направленийМосковского авиационного института.121. Анализ моделей приоритетного распределения воздушных судов позаданным маршрутам1.1. Метод ветвей и границ1.1.1.

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

[20]. Ниже приведены результаты анализа эффективности примененияуказанных методов для решения, поставленной в исследовании задачи.Метод «Полного перебора» достаточно полно представлен в [49]. Средиметодов построения оптимального маршрута движения является самымпростым. При применении этого метода задача поиска оптимальногомаршрута движения решается «в лоб». В основу метода «полного перебора»положеналгоритмрасчетапоказателейвсехвозможныхвариантовследования по маршруту. При его применении исследователь получаетоптимальное (с точки зрения выбранного критерия качества) решение задачи.К основному недостатку метода следует отнести то, что с ростом количествапромежуточных пунктов маршрута (ПМ) время решения задачи (Т)существенно увеличивается, так как количество возможных вариантов равноn!, где n – число промежуточных ПМ (рис.

1.1).TnРисунок 1.1 – Зависимость времени решения задачи от количествапромежуточных пунктов маршрута13Положительными сторонами применения метода являются простотареализации метода и оптимальность найденного решения.Метод, основанный на «Жадном» алгоритме. Этот метод основан напринципе декомпозиции решаемой задачи на частные. В данном случаенахождение оптимального решения для каждой частной задачи означаетполучение оптимальных показателей для каждого возможного маршрутадвижения ВС.

Основным недостатком данного метода является тообстоятельство,чторешениезадачивцеломможетнеявлятьсяоптимальным. Применительно к решаемой в диссертации научной задаче этообстоятельство может быть интерпретировано (рис. 1.2) как нахождениеоптимального маршрута состоящего из последовательности объектов«ближайших» к текущему положению ВС. Такое решение поставленнойзадачи, как и при применении предыдущего метода не гарантируетоптимальность решения.НКРисунок 1.2 – Сравнение оптимального пути (темные стрелки) и пути,полученного с помощью «жадного» алгоритма (светлые стрелки)Анализ рисунка 1.2 показывает, что маршрут из начального ПМ (Н) вконечный ПМ (К), полученный с помощью «жадного» алгоритма, отличаетсяот оптимального.Кположительнымсторонамметодаследуетотнестиреализации, быстроту работы и априорное знание времени поиска.простоту14Метод ветвей и границ применяется при решении задач целочисленноголинейного программирования. Анализ литературы [70] показал, что этотметод является вариантом метода полного перебора, в котором оптимальноерешениенаходитсяпутемпоследовательногоисключениязаведомонеоптимальных маршрутов.Алгоритм, реализующий метод ветвей и границ представлен следующейпоследовательностью шагов:1.

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

1.3.+(1,3)-(1,3)+(4,5) L1<L2+(3,2) L1<L2-(4,5)L2<L1-(3,2) L2<L1+(2,4) L1<L2-(2,4) L2<L1L1<L2L2<L1Рисунок 1.3 – Дерево построения решений для метода ветвей и границПоложительнойсторонойэтогометодаявляетсяоптимальностьнайденного решения.Основным недостатком этого метода является достаточно большоевремя решения задачи, существенно возрастающее с увеличением количествапунктов маршрута. Это обстоятельство ограничивает его применение в15системах реального времени, а также для решения задач с большимколичеством пунктов маршрута.Метод поиска аналитического выражения функции риска.

Этот методоснован на использовании функция риска как простейшей аналитическойформы принятия решений. Применительно к решаемой в диссертации задачеэтотметодпозволяетопределитьпервоочереднойпунктмаршрута,следующий за текущим пунктом. Первоочередным является пункт маршрута,для которого значение функции риска будет минимально. В качествепримера выбора функции риска следует привести степенной полиномвторого порядка относительно приращений географических координат X и Yместоположения пункта маршрута на карте:F j  b1  X j  b2  Y j  b3  X j 2  b4  Y j 2  b5  X j  Y j ,где Xj, Yj - координата j-го пункта маршрута и координата текущегоположения ВС соответственно.Коэффициенты b1…b5 определялись при самообучении на примерах.Алгоритм самообучения для определения коэффициентов полиномасостоит из следующих шагов:1.задается некоторое опорное значение вектора b1(0), b2(0), b3(0), b4(0),b5(0);2.осуществляется маршрутизация полета (в таком необученномсостоянии, находится частота правильных решений);3.создаются отклонения поочередно коэффициентов (bi + Δb); вновьоценивается успех поведения;4.лучший вариант становится опорным для следующего шагасамообучения.Слабойсторонойданногометодаявляетсянеобходимостьформирования примеров обучения, представляющих собой оптимальныемаршруты следования через промежуточные пункты.161.1.2 Анализ методов параметрической оптимизацииДля успешного решения поставленной научной задачи целесообразновыполнить анализ численных методов, применяемых при решения задачбезусловной одномерной и многомерной оптимизации, т.е.

для нахожденияминимума некоторой скалярной целевой функций F(x).Известно [74], что задачи одномерной оптимизации относятся кнаиболее простому виду оптимизационных задач. Тем не менее, анализметодов их решения целесообразно не только в связи с тем, что именно такиезадачи решаются в инженерной практике, но и, потому, что одномерныеметоды решения задач одномерной оптимизации часто используются длярешения подзадач, возникающих при применении численных методов крешению задач многомерной оптимизации.Классификациячисленныхметодоврешенияодномерныхзадачбезусловной оптимизации основана на признаках (характер допущений ипредположений), характеризующих свойства исследуемой целевой функции.Среди известных численных методов безусловной оптимизации [2]наибольшее распространение получили методы исключения интервалов иметоды полиномиальной аппроксимации.Сущность методов исключения заключается в поиске оптимальногозначения функции одной переменной внутри заданного интервала припоследовательном исключении подынтервалов, не содержащих оптимальноезначение функции.Сущность методов полиномиальной аппроксимации, заключается влокальномописаниигладкойцелевойфункцииполиномомдляпоследующего его использования для оценки ее оптимального значения.Ниже приведены результаты подробного анализа методов исключенияинтервалов для определения целесообразности их применения для решенияпоставленных в диссертации задач.17Методика применения методов исключения интервалов предполагаетсравнении одних только значений целевой функции F(x) в различныхпробныхточках,унимодальностиприэтомисследуемойпредполагаетсяцелевойвыполнениефункции.Этотребованиятребованиеиллюстрируется примером, приведенным на рисунках 1.4-1.6 для случаев а)( F ( x1 ) F ( x2 )) ; б) ( ( F ( x1 ) F ( x2 )) ; в) ( ( F ( x1 )  F ( x2 )) .

Исследуемая целевая функцияF(x) будет унимодальной на определенном интервале [a, b], если выполняетсяусловие монотонности по обе стороны от единственной на этом отрезке*точки – оптимального значения функции x (рис. 1.4.).Рисунок 1.4 – Иллюстрация требования унимодальности целевой функции,случай а)Рисунок 1.5 – Иллюстрация требования унимодальности целевой функции,случай б)Рисунок 1.6 – Иллюстрация требования унимодальности целевой функции,случай в)18Анализ особенностей методов исключения интервалов показал, что длявычисления значений целевой функции не обязательно выполнение условиядифференцируемости.

Более того, для их применения (когда целевуюфункцию нельзя представить в аналитическом виде), достаточно определитьзначения целевой функции F(x) в заданных точках с помощью прямыхрасчетов, моделирования или натурного эксперимента (например, значенияцелевой функции определены в результате стендовых или натурныхиспытаний).Основной особенностью применения методов исключения интерваловявляется разделение процесс поиска оптимального значения целевойфункции этапы:- установления границ интервала, содержащего оптимальное значениефункции;- последовательное уменьшение исходного интервала до полученияинтервала заданного размера.Особого внимания заслуживает метод деления интервалов пополам(трехточечный поиск на равных интервалах), применение которого позволяетисключать на каждом шаге поиска оптимального значения функции ровнополовину интервала.Применение метода «золотого» сечения позволяет, при поискеоптимального значения функции, исключать часть интервала меньшую, чемполовина исходного, на каждой итерации поиска, но только при одномвычислении значения функции F(x).