АВТОМАТИЗАЦИЯ СОСТАВЛЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ С ПРИМЕНЕНИЕМ НЕЙРОННЫХ СЕТЕЙ

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

- качество знаний;

- результативность обучения;

- удобство обучения студентов и работы преподавателей.

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

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

Автоматизация процесса формирования учебных занятий позволяет:

- учитывать различные требования и условия, предъявляемых к расписанию;

- правильно формировать расписание для получения наилучшего и гибкого результата;

- осуществить критериальный или оптимизационный подход к составлению расписания;

- уменьшить временные затраты на формирование расписания.

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

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

Нейронные сети – это одно из направлений исследований в области искусственного интеллекта, основанное на попытках воспроизвести нервную систему человека. А именно: способность нервной системы обучаться и исправлять ошибки, что должно позволить смоделировать, хотя и достаточно грубо, работу человеческого мозга [1].

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

Для устранения данного недостатка используются методы эволюционного поиска.

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

1) Группы (G).

2) Аудитории (A).

3) Дисциплины (D).

4) Преподаватели (P).

5) Учебные пары (T).

Пусть в какой-либо группе G проводятся занятия в аудитории A по дисциплине D, преподавателем P, во время учебной пары T, то функция принимает значение равное 1, в противном случае функция принимает значение равное 0.

Таким образом необходимо определить параметры ,t, ρ, которые определяются по формуле (1).

α = (, , ... , , ... , )

  t = (, , ... , , ... , )                                       (1)

ρ = (, , ... , , ... , ),

где  ∈ A (множество аудиторий) – код аудитории, который назначен блоку занятий  ∈ Z;  ∈ T (множество учебных пар) – код учебной пары, который назначен первому занятию из блока занятий  ∈ Z;  ∈ P (множество преподавателей) – код преподавателя, который назначен блоку занятий  ∈ Z.

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

Обязательными ограничениями являются:

1) Отсутствие ошибок различного характера.

2) Отсутствие незанятых занятий («окон»).

3) Соответствие аудитории, в которой проходит занятие типу проводимого занятия.

4) Ограничение на количество занятий, проводимых в один день.

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

К дополнительным ограничениям относятся:

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

2) Учет пожеланий преподавателей.

3) Равномерная нагрузка студентов на протяжении учебного дня и всего семестра.

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

1) Ограничение, гарантирующее отсутствие ошибок для аудиторий. Для всякой двойки элементов пара и аудитория существует один блок занятий из множества Z. Это означает, что занятие этого блока проводятся в этой аудитории в момент прохождения данной пары, либо блок занятий отсутствует, что указывает на свободную аудиторию.

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

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

4) Ограничение, описывающее соответствие типа аудитории проводимому занятию.

5) Ограничение на количество учебных пар, которые проводятся в течении одного учебного дня. Данное ограничение означает, что для любой двойки элементов – группа и день, количество пар не превышает какого-либо максимального допустимого числа .

6) Ограничение отсутствия незанятых занятий для групп.

Одним из алгоритмов метода эволюционного поиска является генетический алгоритм.

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

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

1) Составление исходной популяции.

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

2) Отбор особей.

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

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

На данном этапе выполняется скрещивание хромосом родителей для создания хромосом потомков. Основную работу этого этапа выполняет оператор кроссинговера.

4) Мутации над полученным потомством.

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

5) Селекция особей для новой популяции.

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

6) Тестирование условия остановки алгоритма.

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

7) Выбор оптимальной особи.

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

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

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

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

1. Портал искусственного интеллекта: сайт – [Электронный ресурс]  – Режим доступа. – URL: http://www.aiportal.ru/articles/neural-networks/neural-networks.html (дата обращения: 19.02.2017).
2. Энциклопедия Википедия: сайт – [Электронный ресурс] – Режим доступа. URL:https://ru.wikipedia.org/wiki/Генетический_алгоритм (дата обращения: 19.02.2017).