Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Файлы

Яндыбаева Н.В.

Статья в формате PDF

138 KB

Одной из основных задач развития информационного общества в Российской Федерации является повышения качества образования на основе развития и использования информационных и телекоммуникационных технологий в образовательном процессе вуза [4].

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

Проблема формирования расписания учебных занятий актуальна для многих вузов, поскольку требует значительных затрат времени и материальных ресурсов.

В статье рассматривается постановка задачи математического моделирования расписания занятий и предлагается один из способов ее решения, основанный на стохастическом методе - генетическом алгоритме.

Постановка задачи математического моделирования

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

В вузе в группах g Є G_k , k= 1...G обучается n-количество студентов, nЄ N_i i=1...m. Численность студентов n является величиной переменной, т. к. в процессе обучения наблюдается движение (зачисление/отчисление) студентов по результатам сессий.

В учебном процессе каждая группа занимается по индивидуальному учебному плану. Учебный план представляет собой множество дисциплин D_l с количеством занятий P_i по каждому предмету. Каждое занятие должно проводиться в то время, которое указывается в расписании: t_pi Є T_pi i=1...Z_p, где Z_p-плановое количество занятий по данному предмету.

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

t_фi Є T_фi i=1...Z_ф,

где Z_ф - фактическое количество занятий по данному предмету.

Занятия проводятся в аудиториях аЄA_j j=1....J -количество аудиторий, преподавателями- U_пЄ п, п=1...П, которые являются специалистами по одной/многим учебным дисциплинам.

После окончания обучения студенты получают дипломы, в которых указываются аттестационные оценки и количество учебных часов по изучаемым дисциплинам.

Необходимо:

Оптимизировать время фактического проведения занятий:

                                          1-если наблюдается ситуация, когда преподаватель провел занятие по

t_фi=f(g, p, n, a),                    предмету в соответствующей аудитории,

                                              0-если наблюдается обратная ситуация.

Ограничения:

1.      g Є G_k

         pЄ P_i                      естественные ограничения на переменные,

         nЄU_п

         aЄA_i

2.            Z_ф=Z_p - соответствие количества фактически проведенных занятий плановому.

Поскольку задача составления расписания и его оптимизации является многокритериальной (NP-сложной), решить ее точными математическими способами не представляется возможным. Необходимо использовать стохастические методы.

К ним относятся:

- алгоритм simulated annealing (моделирование отжига), в котором используется аналогия между процессом решения задачи и моделью охлаждения термодинамической системы;

- алгоритм ant colonies; идея алгоритма основана на моделировании поведения муравьев, связанное с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь [3];

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

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

В качестве критерия оптимизации при поиске лучшего расписания занятий выберем интересы учебных групп g и преподавателей п. Для оценки достоинств и недостатков составленного расписания вводится система штрафов (см. таблицу).

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

Приспособленность варианта расписания обратно пропорциональна его весу. А вес (фитнес-функция) - это сумма штрафных баллов, которая суммируется для каждой группы или преподавателя.[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.

Библиографическая ссылка