Электронный научный журнал
Международный студенческий научный вестник
ISSN 2409-529X

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

Маслов А.С. 1 Белов Ю.С. 1
1 Калужский филиал федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)»
В статье излагаются взгляды на использование генетических алгоритмов в процессе генерации расписания для университета. Выдвигаются обязательные и желательные требования к расписанию в университете. Описывается исходная информация основных математических множеств, которые характеризуют математическую модель университета: множество дисциплин изучения, множество учебных групп, множество преподавателей, множество аудиторий, множество временных интервалов. Описываются основные сущности необходимые для составления любого расписания в университете: аудитории; временные интервалы; преподаватель, дисциплина, учебные группы. Рассматриваются и математически обосновываются различные ограничивающие обязательные и желательные условия достоверности генерируемого расписания. Указывается эффективность системы генерации расписания на основе генетических алгоритмов, а не других алгоритмах. Рассматриваются этапы построения модели расписания. Рассматривается состав гена для генетического алгоритма, полученный на основе построенных математических множеств. Рассматриваются этапы реализации генетического алгоритма. Подробно рассказывается за что отвечает каждый этап генетического алгоритма: формирование начальной популяции, селекция особей, скрещивание (кроссинговер), мутация, проверка условия останова алгоритма, выбор наилучшей особи. Рассмотрены результаты работы алгоритмов генерации расписания по отношению к составлению расписания вручную диспетчером по времени и учету предпочтений обоих сторон: преподавателей и студентов.
генетические алгоритмы
генерация расписания
оптимизация расписания
1. Аксютина Е.М., Белов Ю.С. Обзор архитектур и методов машинного обучения для анализа больших данных. // Электронный журнал: наука, техника и образование. 2016. № 1 (5). С. 134-141.
2. Черепков Е.А., Рыбкин С.В. Технологии для обработки и анализа больших данных. // Электронный журнал: наука, техника и образование. 2016. № 4 (9). С. 120-127.
3. Береговых Ю.В., Васильев Б.А., Володин Н.А. Алгоритм составления расписания занятий. // «Искусственный интеллект» 2’2009 С. 50-56.
4. Верёвкин В.И., Исмагилова О.М., Атавин Т.А. Автоматизированное составление расписания учебных занятий вуза с учётом трудности дисциплин и утомляемости студентов //Доклады ТУСУРа, №1 (19), часть 1, 2009 С. 221-225.
5. Конькова И.С. Использование генетического алгоритма в задаче оптимизации расписания вуза. // Вестник ТвГТУ. 2012. Вып. 22. С. 26-31.
6. Асвад Фирас М., Астахова И. Ф. Применение генетического алгоритма для составления расписания. // Кибернетика и высокие технологии XXI века: XIII Международная научно-техническая конференция. –Воронеж, 2012. –Т. 1. – С. 120–124.
7. Астахова И. Ф., Фирас А. М. Составление расписания учебных занятий на основе генетического алгоритма. // Вестник ВГУ, серия: системный анализ и информационные технологии, 2013, № 2 С. 93-99.
8. Кабальнов Ю. С., Шехтман Л. И., Низамова Г. Ф., Земченкова Н. А. Композиционный генетический алгоритм составления расписания учебных занятий // Вестник УГАТУ = Vestnik UGATU. 2006. №2. С. 99-107.
9. Голикова Т.И., Белов Ю.С. Решение проблемы кадрового планирования в виде смешанной целочисленной нелинейной задачи с учетом человеческих факторов. // Электронный журнал: наука, техника и образование. 2017. № СВ2 (13). С. 154-160.

Введение. Вопрос создания оптимального расписания для университета стоит очень давно. Расписание является неотъемлемой частью при планировании учебного процесса, так как без него не может функционировать ни одно учебное заведение. Создание расписания и организация учебного процесса занимает много времени для человека, поскольку необходимо учитывать множество различных факторов, в качестве которых могут выступать комфортные условия обучения у студентов, удобное время проведения занятий для преподавателей, ресурсы университета и т.д. Подходы к решению задач со столь большим количеством учитываемых параметров можно отнести к технологиям больших данных [1,2], а по сложности генерация расписания относится к классу NP-полных задач. Современные технологии позволяют автоматизировать и ускорить этот процесс в тысячи раз. Это стало возможно с появлением эвристических методов, одним из которых является рассматриваемый в данной статье генетический алгоритм. Для таких алгоритмов имеется сильная зависимость под конкретное учебное заведение, что не позволяет сделать универсальную систему. Эти алгоритмы помогают не только автоматизировать создание расписания, но и создать оптимальное расписание с учетом многих предпочтений. В данной обзорной статье будут рассматриваться материалы, взятые из других источников.

Математическая часть. При составлении расписания существуют обязательные и дополнительные, так называемые желательные, требования [3,4,5], которые могут меняться в зависимости от учебного заведения.

Обязательные требования:

  • Аудитория должна вмещать всех студентов, обучающихся в текущий период.   
  • Аудитория должна быть оборудована соответствующим образом.
  • Отсутствие не состыковок в расписании.
  • Полное выполнение учебного плана.
  • У преподавателей и студентов не должно быть больше 3-х лекций в день.
  • Желаемое количество пар в день не более 5 (в субботу - не более 3).

Дополнительные (желательные) требования:

  • У студентов отсутствуют «окна».
  • В начале учебного дня рекомендуется проводить лекционные занятия, затем –практические.
  • Минимальное количество переходов между корпусами/аудиториями.
  • Пожелания преподавателей.

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

Начальная информация — это множества [6,7]:

  • Преподаватели
  • Читаемые дисциплины
  • Группы
  • Временные интервалы
  • Аудитории

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

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

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

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

Таким образом получается:

Каждая аудитория имеет расположение – корпус при наличии нескольких, этаж и сам кабинет, пример 5 – 108, где первая цифра показывает в каком корпусе находится аудитория, 1 – показывает на каком этаже, 08 обозначает номер аудитории. Таким образом для формального описания аудитории введем 3-арный кортеж:

 где - корпус,  - номер аудитории,  - тип аудитории.

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

 где  – номер недели,  - номер дня недели, - номер пары в учебном дне.

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

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

Таким образом, при составлении расписания нам необходимо три множества , которые можно определить следующими векторами:

- номер аудиторий для цикла занятий .

- номер пары из цикла  первого занятия.

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

Ограничивающие условия:

  • Отсутствие проблем для ведения занятий у преподавателей и групп в допустимых аудиториях.
  • Недопустимость «окон» в учебных днях для обучающихся.
  • Максимальное число занятий в день не должно превышать указанного порога.
  • Аудитория должна соответствовать типу проводимого предмета.
  • Полное выполнение учебного плана.

Математическая модель приведённых выше ограничивающих условий очень подробно приведена в статье [8].

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

Благодаря математической модели мы определили, что особь будет состоять из двух хромосом: первая - вектор , вторая - вектор .

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

Алгоритм будет содержать следующие этапы:

  • Формирование начальной популяции.

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

  • Селекция особей.

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

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

  • Скрещивание (кроссинговер).

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

  • Мутация.

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

  • Проверка условия останова алгоритма.

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

  • Выбор максимально подходящей особи.

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

Вывод. По полученным данным, взятым из рассматриваемых источников, видно, что генерация расписания на основе генетических алгоритмов позволяет сократить время создания расписания до нескольких минут, что в сравнении с ручным составлением, которое занимает до нескольких недель, на порядок выше. Помимо этого, такая автоматизация позволяет учитывать интересы обеих сторон: и преподавателей, и студентов [9].

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


Библиографическая ссылка

Маслов А.С., Белов Ю.С. ГЕНЕРАЦИЯ РАСПИСАНИЯ ДЛЯ ВУЗА С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА // Международный студенческий научный вестник. – 2018. – № 6.;
URL: http://eduherald.ru/ru/article/view?id=19255 (дата обращения: 15.09.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252