close

Вход

Забыли?

вход по аккаунту

Стрыгин Андрей ААндреевич. Разработка подсистемы моделирования социальной напряженности

код для вставки
4
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
6
1 ПОСТАНОВКА ЗАДАЧИ И ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ
11
1.1 Описание предметной области
11
1.2 Постановка задачи
12
1.3 Сравнение с похожими задачами
14
1.4 Формирование требований
18
1.4 Сравнение с аналогами
19
1.6 Описание библиотеки Akka
21
1.6.1 Акторная модель
21
1.6.2 Язык программирования Scala
24
1.6.3 Реализация акторной модели в Akka
25
1.6.4 Работа акторов в акторной модели
27
2 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ, СТРУКТУРА И АЛГОРИТМЫ
29
2.1 Моделирование процессов предметной области
29
2.2 Реализация модели с использованием акторов
32
2.3 Алгоритмы первой и второй фаз моделирования
37
2.4 Описание алгоритмов обработки сообщений акторами
39
2.5 Реализация алгоритмов на Akka
44
3 ПРОВЕДЕНИЕ ЭКСПЕРИМЕНТА С ИСПОЛЬЗОВАНИЕМ
ПРОГРАММНОГО СРЕДСТВА
48
3.1 Реализация программы
48
3.2 Проведение эксперимента
49
ЗАКЛЮЧЕНИЕ
61
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
62
ПРИЛОЖЕНИЕ А – ЛИСТИНГ ПРОГРАММЫ
64
ПРИЛОЖЕНИЕ Б – ТАБЛИЦА РЕЗУЛЬТАТОВ ЭКСПЕРИМЕНТА
79
УДОСТОВЕРЯЮЩИЙ ЛИСТ
109
5
ИНФОРМАЦИОННО-ПОИСКОВАЯ ХАРАКТЕРИСТИКА
ДОКУМЕНТА НА ЭЛЕКТРОННОМ НОСИТЕЛЕ
110
6
ВВЕДЕНИЕ
В рамках данной работы рассмотрена задача разработки подсистемы
моделирования социальной напряженности. В отечественных работах под
социальной напряженностью понимается весьма широкий спектр негативных
социальных явлений, сопутствующих тем переменам, которые стали
происходить в общественно-политической сфере российского общества на
рубеже 1980–1990-х гг. Эти явления можно назвать признаками, или
симптомами социальной напряженности.
Социальная напряженность – это реакция общества на некоторые
негативные события во внешней среде. Выделяется ряд внутренних факторов
социальной напряженности.
Первым
фактором
социальной
напряженности
можно
считать
фрустрацию. Протесты и массовые акции деструктивного характера – самые
заметные симптомы социальной напряженности. Поэтому необходимо иметь
представление о том, что приводит к таким действиям. Проведение таких
акций в обществе возможно только в том случае, если в сознании индивида
сформирован образ «виноватого» в сложившейся ситуации. Это лицо должно
представлять угрозу, по мнению общества, либо препятствовать своими
действиями разрешению ситуации. Отсюда вытекает второй фактор
социальной напряженности, наличие «виноватого». Третий фактор –
готовность самих индивидов к участию в протестных действиях. При
отсутствии готовности действовать могут проявляться «психологические»
симптомы социальной напряженности, а именно депрессия, апатия,
подавленное состояние. Но готовность действовать не всегда может
проявляться в повышении гражданской активности в обществе. У индивида
может возникнуть стремление избежать создавшейся ситуации, например,
эмигрировать из страны. Кроме выше перечисленных факторов, для
возникновения
симптомов
социальной
напряженности
необходима
7
организованность общественного движения для достижения определенных
поставленных целей.
Социальная
напряженность
является
сложным
многофакторным
явлением. При исследовании таких явлений недостаточно оценивать только
симптомы. Требуется разработка концептуальной модели для выявления
факторов, лежащих в основе конкретной ситуации.
Агентная модель (АМ) – система, представленная как совокупность
автономных объектов принятия решений, называемых агентами. Каждый
агент индивидуально оценивает ситуацию и принимает решения на основе
имеющегося набора правил. Агенты могут вести себя по-разному, в
зависимости от моделируемой системы, которую они представляют.
Повторяющиеся конкурентные взаимодействия между агентами являются
особенностью АМ, именно это позволяет создать динамическую среду,
недоступную для изучения чистыми математическими методами. В наиболее
простой форме, агентная модель состоит из системы агентов и отношений
между ними. Даже простая агентно-ориентированная модель может
демонстрировать сложные модели поведения и предоставить ценную
информацию о динамике реальной системы, которую она воспроизводит.
Кроме того, агенты могут обладать способностью саморазвития, что
способствует проявлению еще более непредвиденного поведения. Сложные
AM иногда включают в себя нейронные сетей, эволюционные алгоритмы,
или другие методы обучения, позволяющие обеспечить реалистичное
обучение и адаптацию агентов. АМ больше является идеей, чем технологией.
Идея АМ состоит в описания системы с точки зрения её составных частей.
Синонимом АМ будет являться микроскопическое моделирование, а
альтернативой будет макроскопическое моделирование.
АМ имеет следующие основные преимущества по сравнению с
другими методами моделирования:
1.
возникают
AM проявляет эмерджентные явления. Эмерджентные явления
в
результате
взаимодействия
отдельных
объектов.
По
8
определению, такие явления не могут являться свойством частей системы,
они присущи только всей системе в целом. Эмерджентное явление может
иметь свойства, которые не являются свойствами частей. Например,
дорожная пробка может быть вызвана тем, что отдельные водители
двигаются в противоположном направлении, относительно основного потока.
Эта черта эмерджентных явлений делает их непредсказуемыми и сложными
для
понимания,
к
тому
же
эмерджентные
явления
иногда
могут
противоречить здравому смыслу.
2.
AM
обеспечивает
естественное
описание
системы.
В
большинстве случаев АМ наиболее естественно подходит для описания и
моделирования системы, состоящей из поведенческих сущностей. Если
необходимо описать дорожное движение, фондовые рынки, поведение
избирателей, агентный подход позволяет сделать модель, приближенную к
реальности. Например, естественнее описать, как покупатели двигаются в
супермаркете, чем систему уравнений, которые определяют динамику
плотности
покупателей.
Поскольку
уравнения
плотности
являются
результатом поведения покупателей, агентный подход также позволит
пользователю изучить совокупные свойства. AM также позволяет в полной
мере реализовать потенциал данных, которые компания может иметь о своих
клиентах: статистические данные и результаты опросов клиентов формируют
информацию о том, как действуют реальные люди на самом деле. Зная
фактическую потребительскую корзину клиента, можно создать агента с
такой корзиной, а не множество людей с предполагаемыми корзинами,
вычисленными с усреднением по данным продаж
3.
АМ обеспечивает гибкость. Гибкость AM можно наблюдать в
нескольких измерениях. Например, можно легко добавить больше агентов в
модель. AM обеспечивает естественную основу для настройки сложности
агентов: поведение, степень рациональности, способность учиться и
развиваться, правила взаимодействия. Другим аспектом гибкости является
возможность изменения уровня описания и агрегации: можно легко
9
оперировать с агрегатными агентами, подгруппами агентов и отдельными
агентами, которые могут сосуществовать в рамках одной модели.
АМ имеет ряд преимуществ при моделировании социальных систем.
Факторы моделируемой системы, при которых предпочтительнее применять
АМ:
 когда
взаимодействие
между
агентами
являются
сложным,
нелинейным, прерывистым или дискретным, когда поведение агента может
быть изменено под влиянием других агентов;
 когда пространство имеет решающее значение и агенты имеют
возможность перемещения в пространстве;
 когда агенты являются неоднородными, каждый агент может
обладать различным набором параметров;
 когда топология взаимодействия является сложной и неоднородной;
 когда агенты демонстрируют сложное поведение, в том числе
обучение и адаптацию.
Цель работы: разработать программную подсистему моделирования
социальной
напряженности
для
наблюдения
и
оценки
факторов
распространения влияния.
Актуальность
данной
работы
заключается
в
создании
новых
инструментов исследования социальной напряженности в сложной системе
взаимодействующих между собой индивидов.
Задачи работы:
1) описать и проанализировать предметную область;
2) сделать обзор прототипов разрабатываемой модели;
3) сделать постановку задачи для разрабатываемой агентной модели;
4) сформулировать требования к разрабатываемому программному
средству;
5) описать структуру данных и алгоритмы;
6) реализовать
поставленной задачи;
программное
средство
для
моделирования
10
7) провести серию экспериментов и апробацию программного
средства.
Данная работа состоит из трех глав основной части, введения,
заключения, списка литературы и приложения с фрагментами листинга
программы. В первой главе производится постановка задачи, обзор аналогов
моделей, программных средств и обосновывается выбор программного
средства для реализации программы. Второй раздел содержит описание
структуры и алгоритмов программной реализации. Третий раздел содержит
описание логики пользовательского интерфейса, программной реализации, а
также описание экспериментов.
11
1 ПОСТАНОВКА ЗАДАЧИ И ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ
1.1 Описание предметной области
Рассмотрим распространение политических идей в обществе. Зачастую
в политической дискуссии главную роль играет уверенность говорящего в
своих словах. Это связано с распространением политики популизма.
Популизм
–
политика,
апеллирующая
к
широким
массам
с
использованием понятных для рядового жителя тем. Популизм свойственен в
тех обществах, где имеются такие институты как всеобщее избирательное
право и равноправие граждан. Ведь тогда у политика появляется задача
добиваться расположения масс для обеспечения себе политического успеха.
Кроме того, для распространения популизма важен низкий уровень
политической культуры в обществе. В таком случае политик может
позволить себе разбавлять правду несбыточными обещаниями, потому что
для простого человека они будут одинаково реальными и правдивыми.
Распространение популизма свойственно для периодов нестабильности в
стране, когда люди сталкиваются с резкими ухудшениями условий жизни и
теряют уверенность в завтрашнем дне и действующей политике власти. К
этому способу будут прибегать все политические силы, вне зависимости от
их близости к власти.
В условиях социальной напряженности мы имеем общество, состоящее
из людей, для которых правда оценивается по тому, насколько уверено ведет
себя оратор. А тяжкие условия жизни могут заставить прислушаться к самым
радикальным идеям, если они будут обещать решить проблемы, которые
угнетают человека в данный момент.
Также
стоит
учитывать
психологические
аспекты
социальной
активности человека, в основе которых лежит его склонность к переменам,
или,
наоборот,
природная
инертность.
Согласно
социологическим
исследованиям, большая часть людей склонна скорее подстраиваться под
обстоятельства, чем пытаться их изменить. Тем не менее, по мере роста
12
недовольства условиями жизни, у человека накапливается энергия, способная
по достижении некоторого порога толкнуть его на решительные действия.
Этот порог может быть обусловлен следующими факторами:
 размахом
между
представлением
о
комфортной
жизни
и
фактическим уровнем жизни человека;
 временем,
в
течение
которого
человек
находился
в
неудовлетворительных, по его мнению, условиях.
Убедительность, подверженность влиянию и пороговый уровень
недовольства являются сугубо личными характеристиками, однако в их
соотношении можно проследить некоторые закономерности. Это позволяет
разбить людей на кластеры.
Условно выделим 4 кластера и дадим им названия из животного мира:

Лисы – это профессиональные участники социально-политических
процессов, организаторы информационного воздействия. Они обладают
высокой убедительностью и низкой подверженностью влиянию;

Волки – это идейные участники движений, одаренные высокой
убедительностью и низкой инертностью, могут становиться организаторами;

Собаки – твердая основа социально-политических движений с
высокой подверженностью влиянию. Также имеют низкий пороговый
уровень недовольства и легко переходят в активное состояние, однако чаще
являются исполнителями, чем организаторами;

Зайцы – это наиболее многочисленная нейтрально-настроенная
часть населения, пороговый уровень недовольства у них высокий, то есть они
в последнюю очередь переходят активное состояние.
1.2 Постановка задачи
Модель представлена сетью агентов, имеющих свободную связь между
собой. Агенты в сети делятся на несколько кластеров. Агенты, относящиеся к
одному кластеру, имеют общие свойства. Все агенты имеют показатели
убедительности, внушаемости и порог недовольства, определяемые тем, к
13
какому кластеру принадлежит агент. Убедительность и внушаемость
используются во время взаимодействия агентов для определения успешности
влияния активного агента. Порог недовольства используется для определения
момента, когда пассивный агент становится активным. Агенты разделяются
на 4 кластера, со следующими характерными чертами:
1) лисы - профессиональные участники социально-политических
процессов и организаторы информационного воздействия, обладают высокой
убедительностью и отсутствием внушаемости и порога недовольства,
единственный кластер, в котором агенты находятся в состоянии активности
на момент начала моделирования;
2) волки - идейные участники социально-политических движений,
могут быть организаторами, имеют высокую убедительность, среднюю
внушаемость, высокий порог недовольства;
3) собаки - твердая основа социально-политических движений, имеют
низкую убедительность, высокую внушаемость, низкий порог недовольства;
4) зайцы - наиболее многочисленная нейтрально-настроенная часть
населения, характеризуется отсутствием убедительности, низкой средней
внушаемостью и высоким порогом недовольства.
Изменяемыми параметрами модели являются:

численность кластеров в процентах;

границы убедительности и внушаемости агентов, принадлежащих
каждому кластеру.
Процесс моделирования делится на две фазы. В первой фазе активные
агенты делятся между собой сообщениями. Активные агенты рассылают
провокационные сообщения с целью увеличить общий уровень недовольства.
Успешность влияния провокационного сообщения проверяется сравнением
значений убедительности агента отправителя и внушаемости агента
получателя. На агента получателя оказывается воздействие только в том
случае,
если
в
результате
достаточной, чтобы
проверки
поддаться
его
внушаемость
оказывается
убеждению агента отправителя. При
14
достижении порога недовольства пассивный агент может стать активным и
начать принимать участие в рассылке сообщений, если он принадлежит
соответствующему кластеру. Схема первой фазы представлена на рисунке
1.1.
Рисунок 1.1 – Схема активной фазы взаимодействия агентов
Затем, спустя несколько этапов моделирования первой фазы, наступает
вторая фаза. Активные агенты рассылают приглашения на митинг тому
списку контактов, который они сформировали во время первой фазы
моделирования. Агенты, чей уровень недовольства не достиг порогового
значения, исходя из количества полученных приглашений, принимают
конечное решение о том, присоединиться к акции или нет.
1.3 Сравнение с похожими задачами
Диффузионная модель заимствования инноваций, описанная в статье
«A New Product Growth for Model Consumer Durables» Фрэнка Басса имеет в
своей постановке одну деталь, из-за которой ее можно сравнивать с
агентными моделями. Потребители в модели не являются однородными и
разделены на классы. В статье описывается теория момента первоначальной
покупки новых потребительских продуктов. Теория предназначена для
применения к росту первоначальных покупок широкого спектра "новых"
основных классов продуктов. Таким образом, проводится черта между
15
новыми классами продукции и новыми брендами или новыми моделями
имеющихся классов продуктов.
Некоторые люди решают принять инновации независимо от решений
других людей в социальной системе. Мы будем называть этих людей
новаторами. Первых принимающих мы могли бы отнести к новаторам. В
литературе потребители классифицируются следующим образом: новаторы;
быстро принимающие; раннее большинство; позднее большинство; и
консерваторы. Эта классификация основана на периоде адаптации в
различных группах.
Помимо новаторов, принимающие поддаются влиянию со временем
возрастающим давлением со стороны социальной системы, давление
увеличивается для более поздних принимающих с увеличением числа
предыдущих принимающих. В математической формулировке теории группы
объединены в одну группу имитаторов. Имитаторы, в отличие от новаторов,
поддаются серьезному влиянию общества при увеличении сроков принятия
решения. Новаторы описываются как азартные и дерзкие потребители. Кроме
того, они так же взаимодействуют с другими новаторами.
Разделение агентов на кластеры с разной
силой влияния и
податливости является общей чертой для поставленной задачи и моделью
распространения инноваций. Но в отличие от модели распространения
инноваций в поставленной задаче процесс распространения идеи происходит
через личные контакты между отдельно взятыми агентами.
Поставленная
задача
основывается
на
модели
гражданского
неповиновения Джошуа Эппштейна и ограниченной рациональности Брайана
Артура.
Джошуа Эпштейн в статье «Modeling Civil Violence: An Agent-Based
Computational
Approach»
представил
агентную
модель
гражданского
неповиновения, в которой централизованная власть пытается подавить
децентрализованный бунт. В модели описано два вида акторов. «Агенты»
представляют
обобщенное
население
и
могут
проявлять
мятежную
16
активность,
либо
не проявлять. «Полицейские»
представляют
силы
правопорядка, которые ведут поиски и арестовывают активно недовольных
агентов. Агенты имеют параметры, влияющие на недовольство агента
властью. Если агент считает, что его степень недовольства достигла
определенного порога, агент будет рассматривать возможность мятежа. Но
он так же будет оценивать вероятность быть арестованным полицейскими.
Вероятность зависит от количества рядом полицейских и уже активно
митингующих агентов. Для этого агент имеет радиус обзора. Агент может
переходить из нейтрального состояния в активное состояние и наоборот.
Полицейские имеют более простое поведение, чем гражданские агенты.
Полицейский имеет свой собственный радиус обзора, одинаковый для всех
полицейских. Полицейские могут осматривать всех агентов в своем радиусе
обзора и арестовать одного случайного активного агента.
С моделью гражданского неповиновения у поставленной задачи
схожесть в наделении агентов индивидуальными характеристиками и
возможности оценки последствий своих мятежных действий. В модели
гражданского неповиновения агент моментально решает, может ли он
проявлять неповиновения, основываясь на ситуации вокруг него, в
поставленной же задаче для перехода агента из пассивного состояния в
активное состояние, на него необходимо оказать влияние извне. Став
активным, агент может сам начать оказывать влияние на других агентов.
Брайан Артур в своей статье «Inductive Reasoning and Bounded
Rationality» рассмотрел применение агентного подхода в экономике в рамках
«проблемы о посещении бара». При рассмотрении данной задачи было
смоделировано
человекоподобное
индуктивное
мышление
агентов,
способных эволюционировать. Задача сформулирована следующим образом.
Пусть N людей еженедельно решают, независимо друг от друга, идти ли им в
определенную ночь в бар, предлагающий развлекательные мероприятия, или
нет. Для упрощения предположим, что N = 100. Помещение бара ограничено,
и вечер будет приятным, если в этом баре не будет столпотворения
17
(конкретнее – если там будет находиться меньше 60% из возможных 100).
Нет способа заранее определить, сколько людей наверняка придет. Поэтому
лицо, или агент, идет в бар – считает, что стоит пойти, - если ожидает
появления в баре меньше 60 человек, или остается дома, если ожидает
появления в баре больше 60 человек (совершенно не обязательно, что эта
полезность будет сильно различаться в ситуациях, когда количество людей
намного больше или намного меньше 60). На выбор не влияют предыдущие
визиты, нет сговора или предшествующего общения агентов между собой, и
единственная доступная информация – количество людей, которые пришли
на прошлых неделях. Представляет интерес динамика еженедельных
посещений.
В этой задаче не существует очевидной модели поведения, на основе
которой агенты могли бы предсказывать исход посещения бара и принимать
решение. Поскольку все агенты до самого последнего остаются в неведении,
какое решение примут другие агенты, никто не может точно предсказать, как
поступят другие. Также не может существовать общего популярного
решения. Если большинство агентов предположит, что пойдет мало людей и
решит идти, то их ожидает результат прямо противоположный тому, что они
ожидали.
Предполагается, что у агентов есть история посещений бара и
определенный набор правил, которые помогают агентам с помощью истории
принять решение о том, посещать бар или нет. Агент принимает решение на
основе того правила, которое за все время моделирования показало
наибольшую точность. После принятия решения, агенты обновляют историю
и корректируют точность своих правил.
Второй этап моделирования похож на проблему посещения бара, но
только идеей того, что агентам предстоит воспользоваться некоторой
статистикой и правилами для её интерпретации, чтобы принять решение о
том, чтобы пойти на планирующееся мероприятие. Модель посещения бара
основывается
на
длительном
моделировании,
в
процессе
которого
18
формируется доверие агентов к правилам принятия решения, в поставленной
же задаче мероприятие проводится только один раз, поэтому агенты
вынуждены проводить опрос, чтобы узнать численность посетителей и
благоприятность похода на мероприятие.
1.4 Формирование требований
Для более полного понимания моделируемой подсистемы следует
сформировать требования.
Пользовательские требования:
1) Система должна быть доступна для использования уверенным
пользователям ПК;
2) Система может быть запущена внутри сторонней среды разработки,
либо являться самостоятельным приложением;
3) Пользователь должен иметь возможность изменения параметров
модели, наблюдать за ходом моделирования, анализировать результаты
процесса моделирования, экспортировать результаты моделирования.
Функциональные требования:
1) Генерация агентов. Система должна генерировать агентов в
кластерах в соответствии с указанными пользователем входными данными;
2) Перебор
входных
параметров.
Пользователь
может
иметь
возможность указать несколько значений для входных параметров модели. В
этом случае должен быть осуществлен перебор всех возможных комбинаций
входных параметров и выполнен процесс моделирования. Результаты запуска
каждого нового процесса моделирования не должны зависеть от уже
выполненных моделей.
Нефункциональные требования:
1)
Надежность. Процесс моделирования не должно прерываться из-
за внутренних ошибок при корректных входных данных;
2)
Скорость
выполнения.
Процесс
моделирования
выполняться достаточно быстро, не дольше 10 секунд.
должен
19
1.5 Сравнение с аналогами
Программные
средства
можно
разделить
на
две
категории,
специализированные и собственноручно написанные. Специализированное
ПО, обычно, создано группой опытных разработчиков для удовлетворения
обширного
круга
задач
при
массовом
использовании
конечными
пользователями. В большинстве случаев специализированное ПО является
платным. Собственноручно написанное ПО, обычно, разрабатывается для
удовлетворения
какой-то
конкретной
задачи,
поставленной
перед
разработчиком.
К специализированному ПО можно отнести NetLogo. NetLogo –
программируемая среда моделирования для симуляции естественных и
социальных процессов. ПО Netlogo было разработано в 1999 году и
продолжает развиваться. Netlogo позволяет создавать сложные модели с
тысячами независимых агентов, что позволяет исследовать связь между
поведением индивидуальных агентов на микро-уровне и паттернами на
макро-уровне. Netlogo подходит для учебных целей, существует огромная
база обущаючих материалов и документаций по основной программе и
расширениям. Так же имеется большая база моделей, которые могут быть
использованы и модифицированы. Эти модели созданы в таких областях,
как: биология, медицина, физика, химия, математика, информатика,
экономика, социология. Модели в NetLogo запускаются на виртуальной
машине Java, это позволяет использовать NetLogo на всех основных
операционных системах. Netlogo достаточно маленький проект, это может
привести к возникновению сложностей при попытках использования данного
ПО в работе с серьезными проектами.
Еще одно специализированное ПО – AnyLogic. AnyLogic – инструмент
поддержки принятия решений для любого отдела и отрасли. Программа
поддерживает все существующие методы имитационного моделирования
(системную динамику, дискретно-событийное и агентное моделирование).
20
Функциональность
и
гибкость
AnyLogic
позволяет
применять
моделирование практически в любой сфере бизнеса, от цепочек поставок и
логистики до анализа рынка и планирования производства, помогая
принимать правильные решения и эффективно справляться с задачами
компании.
Применяемое
на
любом
уровне,
включая
оперативный,
тактический и стратегический. Есть возможность соединять имитационные
модели, созданные в разных отделах.
AnyLogic – лидер в совместимости с другим софтом. Можно
использовать различные источники ГИС-карт (например, OpenStreetMap,
shapefiles), легко импортировать чертежи CAD и 3D-модели или работать с
различными
оптимизационными
пакетами
(например,
OptQuest)
и
инструментами подбора вероятностного распределения. AnyLogic может
быть легко интегрирован с базой данных (например, MS SQL, Oracle), также
он предоставляет доступ к данным в текстовых и табличных файлах.
ПО AnyLogic совместимо с рабочими станциями и серверами Windows,
Mac
и
Linux.
Имитационные
модели
можно
экспортировать
как
интерактивные и полностью функциональные Java-апплеты, которые затем
можно поместить на собственный веб-сервер. AnyLogic является бесплатным
только для использования в учебных целях, что не позволяет использовать
данное ПО в рабочих целях без покупки дорогостоящей лицензии.
Можно создать специализированное ПО с использованием библиотеки
Akka. Akka – свободно распространяемый пакет библиотек для разработки
конкурентных и распределенных приложений на JVM. Главное Akka
предлагает работать с акторами, которые взаимодействуют между собой
посредством сообщений. Сообщения в Akka служат для того, чтобы акторы
выполняли заранее определенные функции, только все это происходит
параллельно.
Для работы с агентными моделями из Akka можно получить очень
мощный и гибкий инструмент. Основной принцип Akka – это независимые
вычисления с обменом сообщениями между акторами. То есть акторы
21
являются множеством конечных автоматов, которые будут менять свое
внутреннее состояние, представленное различными переменными, при
получении заранее определенных сообщений. Таким образом, акторы в Akka
являются практически нативной реализацией агентов в агентной модели, при
отправке сообщений между акторами по принципу «послал и забыл».
В отличие от специализированных средств моделирования, таких как
AnyLogic,
которые
предлагают
работать
с
урезанной
версией
распространенных языков программирования, при работе с Akka можно
использовать весь потенциал выбранного языка программирования без
лишних неудобств.
1.6 Описание библиотеки Akka
1.6.1 Акторная модель
Для программной реализации поставленной задачи была выбрана
акторная модель. В 1973 году Карл Хьюит, Питер Бишоп и Ричард Штайгер в
статье
«Универсальный
акторный
формализм
для
искусственного
интеллекта» предложили новый подход к выполнению вычислений,
основанный на представлении процесса вычислений в виде совокупности
независимых, параллельных, взаимодействующих между собой посредством
отправки сообщений атомарных элементов, называемых акторами. Модель
акторов исходит из такой философии, что всё вокруг является акторами. Это
похоже на философию объектно-ориентированного программирования, где
всё вокруг является некоторыми объектами, но отличается тем, что в
объектно-ориентированном программировании программы, как правило,
выполняются последовательно, в то время как в модели акторов вычисления
по своей сути совпадают по времени.
В ответ на получаемые сообщения актор может отреагировать
следующим образом:
 отправить конечное число сообщений другим акторам;
 создать конечное число акторов;
22
 выбрать поведение для приема следующего сообщения.
Описанные действия могут быть выполнены актором параллельно.
Отделение
отправителя
фундаментальным
от
достижением
посланных
модели
сообщений
акторов,
стало
обеспечивющим
асинхронную связь и управление структурами в виде формы передачи
сообщений.
Получатели сообщений идентифицируются по адресу, который иногда
называют
«почтовым
адресом».
Таким
образом,
актор
может
взаимодействовать только с теми акторами, адреса которых он имеет, может
извлечь адреса из полученных сообщений или знать их заранее, если актор
создан им самим.
Модель акторов характеризуется внутренне присущим параллелизмом
вычислений внутри одного актора и между акторами, динамическим
созданием акторов, включением адресов акторов в сообщения, а также
взаимодействием только через прямой асинхронный обмен сообщениями без
каких-либо ограничений на порядок прибытия сообщений.
Акторная
модель
была
реализована
в
нескольких
языках
программирования.
Erlang – это язык программирования, разработанный компанией
Ericsson в 1986 году. Название языка можно интерпретировать двумя
разными вариантами. Это может быть дань уважения Датскому математику
Агнеру Эрлангу, основателю научного направления по изучению трафика в
телекоммуникационных системах и теории массового обслуживания. Или как
аббревиатура от словосочетания Ericsson Language. Язык был разработан для
реализации телекоммуникационных приложений с высокой нагрузкой в
реальном времени. В языке Erlang, который разрабатывался специально для
реализации масштабируемости, параллелизма, распределенных вычислений,
акторы являются неотъемлимой частью самого языка. Erlang разрабатывался
для нужд телекоммуникационной отрасли, где огромное количество
параллельных процессов является нормой, учитывая это, невозможно
23
представить Erlang без акторов, благодаря которым реализуются все эти
поставленные задачи. Акторы в Erlang это процессы, которые создаются
специальной встроенной функцией spawn.
В Erlang используется превентивный планировщик для планирования
процессов.Если процесс занимает слишком много времени на выполнение,
либо простаивает без входящих сообщений, он приостанавливается и
помещается обратно в очередь планирования. Это позволяет запускать
большое количество процессов без риска того, что долго выполняющиеся
процессы не позволят остальным процессам выполняться.
Scala – язык программирования, объединяющий в себе объектноориентированное и функуциональное программирование, в то же время имея
полную совместимость с JVM. Язык был разработан в 2001 году Мартином
Одерски. Название языка Scala может быть расшифровано Scalable Language
(Масштабируемый Язык).
Разработчики Scala предполагали, что язык должен масштабироваться
вместе с потребностями его пользователей. Разработчик может писать
короткий
и
сжатый
функциональный
код,
при
этом
объектное-
ориентированный подход позволяет использовать язык для сложных
проектов.
Акторы в Scala доступны в библиотеке scala.actors. Реализации акторов
в Erlang и Scala имеют много общего. Это не случайность, поскольку
акторная библиотека в Scala имеет множество заимствований из Erlang. Тем
не менее, разработчики Scala добавили несколько нововведений в свою
акторную библиотеку.
Разработчики
Scala
заметили
повторяющийся
шаблон
при
использовании акторов, когда разработчику приходится описывать в акторе
принятие сообщения и отправку ответа обратно отправителю, и реализовали
это в своей библиотеке. Была добавлена конструкция, позволяющая ожидать
ответа от актора. Актору можно отправить абсолютно любое сообщение,
если сообщение не соответствует ни одному из шаблонов, которые ожидает
24
актор, оно останется в его почтовом ящике, а не вызовет ошибку. Также Scala
позволяет программистам смешивать в одной программе модель исполнения
на основе потоков и на основе событий. Это позволяет выбирать в каждом
отдельном случае между масштабируемыми легкими конструкциями на
основе событий, которые выполняются на одном потоке, и параллельно
исполняемыми акторами на основе потоков.
1.6.2 Язык программирования Scala
Язык программирования Scala является «симбиозом» Java и C#. Это не
первый язык, комбинирующий ООП с функциональным подходом, но он
начал набирать обороты в тот момент, когда развитие Java замедлилось.
Более того, создатели Scala решили, что язык должен работать на
виртуальной машине JVM и предоставлять доступ к Java-библиотекам.
Язык Scala объединяет три вещи: статическую типизацию, объектноориентированный и функциональный подход.
Помимо упомянутых выше Java и C#, на Scala оказали влияние другие
языки и технологии. Способ выражения свойств во многом заимствован из
Sather. Из Smalltalk перекочевала концепция унифицированной объектной
модели. Beta поделился идеей о вложенности всего подряд, включая классы.
Абстрактные типы в Scala напоминают абстрактные типы сигнатур в SML и
OCaml, обобщенные в контексте полноценных компонентов.
Кроме того, Scala перенял особенности таких функциональных языков,
как Scheme, Standard ML и Haskell.
Scala является объектно-ориентированным функциональным языком
программирования,
исполняющимся
на
JVM.
Scala
как
объектно-
ориентированный язык рассматривает каждое значение в качестве объекта, а
типы и поведение объектов описываются как классы и типажи. Как
функциональный язык, Scala позволяет использовать анонимные функции и
функции
высшего
порядка,
вложенные
функции,
каррирование
сопоставление с образцом. Каждая функция в Scala является значением.
и
25
Scala набирает популярность в мире разработки. Основные вебфреймворки, написанные на Scala — Play, Lift. Среди их пользователей
отмечены ряд крупных сервисов, в частности, Play используют Gilt и
Coursera, а Foursquare — Lift. Социальная сеть LinkedIn использует
микрофреймворк Scalatra для поддержки своего Signal API. В апреле 2009
года Twitter объявил, что перевёл значительную часть своего серверного кода
с Ruby на Scala и собирается перевести оставшийся [9]. В апреле 2011
онлайн-версия газеты The Guardian была переведена с Java на Scala. Проекты
фонда Apache Apache Spark, Apache Ignite (свободная версия основного
продукта компании GridGain) и Apache Kafka написаны в основном на Scala.
Одним из активных пользователей языка также является банк UBS. Для
своих задач Scala вместе с Akka использовали такие компании, как Intel,
PayPal, Amazon, Samsung.
1.6.3 Реализация акторной модели в Akka
Несмотря на то, что в Scala уже есть своя библиотека для реализации
акторов, на данный момент она сильно устарела и с версии Scala 2.11 была
заменена на реализацию акторов из библиотеки Akka. Эта библиотека посути уже давно является стандартом для Scala. Библиотека Akka доступня
для языков программирования Java и Scala. Библиотека изначально
разработана под Scala, а доступность её на Java обусловлена особенностью
Scala в обратной совместимости с Java
Актор Akka состоит из нескольких взаимодействующих компонентов.
ActorRef – это логический адрес актора, позволяющий асинхронно
отправлять актору сообщения по принципу «послал и забыл». Диспетчер
отвечает за постановку сообщений в очередь, ведущую в почтовый ящик
актора, а также приказывает этому ящику изъять из очереди одно или
несколько сообщений, но только по одному за раз — и передать их актору на
обработку, по умолчанию на каждую систему акторов приходится по одному
диспетчеру. Схема взаимодействия представлена на рисунке 1.2.
26
Akka не позволяет получить непосредственный доступ к актору и
поэтому гарантирует, что единственный способ взаимодействия с актором —
это асинхронные сообщения. Невозможно вызвать метод в акторе.
Рисунок 1.2 – Схема взаимодействия акторов в Akka
В Akka отправка сообщения актору и обработка этого сообщения
актором — это две отдельных операции, которые, могут происходить в
разных потоках. Akka обеспечивает необходимую синхронизацию, чтобы
гарантировать, что любые изменения состояния будут видимы всем потокам.
Таким образом, Akka создает иллюзию однопоточности, и
у
программиста не возникает необходимости писать асинхронный код.
В Akka система акторов представляет собой взаимосвязанный
ансамбль, члены которого организованы иерархически, где у каждого актора
есть свой родительский актор. Иерархия акторов представлена на рисунке
1.3.
Рисунок 1.3 – Иерархия акторов
27
Обратиться к актору можно только послав ему сообщение, которое он
умеет принимать, сообщения передаются по принципу «послал и забыл», то
есть, от получателя не приходит уведомление о том, получил или обработал
ли он сообщение.
1.6.4 Работа акторов в акторной модели
Приложение на Akka может состоять из нескольких десятков или
нескольких миллионов акторов. Это достигается благодаря тому, что между
акторами и потоками нет соответствия один к одному. Поскольку акторы не
блокируют потоки вычисления, один поток может выполнять несколько
акторов, переключаясь между ними, в зависимости от того к какому актору
приходят сообщения.
Во время обработки сообщения актор может делать всё что угодно,
кроме возвращения значения. Состояние заключено внутри акторов и каждое
сообщение обрабатывается одно за другим независимо от других акторов.
Это обеспечивает естественный параллелизм, и не возникает необходимости
в синхронизации процессов или семафорах. Акторам можно передавать
сообщения любого типа. Это связано с некоторыми очень важными
архитектурными решениями в Akka. Это позволяет перенаправлять
сообщения другим акторам, управлять вычислительной нагрузкой или
создавать прокси акторы, в тайне от отправителя сообщений и так далее.
Отправление сообщения и приём происходят асинхронно, без
блокирования потока вычислений. Отправитель не будет заблокирован во
время обработки сообщения. Вместо этого он продолжит выполнять свою
работу. Отправленное сообщение доставляется в почтовый ящик актора,
который представляет собой очередь. Добавление сообщения в почтовый
ящик не блокирует вычисления, то есть отправитель не ждёт пока сообщение
будет добавлено в очередь адресата.
Обработчик событий заметит появление нового сообщения, опять же
асинхронно. Если актор не занимается обработкой другого сообщения, для
28
него выделяется отдельный поток, доступный в контексте вычислений. Как
только актор закончит обработку предыдущего сообщения, обработчик
отправит ему следующее сообщение из почтового ящика.
Актор блокирует выделенный ему поток вычислений до тех пор, пока
не закончится обработка сообщения. Хотя это не скажется на отправителе,
это всё же означает, что медленные операции могут затормозить всё
приложение, поскольку для остальных акторов останется меньше потоков.
Каждый актор может содержать внутреннее состояние, хотя это и не
обязательно. Иногда большая часть состояния приложения состоит из
информации передаваемой изменяемыми сообщениями, которые передаются
от одного актора к другому.
Исходя из этого можно сделать вывод, что Akka отлично подходит для
создания агентных моделей.
29
2 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ, СТРУКТУРА И
АЛГОРИТМЫ
2. 1 Моделирование процессов предметной области
Основными объектами моделируемой среды являются агенты, а точнее
кластеры агентов. Представлено 4 кластера агентов, отличающихся
следующими параметрами:
 Численность. Суммарное число агентов кластера из общего числа
агентов;
 Убедительность. Способность агента эффективно воздействовать на
собеседника;
 Внушаемость. Способность агента сопротивляться оказываемому на
него воздействию;
 Порог недовольства. Значение, определяющее, как много раз агент
может подвергаться воздействию перед тем как решиться на активные
действия.
Агенты имеют два состояния, активное и пассивное. Активные агенты
пытаются влиять на пассивных агентов с целью переманить их на свою
сторону. При этом агенты в кластере лис могут быть только активными
агентами.
Пассивный
агент
имеет
параметры
внушаемости
и
порога
недовольства, которые определяются тем, к какому кластеру принадлежит
агент. Накопленный уровень недовольства является внутренним параметром
пассивного агента. В случае достижения уровня недовольства агент начинает
действовать как активный агент. Состояние 1- обычное состояние агента во
время ожидания. Состояние 2 – обработка агентом сообщения от активного
агента. В случае успешного воздействия агент увеличивает уровень
недовольства. Затем агент проверяет, достигнут ли его уровень недовольства,
если да, то он переходит в 3 состояние, иначе он возвращается в 1 состояние
30
с новым уровнем недовольства. Переходя в 3 состояние, агент перестает
действовать как пассивный агент и начинает действовать как активный агент.
При поступлении сообщения с приглашением на митинг агент увеличивает
счетчик принятых приглашений. При поступлении обращения к агенту с
вопросом о том, собирается ли он принять участие в митинге, агент
принимает решение на основе того, сколько ему пришло приглашений. Если
в итоге он соглашается, то он переходит в 5 конечное состояние. На рисунке
2.1 изображен конечный автомат состояний пассивного агента
Рисунок 2.1 – Конечный автомат пассивного агента
Активный
определяется
агент
имеет
принадлежностью
параметр
к
кластеру.
убедительности,
Активный
который
агент
имеет
внутренний параметр список агентов, с которыми он контактировал.
Активный агент может посылать сообщения с целью воздействия и
31
приглашения на митинг. Для воздействия агент выбирает цель случайно из
списка пассивных агентов. Приглашения на митинг активный агент
рассылает всем агентам, с которыми он до этого общался.
Во время воздействия активного агента на пассивного будут
сравниваться абсолютные значения убедительности активного агента и
внушаемости пассивного агента. Если убедительность активного агента
больше значения внушаемости пассивного агента, то засчитывается
успешное влияние. Это отображено на следующей формуле:
(1)
где УН –
Убд –
уровень недовольства пассивного агента;
значение убедительности активного агента;
Внуш – значение внушаемости пассивного агента.
Как только количество таких успешных влияний достигает порога
недовольства, пассивный агент перейдет в состояние активного.
При обработке приглашения на митинг пассивный агент смотрит на
количество приглашений и текущий уровень недовольства и принимает
решение по следующей формуле:
(2)
где ПН –
УН –
порог недовольства;
уровень недовольства;
СлЗн – случайное число в диапазоне от 0 до 1;
Пригл – количество полученных приглашений.
Если значение в правой части формулы получится больше, то агент
согласится принять участие в митинге.
32
2.2 Реализация модели с использованием акторов
Агенты становятся экземплярами акторов в соответствии с тем, к
какому кластеру должен принадлежать агент. Акторы называются FoxAgent,
WolfAgent, DogAgent, RabbitAgent.
Акторы, имеющие возможность действовать как активные агенты,
наследуют
свойство
ActiveAgent.
Это
свойство
содержит
описание
следующих сообщений:
 SendMessage –при получении этого сообщения, активный актор
должен будет послать сообщение указаному пассивному агенту в первой
фазе моделирования;
 SendInvite – при получении этого сообщения, активный актор
должен отправить приглашения на митинг на второй фазе моделирования.
Акторы, имеющие возможность действовать как пассивные агенты,
наследуют свойство PassiveAgent. Это свойство содержит следующие
методы:
 Communication – при получении этого сообщения, пассивный актор
должен обработать сообщение от активного агента. В случае успешного
воздействия увеличить текущий уровень недовольства;
 AgentStatus – при получении этого сообщения, пассивный актор
должен ответить, достиг ли уровень недовольства порога недовольства;
 GetInvites – при получении этого сообщения, пассивный актор
должен обработать приглашение на митинг;
 Decide – при получении этого сообщения, пассивный актор должен
принять решения о своем участии в митинге.
Актор FoxAgent в процессе моделирования может проявлять себя
только как активный агент и наследует свойство ActiveAgent. Актор
содержит следующие параметры:
 переменная connections, в которой содержится история агентов, с
которыми агент взаимодействовал.
33
При
создании
актора
FoxAgent,
ему
передается
значение
убедительности агентов кластера лисы.
Актор WolfAgent в процессе моделирования может проявлять себя как
пассивный агент, так и как активный агент, поэтому актор наследует
свойства ActiveAgent и PassiveAgent. Актор содержит следующие параметры:
 переменная connections, в которой содержится история агентов, с
которыми агент взаимодействовал агента кластера волки;
 переменная patienceLevel, в которой хранится текущий уровень
недовольства агента из кластера волки;
 переменная active, в которой хранится информация, достиг уровень
недовольства агента из кластера волки порога недовольства или нет;
 переменная invites, в которой хранится количество принятых
приглашений на митинг агентом из кластера волки.
При
создании
актора
WolfAgent,
ему
передаются
значение
убедительности, внушаемости и порога недовольства агентов кластера волки.
Актор DogAgent в процессе моделирования может проявлять себя как
пассивный агент, так и как активный агент, поэтому актор наследует
свойства ActiveAgent и PassiveAgent. Актор содержит следующие параметры:
 переменная connections, в которой содержится история агентов, с
которыми агент взаимодействовал агента кластера собаки;
 переменная patienceLevel, в которой хранится текущий уровень
недовольства агента из кластера собаки;
 переменная active, в которой хранится информация, достиг уровень
недовольства агента из кластера собаки порога недовольства или нет;
 переменная invites, в которой хранится количество принятых
приглашений на митинг агентом из кластера собаки.
При
создании
актора
DogAgent,
ему
передаются
значение
убедительности, внушаемости и порога недовольства агентов кластера
собаки.
34
Актор RabbitAgent в процессе моделирования может проявлять себя
только как пассивный агент и наследует свойство PassiveAgent. Актор
содержит следующие параметры:
 переменная connections, в которой содержится история агентов, с
которыми агент взаимодействовал агента кластера зайцы;
 переменная patienceLevel, в которой хранится текущий уровень
недовольства агента из кластера зайцы;
 переменная active, в которой хранится информация, достиг уровень
недовольства агента из кластера зайцы порога недовольства или нет;
 переменная invites, в которой хранится количество принятых
приглашений на митинг агентом из кластера зайцы.
При
создании
актора
RabbitAgent,
ему
передаются
значение
внушаемости и порога недовольства агентов кластера собаки.
Для организации процесса моделирования вводится специальный актор
Dispatcher, который поддерживает актуальную информацию о состоянии всех
агентов и заставляет активных агентов рассылать сообщения пассивным
агентам на первой и второй стадиях моделирования. Актор содержит
следующие методы:
 Cycle – при получении этого сообщения, актор выполняет итерацию
цикла на первом этапе моделирования. После получения этого сообщения
активным агентам рассылается сообщение SendMessage, а затем обновляется
список активных и пассивных агентов с помощью отправки пассивным
агентам сообщения AgentStatus;
 Protest – при получении этого сообщения, актор выполняет второй
этап моделирования. После получения этого сообщения активным агентам
рассылается сообщение SendInvite;
 CheckInvites – при получении этого сообщения, актор рассылает
пассивным агентам сообщение Decide, а затем обновляет список активных и
пассивных агентов с помощью отправки пассивным агентам сообщения
AgentStatus.
35
Актор Dispatcher содержит следующие ствойства:
 переменная activeAgents, в которой хранится список активных
агентов;
 переменная passiveAgents, в которой хранится список пассивных
агентов.
Для сбора информации в процессе моделирования вводится актор
Statistic. Пассивные агенты обращаются к этому актору после перехода в
активное состояние, а актор Dispatcher записывает количество активных
агентов в конце каждой итерации первого этапа моделирования. Актор
содержит следующие методы:
 Activated – при получении этого сообщения, актор фиксирует
информацию о переходе агента-отправителя в активное состояние;
 AddHistroy – при получении этого сообщения, актор добавляет
текущее количество активных агентов в историю;
 GetStatistic – при получении этого сообщения, актор выводит всю
накопленную статистику за время моделирования, количество активных
агентов на каждой итерации моделирование, количество активных агентов в
каждом кластере на конец моделирования и время работы модели в
миллисекундах;
 GetResult – при получении этого сообщения, актор выводит
количество активных агентов в конце моделирования.
Актор Statistic содержит следующие ствойства:
 переменная
statByName,
в
которой
хранится
количество
активированных агентов в каждом кластере;
 переменная history, в которой хранятся значения количества
активных агентов на каждой итерации процесса моделирования;
 переменная startTime, в которой хранится время запуска модели.
Схема структуры изображена на рисунке 2.2.
36
Рисунок 2.2 – Структура акторов
37
2.3 Алгоритмы первой и второй фаз моделирования
Первая фаза моделирования выполняется несколько раз в цикле.
Диспетчер выбирает всех имеющихся активных агентов и передает им
сообщение с указанием случайного пассивного агента, на которого будет
оказываться влияние.
При получении сообщения от диспетчера, активный агент запоминает
адрес
переданного
ему
пассивного
агента
для
следующей
стадии
моделирования и передает пассивному агенту сообщение с указанием
собственной силы убеждения. Пассивный агент получает сообщение и
сравнивает пришедшее значение со своим значением внушаемости. При
успешном воздействии уровень недовольства пассивного агента повышается
и может достигнуть порога недовольства. После достижения порога
недовольства, пассивный агент переходит в активное состояние и так же
начинает передавать сообщения, если он принадлежит кластеру, который
может действовать как активный агент.
В конце шага цикла обновляется список активных и пассивных
агентов, те агенты, которые стали активными, добавляются в список
активных агентов диспетчера и удаляются из списка пассивных агентов
диспетчера.
На второй фазе моделирования диспетчер передает всем активным
агентам сообщение о начале рассылки приглашений на митинг. Активные
агенты отправляют всем агентам, которым они отправляли сообщения на
первой фазе, сообщение с приглашением на митинг. Затем диспетчер
отправляет пассивным агентам сообщение о начале подсчета приглашений.
Пассивные агенты подсчитывают количество полученных сообщений и
принимают решение, исходя из количества принятых приглашений и
текущего уровня недовольства, принимать участие в митинге или нет.
Поскольку большая часть процессов выполняется асинхронно, в схеме
невозможно отобразить точную последовательность операций. Схема
алгоритма моделирования представлена на рисунке 2.4.
38
Рисунок 2.4 – Cхема алгоритма моделирования
39
2.4 Описание процессов обработки сообщений акторами
Рассмотрим подробнее процессы обработки сообщений акторами.
Процессы обработки сообщений акторами со свойством ActiveAgent.
При
получении
сообщения
SendMessage
с
указанием
ссылки
пассивного агента, активный агент заносит ссылку на агента в список своих
контактов, а затем отправляет сообщение Communication с указанием
значения убеждения агенту по указанной ссылке.
При получении сообщения SendInvites, активный агент обходит весь
список своих контактов и отправляет каждому агенту из этого списка
сообщение GetInvites.
Процессы обработки сообщений акторами со свойством PassiveAgent.
При получении сообщения Communication с указанием значения
убеждения активного агента, пассивный агент сравнивает пришедшее
значение убеждения и собственное значение внушаемости. Если значение
убеждения оказалось больше, то засчитывается успешное убеждение и
уровень недовольства пассивного агента увеличивается. Затем пассивный
агент сравнивает уровень недовольства с порогом недовольства, если
недовольство достигло порогового значения, то агент переходит в состояние
активного и отправляет актору Statistic сообщение Activated с указанием
своей принадлежности к определенному кластеру.
При получении сообщения AgentStatus пассивный агент возвращает
отправителю значение переменной active.
При получении сообщения GetInvites пассивный агент увеличивает
значение переменной invites на 1.
При получении сообщения Decide пассивный агент оценивает,
достаточно
ли
он
приглашений
получил
для
достижения
порога
недовольства, если да, то он переходит в активное состояние и и сообщает об
этом актору Statistic.
Диаграммы описанных процессов представлены на рисунках 2-2.
40
Рисунок 2.5 – Схема обработки сообщения SendMessage
Рисунок 2.6 – Схема обработки сообщения SendInvites
41
Рисунок 2.7 – Схема обработки сообщения Communication
42
Рисунок 2.8 – Схема обработки сообщения AgentStatus
Рисунок 2.9 – Схема обработки сообщения GetInvites
43
Рисунок 2.10 – Схема обработки сообщения Decide
44
2.5 Реализация алгоритмов на Akka
Создание актора в Akka выглядит следующим образом. Сначала
создается объект с описанием методов и входных параметров Актора. Для
WolfAgent это выглядит следующим образом:
object WolfAgent {
def props(conviction: Double, obduracy: Double, patience: Int): Props =
Props(new WolfAgent(conviction, obduracy, patience))
}
Тут conviction – это значение убедительности агента, obduracy –
значение внушаемости агента, patience – порог активации. В данном случае
не описаны методы, поскольку они уже описаны в свойствах ActiveAgent и
PassiveAgent.
Свойство PassiveAgent создается следующим образом:
trait PassiveAgent {
final case class Communication(power: Double)
final case class AgentStatus()
final case class GetInvites()
final case class Decide()
final case class CheckInvites()
}
Наконец, чтобы актор можно было использовать, необходимо создать
класс, в котором указываются объект WolfAgent и свойство PassiveAgent.
Инициализация класса выглядит следующим образом:
45
class WolfAgent(conviction: Double, obduracy: Double, patience: Int)
extends Actor with ActorLogging with PassiveAgent with ActiveAgent {
var patienceLevel: Int = patience
var active: Boolean = false
var invites = 0
var connections: Vector[ActorRef] = Vector()
def receive = {…}
}
Данный
класс
наследуется
от
класса
Actor,
а
ActorLogging,
PassiveAgent и ActiveAgent являются классами-свойствами trait. Trait – класс,
который создан для того чтобы добавляться к другим классам.
Актор
обязательно
приходящих
сообщений.
должен
содержать
Сообщения
receive
обрабатываются
для
обработки
с
помощью
сопоставления с шаблонами case. Шаблон _ является универсальным, этот
случай сопоставления присутствует для принятия сообщений, которые не
были запланированы программистом.
def receive = {
case SendMessage(agent) => {…}
case Communication(power) => {…}
case SendInvites() => {…}
case GetInvites() => {…}
case Decide() => {…}
case _ => {
log.error("Wolf error")
}
}
Из-за того, что Akka обеспечивает параллельные вычисления, иногда
приходится прибегать к методам синхронизации программы. Это можно
сделать 2 способами.
46
Для использования акторов в программе для начала необходимо
создать ActorSystem. Делается это так:
val system: ActorSystem = ActorSystem("actorSystem")
ActorSystem передается идентификатор, потому что таких систем
одновременно может быть создано несколько.
Первый способ синхронизации – использование таймера, не самый
надежный способ, но иногда его можно использовать. Можно запланировать
отложенное сообщение актору следующим образом:
system.scheduler.scheduleOnce(1.second, dispatcher, Protest())
Здесь system – ранее созданный экземпляр ActorSystem, dispatcher –
ссылка на актор, а Protest() – значение сообщения для этого актора.
Второй способ синхронизации – это использовать future. Future –
структура данных, используемая для получения результата вычисления
конкурентной операции. Для получения результата из future можно
использовать Await.result. Использование этой конструкции блокирует
исполнение того потока, в котором вызван Await.result, пока в future не
придет ответ от актора.
implicit val timeout = Timeout(1 seconds)
val future = agent ? AgentStatus()
val result = Await.result(future, timeout.duration).asInstanceOf[Boolean]
Для отображения хода моделирования был сделан актор Statistic, в этот
актор передается количество пассивных агентов на конец шага, а так же
пассивные агенты передают информацию о том, когда они переходят в
активное состояние. Описание актора статистики представлено ниже.
object Statistic {
def props(): Props = Props(new Statistic)
final case class Start()
final case class Activated(who: String)
final case class AddHistory(passive: Int)
final case class GetStatistic()
47
}
class Statistic extends Actor with ActorLogging{
import Statistic._
var statByName: mutable.Map[String, Int] = mutable.Map[String, Int]()
var history: Vector[Int] = Vector()
val startTime = System.currentTimeMillis()
def receive = {
case Activated(who: String) => {
if(!statByName.contains(who)) {
statByName(who) = 1
}
else {
statByName(who) = statByName(who) + 1
}
}
case AddHistory(passive: Int) => {
history = history :+ passive
}
case GetStatistic() => {
println(history.toString())
println(statByName.toString())
println(System.currentTimeMillis() - startTime)
}
case _ => {
log.info("Statistic Error")
}
}
}
48
3 ПРОВЕДЕНИЕ ЭКСПЕРИМЕНТА С ИСПОЛЬЗОВАНИЕМ
ПРОГРАММНОГО СРЕДСТВА
3.1 Реализация программы
Программа
реализована
на
языке
Scala
в
виде
консольного
приложения. Для выполнения требования возможности использования
модели в сторонней среде разработки, была реализована работа с моделью в
среде Intellij IDEA. Параметры модели заданы в переменных, а результат
выводится в консоль среды разработки. Среда Intellij IDEA позволяет
использовать точки остановки программы, чтобы подробнее проследить за
процессом моделирования и принятия решений. На рисунке 3.1 изображены
значения входных данных.
Рисунок 3.1 – Входные данные
В программе реализована возможность перебора входных параметров,
заданных в виде массива. После запуска программа выводит в консоль для
каждого сочетания входных параметров результат в виде истории количества
пассивных агентов после каждого шага цикла, количество активированных
агентов
в
каждом
кластере
и
время
исполнения.
Среднее
время
моделирование равно 1.2 секунды. На рисунке 3.2 изображен фрагмент
вывода результата
49
Рисунок 3.2 – Фрагмент вывода программы
3.2 Проведение эксперимента
Проведем эксперимент для модели со следующими зафиксированными
входными данными:
 количество тактов моделирования равно 50;
 общее количество агентов равно 1000;
 порог недовольства агентов в кластере волки равен 2;
 порог недовольства агентов в кластере зайцы равен 7;
 убедительность агентов в кластере зайцы равна 0.
Десять следующих параметров представлены как факторы:
 численность агентов в кластере лисы;
 численность агентов в кластере волки;
 численность агентов в кластере собаки;
 порог недовольства в кластере собаки;
 убедительность агентов в кластере лисы;
 убедительность агентов в кластере волки;
 убедительность агентов в кластере собаки;
50
 внушаемость агентов в кластере волки;
 внушаемость агентов в кластере собаки;
 внушаемость агентов в кластере зайцы.
Описанные факторы и зафиксированные параметры представлены в
таблице 3.1. Агенты в кластере лисы не имеют порога недовольства и
внушаемости, поскольку они с самого начала моделирования являются
активными агентами. Откликом модели будем считать количество активных
агентов на конец процесса моделирования.
Таблица 3.1 – Входные данные для модели
Название
Численность
Порог
кластера
кластера
недовольства
Лисы
F=5..50
-
Fu=40..90
-
Волки
W=30..100
Wn=2
Wu=20..70
Wv=30..70
Собаки
D=200..400
Dn=3..6
Du=10..50
Dv=20..50
Rn=7
Ru=0
Rv=10..30
Зайцы
R=1000-сумма
(F+W+D)
Убедительность Внушаемость
Целью эксперимента является определение влияния факторов на рост
количества активных агентов.
Для достижения поставленной цели необходимо выполнить следующие
задачи:
1) Провести полный факторный эксперимент плана 2K
2) Вычислить главные эффекты факторов
3) Вычислить парный эффект двух факторов с наибольшим влиянием
4) Провести перебор двух факторов с наибольшим влиянием,
остальные зафиксировать
5) Получить поверхность реакции
6) Построить метамодель
51
Для проведения полного факторного эксперимента плана 2 K будем
изменять значения факторов от минимального до максимального уровня, то
есть рассмотрим 2 значения для каждого из 10 факторов.
При
выполнении
полного
факторного
эксперимента
плана
2K
проводится 2K прогонов модели с зафиксированными параметрами в
минимальном или максимальном значении уровня. Поскольку для 10
факторов количество точек плана будет равно 1024, результаты эксперимента
приведены в таблице А.1. В таблице 3.2 приведен пример матрицы
эксперимента для плана 23.
Таблица 3.2 – Матрица эксперимента для плана 23
Комбинация
факторов
(точка плана)
Фактор 1
Фактор 2
Фактор 3
Отклик
1
–
–
–
R1
2
–
–
+
R1
3
–
+
–
R1
4
–
+
+
R1
5
+
–
–
R1
6
+
–
+
R1
7
+
+
–
R1
8
+
+
+
R1
Главным эффектом фактора является средняя величина изменений в
отклике с уровня «–» на уровень «+». Эта средняя величина берется для всех
комбинаций уровней факторов. Для вычисления главного эффекта одного
фактора необходимо сложить все отклики, взятые с определенным знаком, и
разделить на количество точек плана. В том случае, когда используется «–»
уровень, отклик берется со знаком минус, а когда используется уровень «+»,
отклик берется со знаком плюс. Эта формула записана ниже:
52
(3)
где N –
количество точек плана;
Ri –
отклик i-ой точки плана;
xij –
значение уровня фактора, -1 для нижнего уровня и 1 для верхнего
уровня.
В результате получим следующие главные эффекты:
 фактор «численность агентов в кластере лисы» имеет главный
эффект равный 191,76;
 фактор «численность агентов в кластере волки» имеет главный
эффект равный 49,59;
 фактор «численность агентов в кластере собаки» имеет главный
эффект равный 14,05;
 фактор «порог недовольства в кластере собаки» имеет главный
эффект равный -80,11;
 фактор «убедительность агентов в кластере лисы» имеет главный
эффект равный 48,45;
 фактор «убедительность агентов в кластере волки» имеет главный
эффект равный 39,48;
 фактор «убедительность агентов в кластере собаки» имеет главный
эффект равный 54,84;
 фактор «внушаемость агентов в кластере волки» имеет главный
эффект равный -33,11;
 фактор «внушаемость агентов в кластере собаки» имеет главный
эффект равный -40,30;
 фактор «внушаемость агентов в кластере зайцы» имеет главный
эффект равный -8,95.
Сравнительный анализ факторов показывает, что наибольшее влияние
на значение отклика оказывают факторы «численность агентов в кластере
53
лисы» и «убедительность агентов в кластере собаки», 191,76 и 54,84
соответственно.
Поскольку система является сложной, необходимо рассчитать эффект
парного взаимодействия для выделенных факторов. Эффект взаимодействия
факторов рассчитывается как половина разности между средним эффектом
фактора j1, когда фактор j2 находится на уровне «+», и средним эффектом
фактора j1, когда фактор j2 находится на уровне «–». Для получения того, с
каким знаком необходимо взять значение отклика, необходимо перемножить
знаки уровней взятых факторов. В том случае, когда знаки разные, отклик
необходимо взять со знаком –, а когда знаки одинаковые, отклик берется со
знаком +. Формула представлена ниже:
(4)
где N –
количество точек плана;
Ri –
отклик i-ой точки плана;
xij –
значение уровня фактора, -1 для нижнего уровня и 1 для верхнего
уровня;
xik –
значение уровня фактора, -1 для нижнего уровня и 1 для верхнего
уровня.
В результате эффект взаимодействия факторов «численность агентов в
кластере лисы» и «убедительность агентов в кластере собаки» равен 54,73.
Будем перебирать значения факторов «численность агентов в кластере
лисы» и «убедительность агентов в кластере собаки» с шагом 5. Фактор
«численность агентов в кластере лисы» будем перебирать в диапазоне от 5 до
50, фактор «убедительность агентов в кластере собаки» будем перебирать в
диапазоне от 10 до 50. Остальные факторы зафиксируем на верхнем уровне.
В результате перебора были получены значения отклика и построена
поверхность реакции, изображенная на рисунке 3.3. Эта поверхность
является нелинейной и максимальное количество активных агентов, равное
662, достигается при значениях факторов «численность агентов в кластере
54
лисы» и «убедительность агентов в кластере собаки» равных 50. На рисунке
3.4 изображена контурная карта поверхности реакции.
В качестве первого приближения построим метамодель в виде
неполной квадратичной регрессии. Формулы уравнения представлены ниже:
,
(5)
,
(6)
,
(7)
,
(8)
,
где
–
(9)
средний отклик для всех точек плана;
ej –
главный эффект фактора «численность агентов в кластере лисы»;
ek –
главный эффект фактора «убедительность агентов в кластере
собаки»;
ejk –
эффект
парного
взаимодействия
для
выделенных
факторов
«численность агентов в кластере лисы» и «убедительность агентов в
кластере собаки».
55
Рисунок 3.3 – График поверхности отклика
56
Рисунок 3.4 – Контурная карта поверхности реакции
57
В результате получим следующие значения:

значение b0 равно 198,67;

значение bj равно 95,88;

значение bk равно 27,42;

значение bjk равно 27,36.
Теперь подставим эти значения в регрессионную модель и получим
следующее уравнение:
(10)
Анализ уравнения 10 свидетельствует о том, что наибольшее влияние
оказывает фактор «численность агентов в кластере лисы», что подтверждает
значение главного эффекта фактора, равное 191,76.
При рассмотрении графика на рисунке 3.3 можно понять, что линейной
модели может оказаться недостаточно. Поэтому построим нелинейную
модель парной регрессии. Формула уравнения представлена ниже:
(11)
Выполним
линеаризацию
переменных
и
введем
следующие
обозначения:
z1 =
; z2 =
; z3 =
; z4 =
.
Тогда уравнение 11 примет вид:
(12)
Уравнение (12) представляет собой уравнение линейной регрессии с
четырьмя независимыми переменными. Коэффициенты такого уравнения
находятся по следующей формуле:
(13)
где A = (a0, a1, a2, a3, a4) – вектор оценок параметров регрессии;
Y = (y1, y2, …, yn) –
вектор значений отклика;
Z-
матрица значений независимых переменных.
В результате получим следующие значения оценок параметров:
a0 = 46,79; a1 = -9,53; a2 = 0,49; a3 = 0,36; a4 = 0,01.
58
Теперь подставим эти значения в уравнение:
(14)
Проверим адекватность полученной модели нелинейной парной
регрессии. Оценить адекватность модели позволяет анализ случайной
компоненты, которая представляет собой разность между фактическим
значением и значением, рассчитанным по уравнению регрессии:
(15)
где n –
количество испытаний;
–
фактическое значение;
–
рассчитанное значение.
Модель является адекватной процессу, если математическое ожидание
значений остаточного ряда близко или равно нулю, значения остаточного
ряда
случайны,
независимы
и
подчинены
нормальному
закону
распределения.
1. Равенство нулю математического ожидания ряда остатков означает
выполнение следующего соотношения:
(16)
2.
Проверка случайности последовательности ei проводится с
помощью критерия пиков. Каждый уровень ряда (ei) сравнивается с двумя,
рядом стоящими. Точка считается поворотной, если она либо больше и
предыдущего и последующего значения, либо меньше и предыдущего и
последующего значения. В случайном ряду должно выполняться строгое
неравенство:
,
где p –
3.
(17)
количество поворотных точек.
Независимость
значений
остаточного
ряда
(отсутствие
автокорреля-ции) проверяется с помощью d-критерия Дарбина–Уотсона:
59
,
(18)
Эта величина сравнивается с двумя табличными уровнями: нижним –
d1 и верхним – d2. Для 90 точек плана и 2 независимых факторов d1 равно
1,63 и d2 равно 1,72.
4.
Соответствие остаточного ряда нормальному распределению
проще всего проверять при помощи RS-критерия
,
(19)
где emax – максимальный уровень ряда остатков;
emin – минимальный уровень ряда остатков;
S–
среднеквадратичное отклонение.
В таблице 3.3 представлены значения границ для RS-критерия.
Таблица 3.3 – значения границ для RS-критерия
Нижние границы
Верхние границы
Вероятность ошибки
n
0,000 0,005 0,01 0,025 0,05
0,1
0,1
0,05 0,025 0,01 0,005 0,000
4,7
30 1,966
3,21
3,27
3,37
3,47 3,59
4,89
5,06
5,26
5,4
7,62
40 1,975
3,41
3,47
3,57
3,67 3,79 4,96 5,16
5,34
5,56
5,71
8,83
50
1,98
3,56
3,62
3,73
3,83 3,95 5,14 5,35
5,54
5,77
5,93
9,9
60 1,983
3,68
3,75
3,86
3,96 4,08 5,29 5,51
5,7
5,94
6,1
10,86
70 1,986
3,79
3,85
3,96
4,06 4,19 5,41 5,63
5,83
6,07
6,24
11,75
80 1,987
3,88
3,94
4,05
4,16 4,28 5,51 5,73
5,93
6,18
6,35
12,57
90 1,989
3,96
4,02
4,13
4,24 4,36
6,03
6,27
6,45
13,34
5,6
5,82
Для формул 16-19 получились следующие значения:
(20)
(21)
(22)
(23)
60
Исходя из полученных результатов, можно сделать вывод, что модель
нелинейной парной регрессии имеет математическое ожидание ряда остатков
равное нулю, недостаточное количество поворотных точек, d-критерий
меньше d1, что свидетельствует о наличии зависимости значений друг от
друга, RS-критерий находится в допустимых границах.
В результате проведенных испытаний можно сделать вывод, что
имеющаяся модель социальной напряженности достаточно сложна, чтобы ее
можно было выразить в виде линейного или нелинейного уравнения парной
регрессии.
61
ЗАКЛЮЧЕНИЕ
В
результате
выполнения
данной
работы
была
разработана
программная подсистема моделирования социальной напряженности.
В ходе выполнения работы были выполнены следующие задачи:
1)
была описана и проанализирована предметная область, дано
определение социальной напряженности, выделены кластеры агентов по
общим характеристикам;
2)
был выполнен обзор прототипов разрабатываемой модели,
проведено
сравнение
задачи
разрабатываемой
модели
с
задачами
прототипов;
3)
была
выполнена
постановка
задачи
для
разрабатываемой
агентной модели;
4)
были
сформулированы
требования
к
разрабатываемому
программному средству;
5)
была описана структура данных и алгоритмы;
6)
было реализовано программное средство для моделирования
поставленной задачи на языке Scala с применением пакета библиотек Akka;
7)
была проведена серия экспериментов и апробация программного
средства.
Таким образом, цель по разработке программной подсистемы
моделирования социальной напряженности можно считать выполненной.
62
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
1. Олькина,
Е.В.
Методические
указания
по
оформлению
пояснительных записок к дипломным, курсовым проектам (работам) и
отчётов по практикам в соответствии с требованиями государственных
стандартов [Текст] / Е. В. Олькина; рецензент О. В. Конюхова. – ОрёлГТУ,
2007. – 54 с.
2. Олькина, Е.В. Методические указания по оформлению электронных
материалов [Текст] / Е.В. Олькина. – ОрёлГТУ, 2010. – 21 с.: ил.
3. Фаулер М. UML. Руководство по унифицированному языку
моделирования [Текст] / Скотт К. – Пер. с англ. – СПб:Символ-Плюс, 2002. –
192 стр.
4. Воронина Н. Д. Социальная напряженность: концептуальная схема
ресурс]
[Электронный
/
Режим
доступа:
https://publications.hse.ru/chapters/92093340 (Дата обращения 31.05.2018).
5. Epstein J. Modeling civil violence: An agent-based computational
approach
ресурс]
[Электронный
/
Режим
доступа:
https://www.uvm.edu/~pdodds/files/papers/others/2002/epstein2002a.pdf
(Дата
обращения 31.05.2018).
6. Bass F. A New Product Growth for Model Consumer Durables [Текст]/
Bass F. // Management Science – 1969 - Vol.15, No. 5.
7. Arthur B. Inductive Reasoning and Bounded Rationality [Текст] / Arthur
B. – Santa Fe Institute, 1994.
8. Индуктивное мышление и ограниченная рациональность[Текст] /
перевод
И.В.
Розмаинского
//
Экономический
вестник
Ростовского
государственного университета – 2003 – том 1 № 3 – С.53-61.
9. Кельтон В., Лоу А. Имитационное моделирование [Текст] / 3-е изд.
— СПб.; Питер: Киев: Издательская группа BHV, 2004, — 847 с.
63
10. Akka, акторы и реактивное программирование [Электронный
ресурс] / Режим доступа: https://habrahabr.ru/company/piter/blog/266103 (Дата
обращения 12.04.2018).
11. Akka
(toolkit)
[Электронный
ресурс]
/
Режим
доступа:
https://en.wikipedia.org/wiki/Akka_(toolkit) (Дата обращения 12.06.2018).
12. Модель
акторов
[Электронный
ресурс]
/
Режим
доступа:
https://ru.wikipedia.org/wiki/Модель_акторов (Дата обращения 12.06.2018).
13. Actor
model
[Электронный
ресурс]
/
Режим
доступа:
https://en.wikipedia.org/wiki/Actor_model (Дата обращения 12.06.2018).
14. Scala Documentation [Электронный ресурс] / Режим доступа:
https://docs.scala-lang.org/tour/tour-of-scala.html (Дата обращения 12.06.2018).
15. Akka Documentation [Электронный ресурс] / Режим доступа:
https://akka.io/docs (Дата обращения 12.06.2018).
64
ПРИЛОЖЕНИЕ А
(обязательное)
Листинг программы
package social.tension
import scala.concurrent.ExecutionContext.Implicits.global
import akka.actor.{Actor, ActorLogging, ActorRef, ActorSystem, Props, Timers}
import akka.pattern.ask
import akka.util.Timeout
import scala.collection.mutable
import scala.concurrent.Await
import scala.util.Random
import scala.concurrent.duration._
trait PassiveAgent {
final case class Communication(power: Double)
final case class AgentStatus()
final case class GetInvites()
final case class Decide()
final case class CheckInvites()
}
trait ActiveAgent {
final case class SendMessage(agent: ActorRef)
final case class SendInvites()
}
object Statistic {
def props(): Props = Props(new Statistic)
65
final case class Activated(who: String)
final case class AddHistory(passive: Int)
final case class GetStatistic()
final case class GetResult()
}
class Statistic extends Actor with ActorLogging{
import Statistic._
var statByName: mutable.Map[String, Int] = mutable.Map[String, Int]()
var history: Vector[Int] = Vector()
val startTime = System.currentTimeMillis()
def receive = {
case Activated(who: String) => {
if(!statByName.contains(who)) {
statByName(who) = 1
}
else {
statByName(who) = statByName(who) + 1
}
}
case AddHistory(passive: Int) => {
history = history :+ passive
}
case GetStatistic() => {
println(history.toString())
println(statByName.toString())
println(System.currentTimeMillis() - startTime)
}
case GetResult() => {
66
sender ! history.last
}
case _ => {
log.info("Statistic Error")
}
}
}
object Dispatcher {
def
props(active:
Vector[ActorRef],
passive:
Vector[ActorRef],
statistic:
ActorRef): Props = Props(new Dispatcher(active, passive, statistic))
final case class Cycle()
final case class Protest()
}
class Dispatcher(active: Vector[ActorRef], passive: Vector[ActorRef], statistic:
ActorRef) extends Actor with ActorLogging with ActiveAgent with PassiveAgent
with Timers {
import Dispatcher._
import Statistic._
var activeAgents: Vector[ActorRef] = active
var passiveAgents: Vector[ActorRef] = passive
val allAgents: Vector[ActorRef] = activeAgents ++ passiveAgents
def receive = {
case Cycle() => {
var activeLength = activeAgents.length
val passiveLength = passiveAgents.length
for(index <- 0 until activeLength) {
val agent = activeAgents(index)
if(passiveLength > 0) {
67
val ind = Random.nextInt(passiveLength)
agent ! SendMessage(passiveAgents(ind))
}
}
for(index <- 0 until passiveLength) {
val agent = passiveAgents(index)
implicit val timeout = Timeout(1 seconds)
val future = agent ? AgentStatus()
val result = Await.result(future, timeout.duration).asInstanceOf[Boolean]
if(result) {
activeAgents = activeAgents :+ agent
activeAgents = activeAgents.distinct
}
}
activeLength = activeAgents.length
var passiveSet = passiveAgents.toSet
for(index <- 0 until activeLength) {
val agent = activeAgents(index)
passiveSet = passiveSet - agent
}
passiveAgents = passiveSet.toVector
statistic ! AddHistory(passiveAgents.length)
sender ! true
}
case Protest() => {
var activeLength = activeAgents.length
for (index <- 0 until activeLength) {
val actor = activeAgents(index)
actor ! SendInvites()
}
68
timers.startSingleTimer("timer",CheckInvites(),500.milliseconds)
}
case CheckInvites() => {
val passiveLength = passiveAgents.length
var activeLength = activeAgents.length
for(index <- 0 until passiveLength) {
val actor = passiveAgents(index)
actor ! Decide()
}
for(index <- 0 until passiveLength) {
val agent = passiveAgents(index)
implicit val timeout = Timeout(1 seconds)
val future = agent ? AgentStatus()
val result = Await.result(future, timeout.duration).asInstanceOf[Boolean]
if(result) {
activeAgents = activeAgents :+ agent
activeAgents = activeAgents.distinct
}
}
activeLength = activeAgents.length
var passiveSet = passiveAgents.toSet
for(index <- 0 until activeLength) {
val agent = activeAgents(index)
passiveSet = passiveSet - agent
}
passiveAgents = passiveSet.toVector
statistic ! AddHistory(passiveAgents.length)
}
case _ => {
log.error("Dispatcher Error")
69
}
}
}
object FoxAgent {
def props(conviction: Double, statistic: ActorRef): Props = Props(new
FoxAgent(conviction, statistic))
}
class FoxAgent(conviction: Double, statistic: ActorRef) extends Actor with
ActorLogging with ActiveAgent with PassiveAgent {
var connections: Vector[ActorRef] = Vector()
def receive = {
case SendMessage(agent) => {
agent ! Communication(conviction)
connections = connections :+ agent
}
case AgentStatus() => {
sender ! true
}
case SendInvites() => {
val length = connections.length
for(index <- 0 until length) {
val actor = connections(index)
actor ! GetInvites()
}
}
case _ => {
log.error("Fox error")
}
70
}
}
object WolfAgent {
def props(conviction: Double, obduracy: Double, patience: Int, statistic:
ActorRef): Props = Props(new WolfAgent(conviction, obduracy, patience,
statistic))
}
class WolfAgent(conviction: Double, obduracy: Double, patience: Int, statistic:
ActorRef) extends Actor with ActorLogging with PassiveAgent with ActiveAgent
{
import Statistic._
var patienceLevel: Int = patience
var active: Boolean = false
var invites = 0
var connections: Vector[ActorRef] = Vector()
def receive = {
case SendMessage(agent) => {
agent ! Communication(conviction)
connections = connections :+ agent
}
case Communication(power) => {
if (power - obduracy > 0.0001) {
patienceLevel -= 1
}
if (patienceLevel == 0 && !active) {
active = true
statistic ! Activated("Wolf")
71
}
}
case AgentStatus() => {
sender ! active
}
case SendInvites() => {
val length = connections.length
for(index <- 0 until length) {
val actor = connections(index)
actor ! GetInvites()
}
}
case GetInvites() => {
invites += 1
}
case Decide() => {
if(!active) {
val rand = Random.nextDouble() * invites
if(rand > patienceLevel) {
active = true
statistic ! Activated("Wolf")
}
}
}
case _ => {
log.error("Wolf error")
}
}
}
72
object DogAgent {
def props(conviction: Double, obduracy: Double, patience: Int, statistic:
ActorRef): Props = Props(new DogAgent(conviction, obduracy, patience,
statistic))
}
class DogAgent(conviction: Double, obduracy: Double, patience: Int, statistic:
ActorRef) extends Actor with ActorLogging with PassiveAgent with ActiveAgent
{
import Statistic._
var patienceLevel: Int = patience
var active: Boolean = false
var invites = 0
var connections: Vector[ActorRef] = Vector()
def receive = {
case SendMessage(agent) => {
agent ! Communication(conviction)
connections = connections :+ agent
}
case Communication(power) => {
if (power - obduracy > 0.0001) {
patienceLevel -= 1
}
if (patienceLevel == 0 && !active) {
active = true
statistic ! Activated("Dog")
}
}
73
case AgentStatus() => {
sender ! active
}
case SendInvites() => {
val length = connections.length
for(index <- 0 until length) {
val actor = connections(index)
actor ! GetInvites()
}
}
case GetInvites() => {
invites += 1
}
case Decide() => {
if(!active) {
val rand = Random.nextDouble() * invites
if(rand > patienceLevel) {
active = true
statistic ! Activated("Dog")
}
}
}
case _ => {
log.error("Dog error")
}
}
}
object RabbitAgent {
74
def props(obduracy: Double, patience: Int, statistic: ActorRef): Props =
Props(new RabbitAgent(obduracy, patience, statistic))
}
class RabbitAgent(obduracy: Double, patience: Int, statistic: ActorRef) extends
Actor with ActorLogging with PassiveAgent with ActiveAgent {
import Statistic._
var patienceLevel: Int = patience
var active: Boolean = false
var invites = 0
def receive = {
case SendMessage(_) => {
}
case SendInvites() => {
}
case Communication(power) => {
if (power - obduracy > 0.0001) {
patienceLevel -= 1
}
if (patienceLevel == 0 && !active) {
active = true
statistic ! Activated("Rabbit")
}
}
case AgentStatus() => {
sender ! active
}
case GetInvites() => {
75
invites = invites + 1
}
case Decide() => {
if(!active) {
val rand = Random.nextDouble() * invites
if(rand > patienceLevel) {
active = true
statistic ! Activated("Rabbit")
}
}
}
case _ => {
log.error("Rabbit error")
}
}
}
object socialTension extends App {
import Dispatcher._
import Statistic._
val cyclesNumber = 50
val foxNumberArray = (5 to 50 by 5).toArray
val wolfNumberArray = Array(100)
val dogNumberArray = Array(400)
val dogPatienceArray = Array(6)
val foxConvictionArray = Array(90)
val wolfConvictionArray = Array(70)
val dogConvictionArray = (10 to 50 by 5).toArray
76
val wolfObduracyArray = Array(70)
val dogObduracyArray = Array(50)
val rabbitObduracyArray = Array(30)
for(
foxNumber <- foxNumberArray;
wolfNumber <- wolfNumberArray;
dogNumber <- dogNumberArray;
dogPatience <- dogPatienceArray;
foxConviction <- foxConvictionArray;
wolfConviction <- wolfConvictionArray;
dogConviction <- dogConvictionArray;
wolfObduracy <- wolfObduracyArray;
dogObduracy <- dogObduracyArray;
rabbitObduracy <- rabbitObduracyArray
){
val rabbitNumber = 1000 - foxNumber - wolfNumber - dogNumber
val wolfPatience = 2
val rabbitPatience = 7
val system: ActorSystem = ActorSystem("actorSystem")
val statistic = system.actorOf(Statistic.props())
var activeAgent: Vector[ActorRef] = Vector()
var passiveAgent: Vector[ActorRef] = Vector()
for(_ <- 0 until foxNumber) {
77
activeAgent = activeAgent :+ system.actorOf(FoxAgent.props(foxConviction,
statistic))
}
for(_ <- 0 until wolfNumber) {
passiveAgent
=
passiveAgent
:+
system.actorOf(WolfAgent.props(wolfConviction, wolfObduracy, wolfPatience,
statistic))
}
for(_ <- 0 until dogNumber) {
passiveAgent
=
system.actorOf(DogAgent.props(dogConviction,
passiveAgent
dogObduracy,
:+
dogPatience,
statistic))
}
for(_ <- 0 until rabbitNumber) {
passiveAgent
=
passiveAgent
:+
system.actorOf(RabbitAgent.props(rabbitObduracy, rabbitPatience, statistic))
}
val dispatcher = system.actorOf(Dispatcher.props(activeAgent, passiveAgent,
statistic))
implicit val timeout: Timeout = Timeout(2 seconds)
for(_ <- 1 to cyclesNumber) {
val future = dispatcher ? Cycle()
val result = Await.result(future, timeout.duration)
}
dispatcher ! Protest()
78
system.scheduler.scheduleOnce(1.second, statistic, GetStatistic())
val future = statistic ? GetResult()
val result = 1000 - Await.result(future, timeout.duration).asInstanceOf[Int]
println(s"$foxNumber
$wolfNumber
$dogNumber
$dogPatience
$foxConviction $wolfConviction $dogConviction $wolfObduracy $dogObduracy
$rabbitObduracy $result")
}
}
79
ПРИЛОЖЕНИЕ Б
Таблица Б.1 – Результаты эксперимента
F
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
W
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
D
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
Dn
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
Fu
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
Wu
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
Du
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
Wy
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
Dy
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
Ry
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
Результат
7
5
5
7
5
5
5
5
7
6
6
6
5
5
5
5
6
9
5
6
5
5
5
5
7
6
5
7
5
7
5
5
5
80
Продолжение таблицы Б.1
F
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
W
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
D
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
Dn
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
6
6
6
Fu
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
Wu
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
Du
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
Wy
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
Dy
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
Ry
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
Результат
5
5
8
10
6
5
6
6
7
8
6
7
6
6
5
7
6
8
5
5
6
7
6
6
6
8
5
5
6
7
5
6
7
5
81
Продолжение таблицы Б.1
F
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
W
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
D
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
Dn
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
Fu
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
Wu
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
Du
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
Wy
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
Dy
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
Ry
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
Результат
7
5
5
5
5
7
5
5
5
5
5
5
5
5
7
6
6
5
5
5
5
7
7
6
7
5
5
5
5
5
5
9
5
7
82
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
400
400
400
400
400
400
400
400
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
3
3
3
3
3
3
3
3
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
7
6
6
5
7
6
5
7
7
6
6
6
6
5
6
6
5
8
6
5
8
6
6
7
5
5
5
9
7
5
6
6
5
5
5
83
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
5
7
5
5
6
6
5
5
6
6
5
5
5
5
5
5
7
10
6
6
6
7
5
5
7
7
13
6
6
6
7
8
8
6
7
84
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
5
6
5
6
8
6
10
12
8
6
7
7
7
9
5
7
11
6
8
6
6
5
5
6
8
5
5
5
5
5
5
6
6
5
5
5
85
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
5
6
5
5
6
5
5
5
5
6
6
5
5
5
5
5
5
6
5
7
5
5
5
6
6
5
6
7
5
8
6
7
5
6
7
86
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
30
30
30
30
30
30
30
30
30
30
30
30
30
30
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
400
400
400
400
400
400
400
400
400
400
400
400
400
400
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
6
6
6
6
6
6
6
6
6
6
6
6
6
6
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
7
6
6
5
6
7
6
5
6
6
8
6
5
6
11
7
8
6
5
5
5
5
5
8
8
6
6
5
5
5
5
6
9
11
6
87
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
7
5
5
9
14
10
11
6
6
5
5
6
9
8
9
5
7
6
8
8
11
8
10
8
9
11
6
8
15
9
5
8
7
7
9
88
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
6
11
11
11
9
6
6
9
9
8
8
7
5
5
5
5
6
10
7
8
5
5
5
5
7
5
9
6
5
5
5
5
23
5
13
89
Продолжение таблицы Б.1
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
5
100 200
6
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
9
5
5
5
5
7
9
9
7
7
9
10
6
8
9
10
7
7
6
8
6
12
9
9
14
6
7
10
6
7
7
6
6
7
7
90
Продолжение таблицы Б.1
5
100 200
6
5
100 200
6
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
8
9
8
7
6
8
5
5
5
5
14
8
7
7
5
6
5
5
11
7
15
8
6
6
5
5
29
12
8
9
8
8
5
5
10
91
Продолжение таблицы Б.1
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
3
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
9
6
11
9
10
7
9
7
9
12
8
7
8
8
10
12
16
10
10
11
11
7
8
12
12
15
17
10
12
6
12
9
8
9
6
92
Продолжение таблицы Б.1
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
5
100 400
6
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
5
5
5
5
8
7
7
9
5
5
5
5
7
12
7
13
5
5
5
5
10
9
12
6
5
5
5
5
8
8
6
8
9
8
5
93
Продолжение таблицы Б.1
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
50
50
50
50
50
50
50
50
50
50
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
30
30
30
30
30
30
30
30
30
30
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
400
200
200
200
200
200
200
200
200
200
200
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
3
3
3
3
3
3
3
3
3
3
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
7
6
5
11
7
6
7
10
7
8
9
5
9
8
8
6
9
9
14
8
9
6
5
10
7
222
201
108
89
173
163
65
62
1000
937
94
Продолжение таблицы Б.1
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
105
92
950
775
59
63
269
264
119
125
184
167
60
67
1000
1000
140
118
950
956
64
64
233
206
217
190
229
194
210
196
1000
896
587
357
988
95
Продолжение таблицы Б.1
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
928
418
281
266
246
265
243
256
240
263
242
1000
1000
717
901
1000
1000
681
583
115
101
111
86
69
71
70
60
128
115
100
86
81
79
62
65
96
Продолжение таблицы Б.1
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
30
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
140
125
129
119
74
72
64
62
157
164
110
120
82
79
64
59
119
100
121
99
117
90
124
103
117
105
132
116
131
94
115
93
134
151
125
97
Продолжение таблицы Б.1
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
200
6
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
157
134
128
142
131
140
163
156
150
137
173
153
129
349
312
101
82
279
303
60
58
1000
1000
97
83
970
970
63
58
436
469
87
105
284
283
98
Продолжение таблицы Б.1
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
57
58
1000
1000
115
121
970
970
61
57
322
314
349
319
347
320
338
313
1000
1000
894
719
1000
1000
851
849
419
389
456
437
425
437
430
419
1000
99
Продолжение таблицы Б.1
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
3
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
1000
1000
1000
1000
1000
1000
1000
108
114
106
75
79
75
58
67
145
135
96
77
89
87
59
63
138
156
103
94
78
74
61
62
244
198
96
100
100
Продолжение таблицы Б.1
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
50
30
400
6
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
99
97
62
57
124
104
136
105
126
112
126
117
125
136
126
115
151
137
129
109
146
125
158
141
146
145
161
136
200
281
189
200
195
189
158
101
Продолжение таблицы Б.1
50
30
400
6
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
149
463
270
280
142
167
177
61
63
1000
1000
303
140
773
811
69
61
876
841
629
644
165
160
66
67
1000
1000
878
691
779
722
59
59
457
265
102
Продолжение таблицы Б.1
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
3
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
399
260
477
246
424
267
1000
1000
983
505
1000
982
826
505
835
887
836
781
516
573
588
557
1000
1000
1000
1000
1000
1000
1000
1000
280
156
362
148
78
103
Продолжение таблицы Б.1
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
73
67
66
316
158
318
146
83
79
63
65
642
558
451
417
77
76
58
61
1000
994
510
442
73
79
61
61
261
145
349
146
303
159
299
148
104
Продолжение таблицы Б.1
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 200
6
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
20
20
20
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
414
165
311
148
314
168
346
177
613
552
660
599
353
356
401
390
1000
868
842
829
561
577
554
461
546
372
225
133
275
290
59
59
1000
1000
248
105
Продолжение таблицы Б.1
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
20
20
20
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
134
900
900
58
64
1000
1000
800
799
290
293
64
57
1000
1000
1000
1000
900
900
62
59
546
370
512
381
597
381
549
382
1000
1000
1000
961
1000
1000
106
Продолжение таблицы Б.1
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
3
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
20
20
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
987
882
1000
1000
1000
1000
811
827
928
841
1000
1000
1000
1000
1000
1000
1000
1000
235
169
243
128
78
83
61
62
351
176
216
127
89
100
60
59
682
107
Продолжение таблицы Б.1
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
40
40
40
40
40
40
40
40
40
40
40
40
40
40
40
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
70
70
70
70
70
70
70
70
70
70
70
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
20
70
70
70
70
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
10
10
10
10
50
50
50
50
50
50
50
50
10
10
10
10
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
70
70
70
70
30
30
30
30
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
20
20
50
50
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
10
30
614
380
377
79
81
53
65
1000
1000
436
426
93
88
56
56
286
156
287
163
278
161
238
162
297
193
297
180
308
185
236
160
691
674
691
610
108
Продолжение таблицы Б.1
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
50
100 400
6
90
90
90
90
90
90
90
90
90
90
90
90
70
70
70
70
70
70
70
70
70
70
70
70
10
10
10
10
50
50
50
50
50
50
50
50
70
70
70
70
30
30
30
30
70
70
70
70
20
20
50
50
20
20
50
50
20
20
50
50
10
30
10
30
10
30
10
30
10
30
10
30
375
388
428
404
1000
1000
977
970
1000
971
507
596
109
110
111
1/--страниц
Пожаловаться на содержимое документа