Эволюционные алгоритмы для автоматизации проектирования распределенных систем обработки информации и управления

В работе описывается поход к автоматизации моделирования распределенных систем с помощью Марковских процессов и выбора эффективных вариантов таких систем с помощью эволюционных алгоритмов. алгоритм программный управление транспорт К распределенным системам обработки информации и управления относятся системы, в которых объект управления, система сбора и обработки информации об объекте и подсистемы принятия решения разнесены в пространстве. При моделировании функционирования распределенных систем управления (РСУ), авторы используют теорию Марковских процессов с дискретными состояниями и непрерывным временем (Воловик М.А., 1977, Семенкин и др., 2002). С оптимизацией состава аппаратно-программного комплекса РСУ эффективно справляются эволюционные алгоритмы (Семенкин и др., 2002).

Система управления космическим аппаратом (КА) является распределенной системой управления. Все задачи системы управления КА можно разделить на четыре группы, которые называют контурами управления (Семенкин и др., 2002): технологический, командно-программный, целевой, баллистический.

Технологический контур системы управления КА обеспечивает бесперебойную работу аппарата по целевому назначению. В простейшем случае, когда наземный комплекс управления (НКУ) предполагается абсолютно надежным, а бортовой комплекс управления (БКУ) и целевая аппаратура (ЦА), реализующая целевое назначение КА, могут выходить из строя и восстанавливаться, соответствующий Марковский процесс имеет граф состояний, представленный на рис. 1.

Здесь через _i и _i обозначены интенсивности выхода из строя и восстановления подсистем соответственно, а через р₀ — вероятность того что целевая аппаратура будет восстановлена средствами БКУ. По графу состояний для стационарного режима получаем соответствующую систему уравнений Колмогорова-Чэпмена. В данной системе определяются P_i — финальные вероятности пребывания системы в соответствующих состояниях. Показателями эффективности функционирования технологического контура системы управления КА являются коэффициенты готовности КА (k_KA), целевой аппаратуры (k_ЦA), бортового комплекса управления (k_БКУ), наземного комплекса управления (k_НКУ) и системы управления в целом (k_СУ), вычисляемые по финальным вероятностям P_i. В частности, в нашем случае k_КА = P₁, k_ЦA = P₁ + P₃, k_БКУ = P₁ + P₂ + P₄, и т. д. Ограничения накладываются на требуемый объем оперативной памяти бортового компьютера и стоимость структуры системы управления КА. Ограничения имеют вид, соответственно:

.

Целевой контур системы управления КА обеспечивает выполнение требуемых режимов использования целевой аппаратуры (например, ретрансляционного комплекса). Упрощенная схема контура целевого управления состоит из бортового комплекса управления БКУ, центра управления полетом ЦУП, специального центра управления СЦУ и командно-измерительной системы КИС (рис. 2).

Рис. 2. Схема функционирования целевого контура системы управления КА

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

Параметрами аппаратно-программного комплекса являются: н₀ — интенсивность отработки временной программы в БКУ, н₁— интенсивность обработки поступившей заявки в СЦУ, н₂ — интенсивность расчета временной программы в ЦУП, н₃ — интенсивность закладки ВП аппаратурой КИС в БКУ, л₀ — интенсивность отказов БКУ на фазе 0, л'₀ — интенсивность отказов БКУ на других фазах, µ₀ — интенсивность восстановления БКУ аппаратурой КИС, µ'₀ — интенсивность восстановления БКУ аппаратурой ЦУП, p₀ — вероятность восстановления БКУ аппаратурой КИС. Граф состояний в таком случае включает 15 состояний, а показатель эффективности контура ф (среднее время реакции системы управления на поступление заявки) принимает вид:

.

где pi — финальные вероятности, которые рассчитываются алгоритмически из системы линейных алгебраических уравнения (СЛАУ) Колмогорова-Чэпмена, составленной на основе графа состояний.

Следовательно, задача оптимизации среднего времени реакции представляется в виде:

.

где N — число различных вариантов аппаратно-программного комплекса, реализующего функции контура. Ограничения в задаче оптимизации аналогичны введенным выше.

Основной задачей контура командно-программного управления (КПК) является обеспечение формирования, обработки и передачи на КА командно-программной информации и управляющих воздействий, а также реализация режима программно-временного управления. Один из показателей качества функционирования контура — время осуществления программно-временного управления без смены временной программы работы (или длительность автономного функционирования КА по данному контуру), который должен быть максимизирован. Если для большей реалистичности предположить, что подсистемы НКУ являются также ненадежными, то Марковская цепь, моделирующая функционирование КПК может быть представлена виде графа из двадцати одного состояния и переходов между ними (Семенкин и др., 2002). Тогда показатель эффективности КПК Т, характеризующий длительность автономной работы КА, вычисляется по финальным вероятностям следующим образом:

.

Следовательно, задачу оптимизации показателя продолжительности автономного функционирования КА можно представить в виде:

.

где N — число различных вариантов соответствующей аппаратуры.

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

Другим примером распределенной системы обработки информации и управления является система управления движением автомобильного транспорта.

В простейшем случае систему управления дорожным трафиком можно условно представить состоящей из трех подсистем (Бежитский С.С., 2005): центральный комплекс управления (ЦКУ), целевая аппаратура (ЦА) и локальный комплекс управления (ЛКУ). В основе ЦКУ лежит совокупность подсистемы управления и регулирования (ПУР) и подсистемы обработки информации (данных) (ПОИ (Д)), ЦА представляет собой подсистему регистрации параметров дорожного трафика (РПДТ), а ЛКУ включает в себя элементы подсистемы управления и регулирования (ПУР) и подсистемы обработки информации (данных) (ПОИ (Д)), установленные в не посредственной близости к элементам, входящим в состав ЦА. Таким образом, элементы ЛКУ являются вспомогательными объектами генерации управленческих решений, то есть посредниками между ЦА и ЦКУ. Цель элементов ЛКУ — разгрузить ЦКУ, то есть взять часть функций ЦКУ на себя и передавать в ЦКУ лишь готовые результаты работ подсистемы ПОИ (Д) и ПУР.

Соответствующий Марковский процесс имеет граф состояний, представленный на рис. 3.

Рис. 3. Граф состояний технологического контура управления дорожным движением

Здесь через л_i, i = 1, 2, обозначены интенсивности выхода из строя ЦА и ЛКУ соответственно, а через _i, i = 1, 2, 3 — интенсивности восстановления ЦА средствами ЛКУ, ЦА — средствами ЦКУ, ЛКУ — средствами ЦКУ соответственно, p0 — вероятность восстановления работоспособности ЦА средствами ЛКУ (с вероятностью (1-p0), восстановление работоспособности ЦА происходит средствами ЦКУ). Вероятности и интенсивности определяются составом аппаратно-программного комплекса, проектируемого для включения в систему управления. Значения коэффициентов готовности (показателей эффективности) той или иной подсистемы определяются через финальные вероятности, которые находят из этой системы уравнений Колмогорова. На стадии предварительного проектирования системы необходимо среди имеющихся вариантов выбрать состав аппаратно-программного комплекса, максимизирующий показатели эффективности.

Аналогичное моделирование можно провести и для многих других РСУ — системы мониторинга опасных промышленных объектов, системы охранной и пожарной безопасности и т. п. (Семенкин и др., 2002).

Построенные модели функционирования РСУ были реализованы и оптимизированы с помощью программной системы. Разработанная программная система моделирования распределенных систем управления способна проводить сбор, накопление, хранение и обработку информации о проектируемой системе и на основе полученных знаний строить Марковскую модель (строить матрицу переходов), на основе которой строятся показатели эффективности функционирования РСУ. На начальном этапе работы с программной системой в диалоговом режиме, задавая вопросы специалисту-проектировщику на доступном и интуитивно понятном ему языке, осуществляется сбор необходимой информации о проектируемой системе (количество и названия подсистем, способы взаимодействия, возможные состояния, переходы между ними, типы процессов функционирования и т. д.), а затем по полученным и обработанным данным формируется собственная модель функционирования сложной системы. Результатом данного этапа являются граф состояний и переходов системы, его графическое изображение и система уравнений Колмогорова-Чепмена. По значениям финальных вероятностей Марковской цепи, полученным путем решения системы уравнений, вычисляются значения показателей эффективности функционирования проектируемой системы (надежность, быстродействие, производительность, время реакции и т. п.).

В качестве алгоритмов определения полезных (с точки зрения оптимизации) свойств показателей эффективности были выбраны псевдобулевые алгоритмы прямого локального поиска (ЛП). Данные алгоритмы позволили установить свойства описанных выше показателей. Результаты исследования полезных свойств показателей эффективности контуров системы управления КА приведены в таблице 1.

Таблица 1. Результаты работы алгоритмов локального поиска.

В качестве алгоритмов условной и безусловной оптимизации многоэкстремальных показателей эффективности и были использованы генетические алгоритмы — обыкновенный и гибридный (Бежитский и др., 2005а, Бежитский и др., 2005b).

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

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

С помощью данной программы были установлены оптимальные структуры генетического обыкновенного и гибридного алгоритмов (Бежитский и др., 2005b, Бежитский, 2004). Алгоритмы в силу своей стохастической природы сравнивались по трем показателям качества работы: надежность, скорость и разброс скорости. Данные показатели были усреднены по 100-кратным прогонам каждой комбинации алгоритма. Сравнительный анализ обыкновенного и гибридного генетических алгоритмов представлен в таблицах 2, 3 и 4.

Таблица 2. Сравнение показателей эффективности алгоритмов при оптимизации коэффициента готовности КА.

Таблица 3. Показатели эффективности алгоритмов при оптимизации показателя автономной работы КА.

Таблица 4. Показатели эффективности алгоритмов при оптимизации среднего времени реакции системы управления КА.

Из результатов, приведенных в таблицах, видно, что наибольшее значение средней надежности, причем почти всегда с меньшей дисперсией, дает гибридный ГА, моделирующий эволюцию по Ламарку.

Таким образом, гибридный ГА (с эволюцией по Ламарку) представляет собой наиболее эффективную эволюционную процедуру для автоматизации проектирования распределенных систем обработки информации и управления.

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

• 1. Бежитский С. С. Гибридный эволюционный алгоритм для решения сложных задач оптимизации // Вестник университетского комплекса: Сб. научн. тр. Вып. 1 (15). — Красноярск: ВСФ РГУИП, НИИ СУВПТ, 2004. — С. 166−173.
• 2. Бежитский С. С. Выбор оптимальной структуры аппаратно-программного комплекса системы управления движением автомобильного транспорта / С. С. Бежитский // Вестник университетского комплекса. — Вып. 6 (20). — 2005. — С.168- 173.
• 3. Бежитский С. С. Генетический алгоритм условной оптимизации в задаче выбора эффективной структуры системы управления космическим аппаратом / С. С. Бежитский, Е. С. Семенкин, О. Э. Семенкина // Вестник Красноярского государственного университета. Серия «Физико-математические науки», № 4. — 2005. — С. 228−233
• 4. Бежитский С. С., Семенкин Е. С., Семенкина О. Э. Гибридный эволюционный алгоритм для выбора эффективных вариантов систем управления // Автоматизация и современные технологии, № 11. — 2005. — С. 24−31.
• 5. Коэффициент готовности прибора со встроенной системой контроля / М. А. Воловик // Системный анализ и исследование операций. — Новосибирск: ВЦ АН СССР, 1977.
• 6. Семенкин Е. С. Методы обобщенного адаптивного поиска для синтеза систем управления сложными системами / Е. С. Семенкин, В. А. Лебедев. — М.: МАКС Пресс, 2002. — 320 с.