Авторы:И.С. Конькова
Источник: Вестник ТвГТУ. 2012. Вып. 22. С. 26-31.
Одной из основных задач развития информационного общества в Российской Федерации является повышение качества образования на основе развития и использования информационных и телекоммуникационных технологий в образовательном процессе вуза [1].
Автоматизация процессов управления деятельностью вуза, безусловно, на сегодняшний день задача, требующая к себе внимания, необходимо создание информационных систем управления. Одной из важнейших и актуальных задач, решаемых системой управления образовательным учреждением, является составление расписания занятий. При этом формирование расписания учебных занятий для многих вузов проблемно, поскольку требует значительных затрат времени и материальных ресурсов.
Действительно, удачно составленное расписание в значительной степени определяет:
Автоматизированное составление расписания учебных занятий позволяет:
Составление расписания для небольших учебных заведений с малым числом учебных групп и изучаемых дисциплин не представляет особых затруднений. Иначе обстоит дело с крупными образовательными учреждениями, для которых характерно наличие: большого числа студенческих групп на каждом курсе обучения; большого числа дисциплин обучения для каждой студенческой группы в течение семестра, различных типов аудиторных занятий (лекционные, практические, лабораторные); различных видов занятий с различной длительностью их проведения, большого контингента преподавателей, большого аудиторного фонда, включающего в себя различные по площади и по назначению аудитории, многосменного характера организации учебного процесса и т. д.
Известные подходы, основанные на применении методов целочисленного программирования, оказываются малоэффективными по следующим причинам: а) отсутствует гарантия получения приемлемого решения задачи; б) резко (экспоненциально) увеличиваются временные затраты на поиск лучшего (приемлемого) решения с ростом размерности решаемой задачи, что характерно, к примеру, для вузов; в) практически невозможным становится (в силу большой размерности, громоздкости и сложности получаемой математической модели решаемой задачи) оценка влияния на решение задачи интересующих факторов, оценка критичности полученного решения к данным факторам; г) слабо учитываются существующие связи между объектами целочисленной оптимизации; д) требуется большая полнота априорной информации о характеристиках образовательной системы. Поскольку задача составления расписания и его оптимизации является многокритериальной (NP-сложной), решить ее точными математическими способами не представляется возможным. Необходимо использовать стохастические методы. Одним из таких методов является генетический алгоритм. Он представляет собой метод поиска глобального экстремума сложных многокритериальных задач, который использует механизмы кроссовера и мутации, лежащие в основе биологической эволюции. Рассмотрим возможность применения генетического алгоритма в решении задачи оптимизации учебного расписания.
Общая задача составления расписания: при имеющемся множестве ресурсов и наложенных на них ограничениях выполнить некоторую систему заданий. Для этого необходимо найти эффективный алгоритм упорядочивания заданий, оптимизирующий требуемую меру эффективности [3].
В вузе в группах g ∈ Gk, k ∈ 1,G обучается n количество студентов n ∈ Ni, i = 1,m. Численность студентов n является величиной переменной, так как в процессе обучения наблюдается движение (зачисление и отчисление) студентов по результатам сессий.
В учебном процессе каждая группа занимается по индивидуальному учебному плану. Учебный план представляет собой множество дисциплин Di с количеством занятий Pi по каждому предмету. Каждое занятие должно проводиться в то время, которое указывается в расписании: tpi ∈ Tpi i = 1,Zp, где Zp – плановое количество занятий по данному предмету.
По некоторым причинам (техническим, методическим) занятия могут быть отменены или перенесены, поэтому вводится фактическая дата проведения занятий tfi ∈ Tfi i = 1,Zf Zf – фактическое количество занятий по данному предмету.
Занятия проводятся в аудиториях a ∈ Aj , j = 1,J преподавателями Ur ∈ r,r = 1,R, которые являются специалистами по одной или многим учебным дисциплинам.
Таким образом, необходимо оптимизировать время фактического проведения занятий: tfi = f (g,p,n,a)
Функция tfi принимает значение 1, когда устанавливается, что преподаватель проведет занятие по предмету в соответствующей аудитории, и принимает значение 0, если наблюдается обратная ситуация.
На практике необходимо учитывать и формализовывать такие требования: отсутствие окон (непрерывность) у студентов и желательно у преподавателей; расписание может составляться на семестр по неделям, по двум неделям и числителю/знаменателю (синяя неделя/красная неделя); аудиторный фонд, как правило, разделен между кафедрами; необходимость проведения определенных типов занятий в подходящее им время (допустим, лекции, как правило, проводят утром, а физкультуру ставят ближе к середине и концу учебного дня); личные пожелания преподавателей, в какое время они хотели бы проводить занятия; минимизация перемещений студентов и преподавателей в другие корпуса вуза и др.
Как видно из постановки задачи, оценить, насколько качественно составлено расписание, можно только после его полного составления. Следовательно, применение генетических алгоритмов может позволить построить решение искомой задачи. При этом генетические алгоритмы очень быстро сходятся к оптимальному решению в начале цикла, и тогда практически не будет ограничений на объем входных данных.
Рассмотрим возможность применения генетического алгоритма в решении задачи оптимизации учебного расписания.
В общем виде генетический алгоритм состоит из следующих шагов [2]: 1) задание целевой функции (приспособленности) для особей популяции; 2) инициализация, или выбор исходной популяции хромосом; 3) проверка условия остановки алгоритма; 4) селекция хромосом; 5) применение генетических операторов; 6) формирование новой популяции; 7) выбор «наилучшей» хромосомы.
Наиболее характерная ошибка применения генетических алгоритмов состоит в выборе генов. Часто в качестве генов выбирают просто само решение. Выбор генов является самым нетривиальным и творческим элементом при создании генетического алгоритма. При этом выбор генов должен удовлетворять следующим основным требованиям: по набору генов решение искомой задачи должно строиться быстро и однозначно; при скрещивании потомок должен наследовать характерные черты родителей; набор генов должен давать весь набор (возможно оптимальных) решений задачи.
Описание алгоритма составления расписания Как правило, составление расписания опытный диспетчер начинает с расстановки в сетке расписания так называемых «узких» мест. Например, зачастую существует нехватка больших потоковых аудиторий или компьютерных классов, при этом у первых курсов много потоковых лекций и одновременно занятий в подгруппах по компьютерным классам, английскому/немецкому/французскому языкам и т. д. Затем, используя расставленные занятия как скелет, уже достаточно быстро можно достроить расписание. Попробуем сымитировать, в некотором смысле, этот процесс.
Часть занятий уже стоит в расписании, оставшиеся – последовательно занумеруем. Массив номеров занятий будем считать геномом, хотя в принципе здесь важен лишь порядок занятий. Для построения расписания будем последовательно извлекать номера занятий и ставить выбранное занятие в расписание, учитывая необходимые требования и максимизируя целевую функцию для студентов, преподавателей и аудиторий (у них тоже бывают критерии занятости).
Если необходимым требованиям не удается удовлетворить, то особь с таким геномом может быть отброшена как нежизнеспособная. Если расписание составить не получается, то можно заменить необходимые требования штрафом в целевой функции.
Скрещивание можно организовать несколькими способами. Приведем пример одного из них. Пусть имеем следующие гены:
3125647
2357146
Здесь видно, что занятие 3 встречается в обоих генах до позиции 2 включительно, а, например, с позиции 2 до позиции 5 – интервал для 1 занятия и т. д. Тогда это можно представить следующим образом:
_****__ для 1 занятия
***____ для 2 занятия
**_____ для 3 занятия
_____*_ для 4 занятия
__**___ для 5 занятия
____*** для 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*
3**5*46
3*25*46
3*25746
3125746
Поскольку можно и не построить правильную последовательность, то лучше алгоритм организовать в виде простой рекурсии для возможности повторения алгоритма, т. е. организации некоторого перебора.
Данный простейший пример демонстрирует принцип работы генетического алгоритма. В классическом генетическом алгоритме используется двоичное представление хромосом, селекция методом колеса рулетки и точечное скрещивание (с одной точкой скрещивания). Однако с помощью классического генетического алгоритма найти решение задачи, подобной задаче составления расписания вуза, весьма затруднительно, требуются значительные затраты времени и ресурсов. Для повышения эффективности работы создано множество модификаций основного алгоритма. Они связаны с применением других методов селекции, с модификацией генетических операторов (в первую очередь, оператора скрещивания), с преобразованием функции приспособленности (путем ее масштабирования).
собленности (путем ее масштабирования). Так, например, стандартный метод селекции «рулетка» обладает рядом недостатков. Один из них состоит в том, что особи с очень малым значением функции приспособленности слишком быстро исключаются из популяции, что может привести к преждевременной сходимости генетического алгоритма. Поэтому созданы и используются альтернативные алгоритмы селекции, например, турнирная и ранговая селекции.
Оптимизация учебного расписания с помощью генетического алгоритма – задача нетривиальная и трудоемкая. Прежде всего, требуется учитывать и формализовать все требования, предъявляемые к составителю расписания, учитывать их в целевой функции. Кроме этого, требуется вести поиск адаптивного генетического алгоритма, новых модифицированных генетических операторов, к примеру, применять неклассические методы селекции хромосом, ввод коэффициентов качества составленного расписания и т. п.
В статье приведена начальная постановка задачи составления расписания, описан пример, моделирующий работу генетического алгоритма. Дальнейшие исследования будут направлены на проектирование новой модифицированной структуры генетического алгоритма, позволяющей повысить качество получаемых решений и апробацию разработанного алгоритма при практическом решении задачи составления расписания вуза.
1. Стратегия развития информационного общества в Российской Федерации от 7 февр.
2008 г. № Пр-212 / Рос. газ. 2008. 16 февр.
2. Рутковская, Д. Нейронные сети, генетические алгоритмы и нечеткие системы /
Д. Рутковская, М. Пилиньский, Л. Рутковский; пер. с польск. И.Д. Рудинского. М.:
Горячая линия – Телеком, 2006. 452 с.
3. Яндыбаева, Н.В. Генетический алгоритм в задаче оптимизации учебного расписания
вуза / Н.В. Яндыбаева // Современные наукоемкие технологии. 2009. № 11. С. 97–98.