На правах рукописи

Асвад Фирас М.

МОДЕЛИ СОСТАВЛЕНИЯ РАСПИСАНИЯ ЗАНЯТИЙ НА ОСНОВЕ

ГЕНЕТИЧЕСКОГО АЛГОРИТМА НА ПРИМЕРЕ ВУЗА ИРАКА

Специальность 05.13.17 – Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж – 2013 2

Работа выполнена на кафедре математического и прикладного анализа ФГБОУ ВПО «Воронежский государственный университет»

Научный руководитель: Астахова Ирина Федоровна, доктор технических наук, профессор

Официальные оппоненты: Арзамасцев Александр Анатольевич, доктор технических наук, профессор, ФГБОУ ВПО «Тамбовский государственный университет»

им. Державина, зав. каф. компьютерного и математического моделирования Сербулов Юрий Стефанович, доктор технических наук, профессор, ФГБОУ ВПО «Воронежская государственная лесотехническая академия», профессор каф.

вычислительной. техники и информационных систем

Ведущая организация: ФГБОУ ВПО «Тюменский государственный университет»

Защита состоится « 25» декабря 2013 г. в 12 на заседании диссертационного совета Д 212.038.24 при Воронежском государственном университете по адресу: 394006, г. Воронеж, ВГУ, Университетская пл. 1, ауд. 226.

С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного университета.

Автореферат разослан «13» 11 2013 года.

Ученый секретарь диссертационного совета кандидат технических наук, доцент _ Воронина И.Е.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Развитие исследований, направленных на решение задачи составления расписания, можно разбить на два этапа. Первый этап имеет начало в 80-е годы и заканчивается в середине 90-х. В этот период масштабно применяются классические методы решения задач целочисленного программирования: метод полного перебора, метод раскраски графа, метод ветвей и границ (Безгинов А.Н., Трегубов С.Ю., Логоша Б.А., Петропавловская А.В., Гусева Н.Я.). Используемые в этих разработках методы имеют высокую степень формализации как самой задачи, так и используемых алгоритмов. Применение классических методов в образовательных системах обучения становится малоэффективным ввиду большой размерности задачи и значительных временных затрат. Это привело к появлению методов, получивших название интеллектуальных, положившему начало второму этапу. В их основе лежит использование различных эвристик и эвристических алгоритмов (Костин Л.А., Клеванский Н.Н., Маслов М.Г.). Решение задачи составления расписания с помощью эвристик не гарантирует нахождения глобального оптимума. Существует ряд работ, использующих для автоматизации составления расписания математический аппарат нечеткой логики (Ханов Г.В., Алабужев Е.В., Борисов А.Н., Алексеев А.В., Меркурьев Е.В. и д.р.). Нечеткая логика позволяет заметно упростить формализацию требований, но часто приводит к построению расписания, имеющего не лучшие характеристики в результате перехода от «жестких» требований к более «мягким». В настоящее время для решения задачи составления расписания применяется ещ один новый подход – нейронные сети (Пилиньский М., Рутковская Д.). Важнейшим недостатком применения этого подхода является сложность выбора начального состояния нейронной сети. В последние годы особое распространение получили исследования методов эволюционного поиска (Ерунов В.П., Морковин И.И., Каширина И.Л., Низамова Г.Ф., Коробкин А.А.). Применение методов эволюционного поиска приводит к получению хороших результатов, однако имеет место высокая вычислительная трудомкость и относительная неэффективность на заключительных этапах эволюции. В работе Низамовой Г.Ф. используются методы системного анализа, генетических алгоритмов и теории важности критериев. На основании анализа и выявленных недостатков существующих разработок в настоящей работе проводится исследование, направленное на решение задачи составления расписания с использованием агрегированного генетического алгоритма, для чего проводится формализация некоторых составляющих учебного процесса.

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

1. Разработать модели составления расписания занятий в вузе и квазиоптимального варианта.

2. Построить и исследовать структурные модели информационного процесса составления расписания с помощью Rational Rose.

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

Объект исследования – модели составления расписания занятий в вузах, предмет исследования – генетические алгоритмы составления расписания занятий в вузах Ирака (г. Диала).

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

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

1. Модель для задачи составления расписания занятий, отличительной особенностью которой является агрегированное представление объектов расписания.

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

3. Структурные модели системы информационного процесса составления расписания, основанные на СASE технологии Rational Rose, отличительной особенностью которых является работа с агрегированными объектами.

4. Специальное программное обеспечение, отличающееся работой с агрегированными объектами и геном «конфликтов», сокращающим время составления расписания на ЭВМ.

Теоретическая и практическая ценность В работе проведена формализация организационных компонентов учебного процесса: составление расписания и построение структурных моделей системы. Практическая ценность работы заключается в возможности использования разработанного программного обеспечения для принятия решений при построении квазиоптимального расписания учебных занятий и его применение для получения квазиоптимального расписания в вузе г. Диала Ирака. По результатам работы получено свидетельство о регистрации программного комплекса на ЭВМ «Разработка системы составления расписания ВУЗа Ирака» в Федеральном институте промышленной собственности (ФИПС) № 20126118248 от 11 сентября 2012г.

Апробация работы Основные результаты, представленные в диссертационной работе, докладывались и обсуждались на Международной конференции «Актуальные проблемы прикладной математики, информатики и механики»

(Воронеж, 2012), на XIII межд. научно-технической конф. «Кибернетика и высокие технологии XXI века» (Воронеж 2012), на Воронежской весенней математической школе «Понтрягинские чтения» (Воронеж 2010, 2012), на научных сессиях Воронежского государственного университета, (Воронеж, 2011, 2012); на Двенадцатом всероссийском симпозиуме по прикладной и промышленной математике (Москва, 2011 г.), на семинаре каф.

«Компьютерное и математическое моделирование» Тамбовского государственного университета (Тамбов, 2013 г.).

Публикации Результаты диссертации опубликованы в 9 работах. Из совместных работ в диссертацию вошли только результаты, принадлежащие лично диссертанту. Диссертантом получена модель с ограничениями составления расписания, генетический алгоритм с агрегированными объектами, разработаны структура популяции и каждой особи, операторы кроссинговера и мутации, разработаны структурные модели информационного процесса составления расписания, разработан программный комплекс и проведено его применение к вузу Ирака. Списку ВАК соответствуют работы [1-2].

Структура и объм диссертации Диссертация состоит из введения, 4 глав, разбитых на пункты, заключения, списка используемой литературы из 130 наименований и приложения. Общий объем диссертации – 118 страниц. Работа содержит рисунков, 2 диаграммы и 14 таблиц.

Область исследований.

Диссертационная работа соответствует следующим пунктам шифра специальности 05.13.17 – Теоретические основы информатики:

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

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

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

На защиту выносятся:

1. Модель составления расписания занятий в вузе и генетический алгоритм, организующий поиск его квазиоптимального варианта.

2. Структурные модели описания информационного процесса составления расписания, основанные на СASE технологии Rational Rose, отличительной особенностью которых является работа с агрегированными объектами.

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

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

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

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

Для описания j аудитории расположенной в корпусе под номером s и имеющей тип type вводится в рассмотрение трехкомпонентный кортеж использование сквозной нумерации временных интервалов в течение семестра; временные интервалы описываются множеством T, каждый элемент которого представляет собой трехкомпонентный кортеж вида где t k – номер временного интервала, t k 1, N idps ;

t k 1, N dpw ; t k – временной интервал в течение одного дня, t k 1, N cpd.

Здесь N idps – количество временных интервалов в неделе, N dpw – число учебных дней в неделе, N cpd – число временных интервалов в течение одного учебного дня.

Следующим рассматриваемым объектом является блок (B) занятий, который состоит из следующих объектов:

D – множество дисциплин;

G – множество студенческих групп;

P – множество преподавателей;

С учетом связи между этими объектами, образуется новый объект – «занятие». Объект «занятие» представляет собой агрегированный объект, который можно представить в виде множества векторов следующей структуры:

где Bi – элемент множества блок занятий B(i 1, N блоков ) ;

N блоков – количество блоков занятий;

Bid – дисциплина, преподаваемая в блоке;

Big – группа, у которой проводится занятие;

Bip – параметр, определяющий длительность блока;

Biy – параметр определения вида занятия.

Рассмотренная выше операция агрегирования применительно к объектам D и G возможна благодаря наличию между ними связи.

Пусть A ai – множество аудиторий; T t k – множество временных интервалов; B b j – множество блоков занятий, где i A – код аудитории, назначенный блоку занятий bi B ; ti T – код временного интервала, назначенный первому занятию из блока занятий bi B.

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

Стандартные ограничения формализуются следующим образом:

1. Отсутствие совпадений занятий для аудиторий:

где B tk – множество блоков занятий, проводимых во время временного интервала t k.

2. Отсутствие совпадений занятий для преподавателей:

где B j – множество блоков занятий, проводимых во время временного интервала t k.

3. Отсутствие «накладок» для учебных групп:

где B g n – множество блоков занятий, в которых присутствует группа g n, а B j – множество блоков занятий, проводящихся во время временного интервала t k.

4. Соответствие типа аудитории проводимому занятию:

5. Ограничение, налагаемое на количество временных интервалов, проводимых в течение одного учебного дня:

где Z z1, z 2,..., z Nдней – множество учебных дней. Каждый элемент описанного множества, определяется следующим образом:

Помимо стандартных ограничений, накладываемых на расписание, рассмотрим следующие дополнительные ограничения в вузах Ирака:

1. Продолжительность рабочей недели – 5 дней.

2. Максимальное количество занятий – 3 пары в день для каждой группы студентов любого курса.

3. Расписание составляется только для одной недели занятий в течение всего семестра, деления на «числитель/знаменатель» отсутствует;

4. Все занятия проходят в одну смену.

5. Гендерные условия (занятия у студентов мужского пола проходят отдельно от студентов женского пола, для которых аудитории выделяются в отдельном крыле корпуса).

К наиболее значимым желаемым требованиям относятся:

1. Пожелания преподавательского состава.

2. Минимизация количества «окон» у преподавателей.

3. Требование равномерности занятий.

На основе (1) – (3) для получения расписания необходимо получить вектора (9):

С учетом (9), а также при соблюдении ограничений (4) – (8) требуется найти вариант выбора векторов A, T, B, удовлетворяющий ограничениям (4) – (8).

Целевая функция данной задачи имеет вид:

где K (, t, b) ci wi (, t, b), сi – значение штрафного коэффициента за невыполнение i требования, а wi – оценка степени невыполнения i желаемого требования. Каждое нарушение ограничения увеличивает значение целевой функции в соответствии с коэффициентом значимости требования k _ og i. Если ограничения не выполняются или не выполняются желаемые требования, то расписание называется конфликтным.

Для решения задачи (4-10) выбирается стандартная схема генетического алгоритма с конкретным наполнением для этой задачи.

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

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

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

На рис. 1 изображен индивид, который состоит из 3 хромосом – Рис. 1. Схема особи аудитории, времени и блока. Каждая хромосома имеет массив длиной 1-N генов. Эти массивы хранят информацию о хромосомах.

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

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

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

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

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

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

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

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

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

В третьей главе содержится описание построения структурных моделей предметной области и описания информационных процессов при составлении расписания. При проектировании программного комплекса информационной системы в образовании были использованы возможности унифицированного языка моделирования UML и программный пакет Rational Rose для визуального объектно-ориентированного моделирования систем на основе графических диаграмм языка UML.

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

Рис.5. Диаграмма сценариев проектируемой системы Диаграмма классов для системы состоит из трех диаграмм:

Диаграмма классов для объектов базы данных из 7 классов;

Диаграмма классов для объектов генетического алгоритма из Диаграмма классов для разработки интерфейса.

Рис.6. Диаграмма классов для объектов базы данных Рис.7 Диаграмма классов для разработки интерфейса

CHROMOSOME TIME

+GetAuditoryChromosome(): CHROMOSOME AUDITORY

CHROMOSOME AUDITORY

-individuals: List +initialize1(List individuals): void +iterations(): double +crossingover(List IndSListC) +mutation(List indS) SameAuditorySameTimeMoreBlock -AllTimes(): int[] -blocksall(): Block[] -Auditorytype1(): int[] +ForWordMutation(Individual ind): void +calcRule(Individual ind): int -Random R В четвертой главе описана структура разработанного программного комплекса. Описано взаимодействие основных функциональных блоков и обосновано использование связки C# и СУБД SQL SERVER. Интерфейс программного комплекса имеет вид (рис.9):

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

расписание составлено для одного факультета, на один семестр, где каждая учебная неделя состояла из пяти дней по 3 пары занятий в день. Для его составления были задействованы 8 групп, 18 преподавателей, 53 предмета, аудиторий из университета г. Диала Ирака.

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

На рис. 10 представлен результат работы алгоритма – расписание. Оно состоит из даты, времени, групп, преподавателей, предметов, аудиторий и типа занятий.

Отражена структурная схема взаимодействия основных модулей (рис.11).

Рис.11. Структурная схема взаимодействия основных модулей Структура основного модуля работы с базой данных с применением языка C# и СУБД SQL SERVER имеет следующий вид (рис.12):

Составление квазиоптимального расписания занятий вуза Ирака находится в файле ShowTimeTable.cs Синтез расписания производится в результате исполнения сценария CreateNewTimeTable.cs Заключение отражает основные результаты, полученные в ходе выполнения диссертационной работы.

Основным результатом настоящей диссертационной работы является модель формализация задачи составления расписания в вузе. Среди наиболее важных результатов можно выделить:

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

2. Разработку модели составления расписания с агрегированными объектами.

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи из списка изданий, рекомендованных ВАК 1. Асвад Фирас М. Разработка информационной системы вуза с применением методов искусственного интеллекта /Ф.М. Асвад //Вестник Воронежского государственного технического университета.

Технические науки, 2011. Т.7, №5. с. 129–130.

2. Асвад Фирас М. Составление расписания учебных занятий на основе генетического алгоритма / И.Ф.Астахова, Фирас Асвад М. // Вестник Воронежского госуниверситета. Системный анализ и информационные технологии, 2013. – № 2. – с. 93–99.

Асвад Фирас. М. Схема работы генетического алгоритма для составления расписания занятий / И.Ф.Астахова, М.Асвад Фирас // Современные методы теории краевых задач: Мат. Воронежской весенней мат. школы «Понтрягинские чтения ХХIV». – Воронеж:

Издательско-полиграфический центр ВГУ, 2013. – С. 19–21.

Асвад Фирас М. Разработка информационной системы учебного заведения в Ираке/ И.Ф. Астахова И.Ф., Асвад Ф. М. // Современные методы теории краевых задач: Мат. Воронежской весенней мат. школы «Понтрягинские чтения XXI». – Воронеж: Издательскополиграфический центр Воронежского государственного университета, 2010. – С. 20-22.

Асвад Фирас М. Разработка базы данных информационной системы составления расписания ВУЗА Ирака / И.Ф.Астахова, Фирас. М. Асвад // Современные методы теории краевых задач: Мат. Воронежской мат.

школы «Понтрягинские чтения- XXIII». – Воронеж: Издательскополиграфический центр ВГУ, 2012. – С. 18–21.

Асвад Фирас М.: Применение генетического алгоритма для составления расписания./ И.Ф.Астахова, Фирас. М. Асвад// Кибернетика и высокие технологии XXI века: XIII Международная научно-техническая конференция. – Воронеж, 2012. – Т. 1. – С. 120– Асвад Фирас. М.: Разработка системы составления расписания вуза. / М. Асвад Фирас // Обозрение прикладной и промышленной математики. Двенадцатый Всероссийский симпозиум по прикладной и промышленной математике: тезисы межд. конф. – М. : ООО Редакция журнала «ОПиПМ», 2011. – Т. 18, № 4. – С. 621.

Асвад Фирас М.: Разработка моделей проектирования для информационной системы построения расписания. / М.Асвад Фирас // Актуальные проблемы прикладной математики, информатики и механики: Сборник трудов межд. конф. – Воронеж, 2012.Часть 2. – Свидетельство о государственной регистрации программы для ЭВМ № 2012618248. Российская Федерация. Разработка системы составления расписания ВУЗа Ирака / Астахова И.Ф., Фирас А.М..; заявитель и патентообладатель Воронежский государственный университет (RU). – № 2012615867; заявл. 12.06.2012; опубл. 11.09.2012. – 1 с.