Одной из основных задач развития информационного общества в Российской Федерации является повышения качества образования на основе развития и использования информационных и телекоммуникационных технологий в образовательном процессе вуза [4].
Крайне важной на сегодняшний день представляется автоматизация процессов управления деятельностью вуза, в том числе и создание информационных систем управления. Наличие узкого спектра математических моделей и методов поиска информации значительно затрудняет создание информационных систем управления.
Проблема формирования расписания учебных занятий актуальна для многих вузов, поскольку требует значительных затрат времени и материальных ресурсов.
В статье рассматривается постановка задачи математического моделирования расписания занятий и предлагается один из способов ее решения, основанный на стохастическом методе - генетическом алгоритме.
Постановка задачи математического моделирования
Общая задача составления расписания имеет вид: при имеющемся множестве ресурсов и наложенных на них ограничениях выполнить некоторую систему заданий. Для этого необходимо найти эффективный алгоритм упорядочивания заданий, оптимизирующий требуемую меру эффективности.
В вузе в группах g Є Gk , k= 1...G обучается n-количество студентов, nЄ Ni i=1...m. Численность студентов n является величиной переменной, т. к. в процессе обучения наблюдается движение (зачисление/отчисление) студентов по результатам сессий.
В учебном процессе каждая группа занимается по индивидуальному учебному плану. Учебный план представляет собой множество дисциплин Dl с количеством занятий Pi по каждому предмету. Каждое занятие должно проводиться в то время, которое указывается в расписании: tpi Є Tpi i=1...Zp, где Zp-плановое количество занятий по данному предмету.
По некоторым причинам (техническим, методическим) занятия могут быть отменены или перенесены, поэтому вводится фактическая дата проведения занятий:
tфi Є Tфi i=1...Zф,
где Zф - фактическое количество занятий по данному предмету.
Занятия проводятся в аудиториях аЄAj j=1....J -количество аудиторий, преподавателями- UпЄ п, п=1...П, которые являются специалистами по одной/многим учебным дисциплинам.
После окончания обучения студенты получают дипломы, в которых указываются аттестационные оценки и количество учебных часов по изучаемым дисциплинам.
Необходимо:
Оптимизировать время фактического проведения занятий:
1-если наблюдается ситуация, когда преподаватель провел занятие по
tфi=f(g, p, n, a), предмету в соответствующей аудитории,
0-если наблюдается обратная ситуация.
Ограничения:
1. g Є Gk
pЄ Pi естественные ограничения на переменные,
nЄUп
aЄAi
2. Zф=Zp - соответствие количества фактически проведенных занятий плановому.
Поскольку задача составления расписания и его оптимизации является многокритериальной (NP-сложной), решить ее точными математическими способами не представляется возможным. Необходимо использовать стохастические методы.
К ним относятся:
- алгоритм simulated annealing (моделирование отжига), в котором используется аналогия между процессом решения задачи и моделью охлаждения термодинамической системы;
- алгоритм ant colonies; идея алгоритма основана на моделировании поведения муравьев, связанное с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь [3];
- генетический алгоритм, который представляет собой метод поиска глобального экстремума сложных многокритериальных задач и использующий механизмы кроссовера и мутации, лежащие в основе биологической эволюции.
Рассмотрим возможность применения генетического алгоритма в решении задачи оптимизации учебного расписания.
В качестве критерия оптимизации при поиске лучшего расписания занятий выберем интересы учебных групп g и преподавателей п. Для оценки достоинств и недостатков составленного расписания вводится система штрафов (см. таблицу).
|
№ п/п |
Критерий |
Штраф, баллы |
|
1. 2. 3. 4. 5. |
Штрафы, начисляемые за недостатки в расписании групп. За «окно» в расписании. За каждое «окно» сверх одного. Пустая пара в начале дня. За 2 занятия по одной и той же дисциплине в течение дня. За каждое занятие сверх имеющихся трех по той же дисциплине в течение дня. |
10 20 5 10 60 |
|
6. 7. 8. 9. |
Штрафы, начисляемые за недостатки в расписании преподавателей. За наличие пар на выходных. За каждое «окно» сверх одного. Не предусмотрено время переезда между корпусами. За каждую лишнюю пару сверх максимального числа пар в день. |
4 30 60 6 |
|
10. |
Общие штрафы Непопадание одного занятия в сетку расписания. |
60 |
Система штрафов является механизмом, позволяющим регулировать процесс оптимизации расписания. Изменяя количество и значения критериев оптимизации, можно получить расписание, удовлетворяющее тем или иным параметрам.
Приспособленность варианта расписания обратно пропорциональна его весу. А вес (фитнес-функция) - это сумма штрафных баллов, которая суммируется для каждой группы или преподавателя.[1] Критерии выбираются в зависимости от требований к расписанию конкретного вуза, а количество штрафных баллов варьируется для той программной среды, в которой реализуется данный алгоритм (например, на С++) [2].
Таким образом, решение задачи оптимизации учебного расписания можно рассматривать с позиции использования генетического алгоритма, взяв в качестве критерия оптимизации систему штрафов.
СПИСОК ЛИТЕРАТУРЫ
1. Моисеенко А.С., Матьяш В.А. Разработка методов скрещивания эпох для предотвращения сходимости генетического алгоритма // Информационно-управляющие системы. №4, 2008, с. 9-13.
2. Herrera F., Lozano M., Sanches A. M., Hybrid Crossover Operators for Real-Coded Genetic Algorithmus: An Experimental Study // Soft Comput / 9(4): 280-298 (2004).
3. Heuristische Optimierungsverfahren in der Wirtschaftsinformatik. Andreas Fink und Franz Rothlauf/University of Mannheim Department of Information Systems 1D-68131 Mannheim (Germany) 2006.
4. «Стратегия развития информационного общества в Российской Федерации». Утверждена Президентом РФ В. В. Путиным 07.02.2008. №Пр-212.