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

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

НИЗАМОВА Гузель Фанисовна

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

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Уфа-2006

Работа выполнена на кафедре информатики Уфимского государственного авиационного технического университета

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

профессор Ю.С. Кабальное

Официальные оппоненты: доктор физ.-мат. наук,

профессор В.П. Житников

кандидат технических наук, доцент Ю.И. Зозуля

Ведущее предприятие: Башкирский государственный

педагогический университет им. Акмуллы

диссертационного совета К-212.288.01 в Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К. Маркса, 12.

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

Защита состоится «

»

2006 г. в_часов на заседании

Автореферат разослан «

»

2006 г.

Ученый секретарь диссертационного совет! кандидат физ.-мат. наук

Р. А. Гараев

аоо

гБъз^ 1

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

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

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

а) качество обучения;

б) экономическая эффективность обучения;

в) комфортность учебы студентов и работы профессорско-преподавательского состава (учет требуемых психофизиологических аспектов обучения) и т.д.

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

а) учесть множество требований и условий, предъявляемых к расписанию;

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

в) реализовать критериальный или оптимизационный подход к составлению расписания;

г) существенно уменьшить временные затраты на составление расписания.

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

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

а) отсутствует гарантия получения приемлемого решения задачи;

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

Грос. национальная"! библиотека i

С.-Петербург

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

г) слабо учитываются существующие связи между объектами целочисленной оптимизации;

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

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

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

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

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

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

Для достижения цели работы поставлены следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Результаты экспериментальной проверки предложенных алгоритмов

(на примере факультета ИРТ) показали существенное (в 2-3 раза) i

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

В первой главе описывается структурная модель представления исходной информации для составления расписания. Исходную информацию предложено описывать в виде следующих множеств: множество аудиторий А, множество временных интервалов Г возможного проведения занятий и множество блоков занятий 2. Последнее множество, по сути, представляет собой агрегированный объект - блок занятий (рис. 1).

Рис. 1. Структура агрегированного объекта "блок занятий"

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

Теоретико-множественное описание множеств А, Т,

л>РЛ

1 )A = {aj}, aj=[avj, asp afej = \,Nayd,

где v - номер учебного корпуса, s - номер аудитории, type - тип аудитории (может принимать значения "большая", "средняя", "малая", "лабораторная").

2> Г-{/*>, t«k, t{

где t™ — номер недели, t™ =l,Nwps ; tf — номер дня недели, tf =1 ,Ndpw ;

— номер учебной пары в течение дня, = • Здесь Л^^.— число

учебных недель в семестре, Ы— число учебных дней в неделе, Лгсрс{ — число учебных пар в течение одного учебного дня.

-Р -Л 5 е к 1№ с I а

I 7 I ' / ' I' 11 I ' I 5 / * / > I

где / — некоторый элемент множества блоков занятий Ъ (г = 1,^блоков )!

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

г? — преподаватель, ведущий данный блок занятий;

гу — дисциплина, преподаваемая в данном блоке занятий;

г?— учебная группа или поток из нескольких учебных групп (из множества групп б или множества потоков £), для которой проводятся занятия данного блока, г? е С V г? € 5;

е {О, 1} — признак поточного занятия: если г/ = 1, то данный блок содержит поточные занятия и в таком случае компонента г? е Б) если же г/ = 0, то данный блок не является поточным занятием и в таком случае компонента г? 6О;

_e_.fl Л .......... ............. _ -е 1

г, е, 1| — признак полугруппы: если г/ =-, то данный блок содержит занятия, в которых участвует только половина группы; если же

г? = 1, то данный блок не является поточным занятием, и в таком случае компонента т.% е б;

г.

г^ — длительность блока (число занятий в данном блоке занятий);

г™ е {1, 2} — интенсивность занятий в блоке: если г™ = 1, то занятия в

данном блоке проводятся 1 раз в неделю; если же г]" = 2, то занятия в данном блоке проводятся 1 раз в 2 недели;

21 — длина одного занятия (число учебных пар в одном занятии данного блока);

• г\ — параметр, определяющий вид занятия;

г? — код допустимого подмножества аудиторий.

^ Тогда расписание учебных занятий можно полностью определить двумя

векторами аит:

а = (аьа2>...,а^л№ов)

т^Сч.т2,-^Мблоков) '

где а,- е А — код аудитории, назначенный циклу занятий 2/ е Ъ, т,- е Т — код пары, назначенной первому занятию из цикла занятий

8 , Для случая трех исходных множеств задача составления расписания была

сформулирована следующим образом.

Для заданного множества объектов А, Т, 2 требуется найти вариант

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

потерь "качества" расписания

N

Р = Аа,х)=Тсм(а,т), (1) /=1

где щ— значение коэффициента штрафа за невыполнение 1-го частного критерия, с,-— оценка, определяющая степень невыполнения /-го частного критерия.

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

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

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

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

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

Особь (вариант расписания)

а)

ч

----^-

1-я хромосома"'" 2-яхромосома

гены - блоки занятий

Рис. 2. Структура особи (варианта расписания)

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

г, г, ... г, ... г,

а1

г, г,

v - г^ |... г,

а>

г, г, ... г, ...

п

г, - гх

¡к

¿2

Рис. 3. Схема скрещивания двух особей

Первая особь

Вторая особь

Оператор мутации (рис. 4) с некоторой вероятностью изменяет значение нескольких генов в хромосомах некоторой "новой" особи на другие значения, входящие в число допустимых значений данного гена. Например, в результате мутации /-того гена первой хромосомы, где /— определяет некоторое лекционное занятие, а значением этого гена (его информационным наполнением) является номер аудитории, предназначенной для проведения лекционных занятий, /-тому гену будет присвоен номер аудитории, случайно выбранный из подмножества лекционных аудиторий. Аналогично для второй хромосомы в результате выполнения оператора мутации /-тому гену будет присвоен номер учебной пары из допустимого подмножества учебных пар, предназначенных для проведения именно данного вида занятия.

Поро.чл

хр

Рис. 4. Схема мутации особей

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

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

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

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

~Р1

№

п п

I Су 2 йд

/=1 П---Ы-

(2)

т

где р; — -, Ч1=-1-1-, 1,Р/=1. £<?/=1-

т п т п .J

I I Су £ X с1у } }

у=11=1 7=1 М

Сгу - числовая оценка важности у'-го критерия, определенная г'-м

экспертом,

¿у - числовая оценка достоверности у'-го критерия, определенная 1-тым

экспертом,

п - количество экспертов, т - количество критериев.

Предложена скалярная форма представления данного векторного коэффициента (3):

w/ (3)

т

где к1=/{р1,ц/), £>,- = 1, /

к{ - коэффициент коррекции переменной /?,-, описываемой лингвистической переменной,

/()- функция принадлежности, отражающая принятую систему нечетких правил коррекции коэффициента важности р[, учитывающих степень полноты щ имеющейся у экспертов информации.

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

Рис. 5. Схема алгоритма определения коэффициентов коррекции с использованием лингвистической переменной

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

критерии

диспетчер расписания

Рис. 6. Диаграмма первого уровня интеллектуальной системы составления

расписания

Кафедры

ГО кафедры

Преподаватели

ID преподавателя Фамилия

<4 и«я

Отчество ID кафедры (FK) должность

Блоки >аштш

ID блока ззяетця Й) преподавателя (FK) id дисциплины (fk) ID потока (FK) ГО вида занятая (FK) количество занятой и«генсн8ность длительность занятия ID типа подходящих аудиторий (F^ 1

Расписание ID блока занятия (FK) ID ароиени занятий (гК I tD аудитории (ПО

Факультеты

ID группы (Fl^ Учебные группы

tO факультета

факульат

1-

ID группы.

ID факультета (FK) факультет шифр группы количество студентов

Типы аудиторий ID аудитории

ID -nina корпус номер Ю типа (FKJ

тип аудитории

Время проведения занятии

ID еремонн занятий неделя ID дня (FK) номер пары Т

Дни_

Рис. 7. Логическая модель хранения исходной и результирующей информации

На основе предложенных алгоритмов был реализован программный комплекс "Феб". В диссертации также приводится описание программного комплекса и методика составления расписания с его использованием.

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

Факультет Информатики и Робототехники ведет подготовку по 16 специальностям, по каждой из которых обучается одна и более учебных групп, всего насчитывается 116 учебных групп, для которых проводятся занятия по 202 дисциплинам. В учебном процессе задействованы 235 преподавателей.

Для УГАТУ в целом, и для факультета ИРТ в том числе, характерно обучение в две смены. Такой многосменный характер обучения объясняется большим числом факультетов и специальностей обучения. Для проведения занятий УГАТУ располагает 9 учебными корпусами, общее число аудиторий составляет 280 единиц, из них 6 аудиторий предназначены для проведения занятий с большими потоками (несколько учебных групп нескольких специальностей), 62 аудитории - для проведения занятий с небольшими потоками (2-4 учебные группы), 32 аудитории - для занятий с одной группой студентов. Для проведения лабораторных занятий по разным дисциплинам предусмотрено 180 аудиторий. Причем лабораторные занятия проводятся не просто в какой либо лаборатории ВУЗа, а в лаборатории определенной кафедры.

Расписание было составлено на основе следующей исходной информации: число преподавателей - 235, число учебных групп - 116, число потоков - 162, число дисциплин - 202, число аудиторий - 280, число учебных пар в течение семестра для каждой группы - 648.

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

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

Была построена зависимость времени расчета расписания от размерности решаемой задачи (рис. 8) на основании трех проведенных экспериментов по расчету расписания:

1) для одной специальности (число блоков = 92) - 1.5 часа;

2) для одного курса (число блоков = 487) - 2.7;

3) для одного факультета (1679 блоков занятий) - 7 часов.

время

1000

блоки занятий

--»— агрегативный алгоритм

традиционный алгоритм

Рис. 8. Зависимость времени расчета расписания от размерности задачи

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

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

использовании предлагаемых агрегативных алгоритмов. При этом время составления расписания на компьютере Pentium IV с помощью предложенного агрегативного генетического алгоритма составило порядка 7 часов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

1. Кабальнов Ю.С., Низамова Г.Ф., Строкина Ю.Г. Применение информационных технологий при решении прикладных задач теории расписаний // Проблемы техники и технических телекоммуникаций: Материалы 5-й научно-технической конференции, Самара, 2004, С.161-162.

2. Низамова Г.Ф. Использование элементов нечеткой логики в управлении учебным процессом при подготовке специалистов по направлению "Телекоммуникации" // Материалы 8-й международной научно-методической конференции вузов и факультетов телекоммуникаций, Уфа, 2004, С.50-52.

3. Низамова Г.Ф., Строкина Ю.Г. Принципы разработки математической модели гетерогенных задач составления расписания учебных занятий // Компьютерные науки и информационные технологии: Материалы 7-й международной нау чной конференции, Уфа, 2005, С.69-72 (на англ. яз.)

4. Кабальнов Ю.С., Шехтман Л.И., Ковтуненко A.C. Генетический алгоритм составления расписания учебных занятий, основанный на структуризации исходной информации // Деп. научн. работа в ВИНИТИ, УГАТУ, 2006, 27 с.

5. Низамова Г.Ф. Генетический алгоритм составления расписания работы сложных систем (на примере образовательных систем массового обучения) // Интеллектуальные системы обработки информации и управления: Материалы Региональной зимней школы-семинара аспирантов и молодых ученых, Том 1, Уфа, 2006, С.116-122.

6. Алкаев П.А., Кабальнов Ю.С., Масленников В.А., Низамова Г.Ф.. Использование технологий хранения и обработки информации при создании базы данных "Расписание учебных занятий" // Современные проблемы высшего образования в России: Материалы Российской Научно-технической конференции Мавлютовские чтения, Уфа, 2006, С.9-14.

7. Низамова Г.Ф., Ковтуненко A.C. Генетические алгоритмы решения задачи составления расписания в условиях неполноты априорной информации // Сборник трудов второй научно-технической конференции молодых

специалистов, посвященный годовщине образования объединения ОАО "УМЛО", ОАО "УМПО", 2006, С.76-77.

8. Низамова Г.Ф. Агрегативные генетические алгоритмы составления расписания учебных занятий // Системы управления и информационные технологии. - 2006, №2, С.170-173.

9. Кабальнов Ю.С., Ковтуненко A.C., Низамова Г.Ф. Экспертное ранжирование множества альтернатив в условиях неопределенности. Ч. I. Нечеткие модели неопределенности// Информационные технологии моделирования и управления. - 2006, №6(31), С.697-702.

10. Кабальнов Ю.С., Ковтуненко A.C., Низамова Г.Ф. Экспертное ранжирование множества альтернатив в условиях неопределенности. Ч. II. Вероятностные модели неопределенности // Информационные технологии моделирования и управления. - 2006, № 7(32), С.819-824.

Диссертант СШАр^ Г.Ф. Низамова

НИЗАМОВА Гузель Фанисовна

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

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Подписано к печати 25.09.06. Формат 80x64 1/16. Бумага офсетная. Печат., плоская. Гарнитура Times New Roman. Усл. печ. л. 1,0. Усл. кр.-отт. 0,9. Уч.-изд. л. 0.9. Тираж 100 экз. Заказ №455.

Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

¿tooGfi

11112 0 3SS

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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