Диссертация (Агентная модель поведения толпы в условиях чрезвычайной ситуации для оценки интенсивности фронта выходного потока), страница 7

siti 6= 0, определение vi,new базируется не на максимальной скорости ходьбы vi,max, а на максимальной скорости бега v̂i,max.Функция siti (t) определяется следующим образом (см. рис. 1.7)0, 3,siti (t) =2, 1,еслиеслиеслиесли0 ≤ t < t∗ или t ≥ t∗3,i;t∗ ≤ t < t∗1,i ;t∗1,i ≤ t < t∗2,i;t∗2,i ≤ t < t∗3,i,где t∗2,i = t∗ + κ2 (t∗1,i − t∗ ), t∗3,i = t∗ + κ3 (t∗1,i − t∗ ), а t∗1,i – функция от disti,expl итакже носит скачкообразный характер, имеющий следующий видt∗1,i0,=∞, ∗t + κ1 e−(disti,expl −ε1 ) ,siti (t)если 0 ≤ disti,expl ≤ ε0 ;если ε0 < disti,expl ≤ ε1 ;если disti,expl > ε1.32100t∗t∗1,it∗2,it∗3,itРисунок 1.7 — График зависимость siti (t) от времени.Стресс, вызванный экстремальной ситуацией, провоцирует в агенте потерю ориентации на выход и переключение внимания на перемещения окружающих агентов.

Другими словами, в случае ЧС агент в меньшей степени ориентируется на собственное мнение о местоположении выхода, а в большей на динамику толпы. Поэтому точка выхода агента продолжается определяться согласносистеме (1.1) только, если выход находится в непосредственной зоне видимостиагента. Для всех остальных агентов имеет место функция распределения D ве~ i в случае неорироятности ориентации на положение выхода. Сам же вектор Dентированности агента на выход вычисляется как взвешаное среднее векторов40d~j окружающих агентов в соответствующем подсекторе, т.е.N~ =PD̃Iij d~j e−γexit k~ri,new −~rj k,ij=1~D̃i~Di =.~kD̃i k1.4Разработка алгоритма эволюционной кластеризации динамики толпыдля снижения размерности задачиС целью выявления устойчивых групп агентов в основную модель былимпортирован программный пакет динамической кластеризации.

В каждый момент модельного времени на множестве всех агентов проводится кластеризацияодновременно по трем алгоритмам [2; 62; 77]:1. Метод k-средних (k-means++).2. Иерархический метод.3. Метод нечеткой кластеризации C-средних (Fuzzy C-means).Ввиду того, что для первого и третьего алгоритмов в качестве входного параметра выступает количество кластеров, чье значение, с учетом частоты проведенияанализа и вариативности количества агентов и геометрии активного пространства, не поддается никакой оценке, то для вычисления оптимального количествакластеров использовался известный критерий компактности [66]:1nS(U,c) =c PnPi=1 k=1µ2ik kxk − vi k2min kvi − vj k2,(1.9)i,jc = arg min{min S(U,c)},cΩc(1.10)где U – множество всех агентов, i,j – индекс кластеров, k – индекс агентов вкластере, µik – вероятность принадлежности k-ого агента i-ому кластеру, xk –координата k-ого агента, vi – координата центра i-ого кластера, Ωc – всевозможные разбиения U на c кластеров.41С учетом высокой степени перестроения кластеров (распад имеющихсякластеров и соединения в новые), а также максимального “правдоподобия” в качестве основного алгоритма был выбран алгоритм нечеткой кластеризации (см.рис.

1.8). Среди исследуемых характеристик кластерного анализа отдельно стоитРисунок 1.8 — Пример кластеризации.отметить:– Динамика количества кластеров.– Динамика центров кластеров.– Динамика диаметров кластеров.– Количество агентов кластера.Также важно отразить предпочтения агента относительно различных кластеров:– Мера принадлежности агента к кластеру.– Частота выбытия и примыкания к кластеру.Также необходимо отметить, что оценки плотности и диаметров кластеров играют важную роль в процессе регистрации появления эффекта турбулентности идальнейшего развития волн сжатий. Именно кластерный анализ рассматривается автором как основной инструмент дальнейшего анализа и выявления условийкак возникновения, так и разрушения волн сжатия, которые постоянно наблюдаются в процессе экспериментов.

Помимо этого проводимый кластерный анализдает оценки локализации крупных скоплений людей, что позволит в дальнейшемоценить момент максимальной интенсивности на “фронте выхода”.421.4.1Модификация алгоритма нечеткой кластеризацииАлгоритм нечеткой кластеризации Fuzzy C-means является широко используемым подходом к проблеме категоризации наблюдаемых объектам по признакам. В отличие от четких алгоритмов, алгоритм Fuzzy C-means не относит объектоднозначно к какому-нибудь кластеру, а сопоставляет каждому кластеру вероятность отнесения к нему наблюдаемых объектов, формируя, так называемую,матрицу принадлежности. Таким образом, на каждом шаге алгоритм каждыйобъект одновременно относится ко всем кластерам.Впервые данный алгоритм был предложен в работе [92], далее развит в работе [68].

Окончательная форма была представлена в работе [61], а доказательство сходимости – в монографии [62]. Ниже идет описание шагов алгоритма.Исходной информацией для кластеризации является матрица наблюденийl×nx11 x12 . . . x1n x21 x22 . . . x2n ,X=...xl1 xl2 . . .

xlnгде l – число объектов, n — число признаков (наблюдений) для каждого объекта(в нашем случае – координаты).Задача кластеризации состоит в разбиении множества объектов на группы (кластеры) “похожих” между собой объектов. В n-мерном метрическом пространстве признаков мерой “сходства” двух объектов будем считать расстояниемежду ними.Кластерная структура задаётся матрицей принадлежности (c × l матрица):m11 m12 m21 m22M =mc1 mc2. . . m1l. . .

m2l ,.... . . mclгде mij – степень принадлежности j-го элемента i-му кластеру.Отметим, что матрица принадлежности должна удовлетворять следующимусловиям:431. mij ∈ [0,1], i = 1,c, j = 1,l,cP2.mij = 1, j = 1,l, то есть каждый объект должен быть распределёнi=1между всеми кластерами,lP3. 0 <mij < l, то есть ни один кластер не должен быть пустым илиj=1содержать все элементы.Для оценки качества разбиения используется критерий разброса, показывающий сумму расстояний от объектов до центров кластеров с соответствующимистепенями принадлежности:c XlXJ=(mij )w d(vi,xj ),(1.11)i=1 j=1где d(vi,xj ) – евклидово расстояние между j-м объектом xj = (xj1, xj2, .

. . , xjn)и i-м центром кластера vi = (vi1, vi2, . . . , vin), w ∈ (1,∞) – экспоненциальныйвес, определяющий нечёткость, размытость кластеров.v11 v12 v21 v22V =vc1 vc2. . . v1n. . . v2n.... . . vcn– c × n матрица координат центров кластеров, элементы которой вычисляютсяпо формулеlP(mij )w xjkj=1vik =, k = 1,n.(1.12)lP(mij )wj=1Задачей является нахождение матрицы M, минимизирующей критерий J.Для этого используется алгоритм нечётких C-средних, в основе которого лежитметод множителей Лагранжа. Он позволяет найти локальный оптимум, поэтомудля различных запусков могут получиться разные результаты.На первом шаге матрица принадлежностей M, удовлетворяющая условиям 1-3, генерируется случайным образом.

Далее запускается итерационный процесс вычисления центров кластеров и пересчёта элементов матрицы степеней44принадлежности:mij =2(dij ) w−11cP1при dij > 0 и mkj =2(1, k = iпри dij = 0, (1.13)0, k =6 iw−1k=1 (dkj )где dij = d(vi,xj ) для i = 1,c,j = 1,l.Вычисления продолжаются до тех пор, пока изменение матрицы M, характеризующееся величиной kM − M ∗ k2, где M ∗ – матрица на предыдущейитерации, не станет меньше заранее заданного параметра остановки ε.Остановимся на выборе значения w — экспоненциального веса.

Чем больше это значение, тем матрица принадлежности более размазанная и при w → ∞элементы примут вид mij = 1c , что является плохим решением, так как всеобъекты с одинаковой степенью распределены по всем кластерам. При w = 1алгоритм Fuzzy C-means вырождается в обычный k-means. Теоретически обоснованного правила выбора веса пока не существует, и обычно устанавливаютw = 2.Схема работы стандартного алгоритма Fuzzy C-means представлена в левойчасти на Рисунке 1.9.Необходимо отметить ключевые недостатки данного алгоритма:– Высокая степень зависимости результирующего разбиения от начальнойматрицы принадлежности.– Необходимость априорного задания числа кластеров.– Отсутствие учета специфики предметной области (динамика толпы).С целью уменьшения влияния перечисленных недостатков был разработан и имплементирован в модель модифицированный (эволюционный) алгоритм нечеткой кластеризации.

Схема работы эволюционного алгоритма FuzzyC-means представлена в правой части на Рисунке 1.9.Также как и в стандартном алгоритме кластеризации, в начале экспертнозадается экспоненциальный вес w. Далее осуществляется цикл по количествукластеров от 2 до N − 1. В рамках каждого шага цикла осуществляется работаиерархического агломеративного алгоритма кластеризации с расстоянием Уорда[95]|S||P | 2 X p X s R(P,S) =ρ,,|S| + |P ||P ||S|p∈Ps∈S45Рисунок 1.9 — Схема алгоритмов нечеткой кластеризации.где p ∈ P – элементы кластера P , s ∈ S – элементы кластера S, | · | – число элементов в кластере, ρ(·,·) – длина наименьшего пути с учетом наличияпрепятствий.