Реферат по теме выпускной работы
1. Цель исследования, планируемые результаты.
3. Обзор исследований и разработок.
Введение
Организация учебного процесса в высшем учебном заведении является основой подготовки высококвалифицированных специалистов. Базисом учебного процесса обучения является составление «оптимального» расписания учебных занятий. Расписание учебных занятий должно удовлетворять требованиям по обеспечению все более возрастающих требований к будущим специалистам. Существует достаточное количество программных комплексов для составления учебных расписаний. Первые программы автоматизированного составления расписаний учебных занятий появились в начале 90-х годов. К сожалению, лишь небольшая их часть реально используется в учебных заведениях различного уровня. Главными проблемами остаются: высокая трудоемкость получения решений, несовершенство технологии проектирования расписания, низкая эргономичность процедуры и высокие временные затраты [1].
1. Цель исследования, планируемые результаты
Задача автоматизации составления расписаний – одна из тех задач, которые издавна тревожили душу математиков и программистов. Широкие разработки в этом направлении велись с начала XX века.
С развитием компьютерной техники и компьютерных вычислений очень многие задачи старались перевести на автоматизированный, а в лучшем случае и полностью автоматический режим вычисления. Не удивительно, что с середины 90-х годов начинается настоящий бум на реализацию программ автоматического составления расписания. Таких программ было множество, они реализовывали различные алгоритмы, однако со своей задачей они совершенно не справлялись. Результаты работ этих программ выдавали в большинстве своём следующие минусы:
1) Долгое время работы. Пользователь мог запустить программу на выполнение, уйти домой, а через неделю получить сообщение, о невозможности совмещения часов, хотя диспетчера этот учебный план располагали в сетку расписания даже с запасом.
2) Неудобный интерфейс и загрузка базы данных
3) Совершенно неудобные расписания и для студентов, и для преподавателей.
4) Крайняя затруднительность расчета, если предмет предполагает деление группы на подгруппы и деление недель на четную\нечетную.
В результате всего этого были выдвинуты некоторые теории, которые гласили, что задача не имеет решения, поскольку лежит в области межличностных отношений, а поэтому не может быть решена путём алгоритмизации и последующей автоматизации [1].
При разработке алгоритмов автоматизированного составления расписания занятий остро стоит проблема создания универсальных алгоритмов, учитывающих специфику условий каждой конкретной задачи. Такие алгоритмы должны быть достаточно "гибкими", т.е. без существенного их изменения можно было бы включать и исключать требования из системы требований к расписанию. Однако попытка решать задачу каким-либо одним единственным универсальным алгоритмом на данный момент не представляется возможной. Алгоритмы, позволяющие решать широкий класс задач, не дают той эффективности, которую обеспечивают более конкретные, адаптированные с учётом конкретных условий алгоритмы.
Для систем составления расписания занятий характерна сильная зависимость от специфики конкретных учебных заведений уже на уровне математических моделей и представления данных, что затрудняет использование типовых систем. Систему, созданную в одном вузе, обычно без изменения и доработки невозможно эффективно использовать в другом. К тому же многие из них создавались достаточно давно и с их помощью невозможно эффективно решать поставленную задачу [2].
Целью данной работы является анализ основных методов автоматизации составления расписания. Проанализировав основные методы автоматизированного составления расписаний мы можем выбрать то, которое в будущем будем использовать для построения автоматической системы построения первой версии расписания в АСК «Деканат» ФКНТ ДонНТУ. Это и будет являться результатом работы.
2. Постановка задачи
Формально задачу составления расписания можно рассматривать следующим образом: нам заданы:
• Множество преподавателей.
• Множество групп.
• Множество аудиторий.
• Множество предметов.
• Учебный план.
Также могут быть выдвинуты два ряда требований к расписанию:
• Жесткие или обязательные требования:
o Для определённых пар нужны вместительные аудитории (например, потоковые лекции).
o Для определённых пар нужны аудитории со специальным оборудованием (например, аудитории с аналого-вычислительными комплексами для практических занятий по предметам, связанными с электроникой).
• Мягкие требования:
o Отсутствие окон у студентов.
o Отсутствие окон у преподавателей.
o Минимальное количество переездов между группами корпусов, если университетский городок находится не в одном месте (например, Донецкий Национальный Технический Университет имеет 3 группы корпусов достаточно удалённых друг от друга).
o Лекции должны быть утром, практические занятия – на последних парах.
o Равномерная нагрузка студентов.
o «Библиотечные» дни для преподавателей.
o Прочие условия.
Как видно из постановки, оценить качество расписания возможно, только после его полного составления.
Сама задача очень тяжела, и некоторыми учеными названа «задачей без решения». Взглянув на рисунок №1 вы можете увидеть как много частей в этом безусловно нелёгком деле.
Рис. №1 Основные компоненты моделей составления расписаний [4].
Для решения поставленных проблем, требуется построение гибкой и легко адаптируемой системы на основе новых принципов, с использованием современных компьютерных технологий. Необходима система, составляющая расписание в соответствии с выбранными критериями и заданными требованиями, т.е. берущая на себя как можно больше функций человека, чтобы расписание приходилось меньше доводить вручную. Данные возможности должны осуществляться также, без изменения исходного кода системы, чтобы использоваться пользователями-непрограммистами. Для покрытия наиболее типичных случаев, необходим анализ и применение нескольких типовых алгоритмов, реализующих составление расписаний. Нужна система поддержки принятия решений, имеющая возможность настройки, в идеале берущая на учет все возможные ограничения и пожелания.
Данная система должна:
• иметь возможность дополнения и изменения существующей базы данных;
• иметь возможность дополнения и изменения пользовательского интерфейса;
• обеспечивать возможность самостоятельно подключения дополнительных самостоятельно разработанных алгоритмов, возможно с вызовом некоторых предоставляемых системой типовых алгоритмов.
Всё это давало бы возможность задавать в каждом вузе требования, отвечающие его условиям, и, с помощью подбора и настройки подходящего алгоритма, получать требуемое расписание.
3. Обзор исследований и разработок
В теории расписаний выделяют такие группы методов решения задач:
• Точные методы (методы на основе полного перебора). К ним относятся методы линейного программирования, алгоритмы целочисленного программирования Гомори, в котором предполагается, что все коэффициенты в выражениях и целевой функции являются целыми числами. Если учесть неделимость отдельных видов работ и ресурсов, комбинаторный характер операций, из которых состоит расписание, то такой метод имеет определенные возможности.
• Приближенные методы.
Их можно разбить на следующие группы:
o методы локальной оптимизации;
o модификации точных методов;
o эвристические методы, максимально учитывающие специфику решаемых задач;
o методы случайного поиска;
o методы, сочетающие локальную оптимизацию со случайным поиском.
Отметим, что многие приближенные алгоритмы позволяют решать задачи дискретной оптимизации в диалоговом режиме. Это дает возможность в зависимости от выделяемых ресурсов (времени, памяти компьютера и т.п.) последовательно улучшать полученное решение путем изменения всех или некоторых исходных данных. Значительная часть приближенных алгоритмов дискретной оптимизации базируется на использовании вычислительных схем известных точных методов, таких как метод ветвей и границ, последовательного анализа вариантов и прочих. Одними из наиболее развитых приближенных методов являются методы локальной оптимизации, имеющие своей целью отыскание локально оптимальных решений.
Нередко в этих методах на определенных этапах решения задачи используются методы случайного поиска, а также различные способы (эвристики), которые дают возможность сократить ход вариантов и максимально учитывают специфику задачи. Следует отметить, что алгоритмы, в которых комбинируются различные идеи, на практике часто оказываются наиболее эффективными. С помощью этих методов были решены многочисленные сложные задачи классификации объектов, размещения, планирования и проектирования. Основное преимущество этих методов – простота реализации, а основной недостаток – это то, что они не могут адаптироваться к условиям решаемой задачи. Значительно более гибкими являются методы, у которых вероятностный закон зависит от исходов предыдущих испытаний и изменяется от итерации к итерации. Это методы случайного поиска с обучением.
В своей работе я проанализирую 4 базовых алгоритма, которые используются чаще всего в задачах автоматизации составления расписаний, метод перебора, метод границ и ветвей, генетический метод, эвристические методы.
3.1. Метод перебора
Метод перебора или метод равномерного поиска– простейший из методов поиска значений. Любую задачу построения алгоритма можно решить с помощью этого метода, однако сложность перебора зависит от количества условий задачи.
Метод перебора интуитивно прост и понятен. Его единственное преимущество по сравнению с другими методами – он ГАРАНТИРОВАННО даст вам идеальное решение, если оно конечно существует, даже с учетом всех ограничений и требований.
Суть этого метода – попробовать абсолютно все комбинации и перестановки в сетке расписаний.
Отсюда вытекают следующие характеристики этого метода: он прост, он гарантирует результат, при его существовании, он идеально эффективно справляется с малыми задачами, например составление расписания для начальной школы, где 3 параллели по 4 класса в каждой.
Единственный минус, который перечеркивает все преимущества, этого метода вытекает из его плюсов: этот метод абсолютно неэффективен при увеличении количества условий. Если для расписания начальной школы этот метод эффективен, то для расписания уже всей школы результата придётся ждать уже гораздо большее количество времени. Для Донецкого национального технического университета с сотнями групп, преподавателей, аудиторий и предметов, перебор может длиться столетия. Ведь количество вариантов для одной только группы 2*25! (2 недели по 5 занятий 5 раз в день). Поэтому этот метод считается очень неудачным для заданной задачи.
3.2 Метод ветвей и границ
Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Метод ветвей и границ – один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи.
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия “разделяй и властвуй”). На каждом шаге метода элементы разбиения подвергаются проверке для сравнения подмножества и выяснения, оптимальное это решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.
Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д.
Анализируя этот метод мы можем понять, что, хоть он и основан на переборе, он перебирает гораздо меньше вариантов, чем его «отец»—метод полного перебора.
Минусы метода – он уже не настолько прост, как метод полного перебора, он тяжело применяется к теории расписания занятий, он всё еще слишком долгий по выполнению.
3.3 Генетический алгоритм
Генетический алгоритм (англ. genetic algorithm) – это алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Интенсивно развиваются в последнее время методы решения большеразмерных задач целочисленного программирования, объединенных термином «генетические алгоритмы». Основные отличия и преимущества генетических алгоритмов в сравнении с классическими методами заключаются в следующем:
- генетический алгоритм (ГА) работает с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции;
- в процессе поиска ГА использует несколько точек поискового пространства (процесс распараллеливается), а не переходит от точки к точке, как это происходит в традиционных методах, т. е. ГА оперирует со всей совокупностью допустимых решений;
- ГА в процессе работы не использует дополнительной информации, что повышает скорость его работы;
- ГА использует как вероятностные правила для порождения новых точек поиска, так и детерминированные правила для перехода от одних точек к другим и др.
Генетический алгоритм состоит из следующих компонент:
- Хромосома. В качестве хромосомы выступает решение рассматриваемой задачи. Хромосома состоит из совокупности генов – параметров.
- Начальная популяция хромосом.
- Набор операторов для генерации нового поколения. Генетическими операторами являются оператор кроссовера (crossover operator) и оператор мутации (mutation operator). За счет кроссовера производится обмен генами между особями, то есть процесс скрещивания особей. Пусть имеются две родительские особи с хромосомами X ={ xi, I = 1, N}и Y ={ yi, I = 1, N}.
- Случайным образом определяется точка разрыва (crossover point), внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими.
- Оператор мутации инвертирует случайно выбранный бит (ген) в хромосоме.
- Целевая функция для оценки приспособленности (fitness) решения.
Рис.2 схема работы генетического алгоритма.
Рис. №3 схема работы генетического алгоритма. Анимация (21 кадр, 1 повтор).
Генетические алгоритмы имеют недостатки, которые можно представить в виде трех групп:
• Завершение работы генетического алгоритма происходит по достижению заданного (не всегда обоснованного) числа итераций, что в ряде случаев препятствует поиску лучшего расписания.[9]
• Слабый учет специфики задачи составления расписания учебных занятий при организации ее решения с помощью генетических алгоритмов. Так, в известных генетических алгоритмах составления расписания занятий не учитывается наличие связей между объектами расписания и большое многообразие описаний самих объектов расписания.
К плюсам же этого метода можно отнести то, что он даёт оптимальное решение в 99% случаев и достаточно быстр [1].
3.4 Эвристические алгоритмы
Эвристический алгоритм — это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.
Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не корректный»), но при этом практически полезный алгоритм.
Она не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).
Эвристические алгоритмы основаны на приеме, который называется приемом снижения требований. Он заключается в отказе от поиска оптимального решения за приемлемое время. Эвристические алгоритмы используют различные разумные соображения без строгих обоснований, поэтому довольно сложно сделать обобщение эвристических методов. Сталкиваясь с конкретной задачей, человек может обдумывать способ получения решения, обладающего невысокой стоимостью, очень мало заботясь при этом о теоретическом обосновании.
Задача составления расписания сводится к задаче удовлетворения ограничений. Процесс составления расписания представляется как процесс распределения времени и места между занятиями таким образом, чтобы выполнялось множество ограничений. Обычно для этого задается множество правил. Данный метод предполагает «жесткие» (hard) и «мягкие» (soft) ограничения. Выполнение «жестких» ограничений обязательно, а «мягких» желательно. На каждом шаге расставляется одна группа или курс. Если на каком-либо шаге невозможно назначить время или аудиторию таким образом, чтобы не нарушились ограничения, то ослабляется одно из «мягких» ограничений. И так повторяется до тех пор, пока не станет возможным назначить время или аудиторию без нарушений оставшихся ограничений. Недостатком этого метода является то, что не всегда можно расставить группу или курс и поэтому это приходится делать вручную.
Плюсы эвристических методов в том, что при всей своей произвольности и слабости могут быть с успехом применены для решения задач высокой вычислительной сложности (задачи, принадлежащие классу NP). Например, в методе ветвей и границ эвристические алгоритмы применяются как средство получения начальных решений и верхних оценок.
Минусы же эвристических методов в том, что они не гарантируют нахождение лучшего решения и они не гарантируют нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).
Выводы
Проанализировав алгоритмы автоматизации составления расписаний можно сделать следующие выводы:
• Существующие методы составления расписания можно разбить на две группы: полный перебор (точные методы) и методы сокращения полного перебора (приближенные методы).
• Выбор алгоритма непосредственно зависит от условий поставленной задачи. Для задачи расписания – это количество и вид ресурсов, заданий и ограничений.
Таким образом мы можем понять, что для успешной реализации идеи автоматического составления расписания с внедрением её в АСК «Деканат» Донецкого Национального Технического Университета перед началом работы необходимо точно узнать:
• учебный план;
• количество аудиторий;
• мягкие и жесткие ограничения.
Список использованной литературы.
1. Сипко Е.Н. Метод последовательного анализа вариантов решения задачи составления расписания занятий, 2011 г. [Электронный ресурс]. URL:http://archive.nbuv.gov.ua/portal/natural/ii/2011/AI_2011_1/2/00_Sipko.pdf<
2. Бартенев А.С. Обзор основных вопросов автоматизированного составления расписания занятий в высшем учебном заведении. // Современные научные исследования и инновации. – Сентябрь, 2011 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2011/09/2576
3. Каширина И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида. // Вестник ВГУ, Серия физика, математика, 2003, №1. [Электронный ресурс]. URL:http://www.vestnik.vsu.ru/pdf/physmath/2003/01/kashirina.pdf
4. Топорков В.В. Модели распределенных вычислений, М.: ФИЗМАТЛИТ, 2004. 218 стр.
5. Береговых Ю.В., Васильев Б.А., Володин Н.А. Алгоритм составления расписания занятий, Государственный университет информатики и искусственного интеллекта, г. Донецк, Украина. [Электронный ресурс]. URL: http://archive.nbuv.gov.ua/portal/natural/ii/2009_2/2%5C00_Beregovykh_Vasilev_Volodin.pdf
6. Лазарев А.А., Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации, Научная библиотека диссертаций и авторефератов disserCat http://www.dissercat.com/content/metody-i-algoritmy-resheniya-zadach-teorii-raspisanii-dlya-odnogo-i-neskolkikh-priborov-i-ik#ixzz2OqtZiCN6
7. Коффман Э.Г. Теория расписаний и вычислительные машины, М; Наука, 1984. 87-88 стр.
8. Танаев В.С., Шкуба В.В. Введение в теорию расписаний. – М.: Наука, 1975. 139 стр.