Содержание к диссертации
Введение
1. Обзор и анализ моделей, методов и программных комплексов для составления расписаний занятий 15
1.1 Обзор и анализ постановок, методов и алгоритмов решения задачи составления расписаний занятий 15
1.2 Обзор автоматизированных систем составления расписаний занятий 28
Выводы по главе 1 33
2. Системный анализ, построение математической и информационной моделей задачи составления расписаний занятий 36
2.1 Системный анализ задачи составления расписания занятий и формализация основных объектов 36
2.1.1 Формализация объекта «ресурс» 38
2.1.2 Формализация объекта «временной интервал» 41
2.1.3 Формализация объекта «деятельность» 44
2.1.4 Анализ взаимозависимости учебных групп 48
2.1.5 Формализация объекта «расписание» 55
2.2. Анализ требований и пожеланий, учитываемых при составлении расписания 57
2.2.1 Обязательные требования 57
2.2.2 Статические жесткие ограничения 59
2.2.3 Динамические жесткие ограничения 63
2.2.4 Желательные требования (мягкие ограничения)
2.3 Критерий качества расписания 69
2.4 Общая схема обработки информации при составлении расписаний занятий з
2.5 Информационная модель в нотации Information Engineering 84
Выводы по главе 2 87
3. Методы и алгоритмы составления расписаний занятий на основе генетического алгоритма 89
3.1 Общая схема решения задачи составления расписания учебных занятий вуза 89
3.2 Эвристический алгоритм построения допустимого расписания путем последовательного размещения учебных единиц 91
3.3 Локально оптимальная стратегия построения расписания на основе генетического алгоритма 3.3.1 Формулировка задачи последовательной локальной оптимизации 96
3.3.2 Выбор способа кодирования решений 98
3.3.3 Разработка класса chromosomeb 99
3.3.4 Разработка класса populationb 100
3.3.5 Оператор мутации 102
3.3.6 Оператор скрещивания 102
3.3.7 Построение следующей популяции хромосом 103
3.3.8 Интеграция генетического алгоритма в процедуру локальной оптимизации 105
3.4 Применение генетического алгоритма для управления локальной оптимизацией 106
3.4.1 Общая схема гибридизации 106
3.4.2 Выбор способа кодирования решений 108
3.4.3 Разработка класса chromosome p 109
3.4.4 Разработка класса population p 109
3.4.5 Оператор мутации 111
3.4.6 Операторы скрещивания 111
3.4.7 Построение следующей популяции хромосом 113
3.4.8 Интеграция глобального генетического алгоритма в общую схему решения задачи составления расписания занятий 114
Выводы по главе 3 115
4. Веб-ориентированный программный комплекс «расписание» 119
4.1 Общая архитектура программного комплекса «Расписание» и организация диалога с пользователями 119
4.2 Создание базы данных программного комплекса 125
4.3 Разработка объектно-ориентированного вычислительного ядра программного комплекса 126
Выводы по главе 4 135
Заключение 137
Список использованной литературы
- Обзор автоматизированных систем составления расписаний занятий
- Анализ требований и пожеланий, учитываемых при составлении расписания
- Эвристический алгоритм построения допустимого расписания путем последовательного размещения учебных единиц
- Создание базы данных программного комплекса
Введение к работе
Актуальность темы. Задача составления расписания учебных занятий
вуза (University Course Timetabling Problem - UCTP) является типичной
проблемой, с которой постоянно сталкиваются все университеты мира. Она
привлекает внимание математиков ИТ-специалистов уже достаточно
продолжительное время и к настоящему времени сделано большое количество постановок этой задачи, имеющих разную степень строгой математической формализации, предложены различные методы и алгоритмы решения UCTP и разработаны многочисленные информационные системы «Расписание», в том числе и представленные на рынке коммерческие системы. Актуальность поиска эффективных методов и алгоритмов решения UCTP подтверждается фактом проведения с 2002 г. международных соревнований по этой проблематике (International Timetabling Competition). Третье по счету такое соревнование (ITC2011) проводилось в 2011-2012 г. и на нем было представлено 35 участников из 10 стран.
Существует огромное количество работ по тематике UCTP и
неослабевающий интерес исследователей к этой задаче. ожно
констатировать, что на сегодняшний день отсутствуют общепризнанные и
неоспоримые модели, методы и алгоритмы этой области прикладной
математики продолжение исследований в направлении построения
оптимальных расписаний по-прежнему стоит в повестке дня.
Проблеме автоматического составления оптимальных расписаний занятий посвящены многочисленные диссертационные исследования в России (Лопатеева О.Н., Маслов М.Г., Галузин К.С, Низамова Г.Ф., Милехина Т.В., Асвад Фирас М. и др.) и за рубежом (R. Lewis, M. Marte, H. Larget, M.T. Jensen, C. Mihaila и др.)
Количество публикаций в периодических изданиях и трудах конференций
по данной тематике исчисляется тысячами. Для решения UCTP предлагают
использовать: классические методы (теория графов, целочисленное линейное
программирование); метаэвристические (эволюционные генетические
алгоритмы, метод имитации отжига - simulated annealing, табу-поиск - tabu search, метод муравьиных колоний - ant colony optimization, максиминная муравьиная система - max-min ant system, оптимизация роем частиц - particle swarm optimization); мультиагентные системы; метод решения по прецедентам.
Отсутствие универсальных постановок UCTP, имеющих высокую степенью математической строгости и учитывающих последующую компьютерную реализацию делает актуальной построение модели UCTP с максимально возможным учетом ограничений, требований и пожеланий к расписанию на основе сегодняшних реалий организации учебного процесса в вузах, использующей наряду (параллельно) с математической нотацией другие нотации, принятые в компьютерных науках - реляционные отношения и формальные языки программирования.
Заслуживает внимание идея гибридизации (совместного использования) различных методов и алгоритмов при построении общей схемы решения UCTP. Как показал обзор публикаций, наиболее подходящими “кандидатами” для гибридизации являются эвристические алгоритмы последовательной (пошаговой) локальной оптимизации, базирующиеся на идее “жадных” алгоритмов и специализированные версии генетического алгоритма, используемые как для поиска локального оптимума, так и для управляемого перебора вариантов (последовательностей) множества сущностей (учебных единиц), размещаемых в сетке расписания.
В постоянном развитии находится рынок автоматизированных систем составления расписаний занятий, игроками на котором являются даже такие «киты» ИТ-индустрии, как фирма «1С» со своей разработкой «1С: Автоматизированное составление расписания. Университет». Верхние строчки мировых рейтингов занимают также такие зарубежные разработки, как Lantiv Scheduling Studio 7 (Израиль) и OROLOGIO 13.x (Греция).
Все это свидетельствует об актуальности проведения теоретических и прикладных исследований о тематике UCTP, а также построению эффективных компьютерных реализаций разрабатываемых методов и алгоритмов.
Диссертационная работа выполнена в рамках научного направления ЮРГПУ (НПИ) «Теория, принципы и технологии построения информационно-вычислительных и измерительных систем» (утверждено решением ученого совета университета от 20.09.2011 г.)
Целью диссертационной работы является разработка и исследование математических, информационных алгоритмических моделей, а также методов, алгоритмов, программных модулей и комплексов для решения задачи автоматического построения квазиоптимальных расписаний учебных занятий.
Задачи диссертационной работы:
-
На основе системного анализа выполнить формализацию задачи составления расписания занятий учетом требований и пожеланий, отражающих реальные условия планирования организации учебной деятельности вузов. При формализации и построении модели использовать не только общепринятую математическую (теоретико-множественную) нотацию, но и нотации, используемые в компьютерных науках.
-
Обосновать разделение жестких ограничений, устанавливающих физическую реализуемость расписания, на статические, которые можно учесть до составления расписания и динамические, которые должны проверяться в процессе составления расписания. Разработать алгоритмы, программные модули и структуры данных для проверки жестких ограничений, снижающие вычислительные затраты на реализацию основных циклов поиска оптимального расписания за счет максимально возможной априорной обработки исходных данных.
3) Обосновать интегральный критерий качества расписания,
составляющими которого являются количественные оценки меры нарушения
мягких ограничений, «взвешенные» нормирующими множителями.
Реализовать в виде завершенного программного модуля алгоритм оценки
качества расписания, допускающий его использование на различных этапах
решения оптимизационной задачи составления расписания.
4) Сформулировать задачу последовательной локальной оптимизации
расписания; разработать и программно реализовать алгоритм ее решения,
основанный на гибридизации «жадного» и генетического алгоритмов.
5) Разработать реализовать общий алгоритм строения
квазиоптимального расписания использованием схемы двойной
гибридизации, предусматривающей внешний контур поиска оптимальной
перестановки учебных единиц с использованием генетического алгоритма и
внутренний контур поиска оптимального размещения для каждой учебной
единицы в процессе последовательной локальной оптимизации.
6) Разработать реализовать вычислительное дро программного
комплекса построения расписаний, содержащее программную реализацию
«жадного» и генетического алгоритмов, с использованием парадигм
обобщенного и объектно-ориентированного программирования.
7) Разработать общую структуру программного комплекса построения
расписаний с использованием концепции многозвенной архитектуры
реализовать серверную часть на базе современных программных платформ.
Методы исследования. В работе использованы: методы системного анализа, методы математического моделирования, теория графов, теория реляционных отношений, структуры и базы данных, методы поисковой оптимизации, эволюционные и генетические алгоритмы, методы обобщенного и объектно-ориентированного программирования, методы построения многозвенных программных приложений с веб-интерфейсом. Для практической реализации результатов исследований использованы: сервер баз данных Microsoft SQL Server, веб-сервер IIS, технологии и , фреймворк MVC, среда разработки Visual Studio, а также языки программирования С++ и C#.
Достоверность научных результатов и выводов подтверждается корректностью постановок задач, обоснованностью принятых допущений, корректным применением известных теоретических положений, методов и алгоритмов, устойчивой работой разработанного программного обеспечения и результатами численных экспериментов на модельных примерах.
Объектом исследования являются процессы обработки информации и принятия решений при составления расписаний учебных занятий для вузов.
Предметом исследования являются математические модели, методы, алгоритмы и программные комплексы, ориентированные на обработку
информации и построение квазиоптимальных расписаний учебных занятий для вузов.
Тематика работы соответствует п. 4 «Разработка методов и алгоритмов
решения задач системного анализа, оптимизации, управления, ринятия
решений обработки информации», . 5 «Разработка специального
математического и программного обеспечения систем анализа, оптимизации,
управления, принятия решений и обработки информации» и п. 8. «Теоретико-
множественный теоретико-информационный анализ сложных систем»
паспорта специальности 05.13.01 - «Системный анализ, управление и
обработка информации».
Научная новизна. В диссертации получены следующие новые научные и практические результаты:
предложена новая методика выполнения системного анализа формализации задачи составления расписания занятий, основанная на совместном использовании трех взаимодополняющих нотаций: теоретико-множественной, информационной (реляционной) и формально-языковой, что позволяет одновременно с формализацией выполнять компьютерную реализацию моделей и задач благодаря синергетическому эффекту от сочетания строгости и утилитарности этих нотаций;
впервые разработан комплекс математических, информационных и алгоритмических моделей задачи составления расписания занятий, отличающийся от известных высокой гибкостью, взаимосогласованностью моделей, максимальным учетом современных подходов к организации учебного процесса, модульной структурой и конструктивностью;
- предложена оригинальная схема структуризации обработки
информации задачи составления расписания занятий, отличающаяся от
известных новыми алгоритмами априорной обработки исходных данных,
позволяющими значительно снизить вычислительные затраты на реализацию
основных циклов поиска оптимального решения;
- впервые разработан программно реализован алгоритм
последовательной локальной оптимизации расписания, базирующийся на идее
гибридизации «жадного» и генетического алгоритмов;
- впервые предложен программно реализован общий алгоритм
построения квазиоптимального расписания с использованием схемы двойной
гибридизации, предусматривающей внешний контур поиска оптимальной
перестановки учебных единиц с использованием генетического алгоритма и
внутренний контур поиска оптимального размещения для каждой учебной
единицы в процессе последовательной локальной оптимизации;
- предложен и теоретически обоснован новый генетический оператор
скрещивания для решений, кодируемых перестановками, что позволяет в одном
цикле получать множество «потомков» и открывает новые возможности для
совершенствования генетических алгоритмов.
Основные положения, выносимые на защиту:
-
методика формализации сложных задач дискретной оптимизации, основанная на совместном использовании трех различных нотаций: теоретико-множественной, реляционной формально-языковой, о позволяет одновременно строить математическую, информационную и алгоритмическую модели задачи;
-
математическая, информационная и алгоритмическая модели задачи составления расписания занятий;
-
метод и алгоритм решения задачи составления расписания занятий, использующий схему двойной гибридизации для генетического и «жадного» алгоритмов;
-
модификации генетических операторов скрещивания и мутации;
5) реализация вычислительного ядра программного комплекса с
использованием парадигм обобщенного объектно-ориентированного
программирования.
Теоретическая ценность работы.
Ценность научных работ состоит в том, что предложен, научно обоснован и практически реализован оригинальный комплекс математических, информационных и алгоритмических моделей задачи составления расписания занятий. Предложен и программно реализован набор алгоритмов обработки информации ри решении задачи построения оптимального расписания, сокращающих вычислительные затраты и спользующих схему двойной гибридизации, базирующуюся на сочетании «жадного» и генетических алгоритмов.
Практическая ценность работы.
Практическая значимость исследования заключается в том, что на основе
разработанных методов и алгоритмов создано специальное программное
обеспечение - вычислительное ядро программного комплекса «Расписание»,
базирующееся на парадигмах обобщенного и объектно-ориентированного
программирования обеспечивающее высокую надежность
производительность в создании прикладных программных приложений за счет
повторного использования кода. С использованием концепции трехзвенной
архитектуры разработан веб-ориентированный программный комплекс
«Расписание», позволяющий удовлетворять информационные запросы
пользователей с использованием ими простейших программных средств - веб-
браузеров; входящая комплекс программа «Серверное программное
обеспечение я автоматизации работы с расписаниями занятий»,
зарегистрированная в Реестре программ я ЭВМ (свидетельство
№ 2014616666).
Реализация результатов работы. Результаты диссертационной работы нашли практическое применение в высших учебных заведениях Ирака (Al-Furat Al-Awsat Technical University, Babylon Technical Institute) при составлении
расписаний занятий, а также на факультете информационных технологий и управления ЮРГПУ (НПИ) ри реализации магистерских программ программ обучения в аспирантуре по направлениям подготовки 09.04.01, 09.06.01 «Информатика и вычислительная техника», 09.04.04 «Программная инженерия».
Апробация работы. Основные положения и научные результаты диссертации излагались на научно-технических конференциях:
II Международная научная конференция преподавателей, аспирантов, магистров и студентов вузов «Наука. Образование. Культура: вклад молодых исследователей» (г. Новочеркасск, ЮРГПУ (НПИ), 23-24 апреля 2013 г.)
Международные научно-практические конференции «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (г. Новочеркасск, ЮРГПУ (НПИ), 2014 и 2015 гг.)
”The first international conference of Information Technology In Yemen” / Saba Journal of Information Technology and Networking (SJITN) is a peer-reviewed international journal, published under the Faculty of Computer and Information Technology at Saba University in Yemen (Sana'a, 2014)
Кроме того, результаты диссертационного исследования регулярно размещаются для обсуждения на персональной странице автора на Интернет-площадке «Социальная сеть для учёных» ( ).
Публикации. По теме диссертации опубликовано 7 печатных работ, в
том числе: 2 статьи в ведущих рецензируемых изданиях, рекомендованных
ВАК; 1 свидетельство о государственной регистрации программы для ЭВМ; 4
публикации по результатам международных всероссийских научно-
практических конференций.
Структура диссертации. Диссертация содержит 158 страниц основного текста, 33 рисунка, 7 таблиц и состоит из введения, четырех глав, заключения, списка литературы из 137 наименований и 5 приложений объемом 73 страницы.
Обзор автоматизированных систем составления расписаний занятий
Задача составления расписаний учебных занятий вуза (University Course Timetabling Problem - UCTP) привлекает внимание математиков и ИТ специалистов уже достаточно продолжительное время. К настоящему времени сделано большое количество постановок этой задачи, имеющих разную степень строгой математической формализации, редложены различные методы и алгоритмы решения UCTP разработаны многочисленные информационные системы «Расписание», в том числе и представленные на рынке коммерческие системы. Актуальность задачи поиска эффективных методов и алгоритмов построения расписаний занятий доказывается фактом проведения с 2002 г. международных соревнований по этой проблематике (International Timetabling Competition) [1]. Третье по счету такое соревнование (ITC2011) проводилось в 2011-2012 гг. [2]. На нем было представлено 35 участников из 10 стран.
Широта спектра имеющихся постановок UCTP, методов и алгоритмов, а также завершенных систем в этой области показана в следующем обзоре диссертаций и научных публикаций, представленных сегодня в открытом доступе как на русском, так и на английском языках.
В диссертации и татьях Лопатеевой О.Н. [3, 4, 5] UCTP формулируется как задача распределения ресурсов для множества работ, которые, в свою очередь, размещаются на временной сетке. Работа - это пара “учебная дисциплина (z) + вид занятия (v)”, требующая для своего выполнения тройку ресурсов “преподаватель (р) + учебная группа (g) + аудитория (а)”. Работы вместе с ресурсами размещаются в часовой сетке расписания (матрице) «день недели (d), учебная пара (/)». Для каждого ресурса задан «календарь доступности» - список ячеек сетки расписания, для которых ресурс доступен (например, преподватель присутствует в вузе). Факт распределения фиксируется мультииндексными булевыми переменными Xpdi, xgdi и хаса, которые позволяют учесть 3 “жестких” ограничения, связанные с занятостью определенного ресурса в определенный отрезок времени (совместимостью ресурсов по времени). С использованием этих переменных сформулированы 4 критерия оптимальности (минимизация “окон” у преподавателей и студенческих групп и минимизация потерь от переходов между учебными корпусами преподавателей и студенческих групп для смежных учебных пар) и одно ограничение в форме равенства (весь недельный учебный план должен быть выполнен). Доказана NP-полнота UCTP. Предложены эвристики для «жадного» алгоритма последовательного распределения работ и ресурсов. Разработана информационная модель (база данных) и выполнена программная реализация в виде системы. В диссертации Маслова М.Г. [6] выполнена детальная формализация UCTP с писанием всех сущностей (преподаватели, учебные группы, аудитории, учебные дисциплины, временные интервалы и др.) и связей между ними. Рассмотрены 11 обязательных ограничений и 11 желательных требований, из которых конструируется критерий оптимальности расписания. В итоге UCTP сформулирована как задача нелинейного булева программирования с ограничениями критериями виде формул исчисления предикатов. Обсуждается проблема NP-полноты UCTP. Для решения задачи предлагается использовать эвристические методы (для получения начального приближения) и классический генетический алгоритм.
Для кодирования расписания предлагается использовать матричное представление хромосомы: в ячейках матрицы АхН (А - множество аудиторий, Н - множество учебных пар) размещаются учебные занятия (заявки в терминологии автора). Для этого представления разработаны специализированные генетические операторы. Описана программная реализация системы для составления расписания в трехзвенной архитектуре. В диссертации Галузина К.С. [7] параметры UCTP вводятся обычным образом через определение ресурсов: множества преподавателей Т, учебных групп G и аудиторий R, а также задание часовой сетки расписания D для планируемого периода (которая в этой формулировке задается не матрицей, а вектором, образованным конкатенацией строк матрицы) и учебного плана L, перечисляющего все занятия всех видов для всех учебных групп на планируемый период (одну или две недели). Для каждого вида ресурсов задается «календарь доступности», разрешеющий использовать данный ресурс в указанный временной интервал. Отличительной особенностью данной постановки задачи является введение «обобщенных» преподавателей, «обобщенных» учебных групп и «обобщенных» аудиторий для учета деления академических групп на подгруппы и объединения групп в потоки. Вектор решения задачи (т.е. расписание) задается множеством пар «занятие из учебного плана, номер ячейки часовой сетки расписания». В этой работе также формулируются жесткие и нежесткие (мягкие) ограничения, причем для последних применяется аппарат нечетких множеств (функции принадлежности). Построены два обобщенных критерия оптимальности расписания, являющиеся взвешенной аддитивной сверткой двух множеств частных криерив: учитывающих интересы студентов и учитывающих интересы преподавателей. При построении критериев также используется аппарат нечетких множеств. Вводятся понятия множества допустимых расписаний и множества Парето-оптимальных (по отношению двум обобщенным ритериям) расписаний. Предложен гибридный алгоритм построения оптимального решения UCTP, состоящий из трех этапов: 1) Построение множества допустимых расписаний методами распространения ограничений с применением эвристики. 2) Оптимизация на полученном множестве методом стохастического поиска (с использованием эволюционной стратегии). 3) Поиск распределения аудиторий в найденном расписании по времени с помощью метода ветвей и границ. Выполнена программная реализация в 2-звенной архитектуре «клиент-сервер».
В диссертации и статьях R. Lewis [8, 9, 10, 11] выполнена наиболее последовательная и полная формализация UCTP как задачи размещения заданного множества мероприятий (учебных занятий) Е в ячейках матрицы RxT, где R - множество аудиторий (rooms) и Г- множество учебных пар (таймслотов, timeslots) в планируемом периоде (рис. 1.1). При этом аудитории имеют заданную вместимость, для каждого мероприятия указаны преподаватель и студенты. Между множеством студентов S и множеством мероприятий Е существует отношение “многие-ко-многим”, вследствие чего некоторые пары мероприятий являются потенциально конфликтующими, если хотя бы один студент должен посещать оба мероприятия. Еще одно отношение “многие-ко-многим” имеется между множеством аудиторий R и множеством мероприятий Е, обусловленное предпочтительностью определенных аудиторий для определенных мероприятий (аудитории для лекционных потоков, компьютерные классы, химические лаборатории и пр.). Вводится понятие допустимого расписания (feasible timetable), в котором для каждого мероприятия назначена одна аудитория, один таймслот и выполнены “жесткие” ограничения (hard constraints): 1) Конфликтующие по студентам мероприятия не должны быть распределены в один таймслот. 2) Аудитория, назначенная для мероприятия, должна иметь достаточную вместимость. 3) В каждую ячейку матрицы RxТ может быть назначено только одно мероприятие.
В дополнение к жестким ограничениям сформулированы 3 «мягких» ограничения (soft constraints), учитывающих интересы студентов: 1) Ни один студент не должен посещать мероприятие в последний таймслот дня; 2) Ни один студент не должен посещать более двух мероприятий подряд; 3) Ни один студент не должен иметь одно мероприятие в день. Возможны нарушения мягких ограничений и эти нарушения «штрафуются» (один штрафной балл за нарушение одного ограничения для одного студента).
Автор отмечает, что в сделанной постановке UCTP относится к классу задач группировки (grouping problem), или задач разбиения множеств на подмножества, в который входят такие классические задачи, как: задача о ранце (об упаковке блоков) (Bin Balancing (Equal Piles) Problem), задача о раскаске графа (Edge Colouring Problem), обобщенная задача о назначениях (Various versions of the Frequency Assignment Problem), задача о разбиении графа на подграфы (k-way Graph Partitioning Problem), транспортная задача (Pick-up and Delivery Problem), задача о группировке деталей для обработки (Cell Formation Problem). Предлагается для решения UCTP использовать группирующий генетический алгоритм (Grouping Genetic Algorithm - GGA), впервые предложенный E. Falkenauer в 1998 г. [12]. Приводится подробное описание модификации данного алгоритма применительно к UCTP. На персональной странице R.Lewis (http: //www.rhydlewi s. eu ) приведена исчерпывающая библиография публикаций по тематике UCTP и других задач дискретной оптимизации за период 2005 - 2015 гг.
Анализ требований и пожеланий, учитываемых при составлении расписания
Как будет показано в следующей главе работы, можно предложить различные алгоритмы построения допустимых расписаний, удовлетворяющих всем жестким ограничениям, и количество таких расписаний будет достаточно большим. Следовательно, необходим механизм отбора лучших определенном смысле расписаний из множества допустимых. Практически во всех публикациях, посвященных решению UCTP [3-62], отмечается, что не существует единственного критерия для оценки качества расписания, но в то же время имеется достаточно большой список желательных требований к расписанию, формулируемых в виде так называемых «мягких» ограничений (soft restrictions - SR). Эти ограничения могут и не выполняться для конкретного расписания; при этом степень нарушения совокупности таких ограничений может служить мерой качества расписания. Удобно сгруппировать «мягкие» ограничения в 3 группы: 1) общие требования, 2) требования к раписанию конкретного преподавателя и 3) требования к раписанию конкретного студента.
Первая группа требований: - SR1.1 - желательно планировать лекции в начале рабочего дня; - SR1.2 - количество избыточных мест в аудитории по отношению к количеству студентов не должно быть большим. Вторая группа требований: - SR2.1 - количество учебных занятий в день, проводимых преподавателем, не должно превышать заданного значения; - SR2.2 - учебные занятия, планируемые преподавателю на конкретный день, должны быть расположены в смежных таймслотах, без «окон» (соответственно, количество таких «окон» может служить мерой качества расписания); - SR2.3 - желательно отсутствие «переходов» между учебными корпусами в течение ня ля конкретного преподавателя (соответственно -количество переходов служит мерой качества расписания). Третья группа требований: - SR3.1 - количество учебных занятий день, на которых должен присутствовать студент, не должно превышать заданного значения; - SR3.2 - учебные занятия, планируемые студенту на конкретный день, должны быть расположены смежных таймслотах, без «окон» (количество «окон» влияет на оценку качества расписания); - SR3.3 - желательно отсутствие «переходов» между учебными корпусами в течение дня для конкретного студента (соответственно - количество переходов служит мерой качества расписания).
Выполним анализ сформулированных требований. Оценка выполнения требований первой группы - SR1.1 и SR1.2 (или оценка степени их нарушения) особого труда не вызывает и проводится непосредственно для каждой учебной единицы в процессе ее размещения в сетке расписания или для построенного расписания в целом.
Для оценки выполнения требований второй группы целесообразно создать вспомогательную таблицу «График работы преподавателя» (schedule teacher - STCH). С учетом содержания этих требований и для облегчения их проверки в таблицу STCH необходимо включить лишь следующие поля: Ntch (код преподавателя), Nw (номер недели), Nd (номер дня недели), Ntd (номер пары в течение дня), Nb (номер учебного корпуса). Формирование таблицы STCH производится с помощью следующего реляционного выражения на языке Tutorial D: ( U {Nu, Ntch} JOIN S {Nu, Ncell} JOIN SPG JOIN TP JOIN CR {Ncr, Nb} ) {Ntch, Nw, Nd, Ntd, Nb} AS S_TCH;
Эта таблица показывает «загрузку» преподавателя учебными «парами» по дням недели с указанием учебного корпуса, в котором проходит занятие.
При программировании алгоритмов для работы с данными в оперативной памяти компьютера целесообразно применить «свертку» полей Nw и Nd в одно “суррогатное” значение Nwd=10 Nw+Nd, что позволит упростить работу с таблицей STCH. Объявление этой таблицы на языке С++ в форме вектора имеет вид: vector tuple int, int, int, int S TCH; Элементы кортежа располагаются в следующем порядке: Ntch, Nwd, Ntd, Nb. Эта таблица может быть сформирована для готового расписания S или формироваться по ходу решения задачи при размещении очередной учебной единицы в сетке расписания. В приложении 3 (п. 3.2) приведен исходный код функции Tables: :make_S_TCH(), которая для пары (учебная единица и, ячейка сетки расписания с) формирует и добавляет к вектору STCH очередной элемент.
Для оценки выполнения требований третьей группы целесообразно также создать вспомогательную таблицу «График присутствия студента» (schedule student attendance - SST) подобно тому, как это было сделано для преподавателей. Однако студент, в отличие от преподавателя, всегда посещает занятия в составе некоторой учебной группы и поэтому таблица SST должна составляться не для конкретного студента, а для множества групп, в которые входит студент. Ранее для такого множества групп было введно понятие кластера и рассмотрены алгоритмы формирования кластеров. Вся информация о кластерах содержится в двух таблицах: CLGR (кластеры учебных групп) и CIG (вхождение групп в кластеры).
Эвристический алгоритм построения допустимого расписания путем последовательного размещения учебных единиц
Описание класса population_p Класс population_p расширяет базовый класс двумя закрытыми полями: таблицей имен кроссинговеров и номером конкретного выбранного кроссинговера, тремя открытыми статическими полями - параметрами генетического алгоритма: вероятностью скрещивания (P_CROSS_p), вероятностью мутации (P_MUT_p) и долей элиты в следующем поколении (ЕЫТЕ_р), а также двумя конструкторами и открытой функцией next_pop(...), создающей следующую популяцию хромосом. Параметры генетического алгоритма P_CROSS_p, P_MUT_p и ELITE_p также объявляются и инициализируются в основной программе.
Описание класса GAbinary Класс GAbinary обеспечивает реализацию ЛГА и содержит в закрытой части параметры ЛГА - размер популяции N_pop_b и количество поколений (итераций) ITERb, а также саму популяцию pop. В открытой части находится конструктор с параметрами, который заполняет закрытые поля класса и, кроме того, принимает в качестве последнего параметра указатель на внешнюю фитнесс-функцию и передает его в класс chromosomeb (через статическое поле chromosome_b::fit_fun). Именно этот класс и является клиентом внешней фитнесс-функции. В качестве значения по умолчанию для этого параметра использована функция evalDF, которая производит оценку «пригодности» пары (учебная единица и, ячейка сетки расписания с), как это описано в п.3.3.1. В открытой части класса находится также метод GAbin, который и реализует генетический алгоритм: формирует случайным образом начальную популяцию, а затем в цикле формирует еще N_pop_b поколений. В качестве результата своей работы метод GAbin возвращает первую по списку хромосому из последнего поколения, которая и будет наилучшим решением.
В приложении 3 (п.3.6 и 3.7) приведены исходные коды файлов Geneticb.h и Geneticb.cpp с объявлением и реализацией классов chromosomeb, populationb и GAbinary. GA permut Описание класса GA_permut Класс GA_permut обеспечивает реализацию ГГА и содержит в закрытой части параметры ГГА - размер популяции N_pop_p и количество поколений (итераций) ITER_p, а также саму популяцию pop. В открытой части находится конструктор с параметрами, который заполняет закрытые поля класса и, кроме того, принимает в качестве последнего параметра указатель на внешнюю фитнесс-функцию и передает его в класс chromosome_p (через статическое поле chromosome_p::fit fun). Именно этот класс и является клиентом внешней фитнесс-функции. В качестве значения по умолчанию для этого параметра использована статическая функция SLO класса Fitness, которая реализует алгоритм последовательной локальной оптимизации для заданной перестановки учебных единиц, как это описано в п.3.3.8. В открытой части класса находится также метод GA_perm, который и реализует генетический алгоритм: формирует случайным образом начальную популяцию, а затем в цикле формирует еще N_pop_p поколений. В качестве результата своей работы метод GA_perm возвращает первую по списку хромосому из последнего поколения, которая и будет наилучшим решением (наилучшей перестановкой учебных единиц). В завершение работы метода GA_perm еще раз вызывается функция SLO, которая и формирует расписание для наилучшей перестановки.
В приложении 3 (п.3.8 и 3.9) приведены исходные коды файлов Genetic_p.h и Genetic_p.cpp с объявлением и реализацией классов chromosome_p, population_p и GA_permut. В этом же приложении приведен исходный код файлов Fitness.h и Fitness.срр с объявлением и реализацией класса-оболочки Fitness, содержащего фитнесс-функции evalDF и SLO.
Tables Класс, интегрирующий все структуры данных (таблицы) и всю функциональность по их обработке Является классом-сервером для большинства классов вычислительного ядра 2 Fitness Класс-оболочка для двух статических фитнесс-функций: eval_DF и SLO Фитнесс-функции eval_DF и SLO используются в конструкторах классов chromosome_b и chromosome_p для вычисления “пригодности” хромосом 3 chromosome Шаблонный класс для поддержки абстракции «хромосома» Является базовым для конкретных классов chromosome_b и chromosome_p 4 population Шаблонный класс для поддержки абстракции «популяция» Является базовым для конкретных классов population_b и population_p 5 chromosome b Класс для поддержки абстракции «хромосома с бинарным кодированием» Является производным от шаблонного класса chromosome и классом-клиентом Tables 6 chromosome_p Класс для поддержки абстракции «хромосома с кодированием перестановками» Является производным от шаблонного класса chromosome и классом-клиентом Tables 7 population b Класс для поддержки абстракции «популяция хромосом с бинарным кодированием» Является производным от шаблонного класса population, контейнером для объектов класса chromosome_b и классом-клиентом Tables 8 population_p Класс для поддержки абстракции «популяция хромосом с кодированием Является производным от шаблонного класса population, контейнером для объектов класса chromosome_p и перестановками» классом-клиентом Tables 9 GA binary Класс, обеспечивающий реализацию локального ГА (выбор наилучшего размещения для учебной единицы) Включает в качестве поля экземпляр класса population_b и является классом-клиентом Tables 10 GA_permut Класс, обеспечивающий реализацию глобального ГА (выбор наилучшей перестановки учебных единиц) Включает в качестве поля экземпляр класса population_p и является классом-клиентом Tables 11 roulette Класс для генерации псевдослучайных чисел с заданной дискретной функцией распределения («колесо рулетки») Использует специализацию mt19937 шаблонного класса mersenne_twister_engine стандартной библиотеки С++ . При создании экземпляра класса roulette выполняется его инициализация заданной таблицей частот (вариационым рядом распределения) 12 uni int Класс для равновероятного выбора целого числа из заданного диапазона Использует специализацию mt19937 шаблонного класса mersenne_twister_engine стандартной библиотеки С++ . При создании экземпляра класса uni_int выполняется его инициализация парой целых чисел
Создание базы данных программного комплекса
В основе известных из литературы алгоритмов реализации циклического кроссовера лежит идея выделения в паре родительских хромосом (в паре перестановок) сопряженных циклических цепочек элементов и последующей манипулиции этими цепочками (перекрестного внедрения этих цапочек в хромосомы-потомки).
Покажем, что алгоритмы реализации этой общей идеи, описанные в публикациях, представленных в обзоре в главе 1, дают далеко не полный спектр всех возможных вариантов получения хромосом-потомков. Точнее говоря, они позволяют получить в лучшем случае пару потомков от пары родителей. Так, в [117] приведен числовой пример, в котором из пары родительских хромосом {P1=(6,3,10,2,1,4,7,9,8,5), P2=(8,1,2,10,6,9,4,7,3,5)} получают две хромосомы-потомка {Of1=(6,3,2,10,1,4,7,9,8,5), Of2=(8,1,10,2,6,9,4,7,3,5)} с использованием циклического кроссовера. Как будет показано ниже, эта пара родительских хромосом на самом деле порождает не 2, а 6 потомков. Для дальнейшего изложения приведем несколько соображений. Во-первых, отметим, что процедура выделения в родительских хромосомах циклических цепочек элементов в точности совпадает с известным алгоритмом разложения перестановки на циклы [87, с.29], если рассматривать эту пару хромосом как двустрочное представление перестановки. Следовательно, можно воспользоваться этими результатами в части терминологии и полученных результатов.
Примем для циклов следующие обозначения: P2i=(80,38,li,64), Р22=(22,10з), Р23=(95,77,4б), Р24=(59). Нижний индекс в обозначении перестановки (хромосомы) обозначает номер цепочки, а нижний индекс у значения элемента обозначает его позицию в хромосоме. С использованием этих обозначений можно записать труктуру хросомы ерез цепочки элементов следующим образом: Р2=Р2і+Р22+Р2з+Р24. Здесь операция сложения обозначает “склеивание” (конкатенацию) цепочек с учетом сохранения позиций элемента.
Заметим, что можно считать и Р2 первой строкой, а Р1 - второй (т.е. рассматривать обратную перестановку). В этом случае разложение Р1 на циклы будет таким: Р1=(6,1,3,8)(10,2)(4,7,9)(5)
Как видно, по составу значений элементов получены те же циклы. Будем называть их сопряженными циклами. Если записать и для этих циклов выражения с учетом позиций элементов: Р1і=(60,І4,Зі,88), РІ2=(102,2з), Р1з=(45,7б,97), Р14=(59), то можно сделать вывод - в сопряженных циклах один и тот же состав элементов и один и тот же набор занимаемых ими позиций. Различаются толко пары “элемент-позиция”. Структура хромосомы: Р1=Р1і+ РЬ+ Р1з+ РІ4 Заметим, что циклы длиной 1 задают тождественную перестановку Р1[і]=Р2[і]; это - тривиальные циклы и в дальнейших построениях их можно не учитывать. Очевидно, что все циклы в родительских хромосомах не могут быть тривиальными, так как в противном случае мы будем иметь две совершенно одинаковые хромосомы.
В основе предлагаемого нами модифицированного циклического кроссовера (будем называть его полным циклическим кроссовером - Full Cycle Crossover - FCX) лежит идея построения хромосом-потомков путем составления всех возможных комбинаций циклов родительских хромосом.
Каждая хромосома-потомок будет включать тот же набор циклов, что и у родительских хромосом, но случаи, когда все циклы взяты от одноо родителя исключаются. Пусть родительские хромосомы содержат по к нетривиальных циклов. Тогда удобно схему построения потомка изобразить в форме -разрядного двоичного числа: Ьк-Фк-2---Ьфо , в котором каждый разряд соответствует определенному циклу, а значение разряда указывает, от какого родителя берется соответствующий цикл. Так, Ь0 соответствует первому циклу, Ь\ - второму и т.д. При этом 0 означает первого родителя, а 1 - второго. Очевидно, что коды 00...О и 11... 1 не рассматриваются. Легко подсчитать общее количество схем: 2 -2.
Заметим, что для к нетривиальных циклов можно составить 2 -2 схем, а учитывая, что перестановка длиной п может иметь до п/2 нетривиальных циклов (если все циклы имеют длину 2), верхняя оценка количества хромосом-потомков, получаемых от двух родителей, получается такой: 2 -2. Так, при п=20 можно получить до 1022 потомков.