Педагогические  науки/ Стратегические направления реформирова­ния системы образования

 

Искакова, А.Т., Айдарханова А.К., Аубакирова А.С., Касенова Б.Р.

Кокшетауский государственный университет им. Ш. Уалиханова, г. Кокшетау

 

МЕТОДЫ АВТОМАТИЗАЦИИ ПРОЦЕДУРЫ СОСТАВЛЕНИЯ

УЧЕБНЫХ ЗАНЯТИЙ

 

 

 

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

 

Составление расписания учебных занятий является одной из важнейших задач управления учебным процессом. В связи с этим проблема автоматизация составления расписания занятий в образовательных системах массового обучения по-прежнему остается одной из актуальных проблем организации учебного процесса. Действительно, от того насколько "удачно" составлено расписание зависит: качество обучения; экономическая эффективность обучения; комфортность учебы студентов и работы профессорско-преподавательского состава и т.д.

Автоматизация процедуры составления учебных занятий позволяет: учесть множество требований и условий, предъявляемых к расписанию; строго формализовать процедуру получения лучшего, в определенном смысле, расписания; реализовать критерии или оптимизационный подход к составлению расписания; существенно уменьшить временные затраты на составление расписания. [1]

Расписание учебных занятий, по сути, представляет собой пространственно-временной график их проведения с "привязкой" к конкретным учебным группам и дисциплинам обучения. Это означает, что задачу составления расписания на качественном уровне можно сформулировать так: для каждой учебной группы необходимо нужно составить график проведения занятий в течение семестра, в котором указывается аудитория и время проведения занятий по каждой изучаемой дисциплине. В качестве исходной информации для формирования расписания выступают: а) учебные планы специальностей обучения; б) перечень учебных групп различных специальностей обучения конкретного вуза на текущий семестр; в) нагрузка преподавателей (проводимые конкретным преподавателем занятия, их виды и количество в семестре); г) располагаемый для проведения занятий аудиторный фонд с учетом его динамики.

Выходом из создавшегося положения является автоматизация процедуры составления расписания, основанная на формализации данной процедуры с помощью известных методов теории исследования операций и последующей реализации процедуры составления расписания на ЭВМ.

Анализ существующих подходов к составлению расписания учебных занятий. Первые работы в области автоматизации решения задач составления расписания для образовательных систем базировались на адаптации или модификации созданной в 50-60 гг. XX в. классической теории решения задач составления расписания применительно к решению задач эффективному составлению расписания учебных занятий. Данный подход предусматривает формулировку задачи составления расписания занятий в терминах теории расписаний (выделение приборов и требований) с последующим решением ее одним из известных методов целочисленного программирования. [2]

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

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

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

В этом случае строится граф, в котором каждая вершина представляет собой запланированное учебным планом занятие. Если между какими-то двумя вершинами возможны конфликты (появляются накладки), например, два занятия проводятся в одной аудитории, то они соединяются ребром. Это эквивалентно запрету одновременного проведения этих занятий. Тогда задачу составления расписания можно сформулировать как задачу минимизации числа цветов, необходимых для раскраски графа, где каждый цвет соответствует одному периоду расписания. [4]

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

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

В основе интеллектуальных методов решения задачи составления расписания, как правило, лежит использование различного рода эвристик или эвристических алгоритмов, при разработке которых используются интуитивные предположения, не подкрепленные соответствующим математическим обоснованием. Формирование расписания занятий с помощью некоторых правил (эвристик) позволяет несколько ускорить поиск "наилучшего" расписания, но использование таких алгоритмов в большинстве случаев гарантирует лишь нахождение приближенного решения (достижение локального экстремума). В этом случае возникает проблема оценки близости найденного локального экстремума к глобальному экстремуму. [5]

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

Другим, интенсивно развиваемым в последнее время методом решения задач целочисленного программирования, является целый класс методов, объединенных термином "генетические алгоритмы". Основные отличия и преимущества генетических алгоритмов в сравнении с классическими методами заключаются в следующем:

•        Генетические алгоритмы работают с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции;

•        В процессе поиска генетически к алгоритм использует несколько точек поискового пространства, а не переходит от точки к точке, как это происходит в традиционных методах, т.е. генетические алгоритмы оперируют со всей совокупностью допустимых решений;

•        Генетические алгоритмы в процессе работы не используют никакой дополнительной информации, что повышает скорость его работы;

•        Генетический алгоритм использует как вероятностные правила для порождения новых точек поиска, так и детерминированные правила для перехода от одних точек к другим и др. [6]

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

В качестве логической модели особи выступает кортеж кодов хромосом. Генотипом особи принято считать упорядоченный набор генов некоторой особи, фенотипом особи - набор значений (признаков) этих генов. Допустима такая аналогия, генотип - упорядоченная совокупность варьируемых переменных, фенотип - упорядоченная совокупность значений этих переменных. В качестве функции пригодности выступает целевая функция оптимизационной задачи целочисленного программирования.

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

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

Для применения генетических операторов значения этих параметров должны быть представлены в виде двоичной последовательности, т.е. двоичной строки, состоящей из нескольких бит. Количество бит при кодировании гена (хромосомы) зависит от требуемой точности решаемой задачи.

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

В классическом генетическом алгоритме отбор наиболее приспособленных особей осуществляется случайным образом с помощью различных методов генерации дискретных случайных величин, имеющих различные законы распределения. Среди данных методов следует упомянуть отбор методом "колеса рулетки, пропорциональный отбор, отбор с вытеснением, равновероятный отбор и т.д. Каждый из перечисленных методов имеет как свои достоинства, так и недостатки, например, общим недостатком указанных методов является то, что при их использовании в некотором поколении наилучшие особи популяции могут быть потеряны. Одним из способов преодоления этого недостатка является использование элитного отбора, который предусматривает сохранение "наилучшей" особи в популяции ("лучшая'" особь всегда переходит в следующее поколение).

На третьем этапе реализуется операция скрещивания особей. Смысл данной процедуры сводится к нахождению новых комбинаций генетического кода хромосом путем обмена случайным образом участков генетического кода у двух особей, прошедших отбор. Это способствует "получению" дополнительного числа новых особей, среди которых могут оказаться как более приспособленные, так и менее приспособленные особи. Это явление объясняется тем, что точка скрещивания (локус) выбирается случайным образом.

На четвертом этапе к особям популяции, полученным в результате скрещивания, применяется операция мутации. С помощью данной операции можно получать принципиально новые генотипы и фенотипы особи, что приводит к еще большему разнообразию особей в рассматриваемой популяции. Суть этого оператора заключается в следующем: и популяции случайным образом выбирается особь и так же случайно выбирается позиция гена, в которой значение изменяется на противоположное (0—>-1 или 1 —>0). Внесение таких случайных изменений позволяет существенно расширить пространство поиска приемлемых решений задачи целочисленной оптимизации.

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

В качестве критериев останова работы генетического алгоритма принято рассматривать критерии или условия, аналогичные тем, которые используются при пошаговой оптимизации функции многих переменных с помощью градиентных методов:

•         условия, непосредственно свидетельствующие о достижении приемлемых значений целевой функции,

•         условия, непосредственно свидетельствующие о достижении заданных малых значений приращений значения целевой функции,

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

•         Применительно к решению оптимизационных задач с помощью генетических алгоритмов данные условия можно записать следующим образом:

•         сформировано заданное число поколений,

•         популяция достигла заданного уровня качества (например, 80% особей имеют одинаковую генетическую структуру или одинаковое значение функции пригодности),

•         достигнут некоторый уровень сходимости, при котором улучшение популяции не происходит. [7]

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

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

К первой группе относятся недостатки, сходные с недостатками генетических алгоритмов и имеющие место при решении общих задач целочисленной оптимизации. Так, недостаточное разнообразие хромосом в популяции может привести к преждевременному окончанию работы алгоритма и, как следствие, к получению "некорректного" расписания. Далее, завершение работы генетического алгоритма происходит по достижению заданного (не всегда обоснованного) числа итераций, что в ряде случаев препятствует поиску лучшего расписания.

Вторая группа недостатков вызвана слабым учетом специфики задачи составления расписания учебных занятии при организации ее решения с помощью генетических алгоритмов. Так, в известных генетических алгоритмах составления расписания занятий не учитывается наличие связей между объектами расписания и большое многообразие описаний самих объектов расписания. [8]

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

Список литературы:

 

1. Белкин А.Р., Левин М.Ш. Принятие решений: комбинаторные модели аппроксимации информации. М.: Наука, 1990.

2. Березовский Б.А. и др. Многокритериальная оптимизация. Математические аспекты. М.: Наука, 1989.

3. Борисов А.Н., Алексеев A.B., Меркурьев Г.В. и др. Обработка нечеткой информации в системах принятия решений М: Радио и связь, 1989 -304с.

4. Борисов А.Н., Крумберг O.A., Федоров И.П. Принятие решения на основе нечетких моделей: примеры использования; Рига "Знание", 1990, 184 с.

5. Бояршинова А.И. Определение требований к технологическому процессу разработки программного обеспечения / А.И. Бояршинова, И.В. Рудаков // Информационные технологии. Б.м. - 2003.-N3. - с. 18-26.

6. Васильев В.И. Интеллектуальные системы управления с использованием генетических алгоритмов: Учебное пособие / УГАТУ. Уфа: Изд-во УГАТУ, 1999,-105с.

7. Васильков Ю. В. Компьютерные технологии вычислений в математическом моделировании: учебное пособие для вузов / Ю. В. Васильков, IT. И. Василькова.-М.: Финансы и статистика, 2004. 256 с.

8. Введение в математическое моделирование: Учебное пособие / В.И. Ашихмин и др. Под редакцией П.В. Трусова. М.: "Интермет Инжиниринг", 2000.-336 с.

9. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем. М.: Финансы и статистика, 1998. -174 с.

10. Вентцель Е.С. Исследование операций: задачи, принципы, методология. -М.: Наука, Главная редакция физико-математической литературы, 1980. -208 с.