Везде
Кластеризация агентов в модели ограниченного соседства
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
Кластеризация агентов в модели ограниченного соседства
Аннотация
Код статьи
S207751800011151-5-1
DOI
10.18254/S207751800011151-5
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Акопов Андраник Сумбатович 
ORCID: 0000-0003-0627-3037
Должность: главный научный сотрудник
Аффилиация: ЦЭМИ РАН
Адрес: Российская Федерация, Москва
Бекларян Армен Левонович
ORCID: 0000-0001-5141-5140
Аффилиация: Национальный исследовательский университет «Высшая школа экономики»
Адрес: Российская Федерация, Москва
Выпуск
Том 15 Выпуск 3
Аннотация

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

Ключевые слова
модель ограниченного соседства, модель Шеллинга, агентное моделирование, кластерный анализ
Источник финансирования
Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 20-01-00002
Классификатор
Получено
30.07.2020
Дата публикации
05.09.2020
Всего подписок
25
Всего просмотров
2518
Оценка читателей
0.0 (0 голосов)
Цитировать Скачать pdf
Доступ к дополнительным сервисам
Дополнительные сервисы только на эту статью
Преимущества сервисов
100 руб. / 1.0 SU
Дополнительные сервисы на все выпуски за 2020 год
Преимущества сервисов
1200 руб. / 24.0 SU
1

Введение

Управление социально-экономическими процессами является одним из важнейших элементов в современном мире, имеющий целью рациональное использование эколого-экономических и человеческих ресурсов, а также гармонизацию социальных отношений. Помимо этого, важным является управление на уровне государств и регионов. Одним из ключевых инструментов такого управления в последние десятилетия являются методы имитационного моделирования [1]. Среди подобных методов выделяются методы системной динамики [2], а также агент-ориентированный подход [3].
2 Применение методов системной динамики основано на гипотезе о возможности принятия решений на основе усредненных значений характеристик исследуемого объекта. Подобный подход применим для систем с централизованным управлением, состояния которых не зависят от вклада отдельных индивидуумов. Вместе с тем, сложные социальные системы являются децентрализованными, а их динамика существенно зависит от коллективного поведения агентов-индивидуумов. Для изучения подобных систем применяются методы агентного моделирования. Динамика системы, при таком подходе, формируется в результате взаимодействия отдельно взятых агентов, описание характеристик которых является следствием из наблюдений в рамках реальных процессов. Основная сложность, при этом, связана с необходимостью использования значительных вычислительных мощностей, увеличивающихся с ростом количества моделируемых агентов, в том числе, применения суперкомпьютерных технологий [6].
3 При этом, современные методы машинного обучения, а также качественный скачок в эвристических методах анализа данных, например, генетические алгоритмы [7, 8], методы нечёткой кластеризации [9] и др., которые позволяют в случае их интеграции с имитационными моделями получить как детальное описание текущих состояний системы, так и исследовать будущую кластерно-ориентированную структуру пространственного распределения агентов в зависимости от характеристик среды и с учетом возможности оптимизации ее отдельных параметров.
4 В рамках подобного подхода предлагается новая агент-ориентированная модель, относящаяся к моделям класса Шеллинга [17], в которой реализуется принятие решений по выбору каждым агентом района проживания в зависимости от предпочтений по отношению к своему окружению. Изучается поведение двух групп взаимодействующих агентов, предпочитающих существование в превалирующем окружении агентов того же типа. В зависимости от начальных условий и вида кривых распределения порогов толерантности агентов разных типов, исследуются возможности перехода в состояние равновесия и возникающие при этом кластерные срезы. Модель реализована в системе имитационного моделирования AnyLogic [1].
5 Предлагаемая модель развивает ранее предложенный Шеллингом подход к изучению проблем сегрегации, возникающей в результате выбора агентами предпочтительных районов проживания, и развитый в работах, посвященных моделям толерантного поведения и популяционной динамики [4, 5, 16].
6 Цель данной статьи – исследовать влияние множественных управляющих параметров рассматриваемой системы на характеристики кластеров, формирующихся в результате индивидуального выбора каждого агента, и описывающих процессы сегрегации.
7

Модель ограниченного соседства

Предлагается подход к построению новой универсальной и многопараметрической модели сегрегации, относящейся к классу моделей Шеллинга. Рассматривается агентная модель искусственного сообщества с размещением индивидуумов в двумерном дискретном пространстве и с дискретным временем. Пространство представляет собой условный город, а каждая клетка – дом (место размещения агента). Рассматриваются агенты-индивидуумы, принадлежащие к двум различным типам, которые также обозначаются с использованием двух цветов: оранжевого и малинового. Начальное пространственное распределение агентов по городу задается случайным образом (в соответствии с равномерным распределением). При этом, количество агентов-индивидуумов меньше, чем количество домов, что обеспечивает возможность перемещения людей в двумерном пространстве (т.е. всегда есть свободные клетки). Если процент индивидуумов одного типа (цвета) среди ближайших соседей ниже определенного порогового значения, то данный агент чувствует себя некомфортно и перемещается в случайно выбранный пустой дом, в противном случае индивидуум удовлетворен и не предпринимает никаких действий (остается на месте).
8 Условием останова имитационной модели является либо достижение состояния личного комфорта («счастья») всеми агентами или достижение максимально возможного количества шагов имитационного моделирования. При этом, методы кластеризации применяются к окончательному пространственному распределению агентов каждого типа. Пороговое значение, определяющее предпочтение агентом выбора локации с окружением (соседями) того же типа является параметром данной модели. Модельное время, как и пространство размещения агентов, задается дискретно, а оценка уровня «счастья» и шаги агентов выполняются на дискретных временных интервалах. Каждый такой шаг состоит из двух внутренних действий (фаз). Вначале агент оценивает свое ближайшее окружение (8-клеточное Мурово соседство). На второй фазе агент принимает решение (перемещается или остается). Последовательные двухфазные шаги позволяют обеспечить корректную пространственную динамику для каждого агента на основе предварительной оценки окружающего его соседства. В противном случае, возникает рассогласование между оценкой агентами текущей ситуации и выбором направлений перемещения.
9 В результате подобного индивидуального поведения агентов, формируются устойчивые кластеры, описывающие процессы естественной сегрегации. Последующий кластерный анализ пространственного распределения агентов-индивидуумов выполняется на основе плотностного алгоритма DBSCAN [12]. В разработанной модели используются следующие управляющие параметры:
10
  • rows × columns – размерность дискретного пространства (по умолчанию rows =100 и columns =100);
  • numberProportion – доля ячеек, занятых агентами по отношению ко всем ячейкам дискретного пространства пространству ;
  • colorProportion – соотношение между размерами популяций агентов обоих типов ;
  • preference1 – пороговое значение для первой группы агентов (0..1). Данный параметр задается либо детерминировано или согласно бета-распределению (в этом случае параметры и распределения принимают начальные значения);
  • preference2 – пороговое значение для второй агентов (0..1). Данный параметр задается либо детерминировано или согласно бета-распределению
  • limit – максимальное количество шагов моделирования (по умолчанию limit = 50000);
  • epsilon – радиус окрестности опорной точки для алгоритма DBSCAN (по умолчанию epsilon = 1);
  • minNum – минимальное необходимое количество агентов, необходимое для формирования плотностной области в алгоритме DBSCAN (по умолчанию minNum = 4).
11 Предложенная модель была реализована в системе имитационного моделирования AnyLogic, поддерживающей методы агентного моделирования, в том числе с использованием дискретного пространства размещения агентов (рис. 1).
12

Рисунок 1. Реализация модели ограниченного соседства в AnyLogic.
13 Начальные значения основных параметров задаются с помощью интерфейса модели (Рис. 1). При этом, размерность дискретного пространства (число строк и столбцов) может быть уменьшена для снижения размерности системы, что также обосновано известной гипотезой о «гомотетичности» моделей типа Шеллинга [11], также подтверждаемой дальнейшими исследованиями. При этом, параметры применяемого алгоритма кластеризации задаются и калибруются экспертным путем.
14 Разработанная с использованием языка программирования Java, вычислительная процедура в AnyLogic включает ряд необходимых технических элементов, например, сохранение значений управляющих параметров, результатов имитационного моделирования и кластеризации в базу данных (MS SQL Server), инициализация необходимых классов и т.д. При этом, основными шагами разработанной вычислительной процедуры являются следующие:
15

1. Инициализация дискретного двумерного пространства размерностьюrows × сolumns.
16

2. Создание популяции агентов с фиксированной количественной пропорцией:

(int) (rows_columns_numberProportion)
17

3. Распределение агентов на две группы (популяции) в соответствии со следующим правилом:

randomTrue (colorProportion) ? orange : crimson
18

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

5. Оценка агентом окружающего пространства с целью определения уровня личного комфорта («счастья») на первой фазе каждого шага данного агента:
19

Agent [ ] neighbors = getNeighbors ( );

if (neighbors == null) {

happy = true;

}

else {

int nsamecolor =0;

for (Agent a : neighbors)

if ( ((Person) a).color.equals (color))

nsame color ++;

happy = nsame color >= neighbors.length_preference;
20

6. Принятие решения о пространственном перемещении на второй фазе каждого шага данного агента:

if (!happy)

jumpToRandomEmptyCell( );
21

7. Проверка критерия останова модели:

stop = true;

for (Person p : people )

if (! p.happy) {

stop = false;

break;

}

if (stop) {

finishSimulation( );

}

else {

if (getEngine( ).getStep( ) > limit) {

finishSimulation( );
22

8. Выполнение кластерного анализа для каждой группы агентов.
23 Таким образом, в предложенной имитационной модели реализуется полная синхронизация агентов-индивидуумов друг с другом и со средой в условиях псевдослучайного выбора свободной ячейки в каждый момент времени.  
24

Результаты численных исследований

Результаты кластеризации агентов в предложенной имитационной модели ограниченного соседства показаны на Рис. 2.
25

Рисунок 2. Кластеризация агентов в модели ограниченного соседства
26 Из рис. 2 (a, b) следует, что изначально случайно распределенные агенты (рис 2 (a)) в конце моделирования сгруппированы в отдельные кластеры. При этом, алгоритм кластеризации применяется к каждой группе агентов самостоятельно. Кластеризация для каждой группы агентов представлена на рисунке 2 (c, d) (черный цвет указывает на полностью сегрегированных агентов).
27 Далее были проведены вариационные эксперименты в AnyLogic (многократный прогон модели при различных значениях управляющих параметров с целью анализа чувствительности). В таблице 1 показаны выбранные диапазоны значений исследуемых параметров.
28

Таблица 1. Диапазоны допустимых значений

Параметр Минимальное значение Максимальное значение Шаг изменения
numberProportion 0,5 0,8 0,1
colorProportion 0,2 0,8 0,1
α 0,5 4 0,5
α 0,5 4 0,5
β 0,5 4 0,5
β 0,5 4 0,5
29 В ходе вариационных экспериментов было выполнено 701 055 прогонов. Для оценки плотности пространственного распределения агентов, и в целом, для анализа формулируемых кластерных паттернов, можно использовать различные числовые индикаторы, например, индекс сегрегации Дункана (DSI), который является одним из наиболее важных используемых индексов сегрегации в социальных науках [18], индекс сегрегации Фримена (FSI) [13], который позволяет оценить разброс в количестве взаимодействий между агентами различных типов с математическим ожиданием, соответствующим отсутствию сегрегации, индекс энергетической сегрегации (Energy Segregation Index (ESI)) [15]. Для определения значений подобных индексов требуется вычисление уровня отношений для каждого агента внутри заданной области, что представляет собой сложную вычислительную процедуру [10].
30 Поэтому, в данной работе, для оценки сегрегации предлагается использовать более простые характеристики, в частности, коэффициент сегрегации, полученный на основе теории перколяции [14] (т.е. теории, описывающей возникновение бесконечных связных структур (кластеров), состоящих из отдельных элементов) в следующем виде:
31 S=2N2∑cnc2 ,
32 где - общее количество агентов, - количество агентов в -ом кластере.
33 Таким образом, в модели вычисляются следующие характеристики:
34
  • success – сходимость вычислительной процедуры (логическая переменная);
  • step – количество шагов до выполнения критерия останова;
  • numberClusters – количество сформированных кластеров, рассчитываемое как для всех агентов, так и для каждой группы самостоятельно;
  • numberIsolated – количество изолированных агентов;
  • numberAvgCluster – среднее количество агентов в кластерах;
  • numberStdevCluster – стандартное отклонение количества агентов в кластерах;
  • segregation – коэффициент сегрегации, согласно формуле (1).
35 Динамика значений коэффициента сегрегации (segregation) для первой и второй группы агентов показана на рис. 3.
36

Рисунок 3. Динамика значений коэффициентов сегрегации (ось Ox является отнормированным временем).
37 Для обработки результатов имитационного моделирования использовались следующие методы статистического анализа и машинного обучения: линейная регрессия, нейронные сети (MLP, RBF, бустинг, бэггинг), деревья решений (C5.0 Decision tree, CHAID tree), логистическая регрессия, дискриминантная ступенчатая регрессия и др. Отдельно стоит отметить, что помимо анализа точных значений исследуемых характеристик, также оценивалось их бета-распределение (формируемое в результате множественных прогонов), так как такой подход позволяет качественно описать физические свойства полученных зависимостей в моделях типа Шеллинга.
38 В таблице 2 представлены некоторые результаты статического анализа для отдельных модельных характеристик, выполненные с использованием вышеупомянутых методов.
39

Таблица 2. Результаты статистического анализа

Модельные характеристики Метод и результаты анализа
Количество сформированных кластеров (numberClusters) Деревья решений CHAID, глубина - 5, 10 компонент
Параметрические оценки Обучение Тестирование
Minimum Error -45,005 -44,109
Maximum Error 46,968 40,965
Mean Error 0,0 0,03
Mean Absolute Error 6,251 6,236
Standard Deviation 8,086 8,069
Linear Correlation 0,987 0,987
Occurrences 490495 210560
Среднее количество агентов в кластерах (numberAvgCluster) Нейронная сеть MLP, 1 скрытый слой, функция активации: гиперболическая тангенс
Minimum Error -49,85 -44,474
Maximum Error 115,83 81,262
Mean Error 0,01 0,007
Mean Absolute Error 4,827 4,818
Standard Deviation 7,651 7,607
Linear Correlation 0,986 0,987
Occurrences 490495 210560
Коэффициент сегрегации (segregation) Деревья решений CHAID tree, глубина - 5, 10 компонент
Minimum Error -0,775 -0,645
Maximum Error 0,562 0,548
Mean Error 0,0 0,0
Mean Absolute Error 0,056 0,056
Standard Deviation 0,095 0,095
Linear Correlation 0,972 0,972
Occurrences 490495 210560
40 Высокий уровень предсказательной точности различных методов машинного обучения при условии достаточно большого объема как обучающей, так и проверочной выборки указывает на то, что при всей стохастичности самой модели, тем не менее, имеется ряд квази детерминированных метрик, чье конечное значение (по крайне мере, в части интервальных оценок) может быть предсказано по набору исходных параметров моделирования. Формализация перечня таких метрик, а также итоговые зависимости их значений от начальных параметров является предметом дальнейших исследований.
41

Заключение

В статье представлена разработанная агент-ориентированная модель ограниченного соседства, относящаяся к классу моделей Шеллинга. Особенностью данной многопараметрической модели, реализованной в системе AnyLogic (рис. 1), является возможность анализа сегрегационных эффектов с использованием встроенных методов кластеризации (алгоритма типа DBSCAN), а также интегрируемость с базой данных, методами статистического анализа и машинного обучения.
42 Выполнен кластерный анализ с использованием предложенной модели ограниченного соседства для двух типов агентов при различных сценарных условиях (рис. 2) и построена динамика значений коэффициента сегрегации (рис. 3). С использованием предложенной модели выполнены численные эксперименты, направленные на оценку «плотности» результирующих кластеров и оценку равномерности межкластерного распределения агентов-индивидуумов, отражающего уровень сегрегации.
43 Дальнейшие исследования будут направлены на усложнение индивидуальной способности принятия решений агентов-индивидуумов, эндогенизацию характеристик толерантности, разработку новых индикаторов для оценки сегрегации, а также реализации крупномасштабных моделей ограниченного соседства с использованием суперкомпьютерных технологий (Flame GPU).

Библиография

1. Акопов А.С. Имитационное моделирование. Учебник и практикум для академического бакалавриата. М.: Юрайт, 2014.

2. Акопов А.С., Хачатрян Н.К. Системная динамика: учебно-методическое пособие. М.: ЦЭМИ РАН, 2014.

3. Акопов А.С., Хачатрян Н.К. Агентное моделирование: учебно-методическое пособие. ЦЭМИ РАН, 2016.

4. Бреер В.В. Модели толерантного порогового поведения (от Т. Шеллинга – к М. Грановеттеру) // Проблемы управления. 2016, № 1.

5. Макаров В.Л., Бахтизин А.Р., Бекларян Г.Л., Акопов А.С., Ровенская Е.А., Стрелковский Н.В. Агентное моделирование популяционной динамики двух взаимодействующих сообществ: мигрантов и коренных жителей // Экономика и математические методы. 2020, Т. 56, № 2.

6. Макаров В.Л., Бахтизин А.Р., Бекларян Г.Л., Акопов А.С. Разработка программной платформы для крупномасштабного агент-ориентированного моделирования сложных социальных систем // Программная инженерия. 2019, Т. 10, № 1.

7. Akopov A.S., Beklaryan L.A., Thakur M., Verma D.B. Parallel multi-agent real-coded genetic algorithm for large-scale black-box single-objective optimisation // Knowledge-Based Systems. 2019, Vol. 174.

8. Akopov A.S., Beklaryan L.A. Cluster-Based Optimization of an Evacuation Process Using a Parallel Bi-Objective Real-Coded Genetic Algorithm // Cybernetics and Information Technologies. 2020, Vol. 20, No. 3.

9. Beklaryan A.L., Akopov A.S. Simulation of Agent-rescuer Behaviour in Emergency Based on Modified Fuzzy Clustering, in: AAMAS'16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. Richland: International Foundation for Autonomous Agents and Multiagent Systems, 2016. pp. 1275-1276.

10. Cortez V., Rica S. Dynamics of the Schelling social segregation model in networks // Procedia Computer Science. 2015, Vol. 61.

11. Dodson A., Elliot A.J. Schelling’s Bounded Neighbourhood Model: A systematic investigation. PhD thesis, University of York, 2014.

12. Ester M., H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise, in Proc. Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Evangelos Simoudis, 1996, pp. 226–231.

13. Freeman L. C. Segregation in social networks // Sociological Methods & Research. 1978, Vo. 6, No. 4,

14. Gauvin L., Vannimenus J., Nadal J.-P. Phase diagram of a Schelling segregation model // The European Physical Journal B. 2009, Vol. 70, No. 2

15. Goles D.N., Rica S. Dynamics and complexity of the Schelling segregation model. // Physical Review E. 2011, Vol. 83, No. 5, 056111.

16. Granovetter M. Threshold Models of Collective Behavior // AJS. 1978, Vol. 83, No. 6.

17. Schelling T.C. Dynamic models of segregation. // The Journal of Mathematical Sociology. 1971, 1 (2): 143–186.

18. Taylor C., Gorard S., Fitz J. A re-examination of segregation indices in terms of compositional invariance. // Sociology at Surrey. 2000, Vol. 30.

Комментарии

Сообщения не найдены

Написать отзыв
Перевести