ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Performance investigation of self-configuring genetic algorithm for spacecrafts' control systems effective variant choice

The article was published in issue no. № 4, 2013 [ pp. 208-213 ]
Abstract:The work of the spacecraft control system is modeled with Markov chains. The models for the technological and command-programming control contours are developed. The way of the calculation of the control contour effectiveness indicators (readiness coefficients and others) is described. The problem of choosing an effective variant for a spacecraft's control system is formulated as a multi-scale optimization problem with algorithmically given functions. Special self-configuring genetic algorithm is suggested to use for choosing effective variants of spacecraft control systems as it is very reliable, has no requirements to settings determination and parameter tuning and requires no expert knowledge in evolutionary optimization from end users (aerospace engineers). The high performance of the suggested algorithm is demonstrated by solving optimization problems. It was shown that the algorithms require the examination of small part of the search space to find solution that greatly accelerates the process of search for a solution of the problem of choosing effective variants of spacecraft control systems.
Аннотация:В данной статье описано моделирование работы системы управления космическим аппаратом с помощью цепей Маркова. Описаны модели технологического и командно-программного контуров для абсолютно надежного наземного комплекса управления, а также способ расчета показателей эффективности (коэффициент готовности космического аппарата и др.) выбранного варианта аппаратно-программного комплекса для систем управления космическим аппаратом. Выполнено обобщение моделей на случай ненадежного наземного комплекса управления, состоящего из подсистем. Проблема выбора эффективного варианта для системы управления космическим аппаратом формулируется как многомерная задача оптимизации с алгоритмически заданными функциями. Предлагается использовать самоконфигурируемый генетический алгоритм, который не требует настройки параметров алгоритма для получения решений высокого качества, что позволит применять данный алгоритм конечным пользователям, инженерам-проектировщикам космических аппаратов, не имеющим специальных знаний в области эволюционной оптимизации, для выбора эффективных вариантов аппаратно-программного комплекса для систем управления космическим аппаратом. Продемонстрирована высокая эффективность самоконфигурируемого генетического алгоритма при решении задач выбора оптимального варианта системы управления космическими аппаратами, заключающаяся в высокой надежности предлагаемого алгоритма при просмотре малой части поискового пространства, что существенно ускоряет нахождение решения.
Authors: Semenkin E.S. (styugin@rambler.ru) - Academician M.F. Reshetnev Siberian State Aerospace University, Krasnoyarsk, Russia, (semenkina88@mail.ru) - , Russia, (epopov@bmail.ru) - , Russia, Ph.D
Keywords: self-configuring, generic algorithm, effective variant choice, optimisation, Markov chains, control contours models, spacecraft control system
Page views: 11048
Print version
Full issue in PDF (7.95Mb)
Download the cover in PDF (1.45Мб)

Font size:       Font:

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

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

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

Постановка задачи

Система контроля и управления орбитальной группировки спутников связи представляет собой автоматизированную распределенную информационно-управляющую систему, которая включает в свой состав бортовой комплекс управления (БКУ) космическими аппаратами, систему телекоммуникации (СТК), командно-измерительные системы (КИС), а также центр управления полетом (ЦУП). Последние три подсистемы объединены в наземный комплекс управления (НКУ). НКУ взаимодействует с БКУ с помощью СТК, а также КИС и систем передачи данных, которые включают в себя узлы связи, каналы и соответствующее оборудование связи ЦУП. БКУ является подсистемой управления космическим аппаратом, которая в режиме реального времени обеспечивает проверку и контроль состояний бортовых систем, а также выполнение программы полета. Кроме того, БКУ обеспечивает взаимодействие с наземными средствами управления. Контрольные функции, выполняемые системой автоматизированного управления, могут быть разделены на подсистемы, называемые контурами управления, каждый из которых выполняет различные функции. Как правило, можно рассматривать технологический контур, командно-программный, целевой и др. [1].

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

При предварительном проектировании системы управления основной задачей является поиск оптимальных характеристик потоков l1, l2, m1, m2, m3, m4, а также p0, то есть нахождение оптимального распределения функций контура между БКУ и НКУ. Если они являются характеристиками имеющихся вариантов программно-аппаратного оборудования, то существует проблема эффективного выбора варианта, то есть задачи дискретной оптимизации.

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

Подпись:  

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

Обобщение моделей

В более сложной постановке задачи оптимизации НКУ состоит из трех групп подсистем (КИС, СТК, ЦУП). Учитывая все подсистемы группы как один объект, получим три подсистемы НКУ. Если они могут выходить из строя, то в граф должны быть добавлены новые состояния и переходы.

Полный граф состояний для этого случая содержит 40 состояний и 146 переходов (рис. 2). Соответствующая система уравнений Колмогорова содержит 40 строк.

При тех же условиях граф состояний для командно-программного контура содержит 96 состояний и более 300 переходов и не может быть приведен здесь из-за его сложности.

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

Применение самоконфигурируемого генетического алгоритма при выборе аппаратно-программного комплекса

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

Для выбора эффективного варианта технологического контура необходимо оптимизировать алгоритмически заданную функцию от 6 дискретных переменных. Пространство оптимизации содержит около 1,67×107 вариантов и может быть просмотрено алгоритмом полного перебора в разумные сроки. В такой ситуации известны лучшие и худшие допустимые значения показателей. После выполнения 100 запусков алгоритма известны также лучшие и худшие значения показателей, полученные в результате выполнения.

При численном тестировании использовались 20 индивидов в 30 поколениях. Это означает, что алгоритм просматривает 600 точек из пространства оптимизации, то есть около 0,0036 % от него. В качестве показателя эффективности алгоритма будем использовать надежность (процент запусков алгоритма, которые дали точное решение), MD – максимальное отклонение полученных решений от лучшего известного; и относительное максимальное отклонение полученных решений от лучшего известного RMD. Производилось сравнение пяти групп алгоритмов, а именно четырех групп с различными вариантами модифицированного равномерного скрещивания (UE, UR, UP, UT) и лучшими вариантами других настроек (селекция, мутация) и SelfCGA. В таблице 2 представлены результаты вместе с оценкой вычислительных затрат (усредненное количество поколений, необходимых для нахождения точного решения). Надежностью в условиях данной задачи называется доля прогонов, в которых было достигнуто требуемое качество решения.

Таблица 2

Сравнение надежности алгоритмов для технологического контура с 5 состояниями

Алгоритм

Надежность

MD (%)

RMD (%)

Поколение

UE

0,89

0,0021

0,3576

26

UR

0,92

0,0017

0,2895

22

UP

0,84

0,0024

0,4087

26

UT

0,97

0,0009

0,1533

23

SelfCGA

0,98

0,0003

0,051

21

Аналогичные оценки для всех трех показателей программно-командного контура даны в таблице 3.

Разница заключается в размере задачи оптимизации. 600 вычислений целевой функции соответствуют 0,057 % от общей размерности пространства оптимизации.

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

Задача поиска оптимального варианта аппаратно-программного комплекса космического аппарата с точки зрения технологического контура управления имеет 11 дискретных переменных. Соответствующее пространство оптимизации содержит около 1,76×1013 точек и не может быть просмотрено при помощи полного перебора, особенно если вспомнить, что рассмотрение одной точки включает решение системы линейных уравнений с 40 переменными. Лучшие и худшие допустимые значения показателей неизвестны, поэтому здесь используются самые лучшие известные решения после нескольких прогонов. Тем не менее можно попытаться получить результирующую таблицу, аналогичную таблице 2.

Таблица 3

Сравнение надежности алгоритмов для командно-программного контура с 5 состояниями

Алгоритм

Показатель

Надежность

MD (%)

RMD (%)

Поколение

UE

T

0,87

6,431

9,028

26

t1

0,76

0,956

3,528

43

t2

0,83

13,392

26,01

28

UR

T

0,95

3,987

5,6

21

t1

0,93

0,341

1,258

39

t2

0,93

11,347

22,04

26

UP

T

0,79

6,667

9,359

28

t1

0,71

1,156

4,266

45

t2

0,74

16,321

31,7

29

UT

T

0,91

4,873

6,84

23

t1

0,81

0,956

3,528

44

t2

0,86

13,392

26,01

25

SelfCGA

T

0,99

3,245

4,555

19

t1

0,96

0,1226

0,4524

33

t2

0,98

9,987

19,397

17

Для оценки производительности алгоритмов мы используем 40 индивидов на одно поколение и 80 поколений за один прогон, то есть алгоритм просматривает около 1,82×10-7 % точек поискового пространства. Результаты численных экспериментов приведены в таблице 4.

Таблица 4

Сравнение надежности алгоритмов для технологического контура с 40 состояниями

Алгоритм

Надежность

MD (%)

RMD (%)

Поколение

UE

0,79

0,0115

0,2178

56

UR

0,86

0,0099

0,1875

48

UP

0,73

0,0121

0,2292

59

UT

0,87

0,0095

0,1799

49

SelfCGA

0,90

0,0092

0,1742

33

Для последней задачи, то есть для модели командно-программного контура управления с 96 состояниями и более 300 переходами, нет подобной информации. Эта задача имеет 13 переменных и содержит 4,5×1015 точек в пространстве оптимизации. Чтобы найти надежные оценки всех показателей, требуется огромное число вычислений. Для нахождения решения алгоритмам требуется просмотреть около 2,2×10-10 % поискового пространства (100 индивидов на 100 поколений). Усредненные результаты 100 прогонов приведены в таблице 5. Это дает нам некоторое представление о сравнительной надежности исследуемого алгоритма.

Таблица 5

Сравнение надежности алгоритмов для командно-программного контура с 96 состояниями

Алгоритм

Показатель

Надежность

Поколение

UE

T

0,76

65

t1

0,67

81

t2

0,75

69

UR

T

0,84

59

t1

0,81

78

t2

0,84

64

UP

T

0,70

69

t1

0,59

76

t2

0,63

72

UT

T

0,83

61

t1

0,72

85

t2

0,77

66

SelfCGA

T

0,91

58

t1

0,87

75

t2

0,89

53

Таблицы 4 и 5 демонстрируют превосходство SelfCGA над всеми альтернативными алгоритмами.

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

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

Литература

1.     Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Поисковые методы синтеза систем управления  космическими аппаратами. Красноярск: СИБУП, 1996. 325 с.

2.     Семенкина М.Е. Самоадаптивные эволюционные алгоритмы проектирования информационных технологий интеллектуального анализа данных // Искусственный интеллект и принятие решений. 2013. № 1. С. 13–23.

3.     Semenkin E.S., Semenkina M.E. The choice of spacecrafts' control systems effective variants with self-configuring genetic algorithm. Informatics in Control, Automation and Robotics. Proc. 9th Intern. Conf. ICINCO’2012, Rome, Italy, 2012, vol. 1, pp. 84–93.

References

1.     Semenkin E.S., Semenkina O.E., Korobeynikov S.P. Search methods for the synthesis of spacecraft control systems. Krasnoyarsk, Siberian inst. of business, management and psycho­logy Publ., 1996, 325 p.

2.     Semenkina M.E. Self-adaptive evolutionary algorithms for data mining information technologies design. Iskusstvenny intellekt i prinyatiye resheniy [Artificial intelligence and decision making]. 2013, no. 1, pp. 13–23.

3.     Semenkin E.S., Semenkina M.E. The Choice of Space­crafts' Control Systems Effective Variants with Self-Configuring Genetic Algorithm. Informatics in control, automation and robo­tics: proc. of the 9th int. conf. ICINCO’2012. Rome, Italy, 2012, vol. 1, pp. 84–93.


Permanent link:
http://swsys.ru/index.php?page=article&id=3687&lang=en
Print version
Full issue in PDF (7.95Mb)
Download the cover in PDF (1.45Мб)
The article was published in issue no. № 4, 2013 [ pp. 208-213 ]

Perhaps, you might be interested in the following articles of similar topics: