Мультиагентная система формирования расписания в вузе

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

Цель данной работы – создание программного обеспечения поддержки принятия решения, позволяющего упростить процесс автоматизированного составления расписания для учебного заведения и минимизировать влияние человека на систему благодаря использованию мультиагентного подхода.

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

Нагорных Максим Эдуардович магистрант. Санкт-Петербургский государственный университет аэрокосмического приборостроения, Санкт-Петербург. Сфера научных интересов: имитационное моделирование; мультиагентные системы; системы поддержки принятия решений; разработка распределенных систем. Автор 7 опубликованных научных работ.

учебного заведения. Также стоит отметить возможность добавления новых ограничений к системе с минимальными изменениями общего алгоритма работы.

Мультиагентная система

Мультиагентный подход подразумевает систему, состоящую из множества взаимодействующих друг с другом самостоятельных вычислительных частей, – так называемых агентов. Мультиагентные системы (далее – МАС) могут решать проблемы, которые сложно или невозможно решить монолитной системой. Каждый агент может включать методические, функциональные, процедурные подходы, алгоритмический поиск или обучение с подкреплением [4; 10].

Агенты в таких системах обладают несколькими важными характеристиками:

• •    Автономность – агенты частично независимы, самосознательны, автономны.

• •    Локальные представления – ни у одного агента нет полного представления о системе, иначе эта система слишком сложна для агента, чтобы использовать знания о ней.

• •    Децентрализация – ни один агент не назначается контролирующим (или система фактически сводится к монолитной системе).

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

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

Мультиагентная система формирования расписания в вузе

Обзор и анализ аналогов

Чтобы определиться с вектором разработки мультиагентной системы поддержки принятия решения при составлении расписания в учебном заведении, необходимо рассмотреть и проанализировать существующие решения, а также выявить их сильные и слабые стороны.

Для анализа выбрано три проекта, выполняющих задачу составления и оптимизации расписания: Magellan, «Ректор – вуз» и «1С: Автоматизированное составление расписания. Университет».

Magellan. Система Magellan позволяет управлять всем учебным процессом, в том числе составлением расписания в различных режимах, а также учитывать план и последовательность преподавания [2]. В программе возможно расставлять приоритеты для занятий, но при формировании расписания не будет учитываться удовлетворенность расписанием преподавателей и студентов. Работает только на системах Windows, что может вызвать трудности при ее использовании.

«Ректор – вуз». Данная программа позволяет составить расписание для учебного процесса. При составлении расписания учитываются только требуемые нагрузки и учебные планы, а удобство расписания и пожелания студентов и преподавателей не учитываются. Также в программе возможно ручное внесение изменений в расписание [3].

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

Главный минус программы заключается в том, что экспортировать расписание можно только в формате docx, xls и html, что может затруднить процесс импорта расписания в другие сервисы учебного заведения. Кроме того, поддержка приложения, как и у предыдущей программы, осуществляется только в системе Windows.

«1С: Автоматизированное составление расписания. Университет». Данная программа позволяет производить составление и оптимизацию расписания в вузе. Программа учитывает учебный план и нагрузки, а также может учитывать наличие некоторых параметров, например, количество окон между парами. Однако она не позволяет учитывать индивидуальные предпочтения участников учебного процесса относительно параметров первых и последних пар, а также окон [1].

Анализ аналогов и формирование требований к разрабатываемой системе

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

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

Используемый стек технологий и архитектура приложения

Для решения поставленной задачи был выбран язык Python из-за его возможности быстрого создания прототипа приложения, кроссплатформенности, широкого набора модулей, позволяющих реализовать мультиагентный подход [6].

Поскольку расписание в вузе имеет много данных и связей, например, группа – преподаватель, группа – предмет, предмет – аудитория, было принято решение использовать две системы управления базами данных – SQLite [5] и Neo4j [8]. SQLite выбрана для хранения готового расписания для каждой из групп, а Neo4j – для хранения зависимостей между объектами предметной области, что позволяет увеличить скорость ее работы.

Для реализации мультиагентной системы на языке программирования Python использовался модуль The Spian, позволяющий создавать параллельные, распределенные и отказоустойчивые системы на основе модели актора [9]. Графический пользовательский интерфейс был реализован средствами библиотеки PyQT [7].

Модули приложения. Разработанное программное обеспечение состоит из девяти основных модулей, каждый из которых решает определенные задачи.

• •    Environment – предназначен для инициализации всех участников системы и параллельного запуска мультиагентной системы, а также для установления параметров работы системы, таких как количество итераций работы и минимальный уровень удовлетворенности группы;

• •    Actorbase – описывает стандартные интерфейсы взаимодействия акторов друг с другом и их методы;

• •    Group_actor – модуль, наследуемый от модуля Actorbase и реализующий его методы;

• •    Buffer – выполняет обработку взаимодействия акторов и принимает решения о замене пар в расписании;

• •    StateMachine – реализует паттерн машины состояний для агента группы и буфера;

• •    Messages – описывает возможные сообщения между группами и их сигнатуру;

• •    Database – позволяет выполнять взаимодействие с базой данных SQLite посредством заготовленных допустимых запросов;

• •    Neo4j – позволяет выполнять взаимодействие с базой данных Neo4jпосредством заготовленных допустимых запросов;

• •    Logger – позволяет вести журнал обо всех происходящих событиях в системе для их дальнейшего анализа.

На Рисунке 1 представлена структурная схема взаимодействия основных компонентов системы.

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

Актор может быть в 6 состояниях: инициализация, старт, анализ своей удовлетворенности, поиск возможных замен, попытка замены пары, ожидание ответа от буфера и со- стояние остановки.

Мультиагентная система формирования расписания в вузе

Рисунок 1. Структурная схема взаимодействия модулей

Кроме того, в системе присутствуют акторы преподавателей, служащие ограничителем при замене пары, – для каждого преподавателя устанавливаются рабочие дни и пары. Без подтверждения возможности проведения пары со стороны преподавателя ни одна замена не будет принята.

Схема взаимодействия акторов системы представлена на Рисунке 2.

Рисунок 2. Схема взаимодействия акторов

Из рисунка видно, что общий алгоритм взаимодействия состоит из 4 основных стадий.

1. Группа, проанализировав свое расписание, посылает буферу лучшую замену на текущей итерации работы.

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

• 3.    Если возможность замены была подтверждена группами, происходит согласование с преподавателем о замене.

• 4.    Результат о попытке замены пары отправляется группе.

Описание сообщений в МАС. Для взаимодействия акторов друг с другом и системой имеется 6 основных типов сообщений:

• •    об инициализации актора, которое служит для передачи актору группы начальных данных;

• •    для запуска актора и начала его работы;

• •    для проверки наличия в своем расписании той или иной пары, которое служит для проверки группами свободной пары для замены в своем расписании;

• •    сообщение о замене пары, подтверждающее возможность переноса пары на другое время;

• •    сообщение о результатах замены конфликтной пары, например, когда группы могут обмениваться временем проведения пары для улучшения удовлетворения обоих;

• •    сообщение об остановке актора.

Демонстрация работы приложения

Интерфейс приложения представлен на Рисунке 3.

P«H»rop pac~*c>**e ■ i3»**wuiMNfpe группы

Mil 1612 1621 1622 1623 1631 1632 1633 1634 1641 1642 1Л1 1712 1721 1722 1723 1731 1732

’мико ребомык д*»а npweeeeiww*

Абрамов АП.

АгмвГА.0 АталуаоаДВ АгеееМП Аграиоесхий А В. Акимом О В Асоло» В-С Аксенов АВ. Александрова В А Алексеем ИА. Алексеева П М АлбижмыНА. Алабушм ДБ АмемЕЭ.

А*ан<*еоВМ

АмврооаВМ АмПП*й|<О СО

Выберите логи

мост ройки Количество итераций            О

Минимальнее удовлетворенность: О

Рисунок 3. Интерфейс разработанного приложения

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

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

Также пользователь имеет возможность настроить коэффициенты удовлетворенности для каждой группы и редактировать рабочие дни преподавателя. Для настройки коэффициентов группы пользователь выбирает требуемую группу из списка, после чего появляется новое окно для редактирования коэффициентов, которое представлено на Рисунке 4.

I • •               Редактор коэффициентов для группы 1632

коэффициент окон:5

коэффициент первой пары:2

коэффициент последней пары:4

коэффициент рабочих дней:2

Закрыть                                 Сохранить

Рисунок 4. Окно настройки параметров для группы

Для настройки рабочих дней преподавателя требуется также выбрать требуемый пункт из списка, после чего появляется окно для редактирования рабочих дней (см. Рисунок 5). Следует отметить наличие возможности добавления рабочих дней и их удаления.

• • •	Редактор рабочих дней преподавате^		1Я Абрамов А.П.
1 2 3 5 в 7 8 9	Тип недели        День Верхняя      Понедельник Верхняя      Понедельник Верхняя      Понедельник Верхняя      Понедельник Верхняя      Понедельник Верхняя      Понедельник Верхняя      Понедельник Верхняя      Вторник Верхняя      Вторник	Номер пары 2 3 4 5 6 7 8 1 2
	Удалить		Добавить
	Закрыть		Сохранить                   I

Рисунок 5. Окно настройки рабочих дней преподавателя

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

Для проверки работы программы было взято расписание Санкт-Петербургского государственного университета аэрокосмического приборостроения.

На Рисунке 6 представлено исходное расписание для группы, а на Рисунке 7 – расписание по итогам работы мультиагентной системы. Оно содержит меньше рабочих дней и вечерних пар – субботние пары ушли, как и поздняя пара в пятницу. На вход системы подавалось 457 групп с их расписанием за семестр, число итераций устанавливалось 4, а время работы – 5 минут.

КП б»"” ^41 Верхняя Пятгжьа Верхняя Суббота

Оптичеоже осте»м амии

Оптические остам амии

Лазеруме информа^юнгме остены кооычесжих алл... Оптические системы свези

Теория и проектирование акустоолтоэлектрогямх ус...

Технология производства лазерумх остей Технология производства лазерумх систем Лазеруме остам опеина/мюго нахачетя

Лазеруме остам о«1»«ап>мого махаметя«я Лазеруме пнформааояме остам кооычеомх ат... Лазер*ме остам покажу и нави^- au»*i Лазеруме системы локасаи и мавигмаы Лазеруме системы локасды и навит асм« Лазеруме остеум локаие* и навитaix<

Лазеруме »ыфорнас»«онуме остам кооятчесхих ат...

Теория и проектирование акустоопт оэлектроуямх ус..

Техно погни производства лазерумх остей Технология производства лазерумх систем Теория и лроектмровагые акустооптоалектро*»мх ус...

^SgKAjnggmgog^^

faulting БК.

БК.

Б.М.

Б.М.

Б.М. БК. БК.

Е

БК.

Гаст. Гаст. Гаст. Гаст. Б.М.

6М

БК.

Б.М.

Б.М.

технологических коатлек... Б.М.

Лазеруме остам cnei»«a/Mioro нахачвыя

51-06-03 514)643 514)643 514)64)3 514645 13-17

514643 144)2

Пресленев ЛК.

Преслемев Л.м.

ШаюыО.В.

Шакин О.О.

Казаков 8.И.

Петров ПК Лебедева.®. Лебедев В.Ф. Рыжиков МЛ.

1442 514643 1*42 144)2

1442 144)2 514643

514643 514)64)5 13-17

514643 13-15

Рыжжов М.Б.

Шакин ОЛ.

Митько А.8.

Метько А.8.

Митько АЛ.

Митько А.8.

ШакжОЛ.

КазжовВ.И.

Петров ПК. Лебедев В, Ф Лебедеве.®.

Петров П.Н.

514645 Петров П.Н.

1446е

Ноаесос А.Е.]

Рыжиков M.f

Рисунок 6. Исходное расписание группы

wee*.	day_of_week	par....	раг^..	раг_пате	bui*TQ	audence	teacher
певве	Втор***-	5	ПР	Оптичеооте остены амии	БК.	32-02	Пресленев Л.Н.
УХ.ЖНЯЯ	Втормуес	6	Л	Отпичеоос ост сум связи	БК.	514)64)3	г^зесленев Л.Н.
ЬЫжняя	Среда	1	л	Лазеруме информационные остены космучеосих ат...	БК.	51-064)3	Шакин О.В.
м । ее j	Среда	2	ГР	Лазерные информаи<оу*ме системы коо*<ческих ат...	БК.	51-064)3	Шакт0.В.
1-Нжмяя	Среда	3	ГР	Оптические остеум связи	БК.	51-064)3	Казаков 8.и
Ь*ОГМЯЯ	Среда	4	ГР	Теория и проекпиование акустооптозластроу*мх ус.,.	БК.	51464)5	Петров ПК.
►NIMBI	Четверг	4	ГР	Техуслогия производства лазерных систем	БК.	13-17	Лебедев 8®.
ЬМжмяя	Четверг	5	ПР	Технология производства лазерумх систем	БК.	514)643	Лебедев В.®.
ЬЪокняя	Пятница	5	л	Лазеруме остсум спеииал>ного назначения	Гаст.	1442	РьоюясовМ.Б.
| Верхняя	Понедельумс	3	ПР	Лазеруме остсум спеииа^ного назначения	Гаст.	1442	Рыжжов М.Б. |
Верхняя	Пятужуа	5	ЯР	Лазерные остены спеика/мсго назначения	Гаст.	1442	Рыжиков М.Б.
Верхняя	Понедельна	2	ПР	Лазеруме ннформаииоу*ме остеум коо*«чеосих ат...	Б.М.	514643	ШакжО.В.
Верхняя	Втоомс	1	л	Лазеруме остены пока»** и маемгаи**	гест.	1442	Ноьао А.В.
Ввдеве	8ГОШ№	2	ЯР	Лазеруме остены покат»** и навитau*i	Гаст.	1442	Митько А.В.
Верхняя	Вт сем.*	3	ПР	Лазеруме остеум покатаы и навитаие*	гаст.	1442	Митько А.6.
Верхняя	Вт орну*:	4	ПР	Лазерные остетм локзси* и навитai»*<	Гаст.	1442	ЬБпько АЛ.
Верхняя	Сред ■	2	ПР	Лазеруме информаисуеме остены коожчеосих ат...	Б.М.	514643	ШвоатОЛ.
Верхняя	Среда	3	ЛР	Оптичеоа* остеум ашж«	БК.	514)643	Казаков 8К
Верхняя	Среда	4	ГР	Теория и проектированее акустооптоалестроу*мх ус,-	БК.	514645	Петров ПК.
Верхняя	четверг	А	ПР	Технология производства лазерумх остей	БК.	13-17	Лебедев 8®.
Верхняя	чгоег	5	л	Технология производства лазерумх остен	БК.	514643	Лебедев В.®.
Верхняя	Пятужи	3	КР	Теория и проектирование акустооптоалектро»*мх ус...	БК.	13-15	Петров ПК.
Верхняя	Пятктцд	4	л	Теория и проектировау*«е акустоолтозпектромумх ус...	БК.	51-0645	Петров П.Н.
t Верхняя	понедегм**	4	КП	Проекпуованне лазерных технологических конллез ...	6.М,	1446е	ноежооА.Е. 1
(Верхняя;	Понеделтумс	5	ПР	Лазеруме о<сте>м оси«агмюго назначения	гаст.	1442	РыжжовМ.Б. |

Рисунок 7. Расписание группы после завершения работы программы

Мультиагентная система формирования расписания в вузе

При запуске большего числа итераций время выполнения и количество внесенных изменений увеличивается.

Заключение

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

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