Комаров Ю.Ю. Проектирование и изготовление аэрокосмических аппаратов

Подождите немного. Документ загружается.

Н. А. Максимов, А. М. Фёдоров

Московский авиационный институт (государственный технический университет)

РАЗРАБОТКА И РЕАЛИЗАЦИЯ МЕТОДОВ ПЛАНИРОВАНИЯ

РАБОТЫ СЛОЖНЫХ ИНФОРМАЦИОННЫХ СИСТЕМ

С БОЛЬШИМ КОЛИЧЕСТВОМ ЗАДАЧ И УСТРОЙСТВ

Современное состояние информационных систем, а также их дальней-

шее развитие предполагает их сложную организацию и логику функци-

онирования. При этом часто возникает сложная задача планирования ра-

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

использованы как в целях моделирования и априорного оценивания харак-

теристик системы, так и в целях оптимизации организации системы.

Как показал анализ многочисленных классических методов решения за-

дач теории расписаний, существуют типы задач, для которых эти методы

либо не применимы, либо неэффективны. Примером может служить си-

стема, задачи в которой имеют между собой информационные связи, не

только определяющие последовательность выполнения задач, но и связи

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

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

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

задачами поддержки может быть работа серверов.

Целью данной работы является проверка практической работоспособно-

сти и скорости сходимости предлагаемого ниже алгоритма, реализуемого в

составе разрабатываемого программного комплекса планирования работы

информационных систем.

Предлагаемый алгоритм не имеет строгого математического обоснова-

ния в той части, что он всегда находит оптимальное решение для кон-

кретной задачи, если оно существует. Но его ценность заключается в том,

что при сравнительно низкой вычислительной сложности с помощью него

находится квазиоптимальное расписание. При этом для рассмотренных

сложных систем, характеризующихся большим числом задач и устройств,

было найдено расписание, качественнее которого в смысле срока оконча-

ния другими способами найти не удалось.

Предлагаемый алгоритм положен в основу программных продуктов,

осуществляющих планирование работы:

комплекса технических средств (КТС) управления космическими ап-

паратами (КА) дистанционного зондирования Земли (ДЗЗ);

КТС интерактивной обработки информации ДЗЗ;

181

автоматизированной системы архивного хранения видеоизображений.

Общей чертой перечисленных программных продуктов является то, что

рассматриваемый алгоритм “жёстко зашит” в логику программ. При этом

в части количества, типов задач и устройств их обработки логика алгорит-

ма была намеренно ограничена. Для этих систем это и требовалось, так

как значительной смены характера задач и устройств не ожидалось и для

скорости работы комплексов планирования такое ограничение сказалось

благоприятно.

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

более общем виде для планирования работы различных информационных

систем. Также ведётся работа по изменению алгоритма в сторону рас-

ширения покрываемого им класса задач планирования. Разработан способ

формализованного описания работы информационных систем для дальней-

шего планирования. Ещё одно направление работ — это разработка модуля

программного построения моделей информационных систем.

Суть алгоритма планирования заключается в следующем.

Рассматриваемая система представляется в виде информационной мо-

дели, которая состоит из:

множества задач обработки J;

множества средств обработки U;

матриц смежности (i,j), p=1,2,3, содержащих всю информацию о

связях между задачами,

— номера задач из множества задач;

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

, , определяющие время выполнения частей задачи

и интервалы между смежными задачами;

объем ресурса доступности , необходимый для выполне-

ния каждой задачи;

допустимый интервал времени , в котором возможно выпол-

нение

-й задачи;

объем ресурса доступности -го средства обработки, который

может быть выделен в момент времени

для решения задач.

При наличии такой информации решение задачи составления расписа-

ния отдельных вычислительных процессов однозначно определяется век-

тором X=[X

,X ,...,X ], каждая компонента которого содержит две со-

ставляющие: X

=[t,u]. Здесь t - время начала выполнения задачи c

номером

,u - номер средства обработки, на котором выполняется i-я

182

задача. Любой вектор X может быть проверен на допустимость. Для этого

сформулирован ряд ограничений:

моменты начала и окончания каждой задачи должны отвечать матри-

цам смежности;

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

задача в определённый момент времени может выполняться на тех

устройствах, у которых имеется достаточный объём ресурса доступ-

ности;

каждое средство обработки в один момент времени может быть занято

не более чем одной задачей.

На 1-м этапе осуществляется генерация основной последовательности

задач — перечень всех номеров, принадлежащих множеству J. Эта последо-

вательность строится на основе базовой диаграммы, которая представляет

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

Для реализации каждой задачи выделяется персональное вычислительное

средство из U с максимальной производительностью, и все временные

интервалы выполнения задач сдвинуты к концу настолько, насколько это

позволяют информационные связи задач и интервалы их возможного вы-

полнения. При этом ограничения по проверке ресурса доступности не учи-

тываются.

На 2-м этапе для каждой задачи из основной последовательности при-

нимается решение о её назначении на одно из средств обработки. При

таком подходе, если задачи из рассматриваемой последовательности раз-

местить по устройствам нельзя, это, как правило, можно определить без

полного просмотра последовательности. Если задачи в текущей последова-

тельности не могут быть размещены, производится перестановка порядка

задач и проверяется новая последовательность. Количество перестановок

сильно ограничено условиями. Первая удачная последовательность может

считаться допустимым расписанием, а лучший результат из всех возмож-

ных последовательностей — квазиоптимальным расписанием. В большин-

стве случаев первая последовательность оказывается удачной.

Вычислительная трудоёмкость предлагаемого алгоритма в худшем слу-

чае оценивается выражением

бд

,где

бд

— трудоем-

кость построения базовой диаграммы;

— количество средств обработки;

— количество задач; — количество информационных связей всех типов.

Для разрабатываемого программного комплекса представляет интерес

случай перебора всех последовательностей, т. е. именно худший случай

183

в плане вычислений. Тем не менее, пользователю предоставляется выбор

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

Программный комплекс разрабатывается в виде MDI-приложения сре-

ды Windows 98 и выше. Дочерние формы являются редакторами данных,

относящихся к задачам и к устройствам. Исходные данные для планирова-

ния объединяются в проект, для которого предоставляется свой редактор

общих данных — количество задач, устройств, длина имён, пути к файлам

и т. п. Так как широкий круг задач планирования — это построение рас-

писаний для различных производств, разработан специальный редактор

данных по объектам обработки.

Здесь имеет смысл остановиться на понятии отдельного процесса (ОП),

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

а по нему — матрицы смежности. С помощью представления информаци-

онной модели в виде набора связанных ОП, можно свести многостадийную

систему к одностадийной. ОП — система взаимосвязанных задач, которые

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

должна быть вынесена в свой ОП. Системы, специфика работы которых

представляет собой обработку некоторых объектов, имеют информацион-

ную модель, в которой каждому объекту обработки соответствует свой ОП.

Одинаковым объектом в смысле обработки соответствуют одинаковые ОП,

каждой задаче в ОП соответствует фаза обработки одного объекта. Так как

в рамках группы одинаковых объектов при любом расписании они будут

отправляться на первую фазу обработки последовательно, соответствую-

щие им ОП будут иметь информационные связи между своими первыми

задачами. Причём последовательность первых задач одинаковых ОП не

важна, так как объекты равноправны.

Упомянутый редактор по объектам обработки позволяет по общим ха-

рактеристикам каждого экземпляра объекта обработки и количествам этих

экземпляров в группах автоматически породить соответствующие задачи с

готовыми информационными связями. Эта операция довольно трудоёмка

для пользователя в случае отсутствия редактора.

Программный комплекс реализуется в виде модульной структуры, т. е.

он представляет собой набор откомпилированных компонентов. Это поз-

воляет облегчить организацию разработки между несколькими програм-

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

интерфейсу между ним и другими составными частями.

Отдельным элементом программного комплекса выступает система ав-

томатизированного построения имитационных моделей. Сформулирован-

ная информационная модель является входными данными как для плани-

184

рования, так и для построения имитационной модели. Таким образом, имея

расписание, пользователь получает возможность определить оценку неко-

торых характеристик системы в результате имитационного моделирования.

Это полезно, когда требуется определить значение критерия эффективно-

сти, в выражении которого фигурируют оценки характеристик системы.

Реализованная в настоящее время программа строит расписание для

упомянутых вначале систем за время, меньшее секунды (использовался

ПК на базе микропроцессора Intel Celeron 2.8 ГГц). Первая система ха-

рактеризуется 44 задачами и 5 устройствами, среди задач есть две задачи

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

ёмким — потребовалось 146 перестановок. Система характеризуется 60 за-

дачами и 7 устройствами. Третья система представлена 27 задачами и 8

устройствами. В настоящий момент выставлены следующие ограничения

на количество объектов в информационной модели: 200 устройств, 4000

задач, 500 информационных связей, 500 ОП. Разрабатываются ёмкие по

количеству объектов информационные модели.

Упомянутая скорость построения расписания позволяет осуществлять

оперативное перепланирование, например, в связи изменением состояния

устройств.

Используя предлагаемый подход, можно решать задачу планирования

вспомогательного производства на базе планирования основного произ-

водства. Если представить работу оборудования вспомогательного произ-

водства в виде задач поддержки, то построение расписания для основного

производства автоматически определит потребность во вспомогательном

производстве во времени.

Если объекты обработки имеют различные приоритеты, то это может

быть отражено в информационной модели в виде информационных связей

последних задач в ОП соответствующих объектов.

К настоящему моменту не снят основной недостаток предлагаемого

подхода. В общем случае считается, что каждая задача может быть вы-

полнена на любом устройстве. Если надо запретить выполнение задачи

на каких-либо устройствах, для них может быть определено время обра-

ботки, большее интервала планирования. В терминах объектов обработки

указанная особенность означает, что на каждой фазе обработки доступен

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

имеются альтернативные ветви устройств, по которым может направить-

ся объект обработки. Данный подход позволяет лишь строго определить

ветвь для каждого объекта.

Основная идея, предложенная для решения этой проблемы, заключает-

185

ся в следующем. Проводится предварительное имитационное моделиро-

вание работы такой системы с некоторыми разумными правилами выбора

объектами ветвей; оцениваются доли объектов, направляемых по этим вет-

вям. Далее планируется работа системы с учётом этих долей, затем доли

корректируются в сторону улучшения, и проводится новое планирование.

Последняя операция может быть повторена несколько раз.

Развитие разрабатываемого программного комплекса планирования

идёт по следующим направлениям.

1. Исследуется набор правил, позволяющих глубоко проанализировать

формируемую пользователем информационную модель на непротиво-

речивость, чтобы помочь ему на этапе проектирования выявить зара-

нее несостоятельные варианты. Такой анализ является нетривиальной

задачей для систем в общем виде.

2. Исследуются другие алгоритмы построения расписаний с целью их

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

составляли с имеющимся библиотеку методов. Это увеличит универ-

сальность программы и круг внедрения. Интерес представляют подхо-

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

нейросетей.

3. Разрабатывается система визуального проектирования информацион-

ного графа задач.

4. Планируется представлять компоненты программного комплекса в ви-

де программ-серверов, допускающих внешнее управление, что позво-

лит включать программный комплекс планирования в контур другого

ПО.

Р. Р. Захарян, А. А. Федяев

Московский авиационный институт (государственный технический университет)

РАЗРАБОТКА АЛГОРИТМОВ ОБНАРУЖЕНИЯ

И ИДЕНТИФИКАЦИИ ОБЪЕКТА

Актуальность темы исследования методов обнаружения и распознава-

ния образа лица обусловлена тем, что в современных условиях реально

186

встала проблема повышения безопасности стратегически важных объек-

тов в связи с растущей угрозой терроризма.

Целью данной работы являлась разработка алгоритмов, обеспечиваю-

щих поиск, обнаружение и идентификацию графических объектов в по-

ступающем на вход визуальном ряде изображений.

Для выполнения поставленной задачи был произведен сравнительный

анализ как широко применяемых на практике математических методов, так

и узкоспециализированных и малораспространенных методов, на осно-

вании чего произведен выбор наиболее перспективных для дальнейшей

проработки методов: для поиска графических объектов метод адаптивно-

го усиления, а для идентификации — метод скрытых марковских моделей.

Рассмотрим разработанные алгоритмы.

Алгоритм адаптивного усиления, известный также под названием

AdaBoost [1-3], предназначен для обнаружения в исходных графических

данных заданного объекта. AdaBoost позволяет работать со слабыми мо-

делями обучения. Целью этого алгоритма является поиск окончательной

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

ошибок на данном распределении D маркированных примеров обучения.

В отличие от других алгоритмов усиления AdaBoost адаптивно настраи-

вается на ошибки слабых гипотез, возвращаемых слабыми моделями обу-

чения; ограничение производительности AdaBoost зависит от производи-

тельности слабой модели обучения только на тех распределениях, которые

фактически формируются в процессе обучения.

Алгоритм AdaBoost работает следующим образом. На итерации

алго-

ритм усиления реализует слабую модель обучения с распределением

множества примеров обучения . Слабая модель обучения вычисляет ги-

потезу

:X Y, которая корректно классифицирует часть примеров обу-

чения. Ошибка измеряется относительно распределения D

. Этот процесс

продолжается

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

ет гипотезы

в единую заключительную гипотезу . Для

того чтобы вычислить распределение

на итерации и заключитель-

ную гипотезу F

, используется простая процедура, описанная вкратце

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

примеров обучения

, т.е. для всех . Для данного распреде-

ления

и слабой гипотезы на итерации n следующее распределение

вычисляется умножением веса примера на некоторое число

[0, 1), если гипотеза корректно классифицирует входной вектор .В

противном случае вес остается неизменным. В итоге все веса заново нор-

мализуются делением на константу нормализации

. В результате “лег-

187

кие” примеры множества , корректно классифицированные предыдущей

слабой гипотезой, будут иметь более низкий вес, в то время как “трудные”

примеры, для которых частота ошибок классификации была высокой, бу-

дут иметь больший вес. Таким образом, алгоритм AdaBoost концентрирует

основной объем весов на тех примерах, классифицировать которые оказа-

лось сложнее всего.

Окончательная гипотеза

вычисляется голосованием (т. е. взвешен-

ным линейным порогом) из множества гипотез

. Это значит,

что для данного входного вектора

окончательная гипотеза дает на выхо-

де метку

, которая максимизирует сумму весов слабых гипотез, которые

определили эту метку. Вес гипотезы

определяется как log , т.е.

больший вес назначается гипотезе с меньшей ошибкой. В табл. 1 пред-

ставлено описание алгоритма.

Таблица

Краткое описание алгоритма AdaBoost

Дано: Множество примеров обучения

Распределение для маркированных примеров

Слабая модель обучения

Целое число , задающее количество итераций алгоритма

Инициализация: для всех

Вычисления: Для выполняются следующие действия.

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

2. Формируется гипотеза

3. Вычисляется ошибка гипотезы

4. Вычисляется

5. Изменяется распределение :

если

в противном случае

где — константа нормализации (выбираемая таким образом, чтобы было

распределением вероятности)

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

188

Важное теоретическое свойство алгоритма AdaBoost было сформулиро-

вано в следующей теореме.

Пусть при вызове алгоритма AdaBoost слабая модель обучения сгене-

рировала гипотезы с ошибками

, , ..., , где ошибка на итерации

алгоритма AdaBoost определяется как

Пусть также и . Тогда ошибка окончательной

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

Согласно этой теореме, если ошибка слабой гипотезы, построенной сла-

бой моделью обучения, лишь немного меньше величины 1/2, то ошибка

обучения окончательной гипотезы экспоненциально стремится к ну-

лю. Однако это совсем не значит, что ошибка обобщения на тестовых

примерах тоже будет мала. Проведенные эксперименты, показали следую-

щее. Во-первых, теоретическая граница ошибки обучения часто оказыва-

ется слабой. Во-вторых, ошибка обобщения зачастую существенно лучше,

нежели это следует из теоретических выкладок.

Второй рассматриваемый алгоритм Витерби является ядром метода

Скрытых Марковских Моделей [4-7] и предназначен для распознавания

поступающих на вход объектов. В данном случае этот алгоритм исполь-

зуется для идентификации сегментов, поступающих от програмной реали-

зации алгоритма AdaBoost. Описанный ниже алгоритм был опубликован

А. Витерби в 1967г. Фрагмент решетчатой диаграммы кода показан на

рис. 1.

Рис. 1. Решетчатая диаграмма

189

Эта решетчатая диаграмма описывает множество кодовых слов усечен-

ного сверточного кода, получаемого при подаче на вход кодера некоторой

последовательности информационных символов и вслед за ней – после-

довательности из нулей, где

— длина кодового ограничения кода. Для

каждого узла решетки мы называем предшествующими узлами те узлы

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

дущий в данный узел на ярусе с номером, задается последовательностью

из информационных символов, при подаче которой на вход кодера со-

держимое регистра кодера совпадет с номером узла. Суть алгоритма —

отыскание пути с минимальной метрикой. Метрикой узла мы называем

метрику оптимального пути, ведущего в узел; метрикой ребра — сумму

метрик соответствующих кодовых символов. Через

обозначим число

ярусов решетчатой диаграммы, описывающей усеченный сверточный код.

Алгоритм Витерби:

1. Инициализация. Номер яруса 0. Метрика нулевого узла приравнива-

ется нулю, за этим узлом закрепляется “пустой” путь.

2. Для ярусов с номерами

для каждого из узлов на ярусе вы-

полняются следующие вычисления: a) находим метрику каждого из

путей, ведущих в узел, как сумму метрик предшествующих узлов и

ребер, связывающих узлы-предшественники с данным узлом; b) на-

ходим путь с минимальной метрикой, и эту метрику приписываем

данному узлу; c) путь, ведущий в узел, вычисляется дописыванием к

пути, ведущему в выбранный предшествующий узел, информацион-

ного символа, соответствующего переходу из узла-предшественника

в данный узел.

3. Путь, соответствующий единственному узлу на ярусе

, выдается

получателю как результат декодирования.

Пути, сходящиеся в одном узле решетки, называют конкурирующими,

а выбранный из их числа наилучший путь — выжившим. Алгоритм Ви-

терби на каждом ярусе решетки из каждого узла решетки “смотрит назад”

на узлы предыдущего яруса, находит метрики конкурирующих путей и

выбирает путь с наименьшей метрикой. В результате к последнему яру-

су выживает единственный путь, обладающий минимальной метрикой из

всех возможных путей в решетке.

Непосредственно в случае использования СММ применяется метод VPC

(Viterbi Path Counting):

1. Создается случайная СММ с конкретной топологией с параметрами

A, B,

190