Вторушина Софья Александровна | ПРИМЕНЕНИЕ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА И ТЕОРИИ ГРАФОВ ДЛЯ СОСТАВЛЕНИЯ УЧЕБНЫХ РАСПИСАНИЙ

магистрант 1 курса, профиль 

«Менеджмент образования» Института педагогики

и психологии Московского городской

педагогического университета, г. Москва
Е-mail: vtorushinasa029@mgpu.ru 

Научный руководитель: к.п.н., доцент А.Н. Ганичева

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

The author of the article considers the possibilities of artificial intelligence, integrating it with the methods of graph theory. The artificial intelligence resource is viewed from the perspective of genetic algorithms and deep neural network connections and reinforcement learning. By conducting a system analysis, their applicability, computational complexity, and effectiveness in solving the problem of automated scheduling of training sessions are presented. Examples of successful applications of the integration of artificial intelligence and graph theory are presented, the main problems and possible directions of future research are identified.

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

— необходимо обеспечивать равномерную нагрузку на обучающихся;

— учитывать загруженность преподавателей;

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

— обеспечить последовательность изучения дисциплин при модульном построение учебных планов;

— учитывать пожелания педагогов;

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

И.А.Устинов и И.Н.Набродова [3] отмечают, что автоматизация составления учебного расписания остается важной нерешенной проблемой, сложность решения которой определена большими объемами, зависимостью множества переменных друг от друга, значительным количеством субъективных вводных.

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

1. Алгоритм, основанный на оценке свободы расположения.
2. Генетический алгоритм.
3. Логическое программирование в ограничениях.
4. Алгоритм раскраски графов.

С.Н. Зимин связывает задачу раскраски графа с поиском минимального числа цветов, необходимых для раскраски вершин графа таким образом, чтобы каждая пара соседних вершин была окрашена в разные цвета. При этом, «задача поиска хроматического числа представляет собой NP-полную задачу, для решения которой в большинстве случаев используются различные жадные алгоритмы. [2, с. 112]

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

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

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

Задача составления расписания может быть представлена как задача раскраски графа. Пусть \( G = (V, E) \) —  неориентированный граф, где:

— \( V \) — множество вершин, представляющих занятия (лекции, семинары, лабораторные работы), — \( E \) — множество рёбер, соединяющих несовместимые занятия (например, требующие одну и ту же аудиторию или ведущиеся одним преподавателем в один и тот же временной слот).  Задача заключается в нахождении допустимой k-раскраски графа, где каждому занятию (вершине) присваивается цвет (временной слот) так, чтобы никакие два занятия, соединенные ребром, не имели одинаковый цвет.

Второй шаг — расширенные модели графов:  

1. Гиперграфы \( H = (V, E) \) позволяют учитывать многокритериальные зависимости (например, распределение студентов по группам, потребности в лабораторных работах).
2. Двудольные графы \( G = (U, W, E) \) моделируют отношения между преподавателями и курсами, позволяя минимизировать перегрузки.
3. Динамические графы используются в случае необходимости адаптации расписания при изменении условий (например, замены преподавателей).

Третий шаг – использование методов искусственного интеллекта для оптимизации расписаний:  

1. Генетические алгоритмы.

Генетические алгоритмы (GA) представляют собой эвристический метод оптимизации, основанный на принципах эволюции.  Основные этапы работы GA:

— инициализация — генерация случайного набора возможных расписаний;

— функция приспособленности — оценка качества расписания (например, число конфликтов и перегрузок);

— скрещивание — комбинирование успешных расписаний для получения новых решений;

— мутация — случайные изменения, добавляющие вариативность;

— выбор — сохранение лучших расписаний для следующего поколения.

Генетические алгоритмы по мнению E. K. Burke и J. P. Newall успешно применяются для решения задач с жесткими и мягкими ограничениями, но их вычислительная сложность возрастает при увеличении количества параметров [4].

2. Глубокие нейронные сети.

Глубокие нейросетевые модели могут анализировать исторические данные и предсказывать оптимальные комбинации временных слотов. Их основные архитектуры представлены как:

— рекуррентные нейросети (RNN) позволяют учитывать зависимость последовательности занятий;

— графовые нейронные сети (GNN) обеспечивают улучшение раскраски графов;

— трансформеры могут анализировать сложные взаимосвязи между занятиями и ресурсами.

Использование искусственных нейронных сетей значительно ускоряет процесс создания расписаний и способствует снижению вероятности возникновения конфликтов в расписаниях.

3. Метод обучения с подкреплением.

Метод обучения с подкреплением (Reinforcement Learning, RL) заключается в том, что агент (в данном случае алгоритм) учится через взаимодействие с окружающей средой и получение наград за правильные действия  [5].

Ключевые алгоритмы RL включают:

— Deep Q-Networks (DQN) — применение нейросетей для анализа и оценки текущего состояния расписания;

— Proximal Policy Optimization (PPO) — гибкая оптимизация расписания с учетом текущих условий. Метод обучения с подкреплением особенно ценен в условиях, когда входные данные могут быть подвергнуты изменениям (например, при отмене занятий), поскольку он позволяет эффективно адаптироваться к таким изменениям.

К успешным примерам применения можно отнести:

— OptaPlanner — коммерческая платформа, которая использует интеллектуальные эвристики и методы работы с графами для разработки расписаний;

— университеты США и Европы — внедрение AI-технологий позволило сократить время на разработку расписаний на 40% и уменьшить количество конфликтов на 25%;

— школы Японии — применение интегрированных AI-моделей дало возможность учитывать личные предпочтения учащихся и педагогического состава [1].

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

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

 

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

 

1. Всеобъемлющий обзор графовых нейронных сетей / Ч. У С. Пан, Ф. Чэнь, Г. Лун, Ц. Чжан, П. С. Ю // IEEE Transactions on Neural Networks and Learning Systems. 2021. Т. 32, № 1. С. 4–24. (дата обращения 09.03.2025)
2. Зимин С.Н. Составление учебного расписания, используя теорию графов /С.Н.Зимин //Современные наукоемкие технологии. 2007. № 11. С. 89-90.
3. Устинов И.А., Набродова И.Н. Анализ существующих алгоритмов для составления расписаний занятий /И.А. Устинов, И.Н.Набродова. //Известия ТулГУ. Технические науки. 2022. № 3. С. 109-112.
4. Burke E. K., & Newall, J. P. (2004). A hybrid evolutionary approach to the university timetabling problem. // Computers & Operations Research. 2004. Т. 31. № 12. С. 1793–1814. (дата обращения 06.03.2025)
5. Sutton R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press. Кембридж (Массачусетс): MIT Press, 2018. 552 с. URL: https://mitpress.mit.edu/9780262039246/reinforcement-learning/ (дата обращения 03.03.2025)