Локально-параметрические алгоритмы как инструмент выбора класса мультиагентных систем

Федерации, М.: Минэкономразвития, 2008, 211 с.

2. Стратегическое управление: регион, город, предприятие/ под ред. Д.С. Львова, А.Г. Гранберга, А.П. Егоршина; ООО РАН НИМБ, М.: Экономика. 2004.

3. О республиканской целевой программе «О Программе социально-экономического развития Удмуртской Республики на 2010 - 2014 годы»: Постановление Государственного Совета УР № 350-IV от 08 дек. 2009 г.

List of references:

1. Concept of long-term social and economic development of the Russian Federation, M: Ministry of Economic Development and Trade, 2008, 211 pages.

2. Strategic management: the region, the city, the enterprise / under the editorship of the Village of D.S.Lviv, A.G.Granberg, A.P.Egorshina; JSC RAN NIMB, M: Economy. 2004.

3. About the republican target program «About the Program of social and economic development of the Udmurt Republic for 2010-2014»: The resolution of the State Council UR No. 350-IV from the 08th deck. 2009.

УДК 519.6

В.А. Гимаров

д-р техн. наук, профессор, профессор кафедры менеджмента и информационных технологий в экономике, филиал ФГБОУ ВПО «Московский энергетический институт (Национальный исследовательский университет)» в г. Смоленске

В.В. Гимаров

канд. экон. наук, доцент, доцент кафедры менеджмента и информационных технологий в экономике, филиал ФГБОУ ВПО «Московский энергетический институт (Национальный исследовательский университет)» в г. Смоленске

И. В. Иванова

аспирант кафедры менеджмента и информационных технологий в экономике, филиал ФГБОУ ВПО «Московский энергетический институт (Национальный исследовательский университет)» в г. Смоленске

ЛОКАЛЬНО-ПАРАМЕТРИЧЕСКИЕ АЛГОРИТМЫ КАК ИНСТРУМЕНТ ВЫБОРА КЛАССА МУЛЬТИАГЕНТНЫХ СИСТЕМ

Работа поддержана грантом РФФИ №12-01-00266-а

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

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

V.A. Gimarov, The Smolensk branch of the National Research Institute "Moscow Power Engineering Institute"

V.V. Gimarov, The Smolensk branch of the National Research Institute "Moscow Power Engineering Institute"

I.V. Ivanova, The Smolensk branch of the National Research Institute "Moscow Power Engineering Institute"

LOCALLY-PARAMETRIC ALGORITHMS AS A TOOL OF THE CHOICE OF THE MULTI-AGENT

SYSTEM CLASS

Abstract. The paper shows the importance of process modeling to support decision making in the management of complex open systems. An approach to the construction of hierarchical multi-agent systems, as well as a method of classification of the trajectories on the basis of locally approximating models to choose class multi-agent system.

Keywords: complex systems, simulation, multi-agent system, the classification of the trajectories that are locally-approximation model.

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

Известные на сегодняшний день способы моделирования охватывают аналитическое моделирование, аналитическое моделирование с элементами дискретно-событийного моделирования, дискретно-событийное моделирование с элементами аналитического моделирования, дискретно-событийное моделирование с элементами аналитического и/или агентного моделирования. При этом многоагентные системы (МАС) являются одним из наиболее перспективных направлений [1].

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

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

- изменения организационной структуры модели (модификация состава агентов модели и изменения более низких уровней);

- изменение модели взаимодействия агентов (новые виды связей и отношений, изменение архитектуры и характеристик агентов),

- изменение архитектуры агентов;

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

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

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

В настоящее время задача классификации, а также кластеризации траекторий, является достаточно актуальной. В ряде работ предложены различные методы для её решения на основе использования алгоритма нечеткой кластеризации с-теапэ [2]. В то же время известные подходы к использованию данного алгоритма не позволяют в полной мере учесть особенности траекторий на различных их локальных участках. Как представляется, для устранения указанного недостатка в рамках алгоритма с-теапэ может быть использован аппарат методологии локальной аппроксимации, основные положения которого изложены в работах других авторов [3, 4]. Применение процедур локальной аппроксимации для решения задачи классификации траекторий включает следующие этапы:

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

(Хк-п, Хк-(п-1),..., Хк-1, Хк, Хк+1) .

Для их построения используется следующая процедура:

1) Проведение начального эксперимента с регистрацией значений хк и формирование начальной матрицы и с числом строк, большим М.

А

2) Ввод очередного значения хк+1. Расчет прогнозируемого значения Хк+1 по соотношению:

Хt+1 = хТ • (Рт • Р)-1 • Рт • У, где Г - матрица размера М х (п +1), строками которой являются х[.

3) Проверка выполнения неравенства

Хк+1 - Хк+1

> б,

где б - заданная константа, определяющая точность модели.

В случае выполнения неравенства матрица и дополняется строкой

<xk-n,xk-(nxk-1,xk,xk+1 >. При невыполнении неравенства матрица U не изменяется.

4) Проверка выполнения условия останова (общее количество значений процесса xk, используемых для формирования U может быть как фиксированным, так и переменным); например, условием останова процедуры обучения может быть невыполнение неравенства на этапе 3 N0 раз подряд, при его невыполнении переход к п. 2

процедуры, в противном случае - переход к следующему пункту.

Заметим, что обычно нескольких таких уточняющих итераций (по подбору n, M, d) оказывается достаточно для формирования по итогам обучающего этапа матрицы U умеренного размера, при котором прогностические свойства алгоритма соответствуют допустимым.

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

2. На каждой итерации стандартного алгоритма нечетких С-средних в соответствии со следующей формулой рассчитывается значение функции принадлежности объекта i к классу j:

Ми =-1-

° ( d( X ,Vy ) I m-1

h l d (X ,Vk),

где Х - i-ый объект (траектория), Vj и Vk - центры кластеров j и k, с - число кластеров, m - степень размытости кластеров.

Выражение d(x,y) в формуле обозначает меру близости между векторами. Для её определения предлагается следующая процедура.

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

Осуществляется поиск строк баз данных, максимально близких друг к другу по значениям. Так, при использовании локальной модели вида xt+1 = c0xt-1 + ¿1xt, поиск записей будет осуществляться в соответствии со следующим выражением:

|x1+1 -x2^1 + x -x2| + |*1 -1 -x2-1| ^min.

Для найденных пар строк баз данных осуществляется построение локальных моделей xt+1 = c0 xt-1 + <31xf и рассчитываются величины Ac01, Ac11. Таким образом, мера близости двух траекторий может быть определена с помощью выражения:

N

d (X, Vj) = h (ACok +AC1k).

k=1

С помощью данной меры сходства между функциями классический алгоритм нечетких С-средних можно использовать для классификации динамических объектов. При этом расчет центров кластеров b будет осуществляться по формуле [4]:

1

' d (X ,Vj)Л ld(X,,Vk) I

M

I М•

V, = -,' = 1-P, Р - числ0 кластеров.

I (м, )m

j=1

Перерасчет значений функций принадлежности:

М, =-, 1 , ,i = 1..p, j = 1..M .

° Г d ^m-1

I Z!L

^ d

k=1 ^ dkj )

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

Список литературы:

1. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология информатика. - М.: ЭдиториалУРСС, 2002.

2. Бауман Е.В., Дорофеюк А. А. Классификационный анализ данных // Труды Международной конференции по проблемам управления. - Том 1. - М.: СИНТЕГ, 1999. - С. 62-77

3. Angstenberger L. Dynamic Fuzzy Pattern Recognition with Applications to Finance and Engineering. Boston: Kluwer Academic Publishers, 2001.

4. Дли М.И., Круглов В.В., Осокин М.В. Локально-аппроксимационные модели социально-экономических систем и процессов. - М.: Наука. Физматлит, 2000.

List of references:

1. Tarasov V.B. Of multi-agent systems for intelligent organizations: philosophy, psychology, computer science. - M.: EditorialURSS, 2002.

2. Bauman E.V., Dorofeuk A.A. Classification analysis of data // Proceedings of the International Conference on Control. - Volume 1.- М.: SINTEG, 1999. - С. 62-77

3. Angstenberger L. Dynamic Fuzzy Pattern Recognition with Applications to Finance and Engineering. Boston: Kluwer Academic Publishers, 2001.

4. Dli M.I., Kruglov V.V., Osokin M.V. Locally-approximation model of socio-economic systems and processes. - M.: Science. Fizmatlit, 2000.