Содержание к диссертации
Введение
ГЛАВА 1 Агрегати в ный генетический алгоритм составления расписания учебных занятий в образовательных системах массового обучения 25
1.1 Структуризация исходной информации для составления расписания - учебных занятий 25
1.2 Постановка задачи составления расписания учебных занятий на основе структурированных моделей исходной информации 35
1.3 Описание структуры объектов и работы агрегативного генетического алгоритма составления расписания 43
Выводы по первой главе 51
ГЛАВА 2 Интеллектуальные алгоритмы определения коэффициентов важности частных критериев оптимальности 53
2.1 Предварительные замечания 53
2.2 Экспертное ранжирование важности частных критериев оптимальности расписания в условиях высокой степени полноты информации экспертов (в условиях определенности) 54
2.3 Экспертное определение достоверности полученных весовых коэффициентов 60
2.4 Экспертное ранжирование важности частных критериев оптимальности расписания в условиях неопределенности 64
2.4.1 Применение аппарата нечеткой логики для организации процедуры , коррекции весовых коэффициентов 67
2.4.2 Применение метода вероятностного моделирования для коррекции коэффициентов важности критериев 73
Выводы по второй главе 77
ГЛАВА З Экспериментальная проверка эффективности предлагаемых алгоритмов составления расписания 78
3.1 Функциональная модель интеллектуальной системы составления расписания 78
3.2 Организация хранения информации при составлении расписания учебных занятий 82
3.3 Описание структуры программных модулей программного комплекса "Феб" 86
3.4 Методика составления расписания учебных занятий с использованием программного комплекса "Феб" 99
3.5 Оценка эффективности составления расписания с помощью программного комплекса "Феб" 106
Выводы по третьей главе 109
Заключение
Список литературы
- Постановка задачи составления расписания учебных занятий на основе структурированных моделей исходной информации
- Экспертное ранжирование важности частных критериев оптимальности расписания в условиях высокой степени полноты информации экспертов (в условиях определенности)
- Применение аппарата нечеткой логики для организации процедуры , коррекции весовых коэффициентов
- Описание структуры программных модулей программного комплекса "Феб"
Введение к работе
Актуальность работы
Составление расписания учебных занятий является одной из важнейших задач управления учебным процессом. В связи с этим проблема автоматизации составления расписания занятий в образовательных системах массового обучения по-прежнему остается одной из актуальных проблем организации учебного процесса. Действительно, от того насколько "удачно" составлено расписание зависит:
а) качество обучения;
б) экономическая эффективность обучения;
в) комфортность учебы студентов и работы профессорско-
преподавательского состава (учет требуемых психофизиологических аспектов
обучения) и т.д.
Автоматизация процедуры составления учебных занятий позволяет:
а) учесть множество требований и условий, предъявляемых к расписа
нию;
б) строго формализовать процедуру получения лучшего, в определенном
смысле, расписания;
в) реализовать критериальный или оптимизационный подход к составле
нию расписания;
г) существенно уменьшить временные затраты на составление расписа
ния.
Расписание учебных занятий, по сути, представляет собой пространственно-временной график их проведения с "привязкой" к конкретным учебным группам и дисциплинам обучения. Это означает, что расписание задается подмножеством S декартова произведения пяти дискретных множеств: учебные группы (множество С), преподаватели (множество Р), дисциплины обучения
5 (множество D), время (учебные пары) проведения занятий (множество 7), аудитории (множество A): R = {G х Р х D х Г х а),
Тогда задачу составления расписания на качественном уровне можно сформулировать так: для каждой учебной группы нужно составить график проведения занятий в течение семестра, в котором указывается аудитория и время проведения занятий по каждой изучаемой дисциплине. В качестве исходной информации для формирования расписания выступают:
а) учебные планы специальностей обучения;
б) перечень учебных групп различных специальностей обучения конкрет
ного вуза на текущий семестр;
в) нагрузка преподавателей (проводимые конкретным преподавателем за
нятия, их виды и количество в семестре);
г) располагаемый для проведения занятий аудиторный фонд с учетом его
динамики.
Решение задачи составления расписания заключается в определении упомянутого выше подмножества S декартова произведения R.
Расписание занятий должно в определенной мере удовлетворять ряду критериев и ограничений (зачастую противоречащих друг другу), отражающих методические, дидактические, экономические и психофизические требования:
соответствие занятий рабочему учебному плану на рассматриваемый период;
проведение занятий в заданные директивные сроки;
отсутствие накладок разных типов (для студентов, преподавателей, аудиторий);
проведение занятий в аудиториях, приспособленных для соответствующих видов занятий;
непрерывность занятий у всех учебных групп в течение дня (отсутствие "окон");
проведение в течение учебного дня количества пар, не превосходящих заданное;
равномерность занятий;
наиболее сложные формы занятий (например, лекции) рекомендуется проводить во время, способствующее наиболее качественному усвоению знаний;
учет предложений преподавателей;
учет специальных требований, связанные со спецификой вуза и обеспечением комфортности обучения студентов и работы ППС (например, уменьшение количества переходов из одного учебного корпуса в другой).
Составление расписания для небольших учебных заведений с малым числом учебных групп и изучаемых дисциплин не представляет особых затруднений. Совсем иначе обстоит дело с составлением расписания занятий в образовательных системах массового обучения, для которых характерно:
наличие большого числа студенческих групп на каждом курсе обучения,
наличие большого числа дисциплин обучения в течение семестра,
наличие различных типов аудиторных занятий (лекционные, практические, лабораторные),
наличие разных видов занятий с различной длительностью их проведения,
большой контингент преподавателей,
большой аудиторный фонд, включающий в себя различные по площади, по назначению и динамике аудитории,
многосменный характер организации учебного процесса и т.д.
Для подобных образовательных систем, реализующих массовое обучение, составление расписания "вручную" приводит к большой длительности самого
7 процесса его составления и "низкому" качеству составленного расписания, а именно:
наличие "окон" в расписаниях у преподавателей и групп студентов;
неравномерность занятий в течение недели у учебных групп и преподавателей;
сложность учета пожеланий преподавателей о характере временного графика их занятий;
большие затраты времени на переход из одного учебного корпуса в другой в случае некомпактного расположения корпусов вуза и др.
Выходом из создавшегося положения является автоматизация процедуры составления расписания [67], основанная на формализации данной процедуры с помощью известных методов теории исследования операций и последующей реализации процедуры составления расписания на ЭВМ.
Анализ существующих подходов к составлению расписания учебных занятий
Первые работы в области автоматизации составления расписания работ относятся к производственным системам и появились в 50-60-е гг. XX в. в связи с внедрением автоматизированных систем управления производством. Большое разнообразие задач, связанных с составлением расписания выполнения работ в производственных системах, сопровождающееся к тому же их большой размерностью, привело к созданию специальной теории решения задач составления расписаний (ЗСР), облегчающей формулировку и решение задач составления расписания работ для производственных систем. Данная теория дает универсальные решения самых различных производственных задач, связанных с календарным планированием, упорядочением работ во времени и пространстве и др. с учетом имеющихся ограничений на располагаемые ресурсы. Решение задач составления расписания в рамках данной теории в конечном итоге сво-
8 дится к использованию математического аппарата целочисленного программирования [55, 101, 102, 103].
На рубеже XX и XXI веков актуальным стало создание систем автоматизированного управления учебным процессом в образовательных системах массового обучения (автоматизированных обучающих систем АОС) [67]. Связано это с усилением требований к качеству обучения, появлением разнообразных форм обучения, развитием форм дистанционного обучения, необходимостью повышения экономической эффективности обучения и др.
Первые работы в области автоматизации решения ЗСР для образовательных систем базировались на адаптации или модификации созданной в 50-60 гг. XX в. классической теории решения ЗСР применительно к решению задач составления расписания учебных занятий. Данный подход предусматривает формулировку задачи составления расписания занятий в терминах теории расписаний (выделение приборов и требований) с последующим решением ее одним из известных методов целочисленного программирования. В наиболее общей формулировке задача составления расписания в терминах теории расписания состоит в следующем. С помощью некоторого множества ресурсов или приборов должна быть выполнена некоторая фиксированная система требований (заданий). Цель заключается в том, чтобы при заданных свойствах требований и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующих или стремящийся оптимизировать требуемую меру эффективности. В известных работах, реализующих данный подход [101, 103], при формулировке задачи составления расписания учебных занятий в качестве приборов выступают аудитории, в качестве требований -учебные группы.
Необходимо отметить, что подобная формулировка и решение задачи составления расписания занятий с помощью аппарата классической теории расписаний связана с рядом сложностей и требует модификации (в том числе и терминологической) традиционной постановки ЗСР. Это выражается в необхо-
9 димости учета специфических особенностей организации процесса обучения в образовательных системах. Так, в работе [100] предлагается для решения задачи составления расписания учебных занятий использовать теоретический аппарат составления "производственных" расписаний. Это приводит к необходимости введения новых, зачастую искусственных понятий, таких как "многофункциональные приборы" и "комплексные требования", при этом в качестве приборов рассматриваются аудитории, а в качестве требований - занятия (в отличие от традиционного - учебные группы).
Необходимость такой модификации обусловлена спецификой образовательных систем: например, существуют такие виды занятий, которые проводятся одновременно для нескольких учебных групп (поточные лекции), а в рамках теории расписаний один прибор в некоторый момент времени не может обслуживать более одного требования.
Область эффективного применения известных методов составления "производственных" расписаний для составления расписания учебных занятий ограничена малыми образовательными системами с малым числом ограничений, накладываемым на расписание. Все это привело к появлению нового направления решения ЗСР учебных занятий, основанного на непосредственном использовании методов целочисленного программирования без привлечения методов традиционной теории составления "производственных" расписаний.
Все известные работы в этом направлении, посвященные автоматизации процедуры составления расписания занятий [5, 14, 16, 42, 52, 57, 58, 67, 70, 98, 108], можно условно разделить на две группы: к первой группе относятся работы, использующие классические методы решения задач целочисленного программирования: методы полного перебора, ветвей и границ, перебора в глубину, метод Гомори, метод раскраски графа и др. Вторая группа работ основана на современных методах решения задач целочисленного программирования, использующих интеллектуальные алгоритмы решения данных задач.
10 Классические методы решения задачи составления расписания занятий
Отличительной чертой классических методов является достаточно высокая степень формализации (математическая строгость) как постановки задачи составления расписания занятий, так и алгоритмов ее решения (используются "жесткие" алгоритмы). Данные методы позволяют:
а) разрабатывать итеративные методы решения задачи составления рас
писаний учебных занятий, обладающие приемлемым временем сходимости и
точностью решения;
б) оценивать влияние на время и точность решения задачи составления
расписаний учебных занятий интересующих нас факторов.
Следует отметить, что применение классических методов решения задачи составления расписаний учебных занятий хотя и не требует адаптации терминологии, модификации математического аппарата как это имеет место при использовании аппарата теории "производственных" расписаний, однако из-за их неэффективности область их применения ограничена лишь небольшими образовательными системами с малым числом учебных групп, дисциплин обучения и т.п.
Применение перечисленных методов для составления расписания занятий в образовательных системах массового обучения [5, 16, 67, 98] оказывается неэффективным по следующим причинам:
а) резко (экспоненциально) увеличиваются временные затраты на поиск
лучшего (приемлемого) решения с ростом размерности решаемой задачи, что
характерно для образовательных систем массового обучения;
б) отсутствует гарантия получения приемлемого решения ЗСР занятий;
в) практически невозможным становится (в силу большой размерности,
громоздкости и сложности математической модели решаемой задачи) оценива
ние влияния на решение задачи интересующих нас факторов, оценивание кри
тичности полученного решения к данным факторам.
Среди методов, используемых при составлении ЗСР занятий, можно также выделить методы, основанные на использовании математического аппарата теории графов. При использовании данных методов задача составления расписания занятий сводится к задаче раскраски графа [5].
В этом случае строится граф, в котором каждая вершина представляет собой запланированное учебным планом занятие. Если между какими-то двумя вершинами возможны конфликты (появляются накладки), например, два занятия проводятся в одной аудитории, то они соединяются ребром. Это эквивалентно запрету одновременного проведения этих занятий. Тогда задачу составления расписания можно сформулировать как задачу минимизации числа цветов, необходимых для раскраски графа, где каждый цвет соответствует одному периоду расписания.
Применение данного метода при решении реальных задач составления расписания для образовательных систем массового обучения малоэффективно, но сочетание данного подхода с другими методами может оказаться полезным [16].
Общим недостатком всех классических методов является то, что они в своей основе используют итерационную процедуру поиска или улучшения некоторого начального приближения (опорного плана расписания), причем поиск результата осуществляется в окрестностях этого приближения. Это означает, что полученный результат напрямую зависит от некоторого начального приближения и естественно возникает проблема выбора ее значения.
Кроме того, организация поиска экстремума целевой функции в классических методах происходит:
во-первых, на основе изучения ее свойств в "малом" (в малой окрестности от начального приближения), можно сказать почти "в слепую",
во-вторых - только в одном направлении, определяемом направлением желаемого изменения целевой функции в малой окрестности ее наблюдения.
Все это приводит к необходимости множественного эксперимента с разными значениями начального приближения, что существенно увеличивает время поиска окончательного решения.
Низкая эффективность использования классических методов при решении задачи составления расписания занятий, вызвала необходимость в разработке и привлечении для решения задачи составления расписания учебных занятий новых методов решения оптимизационных задач целочисленного программирования.
Интеллектуальные методы решения задачи составления расписания
В основе данных методов, как правило, лежит использование различного рода эвристик или эвристических алгоритмов, при разработке которых используются интуитивные предположения, не подкрепленные соответствующим математическим обоснованием. Формирование расписания занятий с помощью некоторых правил (эвристик) [58, 70] позволяет несколько ускорить поиск "наилучшего" расписания, но использование таких алгоритмов в большинстве случаев гарантирует лишь нахождение приближенного решения (достижение локального экстремума). В этом случае возникает проблема оценки близости найденного локального экстремума к глобальному экстремуму.
В ряде работ эта проблема решается путем сравнения расписания, полученного эвристическим методом и расписания, полученного методом перебора для близкой задачи малой размерности. Несмотря на указанный недостаток, эвристические алгоритмы продолжают оставаться достаточно эффективным инструментом поиска "лучшего" в некотором смысле решения в тех случаях, когда нахождение наилучшего решения крайне затруднено или невозможно.
В работе [108] при автоматизации составления расписания занятий в образовательных системах массового обучения предлагается использовать математический аппарат нечеткой логики для перехода от "жестких" ограничений к более "мягким" требованиям. Однако, несмотря на то, что данный подход позволяет значительно упростить формализацию требований, предъявляемых к
13 расписанию, рассмотрение наиболее важных требований в качестве "мягких" требований может привести к "плохому" расписанию (появлению "окон", "накладок").
Другой подход к решению сложных комбинаторных задач целочисленного программирования, к классу которых относится и задача составления расписания учебных занятий, описывается в работе [29]. В рамках данного подхода решение оптимизационной задачи осуществляется с помощью нейронных сетей (НС), где каждой целочисленной переменной хц решаемой задачи ставится в
соответствие выходной сигнал //-го нейрона 1^,-, стоящего в /-й строке и/-м
столбце матрицы, т.е. строится отображение. Далее с учетом полученного отображения интерпретируются ограничения и целевая функция и строится энергетическая функция НС.
На следующем этапе определяются параметры НС: матрица синаптиче-ских связей и вектор внешних смещений. В конечном итоге, поиск решения задачи с помощью данного метода сводится к реализации динамического процесса перехода НС из некоторого начального состояния в некоторое конечное состояние, которое и принимается за решение задачи.
Недостатком данного метода является сложность выбора некоторого начального состояния НС. Поэтому при наличии достаточного временного ресурса на поиск решения следует реализовывать многократный переходный процесс сети и в качестве решения принимать наилучший из результатов.
Другим, интенсивно развиваемым в последнее время методом решения болынеразмерных задач целочисленного программирования, является целый класс методов, объединенных термином "генетические алгоритмы". Основные отличия и преимущества генетических алгоритмов в сравнении с классическими методами заключаются в следующем:
генетические алгоритмы работают с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции;
в процессе поиска генетический алгоритм использует несколько точек поискового пространства (процесс распараллеливается), а не переходит от точки к точке, как это происходит в традиционных методах. Т.е. генетические алгоритмы оперируют со всей совокупностью допустимых решений;
генетические алгоритмы в процессе работы не используют никакой дополнительной информации, что повышает скорость его работы;
генетический алгоритм использует как вероятностные правила для порождения новых точек поиска, так и детерминированные правила для перехода от одних точек к другим и др.
Основными объектами генетических алгоритмов являются: особь (индивидуум), хромосома, ген, генотип, фенотип, функция пригодности. Основными операциями или, как это принято в теории генетических алгоритмов, операторами, выполняемыми над объектами, являются: селекция, скрещивание и мутация. Особь включает в себя одну или несколько хромосом, каждая хромосома в свою очередь состоит из одного или нескольких генов.
В качестве логической модели особи выступает кортеж кодов хромосом. Генотипом особи принято считать упорядоченный набор генов некоторой особи, фенотипом особи - набор значений (признаков) этих генов. Допустима такая аналогия, генотип - упорядоченная совокупность варьируемых переменных, фенотип - упорядоченная совокупность значений этих переменных. В качестве функции пригодности выступает целевая функция оптимизационной задачи целочисленного программирования.
Решение оптимизационной задачи целочисленного программирования с использованием генетических алгоритмов происходит следующим образом.
На первом шаге алгоритма формируется исходная популяция особей, где каждая особь популяции представляет собой решение задачи, иначе говоря, является кандидатом на решение. Формирование исходной популяции, как правило, происходит с использованием какого-нибудь случайного закона, в ряде слу-
I 5 чаев исходная популяция может быть также результатом работы другого алгоритма. Необходимо отметить, что особи популяции могут состоять как из одной, так и из нескольких хромосом. Каждая хромосома особи в свою очередь состоит из генов, причем количество гонов в хромосоме определяется количеством варьируемых параметров решаемой задачи (аргументов целевой функции).
Для применения генетических операторов значения этих параметров должны быть представлены в виде двоичной последовательности, т.е. двоичной строки, состоящей из нескольких бит. Количество бит при кодировании гена (хромосомы) зависит от требуемой точности решаемой задачи. Оптимальным считается такой выбор, когда выполняется соотношение
где х1ШХ и хт[п - максимальное и минимальное значения аргумента хцелевой
функции;
А - погрешность решения задачи;
п - количество бит, используемых для кодирования значения аргумента.
Количество особей М в популяці 111 определяется, как правило, эмпирическим путем, из интервала п < М < 2п.
На втором шаге работы генетического алгоритма происходит отбор или селекция наиболее приспособленных особей, имеющих наиболее предпочтительные значения функции пригодности по сравнению с остальными особями. После чего к отобранным особям применяются операторы скрещивания и мутации.
В классическом генетическом алгоритме отбор наиболее приспособленных особей осуществляется случайным образом с помощью различных методов генерации дискретных случайных величин, имеющих различные законы распределения. Среди данных методов следует упомянуть отбор методом "колеса рулетки, пропорциональный отбор, отбор с вытеснением, равновероятный от-
If) бор и т.д. Каждый из перечисленных методов имеет как свои достоинства, так и недостатки, например, общим недостатком указанных методов является то, что при их использовании в некотором поколении наилучшие особи популяции могут быть потеряны. Одним из способов преодоления этого недостатка является использование элитного отбора, который предусматривает сохранение "наилучшей" особи в популяции ("лучшая'" особь всегда переходит в следующее поколение).
На третьем этапе реализуется операция скрещивания особей. Смысл данной процедуры сводится к нахождению новых комбинаций генетического кода хромосом путем обмена случайным образом участков генетического кода у двух особей, прошедших отбор. Это способствует "получению" дополнительного числа новых особей, среди которых могут оказаться как более приспособленные, так и менее приспособленные особи. Это явление объясняется тем, что точка скрещивания (локус) выбирается случайным образом.
На четвертом этапе к особям популяции, полученным в результате скрещивания, применяется операция мутации. С помощью данной операции можно получать принципиально новые генотипы и фенотипы особи, что приводит к еще большему разнообразию особей в рассматриваемой популяции. Суть этого оператора заключается в следующем: в популяции случайным образом выбирается особь и так же случайно выбирается позиция гена, в которой значение изменяется на противоположное (0-)-1 или 1->0). Внесение таких случайных изменений позволяет существенно расширить пространство поиска приемлемых решений задачи целочисленной оптимизации.
В процессе работы алгоритма все указанные операторы применяются многократно и ведут к постепенному изменению исходной популяции в направлении улучшения значения функции пригодности.
В качестве критериев останова работы генетического алгоритма принято рассматривать критерии или условия, аналогичные тем, которые используются
17 при пошаговой оптимизации функции многих переменных с помощью градиентных методов:
условия, непосредственно свидетельствующие о достижении приемлемых значений целевой функции,
условия, непосредственно свидетельствующие о достижении заданных малых значений приращений значения целевой функции,
условия, косвенно свидетельствующие о достижении приемлемых
Ш значений целевой функции путем указания временного интервала, в
котором возможно появление значений, при которых целевая функция достигает приемлемых значений. Применительно к решению оптимизационных задач с помощью генетических алгоритмов данные условия можно записать следующим образом:
сформировано заданное число поколений,
популяция достигла заданного уровня качества (например, 80% особей имеют одинаковую генетическую структуру или одинаковое значение функции пригодности),
достигнут некоторый уровень сходимости, при котором улучшение популяции не происходит.
В настоящее время сфера применения генетических алгоритмов обширна, они успешно применяются при решении самых различных оптимизационных задач (задача оптимизации портфеля акций, задачи раскроя-упаковки, задача планирования выполнения работ). Предпринимаются попытки использования генетических алгоритмов и при составлении расписания учебных занятий [42, 52].
Однако при этом имеют место существенные трудности, которые можно
# рассматривать в качестве недостатков применения данных генетических алго-
ритмов к решению задачи составления расписания учебных занятий. Данные недостатки можно условно разбить на четыре группы.
К первой группе относятся недостатки, сходные с недостатками генетических алгоритмов и имеющие место при решении общих задач целочисленной оптимизации [48]. Так, недостаточное разнообразие хромосом в популяции может привести к преждевременному окончанию работы алгоритма и, как следствие, к получению "некорректного" расписания. Далее, завершение работы генетического алгоритма происходит по достижению заданного (не всегда обоснованного) числа итераций, что в ряде случаев препятствует поиску лучшего расписания.
Вторая группа недостатков вызвана слабым учетом специфики задачи составления расписания учебных занятии при организации ее решения с помощью генетических алгоритмов [42]. Так, в известных генетических алгоритмах составления расписания занятий не учитывается наличие связей между объектами расписания и большое многообразие описаний самих объектов расписания.
Третья группа вызвана недостаточной систематизацией исходных данных как на этапе представления объектов генетической оптимизации, так и при организации генетических операций поиска [52]. Так, расписание учебных занятий образовательных систем массового обучения является сложным информационным объектом, в котором сочетаются свойства учебных групп, дисциплин, преподавателей, аудиторий и т.д. Соответственно, хромосомы, являющиеся информационными моделями расписания, также являются сложными объектами, для которых целесообразно применение агрегативных логических моделей, основанных на рассмотрении хромосомы как многоуровневой системы с последующей ее декомпозицией.
В подтверждение этого тезиса, приведем анализ некоторых, наиболее интересных, на наш взгляд, работ, где рассматриваются подходы по применению генетических алгоритмов для решения задачи составления расписания учебных занятий.
19 В работе [42] предлагается генетический алгоритм, где особь состоит из одной хромосомы, которая представляет собой вариант расписания учебных занятий. В качестве модели хромосомы рассматривается трехмерная матрица инциденций, по осям i, j, к которой откладываются соответственно учебные группы, пары и аудитории. Элементы i(i,j,k) многомерной матрицы равны либо О, либо 1:
1, если во время j-й пары в к-й ауд проводится занятие в і-и группе
z = \
[О, если во время j-й пары в к-й ауд не проводится занятие в 1-й группе Такое представление (многомерная логическая модель) расписания учебных занятий облегчает лишь визуализацию, хранение исходной и промежуточной информации в процессе составления расписания. При этом сохраняются все основные присущие генетическим алгоритмам недостатки.
Отметим, что сама по себе идея использования многомерных информационных технологий для реализации решения задачи составления расписания является весьма конструктивной. Однако она требует не только разработки логических моделей представления расгшспния как информационного объекта, но и разработки соответствующих операці і її. по обработке данных информационных объектов, аналогичных операциям реляционной алгебры.
В работе [52] задача составления расписания учебных занятий сводится к задаче о назначениях с квадратичном целевой функцией, которая также решается с помощью генетических алгоритмов целочисленного программирования. Особенностью данного подхода является то, что в качестве логических моделей хромосом рассматриваются двухмерные матрицы, кроме того, используются вспомогательные двухмерные матрицы для записи основных ограничений при составлении расписания. Отметим, что у всех этих матриц элементы могут принимать значения либо 1, либо 0. Использование подобного способа представления исходной информации для решения задачи составления расписания, безусловно, является весьма удобным, однако это не оказывает существенного
20 влияния на улучшение эффективности процедуры решения рассматриваемой задачи с помощью генетических алгоритмов.
Таким образом, на основе данного анализа можно сделать вывод о перспективности и актуальности совершенствования генетических алгоритмов решения ЗСУР применительно к составлению расписания учебных занятий в образовательных системах массового обучения.
На наш взгляд, одним из направлений совершенствования генетических алгоритмов составления расписания является использование идей системного подхода, как на этапе структуризации исходной информации, так и при описании объектов генетических алгоритмов с соответствующей адаптацией к такому описанию генетических оператором.
В настоящей диссертационной работе предлагаются генетические алгоритмы составления расписаний для образовательных систем массового обучения, особенностью которых является наличие в них определенной структуры, элементами которой являются хромосомы и связи между ними. Такие алгоритмы были названы нами агрегативпыми генетическими алгоритмами. Предложенные в диссертации алгоритмы относятся к классу нетрадиционных (интеллектуальных) методов решения задам целочисленного программирования, содержат оригинальные приемы декомпозиции и агрегирования исходной информации (хромосом) и позволяют получить расписание, лучшее с точки зрения частных критериев эффективности расписания в условиях различной степени полноты информации о важности этих частных критериев.
Цель диссертационной работы
Целью диссертационной работы является разработка математического и программного обеспечения для решения задачи составления расписания учебных занятий на основе агрегативных. алгоритмов, обеспечивающих повышение эффективности процесса составления расписания в условиях различной степени полноты информации.
21 Задачи исследования
Для достижения цели в работе необходимо решить следующие задачи:
Разработать структурную модель представления исходной информации для составления расписания;
Разработать агрегативный генетический алгоритм составления расписания учебных занятий;
Разработать интеллектуальный алгоритм определения коэффициентов относительной важности частных критериев оптимальности расписания в условиях неопределенности;
Разработать программное обеспечение, реализующее предложенный агрегативный генетический алгоритм составления расписания;
Провести экспериментальную проверку эффективности предложенного генетического алгоритма.
Методы исследования
В работе использовались методы системного анализа, методы решения многокритериальных задач целочисленной оптимизации, методы искусственного интеллекта, методы экспертного оценивания.
Результаты, выносимые на защиту
На защиту выносятся следующие результаты исследований:
Структурные модели представления исходной информации для составления расписания;
Агрегативный алгоритм генетической оптимизации;
Интеллектуальный алгоритм определения коэффициентов важности частных критериев оптимальности расписания в условиях неопределенности.
22 Научная новизна работы
Научная новизна данной работы заключается в следующем:
Предложено использовать для описания исходной информации (наряду с общепринятыми информационными объектами "аудитории" и "учебные пары") новый информационный объект - "блок занятий", отличительной чертой которого является наличие явно выраженной структуры, объединяющей в единое целое такие объекты как "преподаватели", "группы", "дисциплины". Это позволяет существенно уменьшить количество варьируемых параметров при осуществлении процедуры генетической оптимизации.
Предложено, в соответствии с этим, использовать в качестве объектов генетической оптимизации особи, состоящие из двух хромосом связанных между собой по генам, характеризующим блоки занятий. Это позволяет уменьшить число используемых объектов генетической оптимизации - видов хромосом с пяти до двух и, тем самым, сократить время решения задачи.
Предложены модифицированные процедуры скрещивания и мутации, адаптированные для работы с предложенными выше структурированными объектами генетической оптимизации. Это позволяет существенно упростить учет ограничений.
Предложены интеллектуальные алгоритмы определения коэффициентов важности частных критериев на основе экспертных оценок, отличительной особенностью которых является использование векторного коэффициента важности данных частных критериев. Это позволяет обеспечить высокую достоверность экспертных оценок их важности в условиях неопределенности, правильный выбор весовых коэффициентов аддитивного критерия оптимальности и в конечном итоге заданное качество расписания в условиях неполноты априорной информации.
23 Практическая значимость
В процессе проведенных исследований были получены следующие результаты, имеющие практическую ценность:
Разработано программное обеспечение, реализующее предлагаемые алгоритмы генетической оптимизации применительно к решению задачи составления расписания в образовательных системах массового обучения. Программное обеспечение реализовано в среде Borland Delphi, обладает удобным пользовательским интерфейсом.
Результаты экспериментальной проверки предложенных алгоритмов (на примере факультета ИРТ) показали существенное (в 2-3 раза) уменьшение скорости роста временных затрат по мере увеличения сложности задачи составления расписания (увеличения числа блоков занятий) по сравнению с обычными генетическими алгоритмами.
Основания для выполнения работы
Работа выполнена на кафедре информатики Уфимского государственного авиационного технического университета (УГАТУ) в рамках госбюджетных работ, проводимых на кафедре Информатики УГАТУ, а также в рамках реализации внутривузовской Программы поэтапного внедрения на кафедре информатики технологий автоматизированного и дистанционного обучения.
Апробация работы
Основные результаты, представленные в диссертационной работе докладывались и обсуждались на: 8-й международной научно-методической конференции вузов и факультетов телекоммуникаций "Проблемы техники и технических телекоммуникаций" (Уфа, 2004), 5-й Международной научно- технической конференции "Проблемы техники и технических телекоммуникаций" (Самара, 2004), 7-й международной конференции "Информатика и Информаци-
24 онные технологии" CSIT'2005 (г. Уфа, 2005), Зимней школе аспирантов и молодых ученых (Уфа, 2006).
Публикации
По материалам диссертации опубликовано 10 печатных работ, из них 6 статей, 2 доклада, тезисы 2 докладов.
Благодарности
Автор выражает глубокую благодарность за полезные консультации к. физ.-мат. н., доценту Шехтман Л. И. и Ковтуненко А. С. за помощь при проведении экспериментальных исследований.
Объем и структура работы
Диссертационная работа состоит из введения, трех глав, заключения, библиографии и двух приложений. Работа содержит 122 страницы текста и 111 наименований библиографических источников.
Постановка задачи составления расписания учебных занятий на основе структурированных моделей исходной информации
Как уже говорилось ранее, к расписанию учебных занятий предъявляется множество трудноформализуемых и взаимнопротиворечивых требований. Все требования, предъявляемые к расписанию учебных занятий, условно разобьем на две группы.
Первая группа включает в себя обязательные требования, к числу которых относятся следующие: отсутствие накладок всех типов (для учебных групп, аудиторий, преподавателей), отсутствие "окон", соответствие типа аудитории виду занятий, необходимость проведения всех запланированных на семестр и предусмотренных учебным планом занятий, число проведенных в течение дня пар для каждой учебной группы не должно превышать некоторое заданное количество.
Вторая группа включает в себя требования, выполнение которых является желательным. К числу данных требований отнесем: соблюдение равномерности распределения занятий в течение недели, соблюдение необходимого соответствия между характером проводимых занятий и временным интервалом его проведения (например, лекции желательно проводить в начале учебного дня и т.д.); учет пожеланий преподавателей относительно своего расписания занятий; требования, связанные с обеспечением комфортности условий работы преподавателей и учебы студентов спецификой вуза (например, минимизация количества переходов из одного учебного корпуса в другой).
Требования, входящие в первую группу, будем рассматривать в качестве ограничений оптимизационной задачи составления расписания, требования, входящие во вторую группу - в качестве частных критериев. Описание ограничений 1) Требование отсутствия накладок для учебных групп будем описывать следующим образом: \/{gj,tk):gjEG,tksT 2 f 1 , (1.5) ieZgJ f]Ztk c где Z J — множество блоков занятий, в которых участвует группа ; Z k — множество блоков занятий, «занимающих» пару tjc.
Таким образом, для каждой упорядоченной двойки элементов (группа, пара), сумма компонент z\ блоков из множества ZgJ [}ztk не превышает 1. Фактически, это означает, что во время данной пары данная группа студентов присутствует на одном занятии в полном составе, либо обе подгруппы данной группы присутствуют на двух занятиях, либо одна из подгрупп данной группы присутствует на одном занятии; либо данная группа во время данной пары не присутствует ни на одном занятии.
Поясним условие выделения диапазона для суммирования. Занятия, объединенные в блоки, могут быть не поточными (zf = 0) или поточными (zf - 1). В первом случае достаточно проверить, совпадает ли код группы, участвующей в блоке занятий (z?) с интересующим нас кодом группы g,-. Во втором случае компонента z? является кодом потока, т.е. множества групп, и необходимо проверить, входит ли группа g у в поток z?. Получаем
Компонента тг- указывает на номер пары в течение семестра, присвоенной первому занятию блока zz-. Однако каждый блок Zj в общем случае занимает не одну, а несколько пар. Номер недели пары 1 , «занимаемой» блоком w . ,w w { h її w г Zf, должен удовлетворять условию %i t, Xf +\Zf -lj-zi в любом случае (и при zf =l, и при zf =2). Кроме того, в случае когда занятия проводятся через неделю (zf -2), номер недели пары t/c должен быть четным при четном значении xf и нечетным при нечетном xf (if mod 2 = tf mod 2). Номер дня d d пары tfc должен совпадать с номером дня, присвоенным блоку (t, =% ), а номер пары в течение дня (tP) должен совпадать с номером пары в течение дня, присвоенным блоку (tp= xlp) или, в случае, когда одно занятие блока содержит две пары (zlc = 2), — со следующим номером учебной пары (ti = т „ +1). Получаем Z = \;: х- S т," + (Zf -1). zf )л z» = l)v {zf = 2)л (,» mod 2 = mod 2Цл A =tfWI»;=TfjvW=2N/f=tf+l =K f-f+l]]V (1-6) r 2) Отсутствие накладок для аудиторий Данное ограничение можно сформулировать так: V (ar,t]c):ar є A,tj( є Г 3!Zj : (щ - аг)л\ ZJ є Z к v V BZJ :{щ =ar)/\\zi є Z k (1.7) где — множество блоков занятий, «занимающих» пару t .
Таким образом, для каждой упорядоченной двойки элементов (аудитория, пара), либо существует единственный блок занятий (z/), которому присвоена данная аудитория (а/ = аг) и который «занимает» данную пару (zz- є Z ), либо такого блока не существует вовсе, т.е. данная аудитория свободна во время данной пары.
Экспертное ранжирование важности частных критериев оптимальности расписания в условиях высокой степени полноты информации экспертов (в условиях определенности)
В предыдущей главе было предложено использовать четыре частных критерия оптимальности расписания, входящих с соответствующими коэффициентами важности Wf в аддитивный критерий оптимальности Р расписания учебных занятий. С помощью данных коэффициентов можно учитывать относительную важность частных критериев. Так, чем больше значение весового коэффициента, тем более важным считается тот или иной частный критерий и наоборот.
Подобная форма представления критерия оптимальности расписания позволяет более просто учитывать, во-первых, опыт и предпочтения лиц, ответственных за составление расписания, во-вторых, специфику конкретных образовательных систем. Так, например, для образовательных систем с территориальной разбросанностью учебных корпусов критерий, характеризующий требование минимизации количества переходов из одного учебного корпуса в другой может представлять особую важность, для вузов, чьи учебные корпуса располагается на одной территории, данное требование может быть менее важным по сравнению с другими требованиями.
Следует отметить, что введенный в работе аддитивный критерий качества расписания основан на декомпозиции и последующем агрегировании частных критериев оптимальности, предъявляемых к расписанию учебных занятий. Это существенно облегчает формирование в целом критерия оптимальности расписания. При этом, однако, возникает проблема определения значений коэффициентов важности. Данная проблема может быть решена с использованием или же модификацией существующих методов определения весовых коэффициентов. Здесь следует отметить, что как таковая проблема назначения весовых коэффициентов оптимизируемого критерия (функционала), не является предметом теории оптимизации. Методы классической теории оптимизации предполагают данные весовые коэффициенты заданными.
Тем не менее, проблема выбора весовых коэффициентов существует, однако применяемые методы ее решения являются, в отличие от методов решения основной задачи оптимизации, менее формализованными. Более того, существует два основных подхода к решению задачи назначения весовых коэффициентов.
Первый из них основан на определении значений весовых коэффициентов методами экспертного оценивания, второй подход базируется на организации итеративного процесса поиска весовых коэффициентов по так называемым вторичным критериям оптимальности.
Определение весовых коэффициентов методами экспертного оценивания в известных работах происходит по "разомкнутой схеме", т.е. без решения оптимизационной задачи и анализа частных критериев оптимальности полученного решения. В целом в рамках данного подхода можно выделить две группы способов определения значений весовых коэффициентов. В первом случае весовые коэффициенты назначаются непосредственно экспертами. Однако исследования показывают, что человек (эксперт, ЛПР) не способен непосредственно назначать критериям корректные численные веса. Другой способ предполагает использование различных методов получения и обработки знаний (мнений) экспертов и вычисление на их основе значений коэффициентов важности. Второй способ является более формализованным, но, тем не менее, не гарантирует получение хорошего решения в виду возможного наличия некоторой доли субъективизма в оценках экспертов или же в силу недостаточной их информированности.
Применительно к задаче составления расписания, это означает, что определение весовых коэффициентов при использовании первого подхода не требует достаточно затратной по времени процедуры многократного решения задачи целочисленной оптимизации, т.е. процедура решения задачи является одностадийной.
Второй подход является более формализованным и основан на определении весовых коэффициентов путем организации итеративного процесса их поиска по так называемым вторичным критериям оптимальности. Данный подход не требует привлечения высококвалифицированных экспертов, так как начальные значения весовых коэффициентов определяются либо случайным образом, либо на основе весьма приблизительных представлений об относительной важности частных критериев оптимальности. Однако данный подход требует достаточно затратной по времени процедуры многократного решения задачи целочисленной оптимизации, т.е. процедура решения задачи является многостадийной (итеративной).
Применение аппарата нечеткой логики для организации процедуры , коррекции весовых коэффициентов
Одним из способов устранения неопределенностей является использование подхода, описанного в работе [43] и называемого "нечеткой логикой". Достоинством данного подхода является возможность оперировать в расчетах не точными значениями коэффициентов, а их размытыми отображениями (так называемыми нечеткими множествами). Это позволяет более гибко учитывать множество факторов влияющих на оценку, в нашем случае - учитывать достоверность информации о важности критериев.
Впервые термин "нечеткое множество" был введен в классической работе Лотфи Заде [43]. Нечетким было предложено называть множество элементов X, где для каждого элемента х еХ задано значение функции принадлежности /л(х) из интервала [0;1], описывающее степень принадлежности элемента множеству X.
Аппарат нечеткой вычислительной системы включает в себя следующие понятия: Лингвистические переменные. Интуитивные понятия естественного языка. Термы - это значения, которые может принимать лингвистическая переменная. Для каждой лингвистической переменной задается несколько термов - нечетких множеств, определяющих различные значения лингвистической переменной из естественного языка. Терм определяется функцией принадлежности.
Система нечетких правил. Нечеткое правило - интуитивное лингвистическое правило, построенное по схеме логической импликации «ЕСЛИ - ТО», где условие «ЕСЛИ» соответствует принятию лингвис тической переменной р некоторого значения а, а вывод «ТО» означает необходимость выбора значения b для лингвистической переменной. Например «ЕСЛИ р=а ТО q=b» В связи с этим, для нечетких вычислительных систем приняты следующие основные этапы вычислений.
Фаззификация. Переход от конкретных значений числовых переменных к представлению их в системе нечетких множеств.
Выработка решения. Применение к полученным представлениям используемой базы правил. Результатом это операции является решение задачи в виде нечеткого множества.
Дефаззификация. Отображение нечеткого множества, полученного в результате предыдущей операции в единственное значение, которое и будет являться решением задачи. Здесь следует отметить, что процедура дефаззификации может быть осуществлена разными методами, наиболее распространенным является метод центра тяжести.
Общая схема вычисления коррекции коэффициентов важности представлена на рисунке 2.3. Рассмотрим этапы построения нечеткой системы коррекции коэффициентов важности частных критериев оптимальности расписания более подробно. Как уже было сказано, значения коэффициентов важности необходимо уточнить с учетом имеющихся коэффициентов достоверности, в качестве которых в данной работе принимается степень осведомленности экспертов о важности рассматриваемых критериев. Поэтому нами были выбраны следующие лингвистические переменные:
Важность - коэффициент важности конкретного критерия, показывает, насколько данный критерий, по мнению экспертов, важен для расписания.
Достоверность - достоверность оценки важности критерия, показывает, насколько эксперты осведомлены и обладают всей полнотой информации для оценивания важности критерия.
Коэффициент коррекции - коэффициент коррекции расчетного коэффициента важности.
Для первых двух лингвистических переменных, являющихся входными, зададим следующие термы: «низкая», «средняя», «высокая». Для выходной переменной - коэффициента коррекции - зададим следующие термы: «сильно уменьшить», «немного уменьшить», «не изменять», «немного увеличить», «сильно увеличить».
Далее определим функции принадлежности для введенных нами лингвистических переменных "Важность" и "Достоверность". Функции принадлежности для данных лингвистических переменных могут иметь, например, следующий вид (рисунок 2.4).
Описание структуры программных модулей программного комплекса "Феб"
Предложенные в диссертации модели и алгоритмы составления расписания учебных занятий были реализованы в виде программного комплекса "Феб". С организационной точки зрения программный комплекс составления учебного расписания делится на две части, каждая из которых является самостоятельным независимым приложением. Соответственно, функции, выполняемые каждым приложением, разделены по принципу независимости работы с информацией об учебных нагрузках: 1. Приложение, предназначенное для заполнения базы данных; 2. Приложение, выполняющее все вычисления, соответствующие разработанному генетическому алгоритму.
Первое приложение реализует только структуризацию исходной информации и заносит в базу данные о преподавателях, дисциплинах, группах и т.д. в уже подготовленной для вычислений форме. Второе приложение считывает структурированные и подготовленные данные, производит все необходимые вычисления и выдает на экран оптимальное расписание.
По этому принципу первое приложение будем называть «приложение-заполнитель», второе же - «приложение-построитель». Описание «заполнителя» В программе реализована связь с базой данных MS Access с использованием технологии ADO.
В первую очередь должны быть заполнены терминальные (конечные) таблицы базы данных. В нашем случае информация должна заноситься в следующем порядке: Информация о специальностях, с указанием сокращенного и полного названия специальности Группы, с указанием сокращенного названия специальности, курса и номера группы. Потоки Информация о парах, учебных днях недели, а также об учебных неделях. Используемые типы аудиторий. Аудитории, с указанием номера корпуса и номера аудитории в корпусе. Фамилия, имя и отчество преподавателей Названия дисциплин Информация о блоках занятий, с указанием объема курса, а также наличия деления потока на подгруппы в случае, к примеру, лабораторных занятий
Занесение информации в таком порядке позволит избежать возможных конфликтов, обусловленных наличием в базе данных идентифицирующих связей и требованием непротиворечивости данных.
Описание «построителя»
В программе построителе реализована идеология объектно-ориентированного программирования.
Приложение «построитель» состоит из двух основных модулей: - Модуль GeneticAlgoritm. Содержит описание классов, реализующих генетическое вычисление. - Модуль raspisanie. Он содержит описание классов, которые работают с данными, осуществляют интерфейс программы с базой данных, а также с пользователем. Описание модуля GeneticAlgoritm Структура популяции реализована иерархически. На самом нижнем уровне находится класс «ген» - TGen. Основными его компонентами являются следующие поля: ValueListrarray of real; - множество возможных значений гена property Valuerreal read FValue write SetValue; - текущее значение гена, а также его эквивалент: property ValueNumberrinteger read FValueNumber write SetValueNum-ber; - номер текущего значения из допустимого множества.
Необходимым методом класса «ген» является процедура procedure AssignAsModel(var a:TGen); которая создает из данного гена копию того гена, который подается в нее в качестве параметра путем переноса множества допустимых значений. Главным же методом этого класса является процедура: procedure Initialize;
Она присваивает гену случайное значение из его множества допустимых значений Следующим элементом иерархии является класс «хромосома» Chromosome. Основным его компонентом является множество генов хромосомы: Genrarray of TGen; Длина массива генов указывается в свойстве: property ChromLengthrinteger read FChromLength write SetChrom-Length;
