генетический алгоритм для составления расписания занятий

Question

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

В самом начале я предположил, что у нас есть классы с продолжительностью 1 временной интервал (временной интервал = 1 час), и мы можем просто поместить его в массив (представляет сетку расписания: 1-й массив с емкостью числаOfRooms * numberOfDays * numberOfTimeslots) и может также выполнять мутацию и кроссовер без проблем.

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

Как мы можем поместить один объект класса в массив и заполнить все слоты (несколько ячеек массива), какой класс должен занимать (один объект - несколько ячеек)? И в соответствии с тем, как мы будем помещать его в массив, как можно выполнить операцию мутации и кроссовера? Спасибо заранее! Я очень ценю вашу помощь!

Answer 1

Хорошее правило может пересекать только классы, имеющие одинаковые временные интервалы. Например, вы можете пересечь класс, который занимает два временных интервала с двумя классами, которые занимают один временной интервал.

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

Другой (лучший) способ создает более сложную структуру данных: DailyRoomOccupation. Эта структура данных будет содержать:

• дневная емкость комнаты, выраженная в количестве временных интервалов;
• a (двойной) список классов, запланированных на этот день в этой комнате;
• функция, которая вычисляет, будут ли классы в списке помещаться в временные интервалы;
• функция, которая позволяет перекрещивать два разных DailyRoomOccupation s, заботясь о пересечении только равных количеств временных интервалов.