Содержание к диссертации
Введение
1. Постановка задачи 13
1.1. Задача синтеза логического управления динамической системой...14
1.2. Вычислительные методы синтеза систем управления 17
1.2.1. Метод генетического программирования 17
1.2.2. Метод сетевого оператора 23
1.3. Выводы 39
2. Метод логического сетевого оператора 40
2.1. Конструктивные множества логических операций 40
2.2. Дискретизация вектора состояния 44
2.3. Метод вариации базисного решения 45
2.4. Генетический алгоритм на основе метода вариаций 49
2.5. Выводы 54
3. Задача управления транспортными потоками 55
3.1. Постановка задачи синтеза управления 55
3.1.1. Обзор математических моделей транспортных потоков 61
3.1.2. Математическая модель на основе метода управляемых сетей 63
3.1.3. Пример расчета величины потока 76
3.1.4. Векторная модель управления транспортным потоком 79
3.1.5. Использование информации о маршрутах движения потоков 82
3.2. Критерии качества управления 85
3.3. Оценка величины транспортного потока 86
3.4. Виды управления транспортными потоками 88
3.5. Выводы 91
4. Вычислительные эксперименты 93
Заключение 103
Литература 105
- Метод генетического программирования
- Генетический алгоритм на основе метода вариаций
- Математическая модель на основе метода управляемых сетей
- Использование информации о маршрутах движения потоков
Введение к работе
Актуальность темы. Логическое управление, которое определяется тем, что компоненты вектора управления принимают целочисленные значения из ограниченного множества, в частности из множества {ОД}, сегодня имеет большую прикладную потребность в промышленности в частности в системах принятия решения для эффективного управления потоками в сетях.
Работа посвящена решению задачи синтеза логического управления динамической технической системой. Сегодня не известны общие методы решения задачи синтеза логического управления, когда из постановки задачи на основании заданных критериев и математической модели объекта управления с помощью определенных преобразований получают формально логическую функцию, описывающую зависимость управления от состояния объекта.
Развитие вычислительной техники и последние достижения в области алгоритмизации позволяют конструировать эффективные вычислительные алгоритмы, которые обеспечивают поиск математических выражений для решения различных задач с помощью вычислительной машины. К таким достижениям в области алгоритмизации относятся методы генетического программирования и сетевого оператора, которые позволяют построить численные методы для поиска математических выражений. В работе для решения задачи синтеза логического управления динамической технической системой разрабатывается численный метод на основе логического сетевого оператора.
Полученный в работе вычислительный метод синтеза предназначен для промышленного использования в городском хозяйстве. Метод позволяет построить систему управления транспортными потоками в сети городских дорог. Целью управления является обеспечение максимальной пропускной способности сети дорог за счет согласованного переключения рабочих фаз светофоров на всех регулируемых перекрестках сети. Увеличение пропускной способности сети дорог сегодня является важной прикладной задачей, решение которой может уменьшить количество заторов в сети. Решение задачи синтеза управления предусматривает нахождение функциональной зависимости рабочих фаз светофоров на регулируемых перекрестках от величин параметров транспортных потоков на участках сети дорог. По состоянию перегруженности транспорта на всех участках дорог синтезированное логическое управление обеспечивает для каждого светофора выбор решения о переключении на следующую рабочую фазу или нет.
Построение нового вычислительного метода для решения ранее не решенной научной задачи и применение разработанного метода для решения важной прикладной задачи определяет актуальность темы работы.
Предметом исследования диссертационной работы является вычислительный метод для синтеза логического управления динамической технической системой и его применение для управления транспортными потоками в сети городских дорог.
Целью диссертационных исследований является разработка эффективного вычислительного метода для синтеза логического управления динамической технической системой и применение полученного метода для управления
транспортными потоками в сети городских дорог с целью увеличения пропускной способности сети. Для достижения поставленной цели необходимо решить следующие задачи:
разработать на основе сетевого оператора вычислительный метод для синтеза логического управления динамической системой;
исследовать и выбрать математическую модель управления транспортными потоками в сети городских дорог;
выбрать и обосновать критерии оптимизации для задачи синтеза системы управления транспортными потоками в сети городских дорог;
разработать программный комплекс для решения практических задач синтеза систем управления транспортными потоками в сети городских дорог на основе метода логического сетевого оператора.
Методы исследования, используемые в диссертации, основываются на результатах, полученных в областях теории управления, системного анализа, методах оптимального управления, теории графов, теории алгоритмов.
Новизна научных результатов.
В применении нового вычислительного метода логического сетевого оператора для синтеза системы логико-функционального управления динамическими объектами.
В адаптации модели управления движением транспортных потоков в сети городских дорог, построенной на основе теории управляемых сетей с учетом маршрутов движения части потоков и различных форм управления светофорами на регулируемых перекрестках.
Практическая значимость результатов работы заключается в том, что разработанный метод синтеза предназначен для построения системы управления транспортными потоками в сети городских дорог. В диссертации приведен пример синтеза системы управления транспортными потоками в сети городских дорог. На основании разработанных алгоритмов создан программный комплекс для синтеза систем управления.
Апробация результатов, полеченных в диссертации, подтверждается докладами на семинарах кафедры Кибернетики и мехатроники и на ежегодных конференциях профессорско-преподавательского коллектива Российского университета дружбы народов
Результаты диссертации опубликованы в 4 научных трудах, общим объемом 2,5 п.л., из которых 3 работы, объемом 1,5 п.л. опубликованы в журналах, рекомендуемых ВАК РФ. В совместных работах результаты принадлежат соавторам в равных долях.
Структура диссертации. Диссертация состоит из введения, четырех разделов, заключения, списка литературы. Объем работы - 115 страниц, включая 32 рисунка и 5 таблиц. Список литературы содержит 132 наименования.
Метод генетического программирования
В последнее время появился синергетический метод синтеза систем управления, который назван авторами методом аналитического конструирования агрегированных регуляторов [10,11,18,34,57,62]. Метод включает на первоначальном этапе построение в пространстве состояний объекта управления гладких многомерных поверхностей, называемого инвариантным многообразием, в окрестности которого должны существовать оптимальные траектории системы. Переменные, в пространстве которых определяется многообразие, называются агрегированными и представляют собой гладкие функции от переменных пространства состояний. Далее для агрегированных переменных строится система линейных дифференциальных уравнений. Полная производная агрегированных переменных по времени включает производные по времени компонент вектора состояний объекта, т.е. правые части дифференциальных уравнений объекта. В итоге получаются нелинейные уравнения относительно переменных состояния, включающие управление. Решение полученных уравнений относительно вектора управления и учет требования устойчивости уравнений для агрегированных переменных позволяют найти управление в виде функции от вектора состояний объекта, т.е. решить задачу синтеза.
Основным слабым местом метода аналитического конструирования агрегированных регуляторов является субъективный подход при построении инвариантного многообразия. Метод применим в тех случаях, когда поведение оптимальной системы управления очевидно. Тогда можно построить приблизительно траектории оптимального движения и написать уравнения для инвариантного многообразия. В подавляющем большинстве случаев оптимальное поведение системы очевидно только при синтезе систем стабилизации. Другим существенным недостатком метода аналитического конструирования агрегированных регуляторов является необходимость решения системы нелинейных уравнений относительно управления. При решении необходимо учитывать ограничение на управление, поэтому желательно, чтобы в функционале качества было предусмотрено уменьшение величины управления. Таким требованиям отвечает квадратичный функционал, который часто используется для задач синтеза систем стабилизации.
На практике при решении задачи синтеза систем управления часто первоначально решают вариационную задачу оптимального управления [10,11,18,34,57,62,64,70,75] и находят управление как функцию времени. Найденное управление называют оптимальной программой управления, а решение системы уравнений, описывающей объект управления, для оптимальной программы управления называют программной траекторией. Оптимальные траектории позволяют исследовать оптимальное поведение системы в пространстве состояний. Дальнейший синтез системы управления заключается в построении регуляторов, которые обеспечивают стабилизацию объекта в окрестности программной траектории. При синтезе регуляторов используют линеаризацию уравнений модели объекта управления в окрестности программной траектории, что позволяет использовать широко известные методы синтеза линейных регуляторов.
В последнее время с развитием вычислительной техники» появились методы, которые позволяют конструировать вычислительные алгоритмы для нахождения аналитических решений в виде математических выражений. К таким методам следует отнести метод генетического программирования [126] и метод сетевого оператора [39,44-46,48,50,49,119-121].
В генетическом программировании [38,41,42,125] для описания математического выражения используется строка символов, в которой в определенной последовательности записаны символы, обозначающие операции и операнды. Как правило, в генетическом программировании используется префиксная символьная запись, в которой после символа операции следуют символы операндов. Для каждой операции известно количество используемых в ней аргументов. Если аргументов является снова операции, то количество аргументов новой операции также учитывается.
По символьной префиксной записи математического выражения с помощью несложного алгоритма [8] вычисляют значение математического выражения. Для поиска решения в виде символьной записи в генетическом программировании используют генетический алгоритм.
Согласно правилам работы генетического алгоритма первоначально генерируют множество возможных решений или хромосом в виде строк символов, каждая из которых представляет собой математическое выражение. Потом оценивают каждое возможное решение с помощью функции приспособленности, которую для оптимизационных задач строят на основе целевых функций (1.3). На следующем этапе на основе отобранных возможных решений, которые называют родителями, с учетом их оценок по значениям функции приспособленности воспроизводят новые возможные решения, которые называют потомками, с помощью специальных операций генетического алгоритма скрещивания и мутации. Вероятность какому-либо возможному решению быть использованным для создания нового решения зависит от его оценки на основе функции приспособленности.
В процессе работы генетического алгоритма наихудшие решения по значениям функции приспособленности отбрасывают. В результате после выполнения некоторого количества циклов воспроизводства новых возможных решений останавливают алгоритм и определяют решение по значению функции приспособленности.
При воспроизводстве новых решений в генетическом программировании используются операции скрещивания и мутации. Данные операции отличаются от подобных операций генетического алгоритма. Пи выполнении данных операций используется древовидная структура символьной записи математического выражения.
Генетический алгоритм на основе метода вариаций
Рассмотрим задачу синтеза системы управления транспортными потоками в сети городских дорог. Имеется сеть городских дорог. Сеть представляет собой участки дорог, соединенные между собой через регулируемые и нерегулируемые перекрестки. На регулируемых перекрестках расположены светофоры, которые обеспечивают изменение конфигурации сети, соединяя или разрывая связи между отдельными участками дорог. Определение сети городских дорог связано с наличием регулируемых перекрестков, расположенных на небольшом расстоянии друг от друга. На сеть также поступают входные транспортные потоки. Характеристики транспортных потоков, поступающих на сеть и расположенных в сети известны. На всех перекрестках сети определены величины пропускных способностей маневров, совершаемых транспортом. Часть дорог, по которым транспортные потоки уходят из рассматриваемой сети, определены как выходные участки дорог. Управление потоками транспорта в сети осуществляется с помощью переключения рабочих фаз светофоров. Необходимо найти функцию зависимости управления рабочими фазами светофоров от величин транспортных потоков на всех участках дорог сети. Управление должно обеспечить за заданное время прохождение через сеть максимального количества автомобилей, при этом на всех дорогах сети количество автомобилей не должно превысить допустимой величины.
Особенности управления транспортными потоками в сети городских дорог удобно рассмотреть на примере. Сеть городских дорог с регулируемыми перекрестками приведена на рис. 3.1.
На рис. 3.1. приведен участок городской сети дорог в окрестности площадь у метро Кропоткинская в г. Москве. В периоды загрузки сети на через площадь проходят несколько интенсивных потоков транспорта. Один поток движется в направлении с улицы Волхонка на улицы Пречистенка и Остоженка. Такой же поток движется в обратном направлении. Другие потоки движутся со стороны набережной с Саймоновского проезда на Гоголевский бульвар и обратно.
Потоки пересекаются на площади у метро Кропоткинская. Для развязки потоков на площади установлены три системы светофоров, которые работают независимо друг от друга. Одна система светофоров на пересечении Пречистенки и направления с Гоголевского бульвара в сторону набережной. Вторая система на пересечении Остоженки с площадью и Саймоновский проездом. Третья система светофоров расположена на пересечении Волхонки с площадью и направлением движения по саймоновскому проезду от набережной. На площади имеется два участка дороги, между Пречистенкой и Остоженкой, и между Остоженкой и Волхонкой, на которых транспорт может задержаться в ожидании разрешающих сигналов светофоров. Участки дорог на площади ограничены по вместимости транспорта. Если на какой-либо из этих двух участков дороги в течение нескольких тактов работы светофора приходит больше транспорта, чем уходит, то на этом участке дороги будет переполнение, транспорт заполнит прилегающий к дороге перекресток. Согласно правилам движение транспорта на заполненный перекресток не осуществляется. Возникает состояние затора.
Пусть для сети дорог на рис. 3.1. известно количество транспорта на всех прилегающих к площади дорогах. Даже в этом случае принять решение о длительности рабочих фаз всех светофоров оказывается сложной задачей. Для решения данной задачи необходимо располагать дополнительными параметрами сети дорог и путей движения транспортных потоков. Как видно из простейшего примера длительности рабочих фаз светофоров на перекрестках и сами рабочие фазы должны изменяться в зависимости от количества транспорта на участках дорог. Следует отметить, что рабочие фазы светофоров на перекрестках должны учитывать не только количество транспорта на примыкающих к данному перекрестку дорогах, но и учитывать количество транспорта на остальных участках дорог.
Ситуация усложняется, если в сети имеется много регулируемых перекрестков и большое количество участков дорог с ограниченной вместимостью транспорта.
Задача синтеза системы управления транспортным потоком в сети городских дорог заключается в нахождении функции. Которая определяет зависимость рабочих фаз светофоров на регулируемых перекрестках от количества транспорта на участках дорог сети.
Считаем, что длительности рабочих фаз светофоров кратны некоторой величине, которую называем тактом управления. Реально величина такта управления может составлять 1, 2,..., 10 и более секунд. Переключение фаз светофоров и определения количества транспорта в сети допустимо только на каждом такте управления. Количество дорог в сети п определяет размерность пространства состояний.
Математическая модель на основе метода управляемых сетей
Основной задачей управления является обеспечение прохождения через сеть максимальной величины транспортного потока за счет согласованного переключения рабочих фаз светофоров на перекрестках. Для формализации критерия определим в сети два множества дорог: множество дорог, входящих в сеть и множество дорог, выходящих из сети.
Пусть IQ и її - множества номеров дорог, соответственно, входящих и выходящих из сети. Если в сети п дорог, то справедливы соотношения Транспортный поток на выходящих из сети дорогах не поддается управлению. Дальнейшее движение транспортного потока после его попадание на выходные участки дорог неизвестно. После некоторого количества тактов любой транспорт в сети должен оказаться на каком-либо из выходных участков дорог. Считаем, что за время управления весь транспортный поток суммируется на выходных участках дорог. На транспортную сеть в течение управления не приходят транспортные потоки, кроме тех которые были определены на входящих дорогах. Данные предположения вполне допустимы и могут быть реализованы, если принять условия, что на входящих и выходящих дорогах отсутствуют ограничения по вместимости транспортных потоков. В качестве параметров, определяющих характеристики транспортного потока используют плотность и интенсивность [84]. Под плотностью транспортного потока понимают количество транспорта на единицу длины дороги. Интенсивность транспортного потока определяется количеством транспорта, пересекающего сечение дороги в единицу времени. Предполагаем, что длина дороги измеряется в условных единицах. В качестве единицы времени принимаем один так управления. Тогда показатели интенсивности и плотности будут совпадать. Формально показателем потока считаем некоторое количество транспорта, расположенное на дороге сети. Показатель потока на всех дорогах определяем вектором потока (3.1). Компоненты вектора потока показывают условное количество транспорта на дороге. Данное количество транспорта вычисляется умножением параметров дороги, например ее длины на плотность потока. Предполагаем, что весь транспортный поток имеет конечную величину и равен сумме значений компонент вектора потока. Суммарная величина потока в рассматриваемой сети не зависит от такта управления Целью управления является перемещение за конечное число тактов управления потока с входных участков дорог на выходные участки. Синтезирующая функция (1.8), которая должны быть найдена в результате решения задачи синтеза (3.1) — (3.12) должна по значениям потока на всех участках дорог сети определить управляющие воздействия на светофоры всех регулируемых перекрестков сети, чтобы минимизировать функционал (3.53). Значение терминального функционала (3.52), исходя из принятого условия (3.54), ограничено сверху и снизу
Использование в задаче синтеза функционала (3.53) без учета ограничений (3.12) допускает существование решения рассматриваемой задачи синтеза, так как при любом управлении функционал (3.53) ограничен и любое управление вида (3.10) допустимо.
Управление транспортным потоком осуществляем с помощью переключения фаз светофоров на регулируемых перекрестках сети. Согласно требованиям правил движения переключение светофоров на перекрестках осуществляется в определенном порядке, после каждой рабочей фазы светофора в каждый следующий такт управления следует, либо очередная фаза в строгом соответствии с порядком переключения либо остается та же фаза, которая была ранее. Такое управление называем последовательным. Для последовательного управления каждая компонента управления принимает только два значения.
В особых случаях, когда состояние сети дорог близко к переполнению рабочие фазы светофоров на перекрестках переключаем произвольно. Такой вид управления называем свободным. Свободное управление обычно осуществляет регулировщик. Для свободного управления используем модель (3.4) и вектор управления, компоненты которого показывают номер рабочей фазы светофора (3.10) на соответствующем перекрестке.
В случае свободного управления синтезирующая функция (3.8) также может рассматриваться как многозначный предикат, осуществляющий определение по значению вектора потока набор целых чисел из ограниченного множества значений (3.10).
При длительном управлении транспортным потоком в реальных условиях, как правило, уже рассчитаны длительности рабочих фаз светофоров для различных режимов движения. В таком случае можно сказать, что для модели (3.4) располагаем набором программных управлений
Использование информации о маршрутах движения потоков
Граф конфигурации сети не обязательно является связным и указывает маневры, которые возможно совершить транспорту при определенной комбинации рабочих фаз светофоров на всех перекрестках сети.
Состояние сети определяется количественной характеристикой транспортного потока на каждом участке дороги сети. Количество участков дорог в сети определяет размерность пространства состояния сети.
Количество транспорта в такт управления к определяет вектор потока, компоненты которого указывают на числовую характеристику транспортного потока на каждом отдельном участке дороги сети Размерность п вектора потока х(к) равна количеству участков дорог в сети. Соответственно матрицы смежности А, конфигураций А(и), управлений С и разрешенных фаз F имеют размерность пхп. В рассматриваемом примере имеем 12 дорог в сети, поэтому размерность пространства состояний /? = 12, а соответствующие матрицы имеют размерность 12x12. Движение транспорта на перекрестке распределяется по разрешенным маневрам согласно маршрутам транспортных потоков. Распределение транспортных потоков в пропорциях по допустимым направлениям маневров на перекрестке определяем матрицей распределений D = \сіу J . Компонента djj матрицы распределений D потока указывает, какая доля транспортного потока согласно своему маршруту должна осуществить маневр с участка дороги / на участок дороги у . Маневр с участка / на участок j допустим, если существует связь между этими участками или на базовом графе сети имеется дуга (i,j). Следовательно, для матрицы распределений справедливо условие: б/7у=0, если ац = 0, поэтому матрица распределений имеет ненулевые элементы в тех же позициях, что и матрица смежности базового графа сети. Знание матрицы распределений играет важную роль в управлении транспортными потоками. Практически определение матрицы распределений должны быть предметом исследования движения транспортных потоков в различные периоды времени. Соотношение распределения транспорта по направлениям маневра является основой для вычисления длительности рабочих фаз светофоров. На практике распределение потоков на перекрестке может уточняться в процессе управления. Если учитывать, что матрицы распределений содержит информацию о пропорциях распределения всего транспортного потока с каждого участка дороги по допустимым маневрам, то сумма всех долей потока должна быть равна единице где її - множество номеров выходных из сети участков дорог. Участок дороги / считаем выходным, если он не является входным участком дороги для какого-либо перекрестка сети. На базовом графе сети выходной участок дороги соответствует узлу-стоку, т.е. узлу, из которого не выходит ни одна дуга. В матрице смежности базового графа сети номер выходного участка дороги определяем по номерам нулевых строк, Доля транспортного потока, совершающего определенный маневр с одного участка дороги на другой, не всегда определяет количественную характеристику величины транспортного потока, совершившего маневр. Важной характеристикой является пропускная способность маневра. Если количество транспорта на участке дороги велико, и существует большая доля от этого количества, желающих совершить маневр, то при включении разрешающего маневр сигнала светофора, непосредственно маневр осуществляют только то количество транспорта, которое успевает сманеврировать за время работы разрешающего сигнала светофора. Вполне часто возникают ситуации, когда для совершения маневра всех желающих необходимо несколько включений разрешающих сигналов светофора. Для определения пропускной способности маневра вводим матрицу пропускных способностей B = ,-J, i,j = l,n. Матрица пропускных способностей имеет ту же размерность, что и матрица смежности базового графа сети пхп. Компонента by матрицы пропускных способностей В указывает на количественную характеристику транспортного потока совершающего маневр с участка дороги / на участок дороги j за один такт управления. Матрица пропускных способностей В определяет характеристики маневров, поэтому она имеет нулевые компоненты, в тех позициях, где имеет нулевые компоненты матрица смежности А базового графа сети: by = 0, если ау = 0. Структура матрицы пропускных способностей совпадает со структурой матрицы смежности базового графа сети.
