ВКР: "Разработка приложения по автоматизации расписания ВУЗа с использованием генетического алгоритма"

Описание

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

Формулировка задачи оптимизации

$T$ - множество временных ячеек, в которые можно проводить занятия $S$ - множество дисциплин $P$ - множество преподавателей $G$ - множество учебных групп

Будем называть учебным планом множество из троек $(s, p, g)$, в котором каждый элемент может повторяться несколько раз:

$$ U = ( u, n | u \in S \times P \times G, n \in \mathbf{N} )$$

Тогда расписанием будем называть отображение из учебного плана в множество временных ячеек: $\tau: U \to T$

Корректность расписания определяется следующими естественными ограничениями:

• Каждый преподаватель может проводить только одно занятие одновременно

$$ \nexists u_1, u_2 \in U: \tau (u_1) = \tau (u_2) and p_1 = p_2, where u_i = (s_i, p_i, g_i) $$

• Каждая группа может присутствовать только на одно занятии одновременно.

$$ \nexists u_1, u_2 \in U: \tau (u_1) = \tau (u_2) and g_1 = g_2, where u_i = (s_i, p_i, g_i) $$

Расписание должно удовлетворять пожеланием групп и преподавателей, например:

1. Преподаватель не может вести занятия в определенное время
2. Требуется минимизировать количество окон как для преподавателей, так и для групп
3. Минимизировать число учебных дней, в которые группа приходит на занятия

Пусть для каждого такого пожелания выбрана функция $w_i: (\tau) \to [0; 1]$. Обозначим за $C_q$, где за символлм $q$ может стоять $p$ или $s$, число нарушений соответствующих условий корректности расписания. Тогда целевая функция в задаче оптимизации расписания имеет вид:

$$ f: (\tau) \to \mathbf{R}$$

$$f(\tau) = C_p + C_s + \sum_{i=1}^n w_i \to min$$

Как можно видеть, если функция принимает значение $\ge 1$, то она соответствует некорректному расписанию.

Представление задачи в терминах генетического алгоритма.

Как известно, генетический алгоритм состоит из следующих основных шагов:

1. Инициализация
2. Селекция
3. Применение генетических операций (мутации, кроссинговер)
4. Проверка условия останова, при необходимости переход к пункту 2

На шаге инициализации генерируется случайная популяция - множество особей.

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

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

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

В нашей задаче, особь - это одно конкретное расписание, соответственно популяция - множество расписаний на данном шаге. Мы выбрали представление каждой особи в виде одной хромосомы. Хромосома состоит из целочисленных генов, принимающих значение от $1$ до $|T|$ (количество временных ячеек), в каждой хромосоме $|U|$ генов (количество занятий в учебном плане). Таким образом, хромосома однозначно задаёт расписание