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

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

Гениатулина Елена Владимировна

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

05.13.17 – Теоретические основы информатики

АВТОРЕФЕРЕРАТ

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

кандидата технических наук

Новосибирск – 2010

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

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

Гриф Михаил Геннадьевич

Официальные оппоненты: доктор технических наук, профессор,

Авдеенко Татьяна Владимировна

кандидат технических наук,

Гаврилов Константин Викторович

Ведущая организация: Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им.В.И.Ульянова (Ленина)»,

г. Санкт-Петербург

Защита состоится «20» января 2011 г. в 1400 часов на заседании диссертационного совета Д 212.173.06 при Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет» по адресу: 630092, Новосибирск, пр. К. Маркса 20

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

Автореферат разослан « » декабря 2010 г.

Ученый секретарь

диссертационного совета Чубич В.М.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

Научная новизна.

В диссертации разработаны алгоритмы генерации альтернатив и оптимизации ПФ ЧМС, а именно:

• алгоритм генерации последовательно-параллельного процесса функционирования ЧМС, опирается на объектно-ориентированную модель описания и единую базу знаний ПФ ЧМС с учетом дополнительных ограничений и не требует, в отличие от моделей М.Г. Грифа и Е.Б. Цоя, явного задания альтернатив в виде функциональной сети;

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

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

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

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

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

Разработанные методы и алгоритмы реализованы в рамках новой версии программы ГЭС ИНТЕЛЛЕКТ-3 (Свидетельство о государственной регистрации программы для ЭВМ №2010616283 – М.:Роспатент, 2010).

Разработанные методы нашли практическое применение в работе отдела поддержки продаж ООО фирмы «ГОТТИ», а также в ООО «Трейдсервис». Кроме того, ГЭС ИНТЕЛЛЕКТ-3 используется в учебном процессе в Новосибирском государственном техническом университете на факультете автоматики и вычислительной техники и в Институте Социальной Реабилитации НГТУ.

Результаты научных исследований использованы при выполнении проекта № 3.1.1/1703 в рамках АВЦП «Развитие научного потенциала высшей школы (2009-2010 годы)».

Достоверность научных положений и результатов.

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

Личный вклад. Все изложенные в диссертации алгоритмы и методики были разработаны, реализованы и экспериментально проверены автором лично. Программная реализация ГЭС ИНТЕЛЛЕКТ-3 проводилась коллективом исследователей при непосредственном участии автора. Автором модифицированы, дополнены и доведены до программной реализации методы задания альтернатив, построения процесса функционирования, а также решения задачи с учетом обязательных сочетаний операций.

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

• научно-практической конференции «Технологическое образование и устойчивое развитие региона» (Новосибирск, 2006);

• научной студенческой конференции «Дни науки НГТУ» (Новосибирск, 2006);

• международной научно-методической конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2008, 2009, 2010);

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

• всероссийской научно-практической конференции «Системы автоматизации в образовании, науке и производстве» (Новокузнецк, 2009);

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

• международном форуме по стратегическим технологиям «IFOST-2010» (Ulsan, Korea, 2010).

Публикации. Всего по теме диссертации опубликованы 16 научных работ, в том числе: 1 статья ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК РФ; 8 статей в материалах международных, всероссийских конференций, 1 статья в научном журнале, 5 статей в научных сборниках; 1 работа зарегистрирована в Роспатент.

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, списка используемых источников и приложения. Объем работы составляет 145 страниц основного текста, включая 69 рисунков и 7 таблиц. Список использованных источников содержит 75 наименований.

Краткое содержание работы

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

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

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

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

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

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

Задача оптимизации (обобщенная задача динамического программирования) ставится следующим образом:

(1)

где – критерий оптимальности для сочетаний критериев ЭКН; – множество допустимых альтернатив, альтернативные варианты процесса – .

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

Рис. 1. Альтернативный граф для процесса функционирования ЧМС

Таблица 1

Скалярные и векторные задачи оптимизации с показателями B(A),T(A),V(A)

Здесь – ограничения на совместимость способов выполнения компонентов альтернатив в виде предиката – “Если есть “Истина”, то удовлетворяет ограничениям задачи”.

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

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

Отдельный процесс функционирования ЧМС (функциональная сеть) представляется в виде суперпозиции ТФС:

, (2)

где , – простая или составная операция.

Две операции с совпадающей функцией –и являются альтернативными ("параметрическими") способами выполнения операции , так же как и составные операции и ,- «структурными».

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

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

Частичным решением для задачи (1) с множеством альтернатив называется исходный или укрупненный алгоритмом параметрический способ выполнения произвольной операции . Частичное решение доминирует частичное решение по вероятностным критериям (показателям) и (), если оба решения являются параметрическими способами выполнения некоторой ТФЕ типа РО и и и .