Оптимизация расписания уроков в школе с помощью генетического алгоритма

Математическая постановка задачи и классификация ограничений

Составление расписания относится к классу NP-трудных комбинаторных задач. Простым перебором решить её для средней школы невозможно, ведь количество комбинаций при десяти классах и сорока педагогах превышает число атомов во Вселенной. Первым шагом тебе нужно строго разделить все условия школьной среды на две группы.

• Жёсткие ограничения делают расписание физически невыполнимым в случае нарушения, поэтому один учитель или один класс не могут находиться одновременно в двух местах, а вместимость кабинета обязана соответствовать размеру группы.
• Мягкие ограничения определяют комфорт и педагогические нормы, включая окна между уроками у преподавателей, равномерное распределение сложных предметов по дням недели и сведение к минимуму переходов между этажами.
• Нормативы СанПиН 1.2.3685-21 задают шкалу трудности предметов, по которой пик недельной нагрузки для школьников должен приходиться на вторник и среду, что тоже переводится в мягкие ограничения.

Кодирование данных и генетические операторы

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

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

Построение фитнес-функции на основе штрафов

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

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

Что проверяет преподаватель

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

Где брать данные для тестирования

Для реалистичного эксперимента запроси в учебной части своей школы анонимизированную тарификационную сетку. Потребуется список классов, перечень учителей с их нагрузкой по часам и номерной фонд кабинетов, включая специализированные лаборатории и спортзалы. Гигиенические нормативы сложности школьных дисциплин возьми напрямую из официального текста СанПиН 1.2.3685-21, где математике, физике и химии присвоены высшие баллы трудности, а музыке и физкультуре — низшие.