автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и алгоритмы выбора аппаратно-программного комплекса распределенных систем обработки информации и управления

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

БЕЖИТСКИЙ СЕРГЕЙ СЕРГЕЕВИЧ

МОДЕЛИ И АЛГОРИТМЫ ВЫБОРА АППАРАТНО-ПРОГРАММНОГО КОМПЛЕКСА РАСПРЕДЕЛЕННЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ

05.13.01 -- Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

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

Красноярск - 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М,Ф. Решетнева»

Научный руководитель:

доктор технических наук, профессор Семёнкина Ольга Эрнестовна

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

Ведущая организация:

доктор технических наук, профессор Терехов Виталий Анатольевич кандидат физико-математических наук, доцент Медведев Алексей Викторович

Томский государственный университет

Защита состоится 21 декабря в 11.00 на заседании диссертационного совета Д 212.249.02 в Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газ. "Красноярский рабочий", 31.

С диссертацией можно ознакомиться в научной библиотеке СибГАУ.

Автореферат разослан 20 ноября 2006 г.

Ученый секретарь диссертационного совета

И.В. Ковалев

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

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

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

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

Таким образом, можно утверждать, что разработка средств автоматизации моделирования РСОИиУ с помощью методов теории стохастических процессов и оптимизации выбора эффективных вариантов их аппаратно-

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

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

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

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

2. Формализация выбора эффективных вариантов таких систем в виде оптимизационных задач.

3. Выявление основных свойств оптимизационных задач, возникающих при выборе эффективных вариантов РСОИиУ.

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

5. Анализ свойств разработанных алгоритмов и исследование их эффективности при решении сформулированных задач.

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

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

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

Научная новизна работы заключается в следующем:

1. Построены новые формальные модели выбора структуры РСОИиУ различного назначения, отличающиеся глубиной детализации систем.

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

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

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

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

Работа выполнена в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы» по теме 2006-РИ-16.0/001/07)5 (государственный контракт № 02.438. 11.7043) и 2006-РИ-19.0/001/377 (государственный контраст № 02,442.11. 7337), в рамках НИР 4422 «Разработка и исследование эффективности гибридных методов оптимизации алгоритмически заданных функций дискретных переменных», выполняемой по ведомственной научной программе «Развитие научного потенщгала высшей школы», а также по темплапу СибГАУ «Бионические методы идентификации и оптимизации сложных систем» (№ Б 1.1.05).

Реализация результатов работы. Разработанные модели основных контуров управления космическими аппаратами, программная система моделирования сложных систем Марковскими процессами и гибридные генетические алгоритмы оптимизации переданы НПО прикладной механики (г. Железногорск) в составе отчета по государственному контракту № 02.438. 11.7043.

Моделирование распределенной системы обработки информации и управления сетью автомобильных дорог выполнялась в рамках проекта «Саг Traffic Measurement and Control» Института автоматизации управления Специальной высшей школы (Fachhochschule Ulm, г. Ульм, Германия). Результаты исследования переданы немецкой стороне, о чем имеются подтверждающие документы.

Система автоматизации проектирования распределенных систем обработки информации и управления использовалась в качестве инструмента поддержки принятия решения в ЗАО «А.Р.Т.», занимающегося проектированием, установкой и обслуживанием систем охранно-пожарной сигнализации на крупномасштабных объектах (Красноярский горпо-химический комбинат, Красноярский комбайновый завод, Красноярская гидроэлектростанция и др.), что отражено в акте о передаче и использовании.

Три программные системы, разработанные в ходе выполнения работы, прошли отраслевую и государственную экспертизу и зарегистрированы в ОФАП и ВНТИЦ, что делает их доступными широкому кругу специалистов по моделированию и оптимизации сложных систем.

Разработанные алгоритмы и программные системы используются в учебном процессе при проведении занятий по курсу "Адаптивные и эволюционные методы принятия решений" в Сибирском государственном аэрокосмическом университете, по специальным курсам "Системный анализ и управление", и "Эволюционные алгоритмы оптимизации" в КрасНояр-

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

Основные положения, выносимые на защиту:

1. Система поддержки принятия решений при моделировании Марковскими процессами позволяет автоматизировать моделирование распределенных систем обработки информации и управления.

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

3. Модифицированный гибридный генетический алгоритм условной оптимизации позволяет успешно решать задачи выбора эффективных вариантов РСОИиУ.

Публикации. По теме данной работы опубликовано 25 печатных работ, среди которых три статьи в научных изданиях, входящих в Перечень ВАК. Тринадцать работ опубликованы без соавторов.

Апробация работы. Процесс разработки и результаты, представленные в работе, докладывались и обсуждались па научных конференциях различного уровня, в том числе Международные научно-технические конференции «Интеллектуальные системы и интеллектуальные САПР» (AIS'05, AIS'06, Дивноморское, 2005, 2006 гг.), X Национальная конференция по искусственному интеллекту с международным участием (КИИ'Об, Обнинск, 2006 г.), Международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006 г.), Международная научно-практическая конференция «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2006 г.), Всероссийские научно-практические конференции "Решетневские чтения" (Красноярск, 2003, 2005 гг.), Международная научная конференция молодых ученых «Ломоносов-2005» (Москва, 2005), Всероссийская конференция-конкурс «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2006 г.), а также региональные и межвузовские конференции.

Структура работы. Работа состоит из введения, трех глав, заключения, списка литературы и приложения.

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

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

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

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

В диссертации выполнено моделирование для РСОИиУ трех типов.

В качестве примера РСОИиУ первого типа рассмотрим систему управления космическим аппаратом (КА), а точнее — одного из ее основных контуров.

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

Бели предположить, что процессы, происходящие в подсистемах, являются независимыми простейшими случайными процессами, то подходящим математическим аппаратом для моделирования функционирования целевого контура управления могут быть модели Марковских процессов. Марковский процесс, моделирующий функционирование целевого контура, может быть представлен в виде графа из двенадцати состояний (рисунок 1). Приведем описание состояний. Фаза 1 — обработка заявки, БКУ работоспособен. Фаза 2 — расчет временной программы (ВП), БКУ работоспособен. Фаза 3 - закладка ВП, БКУ работоспособен. Фаза 0 (состояние 4) — отработка временной программы, БКУ работоспособен. 5 - БКУ отказал на фазе 1, восстанавливается аппаратурой КИС. б - БКУ отказал на фазе 1, восстанавливается аппаратурой ЦУП. 7 - БКУ отказал на фазе 2, восстанавливается аппаратурой КИС. 8 - БКУ отказал на фазе 2, восстанавливается аппаратурой ЦУП. 9 - БКУ отказал на фазе 3, восстанавливается аппаратурой КИС. 10 - БКУ отказал на фазе 3, восстанавливается аппаратурой ЦУП. 11-БКУ отказал на фазе 0, восстанавливается аппаратурой КИС, 12-

БКУ отказал на фазе 0, восстанавливается аппаратурой ЦУП. Параметрами аппаратуры являются: Уо - интенсивность отработки временной программы в БКУ, V/ - интенсивность обработки поступившей заявки в СЦУ, у2 -интенсивность расчета временной программы в ЦУП, у,* — интенсивность закладки ВП аппаратурой КИС а БКУ, Х0 - интенсивность отказов БКУ на фазе 0; Л о — интенсивность отказов БКУ на других фазах, Цо — интенсивность восстановления БКУ аппаратурой КИС, р'о — интенсивность восстановления БКУ аппаратурой ЦУП, ро - вероятность восстановления БКУ аппаратурой КИС.

О-рОро

(1-р«)М<>

(1"Ро)цо

(1-Рв>Мо

Рисунок 1. Граф состояний и переходов целевого контура управления

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

Показатель качества функционирования системы г (среднее время реакции системы управления на поступление заявки) принимает вид:

г Р,+Р,+Р,+ Р<+Р<+Р? + Р.+Р, + Р,Ь ^

где р, - финальные вероятности, которые рассчитываются алгоритмически из системы Колмогорова-Чэпмена.

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

г(д,А„/Л)-+ тй—> (2)

где N — число различных вариантов аппаратно-программного комплекса, реализующих функции целевого контура. Добавив ограничения, например, на объем оперативной памяти Мо аппаратуры и потребляемую энергию Щ в виде:

М(у0,Д0,у11Л'()<А/0 и ИЧ^,Л0,уа,Л,0)<ГК0, (3)

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

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

При условии, что ЦКУ абсолютно надежен, соответствующий Марковский процесс имеет ] шый на рисунке 2.-

Рисунок 2. Граф состояний для описания надежности функционирования системы

Описание состояний контура управления, отвечающего за надежность функционирования РСОИиУ дорожным трафиком:

1. Все подсистемы работоспособны.

2. Целевая аппаратура отказала, ЛКУ работоспособен и занят восстановлением работоспособности ЦА, ЦКУ свободен.

3. Целевая аппаратура работоспособна, ЛКУ отказал, ЦКУ восстанавливает работоспособность ЛКУ.

4. Целевая аппаратура отказала, ЛКУ работоспособен и свободен, ЦКУ занят восстановлением работоспособности ЦА.

5. Целевая аппаратура и ЛКУ отказали, ЦКУ восстанавливает работоспособность ЦА, ЛКУ ожидает окончания восстановления ЦА.

Здесь через Яп г = 1, 2, обозначены интенсивности выхода из строя ЦА и ЛКУ соответственно, а через ( = 1, 2, 3 - интенсивности восста-

новдения ЦА средствами ЯКУ, ЦА - средствами ЦКУ, ЛКУ - средствами ЦКУ соответственно, ро - вероятность восстановления работоспособности ДА средствами ЛКУ (с вероятностью (1-ро), восстановление работоспособности ЦА происходит средствами ЦКУ). Значение показателей эффективности (коэффициентов готовности) той или иной подсистемы определяется через финальные вероятности, характеризующие величину доли времени пребывания системы в данном состоянии.

К третьему типу РСОИиУ можно отнести системы управления обеспечением социально-материальной безопасности, например систему управления охранно-пожарной безопасности объекта.

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

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

пожарной сигнализации

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

Описание состояний системы можно представить так:

1. Дежурный режим (нормальное состояние ожидания);

2. «Внимание» (сработали датчики, идет анализ ситуации);

3. «Тревога» (сигнал подтвердился);

4. «Защита» (идет отработка защитных мероприятий);

5. «Пожар» (сигнал о задымлении или появлении пламени подтвердился);

6. «Тушение» (идет отработка мероприятий по ликвидации очагов пожара);

7. «Тушение и Защита» (пока система находилась в состоянии «Тушения» или «Защиты» на объекте произошло проникновение или случился пожар).

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

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

В качестве выхода из данной ситуации предлагается система поддержки принятия решений при моделировании РСОИиУ в виде Марковских процессов.

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

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

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

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

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

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

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

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

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

В работе экспериментальным путем установлено превосходство второй гибридной схемы над первой в задачах выбора эффективных структур аппаратно-программных комплексов РСОИиУ.

В таблицах 1 и 2 для иллюстрации представлен фрагмент результатов тестирования обыкновенного и гибридного (согласно двум схемам) ГА на надежность и скорость, соответственно, для одной из задач, описанных в главе 1 (задача оптимизации без ограничений). Надежность — доля успешных запусков, скорость — номер поколения, на котором впервые было

найдено оптимальное решение, усредненный по успешным прогонам (т.е. чем меньше, тем лучше).

Таблица 1 - Надежность обыкновенного ГА и гибридных схем для целевого контура

Коэффициент готовности КА Коэффициент готовности ЦА Коэффициент готовности ЬКУ

Вид ГА Мин, Макс. Сред. Мии. Макс. Сред. Мнн. Макс.

Обыкновенный 0 1 0,28 0,03 1 0,32 0,98 1 0,99

Эволюция по Дарвину 0,01. 0,39 0,17 0,05 0,63 0,35 0,62 1 0,90

Эволюция по Ламарку 0,87 1 0,97 0,97 1 0,998 1 1 1

Из таблицы 1 видно, что надежность второго гибридного алгоритма очень высока и практически не зависит от настройки параметров ГА (минимальная надежность 87%, средняя 97%), т.е. специалисты предметной области могут использовать этот алгоритм без проблем с его настройкой.

Коэффициент готовности КА Коэффициент готовности ЦА Коэффициент готовности БКУ

Вид ГА Мин. Макс. Сред. Ми». Маке. Сред. Мин. Макс. Сред.

Обыкновенный - 25 18 7 22 16 4 11 7

Эволюция по Дарвину 7 32 20 11 22 16 4 12 9

Эволюция по Ламарку 4 10 6 3 9 5 2 3 2

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

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

Фрагмент тестирования гибридного ГА, имитирующего эволюцию по Ламарку, при выборе эффективного способа учета ограничения по надежность представлен в таблице 3.

Таблица 3 - Надежность гибридного ГА в условной задаче оптимизации

Коэс (фициенг готовности КА

Способ учета ограничений Мин. надежность Макс. . надежность Средняя надежность

Барьерная функция + «Лечение» 0,52 0,73 0,63

«Лечение» локальным поиском 0,56 0,78 0,67

Статическая штрафная функция 0,40 0,70 0,57

Адаптивная штрафная функция 0,63 0,79 0,70

Динамическая штрафная функция 0,58 0,85 0,71

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

В методе динамических штрафов пригодность решения (на ¿-ой итерации) определяется по следующей формуле:

шах ¡0,(х)} если

)j, еояи g +1 S m где (i ) S 0, - 0 - ограничения задачи

fitoessW = /(x) + //(*)

m^c-tr

рекомендованные значения С = 0.S, а = р-1 В методе адаптивных штрафов штрафные функции зависят не только от номера итерации, но и от количества попаданий лучшего представителя популяции на каждом шаге в допустимую или недопустимую области. Эта зависимость выглядит так:

, если Е^ е F для всех + Ht

Л

А<У), в противном случае

где * - лучший индивид ¡-й популяции, >1 и А * А (для избегания зацикливания).

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

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

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

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

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

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

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

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

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

.■-¿•/•■■у.-- . , .

."; ■ $ ^ '^у,-; Ойьв^пвНьйогтги^ра^гУ • ¡З.ЗЭ&ЮСбЗЭМ« К

Параборл ПОЙС*. объектнаиого сгстимцид ^На^сн-ый олгмм^ | £

■¡".¿л н-.=¡¿¿В. и ^^¡Г*-.^ я1; ¿-{-'1 V ¿¿¿Х.

рДа^руТьГД^ Има^^а'Урабогы.уограм^ьГл» ■ ЗаЬ.^ | ::

Рисунок 4. Программная система условной оптимизации с помощью гибридного ГА

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

¥г

ф:«Г',«.^.-^■ к-;ТГереичнЫе ианН^Говис^м^Х-?^

п врвичныв панны» о систему :

V "л 4 ~ ■• • *т.": IV'^: -1

я :(••' -т ¿о-и.-.

Рисунок 5. Стартовое окно программы автоматизации выбора структуры РСОИиУ

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

вании. Кроме того, программа прошла экспертизу и регистрацию на отраслевом и государственном уровне.

В заключении диссертации приведены основные результаты и выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

1. Построены модели функционирования РСОИиУ различных типов.

2. Разработаны формальные модели выбора эффективных вариантов аппаратно-программных комплексов РСОИиУ и исследованы их свойства.

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

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

5. Разработаны программные системы, позволяющие автоматизировать моделирование РСОиУ с помощью методов теории Марковских процессов и их оптимизацию по составу структуры аппаратно-программного комплекса.

6. Разработана, протестирована и апробирована на реальных задачах система автоматизации проектирования аппратно-программных комплексов РСОИиУ.

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

Таким образом, в данной работе на основе автоматизации стохастического моделирования и эволюционной оптимизации обосновал И реали-

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

Публикации по теме работы:

1*. Бежитский, С.С. Гибридный эволюционный алгоритм для задач выбора эффективных вариантов систем управления / С.С. Бежитский, Е.С. Семенкин, О.Э. Семенкина // Автоматизация и современные технологии. — № И.-2005.-С.24-31.

2*. Бежитский, С.С., Генетический алгоритм условной оптимизации в задаче выбора эффективной структуры системы управления космическим аппаратом / С.С. Бежитский, Е.С. Семенкин, О.Э. Семенкина // Вестник Красноярского государственного университета. Серия «Физико-математические науки», Ла 4. — 2005. — С. 228-233.

3*. Бежитский, С.С. О монотонности показателей эффективности технологического контура системы управления космическим аппаратом / С.С. Бежитский // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. — Вып. 5. - 2004. - С. 19-26.

4. Бежитский, С.С. Выбор оптимальной структуры аппаратно-программного комплекса системы управления движением автомобильного транспорта / С.С. Бежитский // Вестник университетского комплекса. -Вып. 6(20). — 2005. — С. 168-173.

5. Бежитский, С.С. Гибридный эволюционный алгоритм для решения сложных задач оптимизации / С.С. Бежитский Н Вестник университетского комплекса. - Вып. 1(15).-2004.-С. 166-173.

6. Бежитский, С.С. Разработка и исследование эволюционного алгоритма для оптимизации управления сложными системами / С.С. Бежитский, Е.С. Семенкин, О.Э. Семенкина // Вестник Кемеровского государственного университета. Журнал теоретических и прикладных исследований. Выпуск 1(17). - 2004. - С. 26-33.

7. Бежитский, С.С. Гибридный эволюционный алгоритм / С.С. Бежитский, О.Э. Семенкина // Компыотерпые учебные программы и инновации. -№10(11). - 2005. - С. 11.

8. Бежитский, С.С. Моделирование и оптимизация распределенных систем управления / С.С. Бежитский // Интеллектуальные системы (AIS'06). Тр. Межд. науч.-тех. конф. - М.: ФИЗМАТЛИТ, 2006. - Т.2. - С. 530-535.

9. Бежитский, С.С. Эволюционные алгоритмы для автоматизации проектирования распределенных систем управления / С.С. Бежитский, Е.С. Семенкин // X Национальная конференция по искусственному интеллекту

с международным участием. - М.: ФИЗМАЛИТ, 2006. - Т.З. - С. 10051013.

10. Бежитский, С.С. Модели и алгоритмы выбора эффективных структур распределенных систем обработки информации и управления / С.С. Бежитский, О.Э. Семенкина // Исследование, разработка и применение высоких технологий в промышленности: Сб. тр. Междунар. конф. Т. 4, - СПб.: Изд-во Политехи, ун-та, 2006. - С. 19-20.

11. Бежитский, С.С. Поддержка принятия решений при проектировании распределенных систем управления / С.С. Бежитский // Системный анализ в проектировании и управлении: Сб. тр. X Междунар. науч.-практ. конф. 4 3,- СПб.: Изд-во Политехи, ун-та, 2006. - С. 21-25.

12. Бежитский, С.С. Программная система поддержки принятия решений при проектировании интеллектуальных распределенных систем управления / С.С. Бежитский // Технологии Microsoft в теории и практике программирования: Сб. тр. Всерос. конф. — Новосибирск: НГУ, 2006. - С. 161-162.

13. Бежитский, С.С. Эффективность гибридного эволюционного алгоритма в задаче выбора варианта системы управления / С.С. Бежитский, О.Э. Семенкина // Интеллектуальные системы (AIS'05). Тр. Межд. науч.-тех. конф. - М.: ФИЗМАТЛИТ, 2005. - Т.1. - С. 22-24.

14. Бежитский С.С., Семенкин Е.С., Семенкина О.Э. Математическое обеспечение для формирования эффективных структур распределенных автоматизированных систем мониторинга чрезвычайных ситуаций / С.С. Бежитский, Е.С. Семенкин, О.Э. Семенкина // Современные методы математического моделирования природных и антропогенных катастроф. Тр. VUI Всероссийской конференции. - Кемерово: ИУУ СО РАН, 2005. - С. 276-284.

15. Бежитский С.С. Гибридный эволюционный алгоритм выбора эффективных вариантов систем управления. / С.С. Бежитский // Ломоносов 2005. Мат. Межд. конф. студ. и асп. - М: Изд-во факультета ВМиК МГУ, 2005. - С. 8-9.

16. Бежитский С.С., Семенкина О.Э. Гибридный эволюционный алгоритм. - М.: ВНТИЦ 2005. гос. per. 50200501803.

17. Бежитский С.С., Семенкин Е.С., Семенкина О.Э. Система поддержки принятия решений при моделировании сложных систем с использованием теории Марковских процессов. — М.: ВНТИЦ, 2006. — № гос. per. 50200601954.

18. Бежитский С.С., Семенкин Е.С. Система автоматизации проектирования распределенных систем обработки информации и управления. — М.: ВНТИЦ 2006.гос. per. 50200601953.

19. Бежитский, С.С. Система поддержки принятия решений на стадии предварительного проектирования распределенных систем управления / С.С. Бежитский // Молодежь и наука - третье тысячелетие: сб. тр. Всерос.

науч. конф. Часть I. - Красноярск: КРО НС «Интеграция», 2006. - С. 362366.

20. Бе жите кий, С.С. О классификации транспортных средств по их магнитному полю / С.С. Бежитский, Г.М, Грамлих // Молодежь Сибири -науке России. Сб. тр. науч.-практ. конф. Часть II. - Красноярск: СИБУП, 2005.-С. 371-372.

21. Бежитский С.С. О классификации транспортных средств но изменению магнитного поля // «Физика н Энштейн - 2005»: Сб. мат. межвуз. конф. молодых ученых. - Красноярск: КрасГУ, 2005.

22. Бежитский, С.С. О применении нейронной сети в задаче оптимизации генетическим алгоритмом структуры технологического контура космического аппарата / С.С. Бежитский // Актуальные проблемы авиации и космонавтики. Сб. тез. Бсерос. конф. молодых ученых. — Красноярск: СибГАУ, 2004.

23. Бежитский, С.С. Разработка и исследование гибридного эволюционного алгоритма для решения сложных задач оптимизации / С.С. Бежитский // Молодежь Сибири — науке России: Сб. мат. науч.-практ. конф. -Красноярск: СИБУП,2004.-С. 16-18.

24. Бежитский, С.С. О свойствах целевой функции в задаче выбора структуры технологического контура космического аппарата / С.С. Бежитский И Решетневскйе чтения: сб. тр. Всерос. науч.-практ, конф. — Красноярск: СибГАУ, 2003. - С. 266.

25. Бежитский, С.С. О трудоемкости алгоритмов локального поиска для задачи выбора структуры технологического контура космического аппарата / С.С. Бежитский // Информатика и информационные технологии. — Красноярск: ИПЦКГТУ,2003.-С. 17-19.

Бежитский Сергей Сергеевич Модели и алгоритмы выбора аппаратно-программного комплекса распределенных систем обработки информации и управления Автореферат

Подписано к печати 20.11.2006. Формат 60x84/16

Уч.изд, л. 1.0 Тираж ЮОэкз. Заказ №

Отпечатано в отделе копировальной и множительной техники СибГАУ. 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

Введение

Оглавление

Глава 1. Модели распределенных систем обработки информации и управления

1.1. Общая характеристика и выделение представительных классов 10 распределенных систем обработки информации и управления

1.2. Модель распределенной системы управления технологическим 13 контуром космического аппарата

1.3. Модель распределенной системы управления целевым контуром 16 космического аппарата

1.4. Модель распределенной системы управления 20 командно-программным контуром космического аппарата

1.5. Модель распределенной системы управления дорожным трафи- 25 ком

1.6. Модель распределенной системы управления охранно-пожарной 29 сигнализацией

Выводы

Глава 2. Алгоритмы выбора эффективных вариантов распределенных систем обработки информации и управления

2.1. Стандартный генетический и локальный алгоритмы выбора эф- 34 фективных вариантов распределенных систем

2.2. Гибридный и модифицированный гибридный генетический ал- 42 горитм

2.3. Результаты тестирования стандартного и модифицированного 49 гибридного алгоритма

2.4. Настройка нейронной сети на вычисление целевых функций

Выводы

Глава 3. Практическая реализация моделей и алгоритмов

3.1. Программная система безусловной оптимизации с помощью 70 стандартного ГА

3.2. Программная система безусловной оптимизации с помощью 75 гибридного и стандартного ГА

3.3. Программная система условной оптимизации с помощью гиб- 82 ридного и стандартного ГА

3.4. Программная система автоматизации моделирования сложных 89 систем с помощью Марковских процессов

3.5. Программная система автоматизации проектирования распреде- 93 ленных систем обработки информации и управления

3.6. Решение задачи моделирования и оптимизации распределенной 99 системы управления охранной сигнализацией

3.7. Модель распределенной системы управления охранной сигна- 108 * лизацией для двух и трех защищаемых объектов

Выводы

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

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

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

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

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

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

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

2. Формализация выбора эффективных вариантов таких систем в виде оптимизационных задач.

3. Выявление основных свойств оптимизационных задач, возникающих при выборе эффективных вариантов РСОИиУ.

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

5. Анализ свойств разработанных алгоритмов и исследование их эффективности при решении сформулированных задач.

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

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

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

Научная новизна работы заключается в следующем:

1. Построены новые формальные модели выбора структуры РСОИиУ различного назначения, отличающиеся глубиной детализации систем.

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

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

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

Работа выполнена в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития науки и техники на 2002-2006 годы» по теме 2006-РИ-16.0/001/076 (государственный контракт № 02.438. 11.7043) и 2006-РИ-19.0/001/377 (государственный контракт № 02.442.11. 7337), в рамках НИР 4422 «Разработка и исследование эффективности гиб* ридных методов оптимизации алгоритмически заданных функций дискретных переменных», выполняемой по ведомственной научной программе «Развитие научного потенциала высшей школы», а также по темплану СибГАУ «Бионические методы идентификации и оптимизации сложных систем» (№ Б 1.1.05).

Реализация результатов работы. Разработанные модели основных контуров управления космическими аппаратами, программная система моделирования сложных систем Марковскими процессами и гибридные генетические алгоритмы оптимизации переданы НПО прикладной механики (г. * Железногорск) в составе отчета по государственному контракту № 02.438. 11.7043.

Моделирование распределенной системы обработки информации и управления сетью автомобильных дорог выполнялась в рамках проекта «Саг Traffic Measurement and Control» Института автоматизации управления Специальной высшей школы (Fachhochschule Ulm, г. Ульм, Германия). Результаты исследования переданы немецкой стороне, о чем имеются подтверждающие документы.

Система автоматизации проектирования распределенных систем обработки информации и управления использовалась в качестве инструмента у поддержки принятия решения в ЗАО «А.Р.Т.», занимающегося проектированием, установкой и обслуживанием систем охранно-пожарной сигнализации на крупномасштабных объектах (Красноярский горно-химический комбинат, Красноярский комбайновый завод, Красноярская гидроэлектростанция и др.), что отражено в акте о передаче и использовании.

Три программные системы, разработанные в ходе выполнения работы, прошли отраслевую и государственную экспертизу и зарегистрированы в ОФАП и ВНТИЦ, что делает их доступными широкому кругу специалистов по моделированию и оптимизации сложных систем.

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

Основные положения, выносимые на защиту:

1. Система поддержки принятия решений при моделировании Марковскими процессами позволяет автоматизировать моделирование распре* деленных систем обработки информации и управления.

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

3. Модифицированный гибридный генетический алгоритм условной оптимизации позволяет успешно решать задачи выбора эффективных вариантов РСОИиУ.

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

ВАК. Тринадцать работ опубликованы без соавторов.

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

- Международные научно-технические конференции «Интеллектуальные системы и интеллектуальные САПР» (AIS'05, AIS'06, Дивно-морское, 2005,2006 гг.);

- X Национальная конференция по искусственному интеллекту с международным участием (КИИ'06, Обнинск, 2006 г.);

- Международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006 г.);

- Международная научно-практическая конференция «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2006 г.);

- Всероссийские научно-практические конференции "Решетневские чтения" (Красноярск, 2003, 2005 гг.);

- Международная научная конференция молодых ученых «Ломоносов-2005» (Москва, 2005);

- Всероссийская конференция-конкурс «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2006 г.), а также региональные и межвузовские конференции.

Структура работы. Работа состоит из введения, трех глав, заключения, списка литературы и приложения.

3.8. Выводы

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

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

Заключение

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

1. Построены модели функционирования РСОИиУ различных типов.

2. Разработаны формальные модели выбора эффективных вариантов аппаратно-программных комплексов РСОИиУ и исследованы их свойства.

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

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

5. Разработаны программные системы, позволяющие автоматизировать моделирование РСОиУ с помощью методов теории Марковских процессов и их оптимизацию по составу структуры аппаратно-программного комплекса.

6. Разработана, протестирована и апробирована на реальных задачах система автоматизации проектирования аппаратно-программных комплексов РСОИиУ.

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

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

1. Антомошкин А.Н. Семенкин Е.С. и др. Разработка модельного и алгоритмического обеспечения сквозного проектирования систем управления космическими аппаратами. Отчет по х/т 13И92 НПО ПМ. - Красноярск: Сибирский филиал Инженерной академии РФ, 1992.-282 с.

2. Архангельский А.Я. Программирование в С++ Builder 5. М.: БИНОМ, 2000.-с. 700.

3. Бабэ Б. Просто и ясно о Borland С++. М.: БИНОМ, 1994. - 400 с.

4. Баринов К.Н., Бурдаев М.Н., Мамон П.А. Динамика и принципы построения орбитальных систем космических аппаратов. М.: Машиностроение, 1975 - с. 270.

5. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.

6. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. URL: http://saisa.chat.ru/ga/summer 97.html

7. Бахвалов Н.С. Численные методы. М.: Наука, 1975 г.

8. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М.: Наука, 1987 г.

9. Бебенин Г.Г., Скрубушевский Б.С., Соколов Г.А. Системы управления полетом космических аппаратов. М.: Машиностроение, 1978. -с 272.

10. Ю.Белецкий Я. Энциклопедия языка Си. -М.: Мир, 1992.

11. П.Беляков Г.П. и др. Основы системотехники: Учеб. Пособие для вузов/ Г.П. Беляков, В.А. Сарычев, В.А. Сорокин, В.О. Чернышев. Под ред. В.О. Чернышева. Томск: МГП «РАСКО», 1992. 312 е.: ил.

12. Бьерн С. Язык программирования С++ Специальное издание. М.: БИНОМ, 2005. - с. 490

13. З.Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов Москва: Наука, 1981 г.

14. М.Буцынская Т.А., Родионов А.В. Функциональное моделирование систем охранно-пожарной сигнализации. // Материалы ХШ-ой научно-технической конференции "Системы безопасности" СБ-2004 -М: Академия ГПС - URL: http://ipb.mos.ru/konf/2004/sb-2004/sec 1 .html

15. Варфоломеев В.Н., Говорущенко Н.Я. Модели управления движением автомобилей. // Материалы IV-ой международной научно-технической конференции «Автомобильный транспорт: проблемы и перспективы» (4-8 сентября 2000 г.). Севастополь: СевГУ, 2000. -С. 4-8.

16. Венедякин Г.В. Общая методика эксперементального исследования и обработки опытных данных. -М.: Колос, 1972. -315с.

17. Вентцель Е.С., Овчаров J1.A. Теория случайных процессов и ее инженерные приложения. М.: Наука. Гл. ред. физ.-мат. лит. -1991. -384с.

18. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. Учебное пособие для студ. Втузов. 2-е из., стер. - М.: Высшая школа, 2001.-208 с.

19. Вентцель Е.С. Теория вероятностей. М.: Высшая школа, 2000.

20. Волков Е.А. Численные методы. М.: Наука, 1987 г.

21. Воловик М.А. Коэффициент готовности прибора со встроенной системой контроля // Системный анализ и исследование операций. -Новосибирск: ВЦ АН СССР, 1977.

22. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. X.: ОСНОВА, 1997.

23. Гмурман В.Е. Теория вероятностей и математическая статистика. -Учеб. пособие. М.: Высш. шк., 2000, 479 с.

24. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1987. - 336 с.

25. Горбань А.Н. Нейронные сети на персональном компьютере / Гор-бань А.Н., Россиев Д.А. Новосибирск: Наука, 1996. - 276 С.

26. Гринченко С.Н. Метод «проб и ошибок» и поисковая оптимизация: анализ, классификация, трактовка понятия «естественный отбор». Электронный журнал «Исследовано в России», 2003.

27. Гутер, Овчинский. Основы теории вероятностей. М.: Просвещение, 1967.-159с.

28. ЗО.Заенцев И.В. Нейронные сети: основные модели. Учеб. пособие к курсу «Нейронные сети», ВГУ, Воронеж, 1999.

29. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений: Энциклопедия программиста: Пер. с англ. / Р. Хэзфилд, J1. Кирби, Д. Корбит и др.- К.: Диасофт, 2001.- 736 с.

30. Исаев С.А. Популярно о генетических алгоритмах. URL: http://saisa.chat.rU/ga/ga-pop.html//top

31. Карлин С. Основы теории случайных процессов: Пер. с англ. М.: Мир, 1971.-536 с.

32. Карманов В.Г. Математическое программирование // БСЭ, т. 15. М.: Советская энциклопедия, 1974.

33. Катаев О.В. Лаборатория лабораторией распределенных систем НИИ МВС. URL:http://w\v\v.tsure.ru/University/nii/raspredelitel.htm

34. Кемени Дж., Снелл Дж. Конечные цепи Маркова: Пер. с англ. М.: Наука, 1970. -271.

35. Кокс Д., Смит В. Теория восстановления.: Пер. с англ. М.: Сов. Радио, 1967.-300 с.

36. Короткий С. Нейронные сети: основные положения. URL: http://\vww.neurok.ru

37. Крижанивский В.Б. Математические модели и методы оптимизации распределенных систем с дискретными источниками физических полей. URL: http://lib.profi.net.ua/\vebsites/ww\v.ziet.zhitoinir.ua/pri in.ziet.zt.ua/krizha n/seininar/resume/resume.htm.

38. Кульбак С. Теория информации и статистика. М.: Наука, 1967.

39. Кьоу Дж., Джеанини М. Объектно-ориентированное программирование: Учебный курс. Издательство: Питер, 2005-237 с.

40. Мейерс Г. Искусство тестирования программ / Пер. с англ. Под ред. Б.А. Позина.-М.: Финансы и статистика, 1982- 176 с.

41. Мельников А.В. Автоматизация проектирования распределенных систем обработки информации на основе развития теории формальных атрибутных грамматик: Дис. д-ра техн. наук: 05.13.12 Челябинск, 1995.

42. Мочалов В.П. Теоретические основы разработки и анализ вероятностно-временных характеристик распределенных систем управления телекоммуникационными сетями и услугами. М.: ФИЗМАТЛИТ. -2006.-365с.

43. Мочалов В.П. Модель распределенной системы обработки данных// Инфокоммуникационные технологии. 2004. -Т.2, №2.-с.31-34.

44. Мочалов В.П. Модель сети управления услугами TMN// Современные наукоемкие технологии: Тез. докл. межд. конф. 12-19 июня 2005г. -Тунис, 2005г.-№5.-с.71-72.

45. Мочалов В.П. Математическая модель организации взаимодействия компонентов распределенных систем// Современные наукоемкие технологии: Тез. докл. межд. конф. 20-27 ноября 2005г.-Канарские острова (о. Тенерифе), 2005г.-№10.-с.85.

46. Ope О. Теория графов.: Пер. с фр.-М: Наука, 1968.-352 с.52.0ре О. «Графы и их применение». Пер. с англ. под ред. И.М. Яглома. М., «Мир», 1965, 174 с.

47. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.Мир, 1979.

48. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2-е изд., доп. Томск, 1997.

49. Проектирование распределенных систем управления. URL: http://wvvw.kaskod.ru/ru/article/03prsycontr.php

50. Растригин J1.A. Случайный поиск. М.: Знание, 1979.

51. Растригин J1.A. Бинаризация задач оптимизации решений в САПР. -В кн.: Моделирование и оптимизация решений в САПР. Таллин, 1983,ч.2.

52. Резников Б.А. Методы и алгоритмы оптимизации на дискретных моделях сложных систем. JL: ВИКИ им. Можайского, 1983. - 250 с.

53. Рубан А.И. Методы анализа данных. Учеб. пособие: В 2 ч. Ч. 2; КГТУ. Красноярск, 1994, -125 с.

54. Саати T.JI. Элементы теории массового обслуживания и ее приложения. -М: Советское радио, 1971.

55. Самарский А.А., Гулин А.В. Численные методы: Учеб. пособие для вузов.—М.: Наука, 1989 г.

56. Саульев В.К. Математические теории массового обслуживания М.: Статистика, 1979. - 96 с.

57. Семенкин Е.С., Лебедев В.А. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами М.: МАКС Пресс, 2002 -320 с.

58. Семенкин Е.С., Семенкина О.Э., Терсков В.А. Методы оптимизации в управлении сложными системами // Учебное пособие. Красноярск: СибЮИ МВД РФ, 2000. - 254 с.

59. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем. Учебное пособие. Красноярск: СИБУП, 1996.

60. Семенкина О.Э., Жидков В.В. Оптимизация управления сложными системами методом обобщенного локального поиска. М.: МАКС Пресс, 2002.-215 с.

61. Симанков B.C., Частикова В.А. Генетические алгоритмы и поиск оптимальных решений // Автоматизация и современные технологии, 2003, № 6.

62. Советов Б. Я., Яковлев С.А. Моделирование систем. М.: Высшая школа, 1985. -326 с.

63. Томашевский В.Н., Печенежский Д.С. Моделирование дорожных знаков в имитационном проекте автомобильного дорожного движения. // Математическое моделирование, 2001, № 1(6).

64. Томашевский В.Н., Печенежский Д.С. Имитационный проект автомобильного дорожного движения. //Радиоэлектроника, автоматика, управление, 2001, № 1.

65. Турский В. Методология программирования. / Пер. с англ. Под ред. и с предисл. А.П.Ершова. М.: Мир, 1981. -264 с.

66. Турчак JI.И. Основы численных методов. / Под редакцией Щеннико-ва В.В. М.: Наука, 1987 г.

67. Тюрин Ю.Н., Макаров А.А. Статистический анализ данных на компьютере. М.: ИНФА - М, 1999. - 528 с.

68. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. М.: Мир, 1984.

69. Ушаков И.А. О вычислении среднего стационарного времени пребывания полумарковского процесса в подмножестве состояний // Извещение АН СССР. Техническая кибернетика. 1990. -№4.

70. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969.

71. Хаймен М. Borland С++ для «чайников». К.: «Диалектика», 1995. -416с.

72. Хант Э. Искусственный интеллект. М.: Мир, 1978. - 558с.

73. Харт-Дэвис Г. Microsoft Windows ХР Professional. Полное руководство. СП ЭКОМ, 2003 .-816с.

74. Хетагуров Я.А. Проектирование информационно-вычислительных комплексов: Учеб. Для вузов. М.: Высш. шк., 1987. - 280с.

75. Шамис В.А. С++ Builder 5. Техника визуального программирования. М.: «Нолидж», 1998.-512 с.

76. Шилдт Г. Теория и практика С++. СПб: BHV - Санкт-Петербург, 1996.-416.

77. Ярцев. Г. Перспективы компьютерного управления дорожным трафиком. По материалам «TweakTown», «ipKonfig», Microsoft Corp. и BMW Group. URL: http://www.atom.by/index.php?p=50&id=118

78. Яноши Л. Теория и практика обработки результатов измерений. -М.: Мир, 1968.-462 с.

79. Anderson D., McNeil G. Artificial neural networks techonology. A DACS State-of-the-Art Report. New York, 1992.

80. Antamoshkin A., Schwefel H.-P., Torn A., Yin G., Zilinskas A. System Analysis, Design and Optimization. An Introduction. Krasnoyarsk, 1993.-203 p.

81. Antamoshkin A., Semenkin E. Optimization of Unimodal Monotone Pseudoboolean Functions. Kibernetica 26. (1990) pp 432-442 pp.

82. Antamoshkin A., Semenkin E. Local Search Under Optimizing Unimodal Pseudoboolean Functions. Informatica 4. (1996) 18 pp.

83. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989.

84. Goodman E. et al (Eds). Evolutionary computation and its applications. Proceedings of the International Conference. Moscow: IHPCS of RAS, 1996.-350 pp.

85. De Jong K. An analysis of the behavior of a class of genetic Algorithms, Doctoral dissertation. University of Michigan, 1975.

86. Hebb D.O. The Organization of Behavior: A Neuropsychological Theory.—NewYork: Wiley, 1949.

87. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: The University of Mithigan Press, 1975.

88. Michalewizc Z. Genetic algorithms, numerical optimization, and constraints. Proceeding of the Sixth ICGA, 1995, pp.151-158

89. Parmee I. (Ed.) Adaptive computing in engineering design and control. Proceedings of the International Conference. Plymouth, 1996. - 325 pp.

90. Schwefel H.-P. Evolution and Optimum Seeking. N.Y.: Whiley Publ., 1995 - pp 612.

91. Semenkin E., Volovik M. Modelling and Optimization of Spacecrafts' Systems Design // Operations research'95. Berlin: Springer, 1995. - Pp. 353-358.

92. Semenkin E., Semenkina 0. Hybrid methods in the design of spacecraft' control systems. Adaptive computing in engineering design and control. Plymouth: University of Plymouth, 1996. Pp. 277-284.

93. Semenkin E. and Semenkina O. Local Search Algorithms in Pseudoboo-lean and Discrete Optimization Problems. // Operations Research'95. Abstracts of International Symposium. Passau: Passau University, 1995. P. 77.

94. Semenkina 0. Adaptive Search Algorithms for Solving Mixed Optimization Problems in CAD of Spacecraft Control Systems // Operations Research'97. Jena: TU-Jena, 1997.

95. Spears W. Evolutionary algorithms. The role of mutation and recombination. Springer, 2000.1. Список публикаций автора

96. Бежитский, С.С. Гибридный эволюционный алгоритм для задач выбора эффективных вариантов систем управления / С.С. Бежитский, Е.С. Семенкин, О.Э. Семенкина // Автоматизация и современные технологии. -№ 11.-2005.-С. 24-31.

97. Бежитский, С.С. Выбор оптимальной структуры аппаратно-программного комплекса системы управления движением автомобильного транспорта / С.С. Бежитский // Вестник университетского комплекса. -Вып. 6(20). 2005. - С. 168-173.

98. Бежитский, С.С. Гибридный эволюционный алгоритм для решения сложных задач оптимизации / С.С. Бежитский // Вестник университетского комплекса.-Вып. 1(15).-2004.-С. 166-173.

99. Бежитский, С.С. Гибридный эволюционный алгоритм / С.С. Бе-житский, О.Э. Семенкипа // Компьютерные учебные программы и иннова-ции.-№10(11).-2005.-С. 11.

100. Бежитский, С.С. Моделирование и оптимизация распределенных систем управления / С.С. Бежитский // Интеллектуальные системы (AIS'06). Тр. Межд. науч.-тех. конф. М.: ФИЗМАТЛИТ, 2006. - Т.2. - С. 530-535.

101. Бежитский, С.С. Эффективность гибридного эволюционного алгоритма в задаче выбора варианта системы управления / С.С. Бежитский, О.Э. Семенкина // Интеллектуальные системы (AIS'05). Тр. Межд. науч.-тех. конф. М.: ФИЗМАТЛИТ, 2005. - Т. 1. - С. 22-24.

102. Бежитский С.С. Гибридный эволюционный алгоритм выбора эффективных вариантов систем управления. / С.С. Бежитский // Ломоносов 2005. Мат. Межд. конф. студ. и асп. М: Изд-во факультета ВМиК МГУ, 2005.-С. 8-9.

103. Бежитский С.С., Семенкина О.Э. Гибридный эволюционный алгоритм. М.: ВНТИЦ, 2005. -№ гос. per. 50200501803.

104. Бежитский С.С., Семенкин Е.С., Семенкина О.Э. Система поддержки принятия решений при моделировании сложных систем с использованием теории Марковских процессов. М.: ВНТИЦ, 2006. - № гос. per. 50200601954.

105. Бежитский С.С., Семенкин Е.С. Система автоматизации проектирования распределенных систем обработки информации и управления. -М.: ВНТИЦ, 2006. -№ гос. per. 50200601953.

106. Бежитский, С.С. О классификации транспортных средств по их магнитному полю / С.С. Бежитский, Г.М. Грамлих // Молодежь Сибири -науке России. Сб. тр. науч.-практ. конф. Часть II. Красноярск: СИБУП, 2005.-С. 371-372.

107. Бежитский С.С. О классификации транспортных средств по изменению магнитного поля // «Физика и Энштейн 2005»: Сб. мат. межвуз. конф. молодых ученых. - Красноярск: КрасГУ, 2005.

108. Бежитский, С.С. Разработка и исследование гибридного эволюционного алгоритма для решения сложных задач оптимизации / С.С. Бежитский // Молодежь Сибири науке России: Сб. мат. науч.-практ. конф. -Красноярск: СИБУП, 2004. - С. 16-18.

109. Бежитский, С.С. О свойствах целевой функции в задаче выбора структуры технологического контура космического аппарата / С.С. Бежитский // Решетневские чтения: сб. тр. Всерос. науч.-практ. конф. Красноярск: СибГАУ, 2003. - С. 266.

110. Бежитский, С.С. О трудоемкости алгоритмов локального поиска для задачи выбора структуры технологического контура космического аппарата / С.С. Бежитский // Информатика и информационные технологии. -Красноярск: ИПЦ КГТУ, 2003. С. 17-19.

111. Результаты выполнения оптимизации с помощью ГА для каждой изцелевых функций