Электронный научный журнал 12+

Информационно-коммуникационные технологии
в педагогическом образовании

ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ АВТОМАТИЧЕСКОГО СОСТАВЛЕНИЯ РАСПИСАНИЯ В ВУЗЕ

Раздел: Прикладные задачи искусственного интеллекта

Журнал: Материалы IV Всероссийской научно-практической конференции с междун. участием «ИИ в образовании. Современные достижения и перспективы применения: в генерации знаний, управлении, обучении, оценке результатов обучения и формировании компетенций обучающихся»

26 июня 2025 г.

Авторы: Решетникова Елена Васильевна , Федулов Давыд Викторович

Информационно-коммуникационные технологии в педагогическом образовании, 2025. № 5 (98). infed.ru

_______________________________________________________________________

 

УДК 004

Д. В. Федулов, Е. В. Решетникова

D. V. Fedulov, E. V. Reshetnikova

Федулов Давыд Викторович, магистрант, КГПИ ФГБОУ ВО «КемГУ», г. Новокузнецк, Россия.

Решетникова Елена Васильевна, к. т. н., зав. кафедрой математики, физики и математического моделирования, КГПИ ФГБОУ ВО «КемГУ», г. Новокузнецк, Россия.

Fedulov Davyd Viktorovich, Master's student, Kuzbass Humanitarian Pedagogical Institute of Kemerovo State University, Novokuznetsk, Russia.

Reshetnikova Elena Vasilievna, Candidate of Technical Sciences, Associate Professor, Kuzbass Humanitarian Pedagogical Institute of Kemerovo State University, Novokuznetsk, Russia.

 

ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ АВТОМАТИЧЕСКОГО СОСТАВЛЕНИЯ РАСПИСАНИЯ В ВУЗЕ

STUDY OF THE APPLICATION OF GENETIC ALGORITHMS FOR AUTOMATIC SCHEDULE PREPARATION IN A UNIVERSITY

 

Аннотация. В статье исследуется применение генетических алгоритмов (ГА) для автоматизации составления учебных расписаний в вузах. Проведен сравнительный анализ эффективности ГА с традиционными методами (ручное планирование, алгоритмические подходы). Особое внимание уделено структуре хромосом, фитнес-функциям и адаптации ГА к динамическим условиям.

Annotation. The article examines the use of genetic algorithms (GA) for automating the preparation of educational schedules in universities. A comparative analysis of the effectiveness of GA with traditional methods (manual planning, algorithmic approaches) is carried out. Particular attention is paid to the structure of chromosomes, fitness functions and adaptation of GA to dynamic conditions.

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

Keywords: genetic algorithm, fitness function, chromosome, scheduling.

 

Составление учебного расписания в вузах относится к классу NP-трудных задач комбинаторной оптимизации [1]. Традиционные методы, такие как ручное планирование или использование электронных таблиц, сталкиваются с рядом проблем:

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

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

В таблице 1 представлены основные методы составления расписаний и их характеристики.

                                                                                                                               Таблица 1

                                          Сравнение традиционных методов

Метод

Преимущества

Недостатки

Ручное составление

Гибкость

Высокая трудоемкость

Электронные таблицы

Визуализация данных

Ограниченная автоматизация

Линейное программирование

Точность решений

Сложность реализации

 

Как видно из таблицы, ни один из методов не обеспечивает баланса между скоростью, точностью и гибкостью.

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

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

Наиболее распространенным вариантом хромосомы является список, каждый элемент которого соответствует занятию, которое определяется набором из предмета, группы, аудитории, времени и преподавателя. Чаще этот набор представляет собой кортеж [5, 8] или словарь с такими же ключами [9]. Также хромосому возможно представлять вектором из временных слотов, расположенных по порядку проведения занятий [6, 10]. В этом случае длина кортежа уменьшается. Такие слоты могут располагаться и в двумерной матрице, тогда происходит распределение не только по порядку проведения занятий, но и по дням [12].

Иногда для ускорения работы программы не учитываются отдельные элементы кортежей: привязка к аудитории и проводимый предмет [6] или аудитория и группа [10], преподаватель, ведущий предмет [12].

Особенная модель представлена в [7, 11], хромосома - граф, где узлы соответствуют занятиям, а рёбра – ограничениям, при этом учитываются только тип занятия, предмет и время проведения занятий.

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

Можно отметить, что каждая структура данных выполняет свое предназначение: кортежи/словари подходят для детализированного описания занятий (предмет, группа, аудитория, преподаватель, время проведения занятия), векторы/матрицы эффективны для компактного представления временных слотов и группировки по дням, графы идеальны для учёта зависимостей между занятиями (например, порядок лекций и семинаров).

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

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

.                                               (1)

Каждый исследователь выбирает свой набор критериев оптимизации и присваивает им весовые коэффициенты в соответствии со значимостью каждого критерия для данной задачи. Таким образом, фитнес-функции адаптируются под приоритеты конкретной задачи, комбинируя различные типы нарушений. Это могут быть количество конфликтов (появление в разных кортежах одного временного слота одинаковых объектов) аудиторий, преподавателей или групп [8, 9], количество окон у обучающихся или преподавателей [5], количество нарушений предпочтений преподавателей [8], превышение вместимости аудитории [6], неправильное распределение аудиторий [12], перегрузка обучающихся и преподавателей [10].

По итогам проведенного анализа выявлено, что наилучшей структурой хромосомы для расписания в вузе является список кортежей, дополненный матричной структурой для учета дней недели [12]. В такой структуре скомбинированы преимущества векторного (простота операций) и матричного (учет дней/времени) представлений. Также в этой модели представлена возможность явно задавать связи между занятиями.

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

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

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

  1. Garey R.M., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York : W. H. Freeman and company, 1979. – 338 с. – Текст : непосредственный.
  2. Goldberg D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Boston : Addison-Wesley Pub. Co., 1989. – 412 с. – Текст : непосредственный.
  3. Holland J. H. Adaptation in Natural and Artificial Systems. Аnn-Аrbor : University of Michigan Press, 1975. – 228 с. – Текст : непосредственный.
  4. Mitchell М. An Introduction to Genetic Algorithms. Cambridge : MIT Press, 1998. – 221 с. – Текст : непосредственный.
  5. Burke, E. K. Recent research directions in automated timetabling / E. K. Burke, S. Petrovic – Текст : электронный. // European Journal of Operational Research. – 2002. – Vol. 140, No. 2. – P. 266-280. – URL: https://www.sciencedirect.com/science/article/abs/pii/S0377221702000693?via%3Dihub (дата обращения: 10.10.2024).
  6. Бейкер, К. Р. Компромисс между сжатыми сроками выполнения и задержками в базовой модели планирования / К. Р. Бейкер, Д. Триетч. – Текст : электронный. // Journal of Scheduling. – 2015. – Vol. 18. – P. 45–62. – URL: https://doi.org/10.1007/s10951-014-0394-9 (дата обращения: 27.01.2025).
  7. Lewis, Р. A Survey of Metaheuristic Scheduling Techniques / Р. Lewis. – Текст : электронный. – Лондон: Springer, 2008. – 150 с. – URL: https://orca.cardiff.ac.uk/id/eprint/13966/1/LewisTTSurvey2007.pdf (дата обращения: 01.02.2025).
  8. Abdallah M., Genetic Algorithm for University Course Timetabling // Journal of Scheduling / M. Mahmoud, A. Ramadan // 2017. Т. 20, № 3. С. 145–162. – URL: https://www.ijcaonline.org/research/volume124/number10/elsherbiny-2015-ijca-905408.pdf (дата обращения: 01.02.2025). – Текст : электронный.
  9. Лалеску Л. FET – Free Timetabling Software // Личный сайт разработчика. – 2020. – URL: https://web.archive.org/web/20200711065343/https://lalescu.ro/liviu/fet/ (дата обращения: 27.01.2025). – Текст : электронный.
  10. Липова, Э. Е. Многокритериальный генетический алгоритм оптимизации распределения учебной нагрузки профессорско-преподавательского состава в условиях АСУ вуза / Э. Е. Липова, А. И. Секирин – Текст : электронный. // Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ-2020) : Сборник материалов XI Международной научно-технической конференции в рамках VI Международного Научного форума Донецкой Народной Республики, Донецк, 27–28 мая 2020 года / Редколлегия: Ю. К. Орлов [и др.]. – Донецк: Донецкий национальный технический университет, 2020. – С. 214-218. – URL: https://elibrary.ru/item.asp?id=42907974 (дата обращения: 27.05.2025).
  11. Курилова, О. Л. Применение генетического алгоритма для оптимизации учебного плана / О. Л. Курилова – Текст : электронный. // CyberLeninka. – 2023. – URL: https://cyberleninka.ru/article/n/primenenie-geneticheskogo-algoritma-dlya-optimizatsii-uchebnogo-plana/viewer (дата обращения: 01.02.2025).
  12. Астахова, И. Ф. Составление расписания учебных занятий на основе генетического алгоритма / И. Ф. Астахова, А. М. Фирас – Текст: электронный // Вестник Воронежского государственного университета, 2013. – № 2. – URL: https://masters.donntu.ru/2017/fknt/zadorozhnaia/library/article7_astakhova.pdf (дата обращения: 10.10.2024).

                                                

© Федулов Д. В., Решетникова Е. В., 2025

PDF