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

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

Левад Фирас М.

-""о

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

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

АВТОРЕФЕРАТ

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

г і иоя 2013

005539052

Воронеж-2013

005539052

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

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

доктор технических наук, профессор

Официальные оппоненты: Арзамасцев Александр Анатольевич,

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

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

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

государственный университет»

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

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

Автореферат разослан «_»_2013 года.

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

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

Актуальность темы

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

Цель работы и основные задачи

Целью диссертационной работы является разработка и исследование моделей формализации составления расписания занятий с использованием

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

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

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

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

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

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

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

Научная новизна

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

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

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

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

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

Теоретическая и практическая ценность

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

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

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

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

Публикации

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

Структура и объём диссертации

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

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

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

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

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

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

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

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

2. Структурные модели описания информационного процесса составления расписания, основанные на CASE технологии Rational

Rose, отличительной особенностью которых является работа с агрегированными объектами.

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

Содержание работы

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

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

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

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

Для описания j аудитории расположенной в v корпусе под номером s и имеющей тип type вводится в рассмотрение трехкомпонентный кортеж A = {aj},aj=(a4,a*,al»e). (1)

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

ч=№лл\ _ (2)

где t'k - номер временного интервала, if = 1, Nidps; tk - номер дня, tf = l,Ndpw; t'k- временной интервал в течение одного дня, /{ = 1, Ncpd. Здесь Nidps- количество временных интервалов в неделе, Ndpw - число учебных дней в неделе, Ncpd- число временных интервалов в течение

одного учебного дня.

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

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

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

Р - множество преподавателей;

К-тип блока.

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

в = {в,},в={в;,в',в!,в!), __(3)

где Вг элемент множества блок занятий В(1 = 1, Мг-а1)К1,„); N блоков - количество блоков занятий;

дисциплина, преподаваемая в блоке; В?~ группа, у которой проводится занятие; В,р-параметр, определяющий длительность блока; В?- параметр определения вида занятия.

Рассмотренная выше операция агрегирования применительно к объектам О и О возможна благодаря наличию между ними связи. Пусть А = {а1} - множество аудиторий; Т = {гк} - множество временных интервалов; Я= ) - множество блоков занятий, где е А - код аудитории, назначенный блоку занятий Ь, е В; е Т - код временного интервала, назначенный первому занятию из блока занятий 6, е В.

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

Стандартные ограничения формализуются следующим образом: 1. Отсутствие совпадений занятий для аудиторий:

) а, е А 1) е Т(З^Ьк (а, =ак )л (Ьк € В'')) V

< ' (4)

{-aЬk^a,=ak)*{ЪkeB,'))

где В'к— множество блоков занятий, проводимых во время временного интервала / к.

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

)р,еР /, Е Т(Э^Ък (Л = Рк) А (Ьк е В'')) V

где В1'- множество блоков занятий, проводимых во время временного интервала (к.

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

^Ь! <Ые В^ 8п &с>1к ВТ , (6)

где ВКп - множество блоков занятий, в которых присутствует группа gn, а

в'1- множество блоков занятий, проводящихся во время временного интервала 1к.

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

УЬ.еВ а,еЛ*г. (7)

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

< мпар т^ е /£Щ:т,8„) =т е 2,8я <= с , (8)

где 2 = \г,,2-,,...,2к } - множество учебных дней. Каждый элемент

I ' дней '

описанного множества, определяется следующим образом:

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

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

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

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

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

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

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

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

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

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

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

Г = (9)

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

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

(10)

/—1 Ы

' 1 • • ■1 кош чество ограни чений

N

где К = <р(а,1,Ь) = £ с, 1С, (а,/, 6), с, - значение штрафного коэффициента за

1=1

невыполнение / требования, а - оценка степени невыполнения / желаемого требования. Каждое нарушение ограничения увеличивает значение целевой функции в соответствии с коэффициентом значимости требования k_ogj. Если ограничения не выполняются или не выполняются желаемые требования, то расписание называется конфликтным.

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

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

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

На рис. 1 изображен индивид, который состоит из 3 хромосом —

образом формируется исходная

С

Хромосома - родитель №2

пусть разыграны гены, после скрещивания

Хромосома - потомок№1

<5 X

\и <_> о.

По,

Рис. 1. Схема особи

Юо

ОЭООСЮО с

(' )000О00 О о

©0ОО0ОО<

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

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

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

X:

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

происходят с двумя хромосомами времени и

С ...................и..............аудиторий в особи. Третья хромосома

переформируется в зависимости от этих двух. Четвертым оператором является О О о оператор мутации (рис.3).Выбираются два гена в двух хромосомах времени и аудиторий и меняются местами. Третья хромосома переформируется в зависимости от этих двух. На пятом этапе проверяется ген «конфликтов» для хромосом аудиторий и временных интервалов.

Рис. 3 Схема работы оператора мутации.

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

одинаковые временные интервалы, 'ТУ7X1Х"к> отвечающие одной аудитории, то из базы данных из массива временных 6узУ,оу7л интервалов выбирается свободный временной интервал с другим номером и незанятый в этой аудитории, ген «конфликтов» уменьшается на единицу. Ген «конфликтов» позволяет сократить СЕХ±ХЕХ®) время проведения вычислений на порядок, то есть он ускоряет процесс .Л/^^ХлУ сходимости алгоритма и получения .„„„,.„»4,„„ квазиоптимального решения, .к.

«конфликт» разрешается на каждом Рис.4. Проверка значений гена «конфликтов» шаге (рис.4).

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

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

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

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

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

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

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

Рис.5. Диаграмма сценариев проектируемой системы

Диаграмма классов для системы состоит из трех диаграмм:

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

• Диаграмма классов для объектов генетического алгоритма из 12 классов;

Одна из основных диаграмм Use Case Diagram (диаграмма сценариев), которая позволяет создать список операций, которые выполняет система. Эта диаграмма - это описание сценария поведения системы, которому следуют действующие лица (рис.5). В данной системе можно выделить одного актера -пользователя, который отдает команды системе.

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

Вкх*

-Шо± ¡еЛ -М&оир: Й

-Нес!: ¡1«

-Шуей: ¡п1

•1йТуреС1а$5: •Мепйу: М

¡п! вЛ *деЙ<Йгоир(): ¡п( где(ИТуреОа550: ¡Й тдеЦ&Л)«© ¡(Л ♦деНгЛепайО: (а! ¿ВкхЦМ ИД ¡п11с_С, ¡«1111, ¡п{ 1е_5иЬ, Ют

Сгеа1е Ней Типе ТаЫе

^екШеТаИеО^

0а1аВа«_Не1рег

тЯакккп гзпй -сп: ЭДСолпкйоп -Зпййд

Нп51йпсе: 0аУже_Не1ра' -8сск Ыоск£ = гай;

•1)8&Ьв$е_Не1рег()

|д ЯлпдЗчкоттак}): ин Ш

8ой0 :кйю»,№кйав):уа(1 г1п5гЛТоГнг.еТайе(1пй«1из1 ше1): юМ •МйеШшпТтеТзЫеО: *ок!

KfiowLeswnsfoffdthGioup.es

-ЙЬ: йуйамМИэСМвЛ

-&0ирР«Й0(к!!л{|^0ир):

Квша1е55<нвРм£а<кеси5

0..1 -

Немп^аЖесЮ: (Моояу-снЛ, и«М» ДОЬВДМВДиМпЬ *ип1п1ийБтгРо(1ес1АйО: Ойюп»У<Й1 Ц4<и1»

-КмиА1!Ш<т!егейТ|гпеМуге)Шр! №): 1М<т!>

*Ь^ТТт#ЫееМ11(): ШкдаусЦ |.а<1гЛ»

НаикмпЛтеАшйшШоге о..К

-оЬ: ¿уйаишОайОмай KnovfTiiitesfortwreyDay.es

+5еМсВосШ<Ште10:шШ •Ф: йуйадаМЗайСогёей

-Ш1те5РогОау{1п1№ау): ия<тГ>

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

С&М«1«11те1а1>1е

I■&>. <1

) «иг-лмя икммде* УМ4

< 11ир»Яй»иЬика11_<:(1<.кО- той! : <им£ф 1химЮч* кк ;. ®> «у тьО'зтяукУЛ пШ

' СюШКЛпФШаЫМШасп.. . : йапШ^ «аК

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

-HnituMBIockU blockd): -KSetTimeGenesC): Gen« «ewmutetiontimeO: wk)

•void m*ialae<)

«3etTimeCbromosome(): CHROMOSOME TIME •KXAuditoryCKromosomeO: CHROMOSOME AUDITORY *fitnessFunctK>n(): double

-KomputelntnessO: vo«d

ze(Eiock[] blocks)

26(611X4] blockd):

*nibabrel(Ust<IndMdual> individuals): •Hlerabons(): double

■mewPopulation(List<Indivldual> okfPopul» +cros»ngov«f(Lisl<!ndMdual> IndSUstC)

*niut30on(Lrsl< Individual* indS)

-AITimesO:

-Auditorytype2(): mlfl ■blocksalK): SockJ]

-AuditoiytypelO: mtf) +forWofdMutation(lndividu

-blocksa»<): B)ock[] -AITimesForOay<int IdDay) •*cakRu!e(!ndivtdual md) -ABTknes(): тЩ +ForWordMulabon(IndMdua

utabon(lndMdual ind): void

-йг&оирО: Dictionary« int. inlfl:

AIITimesO: intj]

RoundTimeFromTnterTimeForLect(int (

OnePartKubrPerDayFbrEachGoupl

dayl, day2, day3, day4, dayS: Block

-Ыоскьа«(): Block* ] •OiiGroup(): Dictionarycint, 1пЦ)> -ADTmesO: inlj]

-ОауАп(ГПте(): Dicbonarycint, Usl<mt>> tf 0fW0'dMutab0n{lndrvidual ind): void

Рис.8 Диаграмма классов для генетического алгоритма

В четвертой главе описана структура разработанного программного комплекса. Описано взаимодействие основных функциональных блоков и обосновано использование связки С# и СУБД SQL SERVER. Интерфейс

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

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

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

Рис.10. Готовое расписание

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

рв 111(1 1

| Sal іявг / я \ , ' «„«I db

.............. т и 1 I

1 ІШГШІІІЙОЗІ Populiti.n 1 j Interlace Of Data 1

St lectio« ^ | Interface Of Rules J

^ Cnssowr I [interface Of Check

i Seleeti.»

1 CkoosUg Tbe Best I tivUaab J

Рис. 11. Структурная схема взаимодействия основных модулей

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

Рис. 12. Базовый модуль для работы с БД

Составление квазиоптимального расписания занятий вуза Ирака находится в файле ShowTirneTable.cs Синтез расписания производится в результате исполнения сценария CreateNewTimeTable.cs

Заключение отражает основные результаты, полученные в ходе выполнения диссертационной работы.

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи из списка изданий, рекомендованных ВАК

1. Асвад Фирас М. Разработка информационной системы вуза с применением методов искусственного интеллекта /Ф.М. Асвад //Вестник Воронежского государственного технического университета. Технические науки, 2011. - Т.7 , №5. - с. 129-130.

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

Другие публикации

3. Асвад Фирас. М. Схема работы генетического алгоритма для составления расписания занятий / И.Ф.Астахова, М.Асвад Фирас // Современные методы теории краевых задач: Мат. Воронежской весенней мат. школы «Понтрягинские чтения XXIV». - Воронеж: Издательско-полиграфический центр ВГУ, 2013. - С. 19-21.

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

5. Асвад Фирас М. Разработка базы данных информационной системы составления расписания ВУЗА Ирака / И.Ф.Астахова, Фирас. М. Асвад // Современные методы теории краевых задач: Мат. Воронежской мат. школы «Понтрягинские чтения- XXIII». - Воронеж: Издательско-полиграфический центр ВГУ, 2012. - С. 18-21.

6. Асвад Фирас М.: Применение генетического алгоритма для составления расписания./ И.Ф.Астахова, Фирас. М. Асвад// Кибернетика и высокие технологии XXI века: XIII Международная научно-техническая конференция. - Воронеж, 2012. - Т. 1. - С. 120— 124.

7. Асвад Фирас. М.: Разработка системы составления расписания вуза. / М. Асвад Фирас // Обозрение прикладной и промышленной математики. Двенадцатый Всероссийский симпозиум по прикладной и промышленной математике: тезисы межд. конф. - М.: ООО Редакция журнала «ОПиПМ», 2011. - Т. 18, № 4. - С. 621.

8. Асвад Фирас М.: Разработка моделей проектирования для информационной системы построения расписания. / М.Асвад Фирас // Актуальные проблемы прикладной математики, информатики и механики: Сборник трудов межд. конф. - Воронеж, 2012.Часть 2. -С. 18-21.

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

Подписано в печать 08.11.13. Формат 60*84 '/,6. Усл. печ. л. 0,93.

Тираж 100 экз. Заказ 1148.

Отпечатано с готового оригинал-макета в типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

>

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

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

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

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

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

Воронеж-2013

ОГЛАВЛЕНИЕ

ОГЛАВЛЕНИЕ 2

ВВЕДЕНИЕ 4

Глава 1. Анализ моделей и методов составления расписания 9 учебных занятий

1.1 Информационные технологии в сфере образования 9

1.1.1 Анализ существующих программных комплексов решения 10 задачи составления расписания

1.1.2 Основные подходы к решению задачи составления расписания 15

1.2 Задача выбора и составление расписания 19

1.2.1 Общие вопросы, связанные с теорией расписаний 20

1.3 Анализ методологий и современных средств проектирования 21 программных комплексов

1.3.1 Структурный подход к разработке программного обеспечения 21

1.3.2 Объектный подход к разработке программного обеспечения 23

1.3.3 Объединение структурного и объектного подхода в новом 27 поколении CASE-средств

1.4 Выводы, цель и задачи исследования 30 Глава И. Решение задачи составления расписания занятий ВУЗа, 32 с использованием генетических алгоритмов

2.1 Постановка математической модели задачи составления 32 расписания

2.2 Систематизация исходной информации 43

2.3 Описание разработанного агрегативного генетического 46 алгоритма

2.4 Результаты практического применения разработанной модели 56 синтеза учебного плана

2.5 Выводы по второй главе 60 Глава 3 Структура программного комплекса информационной 61 системы в образовании

3.1 Графические диаграммы UML 61

3.1.1 Определениетребований к системе при помощи диаграммы Use 64 Case

3.1.2 Machine Diagram (диаграммы состояний). Создание модели 66 поведения системы при помощи диаграммы Statechart

3.1.3 Описание взаимодействия при помощи Sequence diagram 68

3.1.4 Диаграмма классов 74

3.2 Информационные потоки данных 89

3.2.1 Схема работы алгоритма 89

3.2.2 Схема работы программы 92

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

Глава 4. Использование программного комплекса для решения задачи 95

4.1 Средства реализации 95

4.2 Требования к аппаратному и программному обеспечению 95

4.3 Описание программного комплекса 96

4.4 Работа с программным комплексом 96

4.4.1 Описание создания расписания.( Create Time Table) 107

4.4.2 Невидимые компоненты С # для связи программы с БД 111

4.5 Show Time Table : Результаты работы 112

4.6 Структура проекта 114

4.7 Подключение к БД 116

4.8 Описание программного продукта 117

4.9 Выводы по четвертой главе 119

ЗАКЛЮЧЕНИЕ 120

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ ЛИТЕРАТУРЫ 121

ПРИЛОЖЕНИЕ 131

ВВЕДЕНИЕ

Актуальность темы

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

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

Цель работы и основные задачи

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

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

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

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

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

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

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

объектно-ориентированного программирования и объектно-ориентированного проектирования.

Научная новизна

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

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

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

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

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

Теоретическая и практическая ценность

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

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

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

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

Публикации

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

Структура и объём диссертации

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

приложения. Общий объем диссертации - 118 страниц. Работа содержит 57 рисунков, 2 диаграммы и 14 таблиц.

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

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

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

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

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

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

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

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

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

Глава 1. Анализ моделей и методов составления расписания учебных занятий

1.1 Информационные технологии в сфере образования

Информатизация сферы образования - одно из приоритетных направлений процесса развития общества. Задача внедрения новых информационных технологий в сферу образования рассматривается в рамках проекта федеральной целевой программы "Развитие единой образовательной информационной среды на 2010-2015 годы" и считается одной из главных. Она включает в себя создание новых образовательных программ на основе информационных технологий, развитие сети электронных библиотек, модернизация и развитие существующей сетевой инфраструктуры и др. Повышение эффективности обучающего процесса невозможно достичь без использования автоматизированных рабочих мест для решения задач, возникающих в ВУЗах. К таким задачам относятся учет персонала, материально-технических ресурсов, управление документацией, распределение преподавательской нагрузки и т.д. Особо следует отметить важность проблемы создания информационного обеспечения для организационных процессов учебных заведений, от которого в определенной степени зависит эффективность использования научно—педагогического потенциала. В это направление включены задачи назначения и распределения учебной нагрузки студентов и преподавателей - составление расписания занятий и экзаменов. Эта составляющая учебного процесса регламентирует трудовой ритм и влияет на творческую отдачу преподавателей и студентов, поэтому ее можно рассматривать как фактор оптимизации использования ограниченных трудовых ресурсов. Технологию же разработки расписания следует воспринимать не

только как трудоемкий технический процесс или объект автоматизации с использованием ЭВМ, но и как процесс оптимального управления. Таким образом, задачи получения оптимальных расписаний занятий и экзаменов имеют очевидный социальный и экономический эффект [26-27].

1.1.1 Анализ существующих программных комплексов решения задачи составления расписания

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

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

Рассмотрим возможности наиболее популярных на российском рынке программных продуктов, реализующих решение задачи составления расписания [26, 27]:

aSc Timetables (IBN). Программа разработана для всех типов начальных и средних учебных заведений. Среди основных характеристик разработчики выделяют: оптимальное использование кабинетов и других школьных

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

Построение же расписания в ВУЗах этой программой не предусмотрено.

Система A VTOR-2+. Предназначена для составления расписаний занятий и сопровождения их в течение всего учебного года. AVTOR-2+ - универсальная система. Есть несколько версий программы, рассчитанные на любые учебные заведения. AVTOR-2+ имеет приятный дизайн и дружественный интерфейс. Программа достаточно проста в освоении. Имеется подробное руководство, в котором описаны все возможности и способы работы с программой. Программа работает на любых IBM-совместимых компьютерах, начиная с 486DX с оперативной памятью 4Mb (и выше), занимает около 1 Mb на жестком диске. Операционная система: MS DOS, либо WINDOWS 95/98.

Время работы зависит от размера учебного заведения и мощности компьютера.

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

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

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

Ограничения функциональности "Методиста": многосменные расписания ограничены максимальным кол-вом уро�