Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Низамова, Гузель Фанисовна

• Низамова, Гузель Фанисовна
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Низамова, Гузель Фанисовна

ВВЕДЕНИЕ.

ГЛАВА 1 АГРЕГАТИВНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ В ОБРАЗОВАТЕЛЬНЫХ СИСТЕМАХ МАССОВОГО ОБУЧЕНИЯ.

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

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

1.3 Описание структуры объектов и работы агрегативного генетического алгоритма составления расписания.

Выводы по первой главе.

ГЛАВА 2 ИНТЕЛЛЕКТУАЛЬНЫЕ АЛГОРИТМЫ ОПРЕДЕЛЕНИЯ

КОЭФФИЦИЕНТОВ ВАЖНОСТИ ЧАСТНЫХ КРИТЕРИЕВ.

ОПТИМАЛЬНОСТИ.

2.1 Предварительные замечания.

2.2 Экспертное ранжирование важности частных критериев оптимальности расписания в условиях высокой степени полноты информации экспертов (в условиях определенности).

2.3 Экспертное определение достоверности полученных весовых коэффициентов.

2.4 Экспертное ранжирование важности частных критериев оптимальности расписания в условиях неопределенности.

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

2.4.2 Применение метода вероятностного моделирования для коррекции коэффициентов важности критериев.

Выводы по второй главе.

ГЛАВА 3 ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА ЭФФЕКТИВНОСТИ ПРЕДЛАГАЕМЫХ АЛГОРИТМОВ СОСТАВЛЕНИЯ РАСПИСАНИЯ.

3.1 Функциональная модель интеллектуальной системы составления расписания.

3.2 Организация хранения информации при составлении расписания учебных занятий.

3.3 Описание структуры программных модулей программного комплекса "Феб".

3.4 Методика составления расписания учебных занятий с использованием программного комплекса "Феб".

3.5 Оценка эффективности составления расписания с помощью программного комплекса "Феб".

Выводы по третьей главе.

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов»

Актуальность работы

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

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

Расписание учебных занятий, по сути, представляет собой пространственно-временной график их проведения с "привязкой" к конкретным учебным группам и дисциплинам обучения. Это означает, что расписание задается подмножеством 8 декартова произведения пяти дискретных множеств: учебные группы (множество (7), преподаватели (множество Р), дисциплины обучения множество £)), время (учебные пары) проведения занятий (множество 7), аудитории (множествоА): /? = {СхРхОхГх/(}.

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

Решение задачи составления расписания заключается в определении упомянутого выше подмножества Б декартова произведения 7?.

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

• соответствие занятий рабочему учебному плану на рассматриваемый период;

• проведение занятий в заданные директивные сроки;

• отсутствие накладок разных типов (для студентов, преподавателей, аудиторий);

• проведение занятий в аудиториях, приспособленных для соответствующих видов занятий;

• непрерывность занятий у всех учебных групп в течение дня (отсутствие "окон");

• проведение в течение учебного дня количества пар, не превосходящих заданное;

• равномерность занятий;

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

• учет предложений преподавателей;

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

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

• наличие большого числа студенческих групп на каждом курсе обучения,

• наличие большого числа дисциплин обучения в течение семестра,

• наличие различных типов аудиторных занятий (лекционные, практические, лабораторные),

• наличие разных видов занятий с различной длительностью их проведения,

• большой контингент преподавателей,

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

• многосменный характер организации учебного процесса и т.д.

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

• наличие "окон" в расписаниях у преподавателей и групп студентов;

• неравномерность занятий в течение недели у учебных групп и преподавателей;

• сложность учета пожеланий преподавателей о характере временного графика их занятий;

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

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

Анализ существующих подходов к составлению расписания учебных занятий

Первые работы в области автоматизации составления расписания работ относятся к производственным системам и появились в 50-60-е гг. XX в. в связи с внедрением автоматизированных систем управления производством. Большое разнообразие задач, связанных с составлением расписания выполнения работ в производственных системах, сопровождающееся к тому же их большой размерностью, привело к созданию специальной теории решения задач составления расписаний (ЗСР), облегчающей формулировку и решение задач составления расписания работ для производственных систем. Данная теория дает универсальные решения самых различных производственных задач, связанных с календарным планированием, упорядочением работ во времени и пространстве и др. с учетом имеющихся ограничений на располагаемые ресурсы. Решение задач составления расписания в рамках данной теории в конечном итоге сводится к использованию математического аппарата целочисленного программирования [55, 101, 102, 103].

На рубеже XX и XXI веков актуальным стало создание систем автоматизированного управления учебным процессом в образовательных системах массового обучения (автоматизированных обучающих систем АОС) [67]. Связано это с усилением требований к качеству обучения, появлением разнообразных форм обучения, развитием форм дистанционного обучения, необходимостью повышения экономической эффективности обучения и др.

Первые работы в области автоматизации решения ЗСР для образовательных систем базировались на адаптации или модификации созданной в 50-60 гг. XX в. классической теории решения ЗСР применительно к решению задач составления расписания учебных занятий. Данный подход предусматривает формулировку задачи составления расписания занятий в терминах теории расписаний (выделение приборов и требований) с последующим решением ее одним из известных методов целочисленного программирования. В наиболее общей формулировке задача составления расписания в терминах теории расписания состоит в следующем. С помощью некоторого множества ресурсов или приборов должна быть выполнена некоторая фиксированная система требований (заданий). Цель заключается в том, чтобы при заданных свойствах требований и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующих или стремящийся оптимизировать требуемую меру эффективности. В известных работах, реализующих данный подход [101, 103], при формулировке задачи составления расписания учебных занятий в качестве приборов выступают аудитории, в качестве требований -учебные группы.

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

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

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

Все известные работы в этом направлении, посвященные автоматизации процедуры составления расписания занятий [5, 14, 16, 42, 52, 57, 58, 67, 70, 98, 108], можно условно разделить на две группы: к первой группе относятся работы, использующие классические методы решения задач целочисленного программирования: методы полного перебора, ветвей и границ, перебора в глубину, метод Гомори, метод раскраски графа и др. Вторая группа работ основана на современных методах решения задач целочисленного программирования, использующих интеллектуальные алгоритмы решения данных задач.

Классические методы решения задачи составления расписания занятий

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

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

Применение перечисленных методов для составления расписания занятий в образовательных системах массового обучения [5, 16, 67, 98] оказывается неэффективным по следующим причинам: а) резко (экспоненциально) увеличиваются временные затраты на поиск лучшего (приемлемого) решения с ростом размерности решаемой задачи, что характерно для образовательных систем массового обучения; б) отсутствует гарантия получения приемлемого решения ЗСР занятий; в) практически невозможным становится (в силу большой размерности, громоздкости и сложности математической модели решаемой задачи) оценивание влияния на решение задачи интересующих нас факторов, оценивание критичности полученного решения к данным факторам.

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

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

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

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

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

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

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

Интеллектуальные методы решения задачи составления расписания

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

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

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

Другой подход к решению сложных комбинаторных задач целочисленного программирования, к классу которых относится и задача составления расписания учебных занятий, описывается в работе [29]. В рамках данного подхода решение оптимизационной задачи осуществляется с помощью нейронных сетей (НС), где каждой целочисленной переменной х-у решаемой задачи ставится в соответствие выходной сигнал {¡-го нейрона У^, стоящего в /-й строке и у'-м столбце матрицы, т.е. строится отображение. Далее с учетом полученного отображения интерпретируются ограничения и целевая функция и строится энергетическая функция НС.

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

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

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

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

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

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

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

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

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

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

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

Для применения генетических операторов значения этих параметров должны быть представлены в виде двоичной последовательности, т.е. двоичной строки, состоящей из нескольких бит. Количество бит при кодировании гена (хромосомы) зависит от требуемой точности решаемой задачи. Оптимальным считается такой выбор, когда выполняется соотношение п> 1оё9ГХтах~Хт!п), А где хтах и хП1ц1 - максимальное и минимальное значения аргумента хцелевой функции;

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

Количество особей М в популящ I! г определяется, как правило, эмпирическим путем, из интервала п<М<2п.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В работе [42] предлагается генетический алгоритм, где особь состоит из одной хромосомы, которая представляет собой вариант расписания учебных занятий. В качестве модели хромосомы рассматривается трехмерная матрица инциденций, по осям /, /, к которой откладываются соответственно учебные группы, пары и аудитории. Элементы 1(1,},к) многомерной матрицы равны либо О, либо 1:

1, если во время ¡'-й пары в к-й ауд проводится занятие в 1-й группе [О, если во время / -й пары в к-й ауд не проводится занятие в 1-й группе

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

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

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

Таким образом, на основе данного анализа можно сделать вывод о перспективности и актуальности совершенствования генетических алгоритмов решения ЗСУР применительно к составлению расписания учебных занятий в образовательных системах массового обучения.

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

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

Цель диссертационной работы

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

Задачи исследования

Для достижения цели в работе необходимо решить следующие задачи:

1. Разработать структурную модель представления исходной информации для составления расписания;

2. Разработать агрегативный генетический алгоритм составления расписания учебных занятий;

3. Разработать интеллектуальный алгоритм определения коэффициентов относительной важности частных критериев оптимальности расписания в условиях неопределенности;

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

5. Провести экспериментальную проверку эффективности предложенного генетического алгоритма.

Методы исследования

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

Результаты, выносимые на защиту

На защиту выносятся следующие результаты исследований:

1. Структурные модели представления исходной информации для составления расписания;

2. Агрегативный алгоритм генетической оптимизации;

3. Интеллектуальный алгоритм определения коэффициентов важности частных критериев оптимальности расписания в условиях неопределенности.

Научная новизна работы

Научная новизна данной работы заключается в следующем:

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

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

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

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

Практическая значимость

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

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

2. Результаты экспериментальной проверки предложенных алгоритмов (на примере факультета ИРТ) показали существенное (в 2-3 раза) уменьшение скорости роста временных затрат по мере увеличения сложности задачи составления расписания (увеличения числа блоков занятий) по сравнению с обычными генетическими алгоритмами.

Основания для выполнения работы

Работа выполнена на кафедре информатики Уфимского государственного авиационного технического университета (УГАТУ) в рамках госбюджетных работ, проводимых на кафедре Информатики УГАТУ, а также в рамках реализации внутривузовской Программы поэтапного внедрения на кафедре информатики технологий автоматизированного и дистанционного обучения.

Апробация работы

Основные результаты, представленные в диссертационной работе докладывались и обсуждались на: 8-й международной научно-методической конференции вузов и факультетов телекоммуникаций "Проблемы техники и технических телекоммуникаций" (Уфа, 2004), 5-й Международной научно- технической конференции "Проблемы техники и технических телекоммуникаций" (Самара, 2004), 7-й международной конференции "Информатика и Информационные технологии" С8ГГ2005 (г. Уфа, 2005), Зимней школе аспирантов и молодых ученых (Уфа, 2006).

Публикации

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

Благодарности

Автор выражает глубокую благодарность за полезные консультации к. физ.-мат. н., доценту Шехтман Л. И. и Ковтуненко А. С. за помощь при проведении экспериментальных исследований.

Объем и структура работы

Диссертационная работа состоит из введения, трех глав, заключения, библиографии и двух приложений. Работа содержит 122 страницы текста и 111 наименований библиографических источников.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Низамова, Гузель Фанисовна

Выводы по третьей главе

1. В соответствие со стандартом IDEF0 разработана функциональная модель интеллектуальной системы составления расписания.

2. В соответствие со стандартом IDEF1 разработана информационная модель типа «сущность-связь» хранения исходной и результирующей информации для организации процедуры составления расписания. В соответствие с данной моделью разработана база данных с использованием СУБД MS Access.

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

4. Проведен эксперимент по составлению расписания учебных занятий для факультета ИРТ УГАТУ. Оценены возможные затраты времени на составление расписания всего ВУЗа. Составление расписания для одного факультета, как показал эксперимент, будет составлять около 7 часов. Первичное заполнение базы данных (для Вуза) происходит в течение недели. Эксперимент показал эффективность предлагаемого алгоритма и несомненную эффективность его использования ВУЗами для составления учебных расписаний.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

6. Разработано программное обеспечение, реализующее предлагаемые алгоритмы составления расписания. Отличительной особенностью его является существенная экономия оперативной памяти и времени процессора при организации цикличной процедуры генетической оптимизации. Программное обеспечение внедрено в УГАТУ и используется в учебном процессе при проведении занятий по дисциплинам "Методы оптимизации", "Системы искусственного интеллекта", "Исследование операций".

7. Проведен эксперимент по составлению расписания учебных занятий для факультета ИРТ УГАТУ. Оценены возможные затраты времени на составление расписания всего ВУЗа. Время составление расписания для факультета ИРТ, как показал эксперимент, будет составлять около 7 часов. Первичное заполнение базы данных (для ВУЗа) происходит в течение недели. Эксперимент показал эффективность предлагаемого алгоритма и несомненную эффективность его использования ВУЗами для составления учебных расписаний.

Список литературы диссертационного исследования кандидат технических наук Низамова, Гузель Фанисовна, 2006 год

1. Blickle Т., Thiele L. A Comparison of Selection Schemes used in Genetic Algorithms. TIK-Report 11/12/95

2. CASE-технологии. Консалтинг при автоматизации бизнес-процессов. 2-е изд. перераб. и доп. М.: Горячая линия, Телеком, 2000. - 320 с.

3. Cogger К.О., Yu P. L. Eigenweight vector and least-distance approximation // J. Optimiz. Theory and Appl, 1985, V. 46, №4, p.483-491.

4. Davis. L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991.

5. E.K. Burke, D.G. Elliman, R.F. Weare. A University Timetabling System Based on Graph Coloring and Constraint Manipulation, Journal of Research on Computing in Education, 1993.

6. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

7. R. Poli. "Introduction to Evolutionary Computation". Lectures notes. School of Computer Science, The University of Birmingham, 1996.Ш

8. Saaty Thomas L Eigenweinghtor an logarithmic lease sguares // Eur. J. Oper. res, 1990, V. 48, № l,p. 156-160.

9. Автоматизированное проектирование информационно-управляющих систем. Системное моделирование предметной области/ Куликов Г.Г., Набатов А.Н., Речкалов А.В. Уфа: УГАТУ, 1998. - 104 с.

10. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные системы: Учебник. М.: Финансы и статистика, 2004. - 424 с.

11. Анохин A.M., Глотов В.А., Павельев В.В., Черкашин A.M. Методы определения коэффициентов важности критериев "Автоматика и телемеханика", №8, 1997, с 3-35.

12. Аттетков А. В. Методы оптимизации: учебник для втузов / Под ред. В. С. Зарубина, А. П. Крищенко.- Изд. 2-е, М.: МГТУ им. Н.Э. Баумана, 2003. - 440 с.

13. Баева Н.Б., Бондаренко Ю.В. Методы экстраполяции выявленных предпочтений. Вестник ВГУ, Серия физика, математика, 2002, № 1

14. Безгинов А.Н., Трегубов С.Ю. Обзор существующих методов составления расписания// Информационные технологии и программирование: межвузовский сборник статей. Выпуск 2(14). -М.: МГИУ, 2005.

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

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

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

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

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

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

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

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

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

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

25. Воронов A.A. Исследование операций и управление. М.: Наука, 1970. -128 с.

26. Галушкин А.И. Нейроинформатика. М.: Энергия, 2002. - 448 с.

27. Гареев А.Ф. Базы данных. Интеллектуальная обработка информации / В.В. Корнеев, А.Ф. Гареев, C.B. Васютин, В.В. Райх. М.: Нолидж, 2000. -352с.

28. Гафт М.Г. Принятие решений при многих критериях. М.: Знание, 1979.

29. Глотов В.А., Павельев В.В. Векторная стратификация. М.: Наука, 1985.33