АВТОМАТИЗИРОВАННАЯ СИСТЕМА СОСТАВЛЕНИЯ РАСПИСАНИЯ ЗАНЯТИЙ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Введение

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

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

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

Основная часть

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

Жесткими ограничениями являются:

1. Уникальность использования ресурсов:

• Один учитель не может вести два урока одновременно
• Один класс не может находиться на двух уроках одновременно
• Один кабинет не может использоваться для разных занятий одновременно

2. Соблюдение учебного плана:

• Количество часов по каждому предмету в классе соответствует учебному плану

3. Технические ограничения:

• Продолжительность урока фиксирована
• Урок не может выходить за пределы учебного дня

Мягкие ограничения

Выполнение мягких ограничений желательно, но они могут нарушаться с определенным штрафом:

1. Равномерная нагрузка на учителей в течение недели
2. Отсутствие «окон» в расписании учителей и классов
3. Проведение уроков в предпочтительное время
4. Соответствие кабинета требованиям предмета
5. Учет предпочтений учителей

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

где для каждого мягкого ограничения, индексированного k:

- ω_k — вес (важность) ограничения,

- P_k — штраф, налагаемый при нарушении мягкого ограничения.

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

Методы решения:

Для решения задачи был выбран генетический алгоритм, так как:

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

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

Схема компонентов и потоки данных

Все части генетического алгоритма представляются в виде последовательно соединённых блоков:

1. Инициализация начальной популяции
2. Блок оценки приспособленности (фитнес-функция)
3. Оператор селекции (отбора)
4. Оператор скрещивания (кроссинговер)
5. Оператор мутации
6. Блок формирования новой популяции

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

Блок инициализации

На вход блока инициализации подаётся множество параметров задачи:

X=(x1,x2,...,xn),

где xi– значения переменных оптимизации (например, границы диапазонов, типы данных и т.д.).

На выходе формируется начальная популяция:

P₀={p1,p2,...,pm},

где:

m – размер популяции,

каждый pj – хромосома (допустимое решение задачи).

Блок оценки приспособленности (формализуется математически)

Для каждой хромосомы вычисляется значение фитнес-функции:

F(pj)→R,

где F(pj) – числовая мера качества решения pj.

Этот блок имеет полную математическую формализацию. Значение Fj​ передаётся в оператор селекции.

Оператор селекции (формализуется математически)

На основе полученных значений фитнес-функции строится вероятностное распределение отбора:

Q(pj)=F(pj)∑k=1mF(pk),

где Q(pj)– вероятность выбора хромосомы pj для участия в скрещивании.

Оператор скрещивания (частичная формализация)

С заданной вероятностью Pcross​ выполняется обмен участками хромосом:

crossover(pa,pb)→(pa′,pb′)

Математическое описание (для бинарного представления):

• Выбирается точка разрыва t (или несколько точек)
• Обмениваются фрагменты после точки разрыва

Представление данных через переменные:

• pa,pb– родительские хромосомы на входе
• pa′,pb′– дочерние хромосомы на выходе
• Множество хромосом до скрещивания: Ptbefore
• Множество хромосом после скрещивания: Ptafter

Оператор мутации (частичная формализация)

С заданной вероятностью Pmut выполняется изменение элементов хромосомы:

mutate(p)→p′

Математическое описание (для битового представления):

• Для каждого бита bi с вероятностью Pmut выполняется bi:=1−bi

Представление данных через переменные:

• p – хромосома на входе
• p′ – изменённая хромосома на выходе

Блок формирования новой популяции (частичная формализация)

Новая популяция Pt+1​ формируется путём слияния лучших особей из предыдущей популяции и полученных потомков. Правило элитизма:

Pt+1={лучшие k из Pt}∪{потомки},

где k – заданное число элитных особей, сохраняемых без изменений.

Представление данных через переменные:

• Pt – текущая популяция
• Pt+1​ – популяция следующего поколения

Итоговая формализация

Таким образом:

Компонент	Математическая формализация	Представление данных
Фитнес-функция	Полная (F(pj))	Числовые значения Fj
Селекция	Полная (Q(pj))	Вероятности отбора
Скрещивание	Частичная (оператор crossover)	Множества Ptbefore,Ptafter
Мутация	Частичная (оператор mutate)	Переменные p,p′
Формирование популяции	Частичная (правило элитизма)	Множества Pt,Pt+1

 

Детализация Входных Данных (Параметров Модели):

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

• Учебный план: Точное количество часов для каждого класса по каждому предмету, разбивка на группы (если есть).
• Сведения об учителях: Список учителей, их предметы, предпочтения по временным слотам, ограничения по максимальной/минимальной нагрузке.
• Сведения о классах: Количество учеников, особенности (например, класс с углубленным изучением чего-либо).
• Сведения об аудиториях: Вместимость, специализация (химкабинет, спортзал, компьютерный класс), доступность (например, кабинет закрыт на ремонт).
• Доступные временные слоты: Точное время начала и окончания каждого урока, количество уроков в день, выходные дни.

Настройка Жестких Ограничений

• Проверка на полноту: Учтены ли все абсолютно нерушимые правила конкретной школы.
• Уточнение условий: Если предмет требует специализированной аудитории.

Ключевой Этап: Адаптация и Весовая Настройка Мягких Ограничений (Минимизация Штрафов): это самый важный этап, определяющий качество и "удобство" расписания. Мягкие ограничения превращаются в штрафы, и их весовые коэффициенты ω_k должны быть тщательно подобраны.

Идентификация всех желаемых условий: совместно с представителями школы выявляются все пожелания.

• Минимизация "окон" (свободных периодов) для учителей: Учителя предпочитают работать без долгих перерывов между уроками.
• Штраф за каждое "окно" (период, когда учитель свободен между двумя уроками).
• Минимизация "окон" для классов/учащихся: Учащиеся также предпочитают компактное расписание без длинных перерывов.
• Штраф за каждое "окно" в расписании класса.
• Равномерное распределение нагрузки: Распределение сложных или требующих концентрации предметов в течение недели (не ставить подряд много математики).
• Штраф за слишком много уроков одного типа подряд.
• Предпочтения учителей/классов: Учет пожеланий учителей относительно определенных дней или времени для своих уроков.
• Распределение уроков по дням: Избегание слишком большого или слишком малого количества уроков у класса в определенный день.
• Штраф за отклонение от желаемого количества уроков в день.
• "Чистые" дни: По возможности иметь один свободный день для учителя в неделю.

Для решения задачи разработан специализированный ГА со следующими характеристиками:

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

Генетические операторы:

Отбор: используется турнирная селекция, сохраняющая лучшие особи (элитизм).

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

Мутация: включает случайное перемещение урока в свободный слот или обмен местами двух уроков одного класса.

Выводы

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

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

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