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

КАРЯКИН Юрий Евгеньевич

МОДЕЛИ И АЛГОРИТМЫ

СИСТЕМ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

НА ОСНОВЕ СИТУАЦИОННОГО ПОДХОДА

Специальность 05.13.18 – математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Тюмень – 2010

Работа выполнена на кафедре информационных систем Института математики и компьютерных наук ГОУ ВПО Тюменский государственный университет.

Научный руководитель: доктор технических наук, профессор ГЛУХИХ Игорь Николаевич

Официальные оппоненты: доктор физико-математических наук, профессор АКСЕНОВ Борис Гаврилович кандидат технических наук ХАРТЬЯН Денис Юрьевич

Ведущая организация: ГОУ ВПО Сургутский государственный университет ХМАО-Югра, г.Сургут

Защита диссертации состоится «_21_»_декабря_2010 г. в 1400 часов на заседании диссертационного совета Д 212.274.14 при Тюменском государственном университете по адресу: 625003, г. Тюмень, ул. Перекопская, 15А, ауд. 410.

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

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

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

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

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

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

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

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

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

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

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

Для достижения этой цели определены следующие задачи:

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

создание модели знаний о ситуациях и решениях на основе их формализованного представления;

разработка и исследование алгоритмов классификации и распознавания ситуаций;

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

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

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

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

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

На защиту выносятся:

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Результаты исследований использовались при выполнении госбюджетной НИР «Интеллектуальные системы обучения решению профессионально-ориентированных проблемных задач (в области управления организационно-техническими объектами)»

(№ госрегистрации НИР 01.20.02 14952), включены в курсы «Компьютерное моделирование», «Информационные системы» подготовки студентов специальностей «Прикладная информатика в экономике», «Прикладная информатика в географии», «Компьютерная безопасность» в Тюменском государственном университете.

Апробация работы. Основные результаты докладывались на VI международной научно-технической конференции (Пенза, 2007), III межрегиональной научно-практической конференции «Информационные технологии и телекоммуникации в экономике, управлении и социальной сфере» (Тюмень, 2008), межрегиональной научно-практической конференции «Теория и практика имитационного моделирования и создания тренажеров» (Пенза, 2002), III научнопрактической региональной конференции «Современные проблемы математического и информационного моделирования. Перспективы разработки и внедрения инновационных IT-решений» (Тюмень, 2010), межвузовской научнометодической конференции «Межсессионный контроль и качество обучения»

(Тюмень, 2001), областной научно-методической конференции «Роль информационных технологий в обучении: проблемы, перспективы, решения» (Тюмень, 2003), на научно-методических семинарах Института математики и компьютерных наук и кафедры информационных систем Тюменского государственного университета (2002-2010 г.г.).

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

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

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

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

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

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

Методы анализа многомерных данных, применяемые для исследования структуры и взаимосвязей характеристик функционирования сложных систем, рассматриваются в трудах Б.Г. Миркина, С.А. Айвазяна, Б.П. Ивченко, А.И. Орлова, Т. Саати и др. Системный аспект при обработке информации, циркулирующей в сложных системах, рассматривается в трудах Н.П. Бусленко., Б.Г. Литвак. А.А. Денисова, В.Н. Волковой, Ф.Ф. Пащенко, Б.П. Бусыгина.

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

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

Понятие модели представления знаний о ситуациях и их решениях формулируется как кортеж:

где Si — i-ая ситуация-пример; Ui — решение i-ой ситуации-примера;

I — информационная база правил выработки управляющих воздействий;

С — критерии оценки ситуаций и решений.

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

Формальный аппарат представления в СППР информации о ситуациях в сложных системах основан на использовании набора атрибутов (показателей) А1, А2, …, Аn, которыми описывается любая ситуация в системе. Информация о ситуациях в сложной системе представляется в виде строк с фиксированным расположением каждого атрибута Аi:

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

Формализованное представление множества всех ситуаций, характеризующих какую-либо предметную область, имеет следующий вид:

где Si(xi1,…,xin) – i-я ситуация; xij – оцифрованное значение j-го показателя для i-й ситуация (j=1,…,n); N – количество ситуаций; n – количество показателей.

Поведение сложной системы описывается движением представляющей ее точки в n-мерном пространстве.

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

1. Штатные (стандартные) K+;

2. Потенциально конфликтные K±;

3. Конфликтные (нестандартные) K-.

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

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

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

Для последующей структуризации показателей и учета их статистической взаимозависимости вводится матрица связи. Матрица связи – квадратная симметрическая матрица типа «показатель-показатель», где на пересечении i-ой строки j-ого столбца стоит мера «взаимосвязанности» i-го и j-го показателей.

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

где skj = В результате матрицей связи становится корреляционная матрица R=(rij).

Корреляционная матрица находится из соотношения где Ft=(tij) - информативная матрица, составленная из стандартизированных значений показателей (1).

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

Утверждение 1. Решением является последовательность пошаговых управляющих воздействий (один из основных постулатов ситуационного управления).

Утверждение 2. Элементарное управляющее воздействие – это изменение одного из управляющих параметров.

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

Элементарное управляющее воздействие определяется как отображение:

Si – текущая ситуация; uk(0, …, xk,..., 0) – вектор воздействия.

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

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

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

В предположении линейного характера зависимости между показателями xi и xj имеем зависимость xi = ax j + b +, где - случайная составляющая.

Получив оценки a и b, имеем уравнение регрессии:

rij – коэффициент корреляции; i, j – оценки средних квадратических отгде клонений значений i-го и j-го показателя соответственно; – оценка свободного коэффициента b.

При изменении значения объясняющего показателя имеем изменение объясняемого:

Из (4) и (5) получаем Пренебрежение случайной составляющей возможно тогда, когда в рассматриваемой системе математическое ожидание случайного возмущения равно 0. При этом дисперсия возмущений оценивается величиной где ei = y i y i - выборочная оценка возмущения; y i - групповая средняя.

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

Формула (6) характеризует изменение параметров исходной ситуации в результате изменения одного из параметров. Элементарное воздействие в матричном представлении будет иметь вид:

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

x – вектор изменения значений исходной ситуации; R – «скорректирогде ванная» корреляционная матрица; uупр – вектор управляющих воздействий Подобный подход к представлению решений обладает инвариантностью относительно перестановки элементарных управляющих воздействий, образующих решение. Данное свойство формулируется в виде доказанного в работе утверждения 4.

Утверждение 4. Результат суперпозиции элементарных управляющих воздействий не зависит от последовательности их реализации, т.е.

где Ui – элементарное управляющее воздействие по изменению i-го атрибута состояния системы; p – возможная перестановка.

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

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

Алгоритм кластеризации — это функция, которая каждой ситуации, содержащейся в ситуационной базе знаний, ставит в соответствие номер кластера.

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

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

где tij – стандартизированное значение i-го показателя j-го объекта кластера;

Ik – количество объектов в k-ом кластере.

Радиус кластера определяется как максимальное расстояние точек от центра кластера:

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

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

Алгоритм кластеризации заключается в следующем.

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

Начальное число кластеров k=3. Определенные ранее классы ситуаций будут являться начальными кластерами. В результате каждая ситуация назначена определенному кластеру.

2. Формирование новых кластеров.

Для каждого кластера находятся компоненты центра и радиус по формулам (8) и (9). Создание нового кластера (k = k + 1) производится, если имеет место пересечение кластеров, содержащих ситуации, относящиеся к разным классам, или имеются значительные расстояния между ситуациями.

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

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

3. Правило остановки.

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

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

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

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

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

Метод состоит в том, чтобы, выработав n независимых случайных величин (у1, …, уn), применить к ним линейное преобразование А:

Матрица А выбирается треугольной Элементы матрицы находятся из условия:

Для элементов корреляционной матрицы имеем:

Из (11) получаются коэффициенты матрицы А:

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

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

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

Приращение координат исходной ситуации представимо в виде где x (x1, …, xn) - текущая ситуации; x (x1, …, xn) – требуемая ситуация; B – матрица линейного преобразовании, переводящего вектор x в вектор x.

Из (7) и (13) получается выражение для нахождения управляющего воздействия при известном преобразовании исходной ситуации Алгоритм нахождения обратной матрицы (R')-1 реализуется численно.

Использование в (14) различных вариантов матрицы В позволяет получать множество альтернатив управляющих воздействий.

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

Функция F(B) является скалярной многопараметрической функцией, которая определяется как где x' = (x'1, x'2,..., x'n ), z = (z1, z2,..., zn ) - векторы, принадлежащие n.

Коэффициенты b11, b12,..., b21, b22,..., bn1,..., bnn матрицы B кодируются двоичными целочисленными строками, образуя хромосому (особь) h = (b11, b12,..., bnn ).

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

Используя целевую функцию F(B), строится функция пригодности генетического алгоритма Генетический алгоритм можно представить следующей последовательностью:

// Создание исходной популяции мощности М