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

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

ЛИСТОПАД СЕРГЕЙ ВИКТОРОВИЧ

ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА МОДЕЛИРОВАНИЯ

КОЛЛЕКТИВНОГО ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ

Специальность: 05.13.17-«Теоретические основы информатики»

АВТОРЕФЕРАТ ДИССЕРТАЦИИ на соискание ученой степени кандидата технических наук

1 (лДР Ш

005015122

Москва 2012

005015122

Работа выполнена в Калининградском филиале Федерального государственного бюджетного учреждения науки Института проблем информатики Российской академии наук

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

профессор Колесников Александр Васильевич

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

Ярушкина Надежда Глебовна, доктор технических наук, профессор, ФГБОУ ВПО Ульяновский государственный технический университет, заведующая кафедрой "Информационные системы"

Тарасов Валерий Борисович, кандидат технических наук, доцент, ФГБОУ ВПО Московский государственный технический университет им. Н.Э. Баумана, доцент кафедры компьютерных систем автоматизации производства

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

Федеральное государственное бюджетное учреждение науки Межведомственный суперкомпьютерный центр Российской академии наук

Защита диссертации состоится лу?^ 2012 г. в /часов мин на заседании диссертационного совета Д002.073.01 при Федеральном государственном бюджетном учреждении науки Институте проблем информатики Российской академии наук по адресу: 119333, Москва, ул. Вавилова, 44, корп. 2.

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

Автореферат разослан «¿^»^£¿£¡/¡¿$2012 г. Ученый секретарь

диссертационного совета Д002.073.01 доктор технических наук, профессор

іинченко Сергей Николаевич

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

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

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

Теоретические основы комбинированных моделей для машинного синтеза новых динамично изменяемых методов решения задач рассматривались в работах В.И. Городецкого, М.С. Грушинского, H.A. Земцова, В.Д. Ильина, JI.A. Калиниченко, К.А. Неусыпина, С.А. Ступникова, В.Б. Тарасова (много-агентные системы), A.B. Гаврилова, A.B. Колесникова, Н.Г. Ярушкиной (гибридные интеллектуальные системы), А.Н. Борисова, Г.В. Рыбиной, И.Б. Фоминых, А.И. Эрлих (интегрированные экспертные системы) и др. Наиболее цитируемые зарубежные авторы в этой области - H.-D. Burkhard, Y. Demazeau,

B. Fley, M. Florian, M.-P. Gleizes, F. Hillebrandt, D. Hinck, N.R. Jennings, A. Karageorgos, A.C. Rocha Costa, M. Schillo, G.D.M. Serugendo, M. Wooldridge,

C. Zhang, Z. Zhang.

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

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

Выполнение работы связано с плановыми исследованиями Калининградского филиала ИПИ РАН, проводимыми в рамках Программы фундаментальных научных исследований государственных академий наук на 2008 - 2012 годы, утвержденной распоряжением Правительства Российской Федерации от 27.02.2008 г. № 233-р (направления 27,28).

Цель диссертационной работы состоит в том, чтобы для решения поставленной научно-технической задачи: 1) получить новые знания о сложности моделирования задач; 2) разработать и исследовать метод, модели, алгоритмы интегрированного, гибридно-многоагентного представления знаний о сложной задаче; 3) создать и исследовать программный продукт (ПП), имитирующий поведение коллектива людей, вырабатывающих и применяющих метод решения сложной задачи над различными линиями рассуждений экспертов.

Задачи исследования:

1. Выявление объективных параметров классификации задач по признаку сложности моделирования и разработка меры сложности моделирования задач;

2. Исследование явлений и процессов самоорганизации в СППР;

3. Разработка метода моделирования процессов самоорганизации в системах поддержки принятия решений с использованием гибридных интеллектуальных многоагентных систем (ГиИМАС);

4. Извлечение знаний о поведении ЛПР по управлению коллективом в СППР с использованием компьютерного моделирования;

5. Разработка и исследование программной реализации ГиИМАС с самоорганизацией и методики для решения сложной транспортно-логистической задачи (СТЛЗ).

Данные задачи были решены в ходе работы.

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

Содержание диссертационного исследования соответствует специальности 05.13.17 «Теоретические основы информатики» (пункты 1, 2, 4, 8 паспорта специальности ВАК)

Методическая база исследований. Для разработки меры сложности задач использовались: дискретная математика, теория множеств, теория графов, модели «неоднородная задача» и «однородная задача», информационный язык «ресурс-свойство-действие-отношение» A.B. Колесникова. Для разработки метода моделирования процессов самоорганизации в СППР с использованием ГиИМАС применялись теория нечетких множеств, методы нечеткой логики. При разработке ПП «Транспортный маршрутизатор ТРАНСМАР» использовались алгебраические уравнения, алгоритм колонии муравьев, продукционная экспертная система с рассуждениями в прямом направлении, алгоритм нечетких рассуждений Мамдани и метод Монте-Карло. Применялось объектно-ориентированное, агентно-ориентированное, модульное программирование. Методика основана на проблемно-структурной методологии гибридных интеллектуальных систем (ГиИС).

Научная новизна состоит в том, что:

1. Предложена классификация задач по сложности моделирования и разработана мера сложности моделирования задач;

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

3. Разработан метод моделирования самоорганизации в СППР с использованием гибридной интеллектуальной многоагентной системы;

4. Получены новые знания о поведении лица, принимающего решения, по управлению коллективом СППР методом компьютерного моделирования;

5. Разработана программная реализация гибридной интеллектуальной многоагентной системы с самоорганизацией для решения сложной транспорт-но-логистической задачи - ПП «Транспортный маршрутизатор ТРАНСМАР» версии 1.1 - и методика его применения.

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

и экспериментальными данными, полученными при внедрении ГиИМАС. Определения, классификация задач, мера сложности моделирования апробированы на конференциях и в научных публикациях.

Практическая ценность диссертационной работы состоит в том, что разработанный программный продукт «Транспортный маршрутизатор ТРАНСМАР» версии 1.1 может использоваться при создании компьютерных интеллектуальных систем поддержки принятия решений, что снижает временные затраты на проект у разработчика и повышает эффективность системы управления, сокращая потери от ошибочных и нерелевантных решений.

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

Реализация результатов исследования. Метод моделирования самоорганизации в СППР с использованием ГиИМАС реализован, что подтверждается свидетельствами о регистрации трех программ для ЭВМ. Мера оценки сложности моделирования и ПП ТРАНСМАР использовались: 1) в лабораторных экспериментах с целью моделирования самоорганизации в СППР и оценки качества коллективных решений в сравнении с индивидуальными; 2) при разработке компьютерных систем поддержки принятия решений (КСППР) для транспорт-но-логистических предприятий ЗАО «Совтрансавто-Калининград» и ООО «Балтреммаш», выполняющих международные и региональные перевозки. Использование подтверждается двумя актами о внедрении результатов диссертационной работы.

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

Положения, выносимые на защиту. На защиту выносятся следующие полученные автором результаты:

1. Мера оценки сложности моделирования, основанная на объективных параметрах разнообразия и неоднородности информации: «класс переменных» и «класс отношений», позволяющая вычислить границу сложных задач, определить требования к структурным свойствам КСППР, количественно оценить релевантность моделей оригиналам;

2. Модель ГиИМАС с самоорганизацией, релевантно отображающая в памяти ЭВМ как разнообразие знаний агентов-экспертов, так и их информационные взаимодействия между собой и агентом-ЛПР в ходе анализа, редукции и поиска решения сложной задачи;

3. Метод моделирования самоорганизации СППР на основе анализа целей агентов для синтеза релевантного ситуации принятия решений инструмента;

4. Модель информационной структуры, реализующей в ЭВМ интегрированное представление знаний, - ГиИМАС - и процесс ее функционирования, отображающий самоорганизацию в СППР;

5. Методика применения ГиИМАС для решения CTJI3 с целью прокладки маршрутов транспортных средств, выполняющих доставку грузов клиентам логистической компании.

Апробация работы. Основные положения диссертационной работы обсуждались на Международной научной конференции «Образование, наука и инженерная деятельность в социокультурном пространстве эксклавного региона: история, актуальные проблемы, перспективы развития» (Калининград, 2007), Международной научной конференции Computer Days - 2009 (Каунас, Литва, 2009); 7-й Международной конференции «Инновации в науке и образовании» (Калининград, 2009), Международных научных конференциях IT 2010 и IT 2011 (Каунас, Литва, 2010, 2011), III - V Всероссийских конференциях студентов, аспирантов и молодых учёных «Искусственный интеллект: философия, методология, инновации» (Москва, 2009, 2010, 2011), IX Международной конференции, посвященной 45-летию Балтийской государственной академии рыбопромыслового флота «Морская индустрия, транспорт и логистика в странах региона Балтийского моря: новые вызовы и ответы» и др. Работа отмечена премией в рамках Второй школы молодых ученых ИЛИ РАН в 2011 г.

Публикации. По тематике диссертационной работы имеется 18 печатных публикаций общим объемом 17,6 печатных листа, из них 7,1 авторских (в изданиях, рекомендованных ВАК, - 2 публикации общим объемом 1,5 печатных листа, из них 1,1 авторских), в том числе одна коллективная монография и три свидетельства о регистрации программ для ЭВМ в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатент).

Объем и структура работы. Диссертация состоит из введения, пяти глав, 17 таблиц, 35 рисунков, заключения, списка литературы, содержащего 170 наименований, и двух приложений. Объем основного текста работы - 145 страниц.

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

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

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

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

Проведен анализ определений сложности Э.С. Вира, С.П. Капицы, E.H. Князевой, С.П. Курдюмова, Г.Г. Малинецкого, Г. Николиса, И.Р. Приго-жина, Г. Хакена и др. Рассмотрены подходы к определению сложности задачи В.М. Глушкова, Дж.Д. Додсона, P.M. Йеркса, П. Норвига, С. Рассела и др. Их анализ показал, что понятие сложности многоаспектно, причем сложности моделирования (разработке модели) уделяется мало внимания. Сделан вывод об актуальности создания ее количественной меры для классификации задач и оценки успешности выполнения проекта ограниченными ресурсами.

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

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

В отличие от «задачи коммивояжера» в СТЛЗ снимаются ограничения на количество объектов, расширяется список классов отношений между объекта-

ми и их свойствами. Моделируются «человеческий фактор», стохастические события, расширяется количество моделируемых классов переменных.

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

На информационном языке «ресурс - свойство - действие - отношение» вводится концептуальная модель СППР:

dis = Rr" "\prtäm,env) о R"s r"(PRT,PRT), (1)

где dss - модель взаимодействия участников СППР на структурно-информационном микроуровне; prtJm — модель знаний ЛПР; env s RES - внешняя среда; PRT = {prt^...,prtn,prté"}, PRTç RES - множество участников СППР, включающее ЛПР prt'1'" ; Rr" - множество отношений «ресурс - ресурс» между участниками СППР, а также ЛПР и внешней средой.

Графически концептуальная модель (1) взаимодействия участников СППР на структурно-информационном микроуровне представлена на рис. 1.

Рис. 1. Концептуальная модель СППР на микроуровне

Каждый ее участник преследует собственные цели, совпадающие или противоречащие целям других участников. За счет локальных взаимодействий Л""" экспертов в СППР возникают макроуровневые, внешне проявляющиеся явления и процессы. В результате построения и исследования их концептуальных моделей сделан вывод, что в основе явлений адаптации ас1, гомеостаза ко, самообучения д/ и синергетического эффекта яе лежит самоорганизация до -способность СППР реагировать на изменения во внешней среде, адаптироваться к ней, корректируя свое поведение и устройство. Благодаря самоорганизации каждый раз при решении сложной задачи СППР вырабатывает новый метод решения, релевантный ее условиям, что повышает качество работы, проявляясь в синергетическом эффекте от взаимодействия экспертов.

Идеи самоорганизации восходят к A.A. Богданову, JI. Берталанфи, Ф.Х. Вареле, У.Р. Матуране, H.H. Моисееву, Г. Николису, И.Р. Пригожину, И. Стенгерсу, Г. Хакену, Э. Шредингеру, У.Р. Эшби и др.

В работе самоорганизация в СППР - перестроение ЛПР взаимодействий между экспертами на основе анализа степени их согласованности (близости целей). Вводятся три типа отношений: конкуренция - достижение цели одним участником исключает достижение цели другим; сотрудничество - цели участников совпадают; нейтралитет — цели не совпадают и не противоречат. В зависимости от наличия в СППР тех или иных типов отношений различаются три ситуации: 1) сотрудничества - СППР состоит только из сотрудничающих и нейтральных участников; 2) нейтралитета - в СППР есть только нейтральные отношения; 3) конкуренции - в СППР есть хотя бы одна пара экспертов с отношением конкуренции. По результатам анализа условий задачи ЛПР стремится установить одну из перечисленных ситуаций коллективного решения.

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

Таблица 1. Аналитический обзор концепций искусственного интеллекта для моделирования систем поддержки принятия решений

Концепция ИИ Основополагающие работы Моделируемые объекты и аспекты СППР

эксперт среда правила взаимодействия микро-уровневые модели макро-уровневые эффекты

Гибридные системы Дж. Антсаклис, Р. Брокетт, А. Бэк, X. Витценхаузен, У. Кон, М.Д. Леммон, М.А. Майерс, А. Нерод, Дж. Стивер, Л. Травернини - + - - -

Интегрированные экспертные системы А.Н. Борисов, Г.В. Рыбина, И.Б. Фоминых, А.И. Эрлих + + - - +

Гибридные интеллектуальные системы И. А. Кириков, A.B. Колесников, Н.Г..Ярушкина, Н. Касабов, Р. Козма, С.Кхеббал, Л. Медскер + + - + +

Многоагентные системы Т. А. Гавр ил ов а, В.И. Городецкий, М.С. Грушинский, В.Б. Тарасов, A.B. Хабалов, В.Ф. Хорошевский, Г. Вейсс, М. Вулдридж + + + + +

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

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

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

Мера сложности моделирования задачи позволяет рассчитывать границу между сложными и простыми задачами, количественно сравнить сложность моделирования задач, а также предъявлять требования к структурным свойствам системы, способной ее решать, оценивать релевантность задаче тех или иных КСППР. При этом разнообразие и неоднородность информации о задаче оценивается по двум объективным параметрам: «класс переменной» и «класс отношения». Составлены ограниченные перечни классов переменных, используемых в МФПС: детерминированные с1е; стохастические st^, логические (пропозициональные) /о; лингвистические нечеткие /к и лингвистические четкие (символьные) //. Так как переменные используются в информационном языке «ресурс - свойство - действие - отношение» для описания концептов «свойство» - РИ, определим подмножества свойств, описываемых разными классами переменных: Рк = У/>/<!', РЯ' пРЯ' =0, /,у е{с1е,$1,1о,/и,И}, ¡-Ау, а во мно-

I

жестве отношений «свойство - свойство» к'"рг выделим подмножества отношений, связывающие свойства из различных классов: К'"'"' рг/,

¡,]£.{с1е,з1,1о,/и,и}. Класс отношения определяется по классам связываемых переменных. Отношения 11'"'рг1, /е {¿е, ¡¡,10,/и,И} между переменными одного класса назовем однородными, иначе если К',г1 рп, ¡'.у' е {с1е,х(,1о,/и,И}, г* у, то они считаются разнородными.

Предлагаемая мера сложности включает два параметра: 1) количество х=\УТ'\ классов переменных в концептуальной модели задачи, где УТ' = {РЯ' \1'е{с1е,51,1о,/и,И}}; 2) количество у =| КТ'"' | классов разнородных отношений между ними, где кТ'"' = {Нрг' рг-) | /,у е {¿е, я!, 1а,/и,И},/ Ф у'}. Множества их значений обозначим X = [х\х = \УТ'\} и

¥ = {у\у = \ЯТ*"'\}. Число классов переменных ограничим сверху пятью известными науке, рассмотренными выше, л-^5. Таким образом, Х = К = {у|^£Ки{0}}. Тогда мера сложности записывается как:

Я = (.х,у)Ье(2 сХ®¥, (2)

где () - множество векторов (х, у), т.е. допустимых в модели задачи пар («число классов переменных», «число классов разнородных отношений»):

е = {(*, Є N. ^2,уєКи{0),ї-1^х!/(ї-2)!}и{(і, О)}. (3)

Для сравнения задач по сложности моделирования введем метрику р множества 0;.

Определим отображение Н множества векторов Q (3) на множество классов задач Х= {«простые», «сложные»}:

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

Выполнен сравнительный анализ известных и разработанной мер сложности по признакам «объект измерения», «степень формализации», «применимость для выбора метода решения», и показано, что мера (2) дает численные оценки и применима на наименее формализованном этапе разработки модели.

Мера сложности (2) апробирована на вычислении оценок сложности для классификации известных формулировок транспортно-логистических задач, сводимых к задаче коммивояжера: 1) классической, 2) обобщенной, 3) с временными окнами, 4) динамической, 5) вероятностной. Вычисление оценок выполнялось по разработанному алгоритму 2.1. Задачи 1 и 2 имеют оценки меры сложности ц = (1, 0) и относятся к классу простых. Задачи 3-5 имеют оценку ц = (2, 1) и попадают в класс сложных.

Детально формулируются условия СТЛЗ, определяются исходные и выходные данные, строится ее концептуальная модель и вычисляется оценка сложности моделирования (разработки модели). Построенная концептуальная модель показала, что задача имеет меру сложности моделирования ц — (5, 7).

В третьей главе «Моделирование коллективного решения сложной транспортно-логистической задачи» разработаны модель ГиИМАС с самоорганизацией, модель рассуждений агента, принимающего решения, метод моделирования процессов самоорганизации в СППР с использованием ГиИМАС.

Процесс самоорганизации в СППР предлагается моделировать с использованием ГиИМАС, определяемой следующим образом:

(4)

И: е-»г,

если (х,у) = (1, 0), то г = «простая», 1 если (ху) є <3, то г = «сложная» Г

Ытж = (Л С, ет>, ШҐ, ОКв, {50, і/}), АСГ ...,agn,ag'ы}, ШТ' = {ргог, Іап£, опі,гсІ},

(5)

(6) (7)

ORG = ORGmlp и ORGmM u ORGcomp, ORGmtlp n 0/?G„„ = 0, ORGcxp n ORGcmip = 0, n 0/?G„e„, = 0,

<"**«« = ( (J ac^juac^uac^uac^, (9)

agtAG

actv=(METv,ITJ,ageA(?, ||J JTJ>2, (10)

ageAC"

ag-=agwhimas, (11)

где AG' - множество агентов ag, включающее агента, принимающего решения (АПР) - ag'lm ; п - число агентов-экспертов; ет - внешняя среда ГиИМАС; INT - элементы структурирования взаимодействий агентов: prot - протокол взаимодействия, lang - язык передачи сообщений, ont - модель предметной области, rcl - классификатор отношений агентов; ORG - множество архитектур ГиИМАС (ORGmlp - с сотрудничающими, ORGnelll - с нейтральными и

ORGcomp - с конкурирующими агентами); {sa, si] - множество концептуальных моделей макроуровневых процессов в ГиИМАС: so - самоорганизация и si -самообучение ЛПР; acthlmjs - функция ГиИМАС в целом; actag - функция агента из множества AG' ; actta - функция «анализ взаимодействий» АПР agäm\ actac - функция «выбор архитектуры» АПР ag'1'" ; actœ, - коллективная функция ГиИМАС на межагентных отношениях Rra"s в выражении (14) и определяемая текущей архитектурой org, конструируемая динамически в процессе функционирования системы; met - метод решения задачи; it - интеллектуальная технология (МФПС), в рамках которой реализован метод metag.

Для реализации функции «выбор архитектуры» actac АПР должен иметь базу знаний о релевантности архитектуры ГиИМАС ситуации решения задачи:

act* = С т°"{Шж,тос1ос) ° г," °'s{actac,algJ, (12)

где moclac - модель нечеткого вывода; algac - алгоритм функции «выбор архитектуры»; г"" """' - отношение между действием и его моделью; r°" "'s - отношение действия и его алгоритма.

Сформулирована modac модель нечеткого вывода Мамдани с самообучением. В результате выполнения этапов нечеткого вывода определяются четкие оценки степеней уверенности АПР в выборе одной из трех архитектур: ORGcmp, ORG„eu, или ORGmmp.

Используя (5) - (11), разработан метод моделирования самоорганизации СППР как управление взаимодействием экспертов на основе анализа их целей. Вводится формализованное понятие нечеткой цели эксперта рг- нечеткое множество с функцией принадлежности , заданное на множестве состояний БТ объекта управления (ОУ). Состояние .с; ОУ описывается набором его свойств РЯ = {рг, ,...,ргЫрг}, т.е. = ..., ргКрг) ■ Значение нечеткой цели определяется подстановкой значений свойств ОУ для данного состояния из множества УАЬ = {уд/,, ..., valNml}, т.е. ц(ря/,, ..., уа1ы). Вводится мера сходства нечетких целей Л и В для одномерного случая:

1 1'£|/пи, *(А,В) = ~( } ^(рг)Ырг)-а | »л{рг),1ргГ1Н ] \1,(рг) а рг)-*). (12)

ш'ггап

Представим тип отношения по направленности взаимодействия между экспертами нечеткими множествами конкуренции, нейтралитета и сотрудничества на универсуме значений меры сходства целей (множестве действительных чисел в интервале [0; 1]): = + .у)8)"', =

(1 + (б • •- 0,5))»)-', = (1 + (3 ■ (, ■-1))8)'1.

Отношение между участниками СППР по степени согласованности их взаимодействия представим лингвистической переменной:

с1 = ф,Т,и,в,М), (13)

где р =«тип отношений» - наименование лингвистической переменной; Г= {«конкуренция»', «нейтралитет»; «сотрудничество»} - терм-множество ее значений, каждое из которых - название нечеткой переменной; и = [0; 1] - универсум нечетких переменных; О = 0 - процедура образования из элементов множества Т НОВЫХ термов; М = {^конкуренция^), (¡нейтралитет^), ИсотруднтесттСО} ~ процедура, ставящая в соответствие каждому терму множества Т осмысленное содержание путем формирования соответствующего нечеткого множества.

Когда для каждой пары участников СППР определено значение с1 и составлена матрица СЬ (матрица типов отношений), она анализируется, чтобы определить ситуацию коллективного решения задачи: сотрудничество, нейтралитет и конкуренция. В зависимости от параметров задачи ЛПР стремится установить одну из них, чтобы повысить эффективность работы СППР.

В результате имитации процессов самоорганизации и самообучения определяется архитектура ощ ГиИМАС:

ог% = К""\AG\env) о Я'" г"(АС,Ав'), (14)

где Л1"- множество отношений «ресурс - ресурс». 14

Учитывая, что функция ас1п агента ag е АО' выполняется множеством методов МЕТ^ (над множеством МФПС - ¡Т^), концептуальная модель ГиИМАС, как метода решения сложной задачи, представляется выражением:

-(ЛЖГЧ1,А<ЕГЧу), аьщеАСГ, а^Фаг,, где метод МЕТ^, вырабатываемый ГиИМАС при решении сложной задачи, -взаимосвязанная совокупность методов МЕТ > реализуемых агентами.

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

Таким образом, суть метода моделирования процессов самоорганизации в СППР с использованием ГиИМАС состоит в выполнении логически упорядоченной последовательности следующих действий: 1) Анализ взаимодействий агентов; 2) Выбор архитектуры: 2.1) Получение исходных данных; 2.2) Вычисление по алгоритму нечеткого вывода Мамдани значений степеней уверенности в выборе архитектуры; 2.3) Выбор архитектуры с вероятностью пропорциональной степеням уверенности из п. 2.2; 2.4) Имитационный процесс решения задачи на архитектуре из п. 2.3; 2.5) Вычисление значения абсолютной ошибки нечеткого вывода в п. 2.2; 2.6) Корректировка функций принадлежности нечетких переменных по ошибке. Для компьютерной реализации этого метода разработано, в общей сложности, шесть алгоритмов.

В четвертой главе «Гибридная интеллектуальная многоагентная система с самоорганизацией для решения сложной транспортно-логистиче-ской задачи» обосновывается функциональная структура системы, выбирается программная среда и разрабатывается методика применения системы для решения СТЛЗ.

По результатам анализа (5) - (11) сформулированы восемь требований к программной реализации ГиИМАС с самоорганизацией. Для удовлетворения этим требованиям разработана универсальная функциональная структура ГиИМАС (рис. 2). Рассмотрим назначение ее агентов:

1) интерфейсный агент запрашивает входные данные и выдает результат;

2) АПР рассылает агентам поиска решения условия задачи, определяет порядок их взаимодействия (функции «анализ взаимодействия» и «выбор архитектуры»), Когда последние решили задачу, он выбирает одну из альтернатив и

15

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

Аналитический Сюх.чсжчс- Логическии

агент скин а1С1Н агет

И|ИС|х)|СЙС-

ный агент

0<МП11<Р

-- 1Г.ЛШ1№Т1|1МТ!С!!ИЯ ПГСПТЛП: 'МИф'ХЫ 111|форМ11ЦИИ. ПСрСДПЧЛ 1^С1\'.Т1.ТПТОП 11\* рСШСГГПЯ.

------к. - ГГ"ИШООП1(1ШС1ГНЯ пгептоп: гппрош помощи в решепнн ПОДТЛД/1'1.

--- и -шмпдснс иши и| стон с моделью иредмешойиб»ш;|и

Рис. 2. Универсальная функциональная структура гибридной интеллектуальной многоагентной системы с самоорганизацией

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

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

5) агенты интеллектуальных технологий в верхней части рис. 2 вместе с агентом-преобразователем реализуют гибридную составляющую ГиИМАС, комбинируя разнородные знания, и предоставляют «услуги» агентам с использованием следующих моделей и алгоритмов: алгебраических уравнений для описания причинно-следственных связей концептов предметной области; метода Монте-Карло; продукционной экспертной системы с рассуждениями в прямом направлении; алгоритма нечеткого вывода Мамдани;

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

Анализ предложенной структуры ГиИМАС с самоорганизацией (рис. 2) и архитектур его агентов показал, что они полностью соответствуют модели ГиИМАС с самоорганизацией на основе анализа целей агентов (5) - (11) и реализуемы на одном из специальных средств разработки многоагентных систем: 16

Tryllian Agent Development Kit, AnyLogic, JACK, Java Agent Development Framework (JADE), Multi Agent Development Kit, NetLogo. Для разработки выбрана среда JADE, как соответствующая спецификации FIPA, свободно распространяемая система, содержащая средства отладки и развертывания, позволяющая создавать кроссплатформенные приложения.

Разработанный ПП ТРАНСМАР состоит из 57 модулей, разбитых на три пакета: «agents» - девять модулей, описывающих агентов ГиИМАС; «interface» — пять модулей пользовательского интерфейса интерфейсного агента; «ontology» - 43 модуля, обслуживающие модель предметной области. Общий объем исходного кода превысил девять тысяч строк.

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

Рис. 3. Методика действий пользователя по решению СТЛЗ с использованием ПП ТРАНСМАР

В пятой главе «Исследование явлений и процессов коллективного принятия решений в программном продукте ТРАНСМАР на примере сложной транспортно-логистической задачи» ставятся цели, задачи, рассматривается организация лабораторных экспериментов, оцениваются экономические показатели практического использования ПП ТРАНСМАР.

Сформулированы следующие цели экспериментов:

1) проверить в лаборатории работоспособность ПП ТРАНСМАР, оценить технико-эксплуатационные показатели автоматизированного решения СТЛЗ;

2) сравнить качество решений СТЛЗ, предлагаемых ЭВМ, с результатами экспертов, принимающих решения на практике;

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

4) по результатам компьютерного моделирования коллективных решений извлечь знания для подготовки и совершенствования деятельности ЛПР в СППР на транспорте;

5) рассчитать оценки экономических показателей автоматизированного решения сложных задач с использованием ПП ТРАНСМАР в условиях опытной и промышленной эксплуатации.

Эксперименты выполнялись для СТЛЗ (табл. 2), сформулированной в гл. 2. Выходные данные: совокупность маршрутов доставки грузов (по одному на транспортное средство) и ее параметры: стоимость, длительность, надежность и вероятность опоздания, сводный критерий качества маршрута (среднее значение нечеткой цели АПР). Исходные данные СТЛЗ: 1) запросы клиентов на доставку грузов (наименование, количество товара, временной интервал его доставки); 2) сведения о дорогах к клиентам (протяженность, загруженность, качество); 3) паспортные данные транспортных средств (расход горючесмазочных материалов, грузоподъемность и т.п.); 4) сведения о графиках работы и заработной плате персонала (водителей и грузчиков); 5) информация о перевозимом грузе (вес, габариты, хрупкость и т.п.).

Таблица 2. Количественные параметры тестируемых СТЛЗ

Задача Количество Количество Количество Количество Количество

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

СТЛЗ 10 10 75 3 3 3

СТЛЗ 15 15 240 5 5 5

СТЛЗ 20 20 420 5 5 5

СТЛЗ 25 25 650 9 9 9

СТЛЗ 30 30 377 б б 6

Исследовались три архитектуры ГиИМАС (табл. 3).

Таблица 3. Оценки архитектур ГиИМАС

Архитектура Параметры маршрута

Агент, принимающий решения Агент поиска решения 1 Агент поиска решения 2 Агент поиска решения 3 Агент поиска решения 4

org^ORGcoop ст, дл, ве(гшп), на(тах) ст, дл, ве(тт), на(тах) ст, дл, ee(min), на(тах) ст, дл, ве(ш1п), на (шах) ст, дл, ве(т1п), на(тах)

orgzeORGml ст, дл, ве(тт), на(тах) ст(тт) дл(тт) на(тах) ве(тш)

org3 е ORGu>mp ст, дл, ве(тт), на(тах) ст(тт), дл(тах) ст(тах), дл (min) на(тах), ве(тах) на(тт), ве(тт)

Обозначения: ст - стоимость; дл - длительность; на — надежность; ве — вероятность опоздания

В общей сложности для каждой архитектуры (табл. 3) и каждой задачи (табл. 2) проведено по сто вычислительных экспериментов на ПЭВМ со следующими характеристиками: процессор - Intel Соге 2 Duo 2,4 ГГц, оперативная память - 2 Гб, операционная система - Microsoft Windows ХР Professional.

В ходе экспериментов установлено следующее.

ПП ТРАНСМАР версии 1.1 работоспособен, его технико-эксплуатационные характеристики: занимаемая память - от 0,2 до 1,5 Гб, время решения тестовой задачи от 2 до 30 мин, при загрузке процессора в среднем 95%; подготовка исходных данных от 5 до 30 мин. Эти показатели лучше, чем у ГиИС, решавшей СТЛЗ со сложностью моделирования q = (3, 2) в ранних работах автора. Сравнение ГиИМАС и аналогичной ГиИС для решения CTJI3 показало, что моделирование эффекта самоорганизации СППР в ГиИМАС позволило динамически синтезировать метод решения сложных задач на основе базовых методов-знаний агентов: 1) при решении СТЛЗ вырабатывается релевантный ей метод, что повышает качество решений; 2) стало возможным решать СТЛЗ с более высокими оценками сложности моделирования; 3) сокращается трудоемкость проекта за счет отказа от настройки межагентных связей. Разработанная методика поддерживается системой управления ПП ТРАНСМАР, легко усваивается персоналом, позволяя эффективно использовать ПП на практике.

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

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

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

-----о—------—---г^

..............х.

£ 50 .

1 «

*' х.

ю . \

N

Архитектура ГиИМАС с Количество клиентов

10 15 20 и 30

......*......иониуренцией 35 73 69 36 2

—О— ней фа пи те юм 93 94 93 92 63

— * — согр>дн»*еетвом 69 ее В7 68 99

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

Разработка, внедрение и эксплуатация ПП ТРАНСМАР сопровождались технико-экономическими показателями, приведенными в табл. 4.

Таблица 4. Оценки экономических показателей в результате внедрения ПП

ТРАНСМАР

Показатель Значение до внедрения Значение после внедрения Процент изменения

Средняя суммарная себестоимость доставки в день, руб. 14923,15 13784,61 7,63

Средняя суммарная длительность доставки в день, ч 62,4 59,2 5,13

Среднее число опозданий к клиентам в день, шт. 7,6 6,3 17,11

Среднее число обслуженных клиентов в день, шт. 78,2 80,8 3,32

Средняя себестоимость доставки в расчете на одного клиента, руб. 190,83 170,6 10,6

Среднее время построения маршрутов в день, ч 3,8 2,6 31,58

Рассчитаны экономическая эффективность и срок окупаемости ПП ТРАНСМАР. Определены стоимость разработки Цт =417 407,02 руб., расходы потребителя, связанные с эксплуатацией ПП Рзп = 142 022,82 руб., общие капитальные затраты на внедрение ПП Ркт = 431 532,02 руб., затраты потребителя при решении задачи вручную = 321 600 руб. В результате годовая экономия эксплуатационных расходов у одного потребителя составила 179 577,18 руб. Годовая экономия за счет оптимизации маршрутов доставки составила 285 773,54 руб. Срок окупаемости ПП - Ток = 0,93 года.

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

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

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

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

4. Универсальная информационная структура, реализующая в ЭВМ интегрированное представление знаний - ГиИМАС - и имитационный процесс ее функционирования, отображающий самоорганизацию систем, принимающих коллективные решения, удовлетворяют предложенным в работе требованиям, реализованы программно и апробированы на примере СТЛЗ.

5. Методика применения ГиИМАС для решения СТЛЗ позволяет сделать обработку информации в отношении «оригинал - модель» целенаправленной и может быть положена в основу методологии и технологии компьютерных систем поддержки принятия решений, а также позволит избежать многочисленных ошибок проектирования и «откатов назад», что приводит к выходу проектов интеллектуальных систем за рамки бюджета и ресурсов.

6. Разработанный ПП «Транспортный маршрутизатор» позволил в лабораторных условиях имитировать и исследовать сложное и многогранное явле-

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

7. Анализ технико-эксплуатационных параметров показывает, что в условиях эксперимента время решения СТЛЗ составило 2-30 мин, а качество решений подтверждено экспериментально и экспертами. По итогам практического использования ПП ТРАНСМАР на двух объектах средняя суммарная себестоимость доставки грузов в день сократилась на 7,6%, средняя суммарная длительность доставки в день - на 5%, среднее время построения маршрутов в день уменьшилось на 31,6%.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в журналах, рецензируемых ВАК

1) Кириков И.А., Колесников A.B., Листопад C.B. Моделирование самоорганизации групп интеллектуальных агентов в зависимости от степени их взаимодействия // Информатика и её применения. - Т. 3, Вып. 4. - М., 2009. - С. 76 -86 (личный вклад - разработка подхода к созданию интеллектуальной СППР с самоорганизацией).

2) Кириков И.А., Колесников A.B., Листопад C.B. Исследование эффекта самоорганизации в компьютерных системах поддержки принятия решения на примере многоагентных систем // Вестник Российского государственного университета им. Иммануила Канта. - Вып. 10: Сер. Физико-математические науки. - Калининград: Изд-во РГУ им. И. Канта, 2010. - С. 79 - 90 (личный вклад - разработка модели самоорганизации СППР на основе анализа степени взаимодействия участников, результаты вычислительных экспериментов).

Коллективная монография

3) Колесников A.B., Кириков И.А., Листопад C.B., Румовская С.Б., Доманиц-кий A.A. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем / Под ред. A.B. Колесникова. - М.: ИПИ РАН, 2011. - 295 с. (личный вклад - обзор постановок траспортно-логистических задач, в том числе задачи коммивояжера, методов га решения, разработка метода решения СТЛЗ коллективом интеллектуальных агентов).

Статьи, тезисы докладов

4) Листопад C.B. Решение сложной практической задачи коммивояжера методами гибридных интеллектуальных систем // Искусственный интеллект: философия, методология, инновации. Материалы 2-ой международной молодежной конференции. Санкт-Петербург, 15-17 ноября 2007 г. - СПб., 2007. - С. 199-201.

5) Листопад C.B. Философско-методологический анализ синергетического эффекта в симбиозе интеллектуальности и реактивности в системах искусственного интеллекта // Образование, наука и инженерная деятельность в социокультурном пространстве эксклавного региона: история, актуальные проблемы, перспективы развития / ФГОУ ВПО «КГТУ»; гл. ред. В.В. Брюханов. - Калининград, 2007. - С. 51 - 53.

6) Kolesnikov А.V., Listopad S.V., Kirikov I.A. Investigation of self-organization relations in intelligent agents' teams// Pr. of The "Computer Days - 2009" . - Kaunas, 2009. - 89 - 91 pp. (личный вклад - разработка алгоритма определения архитектуры многоагешпной системы на основе анализа целей агентов).

7) Колесников A.B., Листопад C.B. Исследование отношений самоорганизации в коллективах интеллектуальных агентов // Искусственный интеллект: философия, методология, инновации. Материалы III Всероссийской конференции студентов, аспирантов и молодых ученых, МИРЭА / Под ред. Д.И. Дубровского и Е.А.Никитиной. - М.: Связь-Принт, 2009. - С. 18-20. (личный вклад - исследование самоорганизации коллектива интеллектуальных агентов).

8) Колесников A.B., Листопад C.B. Метод оценки степени сплоченности коллектива интеллектуальных агентов, принимающих решения // Труды VII юбилейной международной научной конференции Инновации в науке и образова-нии-2009, Ч. 2. - Калининград: КГТУ, 2009. - С. 175 - 177 (личный вклад - разработка меры сходства нечетких целей агентов).

9) Колесников A.B., Листопад C.B. Метод оценки степени взаимодействия интеллектуальных агентов в компьютерных системах поддержки принятия решений // Известия КГТУ. - 2010. - № 17: Материалы VII Международной научной конференции Инновации в науке и образовании-2009. - С. 166 - 170 (личный вклад - разработка метода идентификации типа архитектуры многоагент-ной системы на основе анализа целей агентов).

10)Кириков И.А., Колесников A.B., Листопад C.B. Моделирование процессов самоорганизации в коллективах интеллектуальных агентов // Материалы IV Всероссийской конференции студентов, аспирантов и молодых учёных Искусственный интеллект: философия, методология, инновации. - Ч. 1. - М.: Радио и связь, 2010. - С. 9 - И (личный вклад - разработка модели самоорганизации коллектива интеллектуальных агентов).

Подписано в печать: 15.02.12

Объем: 1,5 усл.п.л. Тираж: 100 экз. Заказ № 7058 Отпечатано в типографии «Реглет» 119526, г. Москва, Проспект Вернадского д.39 (495) 363-78-90; www.reglet.ru

61 12-5/1726

КАЛИНИНГРАДСКИЙ ФИЛИАЛ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО УЧРЕЖДЕНИЯ НАУКИ ИНСТИТУТА ПРОБЛЕМ ИНФОРМАТИКИ РОССИЙСКОЙ АКАДЕМИИ НАУК

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

Листопад Сергей Викторович

ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА МОДЕЛИРОВАНИЯ

КОЛЛЕКТИВНОГО ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ

Специальность 05.13.17 — «Теоретические основы информатики»

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

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

Калининград 2012

СОДЕРЖАНИЕ

1 СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ — ИНСТРУМЕНТ

КОЛЛЕКТИВНОГО РЕШЕНИЯ ЗАДАЧ.................................................................11

1.1 Особенности сложной транспортно-логистической задачи......................11

1.2 Концептуальная модель коллективного принятия решений..................25

1.3 Интегрированные методы компьютерного моделирования процессов и явлений коллективного принятия решений...............................36

1.4 Проблемы коллективного принятия решений и задачи диссертационной работы.......................................................................................42

2 МОДЕЛИРОВАНИЕ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ...........................................................................................................................45

2.1 Мера сложности моделирования задач.........................................................45

2.2 Классификация транспортно-логистических задач по сложности моделирования.........................................................................................................53

2.3 Условия сложной транспортно-логистической задачи.............................58

3 МОДЕЛИРОВАНИЕ КОЛЛЕКТИВНОГО РЕШЕНИЯ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ...................................................65

3.1 Концептуальная модель самоорганизации в системах поддержки принятия решений на основе анализа целей.....................................................65

3.2 Гибридная интеллектуальная многоагентная система с самоорганизацией....................................................................................................74

3.3 Модель рассуждений агента, принимающего решения.............................79

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

4 ГИБРИДНАЯ ИНТЕЛЛЕКТУАЛЬНАЯ МНОГОАГЕНТНАЯ СИСТЕМА С САМООРГАНИЗАЦИЕЙ ДЛЯ РЕШЕНИЯ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ...................................................92

4.1 Функциональная структура системы...........................................................92

4.2 Выбор среды разработки...............................................................................100

4.3 Методика применения системы при решении сложной транспортно-логистической задачи...................................................................103

5 ИССЛЕДОВАНИЕ ЯВЛЕНИЙ И ПРОЦЕССОВ КОЛЛЕКТИВНОГО ПРИНЯТИЯ РЕШЕНИЙ В ПРОГРАММНОМ ПРОДУКТЕ ТРАНСМАР НА ПРИМЕРЕ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ ....109

5.1 Цели, задачи и организация экспериментов..............................................109

5.2 Результаты и анализ вычислительных экспериментов..........................116

5.3 Оценка экономических показателей практического использования программного продукта ТРАНСМАР...............................................................123

ЗАКЛЮЧЕНИЕ............................................................................................................129

СПИСОК ЛИТЕРАТУРЫ..........................................................................................131

ПРИЛОЖЕНИЕ А.......................................................................................................146

ПРИЛОЖЕНИЕ Б

149

Список сокращений

ВЗК — вероятностная задача коммивояжера

ГиИМАС — гибридная интеллектуальная многоагентная система

ГиИС — гибридная интеллектуальная система

ГСМ — горюче-смазочные материалы

ДЗК — динамическая задача коммивояжера

ДП — детерминированная переменная

ЗКВО — задача коммивояжера с временными окнами

ИИ — искусственный интеллект

ИЭС — интегрированная экспертная система

КЗК — классическая задача коммивояжера

КСППР — компьютерная система поддержки принятия решений

ЛПР — лицо, принимающее решения

MAC — многоагентная система

МФПС — метод формализованного представления систем

ОЗК — обобщенная задача коммивояжера

ОУ — объект управления

ГШ — программный продукт

CTJI3 — сложная транспортно-логистическая задача

СППР — система поддержки принятия решений

СП — стохастическая переменная

ACL — Agent communication language

ADK — Agent development kit

COOL — Coordination language

JADE — Java agent development framework

KQML — Knowledge query manipulation language

MADKit — Multi agent development kit

MASIF — Mobile agent system interoperability facilities

OMG — Object management group

FIPA — Foundation for intelligent physical agents.

Введение

Результаты информатики за последние полвека со всей очевидностью показали, что применение на практике методов моделирования принятия решений, развитых в рамках парадигмы рационализма и редукционизма, не всегда дает корректные результаты [1 - 4]. Дело в том, что задачи из практики принятия решений — сложные, состоящие из множества взаимосвязанных, взаимозависимых частей, и для их решения требуются знания различных научных школ. В практике принятия решений сложные задачи по-прежнему решаются «вручную» системами поддержки принятия решений — коллективами экспертов под управлением лица, принимающего решения.

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

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

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

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

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

Выполнение работы связано с плановыми исследованиями Калининградского филиала ИПИ РАН, проводимыми в рамках Программы фундаментальных научных исследований государственных академий наук на 2008 - 2012 годы, утвержденной распоряжением Правительства Российской Федерации от 27.02.2008 г. № 233-р (направления 27, 28). Гибридная интеллектуальная многоагентная система для решения сложной транспортно-логистической задачи и программный продукт «Транспортный маршрутизатор ТРАНСМАР» версия 1.1, реализующий ее, были разработаны в Калининградском филиале ИПИ РАН в рамках проекта «Альянс» (2010 - 2011 гг.), а также тесно связанного с ним проекта «Гибрид-функционал» (2007 - 2009 гг.). Особенность ГиИМАС — использование взаимодействующих агентов интеллектуальных технологий, которые вместе способны имитировать несколько разнородных линий рассуждений. Благодаря наличию агента, принимающего решения, система может перестраивать свою архитектуру и менять алгоритм своего функционирования, т.е. проявлять признаки самоорганизации, а сам агент, принимающий решения, способен обучаться в ходе эксплуатации системы. В качестве примера сложной задачи в диссертации рассматривается сложная транспорт-но-логистическая задача доставки грузов клиентам.

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

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

В третьей главе разработаны модель ГиИМАС с самоорганизацией, модель рассуждений агента, принимающего решения, метод моделирования процессов самоорганизации в СППР с использованием ГиИМАС.

В четвертой главе предлагается функциональная структура системы, выбирается программная среда и разрабатывается методика применения системы для решения СТЛЗ.

В пятой главе ставятся цели, задачи, рассматривается организация лабораторных экспериментов, оцениваются экономические показатели практического использования ПП «Транспортный маршрутизатор ТРАНСМАР».

Цель диссертационной работы состоит в том, чтобы для решения поставленной научно-технической задачи: 1) получить новые знания о сложности моделирования задач; 2) разработать и исследовать метод, модели, алгоритмы интегрированного, гибридно-многоагентного представления знаний о сложной задаче; 3) создать и исследовать ПП, имитирующий поведение коллектива людей, вырабатывающих и применяющих метод решения сложной задачи над различными линиями рассуждений экспертов.

Задачи исследования:

1. Выявление объективных параметров классификации задач по признаку сложности моделирования и разработка меры сложности моделирования задач;

2. Исследование явлений и процессов самоорганизации в СППР;

3. Разработка метода моделирования процессов самоорганизации в системах поддержки принятия решений с использованием ГиИМАС;

4. Извлечение знаний о поведении ЛПР по управлению коллективом в СППР с использованием компьютерного моделирования;

5. Разработка и исследование программной реализации ГиИМАС с самоорганизацией и методики для решения СТЛЗ.

Данные задачи были решены в ходе работы.

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

классов методов: аналитические, статистические, экспертных систем, нечетких систем, искусственных нейронных сетей, генетических алгоритмов; новый класс гибридных интеллектуальных многоагентных систем.

Содержание диссертационного исследования соответствует специальности 05.13.17 «Теоретические основы информатики» (пункты 1, 2, 4, 8 паспорта специальности ВАК)

Методическая база исследований. Для разработки меры сложности задач использовались: дискретная математика, теория множеств, теория графов, модели «неоднородная задача» и «однородная задача», информационный язык «ресурс-свойство-действие-отношение» A.B. Колесникова. Для разработки метода моделирования самоорганизации в СППР с использованием ГиИМАС применялись теория нечетких множеств, методы нечеткой логики. При разработке ПП ТРАНСМАР использовались алгебраические уравнения, алгоритм колонии муравьев, продукционная экспертная система с рассуждениями в прямом направлении, алгоритм нечетких рассуждений Мамдани и метод Монте-Карло. Применялось объектно-ориентированное, агентно-ориентированное, модульное программирование. Методика применения ПП основана на проблемно-структурной методологии ГиИС.

Научная новизна состоит в том, что:

1. Предложена классификация задач по сложности моделирования и разработана мера сложности моделирования задач;

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

3. Разработан метод моделирования самоорганизации в СППР с использованием гибридной интеллектуальной многоагентной системы;

4. Получены новые знания о поведении лица, принимающего решения, по управлению коллективом СППР методом компьютерного моделирования;

5. Разработана программная реализация ГиИМАС с самоорганизацией для решения сложной транспортно-логистической задачи - ПП «Транспортный маршрутизатор ТРАНСМАР» версии 1.1 - и методика ее применения.

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

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

Практическая ценность диссертационной работы состоит в том, что разработанный ПП «Транспортный маршрутизатор ТРАНСМАР» версии 1.1 может использоваться при создании компьютерных интеллектуальных СППР, что снижает временные затраты на проект у разработчика и повышает эффективность системы управления, сокращая потери от ошибочных и нерелевантных решений.

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

Реализация результатов исследования. Метод моделирования самоорганизации в СППР с использованием ГиИМАС реализован, что подтверждается свидетельствами о регистрации программ для ЭВМ [5-7]. Мера оценки сложности моделирования и ПП ТРАНСМАР использовались: 1) в лабораторных экспериментах для моделирования самоорганизации в СППР и оценки качества коллективных решений в сравнении с индивидуальными; 2) при разработке КСППР для транспорт-но-логистических предприятий ЗАО «Совтрансавто-Калининград» и ООО «Балт-реммаш», выполняющих международные и региональные перевозки. Использование подтверждается двумя актами о внедрении результатов диссертационной работы (приложение А). Результаты планируется использовать в проектах интеллектуального муниципалитета и ситуационных центров в Калининградской области.

Положения, выносимые на защиту. На защиту выносятся следующие полученные автором результаты:

1. Мера оценки сложности моделирования, основанная на объективных параметрах разнообразия и неоднородности информации: «класс переменных» и «класс отношений», позволяющая вычислить границу сложных задач, определить требования к структурным свойствам КСППР, количественно оценить релевантность моделей оригиналам;

2. Модель ГиИМАС с самоорганизацией, релевантно отображающая в памяти ЭВМ как разнообразие знаний агентов-экспертов, так и их информационные взаимодействия между собой и агентом-ЛПР в ходе анализа, редукции и поиска решения сложной задачи;

3. Метод моделирования самоорганизации СППР на основе анализа целей агентов для синтеза релевантного ситуации принятия решений инструмента;

4. Модель информационной структуры, реализующей в ЭВМ интегрированное представление знаний - ГиИМАС, и процесс ее функционирования, отображающий самоорганизацию в СППР;

5. Методика применения ГиИМАС для решения СТЛЗ с целью прокладки маршрутов транспортных средств, выполняющих доставку грузов клиентам логистической компании.

Апробация работы. Основные положения диссертационной работы обсуждались на Международной научной конференции Computer Days - 2009 (Каунас, Литва, 2009); 7-й Международной конференции «Инновации в науке и образовании» (Калининград, 2009), Международных научных конференциях IT 2010 и IT 2011 (Каунас, Литва, 2010, 2011), III - V Всероссийских конференциях студентов, аспирантов и молодых учёных «Искусственный интеллект: философия, методология, инновации» (Москва, 2009, 2010, 2011), IX Международной конференции «Морская индустрия, транспорт и логистика в странах региона Балтийского моря: новые вызовы и ответы», посвященной 45-летию Балтийской государственной ак