Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,909

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ В ЗАДАЧЕ ОПТИМИЗАЦИИ УЧЕБНОГО РАСПИСАНИЯ ВУЗА

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

Одной из основных задач развития информационного общества в Российской Федерации является повышения качества образования на основе развития и использования информационных и телекоммуникационных технологий в образовательном процессе вуза [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.


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

Яндыбаева Н.В. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ В ЗАДАЧЕ ОПТИМИЗАЦИИ УЧЕБНОГО РАСПИСАНИЯ ВУЗА // Современные наукоемкие технологии. – 2009. – № 11. – С. 97-98;
URL: http://top-technologies.ru/ru/article/view?id=25972 (дата обращения: 14.11.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074