Составление расписания учебных занятий является одной из важнейших задач управления учебным процессом. Расписание занятий представляет собой пространственно-временной график их проведения с «привязкой» к конкретным учебным группам и дисциплинам. В данной статье будет описано применение генетического алгоритма для решения поставленной задачи.

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

Между вышеперечисленными множествами объектов существуют связи, отражающие организационную структуру образовательной системы, задачей которой является реализация учебного процесса. Исходя из этого, теоретико-множественную модель расписания можно представить в виде функции R, отображающей декартово произведение множеств на множество нулей и единиц {0,1}:

R : G × A × D × P × T → {0,1} .

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

Учитывая связь между объектами «группы» и «дисциплины» на основе учебного плана мы можем образовать новую структуру, которую назовём «занятие». «Занятие» представляет собой агрегированный объект. Каждый элемент этого множества определяет дисциплину, по которой требуется провести занятие у конкретной учебной группы. При решении задачи составления расписания занятий будем рассматривать особь, состоящую из трех хромосом. Каждая хромосома в свою очередь состоит из генов, обозначаемых целыми числами 1,2,...i,...N, причем номер гена каждой хромосомы соответствует номеру блока занятия, так, z – й ген и в первой, во второй и в третьей хромосоме характеризует блок занятия z из множества Z.

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

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

Следующим этапом алгоритма будет селекция. Оператор отбора является важнейшим фактором, влияющим на эффективность генетического алгоритма. Далее применяется скрещивание – «кроссинговер». В данном алгоритме применяется одноточечный кроссинговер.

Заключительным этапом первого витка является мутация - изменение вида хромосом случайным образом. К некоторым из особей получившимся после скрещивания применяется оператор мутации. Наряду с описанной выше "случайной" мутацией в предлагаемом нами генетическом алгоритме реализована "направленная" мутация генов особи. При решении задачи составления расписания учебных занятий каждая такая особь генетического алгоритма будет представлять собой готовый вариант расписания занятий. Совокупность всех особей (вариантов расписаний) является множеством возможных решений данной задачи.

Алгоритм заканчивает свою работу, когда некоторый процент особей (60-80%) принимают одинаковые значения функции приспособленности.

На последнем этапе происходит выбор наилучшей особи среди всех допустимых решений.

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