МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

УДК 519.857:681.3.06:007.5

Тудэвдагва Уранчимэг

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

ЧЕЛОВЕКО-МАШИННЫХ СИСТЕМ НА ОСНОВЕ

МЕТОДА ПОСЛЕДОВАТЕЛЬНОЙ ОПТИМИЗАЦИИ

Специальность 05.13.17 Теоретические основы информатики Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель доктор технических наук, доцент Г.М. Гриф Новосибирск -

ОГЛАВЛЕНИЕ

Перечень сокращений Введение Глава I. Постановка и обоснование задач исследования §1.1. Сравнительный анализ моделей процессов функционирования при проектировании ЧМС § 1.2. Основы функционально-структурной теории ЧМС § 1.2.1. Формализация данных на основе обобщенного структурного метода § 1.2.2. Вероятностно-алгоритмический и нечетко-алгоритмический подходы к оценке показателей функционирования §1.3. Задачи оптимизации на базе вероятностных и нечетких показателей эффективности, качества и надежности §1.4. Способы формирования множества альтернатив §1.4.1. Формализованное описание вариантов выполнения процесса функционирования ЧМС §1.4.2. Структурные и объектно-ориентированные стратегии построения альтернативного графа §1.5. Метод последовательной оптимизации ЧМС §1.5.1. Свойства вероятностных и нечетких показателей функционирования ЧМС §1.5.2. Метод направленного перебора §1.6. Выводы и заключение по первой главе Глава 2. Модели и алгоритмы последовательной оптимизации §2.1. Способ задания условных назначений элементов ЧМС на выполняемые функции §2.2. Алгоритмы последовательной оптимизации с проверкой необходимых условий допустимости частичных решений §2.3. Алгоритмы приближенного решения §2.4. Результаты второй главы Глава 3. Программное обеспечение оптимального проектирования ЧМС и примеры решенных задач §3.1. Программные средства поддержки проектирования ЧМС §3.1.1. Общее описание гибридной экспертной системы проектирования ЧМС ИНТЕЛЛЕКТ- §3.1.2. Подсистемы определения множества альтернатив и решения задач оптимизации §3.2. Проектирование компьютерной сети института Энергетики Монгольского государственного университета науки и технологий § 3.2.1. Общая характеристика сети института Энергетики § 3.2.2. Выбор способа обслуживания и ликвидации отказов компьютеров в терминальных классах §3.3. Результаты третьей главы Заключение Список литературы Приложение 1. Численные исследования алгоритмов оптимизации П.1.1. Численные исследования приближенных алгоритмов П.1.2. Численные исследования алгоритмов точного решения

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ

АСУ - автоматизированная система управления АСУТП - АСУ технологическим процессом АНП - алгоритм направленного перебора АГ - альтернативный граф ВГ - вероятностный граф ГЭС - гибридная экспертная система ДК - диагностический контроль МЛВ - механизм логического вывода НУД - необходимые условия допустимости НУО - необходимые условия оптимальности НВГ - нечеткий вероятностный граф ОСМ - обобщенный структурный метод ООП - объектно-ориентированное проектирование ООФС - объектно-ориентированная ФС ПФ - процесс функционирования ПМП - полумарковский процесс РО - рабочая операция САПР - система автоматизированного проектирования ТФЕ - типовая функциональная единица ТФС - типовая функциональная структура ФС - функциональная сеть ФСС - функционально-семантическая сеть ФСТ - функционально-структурная теория ФК - функциональный контроль ЧМС - человеко-машинная система ЭКН - эффективность, качество, надежность ЭС - экспертная система ЭВМ - электронная вычислительная машина

ВВЕДЕНИЕ

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

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

Следовательно, центральным вопросом рассматриваемой проблемы является разработка методов и алгоритмов оптимизации ПФ ЧМС, позволяющих организовать разрабатываемых систем.

Несмотря на имеющийся широкий арсенал моделей описания и количественной оценки процессов функционирования ЧМС, разработанных отечественными и зарубежными научными школами (марковские и полумарковские процессы, модели теории массового обслуживания, формальные грамматики, сети Петри, логические автоматы и схемы алгоритмов Ляпунова, логико-лингвистические модели, сети GERT, PERT, функциональные и функционально-семантические сети, вероятностноалгоритмические и нечетко-алгоритмические модели), ни одна из них не свободна от того или иного недостатка и не может быть положена в основу современной системы автоматизации проектирования ПФ ЧМС. Анализ указанных моделей показывает, что наиболее универсальными из них являются функционально-структурная теория и обобщенный структурный метод проф. Губинского А.И. (1977), получившие творческое развитие в работах В.Г.Евграфова, А.П.Ротштейна, П.И.Падерно, А.Н.Адаменко, П.П.Чабаненко, А.Т.Ашерова, Е.А.Лаврова, Е.А.Павлова и др.

Следует отметить также хорошо зарекомендовавшие себя на практике методы формализации данных в дискретном процессе функционирования ЧМС, например, операционно-психологический (Зараковский, 1966), структурно-алгоритмический (Суходольский, 1976), логико-комбинаторный (Анкудинов, 1986). В работах М.Г.Грифа, Е.Б.Цоя и других получили развитие модели, методы и технологии последовательной оптимизации процессов функционирования ЧМС по показателям эффективности, качества и надежности на основе ФСТ. Рассматривался достаточно широкий спектр ЧМС: АСУП, АСУТП, САПР, АСНИ, системы автоматизации эргономических исследований, принятия решений. Однако не все аспекты метода последовательной оптимизации исследованы одинаково глубоко: отсутствует возможность гибкого задания назначений элементов ЧМС на выполняемые функции, включаемых в МА при изменении внешних и внутренних условий в процессе функционирования ЧМС (базе знаний); отсутствуют эффективные алгоритмы последовательной оптимизации с проверкой необходимых условий допустимости частичных решений; недостаточно исследованы алгоритмы приближенного решения в рамках метода последовательной оптимизации на основе различных стратегий сжатия частичных решений.

Актуальность темы диссертации подтверждается тем, что она выполнялась в рамках гранта Г02-4.1-34 Минобразования РФ “Разработка методов моделирования и оптимизации сложных систем по вероятностным и нечетким показателям” (2003), а также являлась частью исследований в ходе проведения в НГТУ прикладной НИР по тематическому плану министерства образования РФ "Исследование теоретических основ и разработка систем организации и управления реабилитационнообразовательным процессом в условиях государственного учреждения для инвалидов" (2002-2003).

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

Предметом исследования служат процессы исследования и проектирования ПФ ЧМС на основе вероятностных и нечетких показателей эффективности, качества и надежности.

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

Основными задачами

являются:

- разработка способа задания условных назначений элементов ЧМС на выполняемые функции, включаемые в МА при соответствующем состоянии базы знаний ПФ ЧМС;

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

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

- разработка алгоритмического и программного обеспечения и его применение для решения конкретных прикладных задач исследования и проектирования процессов функционирования ЧМС.

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

Научная новизна. В диссертации существенно расширены возможности модели проектирования и метода последовательной оптимизации процессов функционирования ЧМС по вероятностным и нечетким показателям эффективности, качества и надежности, а именно:

1. Оптимизационная модель процесса функционирования ЧМС, которая впервые в функционально-структурной теории ЧМС использует условные назначения элементов ЧМС на выполняемые функции, включаемые в МА при соответствующем состоянии базы знаний ПФ ЧМС.

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

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

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

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

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

- сократить в среднем на 10% время решения задачи в результате использования необходимых условий допустимости частичных решений в алгоритмах точного перебора;

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

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

Реализация результатов исследования. Теоретические результаты работы доведены до удобных для практического применения формул, алгоритмов, методик, применены для разработки прикладного математического обеспечения, которое использовано при проектировании компьютерной сети института Энергетики Монгольского государственного университета науки и технологий (Улан-Батор, 2003), а также вошло составной частью в гибридную экспертную систему проектирования ПФ ЧМС ИНТЕЛЛЕКТ-2 (Новосибирск, 2003).

Ряд разработанных в диссертации результатов используется в учебном процессе НГТУ в дисциплинах,,Базы знаний и экспертные системы”, “Современные средства проектирования АСОИУ” (специальность “Автоматизированные системы обработки информации и управления”).

Апробация работы. Основные положения диссертационной работы, разработанные модели, методы, алгоритмы и программы были представлены и обсуждались в 2003 г. на трех международных конференциях, в том числе на Международной научно-методической конференции "Качество образования.

Системы управления, достижения, проблемы" (Новосибирск, 2003), VII РоссийскоКорейском международном симпозиуме KORUS '2003 (Корея, Ulsan, 2003), :

Международной научно-технической “Информационные системы и технологии” (Новосибирск, 2003), научных семинарах кафедры “Автоматизированные системы управления” (Новосибирск, 2002, 2003) и получили положительную оценку.

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

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

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

Автор выражает глубокую благодарность и признательность профессору Евгению Борисовичу Цою за постоянные консультации и методическую поддержку.