как заняться этой комбинаторной проблемой алгоритма

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

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

Вот пример того, как вы могли бы смоделировать это с помощью GA.

Используя ваши обозначения:

• N (количество экзаменов)
• T (количество экзаменов)

Пусть ген человека выражает полное расписание бронирований. т.е. человек - это список конкретных заказов: (i, j, t, d)

• i - i-й экзаменатор [1, N]
• j - j-й экзаменатор [1 ,? ]
• t - й тест, который должен сдать экзаменующий [1, T]
• d - начало экзамена (дата + время)

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

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

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

, чтобы эта работа работала хорошо, рассмотрите:

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

, инициируемые разумным способом:

• случайный выбор d в течение периода времени
• случайным образом перестановка (1,2, .., N), а затем выберите i из этого (избегая дублирования), то же самое для j и t

правильные операторы GA:

говорят, что у вас есть резервирование a и b : (a_i, a_j, a_t, a_d) (b_i, b_j, b_t, b_d)

вы можете поменять местами a_i и b_i, и вы можете поменять местами a_j и b_j и a_d и b_d, но, вероятно, нет смысла менять местами a_t и b_t.

у вас также может быть цикл, лучше всего проиллюстрированный примером, если N * T = 4, полное резервирование составляет 4 кортежа, и затем вы должны циклически перемещаться по i, j или d, например, по i:

a_i = b_i
b_i = c_i
c_i = d_i
d_i = a_i

Как предложил julienaubert , решение (которое я назову графиком ) представляет собой последовательность кортежей (дата, студент, экзаменатор, тест), которая охватывает все соответствующие комбинации ученика и теста. (все ли N студентов сдают все тесты T?). Я понимаю, что один экзаменатор может тестировать сразу нескольких студентов. В противном случае потребуется огромное количество экзаменаторов (хотя бы по одному на студента), в чем я очень сомневаюсь.

Два кортежа A и B конфликтуют, если

• учащийся один и тот же, тест другой и период времени перекрывается
• экзаменатор тот же, тест другой и период времени перекрывается
• студент уже работал с экзаменатором над другим тестом.

Обратите внимание, что конфликты кортежей отличаются от конфликтов расписания (которые должны дополнительно проверять наличие повторяющейся проблемы экзаменатора).

Нижняя граница:

• количество экзаменующих E должно быть> = общее количество тестов самого перегруженного ученика
• общее время должно быть больше, чем общая продолжительность тестов самого перегруженного ученика.

Простое жадное расписание можно составить следующим методом:

1. Возьмите самого перегруженного ученика и назначение тестов в случайном порядке, каждый с другим экзаменатором. Некоторые бункерную упаковку можно использовать для повторного заказа тесты, так что обеденный перерыв хранится бесплатно. Это будет счастливым студент: он закончит в минимально возможное время.
2. Для каждого другого студента, если студент должен пройти какой-либо уже запланированный тест, поделитесь своим временем, местом и экзаменатором с ранее запланированным тестом.
3. Возьмите самого перегруженного ученика (например: наибольшее количество внеплановых тестов) и назначьте кортежи, чтобы не нарушались никакие ограничения, добавив больше времени и экзаменаторов, если необходимо
4. Если у кого-то из учеников есть внеплановые тесты, перейдите к 2.

. Улучшение выбора, сделанного на шаге 2 выше, имеет решающее значение для улучшения; этот выбор может лечь в основу эвристического поиска. Вышеупомянутый алгоритм пытается минимизировать количество требуемых экзаменаторов за счет времени студентов (студенты могут закончить с одним экзаменом на раннем этапе и другим последним делом в течение дня, ничего между ними). Тем не менее, это гарантированно приведет к юридическим решениям. Запуск его с разными студентами может быть использован для создания «стартовых» решений для GA, которые придерживаются юридических ответов.

В целом, я считаю, что не существует «идеального ответа» на проблему, подобную этой, потому что необходимо принимать во внимание множество факторов: студенты хотели бы свести к минимуму свое общее время, затрачиваемое на сам экзамен, как это сделали бы экзаменаторы. ; мы хотели бы свести к минимуму количество экзаменаторов, но есть также практические ограничения на то, сколько студентов мы можем разместить в комнате с одним экзаменатором. Кроме того, мы хотели бы сделать расписание «справедливым», чтобы никто не становился намного хуже других. Таким образом, лучшее, на что вы можете надеяться, - это позволить возиться с этими ручками, чтобы результаты были известны (общее время, удовлетворенность каждого студента, степень удовлетворенности каждого экзаменатора, размеры экзаменов, воспринимаемая справедливость) и позволить пользователю исследовать пространство параметров и сделайте осознанный выбор.

Я бы рекомендовал использовать для этого SAT-решатель. Хотя проблема, вероятно, NP-трудная, хорошие SAT-решатели часто могут обрабатывать сотни тысяч переменных. Посмотрите Chaff или MiniSat для двух примеров.

Вы также можете рассмотреть возможность программирования в ограничениях. Ознакомьтесь с Prolog или, для более современного выражения логического программирования, PyKE