ПРИМЕНЕНИЕ  АДАПТИРОВАННОГО  ГЕНЕТИЧЕСКОГО  АЛГОРИТМА  ДЛЯ  ФОРМИРОВАНИЯ  СУБОПТИМАЛЬНЫХ  ПЛАНОВ  РАБОТЫ  ЭКИПАЖА

Орловский  Николай  Михайлович

ведущий  инженер,  Донской  филиал  Центра  тренажеростроения,  РФ,  г.  Новочеркасск

E.mail: 

APPLICATION  OF  ADAPTED  GENETIC  ALGORITHM  FOR  SUBOPTIMAL  CREW  ACTIVITY  SCHEDULING  FORMATION

Orlovsky  Nickolay

leading  engineer,  Don  Department  of  Simulation  Systems  Design  Center,  Russia,  Novocherkassk

АННОТАЦИЯ

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

ABSTRACT

The  article  describes  the  application  of  adapted  genetic  algorithm  for  crew  activity  scheduling  formation  on  cosmonauts  example.  The  author  proposed  a  new  modification  of  single-point  crossing  operator,  which  makes  it  possible  to  place  an  activity  in  the  most  suitable  moment  of  time  in  planning  horizon.  The  results  of  set  experiment  are  presented.  This  experiment  consists  in  comparison  efficiency  of  plan  formation  with  operator-scheduler  and  with  adapted  genetic  algorithm.

Ключевые  слова :  генетический  алгоритм;  планирование.

Keywords :  genetic  algorithm;  scheduling.

Для  успешного  управления  различными  эргатическими  системами  [1]  необходимо  проводить  качественное  планирование  деятельности  группы  исполнителей,  посредством  которых  осуществляются  управляющие  воздействия.  В  случае,  когда  каждому  специалисту  из  группы  отведена  определенная  роль  в  достижении  единой  для  всех  целевой  задачи,  то  речь  идет  об  экипаже.  Экипаж  выступает  в  качестве  одного  из  звеньев  структуры  управления  такими  техническими  объектами,  как:  пилотируемая  орбитальная  станция,  самолет,  подводная  лодка,  глубоководный  водолазный  комплекс.

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

В  работе  [2]  приведена  многокритериальная  математическая  модель  формирования  субоптимальных  планов  действий  экипажа  на  примере  космонавтов  Российского  сегмента  Международной  космической  станции  (РС  МКС).  Для  решения  многокритериальной  постановки  задачи  был  разработан  адаптированный  ГА,  на  каждой  итерации  которого  решаются  две  задачи:

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

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

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

1.  Из  множества  родительских  кодировок  выбираются  две  последовательности    и  ;

2.  Случайным  образом  с  равной  вероятностью    выбирается  точка  разрыва  ;

3.  Последовательности    и    разрываются  в  одной  и  той  же  точке  ;

4.  Из  полученных  четырех  участков  родительских  кодировок  ,  ,    и    формируются  особи  двух  потомков  путем  обмена  участками  крест-накрест  ,  .

Рисунок  1.  Перекрестный  обмен  участками  векторов  решений  при  одноточечном  кроссинговере

Планирование  действий  экипажа  РС  МКС  в  настоящее  время  осуществляется  с  помощью  программно-аппаратного  комплекса  «Автоматизированная  система  планирования  РС  МКС»  (АСП  РС  МКС),  которая  учитывает  все  особенности  организации,  контроля  и  управления  деятельностью  экипажа  и  наземного  персонала  [3].  Большинство  действия  по  составлению  расписаний  работы  экипажа  выполняется  планировщиком  вручную,  что  требует  определенного  времени  на  формирование  итоговой  версии  плана  и  не  исключает  возникновения  нарушений  правил  планирования.  Предложенный  ГА  позволяет  создавать  планы  таким  образом,  что  все  включенные  в  них  операции  полностью  удовлетворяют  системе  заявленных  правил  и  ограничений.

С  целью  проверки  эффективности  применения  адаптированного  генетического  алгоритма  [2]  для  формирования  планов  работы  экипажа  РС  МКС  были  разработаны  две  имитационные  модели  [4]:  1)  модель  процесса  подготовки  планов  действий  экипажа  РС  МКС  специалистом  группы  планирования;  2)  модель  формирования  планов  действий  экипажа  с  использованием  предложенного  генетического  алгоритма.

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

Первый  эксперимент  заключался  в  изменении  объема  операций  в  исходном  множестве  при  фиксированных  значениях  остальных  параметров.  Результаты  измерений  приведены  в  таблице  1  и  на  графике  рисунка  2.  Среднее  значение  отношения  общего  времени  занятости  планировщика  за  день  ко  времени  работы  генетического  алгоритма  получилось  равным  9.  На  основе  анализа  данных  таблицы  1  можно  также  сделать  выводы  о  том,  что  среднее  время  планирования  одной  работы  специалистом  уменьшается,  в  то  время  как  количество  минут,  затраченное  алгоритмом  на  формирование  плана,  увеличивается.  Это  происходит  потому,  что  число  «простых»  операций  растет  вместе  с  общим  количеством  операций  на  размещение.  Время  работы  адаптированного  генетического  алгоритма  также  увеличивается  с  ростом  общего  количества  операций  в  исходном  множестве,  которое  следует  запланировать.

Таблица  1. 

Итоги  эксперимента  (изменение  количества  операций)

Рисунок  2.  Результаты  испытаний  имитационных  моделей  при  различном  количестве  операций  в  исходном  множестве

Второй  эксперимент  заключался  в  изменении  количества  процедур  перепланирования  в  течение  дня  с  5  до  15  при  фиксированных  значениях  всех  остальных  параметров.  Испытания  проводились  на  наборе  из  160  операций.  Результаты  эксперимента  приведены  в  таблице  2  и  на  графике  рисунка  3.  Анализ  данных  показал,  что  уже  при  12  процедурах  перепланирования  в  течении  8-ми  часового  трудового  дня  планировщику  требуется  больше  времени,  чем  8  часов,  чтобы  успеть  завершить  последнее  включение  срочной  работы  в  план.  Среднее  значение  отношения  общего  времени,  затраченного  на  подготовку  планов  оператором-планировщиком  и  генетическим  алгоритмом,  получилось  равным  7.

Таблица  2.

Итоги  эксперимента  (изменение  количества  процедур  перепланирования)

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

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

Список  литературы:

1.Лозгачева  Т.М.,  Завалишин  Ю.К.  Исследование  систем  управления:  учеб.  пособие.  Н.  Новгород:  Нижегород.  гос.  архит.-строит.  ун-т,  2004.  —  102  с.

2.Орловский  Н.М.  Исследование  математической  модели  формирования  оптимальных  планов  функционирования  группы  специалистов  //  Современные  проблемы  науки  и  образования:  электрон.  журн.  —  2014.  —  №  3.  —  []  Режим  доступа.  —  URL:  http://www.science-education.ru/117-13639,  свободный.  —  Загл.  с  экрана  (дата  обращения:  24.06.2014).

3.Станиловская  В.И.,  Беляев  А.М.,  Потоцкий  С.И.,  Козлечков  А.Г.,  Колокольцева  О.М.,  Будникова  Т.С.  Автоматизированная  система  планирования  полета  Российского  сегмента  Международной  космической  станции.  //  «Программные  продукты  и  системы»,  —  №  3,  —  2013.  —  С.  48—54.

4.Орловский  Н.М.  Имитационная  модель  процесса  планирования  на  примере  составления  расписаний  для  действий  экипажа  РС  МКС  //  «Наука  XXI  века:  новый  подход»:  материалы  IX  молод.  междунар.  науч.-практ.  конф.  студентов,  аспирантов  и  молодых  ученых,  г.  Санкт-Петербург,  апрель  2014  г.  /  Науч.-издат.  центр  «Открытие».  2014.  —  С.  46—51.