автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.14, диссертация на тему:Оптимизация процессов формирования технологических циклов управления

На правах рукописи

ггь од

2 8 к:о1'1 ш

Ступина Алёна Александровна

ОПТИМИЗАЦИЯ ПРОЦЕССОВ ФОРМИРОВАНИЯ ТЕХНОЛОГИЧЕСКИХ ЦИКЛОВ УПРАВЛЕНИЯ

05.13.14 — Системы обработки информации и управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

Красноярск 2000

Работа выполнена в Красноярском государствен] техническом университете

Научные руководители: доктор технических наук, профессор

Соустин Б.П. доктор технических наук, профессор Ковалев И.В.

Официальные оппоненты:

доктор технических наук, профессор Воловик М.А. доктор технических наук, профессор Семенкин Е.С.

Ведущая организация: факультет прикладной математик кибернетики Томского государственного университета

Защита состоится 19 мая 2000 года в 14 часов на засед; диссертационного Совета Д064.54.01 Красноярс государственного технического университета

С ' диссертацией можно ознакомиться в библис Красноярского государственного технического университета

Ваш отзыв, заверенный печатью, просьба направлять по ад] 660074, Красноярск, ул. Киренского, 26, КГТУ, ученому секре-диссертационного Совета Ловчикову А.Н.

Автореферат разослан 18 апреля 2000 года.

Ученый секретарь диссертационного Совета доктор технических наук, профессор

А.Н.Ловч

Об? - ГХЗ МЛ. / />*Г. /Р

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Большое значение на современном этапе среди множества требований к 1честву ПО, методам и методикам его разработки и сопровождения риобретают такие требования как скорость и стоимостная эффективность гзработки, внешние средства поддержки исполнения, тестирования и ^иза, а также доступность методов и инструментальных средств :ирокому кругу специалистов, ответственных за системы управления КА и шюлогические циклы управления в целом.

Таким образом, существует важная народно-хозяйственная задача: зтоматизация процессов формирования технологии управления КА,

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

Исследования, результаты которых вошли в настоящую работу, выполняются в рамках Программы развития системы спутниковой связи и вещания "Россия", принятой решением коллегии Министерства связи Российской федерации №. 4-1 от 14 февраля 1992 г. и в соответствии с концепцией развития средств железнодорожной автоматики и телемеханики (СЖАТ), одобренной президиумом НТС МПС РФ в октябре 1998г. (протокол № 28 от 7 ноября 1998г.)

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

Поставленная цель- определила следующие основные задачи исследований:

- анализ реализуемости, коррекция и оптимальное конструирование ТЦУ КА на основе разработанного комплекса детерминированных и стохастических моделей;

проведение анализа реальных процессов инженерного программирования ТЦУ, жизненного цикла и проблем проектирования управляющего ПО;

формальное описание постановок оптимизационных задач формирования ТЦУ и поддерживающего их реализацию ПО при сложных алгоритмически заданных целевых функциях и ограничениях;

- построение, обоснование и исследование математических методов и алгоритмов решения моделей формирования ТЦУ и мультиверсионного ПО исполнения технологии управления в интерактивном режиме;

- программная реализация с использованием современных средств и подходов и внедрение разработанных методов и моделей в системах автоматизированного формирования ТЦУ и мультиверсионного ПО исполнения технологии управления.

Методы исследования. Системный анализ и методы теории химизации. Методы теории вероятностей. Методы анализа сетей, •охастические сети. Теория множеств, комбинаторика и теория графов, [ногоатрибутивные методы принятия решений и методы случайного поиска бинарном пространстве.

Научная новизна работы.

1. Разработана унифицированная сетевая модель для формального редставления технологических циклов управления КА различных классов.

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

3. Разработаны математические модели и алгоритмы .втоматизированного формирования программного обеспечения, юддерживающего реализацию ТЦУ КА, и учитывающие алгоритмически ¡аданные на комплексе сетевых моделей ограничения и целевые функции ¡адач.

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

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

6. Доказано, что сепарабельные критерии моделей формирования мультиверсионного ПО являются слабо немонотонными и применение для их оптимизации регулярного локального поиска имеет быстродействие порядка 0(п).

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

8. Формальный аппарат автоматизации процессов формирования ТЦУ реализован в виде интерактивной системы с использованием современных сред и подходов.

Практическая ценность. Разработанные в диссертации модели и алгоритмы формирования ТЦУ КА применены при проектировании высоконадежного ПО систем управления. Созданные на их базе в составе

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

Реализация результатов работы. При непосредственном участии автора диссертации выполнены х/д НИР, в ходе которых разработана и передана в составе САПР управления движением объекта (КрЖД, г. Красноярск) программная система диалогового формирования ПО ТЦУ системы управления перевозочным процессом. Комплекс программ модельного обеспечения ТЦУ применяется при разработке и реализации автоматизированного комплекса технической диагностики. Материалы диссертационной работы введены в учебные курсы и используются при чтении лекций для студентов Красноярского государственного технического университета и Сибирской аэрокосмической академии. Эти материалы нашли отражение в монографии "Технология надежностного программирования задач автоматизации управления в технических системах", г. Красноярск, НИИ СУВПТ и НИИ ИПУ, 2000 г., написанной в соавторстве с И'Н.Давыдовым и А.С.Приваловым, а так же в учебном пособии на английском языке "Data envelopment analysis", г.Красноярск, НИИ СУВПТ и СИБУП, 2000г., написанном в соавторстве с Е.Моргуновым.

Основные тезисы, выносимые на защиту.

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

2. Предложенная аналитико-оптимизационная процедура позволяет решать указанные задачи на основе комбинаций алгоритмического

обеспечения методов случайного поиска и методов анализа сетей в интерактивном режиме.

3. Для задач формирования состава ПО ТЦУ КА разработан комплекс моделей, учитывающий сложные алгоритмически заданные ограничения и

¡левые функции на сетевых моделях и отражающий надежностный фактор О при одно- и многофункциональном исполнении..

4. Разработанное алгоритмическое обеспечение позволяет эффективно ;шать однокритериальные задачи автоматизированного формирования ЦУ и мультиверсионного ПО реализации технологии управления.

5. Предложенный формальный аппарат автоматизированного ормирования ТЦУ КА и пакет "NVS Designer" применимы для втоматизации проектирования широкого класса сложных информационно-правляющих систем, построенных на принципах методологии [ультиверсионного программирования.

Апробация работы. Основные положения и результаты работы прошли сес тороннюю апробацию на всероссийских и международных юнференциях, научных семинарах и научно-практических конференциях. В ом числе, на всероссийской конференции "Гагаринские чтения" (Москва, .996 г.), на международной AMSE конференции ССМ'99 (Santiago de Zompostela, Испания, 1999), так же на международной конференции 'Optimization Days" (Монреаль, Канада, 1997).

Основные положения диссертации и отдельные результаты докладывались на семинарах кафедры СА и ИО Сибирской аэрокосмической жадемии (1995-2000), кафедры САУП Красноярского государственного технического университета (1997-2000), кафедре Системного анализа Дортмундского университета (Германия, 1998-1999).

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

СОДЕРЖАНИЕ РАБОТЫ

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

лимитирование времени ответа ЦУП на запрос от объекта. Ограничения на время реакции связывается в этом случае с выполнением периодических действий в рамках технологического цикла управления.

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

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

Рассмотрены проблемы формирования технологических циклов управления с применением детерминированных моделей. С этой целью изучены процессы управления КА, проведен анализ их характеристик, что обеспечило возможность построения как детерминированных, так и стохастических моделей и реализацию на их базе алгоритмически заданных ограничений и целевых функций оптимизационных задач. При организации эффективного и согласованного по времени ТЦУ достигаются следующие критерии качества: выполнение задач обработки информации и управления при соблюдении директивных сроков, регламентированных ТЦУ; рациональное использование вычислительных ресурсов; минимизация материальных и временных затрат и т.д.

Сетевое представление ТЦУ открывает широкие возможности для использования в моделях анализа реализуемости циклограмм математического аппарата, учитывающего вероятностную интерпретацию. Одна из таких возможностей связана с введением неопределенности в продолжительность реализации задач ТЦУ (аналогично использованию РЕЯТ-методики в сетевом анализе). Однако такая модель представляет собой типичную детерминированную сеть, для полного выполнения которой необходимо выполнение всех дуг, то есть под этим понимается безоговорочное выполнение соответствующих операций ТЦУ. Из этого условия следует, что в такую модель не могут быть включены операции с

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

В этой связи рассматривается возможность использования ггохастического вЕЯТ-анализа при оптимизации формирования 'ехнологических циклов управления. Эта возможность, как упоминалось ¡ыше, связана с использованием сетевых моделей со стохастической :труктурой, так как нередко именно они оказываются наиболее гибкими и юлезными на практике. При анализе реализуемости ТЦУ определяется ггохастическая сеть как сеть, которая может быть выполнена только при 5ьшолнении некоторого подмножества дуг; при этом время выполнения саждой дуги (задачи ТЦУ) выбирается в соответствии с вероятностным распределением. В такой стохастической сети для выполнения узла нет необходимости в выполнении всех дуг, входящих в него. Поэтому в такой модели допускается существование циклов и петель.

Для детерминированного случая рассматривается простой щиклический детерминированный ТЦУ, который имеет СЕКТ-подобную /зловую логику. Такая модель соответствует сети для троектирования/решения ТЦУ. Это указывает на .то, что мы осуществляем зыбор, то есть принимаем решение о том, какие задачи ТЦУ должны быть выполнены для минимизации некоторой целевой функции. Для учета вероятностных характеристик реализации ТЦУ вводится понятие случайных акций и рассматривается возможность многоразовой последовательной реализации ТЦУ до момента успешного завершения.

Пусть N— ациклическая сетевая модель ТЦУ с источниками и стоками (действия, соответствующие задачам ТЦУ, представляются дугами), где множество узлов обозначается V, а множество дуг — Е. Сеть имеет только один исток, который обозначается через г и соответствует началу рассматриваемого ТЦУ. Предполагается, что один из стоков N представляет собой успешное завершение ТЦУ и обозначается л. Оставшиеся стоки, если

они есть, могут представлять собой различные виды неудачного завершения или прерывания процесса управления.

Определение (1). Ациклическую сетевую модель ТЦУ только с одним истоком и со стоками назовем сетью для проектирования/решения ТЦУ, если каждый узел / из N определен через входную характеристику СН^е {0,1,...,|/>(7)|} и выходную характеристику СЯ,+ е {0,1,...,|5(7у|}. Эти характеристики, формирующие узловую логику, имеют следующие

значения: (а) узел активируется сразу же, как только входные действия С/Г, завершаются; (б) как только узел i активирован, то не более С/Г/ выходных действий начинает выполняться. Если узел /' не активируется, то ни одно выходное действие не выполняется.

Для источника г полагаем СНГ = 0, т.е. он всегда активирован. Кроме того, С/Г, - 0 для ieS, где S — множество стоков. Заметим, что если СН~ = 1, то узел / имеет OR-вход, а если CHr - \P(i)\, то тогда i имеет AND-вход. И если "не более" заменяется на "точно" в Опр.1(б), то СН'",• = 1 соответствует вероятностному выходу, а С/Г, = \S(i)\ соответствует детерминированному выходу. Если же заданная сеть N для формирования ТЦУ имеет множество источников R (|Я|>1) и множество RcR, R * 0, активизируется в начале выполнения ТЦУ, то можно формально перевести N в соответствующую одно-истоковую сеть.

Дуговые переменные обозначаются через wtJ, положив wtJ = 1, если (г, j) выполняется ((i,j) еЕ), и wu = 0 — в противном случае. Узловые переменные щ =1 (i eV), если / активируется. Иначе — щ-0, причем ur= 1, т.е. источник всегда активируется. Тогда условия узловой логики (Опр.1(а) и (б)) представляются в следующем виде.

> СИ, и,; (i eV\{rj), (1)

keP(i)

2 wki < СИ, + М, и,; (i eV\{rJ), где М, > | P(i) - CHi |, (2)

ksP{i)

- С/Г, и,; (i eV\S). (3)

Так как решающая модель ациклична, то каждая задача соответствующего ТЦУ либо выполняется только один раз, либо не выполняется вообще. Таким образом, каждая реализация ТЦУ (или реализация сетевой модели) может быть соотнесена с множеством выполняемых задач ТЦУ (выполняемых действий сети) или с функцией м>:Е -» {0,1}; ((и j) £ Е), значения которой задаются как w((i, j)) =: w0 =l, если (i, j) выполняется, и - 0, иначе.

С другой стороны, если некоторая w-я реализация ТЦУ задана, то как узловые, так и дуговые переменные для этого случая специфицированы и можно .говорить о допустимой pecuimaifun ТЦУ , если w удовлетворяет условиям узловой логики. Тогда е = {xv: Е —> {0,1 }j wv удовлетворяет (1)-(3); (/', _/) е Е }, и в — множество всех допустимых реализаций ТЦУ.

Если в решающей сети для формирования ТЦУ обозначить вес дуги %j)eE как длительность dveR. соответствующей задачи ТЦУ, то diV — ошительность и>-й реализации ТЦУ, т.е.. время, требуемое для исполнения всех задач (i, j) при w,t = 1 (согласно Опр.{ \ ) каждое действие начинается в наиболее ранний, возможный при данной vv-й реализации рассматриваемого ГЦУ, срок). Необходимо минимизировать dw при условиях: w активирует j; (wes). Через s* :={ wes | w активирует j} обозначим множество успешных реализаций ТЦУ. Для s* * О

d* - min dw 1 ces

соответствует минимальному значению целевой функции задачи.

Приняв, что каждая реализация ТЦУ начинается с задействования истока г в момент 0, считаем для wee, что // есть время активации узла jeV для w-н реализации, причем trw = 0 и // = оо, если j не активируется в течение w-й реализации ТЦУ. Для j е V\{r} имеем г/ = min{/ > 0 | существуют СН/ , отличные от iePQ) такие, что wy = 1 и t)w + dv < г}.

Кроме того, справедливо dw S tsw V wee*. Тогда dw > t " , если сток s активируется, пока некоторые действия (ij) при wtJ = 1 все еще выполняются. Так как

fj - min tj

wes

самое раннее из возможных времен задействования узла j в течение какой-либо возможной реализации ТЦУ, то очевидно

tcs = min max {(//"'+ d:j) wy }. wei* (ij)e£

Ew ={(i,j) e EI wu=1} — множество задач, выполняемых в течение w-й реализации ТЦУ. Учитывая вышесказанное, можно утверждать, что минимальная длительность успешной реализации ТЦУ равна самому раннему моменту задействования стока s: d*=fs для £**0. Таким образом, мы можем найти величину d*, вычисляя минимально возможные моменты задействования fs (Je V).

Рассматривая моменты /, как компоненты вектора временной развертки (ВВР) ТЦУ, которые удовлетворяют [tf d0) w0 > 0, (i,j) eE; t, > 0, / eV\{r}; tr= 0, можно утверждать, что для некоторой w-й реализации ТЦУ (wes*), отвечают этим ограничениям, а самые ранние удовлетворяют им для

соответствующей минимальной wee*. Соответствующая оптимизационная,, задача имеет вид:

Минимизировать шах {(i,w+ dv) wt]} (<J)e£

при выполнении (1) - (3) и ограничений ВВР (м, = 0).

По сравнению с минимизацией затрат на выполнение ТЦУ мы имеем не только добавочные ограничения, но и более сложною целевую функцию. Кроме того, дополнительно к узловым и дуговым переменным имеются моменты t,(ieV), которые также являются переменными данной оптимизационной задачи.

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

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

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

Процедура, используемая для анализа вероятностных характеристик ТЦУ, базируется на стохастических сетях типа GERT и совмещает теорию потоков в графах, функции генерации момента и PERT-анализ для. получения результата. Этапы процедуры представлены в диссертации и позволяют вычислять через эквивалентную функцию следующие характеристики функционирования сети: вероятности выполнения конкретного узла; функции генерации момента для времени, связанного с узлом, если он выполняется. Таким образом, стохастическое представление ТЦУ в виде GERT-сети позволяет получить достаточное количество полезной информации о временных характеристиках реализации ТЦУ. Используя неравенство Чебышева, можно показать пределы, в которых будет изменяться фактическое время реализации ТЦУ, а также получить более сильные утверждения. Кроме того, если реальный показатель не соответствует этим оценкам, то строится ряд критериев для проверки гипотез, позволяющих определить перспективные характеристики времени реализации ТЦУ.

В заключение данного раздела отмечается, что рассмотренная GERT-модель является своеобразной альтернативой традиционным методам определения директивных времен реализации ТЦУ, то есть система моделей позволяет учесть случайные отклонения и неопределенность, возникающие непосредственно во время выполнения каждой отдельной задачи ТЦУ. Следовательно, в полученный результат уже включены все случайные колебания и нет необходимости вносить в него дополнительные поправки, не считая тех, которые соответствуют нештатным ситуациям или авариям.'

Во второй главе рассмотрены алгоритмы, предлагаемые для реализации оптимизационных моделей, полученных в первой главе.

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

Формально указанные оптимизационные модели могут быть сведены к задаче псевдобулевой оптимизации вида:

(4)

N еЛ'

5 = ^еЯ? : =от,т</т| (5)

на решение которой и ориентированы алгоритмы метода изменяющихся вероятностей (МИВЕР). Основная трудность в применении этих алгоритмов к решению оптимизационных моделей формирования ТЦУ состоит в том, что переменные моделей многоиндексные, т.е. представляются многомерными матрицами, причем с разной размерностью по каждой переменной. Поэтому был построен алгоритм преобразования многоиндексных переменных моделей в одноиндексные и обратно. В самом общем виде идею алгоритма можно пояснить на следующем примере (см. схему на рис. 1 для случая двухиндексной переменной - версии, задачи).

Первая компонента вектора X описывает 1-ю версию модуля, реализующего 1-ю задачу ТЦУ. Если программный модуль, решающий первую задачу, имеет более одной версии, то следующая координата вектора X будет описывать вторую версию модуля первой задачи и таким образом поочередно перебираются версии модулей каждой из задач.

Версии Задачи

Следовательно, для того, чтобы"определить номер компоненты вектора X, зная соответствующие номера задачи - / и версии - 5, необходимо

росуммировать число версий модулей, участвующих в решении первых (1) задач. И к полученному числу прибавить 5.

Для того чтобы на практике в алгоритмах оптимизации каждый раз не ересчитывать первую сумму (число версий в первых (¡-1) задачах), они росчитываются один раз и запоминаются в векторе индексов - <7, т.е. начение /-й координаты вектора <7 равно числу версий в модулях, частвующих в решении задач с первой по /-ю. Отсюда следует, что начение последней координаты вектора <7 равно п - размерности вектора 'частия X.

Задача обратного перехода (перехода от номера компоненты вектора 'частая к номеру задачи и версии) состоит из последовательного шределения величин /' и 5.

Очевидно, что алгоритмы МИВЕРа не укладываются в традиционную ;хему алгоритмов случайного поиска для непрерывной оптимизации, <оторая в общем случае включает два этапа.

1. В соответствии с некоторым правилом и вероятностным распределением на множестве всех возможных направлений поиска случайным образом выбирается одно из направлений.

2. По заданному алгоритму выбирается длина шага перемещения поиска в выбранном направлении.

Очевидно, что для реализации этой схемы в пространстве булевых переменных необходимо определить понятия направления в В" ■

Определим инверсию я, (1 <1 <п) как подстановку на множестве . И пусть X, УеВ". Тогда направлением К(Х,У)аВ"2 назовем множество таких точек В1, которые можно представить в виде

2 = 71;. »я, X, где я, е!¥(Х,У),

Л !1 'л )т

,пи , такое, что У = (к<п).

/, 12 V /

В соответствии с этим определением для любой точки ХеВ"г существует (Т-1) направлений, каждое из которых однозначно определяется любой точкой УеВ"г либо множеством 1У(Х, У). Длину шага по направлению К(Х,¥) определяем, используя метрику Хэмминга.

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

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

2. По заданному правилу определяется длина шага / < сагУ)). Формируется множество инверсий саг Осуществляется переход в точку 2 = я^ • я^ •... • 7Г,;,я, € IV(Х°, 2).

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

В качестве возможных схем определения направления поиска в диссертации рассмотрены:

- случайная оценка направления поиска,

- оценка направления поиска по наилучшей пробе,

- оценка направления поиска методом пересечения.

В качестве стратегий движения вдоль выбранного направления рассмотрены:

- поиск с парными пробами,

- прямой поиск,

- экстраполяционный поиск.

Приведенные процедуры направленного случайного поиска были реализованы программно и прошли апробацию при решении задач формирования ТЦУ (с использованием приведенного в предыдущем разделе алгоритма преобразования). Численные результаты показали, что в ряде случаев алгоритмы направленного поиска позволяют получить лучшие результаты по сравнению с алгоритмами МИВЕРа, однако проведенных исследований явно недостаточно для конкретных рекомендаций по областям эффективного применения алгоритмов. Регулярные процедуры в отличие от рассмотренных выше рандомизированных гарантируют получение точного решения и позволяют априори оценить трудоемкость его получения, тем более, что анализ

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

Сепарабельные псевдобулевые функции определяются следующим »бразом:

1< /<п

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

Оценкой сверху числа необходимых вычислений значений целевой функции, когда поиск начинается в точке (1,...,1) (самая дальняя от минимума точка) будет п2-п+2 вычислений, а оценкой в среднем (по выбору шчальной точки поиска) будет величина (п2+4)/2-1/2" . Данные оценки юзволяют сравнить эффективность локального поиска на классе :епарабельных псевдобулевых функций с эффективностью других подходов, запример, эволюционных алгоритмов.

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

В работе был доказан ряд утверлсдений позволивших построить так зазываемые «секущие» алгоритмы оптимизации.

Для унимодальной разнозначной на В"2 функции / общая схема :<секущего» алгоритма будет выглядеть следующим образом.

Выбирается произвольно точка Х° е В^ и некоторый ее уровень

Ок (ЛГ°), к = 1, л -1. Полагаем / = О, Ь = п.

2. Определяются Х*к и Xк из условий: ПХ1)<ДХ)УХеОк(Х°)

АХь)<ЯХ'к),ХкеО,(Х1)

Если Хк не существует, то X* = Х*к и переход к п. 5.

Если Хк е Ок_х(Х°), то I = к, к = к -/ (/ = 1Д-/-1).

Если Хк е,то 1 = к,к = к + 1 (/ = \,Ь~к~\).

Если X - / = 2 , то из условия

АХ') = тш{Г(ХО,/(Х')}

определяем X*. Иначе - переход к п. 2.

¿Г Останов,

Здесь / и £ - номера соответственно первого и последнего уровней рассматриваемого на каждом этапе подпространства.

Поясним работу алгоритма.

На первом этапе делим пространство В£ на два подпространства (п.2). Определяем, в каком из них находится X* (п.З). Найденное таким образом подпространство аналогично делим на два (п. 2, 3). И так до тех пор, пока подпространство, содержащее X, не будет состоять из одного уровня (если, конечно, до этого не будет определен минимум). После чего определяется X

(п.4).

Свобода выбора «секущего» уровня Ок(Х°) на каждом этапе

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

Рассмотрено два конкретных алгоритма: Алгоритм 1. в котором «средний» уровень на этапе определяется номерами первого и последнего уровней, и Алгоритм 2, в котором «секущий» уровень делит исследуемое подпространство на равномощные (близкие по мощностям). Доказано, что оценкой быстродействия алгоритма 1 снизу в общем случае будет величина + п, а сверху -

?!(«)= I СИ +п-[1оё2(и-1)] /=1

гае ;0=0, ]х=\п!2\ л=[0"м+лУ2] / = 2,|_1оё2(«-1)]

Для алгоритма 1 в наихудшем случае имеем: /(я) .

Т2(п)= I + »•'(«),

;=1

;е ],(п) - номера , 1(п) - число «секущих» уровней, определенных для

[ЖДОГО.

Легко видеть, что оценка Т2(п) не может быть хуже оценки Т^п).

Показано, что «секущие» алгоритмы, построенные для унимодальных /нкций, можно использовать и при поиске глобального минимума :евдобулевых функций. Вероятность совпадения найденного локального шимума с глобальным будет относительно высокой. Для алгоритмов 1, 2, лример, не менее + п) / 2".

По полученным аналитическим оценкам эффективности алгоритмов юведено исследование их сравнительной эффективности. Показано «имущество «секущих» алгоритмов перед локальным поиском при [тимизации произвольных псевдобулевых функций.

В третьей главе рассмотрена реализация формального аппарата [тимизации формирования и исполнения ТЦУ в виде программной стемы, которая предоставляет пользователю (специалисту проблемной ласти) удобные средства для решения специфических задач в составе [струментальной системы на начальном этапе формирования системы ходных данных (СИД). Диалоговая система формирования (ДСФ) ТЦУ вобождает пользователя-непрограммиста от необходимости углубляться в тали, связанные с составом аппаратно-программных средств, методами ограммирования и организации решения технологических задач работки информации и управления, регламентированных ТЦУ.

Пользователь может формировать ТЦУ и систему исходных данных для зличных КА заданного класса. Это достигается за счет единой формы едставления ТЦУ. Модель ТЦУ специфицируется путем фиксации нечных наборов входных и выходных параметров задач обработки формации и управления из установленного множества имен. В качестве рактеристик задач используются числовые значения из установленного апазона. Аналогичным образом специфицируются компоненты ПО,

которые могут быть использованы для решения конкретной задачи ТЦУ. Эта согласованность возможна при реализации принципов модульного программирования и формализации задач ТЦУ в терминах имен программных модулей.

Тот факт, что язык описания моделей ТЦУ приближен к табличной форме, позволяет использовать большие объемы числовых данных, реализованные на основе реляционных баз данных (БД) и технологий «клиент-сервер». Это обеспечивает эффективность использования таких преимуществ БД, как «независимость» от прикладных программ (реализующих режимы работы ДСФ ТЦУ), минимальную избыточность данных, т.к. одними и теми же данными можно пользоваться при решении различных задач и т.д.

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

Для автоматизированной системы формирования ТЦУ с таким« возможностями описания исходных данных и моделей программисте^ квалификация пользователей не существенна. Качество программно? реализации формируемого ТЦУ во многом будет зависеть не от пользователя (специалиста проблемной области), а от разработчик; инструментальных средств в целом, т.е. от функциональных возможносга подсистем ДСФ ТЦУ.

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

юответствие сформированных моделей и алгоритмов, реализующих эешение поставленных задач.

Собственно оптимизация формирования ТЦУ и исполнения /правления реализована в пакете "NVS Designer".

"NVS Designer" - представляет собой среду проектирования систем /правления, построенных на принципах методологии мультиверсионного программирования.

Пакет реализован с использованием среды визуального программирования Borland C++Builder 3.0 на платформе операционной системы Windows 95/98. Программный код написан с использованием тодхода объектно-ориентированного программирования, что позволило реализовать в приложении наибольшую модульность. Этот факт допускает вменение программного кода отдельных составных частей продукта и без искажения кода других частей. Существует также возможность усиления системы проектирования за счет добавления программного кода, эеализующего оптимизационные процедуры.

Приложение реализовано с использованием основных достоинств операционной системы Windows 95/98: графический интерфейс юльзователя, многозадачность, модульность и т.д.

В версию 1.0 данного программного продукта входят следующие :войства:

• проектирование системы по одной из двух формулировок тостроения мультиверсионных систем управления;

• возможность варьирования всех параметров системы;

• представление структуры системы в виде вектора булевых теременных (вектор участия);

• оптимизация структуры системы с использованием методов юевдобулевой оптимизации;

• возможность задания постановки оптимизационной задачи по /смотрению пользователя;

• наличие следующих оптимизационных процедур: метод юлного перебора, случайный перебор, различные алгоритмы схемы метода «меняющихся вероятностей (СПА, МСПА, СПАБО, МСПАБО) с 1езависимой генерацией компонент вектора вероятностей, в том числе с «пользованием непараметрического восстановления целевой функции, традиционные схемы случайного поиска, различные модификации

локального поиска, секущие алгоритмы;

• графическое представление данных, позволяющее наблюдать за процессом оптимизации в реальном времени;

• возможность сохранения и восстановления данных в виде файлов особого формата (файлы *.nvs);

• ■ функция быстрой загрузки файлов, с которыми приходилось .■ работать ранее;

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

ЗАКЛЮЧЕНИЕ

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

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

2. Предложенные модели и алгоритмы обеспечивают возможность формализованного анализа реализуемости, коррекции и формирования оптимальных технологических циклов управления КА, причем эти этапы поддерживаются типовыми диалоговыми процедурами в составе систем формирования ТЦУ.

3. Разработанные алгоритмические процедуры, объединенные в унифицированную схему анализа, коррекции и оптимизации ТЦУ КА, обеспечивают минимизацию затрат и времени при реализации процессов управления КА, анализ различных аспектов при введении случайных акций и многочисленных исполнений задач, регламентированных технологическими циклов управления КА.

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

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

5. Разработано, математически обосновано и исследовано алгоритмическое обеспечение автоматизированного формирования ТЦУ и мультиверсионного ПО исполнения задач управления.

6. Предложенная диалоговая система формирования ТЦУ КА обеспечивает интерактивный режим для пользователя — специалиста проблемной области — при специальной организации инструментальных программных средств и позволяет эффективно решать поставленные задачи.

7. С использованием среды визуального программирования на основе подхода объектно-ориентированного программирования предложенные модели и алгоритмы автоматизированного формирования ТЦУ и мультиверсионного ПО исполнения задач управления реализованы в пакете "NVS Designer".

8. Разработанное модельное и алгоритмическое обеспечение внедрено в практику проектирования ТЦУ. Результаты решения реальных задач формирования ТЦУ в составе АСТД и системы управления перевозочным процессом показали эффективность разработанных инструментальных программных средств.

Основные положения и результаты диссертации опубликованы в следующих работах:

1. Ковалев И.В., Ступина А.А. Модельное и алгоритмическое обеспечение средств автоматизированного формирования технологических циклов управления// КГТУ: Сб. научн. трудов; под ред. Б.П.Соустина/ КГТУ. Вып.5. Красоярск , 1996. С. 55-63

2. Ступина А.А. Эффективность локального поиска для сепарабельных псевдобулевых функций// Вестник КГТУ, посвященный 65-летию Б.П.Соустина, под ред. Б.П.Соустина/ Красноярск: КГТУ, 1998. С. 282-284

3. Ступина А.А. Решение задач формирования программного обеспечения бортового комплекса управления космическим аппаратом// Тезисы всероссийской молодежной конференции «Гагаринские чтения». Москва, 1996. С. 113-114

4. Stupina A. On optimization of isotone pseudoboolean functions//' Proceedings of International AMSE Conference on Modelling and Simulation, Universidade de Santiago de Compastela 1999, Vol I. Pp. 63-75

5. Antamoshkin A., Stupina A. On class of functions with binary variables// Proceedings of International AMSE Conference on Modelling and Simulation, Universidade de Santiago de Compastela 1999, Vol I. Pp. 31-37

6. Кошкин Ю.Г., Ступина А.Ф. Традиционные схемы случайного поиска

в пространстве булевых переменных// КГТУ: Информатика и систол управления; под ред. Б.П.Соустина/ НИИ ИПУ, вып. 2. Красноярск, 1997.

7. Stupina A. Realization of conventional pattern of random search metho in the space of Boolean variables// Optimization Days, Montreal, 1997. P. 78.

8. Antamoshkin A. and Stupina A. The random search algorithms in t space of Boolean variables.// Symp. OR'97, Jena, 1997. P. 17

9. Koshkin Ju. and Stupina A. The cutting off techniques for poiimoc pseudoboolean optimization.// Symp. OR'97, Jena, 1997. P. 18

10. Евстигнеев В.Ф., Привалов A.C., Ступина А.А. Мультивереионн модели формирования многофункциональных информациош программных комплексов систем эксплуатации искусственных сооружен|[ Сборник статей и материалов по 100-летию КЖД "Ресурсосберегаюш технологии, перспективное оборудование и аспекты системы управлен Красноярской железной дорогой", Красноярск: НИИ СУВПТ и НИИ И1Т 1999. С. 283-295

11. Давыдов И.Н., Привалов А.С., Ступина А.А. Технолог надежностного програм-мирования задач автоматизации управления технических системах.- Красноярск: НИИ СУВПТ и НИИ ИПУ. 2000. 206

12. Morgunov Е., Stupina A. Data. Envelopment Analysis. Study Aid Krasnoyarsk: RICSWPT and SIBMP, 2000. Part I - 33 p., Part И - 31 p.

13. Stupina A. Optimization of separable pseudoboolean function. Lehtst fuer Sistemanalyse. Jahresbericht 1998/1999. Prof. Dr.-Ing. H.-P. Schwefel, Pi Dr. W. Banzhaf. Universitaet Dortmund

14. Antamoshkin A. and Stupina A. Optimization of separable pseudobuh functions in linear time. - Informatika, Vol. 11, No. 1, 2000. P. 11-13

15. Ковалев И.В., Ступина А.А. Анализ постановок оптимизационн задач мультиверсионного программирования. Информатика и систе управления: Межвуз. сб-к научн. трудов/ Отв. ред. Б.П.Соустин. Красноярск: НИИ ИПУ, 1999. -С.99

96-101

Ступина Алена Александровна Оптимизация процессов формирования технологических циклов управления

а

Автореферат

Подписано к печати 10.04.200 Уч. изд.л. 1,5

Тираж 100 экз

Формат 60\84 '1(-Закат X;7

Oiпечатано в НИИ СУВПТ 660028. г. Красноярск, ул. Баумана, 20-в