Автоматизация построения расписания экзаменов ВУЗа с использованием генетического алгоритма

Размещено на http://allbest.ru

Донской государственный технический университет

Автоматизация построения расписания экзаменов ВУЗа с использованием генетического алгоритма Инженерный вестник Дона, №3 (2017), ivdon.ru/ru/magazine/archive/n3y2017/4341

М.Ю. Жукова,

В.М. Аль-Габри

Ростов-на-Дону

Аннотация

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

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

Ключевые слова: генетический алгоритм, расписание, экзамены, ВУЗ, учебная группа.

Введение

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

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

Формально расписание экзаменов это отношение, построенное на прямом произведении множеств объектов: учебная группа, преподаватель, дисциплина [3]. Для решения задачи формирования расписания экзаменов принимается разные методы и технологии, основанные на классических методах и алгоритмах целочисленного программирования, методах раскраски графов. Кроме того, применяются методы: полного перебора, ветвей и границ, а также эвристические методы, в том числе основанные на генетических алгоритмах [4].

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

Постановка задачи

(1)

- множество учебных групп, где ng - название группы, cnt - количество студентов в группе;

(2)

- множество преподавателей;

(3)

- множество дисциплин;

(4)

- множество диапазонов дат, для проведения экзаменационной сессии.

Множество временных интервалов для расписания экзаменов можно представить в виде:

(5)

где date - дата из диапазона (dt_start, dt_end)_i, tm - временной интервал, принадлежащий дню, когда может быть проведен экзамен (tm=1 - первая половина дня, tm=2 - вторая половина дня экзамена).

Множество учебных аудиторий можно представить в следующем виде:

(6)

где nr - название аудитории, rns - вместимость, tr - тип аудитории;

При формировании расписания экзаменов необходимо учитывать ряд требований, предъявляемых к этому расписанию. Требования можно определить как жесткие и мягкие ограничения. Под жесткими ограничениями будем рассматривать требования, нарушение которых приводит к недопустимости использования построенного расписания. К мягким отнесем рекомендации и пожелания [5]. В таблице 1 рассмотрены ограничения с их весовыми коэффициентами.

Таблица 1. Требования к расписанию экзаменов

№	Ограничение	Весовой коэффициент
1. Жесткие ограничения
1.1.	В одной учебной группе не может быть более одного экзамена в один и тот же временной интервал	k11
1.2.	Один преподаватель не может проводить более одного экзамена в один и тот же временной интервал	k12
1.3.	Одна аудитория не может быть использована для проведения более чем одного экзамена в один и тот же временной интервал	k13
1.4.	В одной учебной группе минимальный временной промежуток между экзаменами составляет 2 дня	k14
1.5.	Количество посадочных мест в аудитории должно быть больше или равно количеству студентов в группе	k15
2. Мягкие ограничения
2.1.	Для учебной группы учитывается порядок следования экзаменов, прогнозирующий наилучшую успеваемость [6]	k21
2.2.	В одной учебной группе минимальный временной промежуток между экзаменами не менее 3 дней	k22
2.3.	Количество свободных посадочных мест в аудитории не превышает 20% от ее общей вместимости	k23
2.4.	Один преподаватель проводит не более одного экзамена в один день	k24

Объемы нарушений ограничений определяются по следующим формулам:

(7)

где - функция, определяющая нарушение ограничения 1.1, countExamG() - функция, определяющая количество экзаменов в группе g_i во временном интервале dt_ej.

(8)

где - функция, определяющая нарушение ограничения 1.2, countExamT() - функция, определяющая количество экзаменов у преподавателя t_i во временном интервале dt_ej.

(9)

где - функция, определяющая нарушение ограничения 1.3, countExamR() - функция, определяющая количество экзаменов в аудитории r_i во временном интервале dt_ej.

(10)

где - функция, определяющая нарушение ограничения 1.4.

(11)

где - функция, определяющая нарушение ограничения 1.5,

countst() - функция, определяющая количество студентов в группе,

RoomCap() - функция, определяющая количество посадочных мест в аудитории.

(12)

где - функция, определяющая нарушение ограничения 2.1,

- функция получения коэффициента успеваемости группы по заданной последовательности экзаменов (w_i).

(13)

где - функция, определяющая нарушение ограничения 2.2.

 (14)

где - функция, определяющая нарушение ограничения 2.3,

countst() - функция, определяющая количество студентов в группе,

RoomCap() - функция, определяющая количество посадочных мест в аудитории,

iRecom - рекомендуемый максимальный процент свободных мест в аудитории.

(15)

где - функция, определяющая нарушение ограничения 2.4,

countExamT() - функция, определяющая количество экзаменов у преподавателя t_i в день экзамена e_j (date_ej).

Для определения качества сформированного расписания экзаменов используется целевая функция, представляющая собой количественную оценку нарушений ограничений [7].

(16)

где k_ij - весовой коэффициент ограничения,

c_ij - объем нарушений ij -го ограничения,

n - число типов ограничений (в данном случае n =2),

m_i - количество ограничений i-го типа, x - текущее решение.

Алгоритм построения допустимого расписания

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

aProgress = {(g_i, (e₁, e₂, …, e_ne, w)_j) | g_i G, j=, w?[0, 1]}

- массив зависимостей успеваемости группы от порядка следования экзаменов, отсортированные по убыванию w, e_l - экзамен с порядковым номером l, w - коэффициент успеваемости группы.

(e₁, e₂, …, e_ne)_jProgress = getSequence(g_i, jProgress) - функция, получающая для группы g_i, по порядковому номеру jProgress последовательность экзаменов из массива aProgress.

minTimeout - минимально количество дней между экзаменами.

normTimeout - рекомендуемое количество дней между экзаменами.

countApptExams - количество расставленных экзаменов в группе.

Q_allnappt - очередь из всех нераспределенных экзаменов.

eCount() - функция вычисления количества экзаменов в группе.

maxTOg_i - максимально допустимый интервал между экзаменами в период заданного диапазона.

getCountApptExams() - функция получения количества расставленных экзаменов.

addExamToQ() - функция добавления экзамена в очередь.

removeExamFromQ() - функция удаления экзамена из очереди.

isApptExam() - функция проверки расставлен ли экзамен (true - расставлен, false - не расставлен).

setRDExam() - функция присвоения пространственно-временной характеристика экзамену.

getPossibleDate() - функция получения возможной даты из диапазона дат для проведения экзамена.

getNextDate() - функция получения следующей даты.

Псевдокод алгоритма построения допустимого расписания экзаменов:

1 Сортировка групп по диапазонам сессии.

2 Цикл по группам g_i ?G

3 Вычислить eCount(g_i)

4 Вычислить maxTOg_i с округлением в меньшую сторону

5 Если (maxTOg_i < minTimeout)

6 ТО переход на шаг 2

7 ИНАЧЕ

8 ЕСЛИ getCountApptExmas(g_i) == eCount(g_i)

9 ТО переход на шаг 2

10 ИНАЧЕ

11 ПРИСВАИВАЕМ jProgress = 1

12 ПРИСВАИВАЕМ Q_jpgi = getSequence(g_i, jProgress)

13 ПРИСВАИВАЕМ countApptExmas[g_i] = 0

14 ЦИКЛ ПОКА не конец очереди Q_jpgi

15 ЕСЛИ isApptExam(e_j) == true

16 ТО

17 removeExamFromQ(e_j, Q_jpgi)

18 countApptExmas[g_i]+1

19 переход на шаг 14

20 ИНАЧЕ

21 date = getPossibleDate(g_i)

22 ЕСЛИ date == null

23 ТО addExamToQ(e_j, Q_allnappt)

24 ИНАЧЕ

25 ЕСЛИ findConf(date, g, e_j) == false

26 ТО

27 setRDExam(date, g, e_j)

28 countApptExmas[g_i] +1

29 removeExamFromQ(e_j,Q_jpgi)

30 ИНАЧЕ

31 date = getNextDate()

32 ЕСЛИ date == null

33 ТО

34 jProgress+1

35 переходим на шаг 12

36 ИНАЧЕ переход на шаг 25

37 ВСЕ ЕСЛИ

38 ВСЕ ЕСЛИ

39 ВСЕ ЕСЛИ

40 ВСЕ ЕСЛИ

41 ВСЕ ЦИКЛ ПОКА

42 ВСЕ ЕСЛИ

43 ВСЕ Если

44 ВСЕ Цикл

Минимизация целевой функции (16) реализуется с помощью генетического алгоритма, основанного на механизмах естественного отбора и наследования[8]. Будем рассматривать расписание экзаменационной сессии как некоторое однозначное отображение ES из множества экзаменов E во множество Dtm Ч R (декартово произведение временных интервалов и аудиторий):

ES : E > Dtm Ч R.

Табличное представление данного отображения представлено в таблице 2.

Таблица 2. Табличное представление отображения ES

date	tm	r1	r2	...	...	rnr
d1	1	e1	e2	...	...	el
d1	2	X	X	...	...	...
d2	1	...	em	...	...	...
d2	2	...	...	...	ek	X
...	...	...	...	...	...	...
dt	1	...	...	...	...	...
dt	2	ei	X	...	ej	...

Так как размерность ndr множества Dtm Ч R (будем называть это множество множеством пространственно-временных характеристик) обычно превышает количество экзаменов ne, то некоторые пространственно-временные характеристики будут являться свободными (в таблице такие позиции обозначены Х).

Если пронумеровать все ячейки таблицы 1, и развернуть их в строку, то получится последовательность пространственно-временных характеристик с заданными на них экзаменами. Представление допустимого расписания в таком виде, позволяет использовать ГА для улучшения этого решения. В нашем случае, в терминологии ГА, под геном будет пониматься ячейка таблицы расписания, а под особью или хромосомой - один из вариантов расписания экзаменов. При этом «жизнеспособными» будут считаться только те хромосомы, которые удовлетворяют заданным ограничениям, т.е. являются допустимыми решениями.

Популяцией будем считать множество «жизнеспособных» хромосом с наиболее высокой степенью выживания (с наибольшим значением функции «приспособленности»).

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

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

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

Скрещивание (или кроссовер)

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

Суть метода заключается в следующем:

1. Выбираются 2 родительские хромосомы, которые будут участвовать в скрещивании (СН1 и СН2). Например:

Рисунок 1. - Родительская хромосома СН1.

Рисунок 2. - Родительская хромосома СН2.

2. Построим циклические перестановки по родительским хромосомам:

Рисунок 3. - Пример построения циклических перестановок.

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

CH1 = Z₁+СН1₁+Z₂+СН1₂+Z₃+СН1₃+Z₄+СН1₄+Z₅+СН1₅+Z₆

CH2 = Z₁+СН2₁+Z₂+СН2₂+Z₃+СН2₃+Z₄+СН2₄+Z₅+СН2₅+Z₆

где Z₁ = (1), Z₂ = (4)(5)(9), Z₃ = (12)(13)(16)(65)(66)(67)(68)(17),

Z₄ = (21)(24)(32)(33)(37)(40)(41)(42)(43)(44)(45), Z₅ = (49),

Z₆ = (53)(54)(56)(59)(60)(61)(64)

СН1₁ = (2,19,14,7,6,18,3,8), СН2₁ = (8,3,18,6,7,14,19,2),

СН1₂ = (10, 15, 22, 23, 25, 29, 35, 38, 48, 50, 51, 58, 57, 62, 63, 34, 39, 30, 31, 26, 27, 28, 11),

СН2₂ = (11, 28, 27, 26, 31, 30, 39, 34, 63, 62, 57, 58, 51, 50, 48, 38, 35, 29, 25, 23, 22, 15, 10),

СН1₃ = (20,36), СН2₃ = (36,20),

СН1₄ = (46,47), СН2₄ = (47,46),

СН1₅ = (52,55), СН2₅ = (55,52).

3. Операция скрещивания может быть представлена как обмен совпадающих по набору генов циклов:

Рисунок 4. - Пример выполнения операции скрещивания.

Тогда хромосомы-потомки будут представлять собой комбинацию вида:

Z₁+ X₁+Z₂+ X₂+Z₃+ X₃+Z₄+ X₄+Z₅+ X₅+Z₆,

где X_i - i-й цикл родительской хромосомы СН1 или СН2.

Количество хромосомы-потомки будет равно 2^nc-2 (где nc - количество нетривиальных циклов в родительских хромосомах).

Таблица 3. Возможные хромосомы-потомки

CH1:	Z1+СН11+Z2+СН12+Z3+СН13+Z4+СН14+Z5+СН15+Z6
CH2:	Z1+СН21+Z2+СН22+Z3+СН23+Z4+СН24+Z5+СН25+Z6
Потомки:	Z1+СН21+Z2+СН12+Z3+СН13+Z4+СН14+Z5+СН15+Z6
	Z1+СН11+Z2+СН22+Z3+СН13+Z4+СН14+Z5+СН15+Z6
	…
	Z1+СН11+Z2+СН22+Z3+СН23+Z4+СН24+Z5+СН15+Z6
	Z1+СН11+Z2+СН22+Z3+СН23+Z4+СН14+Z5+СН25+Z6
	…
	Z1+СН21+Z2+СН22+Z3+СН23+Z4+СН14+Z5+СН25+Z6
	Z1+СН21+Z2+СН22+Z3+СН23+Z4+СН24+Z5+СН15+Z6

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

Мутация

Генетический оператор мутации изменяет значение гена на противоположное (в бинарном представлении хромосом 0 на 1 или наоборот) с некоторой вероятностью p_m.

Например, в хромосоме CH1 5-й ген представляет кортеж {d, e_i, r_j}, а 14-й ген: {d, e_k, r_l}.

При этом аудитории r_j и r_l являются идентичными. Под идентичными, будем понимать аудитории, имеющие аналогичное материально-техническое оснащение и вместимость.

Тогда мутация в хромосоме CH1 может быть представлена на рис.4.

Рисунок 4. - Пример мутации в хромосоме CH1.

Функция приспособленности

Чтобы оптимизировать какую-либо структуру с использованием ГА, нужно задать меру качества для каждого индивида в пространстве поиска.

Для этой цели используется функция приспособленности.

В поставленной задаче целевая функция (16) выступает в качестве функции приспособленности [9,10].

Результаты

Разработанный экспериментальный программный стенд позволяет:

· проанализировать существующие расписания;

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

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

Выводы

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

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

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

4. Использование механизмов построения расписаний экзаменов совместно с системами построения рациональных последовательностей экзаменов, позволит проектировать системы автоматизации построения расписаний сессий и управления их результатами.

Литература

1.Дворянкин А.М. Обзор методов составления расписания вузов/ А.М. Дворянкин, В.С. Чалышев // Изв. ВолгГТУ. Серия Актуальные проблемы управления, вычислительной техники и информатики в технических системах: межвуз. сб. науч. ст. / ВолгГТУ.- Волгоград, 2011. - Вып. 11, № 9. - c. 110-113.

2.Аль-Габри В.М., Обзор литературных источников по теме «Автоматизация составления расписания занятий и экзаменов в высших учебных заведениях»// Вестник Донского государственного технического университета 2017, №1(88), c. 132-143.

3.Гранков М.В., Аль-Габри В.М., Горлова М.Ю., Анализ и кластеризация основных факторов, влияющих на успеваемость учебных групп вуза// Инженерный вестник Дона, 2016, № 4, URL: ivdon.ru/ru/magazine/archive/n4y2016/3775.

4. Семенов С.П. Сравнительный анализ подходов к автоматизации составления расписаний учебных занятий в образовательных учреждениях / С.П. Семенов, Я.Б. Татаринцев // Изв. Алтайского гос. ун-та. - 2010. - № 1(65). - с. 103-105.

5.Абухания А.Ю. Модели, алгоритмы и программные средства обработки информации и принятия решений при составлении расписаний занятий на основе эволюционных методов: Дис. …канд. техн. наук: 05.13.01 / Абухания Амер Юсеф - Новочеркасск, 2016. - 231 с.

6.Гранков М.В., Аль-Габри В.М., Регрессионная модель успеваемости студенческих групп вуза// Инженерный вестник Дона, 2017, № 1, URL: ivdon.ru/ru/magazine/archive/ /n1y2017/4058

7.Omar Ibrahim Obaid, MohdSharifuddin Ahmad, Salama A. Mostafa, Mazin Abed Mohammed. Comparing Performance of Genetic Algorithm with Varying Crossover in Solving Examination Timetabling Problem/ Omar I.O, MohdSharifuddin A., Salama A.M., Mazin A.M. // Journal of Emerging Trends in Computing and Information Sciences- VOL. 3, NO.10, Oct 201, pp. 1427- 1434.

8.Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский. - М.: Горячая линия - Телеком, 2013. - 384 c.

9.Burke E. A Genetic Algorithm for university timetabling // In AISB Workshop on Evolutionary Computing. University of Leeds. - UK. - 1994. - pp. 134 - 140.

10. Лопатеева О.Н. Система автоматизированного формирования учебного расписания в высшем учебном заведении на основе эвристических алгоритмов: Дис. …канд. техн. наук: 05.13.01 / Лопатеева Ольга Николаевна - Красноярск, 2006. - 205 с.

References

1. Dvoryankin A.M. Izv. VolgGTU. Seriya Aktual'nyye problemy upravleniya, vychislitel'noy tekhniki i informatiki v tekhnicheskikh sistemakh: mezhvuz. sb. nauch. st. VolgGTU.Volgograd, 2011. Vyp. 11, № 9, pp. 110-113.

2. Al'-Gabri V.M., Vestnik Donskogo gosudarstvennogo tekhnicheskogo universiteta 2017, №1 (88), pp. 132-143.

3. Grankov M.V., Al'-Gabri V.M., Gorlova M.U., Inћenernyj vestnik Dona (Rus), 2016, № 4, URL: ivdon.ru/ru/magazine/archive/n4y2016/3775.

4. Semenov S.P. Izv. Altayskogo gos. un-ta. 2010. № 1(65). pp. 103-105.

5. Abukhaniya A.YU. Modeli, algoritmy i programmnyye sredstva obrabotki informatsii i prinyatiya resheniy pri sostavlenii raspisaniy zanyatiy na osnove evolyutsionnykh metodov [Models, algorithms and software for information processing and decision making in scheduling lessons based on evolutionary methods] : Dis. kand. tekhn. nauk: 05.13.01. Abukhaniya Amer Yusef. Novocherkassk, 2016. 231 p.

6. Grankov M.V., Al'-Gabri V.M., Inћenernyj vestnik Dona (Rus), 2017, № 1, URL: ivdon.ru/ru/magazine/archive/n4y2017/3775.

7. Omar Ibrahim Obaid, MohdSharifuddin Ahmad, Salama A. Mostafa, Mazin Abed Mohammed. Comparing Performance of Genetic Algorithm with Varying Crossover in Solving Examination Timetabling Problem. Omar I.O, MohdSharifuddin A., Salama A.M., Mazin A.M. Journal of Emerging Trends in Computing and Information Sciences. VOL. 3, NO.10, Oct 2012, pp. 1427- 1434.

8. Rutkovskaya D. Neyronnyye seti, geneticheskiye algoritmy i nechetkiye sistemy [Neural networks, genetic algorithms and fuzzy systems]. M.: «goryachaya linya-telekom», 2013. 384 p.

9. Burke E. A Genetic Algorithm for university timetabling. In AISB Workshop on Evolutionary Computing. University of Leeds. UK. 1994, pp. 134 - 140.

10. Lopateyeva O.N. Sistema avtomatizirovannogo formirovaniya uchebnogo raspisaniya v vysshem uchebnom zavedenii na osnove evristicheskikh algoritmov [The system of the automated formation of the educational schedule in a higher educational institution on the basis of heuristic algorithms]: Dis. kand. tekhn. nauk: 05.13.01. Lopateyeva Ol'ga Nikolayevna. Krasnoyarsk, 2006. 205 p.

Размещено на Allbest.ru