В современном мире все чаще возникает проблема разработки программных средств автоматизированного расписания. Для решения этой задачи были проанализированы существующие методы составления расписания с возможностью полной автоматизации большого объема исходной информации и большого числа трудноформализуемых требований, с целью выявления наиболее эффективных алгоритмов, удовлетворяющих следующим критериям: многофункциональности, универсальности, возможности оптимизации в процессе разработки, простоты реализации математической модели.
Ключевые слова: трудноформализуемые требования, многофункциональность, универсальность, оптимизация, автоматизированные системы, классические методы, теория графов, целочисленное линейное программирование, метаэвристичческие, генетические, метод отжига, метод муравьиных колоний, мульти-агентные системы, метод решения по прецедентам, метод полного перебора, метод ветвей и границ, масштабируемость, детерминированный.
В результате исследования были определены основные методы, встречающиеся на практике при решении задач по составлению автоматизированных систем составления расписания в образовательных учреждениях, на практике часто применяются: классические методы (теория графов, целочисленное линейное программирование); метаэвристические (генетические алгоритмы, метод отжига, метод муравьиных колоний); мульти-агентные системы; метод решения по прецедентам. Кроме того, применяются методы полного перебора, градиентные методы, методы ветвей и границ. Разнообразие методов и подходов при решении задач говорит, о том, что нет универсального способа составления автоматизированных систем, поэтому был проведен анализ методов для определения наиболее оптимального подхода, выявлены достоинства и недостатки методов, а так же их универсальность и ограничения, которым они удовлетворяют.
Классические методы.
Специфической характеристикой классических методов является полная наибольшая степень официализации (математическая точность) как положение задачи составления расписания занятий, так и алгоритмов ее реализации (обращаются «жесткие» алгоритмы). Данные методы разрешают:
а) Исследовать методы повторения решения задачи составления учебных занятий;
б) Понять воздействие на время и четкость решения задачи составления расписаний учебных занятий интересующих нас факторов.
Рассмотрим классические методы решения.
Метод раскраски графа основан на применении математического автомата теории графов, заключается в проблеме составления расписания следующим образом: каждая вершина показывает рассчитанный учебным планом урок, накладки возникают в том случае, если между какими-то двумя вершинами появляется разногласие, к примеру, два урока проводятся в одном классе, то они соединяются ребрами. Это равносильно запрету одновременного проведения этих уроков, тогда проблему составления расписаний можно выразить как проблему уменьшения числа цветов, нужных для раскраски графа, где каждый цвет отвечает единственному периоду расписания. Приближенные методы решения этой задачи встречаются как подзадачи в гибридных методах для решения задачи о составлении расписания.
Использование указанного способа при реализации действительных проблем составления расписания для образовательных систем многочисленного обучения непродуктивно, но комбинация рассматриваемого подхода с другими методами может оказаться практичной.
Вторым методом является метод целочисленного линейного программирования, применяется в решении задачи составления расписания, при помощи решения симплекс-метода для нахождения целевой функции.
Метаэвристические методы решения.
В положении эвристических методов принята эксплуатация разнообразных видов эвристик, или эвристических алгоритмов, при подготовки которых обращаются «слепые» предположения, не подтвержденные соответствующим математическим аргументом. Формирование некоторых правил (эвристик) допускает некоторое ускорение поиска «наилучшего» расписания, но применение таких алгоритмов в преимуществе случаев дает гарантию всего лишь извлечения приблизительного решения задачи (приближение локального экстремума). В данном случае появляется задача оценки приближенности найденного локального экстремума к глобальному экстремуму.
В ряде работ эта задача реализуется с помощью сравнения расписаний, полученных эвристическими методами и расписаний, полученных методами перебора, для применения к проблеме небольшой размерности. В связи с указанным недостатком, эвристические алгоритмы остаются надежным инструментом поиска «лучшего» в определенном смысле решения в тех случаях, когда нахождение оптимального наилучшего решения практически затруднительно или невозможно.
Рассмотрим метаэвристические методы решения:
Генетические алгоритмы — интенсивно развивающиеся методы решения большеразмерных задач целочисленного программирования. Существенные отличия и превосходство генетических алгоритмов в сравнении с классическими методами выражается в следующем:
- генетический алгоритм работает с командами, в которых представлен список параметров, зависящих напрямую от аргументов целевой функции;
- в процессе поиска используется некоторое количество точек поискового инструмента (процесс распараллеливается), а не переключается от точки к точке, как это выполняется в традиционных методах, то есть генетический алгоритм оперирует со своей совокупностью допустимых решений;
- генетический алгоритм в процессе работы не используется вспомогательной информации, что делает существенной скорость его реализации;
- генетический алгоритм применяется как вероятность установки для создания новых точек поиска, так и детерминированные установки для переключения от одних точек к другим.
Метод роя частиц.
В методе роя частиц агентами являются частицы, которые в каждый момент времени имеют в пространстве параметров задачи некоторое положение и скорость. Правила, по которым частицы меняют свое положение и скорость, определяются на основе вычисления целевой функции частицы. В основе канонического метода роя частиц лежит следующий принцип: на каждой итерации для определения следующего положения частицы учитывается информация о наилучшей частице от «соседей» и информация о данной частице на том шаге, когда этой частице соответствовало наилучшее значение целевой функции. Так же существует модификация канонической модели, которая учитывает значение целевой функции всех частиц роя, в некоторых моделях частицы группируются в несколько роев и так далее.
Мульти-агентные системы.
Мульти-агентная система — это самоорганизующаяся система, состоящая из нескольких взаимодействующих между собой интеллектуальных агентов.
Выделяют две роли агентов:
а) Агенты — организаторы (агенты-учителя);
б) Агенты — участники (агенты-классы, агенты-аудитории, агенты).
Агенты взаимодействуют между собой, пытаясь найти приемлемое время и место события (занятия). Мультипликативная система не нашла ни одного допустимого расписания на тестах соревнований ITC 2007, которое проводилось в рамках конференции PATAT (Practice and Theory of Automated Timetabling).
Методы решения по прецедентам.
Прецеденты представляются в виде списка особенность-значение, база прецедентов содержит по две лучших эвристики из предопределенного набора эвристик.
Недостатки метода: низкая гибкость в ограничениях, низкое качество расписания при небольшом количестве прецедентов, плохая масштабируемость. Метод не учитывает специфические требования.
Вывод: в результате анализа существующих методов составления расписания можно сделать вывод об экономической нецелесообразности применения полностью автоматизированных систем составления расписаний в средний школах, институтах из-за трудоемкости построения точных математических моделей, большого числа входных варьированных данных и трудноформализуемых правил описания ограничений при составлении расписания.
Алгоритмы для составления расписания, которые удовлетворяют условию полной автоматизации, могут быть эффективными только для групп с небольшим числом входных варьированных данных. Таким условиям удовлетворяет начальная школа, для которой можно составить полностью автоматизированное расписание.
Литература:
1. Свиридова О. В. Автоматизированная система методов контроля знаний в области информационных технологий 2011.- Сборник материалов 48-й внутривузовской научной конференции Вол-ГТУ, Волгоград, 2011.
2. Семенов С. П. Татаринцев Я. Б. Сравнительный анализ подходов к автоматизации составления расписаний учебных занятий в образовательных учреждениях 2010.- Известия Алтайского государственного университета, 2010.-Т.105.
3. Афонин П. В., Кокшагин О. В. Гибридные генетические алгоритмы для задачи составления расписания проекта 2008.- Известия Южного федерального университета, 2008 № 9–46–51с.
4. Михайлов А. В. Свиридова О. В. Проблема выбора алгоритма для проектирования и разработки автоматизированного составления расписания образовательных учреждений. Студенческий научный форум 2013: v международная студенческая электронная научная конференция. 15 февраля -31 марта 2013г. Направление «Технические науки» Российская академия естествознания. — М.. 2013г. 3с.
