Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
ЛИСТОПАД СЕРГЕЙ ВИКТОРОВИЧ
ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА МОДЕЛИРОВАНИЯ КОЛЛЕКТИВНОГО ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ СЛОЖНОЙ ТРАНСПОРТНО-ЛОГИСТИЧЕСКОЙ ЗАДАЧИ
Специальность:
05.13.17 - Теоретические основы информатики
АВТОРЕФЕРАТ
ДИССЕРТАЦИИ на соискание ученой степени кандидата технических наук
Москва 2012
Работа выполнена в Калининградском филиале Федерального государственного бюджетного учреждения науки Института проблем информатики Российской академии наук
Научный консультант: доктор технических наук, профессор Колесников Александр Васильевич
Официальные оппоненты:
Ярушкина Надежда Глебовна, доктор технических наук, профессор, ФГБОУ ВПО Ульяновский государственный технический университет, заведующая кафедрой "Информационные системы" Тарасов Валерий Борисович, кандидат технических наук, доцент, ФГБОУ ВПО Московский государственный технический университет им. Н.Э. Баумана, доцент кафедры компьютерных систем автоматизации производства
Ведущая организация:
Федеральное государственное бюджетное учреждение науки Межведомственный суперкомпьютерный центр Российской академии наук
Защита диссертации состоится _____________ 2012 г. в ___ часов ____ мин на заседании диссертационного совета Д002.073.01 при Федеральном государственном бюджетном учреждении науки Институте проблем информатики Российской академии наук по адресу: 119333, Москва, ул. Вавилова, 44, корп. 2.
С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института проблем информатики Российской академии наук.
Автореферат разослан л ___ _______ 2012 г.
Ученый секретарь диссертационного совета Д002.073.доктор технических наук, профессор _________ Гринченко Сергей Николаевич
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Увеличивающееся в обществе разнообразие информации и, как следствие, усложняющиеся задачи создания, накопления и обработки информации неизбежно приводят к ошибкам принятия решений, науко- и трудоемкости автоматизированного решения проблем. В то время как люди научились решать сложные задачи коллективно в самоорганизующихся системах поддержки принятия решений (СППР), информационные интеллектуальные системы с парадигмой компьютерного моделирования процессов и явлений в памяти одного человека все менее и менее релевантны этим целям. Методы и модели информатики для автоматизированного решения задачи в принципе в научной лаборатории оказались не пригодными в программных приложениях на практике. Одна из фундаментальных проблем состоит в том, что, с одной стороны, коллективы способны анализировать, редуцировать сложность проблемы и вырабатывать релевантный ситуации новый метод решения, комбинируя под руководством лица, принимающего решения (ЛПР), линии рассуждений экспертов, с другой стороны, в информатике: 1) компьютеры остаются вычислителем для одного из известных инструментариев; 2) оценки сложности вычислений известны, а разработка моделей не изучается математикой.
По аналогии с экспертными системами, позволившими компьютеру рассуждать не хуже одного человека, актуально научить ЭВМ работать в условиях сложных задач не хуже коллектива специалистов. Д.А. Поспелов выделил задачу моделирования коллективного принятия решений как одну из десяти горячих точек в исследованиях по искусственному интеллекту. Автоматизированные системы, моделирующие коллективное принятие решений, смогут комбинировать различные виды знаний для решения сложной задачи, самостоятельно меняя алгоритм своего функционирования.
Теоретические основы комбинированных моделей для машинного синтеза новых динамично изменяемых методов решения задач рассматривались в работах В.И. Городецкого, М.С. Грушинского, Н.А. Земцова, В.Д. Ильина, Л.А. Калиниченко, К.А. Неусыпина, С.А. Ступникова, В.Б. Тарасова (многоагентные системы), А.В. Гаврилова, А.В. Колесникова, Н.Г. Ярушкиной (гибридные интеллектуальные системы), А.Н. Борисова, Г.В. Рыбиной, И.Б. Фоминых, А.И. Эрлих (интегрированные экспертные системы) и др. Наиболее цитируемые зарубежные авторы в этой области - 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 паспорта специальности ВАК) Методическая база исследований. Для разработки меры сложности задач использовались: дискретная математика, теория множеств, теория графов, модели неоднородная задача и лоднородная задача, информационный язык ресурс-свойство-действие-отношение А.В. Колесникова. Для разработки метода моделирования процессов самоорганизации в СППР с использованием ГиИМАС применялись теория нечетких множеств, методы нечеткой логики.
При разработке ПП Транспортный маршрутизатор ТРАНСМАР использовались алгебраические уравнения, алгоритм колонии муравьев, продукционная экспертная система с рассуждениями в прямом направлении, алгоритм нечетких рассуждений Мамдани и метод Монте-Карло. Применялось объектноориентированное, агентно-ориентированное, модульное программирование.
Методика основана на проблемно-структурной методологии гибридных интеллектуальных систем (ГиИС).
Научная новизна состоит в том, что:
1. Предложена классификация задач по сложности моделирования и разработана мера сложности моделирования задач;
2. Исследованы процессы и разработана модель самоорганизации в системах поддержки принятия решений на основе анализа целей участников;
3. Разработан метод моделирования самоорганизации в СППР с использованием гибридной интеллектуальной многоагентной системы;
4. Получены новые знания о поведении лица, принимающего решения, по управлению коллективом СППР методом компьютерного моделирования;
5. Разработана программная реализация гибридной интеллектуальной многоагентной системы с самоорганизацией для решения сложной транспортно-логистической задачи - ПП Транспортный маршрутизатор ТРАНСМАР версии 1.1 - и методика его применения.
Достоверность научных положений, рекомендаций и выводов. Обоснованность научных положений, рекомендаций и выводов определяется корректным использованием математических методов и моделей. Достоверность положений и выводов подтверждена результатами лабораторных исследований и экспериментальными данными, полученными при внедрении ГиИМАС. Определения, классификация задач, мера сложности моделирования апробированы на конференциях и в научных публикациях.
Практическая ценность диссертационной работы состоит в том, что разработанный программный продукт Транспортный маршрутизатор ТРАНСМАР версии 1.1 может использоваться при создании компьютерных интеллектуальных систем поддержки принятия решений, что снижает временные затраты на проект у разработчика и повышает эффективность системы управления, сокращая потери от ошибочных и нерелевантных решений.
Разработанная мера сложности моделирования задачи может использоваться для анализа результатов предпроектного обследования объекта автоматизации и разработки технического задания на компьютерные системы поддержки принятия решений, что позволяет рассчитать релевантные оценки архитектуры ГиИМАС, времени и ресурсов на реализацию проекта.
Реализация результатов исследования. Метод моделирования самоорганизации в СППР с использованием ГиИМАС реализован, что подтверждается свидетельствами о регистрации трех программ для ЭВМ. Мера оценки сложности моделирования и ПП ТРАНСМАР использовались: 1) в лабораторных экспериментах с целью моделирования самоорганизации в СППР и оценки качества коллективных решений в сравнении с индивидуальными; 2) при разработке компьютерных систем поддержки принятия решений (КСППР) для транспортно-логистических предприятий ЗАО Совтрансавто-Калининград и ООО Балтреммаш, выполняющих международные и региональные перевозки. Использование подтверждается двумя актами о внедрении результатов диссертационной работы.
Результаты планируется использовать в проектах интеллектуального муниципалитета и ситуационных центров в Калининградской области.
Положения, выносимые на защиту. На защиту выносятся следующие полученные автором результаты:
1. Мера оценки сложности моделирования, основанная на объективных параметрах разнообразия и неоднородности информации: класс переменных и класс отношений, позволяющая вычислить границу сложных задач, определить требования к структурным свойствам КСППР, количественно оценить релевантность моделей оригиналам;
2. Модель ГиИМАС с самоорганизацией, релевантно отображающая в памяти ЭВМ как разнообразие знаний агентов-экспертов, так и их информационные взаимодействия между собой и агентом-ЛПР в ходе анализа, редукции и поиска решения сложной задачи;
3. Метод моделирования самоорганизации СППР на основе анализа целей агентов для синтеза релевантного ситуации принятия решений инструмента;
4. Модель информационной структуры, реализующей в ЭВМ интегрированное представление знаний, - ГиИМАС - и процесс ее функционирования, отображающий самоорганизацию в СППР;
5. Методика применения ГиИМАС для решения СТЛЗ с целью прокладки маршрутов транспортных средств, выполняющих доставку грузов клиентам логистической компании.
Апробация работы. Основные положения диссертационной работы обсуждались на Международной научной конференции Образование, наука и инженерная деятельность в социокультурном пространстве эксклавного региона: история, актуальные проблемы, перспективы развития (Калининград, 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 страниц.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность работы. Сформулирована научно-техническая задача исследования. Ставятся цель и задачи исследования.
Рассматриваются объекты и методы исследования. Обоснованы научная новизна, достоверность, практическая значимость результатов исследований. Пред ставлены положения, выносимые на защиту. Приведены сведения о реализации и апробации результатов исследования.
В первой главе Системы поддержки принятия решений - инструмент коллективного решения задач проводится анализ особенностей сложной транспортно-логистической задачи, вводится и исследуется концептуальная модель коллективного принятия решений, дается аналитический обзор интегрированных методов компьютерного моделирования явлений и процессов коллективного принятия решений, выявляются проблемы коллективного принятия решений и ставятся задачи диссертационного исследования.
Проведен анализ определений сложности Э.С. Бира, С.П. Капицы, Е.Н. Князевой, С.П. Курдюмова, Г.Г. Малинецкого, Г. Николиса, И.Р. Пригожина, Г. Хакена и др. Рассмотрены подходы к определению сложности задачи В.М. Глушкова, Дж.Д. Додсона, Р.М. Йеркса, П. Норвига, С. Рассела и др. Их анализ показал, что понятие сложности многоаспектно, причем сложности моделирования (разработке модели) уделяется мало внимания. Сделан вывод об актуальности создания ее количественной меры для классификации задач и оценки успешности выполнения проекта ограниченными ресурсами.
Сложные задачи как оригиналы, прежде всего, характеризуются составным характером и разнообразием информации. Им релевантна модель неоднородная задача - задача-система, состоящая минимум из двух подзадач, отображаемых моделями лоднородная задача и несколькими методами формализованного представления систем (МФПС). Интегративное свойство сложной задачи не сводится к сумме свойств составляющих ее подзадач. Выделены и другие особенности класса сложных задач: невозможность поиска решения по частям и обеспечения полноты исходной информации, линии рассуждения одного эксперта недостаточно (полиязыковой характер), а единственный способ проверки качества решения - его выполнение.
Типичный пример задачи из класса сложных - СТЛЗ, решаемая в СППР логистических предприятий, доставляющих грузы своим клиентам. Она формулируется следующим образом: требуется найти совокупность маршрутов доставки (по одному на транспортное средство), охватывающих всех клиентов, заказавших доставку, с учетом условий перевозки для отдельных видов грузов, качества и загруженности дорог, временных интервалов доставки по желанию клиентов, а также нормативных актов в отношении персонала. Совокупность найденных маршрутов должна удовлетворять четырем критериям: стоимость (min), длительность (min), надежность (max) и вероятность опоздания (min).
В отличие от задачи коммивояжера в СТЛЗ снимаются ограничения на количество объектов, расширяется список классов отношений между объектами и их свойствами. Моделируются человеческий фактор, стохастические события, расширяется количество моделируемых классов переменных.
Исходя из особенностей класса сложных задач, решение СТЛЗ не может быть получено индивидуально, одним экспертом и требуется использование СППР - организационного в условиях внешней среды мероприятия коллективного принятия решений, основные участники которого - эксперты и ЛПР.
На информационном языке ресурс - свойство - действие - отношение вводится концептуальная модель СППР:
dss Rres res( prtdm,env) Rres res(PRT, PRT ), (1) где dss - модель взаимодействия участников СППР на структурно-информационном микроуровне; prtdm - модель знаний ЛПР; env RES - внешняя среда; PRT {prt1,..., prtn, prtdm}, PRT RES - множество участников СППР, включающее ЛПР prtdm ; Rres res - множество отношений ресурс - ресурс между участниками СППР, а также ЛПР и внешней средой.
Графически концептуальная модель (1) взаимодействия участников СППР на структурно-информационном микроуровне представлена на рис. 1.
Рис. 1. Концептуальная модель СППР на микроуровне Каждый ее участник преследует собственные цели, совпадающие или противоречащие целям других участников. За счет локальных взаимодействий Rres res экспертов в СППР возникают макроуровневые, внешне проявляющиеся явления и процессы. В результате построения и исследования их концептуальных моделей сделан вывод, что в основе явлений адаптации ad, гомеостаза ho, самообучения sl и синергетического эффекта se лежит самоорганизация so - способность СППР реагировать на изменения во внешней среде, адаптироваться к ней, корректируя свое поведение и устройство. Благодаря самоорганизации каждый раз при решении сложной задачи СППР вырабатывает новый метод решения, релевантный ее условиям, что повышает качество работы, проявляясь в синергетическом эффекте от взаимодействия экспертов.
Идеи самоорганизации восходят к А.А. Богданову, Л. Берталанфи, Ф.Х. Вареле, У.Р. Матуране, Н.Н. Моисееву, Г. Николису, И.Р. Пригожину, И. Стенгерсу, Г. Хакену, Э. Шредингеру, У.Р. Эшби и др.
В работе самоорганизация в СППР - перестроение ЛПР взаимодействий между экспертами на основе анализа степени их согласованности (близости целей). Вводятся три типа отношений: конкуренция - достижение цели одним участником исключает достижение цели другим; сотрудничество - цели участников совпадают; нейтралитет - цели не совпадают и не противоречат. В зависимости от наличия в СППР тех или иных типов отношений различаются три ситуации: 1) сотрудничества - СППР состоит только из сотрудничающих и нейтральных участников; 2) нейтралитета - в СППР есть только нейтральные отношения; 3) конкуренции - в СППР есть хотя бы одна пара экспертов с отношением конкуренции. По результатам анализа условий задачи ЛПР стремится установить одну из перечисленных ситуаций коллективного решения.
Приводятся и анализируются результаты обзора концепций искусственного интеллекта (ИИ), релевантных явлениям и процессам в СППР (табл. 1).
Таблица 1. Аналитический обзор концепций искусственного интеллекта для моделирования систем поддержки принятия решений Моделируемые объекты и аспекты СППР правила микро- макроКонцепция ИИ Основополагающие работы экссреда взаимо- уровневые уровневые перт действия модели эффекты Дж. Антсаклис, Р. Брокетт, А. Бэк, Х.
Гибридные Витценхаузен, У. Кон, М.Д. Леммон, - + - - - системы М.А. Майерс, А. Нерод, Дж. Стивер, Л. Травернини Интегрирован- А.Н. Борисов, Г.В. Рыбина, ные экспертные И.Б. Фоминых, А.И. Эрлих + + - - + системы Гибридные И.А. Кириков, А.В. Колесников, интеллектуаль- Н.Г.Ярушкина, Н. Касабов, Р. Козма, + + - + + ные системы С.Кхеббал, Л. Медскер Т.А. Гаврилова, В.И. Городецкий, Многоагентные М.С. Грушинский, В.Б. Тарасов, + + + + + системы А.В. Хабалов, В.Ф. Хорошевский, Г. Вейсс, М. Вулдридж Анализ табл. 1 показывает, что концептуальной модели СППР релевантна комбинация гибридных интеллектуальных и многоагентных систем, которая в синергетическом ИИ определяет свойства нового класса систем - гибридных интеллектуальных многоагентных систем.
По итогам исследования особенностей сложных задач, концептуального моделирования СППР и спецификации ГиИМАС выделяются проблемы моделирования коллективного принятия решений и ставятся задачи исследований.
Во второй главе Моделирование сложной транспортнологистической задачи разрабатывается мера сложности моделирования (разработки модели) задач, предлагается классификация транспортно-логистических задач по сложности моделирования, формулируются условия сложной транспортно-логистической задачи.
Мера сложности моделирования задачи позволяет рассчитывать границу между сложными и простыми задачами, количественно сравнить сложность моделирования задач, а также предъявлять требования к структурным свойствам системы, способной ее решать, оценивать релевантность задаче тех или иных КСППР. При этом разнообразие и неоднородность информации о задаче оценивается по двум объективным параметрам: класс переменной и класс отношения. Составлены ограниченные перечни классов переменных, используемых в МФПС: детерминированные de; стохастические st; логические (пропозициональные) lo; лингвистические нечеткие fu и лингвистические четкие (символьные) li. Так как переменные используются в информационном языке ресурс - свойство - действие - отношение для описания концептов свойство - PR, определим подмножества свойств, описываемых разными классами i j переменных: PR PR, PRi PR , i, j {de,st,lo, fu,li}, i j, а во мноi pr pr жестве отношений свойство - свойство R выделим подмножества отноpr pr pr i pr j шений, связывающие свойства из различных классов: R R, i, j i, j {de,st,lo, fu,li}. Класс отношения определяется по классам связываемых pr i pr i переменных. Отношения R, i{de, st,lo, fu,li} между переменными одноpr i pr j го класса назовем однородными, иначе если R, i, j {de,st,lo, fu,li}, i j, то они считаются разнородными.
Предлагаемая мера сложности включает два параметра: 1) количество x |VT | классов переменных в концептуальной модели задачи, где VT ' he {PRi | i {de, st,lo, fu,li}}; 2) количество y | RT | классов разнородных отноhe ' pr i pr j шений между ними, где RT {R | i, j {de, st,lo, fu,li },i j}. Множества he их значений обозначим X {x | x |VT |} и Y {y | y | RT |}. Число классов переменных ограничим сверху пятью известными науке, рассмотренными выше, x5. Таким образом, X {x | x , x5}, Y {y | y {0}}. Тогда мера сложности записывается как:
q (x, y) q Q X Y, (2) где Q - множество векторов (x, y), т.е. допустимых в модели задачи пар (лчисло классов переменных, число классов разнородных отношений):
Q x, y x , x2, y {0}, x 1yx!/ (x 2)! 1, 0. (3) Для сравнения задач по сложности моделирования введем метрику p множества Q:
p(q1,q2) (x2 x1)2 (y2 y1)2. (4) Определим отображение H множества векторов Q (3) на множество классов задач Z = {лпростые, сложные}:
h : Q Z, если (x,y) (1, 0), то z простая, H ((x, y), z).
если (x,y)Q, x2, то z сложная Соотнесение задачи с оценкой сложная означает, что метод ее решения должен быть получен комбинированием разнородных знаний МФПС. Соотнесение задачи с оценкой простая указывает на то, что принятие решений может носить индивидуальный характер.
Выполнен сравнительный анализ известных и разработанной мер сложности по признакам лобъект измерения, степень формализации, применимость для выбора метода решения, и показано, что мера (2) дает численные оценки и применима на наименее формализованном этапе разработки модели.
Мера сложности (2) апробирована на вычислении оценок сложности для классификации известных формулировок транспортно-логистических задач, сводимых к задаче коммивояжера: 1) классической, 2) обобщенной, 3) с временными окнами, 4) динамической, 5) вероятностной. Вычисление оценок выполнялось по разработанному алгоритму 2.1. Задачи 1 и 2 имеют оценки меры сложности q = (1, 0) и относятся к классу простых. Задачи 3 - 5 имеют оценку q = (2, 1) и попадают в класс сложных.
Детально формулируются условия СТЛЗ, определяются исходные и выходные данные, строится ее концептуальная модель и вычисляется оценка сложности моделирования (разработки модели). Построенная концептуальная модель показала, что задача имеет меру сложности моделирования q = (5, 7).
В третьей главе Моделирование коллективного решения сложной транспортно-логистической задачи разработаны модель ГиИМАС с самоорганизацией, модель рассуждений агента, принимающего решения, метод моделирования процессов самоорганизации в СППР с использованием ГиИМАС.
Процесс самоорганизации в СППР предлагается моделировать с использованием ГиИМАС, определяемой следующим образом:
himas (AG*,env, INT*,ORG,{so,sl}), (5) AG* {ag1,..., agn, agdm}, (6) INT* {prot, lang, ont,rcl}, (7) ORG ORGcoop ORGneut ORGcomp, ORGcoop ORGneut , (8) ORG ORG , ORG ORG , coop comp comp neut acthimas ( actag ) actia actac actcol, (9) agAG* actag (MET, IT ), ag AG*, | IT |2, (10) ag ag ag agAG* ag ag himas, (11) где AG* - множество агентов ag, включающее агента, принимающего решения (АПР) - agdm ; n - число агентов-экспертов; env - внешняя среда ГиИМАС;
INT* - элементы структурирования взаимодействий агентов: prot - протокол взаимодействия, lang - язык передачи сообщений, ont - модель предметной области, rcl - классификатор отношений агентов; ORG - множество архитектур ГиИМАС (ORGcoop - с сотрудничающими, ORGneut - с нейтральными и ORGcomp - с конкурирующими агентами); {so, sl} - множество концептуальных моделей макроуровневых процессов в ГиИМАС: so - самоорганизация и sl - самообучение ЛПР; acthimas - функция ГиИМАС в целом; actag - функция агента из множества AG* ; actia - функция ланализ взаимодействий АПР agdm ;
actac - функция выбор архитектуры АПР agdm ; actcol - коллективная функция ГиИМАС на межагентных отношениях Rres res в выражении (14) и определяемая текущей архитектурой org, конструируемая динамически в процессе функционирования системы; metag - метод решения задачи; itag - интеллектуальная технология (МФПС), в рамках которой реализован метод metag.
Для реализации функции выбор архитектуры actac АПР должен иметь базу знаний о релевантности архитектуры ГиИМАС ситуации решения задачи:
actac r1act mod (actac,modac) r1act alg (actac,algac), (12) где modac - модель нечеткого вывода; algac - алгоритм функции выбор архитектуры; r1act mod - отношение между действием и его моделью; r1act alg - отношение действия и его алгоритма.
Сформулирована modac модель нечеткого вывода Мамдани с самообучением. В результате выполнения этапов нечеткого вывода определяются четкие оценки степеней уверенности АПР в выборе одной из трех архитектур: ORGcoop, ORGneut или ORGcomp.
Используя (5) - (11), разработан метод моделирования самоорганизации СППР как управление взаимодействием экспертов на основе анализа их целей.
Вводится формализованное понятие нечеткой цели эксперта pr - нечеткое множество с функцией принадлежности (st), заданное на множестве состояний ST объекта управления (ОУ). Состояние st ОУ описывается набором его свойств PR {pr1,..., prNpr}, т.е. (st) ( pr1,..., prNpr ). Значение нечеткой цели определяется подстановкой значений свойств ОУ для данного состояния из множества VAL {val1,..., valNval}, т.е. (val1,..., valNval ). Вводится мера сходства нечетких целей A и B для одномерного случая:
valmax valmax valmax s(A, B) ( AB ( pr) d pr) (( A( pr) d pr)1 ( B( pr) d pr)1). (12) valmin valmin valmin Представим тип отношения по направленности взаимодействия между экспертами нечеткими множествами конкуренции, нейтралитета и сотрудничества на универсуме значений меры сходства целей s (множестве действительных чисел в интервале [0; 1]): "конкуренция"(s) (1 (3 s)8)1, "нейтралитет"(s) (1 (6 (s 0,5))8)1, "сотрудничество"(s) (1 (3 (s 1))8)1.
Отношение между участниками СППР по степени согласованности их взаимодействия представим лингвистической переменной:
cl ,T,U,G,M, (13) где = тип отношений - наименование лингвистической переменной;
T = {лконкуренция; нейтралитет; сотрудничество} - терм-множество ее значений, каждое из которых - название нечеткой переменной; U [0; 1] - универсум нечетких переменных; G - процедура образования из элементов множества T новых термов; M = {конкуренция(s), нейтралитет(s), сотрудничество(s)} - процедура, ставящая в соответствие каждому терму множества T осмысленное содержание путем формирования соответствующего нечеткого множества.
Когда для каждой пары участников СППР определено значение cl и составлена матрица CL (матрица типов отношений), она анализируется, чтобы определить ситуацию коллективного решения задачи: сотрудничество, нейтралитет и конкуренция. В зависимости от параметров задачи ЛПР стремится установить одну из них, чтобы повысить эффективность работы СППР.
В результате имитации процессов самоорганизации и самообучения определяется архитектура org ГиИМАС:
org Rres res(AG*,env) Rres res(AG*, AG*), (14) где Rres res - множество отношений ресурс - ресурс.
Учитывая, что функция actag агента ag AG* выполняется множеством методов MET (над множеством МФПС - IT ), концептуальная модель ag ag ГиИМАС, как метода решения сложной задачи, представляется выражением:
METhimas Rmet met (MET,MET ), agi,ag AG*, agi ag, agi ag j j j где метод METhimas, вырабатываемый ГиИМАС при решении сложной задачи, - взаимосвязанная совокупность методов MET, реализуемых агентами.
ag При решении очередной задачи АПР заново анализирует взаимодействия actia между агентами, выбирает архитектуру actac, определяя, таким образом, интенсивность и направленность отношений Rmet met между моделями знаний агентов, что может рассматриваться как выработка нового метода, релевантного ситуации решения сложной задачи. При этом возникает синергетический эффект. Внешнее его проявление - получение с помощью ГиИМАС решений более высокого качества в сравнении с решениями отдельных агентов.
Таким образом, суть метода моделирования процессов самоорганизации в СППР с использованием ГиИМАС состоит в выполнении логически упорядоченной последовательности следующих действий: 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) АПР рассылает агентам поиска решения условия задачи, определяет порядок их взаимодействия (функции ланализ взаимодействия и выбор архитектуры). Когда последние решили задачу, он выбирает одну из альтернатив и передает интерфейсному агенту, или запускает новую итерацию решения задачи, рассылая решение остальным агентам поиска;
Рис. 2. Универсальная функциональная структура гибридной интеллектуальной многоагентной системы с самоорганизацией 3) агенты поиска решения - специализированные агенты, имеющие знания о предметной области и использующие муравьиный алгоритм для решения поставленных перед ними подзадач;
4) агент-посредник отслеживает имена, модели и возможности зарегистрированных агентов интеллектуальных технологий. Агенты обращаются к нему, чтобы узнать, какой из агентов интеллектуальных технологий может помочь в решении поставленной перед ними подзадачи;
5) агенты интеллектуальных технологий в верхней части рис. 2 вместе с агентом-преобразователем реализуют гибридную составляющую ГиИМАС, комбинируя разнородные знания, и предоставляют луслуги агентам с использованием следующих моделей и алгоритмов: алгебраических уравнений для описания причинно-следственных связей концептов предметной области; метода Монте-Карло; продукционной экспертной системы с рассуждениями в прямом направлении; алгоритма нечеткого вывода Мамдани;
6) модель предметной области - семантическая сеть, основа взаимодействия агентов, построена по концептуальной модели СТЛЗ. Агенты интерпретируют смысл получаемых сообщений на этой модели.
Анализ предложенной структуры ГиИМАС с самоорганизацией (рис. 2) и архитектур его агентов показал, что они полностью соответствуют модели ГиИМАС с самоорганизацией на основе анализа целей агентов (5) - (11) и реализуемы на одном из специальных средств разработки многоагентных систем:
Tryllian Agent Development Kit, AnyLogic, JACK, Java Agent Development Framework (JADE), Multi Agent Development Kit, NetLogo. Для разработки выбрана среда JADE, как соответствующая спецификации FIPA, свободно распространяемая система, содержащая средства отладки и развертывания, позволяющая создавать кроссплатформенные приложения.
Разработанный ПП ТРАНСМАР состоит из 57 модулей, разбитых на три пакета: agents - девять модулей, описывающих агентов ГиИМАС; interface - пять модулей пользовательского интерфейса интерфейсного агента;
ontology - 43 модуля, обслуживающие модель предметной области. Общий объем исходного кода превысил девять тысяч строк.
Для организации функционирования человеко-машинной системы с целью автоматизированного решения СТЛЗ разработана методика, как логически упорядоченная и целенаправленная последовательность действий человекомашинной системы управления (рис. 3).
Рис. 3. Методика действий пользователя по решению СТЛЗ с использованием ПП ТРАНСМАР В пятой главе Исследование явлений и процессов коллективного принятия решений в программном продукте ТРАНСМАР на примере сложной транспортно-логистической задачи ставятся цели, задачи, рассматривается организация лабораторных экспериментов, оцениваются экономические показатели практического использования ПП ТРАНСМАР.
Сформулированы следующие цели экспериментов:
1) проверить в лаборатории работоспособность ПП ТРАНСМАР, оценить технико-эксплуатационные показатели автоматизированного решения СТЛЗ;
2) сравнить качество решений СТЛЗ, предлагаемых ЭВМ, с результатами экспертов, принимающих решения на практике;
3) исследовать на компьютерной модели ситуации решения СТЛЗ, и установить условия возникновения синергетического эффекта, когда общее коллективное решение оказывается качественно лучше частных решений экспертов;
4) по результатам компьютерного моделирования коллективных решений извлечь знания для подготовки и совершенствования деятельности ЛПР в СППР на транспорте;
5) рассчитать оценки экономических показателей автоматизированного решения сложных задач с использованием ПП ТРАНСМАР в условиях опытной и промышленной эксплуатации.
Эксперименты выполнялись для СТЛЗ (табл. 2), сформулированной в гл. 2. Выходные данные: совокупность маршрутов доставки грузов (по одному на транспортное средство) и ее параметры: стоимость, длительность, надежность и вероятность опоздания, сводный критерий качества маршрута (среднее значение нечеткой цели АПР). Исходные данные СТЛЗ: 1) запросы клиентов на доставку грузов (наименование, количество товара, временной интервал его доставки); 2) сведения о дорогах к клиентам (протяженность, загруженность, качество); 3) паспортные данные транспортных средств (расход горючесмазочных материалов, грузоподъемность и т.п.); 4) сведения о графиках работы и заработной плате персонала (водителей и грузчиков); 5) информация о перевозимом грузе (вес, габариты, хрупкость и т.п.).
Таблица 2. Количественные параметры тестируемых СТЛЗ Задача Количество Количество Количество Количество Количество клиентов дорог водителей грузчиков транспортных средств СТЛЗ_10 10 75 3 3 СТЛЗ_15 15 240 5 5 СТЛЗ_20 20 420 5 5 СТЛЗ_25 25 650 9 9 СТЛЗ_30 30 377 6 6 Исследовались три архитектуры ГиИМАС (табл. 3).
Таблица 3. Оценки архитектур ГиИМАС Архитектура Параметры маршрута Агент, прини- Агент поиска Агент поиска Агент поиска Агент поиска мающий решения решения 1 решения 2 решения 3 решения ст, дл, ве(min), ст, дл, ве(min), ст, дл, ве(min), ст, дл, ве(min), ст, дл, ве(min), org1 ORGcoop на(max) на(max) на(max) на(max) на(max) ст(min) дл(min) на(max) ве(min) org2 ORGneut ст, дл, ве(min), на(max) ст, дл, ве(min), ст(min), дл(max) ст(max), дл (min) на(max), ве(max) на(min), ве(min) org3 ORGcomp на(max) Обозначения: ст - стоимость; дл - длительность; на - надежность; ве - вероятность опоздания В общей сложности для каждой архитектуры (табл. 3) и каждой задачи (табл. 2) проведено по сто вычислительных экспериментов на ПЭВМ со следующими характеристиками: процессор - Intel Core 2 Duo 2,4 ГГц, оперативная память - 2 Гб, операционная система - Microsoft Windows XP Professional.
В ходе экспериментов установлено следующее.
ПП ТРАНСМАР версии 1.1 работоспособен, его технико-эксплуатационные характеристики: занимаемая память - от 0,2 до 1,5 Гб, время решения тестовой задачи от 2 до 30 мин, при загрузке процессора в среднем 95%; подготовка исходных данных от 5 до 30 мин. Эти показатели лучше, чем у ГиИС, решавшей СТЛЗ со сложностью моделирования q (3, 2) в ранних работах автора. Сравнение ГиИМАС и аналогичной ГиИС для решения СТЛЗ показало, что моделирование эффекта самоорганизации СППР в ГиИМАС позволило динамически синтезировать метод решения сложных задач на основе базовых методов-знаний агентов: 1) при решении СТЛЗ вырабатывается релевантный ей метод, что повышает качество решений; 2) стало возможным решать СТЛЗ с более высокими оценками сложности моделирования; 3) сокращается трудоемкость проекта за счет отказа от настройки межагентных связей. Разработанная методика поддерживается системой управления ПП ТРАНСМАР, легко усваивается персоналом, позволяя эффективно использовать ПП на практике.
Качество решений оценивалось по объективным показателям и субъективно экспертами. Для этого с каждой задачей для каждого класса архитектуры ГиИМАС проведено по сто вычислительных экспериментов. Одна из графических зависимостей, показывающая причинно-следственную связь числа ситуаций (в процентах), в которых возникает синергетический эффект и как следствие коллективное решение (решение ЛПР) оказывается лучшим, чем любое индивидуальное решении эксперта от количества клиентов, показана на рис. 4.
Для каждой задачи и архитектуры ГиИМАС, а также для архитектуры ГиИМАС без взаимодействия (агенты не обмениваются индивидуальными решениями) построены графические зависимости среднего значения цели агента, принимающего решения, средних значений стоимости, длительности, надежности, вероятности опоздания для маршрутов от числа клиентов. Анализ графических зависимостей показал высокое качество маршрутов, рекомендуемых ПП ТРАНСМАР, что подтверждено и экспертами.
Проведенные эксперименты позволили получить новые знания о методах работы ЛПР по управлению работой коллектива экспертов, которые чрезвычайно сложно получить применением известных методов приобретения знаний.
Рис. 4. Графическая зависимость причинно-следственной связи числа ситуаций, когда коллективное решение лучше любого индивидуального, от количества клиентов Разработка, внедрение и эксплуатация ПП ТРАНСМАР сопровождались технико-экономическими показателями, приведенными в табл. 4.
Таблица 4. Оценки экономических показателей в результате внедрения ПП ТРАНСМАР Показатель Значение до Значение после Процент внедрения внедрения изменения Средняя суммарная себестоимость доставки в день, руб. 14923,15 13784,61 7,Средняя суммарная длительность доставки в день, ч 62,4 59,2 5,Среднее число опозданий к клиентам в день, шт. 7,6 6,3 17,Среднее число обслуженных клиентов в день, шт. 78,2 80,8 3,Средняя себестоимость доставки в расчете на одного 190,83 170,6 10,клиента, руб.
Среднее время построения маршрутов в день, ч 3,8 2,6 31,Рассчитаны экономическая эффективность и срок окупаемости ПП ТРАНСМАР. Определены стоимость разработки Цпп = 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) Кириков И.А., Колесников А.В., Листопад С.В. Моделирование самоорганизации групп интеллектуальных агентов в зависимости от степени их взаимодействия // Информатика и её применения. - Т. 3, Вып. 4. - М., 2009. - С. 76 - 86 (личный вклад - разработка подхода к созданию интеллектуальной СППР с самоорганизацией).
2) Кириков И.А., Колесников А.В., Листопад С.В. Исследование эффекта самоорганизации в компьютерных системах поддержки принятия решения на примере многоагентных систем // Вестник Российского государственного университета им. Иммануила Канта. - Вып. 10: Сер. Физико-математические науки. - Калининград: Изд-во РГУ им. И. Канта, 2010. - С. 79 - 90 (личный вклад - разработка модели самоорганизации СППР на основе анализа степени взаимодействия участников, результаты вычислительных экспериментов).
Коллективная монография 3) Колесников А.В., Кириков И.А., Листопад С.В., Румовская С.Б., Доманицкий А.А. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем / Под ред. А.В. Колесникова. - М.: ИПИ РАН, 2011. - 295 с. (личный вклад - обзор постановок траспортнологистических задач, в том числе задачи коммивояжера, методов их решения, разработка метода решения СТЛЗ коллективом интеллектуальных агентов).
Статьи, тезисы докладов 4) Листопад С.В. Решение сложной практической задачи коммивояжера методами гибридных интеллектуальных систем // Искусственный интеллект: философия, методология, инновации. Материалы 2-ой международной молодежной конференции. Санкт-Петербург, 15-17 ноября 2007 г. - СПб., 2007. - С. 199Ц201.
5) Листопад С.В. Философско-методологический анализ синергетического эффекта в симбиозе интеллектуальности и реактивности в системах искусственного интеллекта // Образование, наука и инженерная деятельность в социокультурном пространстве эксклавного региона: история, актуальные проблемы, перспективы развития / ФГОУ ВПО КГТУ; гл. ред. В.В. Брюханов. - Калининград, 2007. - С. 51 - 53.
6) Kolesnikov A.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) Колесников А.В., Листопад С.В. Исследование отношений самоорганизации в коллективах интеллектуальных агентов // Искусственный интеллект: философия, методология, инновации. Материалы III Всероссийской конференции студентов, аспирантов и молодых ученых, МИРЭА / Под ред. Д.И. Дубровского и Е.А.Никитиной. - М.: Связь-Принт, 2009. - С. 18 - 20. (личный вклад - исследование самоорганизации коллектива интеллектуальных агентов).
8) Колесников А.В., Листопад С.В. Метод оценки степени сплоченности коллектива интеллектуальных агентов, принимающих решения // Труды VII юбилейной международной научной конференции Инновации в науке и образовании-2009, Ч. 2. - Калининград: КГТУ, 2009. - С. 175 - 177 (личный вклад - разработка меры сходства нечетких целей агентов).
9) Колесников А.В., Листопад С.В. Метод оценки степени взаимодействия интеллектуальных агентов в компьютерных системах поддержки принятия решений // Известия КГТУ. - 2010. - № 17: Материалы VII Международной научной конференции Инновации в науке и образовании-2009. - С. 166 - 170 (личный вклад - разработка метода идентификации типа архитектуры многоагентной системы на основе анализа целей агентов).
10) Кириков И.А., Колесников А.В., Листопад С.В. Моделирование процессов самоорганизации в коллективах интеллектуальных агентов // Материалы IV Всероссийской конференции студентов, аспирантов и молодых учёных Искусственный интеллект: философия, методология, инновации. - Ч. 1. - М.: Радио и связь, 2010. - С. 9 - 11 (личный вклад - разработка модели самоорганизации коллектива интеллектуальных агентов).
Авторефераты по всем темам >>
Авторефераты по техническим специальностям