Воцарилась тишина, которую нарушил сам Швейк, вздохнув:
— … На военной службе должна быть дисциплина — без неё никто бы и пальцем для дела не пошевельнул. Наш обер-лейтенант Маковец всегда говорил: «Дисциплина, болваны, необходима. Не будь дисциплины, вы бы, как обезьяны, по деревьям лазили. Военная служба из вас, дураки безмозглые, людей сделает!» Ну, разве это не так? Вообразите себе сквер, скажем, на Карловой площади, и на каждом дереве сидит по одному солдату без всякой дисциплины. Это меня ужасно пугает.
Ярослав ГАШЕК ПОХОЖДЕНИЯ БРАВОГО СОЛДАТА ШВЕЙКА
Расписание занятий, это совмещение в пространстве и времени дисциплины (предмета), преподавателя (преподавателей), аудитории и группы (подгруппы, потока) студентов.
Постановка задачи
Буду краток.
- При проведении занятия могут отсутствовать его любые участники, например, на заседании кафедры студенты, как правило не приходят или студенты ушли на военную кафедру (у них свое расписание), а для того рода занятий нет дисциплины, преподавателя и аудитории.
- Как правило, необходимым требованием ставится непрерывность (отсутствие окон) у студентов и желательно у преподавателей.
- Расписание может составлятся на семестр/полсеместра по неделям, по двум неделям и числитель/знаменатель (нечетная неделя/четная неделя). Также бывает расписание на месяц.
- Занятия должна иметь возможность постановки в ручном режиме (другими словами в редакторе). Например учёный совет или пара большого начальника и даже занятие просто хорошего человека.
- Должна быть система запретов для всех участников занятия. Например, сейчас практически все преподаватели подрабатывают на стороне (иначе не проживешь) или аудиторный фонд разделен между факультетами и после обеда в часть аудиторий занятия ставить нельзя.
- Наличие изощренных пожеланий преподавателей, одному ставь 5 пар в день, чтобы освободить другие дни, а другому больше двух пар в день не ставить, он переутомляется, а если лекцию, то одну пару и обязательно 2 или 3-ю пару.
- Занятия в разных корпусах, требующих для перехода время большее, чем время перерыва между занятиями. Естественно и условие минимизации перемещений.
Вывод. Как видно из постановки, оценить качество расписания возможно, только после его полного составления. Следовательно применение генетических алгоритмов может позволить построить решение искомой задачи и даже получить в некотором смысле одно из хороших. При этом генетические алгоритмы очень быстро сходятся к оптимальному в начале и значит практически не будет ограничений на объем входных данных.
Картинка взята отсюда.
Генетический алгоритм
Чисто риторически, повторю основные этапы генетического алгоритма:
- Задать целевую функцию (приспособленности) для особей популяции
- Создать начальную популяцию
- (Начало цикла)
- Размножение (скрещивание)
- Мутирование
- Вычислить значение целевой функции для всех особей
- Формирование нового поколения (селекция)
- Если выполняются условия остановки, то конец цикла, иначе (начало цикла).
Наиболее характерная ошибка применения генетических алгоритмов состоит в выборе генов. Часто в качестве генов выбирают просто само решение. Выбор генов является самым нетривиальным и творческим элементом при создании генетического алгоритма. Лично я считаю, что выбор генов должен удовлетворять двум следующим основным требованиям.
- По набору генов решение искомой задачи должно строится быстро и однозначно.
- При скрещивании потомок должен наследовать характерные черты родителей.
Комментарий. Набор генов должен давать весь набор (возможно оптимальных) решений задачи. В принципе, не обязательно требовать взаимной однозначности, достаточно чтобы отображение генов на пространство решений было на (сюръекцией).
Алгоритм составления расписаний
Я только опишу сами гены, алгоритм построения по ним решения, скрещивание и мутацию.
Как составляет расписание опытный диспетчер. Слово опытный означает, что диспетчер уже составлял/а расписание уже на раз и знает его узкие места. Например нехватку больших потоковых аудиторий или компьютерных классов. Первый курс, поскольку у них много потоковых лекций и одновременно занятий в подгруппах по компьютерным классам, английский/английский с нуля/немецкий/французский и т.д., а начальство при этом требует, чтобы у первого курса не в коем случае не было окон и не больше двух лекций в день и дни были равномерно нагружены. Поэтому опытный диспетчер расставляет сначала «узкие занятия», занятия начальства по их требованию и занятия особо надоедливых преподавателей. Затем используя расставленные занятия как скелет, достаточно быстро достраивает расписание. Попробуем с имитировать, в некотором смысле, этот процесс.
Часть занятий уже у нас стоит в расписании, оставшиеся последовательно занумеруем. Массив номеров занятий будем считать геномом, хотя в принципе здесь важен лишь порядок занятий. Для построения расписания будем последовательно извлекать номера занятий и ставить выбранное занятие в расписание удовлетворяя необходимым требованиям и максимизируя целевую функцию для студентов, преподавателей и аудиторий (у них тоже бывают критерии занятости).
Если необходимым требованиям не удается удовлетворить, то особь с таким геномом может быть отброшена как нежизнеспособная. Если расписание составить не получается, то можно заменить необходимые требования штрафом в целевой функции.
Скрещивание можно организовать несколькими способами. Например один из них. Пусть имеем следующие гены
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
Поскольку можно и не построить правильную последовательность, то лучше алгоритм организовать в виде простой рекурсии для возможности повторения алгоритма, т.е. организации некоторого перебора.
Мутацию можно организовать достаточно просто, случайной перестановкой номеров занятий.
Заключение
Это продолжение, в некотором смысле, моих постов Программа по составлению расписания занятий в ВУЗе и Расчет нагрузки по кафедре.
Повторно предлагаю следующие решение (набросок).
- GUI на PyQt или PySide
- СУБД PosgreSQL (у меня здесь готово примерно на 80%), в ней кроме самого расписания еще заявки и нагрузка преподавателей, учебные планы и еще много чего (с этой целью опубликую один или несколько топиков)
- web интерфейс на CherryPy+Cheetah (но это может обсуждаться)
- экспорт всяких отчетов (расписаний, карточек учебных поручений и т.д.) в формате OpenDocument (ГОСТ Р ИСО/МЭК 26300-2010. Госстандарт России (01.06.2011)) посредством ODFPY
- алгоритмы составления расписания от меня (об этом этот топик)
- постановка от меня
- для заинтересованных работа над общим ядром
- для заинтересованных адаптация под собственный ВУЗ и возможность гибко все менять, жизнь идет, а чиновники не дремлют
Спасибо Всем кто откликнулся, после обсуждения этого топика можно будет со организоваться.
Автор: bya
