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

Воцарилась тишина, которую нарушил сам Швейк, вздохнув:
— … На военной службе должна быть дисциплина — без неё никто бы и пальцем для дела не пошевельнул. Наш обер-лейтенант Маковец всегда говорил: «Дисциплина, болваны, необходима. Не будь дисциплины, вы бы, как обезьяны, по деревьям лазили. Военная служба из вас, дураки безмозглые, людей сделает!» Ну, разве это не так? Вообразите себе сквер, скажем, на Карловой площади, и на каждом дереве сидит по одному солдату без всякой дисциплины. Это меня ужасно пугает.
Ярослав ГАШЕК ПОХОЖДЕНИЯ БРАВОГО СОЛДАТА ШВЕЙКА

Расписание занятий, это совмещение в пространстве и времени дисциплины (предмета), преподавателя (преподавателей), аудитории и группы (подгруппы, потока) студентов.

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

Буду краток.

• При проведении занятия могут отсутствовать его любые участники, например, на заседании кафедры студенты, как правило не приходят или студенты ушли на военную кафедру (у них свое расписание), а для того рода занятий нет дисциплины, преподавателя и аудитории.
• Как правило, необходимым требованием ставится непрерывность (отсутствие окон) у студентов и желательно у преподавателей.
• Расписание может составлятся на семестр/полсеместра по неделям, по двум неделям и числитель/знаменатель (нечетная неделя/четная неделя). Также бывает расписание на месяц.
• Занятия должна иметь возможность постановки в ручном режиме (другими словами в редакторе). Например учёный совет или пара большого начальника и даже занятие просто хорошего человека.
• Должна быть система запретов для всех участников занятия. Например, сейчас практически все преподаватели подрабатывают на стороне (иначе не проживешь) или аудиторный фонд разделен между факультетами и после обеда в часть аудиторий занятия ставить нельзя.
• Наличие изощренных пожеланий преподавателей, одному ставь 5 пар в день, чтобы освободить другие дни, а другому больше двух пар в день не ставить, он переутомляется, а если лекцию, то одну пару и обязательно 2 или 3-ю пару.
• Занятия в разных корпусах, требующих для перехода время большее, чем время перерыва между занятиями. Естественно и условие минимизации перемещений.

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

Картинка взята отсюда. ^[1]

Генетический алгоритм

Чисто риторически, повторю основные этапы генетического алгоритма ^[2]:

1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию
3. (Начало цикла)
   1. Размножение (скрещивание)
   2. Мутирование
   3. Вычислить значение целевой функции для всех особей
   4. Формирование нового поколения (селекция)
   5. Если выполняются условия остановки, то конец цикла, иначе (начало цикла).

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

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

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

Алгоритм составления расписаний

Я только опишу сами гены, алгоритм построения по ним решения, скрещивание и мутацию.

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

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

Скрещивание можно организовать несколькими способами. Например один из них. Пусть имеем следующие гены

3 1 2 5 6 4 7
2 3 5 7 1 4 6

Здесь видно, что занятие 3 встречается в обоих генах до позиции 2 включительно, а, например, с позиции 2 до позиции 5 интервал для 1 занятия. Сделаем следующую табличку

_ * * * * _ _ для 1 занятия
* * * _ _ _ _ для 2 занятия
* * _ _ _ _ _ для 3 занятия
_ _ _ _ _ * _ для 4 занятия
_ _ * * _ _ _ для 5 занятия
_ _ _ _ * * * для 6 занятия
_ _ _ * * * * для 7 занятия

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

1 позиция {2, 3}
2 позиция {1, 2, 3}
3 позиция {1, 2, 5}
4 позиция {1, 5, 7}
5 позиция {1, 6, 7}
6 позиция {4, 6, 7}
7 позиция {6, 7}

Для построения решений можно использовать следующий алгоритм. Сначала будем ставить те номера занятий, которые реже встречаются. Если их отсортировать по возрастанию, то будем иметь
1 раз 4
2 раза 3, 5
3 раза 2, 6
4 раза 1, 7
Следовательно сначала ставим 4 занятие на 6 позицию, затем 3 или 5 на позиции {1, 2} или {3, 4} соответственно. На каждом шаге можно кидать коробок спичек. В результате можно получить например следующие шаги для алгоритма скрещивания

* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6

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

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

Заключение

Это продолжение, в некотором смысле, моих постов Программа по составлению расписания занятий в ВУЗе ^[3] и Расчет нагрузки по кафедре ^[4].

Повторно предлагаю следующие решение (набросок).

• GUI на PyQt или PySide
• СУБД PosgreSQL (у меня здесь готово примерно на 80%), в ней кроме самого расписания еще заявки и нагрузка преподавателей, учебные планы и еще много чего (с этой целью опубликую один или несколько топиков)
• web интерфейс на CherryPy+Cheetah (но это может обсуждаться)
• экспорт всяких отчетов (расписаний, карточек учебных поручений и т.д.) в формате OpenDocument (ГОСТ Р ИСО/МЭК 26300-2010. Госстандарт России (01.06.2011) ^[5]) посредством ODFPY ^[6]
• алгоритмы составления расписания от меня (об этом этот топик)
• постановка от меня
• для заинтересованных работа над общим ядром
• для заинтересованных адаптация под собственный ВУЗ и возможность гибко все менять, жизнь идет, а чиновники не дремлют

Спасибо Всем кто откликнулся, после обсуждения этого топика можно будет со организоваться.

Автор: bya