Содержание к диссертации
Введение
1 Анализ задач, методов, моделей и средств моделирования поведения интеллектуальных агентов14
1.1 Классификация интеллектуальных агентов, анализ типов их взаимодействия 14
1.2 Анализ задач и методов моделирования поведения интеллектуальных агентов 20
1.3 Анализ нечётких ситуационных сетей для моделирования ситуативного поведения интеллектуальных агентов 28
1.4 Постановка задачи исследования 33
1.5 Выводы по главе 35
2 Разработка адаптивных нечётких ситуационных сетей и методов моделирования коллективного и индивидуального поведения интеллектуальных агентов на их основе 37
2.1 Адаптивные нечёткие ситуационные сети и способы их построения 37
2.1.1 Адаптивные нечёткие ситуационные сети 37
2.1.2 Пример адаптивной нечёткой ситуационной сети
2.1.2 Способ адаптации адаптивных нечетких ситуационных сетей 53
2.1.3 Способ прямого построения адаптивных нечётких ситуационных сетей 57
2.1.4 Способ обратного построения адаптивных нечётких ситуационных сетей
2.2 Метод моделирования индивидуального поведения интеллектуальных агентов на основе адаптивных нечётких ситуационных сетей 66
2.3 Метод моделирования коллективного поведения интеллектуальных агентов на основе адаптивных нечётких ситуационных сетей 73
2.4 Выводы по главе 83
3 Разработка алгоритмов и программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов на основе адаптивных нечётких ситуационных сетей 86
3.1 Структура программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов на основе адаптивных нечётких ситуационных сетей 86
3.2 Описание разработанных алгоритмов
3.2.1 Алгоритм способа прямого построения адаптивной нечёткой ситуационной сети 90
3.2.2 Алгоритм адаптации АНСС 92
3.2.3 Алгоритм моделирования индивидуального поведения интеллектуальных агентов 94
3.2.4 Алгоритм поиска и идентификации текущей ситуации в АНСС 95
3.2.5 Алгоритмы объединения адаптивных нечётких ситуационных сетей
3.3 Моделирование динамики поведения агентов 97
3.4 Разработка программных технологий обработки и хранения информации 99
3.5 Разработка интерфейса программных средств 101
3.6 Выводы по главе 107
4 Оценка качества принятия решений на основе разработанных программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов 108
4.1 Моделирование поведения интеллектуальных агентов на примере решения логистических задач 108
4.2 Оценка качества принятия решений с использованием разработанных программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов 120
4.3 Выводы по главе 123
Заключение 124
Список использованных источников 127
- Анализ нечётких ситуационных сетей для моделирования ситуативного поведения интеллектуальных агентов
- Способ адаптации адаптивных нечетких ситуационных сетей
- Описание разработанных алгоритмов
- Оценка качества принятия решений с использованием разработанных программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов
Анализ нечётких ситуационных сетей для моделирования ситуативного поведения интеллектуальных агентов
Наиболее актуальными из перечисленных являются задачи моделирования поведения интеллектуальных агентов. Рассмотрим особенности задач моделирования поведения интеллектуальных агентов, использовав трехуровневую семантическую модель «деятельность–действие–операция» ([83]), отражающую на каждом уровне как связи между регулятивными (интенциональными, поведенческими) и морфологическими компонентами поведения агентов, так и связи между базовыми функциями поведения. В общем случае можно представить:
Деятельность = F (среда, потребности, мотивация, планирование, знания); Действие = G (деятельность, объекты, цели, стратегии, умения); Операция = Н (действие, условия, задачи, тактики, навыки), где F, G и Н – отношения «один-ко-многим». В этой модели проиллюстрированы внутренние механизмы поведения агента относительно представления внешней среды и опыта, внешней регуляции и саморегуляции. Моделирование поведения агентов может проводиться как для «вертикальных» отношений «мотивы–цели–задачи», «планы–стратегии–реакции», так и для «горизонтальных» отношений «потребности–мотивы–планы–знания», «объекты–цели– стратегии–умения», «условия–задачи–тактики–навыки».
Соответственно, и само понятие агента можно определить подмножеством из указанного набора характеристик поведения. Для реактивных агентов можно ограничиться моделированием характеристик поведения нижнего уровня и их связей с характеристиками среднего уровня. Для интеллектуальных же агентов в общем случае необходимо моделировать отношения между характеристиками верхнего уровня и их связи с характеристиками среднего уровня. Так на верхнем уровне интерпретируемые интеллектуальными агентами потребности формируют сферу мотивации, а построение планов реализации мотивов требует пополнения знаний или пересмотра убеждений агента.
Несмотря на различия в степени интеллектуальности агентов, задачи моделирования поведения агентов, как правило, сводятся к ситуативному формированию стратегии (алгоритма) поведения, т.е. последовательности действий, позволяющей из текущей ситуации (состояния агента) достичь поставленной цели (целевой ситуации).
Исходя из этого, к основным задачам моделирования ситуативного поведения интеллектуальных агентов относятся следующие: идентификация текущего состояния агента, состояний взаимодействующих с ним агентов и окружающей среды; формирование действий (управляющих решений) и последовательностей действий в зависимости от вида и ситуации(й) взаимодействия агентов и стратегий поведения; адаптация поведения агентов к изменениям условий взаимодействия с другими агентами и окружающей среды с учетом целей, ролей, степени ответственности и ресурсов.
Выполним анализ методов решения этих задач моделирования ситуативного поведения интеллектуальных агентов, основанных на моделировании или построении стратегии поведения агента.
Моделирование ситуативного поведения интеллектуальных агентов на основе продукционных моделей относится к наиболее распространенным методам. Такие модели задаются наборами продукционных правил вида: «Если Условия, То Действия» [29]. Особенностями моделирования ситуативного поведения агентов на основе таких моделей является то, что воспринимаемая агентом информация об окружающей среде и взаимодействующих агентах поступают в базы продукционных правил, по результату вывода на которых (в соответствии со сформированными целями и ситуативными оценками) задаются отдельные действия и стратегии поведения агентов [82].
Использование же нечёткого подхода при построении продукционных моделей и основанных на них методов моделирования ситуативного поведения агентов позволяет обеспечить: возможность использования разнокачественных, в том числе экспертных данных, а также представленных с помощью различных шкал; простоту представления знаний, в том числе экспертных; четкое и нечёткое лингвистическое задание параметров; возможность лингвистической интерпретации результатов; возможность представления неточности и неопределённости данных; возможность представления и моделирования нелинейности; использование в реальном масштабе времени. К ограничениям данных моделей и методов относятся: сложность экспертного формирования базы правил; сложность проверки на полноту и непротиворечивость базы правил; сложность структурной и параметрической оптимизации базы правил; отсутствие возможности автоматического приобретения знаний [27].
Нейросетевые модели, построенные по принципу организации и функционирования биологических нейронных сетей, представляют собой совокупность нейроподобных элементов, определенным образом соединенных друг с другом и с внешней средой с помощью связей, задаваемых весовыми коэффициентами [60, 71]. Основные достоинства нейросетевых моделей и основанных на них методов при моделировании ситуативного поведения интеллектуальных агентов заключаются в: возможности выявления закономерностей в данных, их обобщении; возможности представления и моделирования нелинейности; типовом подходе к решению различных задач, в том числе, к моделированию поведения агентов; способности к адаптации и обучению; возможности представления неточности и неопределённости данных; возможности моделирования поведения агентов в реальном масштабе времени. К ограничениям нейросетевых моделей и методов относятся: сложность объяснения результатов моделирования поведения; большое число циклов обучения; сложность и эвристичность формирования топологии и параметров нейросетевой модели, адекватной задаче моделирования поведения; сложность формирования представительной и непротиворечивой обучающей выборки [27].
Следует также выделить: во-первых, нейронные нечёткие сети, в которых на основе положения теории нечётких множеств осуществляется включение нечёткости в различные компоненты нейронных сетей (элементы структуры и механизмов обучения и функционирования); во-вторых, гибридные нечётко-нейронные сети, в которых реализуется интеграция нечётких и нейросетевых моделей в единую модель на уровне решаемых задач; в-третьих, нечёткие нейронные продукционные сети, в которых нейросетевая технология используется в качестве инструмента для реализации компонентов нечётких продукционных моделей.
Способ адаптации адаптивных нечетких ситуационных сетей
Пусть в результате применения некоторого управляющего решения г/ нечёткое множество pi = {(jUPj(Tf )/Tf )},/є{1,2,...,/},jє{1,2,...,Ji}, пред 45 ставляющее значение изменяемого ситуационного признака Pt, изменилось следующим образом: р\ = {(//-, (Tf)/ Tf)}, / є {1,2,..., /}, jє {1,2,..., Jt}.
Тогда результирующее изменение Ар. этого признака можно представить в виде пары нечётких множеств (для решения проблемы совместного учета его положительных и отрицательных изменений): Арг+ = Uu (Tf) / Tf )},/ є {1,2,...,/}, у є {1,2,...,./.} - для учета положительных изменений значений признака Pt; А/?7 = (//д__(Г/)/Г/)},/є {1,2,...,/}, у є {1,2,..., Jt) - для учета отрицательных изменений значений признака Pt.
Затем отдельно определяются нечёткие множества, задающие положительные Ap+z и отрицательные Ар изменения нечёткого признака р2 с учетом влияния на него признака pt: АР:=АР:ОЫ(П = АТП/Т-)}, Ар Ар-оІпҐ ф тр/тр)}. Тогда в результате воздействия на признак pt управляющего решения rf , нечёткое множество p z, характеризующее измененное значение зависимого признака р2, изменится в соответствии с выражением: p z = (min(l, max(o, iph (Tf) + p + (Tf) - p _ (Tf ))))/Tf)}, j є {1,2,..., Jz). Аналогичным образом учитывается влияние признака Pt при воздействии на него управляющего решения на другие ситуационные признаки из Р.
Учет отношений влияния нечётких признаков друг на друга на основе предлагаемого способа позволяет повысить гибкость создания АНСС и упростить процедуры их построения и адаптивного изменения при моделировании поведения агентов, в отличие от способа из работы [67], где это влияние учиты 46 вается лишь косвенным образом за счет трудоемких процедур при реализации свойства -локальности управляющих решений.
Множество ролей Roles = {Role},w = 1,...,W, различаются доступом к различным совокупностям нечётких признаков, ситуаций, управляющих решений, переходов.
Соответствие между ролями и перечисленными компонентами АНСС может устанавливаться декларативно, то есть непосредственным назначением. Однако в этом случае требуется проверка на полноту и непротиворечивость такого соответствия, вследствие того, что соответствие ситуационных признаков (значений ситуационных признаков) фактически обуславливает соответствие этих ролей и для тех нечётких ситуаций, которые образуются для этих ситуационных признаков (значений ситуационных признаков).
Если одному агенту назначается несколько ролей, тогда относительно него объединяются совокупности соответствующих этим ролям: признаков, ситуаций, управляющих решений, переходов.
Правила адаптации АНСС Adapt применяется на этапах построения и использования сети (см. подраздел 2.1.3).
Множество путей (маршрутов) между ситуациями представляет собой множество совокупностей путей между каждой парой нечётких ситуаций в результате выполнения соответствующих последовательностей управляющих решений: Paths = {Path(Satr,s ars)}, где Path(Sc"s,ars) - совокупность путей между текущей scur и целевой starg ситуациями, scur, starg GS. Некоторый b-й путь между ситуациями scur и starg определяется для каждой роли Rolew є Roles следующим образом: b,Rolew : р fj(Scur,-barg) 7. П Scur Starg гшпЪ ( cur, tb ,..., V, Atarg), U 1,., D , где B – число возможных путей между ситуациями scur и st Переход по маршруту из исходной нечёткой ситуации sm в смежную с ней ситуацию sfin осуществляется, во-первых, при наличии управляющего перехода и между этими ситуациями и, во-вторых, при воздействии на исходную ситу-ацию sm соответствующего этому переходу управляющего решения г/ .
Воздействие же управляющего решения rPi на нечёткую ситуацию sm сводится к операции нечёткой композиции соответствующего этой ситуации нечёткого множества 2-го уровня sm и нечёткого отношения FkPi, характеризующего данное управляющее решение. После чего полученный результат в виде нечёткого множества 2-го уровня S (характеризующего промежуточную ситуацию s ) сопоставляется с нечётким множеством 2-го уровня sfin (представляющим нечёткую ситуацию sfm) на основе, например, операции нечёткого равенства или нечёткой g-q общности (для случая различного числа признаков). И при превышении некоторого порогового значения делается вывод о переходе из ситуации sm в ситуацию sfin :
После вывода о переходе в новую ситуацию может быть выполнено так называемое «контрастирование» ситуации, т.е. присвоение показателям текущей ситуации эталонных значений показателей типовой ситуации sfm .
Могут быть рассмотрены следующие случаи построения маршрутов: для случая уже сформированной сети; в процессе построения сети; в случае «распределения» фрагментов сети по ролям при изменении (до полнении, сокращении) структуры сети (ситуациями, управляющими ре шениями, управляющими переходами), если для какой-либо роли отсут ствует возможность достижения целевой(ых) ситуации(й). Маршруты строятся для каждого агента. При этом на построение марш рутов влияют следующие факторы:
Описание разработанных алгоритмов
Веса управляющих переходов непосредственно не используются для описания нечётких ситуаций и могут трактоваться как показатели, которые должны быть изменены для перехода из одной ситуации в другую, либо которые выражают эффект от такого перехода. В качестве них могут выступать, например, время перехода из одного состояния другое состояние, затраты ресурсов на этот переход, выигрыш от перехода и т.п. Например, в случае оценки времени и затрачиваемых ресурсов следует выбирать маршрут с минимальным весом, а для минимизации рисков при достижении целевой ситуации требуется искать маршрут в сети с максимальным суммарным весом.
Специфика моделирования ситуативного поведения агентов также оказывают влияние на выбор критерия поиска и формирование соответствующей ей последовательности управляющих решений в АНСС. Примером могут служить ограничения для какой-либо роли, для которой суммарный вес управляющих переходов до целевой ситуации не должен превышать определенного значения. И при выборе последовательности управляющих решений должно учитываться это ограничение [16]. Следующим шагом после задания текущей и целевой ситуаций, критерия поиска и выбора последовательности управляющих решений, является собственно поиск маршрутов на графе сети между текущей и целевой ситуациями. Поиск маршрутов может осуществляться с помощью эффективных алгоритмов поиска путей на графе: волнового алгоритма, алгоритма Дейкстры, алгоритма Флойда– Уоршелла, алгоритма Беллмана–Форда, переборного алгоритма. Выбор алгоритма необходимо осуществлять с учетом решаемой задачи моделирования ситуативного поведения агента и специфики представления параметров [11, 16].
Вследствие этих особенностей типовые поисковые алгоритмы практически неприменимы для решения поставленной поисковой задачи на АНСС. Поэтому, как правило, требуется модифицировать поисковые алгоритмы [35].
Требуется учесть возможность того, что на графе АНСС может быть не найдено ни одного маршрута (и последовательности управляющих решений), удовлетворяющего поставленной задаче и условиям. В этом случае используется предлагаемый способ адаптации АНСС, суть которого заключается в добавлении в АНСС новых ситуаций и переходов в них из уже существующих ситуаций и переходов сети. Для этого можно использовать оценку g-q- общности нечётких ситуаций. Недостижимую целевую ситуацию в этом случае нужно сравнить со всеми ситуациями сети, используя g-q-общность. В результате каждого такого сравнения формируется множество Pqi (где i – номер ситуации сети) признаков, по которым данная i-я ситуация отличается от целевой. После этих сопоставлений в качестве ближайшей к целевой выбирается ситуация, мощность Pqi соответствующего множества которой минимальна. Эта ситуация и будет являться ближайшей к целевой. Затем из неё строится путь к целевой ситуации на основе способа прямого или обратного построения АНСС (см. подраздел 2.1) с учетом условий и критерия поиска. В полученной таким образом сети будут иметься маршруты из текущей в целевую ситуацию [38].
Для ускорения процедуры поиска кратчайшие пути в рамках заданных критерия поиска Cr и ограничений Ogr сохраняются в множестве Paths, которое формируется при построении АНСС. В дальнейшем при использовании АНСС для моделирования поведения агентов выполняется только пересчет этих путей в случае изменения самой АНСС (при изменении, добавлении или удалении управляющих переходов U) или критерия поиска Cr, или ограничений Ogr, а также при изменении ролей агента.
На этапе использования поиск маршрута будет заключаться в его выборе из множества Paths по текущей и целевой ситуациям. Выбор маршрута из Paths в этом случае будет характеризоваться заведомо меньшим временем, чем это необходимо на поиск маршрута в графе.
Непосредственный поиск и выбор путей в АНСС может осуществляться на основе поисковых алгоритмов в ориентированных взвешенных графах, например, Форда, Мура, Беллмана и Флойда. Для изменения множества Paths при добавлении нового управляющего перехода в АНСС можно использовать либо алгоритм Флойда, либо выполнение поиска k раз (по количеству возможных сочетаний ситуаций АНСС) с помощью алгоритма Форда, Мура, Беллмана. Но затратность поиска с использованием алгоритма Флойда составляет O3, тогда как аналогичный показатель для алгоритма Форда, Мура, Беллмана – O4. Следовательно, для пересчета расстояний между ситуациями АНСС (вершинами графа) целесообразно использовать алгоритм Флойда [35].
Таким образом, разработанный метод моделирования индивидуального поведения интеллектуальных агентов основывается на АНСС и учитывает особенности поведения как самих агентов, так и специфику изменяющейся среды, в которой они функционируют.
Оценка качества принятия решений с использованием разработанных программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов
Качество принятия решений при выполнении логистических задач с использованием разработанных программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов оценивалось с точки зрения: идентификации текущей и/или целевой ситуации; поиск и выбор маршрутов (соответствующих последовательностям управляющих решений) для перехода из текущих в целевые ситуации в соответствии с различными критериями.
При идентификации текущей и/или целевой ситуации качество принятия решений оценивалось с точки зрения нахождения ситуации, ближайшей к текущей ситуации, при заданном пороге нечёткого равенства ситуаций о в соответствии с показателем (показатель Kid).
Для задачи поиска и выбора путей для достижения целевых ситуаций из текущих качество решений оценивалось с точки зрения следующих критериальных показателей: Kpos - максимальное число найденных маршрутов между текущими и целевыми ситуациями; min/– минимальная длина пути (последовательности управляющих переходов) между текущими и целевыми ситуациями; Kavgh- средний вес пути между текущими и целевыми ситуациями; Kminh - минимальный вес пути между текущими и целевыми ситуациями.
Качество принятия решений при выполнении логистических задач выполнялась на основе моделирования индивидуального и коллективного поведения интеллектуальных агентов в соответствии с примером, представленным в подразделе 4.1.
Моделирование индивидуального поведения проводилась на примере агентов: «Директор предприятия», «Начальник производства». При этом все их взаимодействия с другими агентами не учитывались и исключались из рассмотрения. Для каждого агента были решены задачи идентификации текущей ситуации и целевых ситуаций (по показателю Kid ), а также поиска и выбора маршрутов (по показателям Kpos , Kminl , Kavgh , Kminh ).
Для каждой задачи были получены оценки с использованием существующей на АО «НПП Измеритель» системы «Cur» и разработанных программных средств «ANSS». Результаты сравнительной оценки качества принятия решений для агентов «Директор предприятия» и «Начальник производства» представлены в таблице 4.19.
Результаты сравнительной оценки качества принятия решений для агентов «Директор предприятия» и «Начальник производства» Агент AKld, % AK pos , % AKminl, % AK avgh , % A minA, % «Директор предприятия» 9,4 12,2 11,0 12,6 11,3 «Начальник производства» 11,6 14,1 10,3 9,8 9,9 Использование разработанных программных средств обеспечивает повышение качества принятия решений для невзаимодействующих агентов: при идентификации текущих и целевых ситуаций - в среднем на 10,5%; при поиске и выборе маршрутов по достижению целевых ситуаций - в среднем на 11,4%.
Моделирование коллективного поведения проводилось для взаимодействующих 2-х и 3-х агентов и для различных типов взаимодействия. Причём, 122 для случая 3-х агентов моделировались, в том числе, «смешанные» взаимодействия. Результаты сравнительной оценки качества принятия решений для взаимодействующих агентов приведены в таблице 4.20. Таблица 4.20 – Результаты сравнительной оценки качества принятия решений для взаимодействующих агентов Число агентов Тип взаимодействия AKid % % % д А% % Два агента «Конкуренция» («Менеджер» – «Менеджер») 12,3 16,1 15,4 13,8 12,4 «Сотрудничество» («Менеджер» – «Кладовщик») 8,8 9Д 14,3 14,4 12,8 «Независимость» («Менеджер» – «Менеджер отдела закупок») 11,5 12,2 10,1 9,4 10,0 Три агента «Конкуренция» – «Конкуренция» («Менеджер» – «Менеджер» – «Менеджер») 14,8 17,5 14,9 13,1 15,1 «Конкуренция» – «Сотрудничество» («Менеджер» – «Менеджер» – «Кладовщик») 14,3 14,8 13,8 12,9 10,3 «Конкуренция» – «Независимость» («Менеджер» – «Менеджер» – «Менеджер отдела закупок») 13,8 12,9 11,0 10,9 11,4 «Сотрудничество» – «Сотрудничество» («Кладовщик» – «Начальник производства» – «Менеджер») 9Д 10,1 9,6 10,2 14,7 «Сотрудничество» – «Независимость» («Кладовщик» – «Начальник производства» – «Менеджер отдела закупок») 11,2 10,9 13,8 12,7 10,8 «Независимость» – «Независимость» («Менеджер отдела закупок» – Начальник производства» – «Менеджер отдела закупок») 11,6 12,4 10,4 9,6 9,5
Использование разработанных программных средств обеспечивает повышение качества принятия решений для взаимодействующих агентов: при идентификации текущих и целевых ситуаций - в среднем на 12,1%; при поиске и выборе маршрутов по достижению целевых ситуаций - в среднем на 13,5%.
Таким образом, в результате разработанные программные средства позволили повысить качество (в среднем на 11,9%) принятия логистических решений при производстве, хранении и выдаче изделий в АО «НПП Измеритель» за счет моделирования индивидуального и коллективного поведения интеллектуальных агентов при различных типах их взаимодействия.
Представлено описание моделируемых логистических процессов при производстве, хранении и выдаче изделий в АО «НПП Измеритель» (г. Смоленск), включающее состав, характеристики агентов, их количество, способы их взаимодействия. Приведено описание нечётких признаков, управляющих решений, и показаны примеры построения АНСС интеллектуальных агентов.
Созданы программные средства моделирования индивидуального и коллективного поведения интеллектуальных агентов на основе адаптивных нечётких ситуационных сетей для поддержки логистических решений, реализующие предлагаемые методы, модели и алгоритмы.
Проведены экспериментальные исследования и выполнена оценка качества принятия решений на основе использования разработанных программных средств моделирования индивидуального и коллективного поведения интеллектуальных агентов. Результаты показали, что разработанные методы, алгоритмы и программные средства позволили повысить качество принятия логистических решений при производстве, хранении и выдаче изделий в АО «НПП Измеритель» в среднем на 11,9%.