Дипломная Работа




НазваниеДипломная Работа
страница13/13
Дата публикации29.07.2013
Размер0.52 Mb.
ТипДиплом
lit-yaz.ru > Информатика > Диплом
1   ...   5   6   7   8   9   10   11   12   13
^

8.2Результаты испытаний


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

8.2.1Методика испытаний


Исследования проводились на реальных данных факультета ВМиК МГУ. В качестве критерия эффективности рассматривалось количество работ, размещенных в ходе работы модифицированного алгоритма, по отношению к суммарному количеству работ. Исследовалась зависимость данного критерия от загрузки аудиторий. Загрузка аудиторий представляет собой отношение количества работ, которые необходимо разместить, к количеству работ, которые возможно провести в данных аудиториях за данное время: , где NJ – количество работ (в данном случае количество работ равно 649), ^ NP – количество пар в неделю, NA – количество доступных аудиторий. Загрузка аудиторий менялась в зависимости от устанавливаемых ограничений на число пар в день и дней в неделе.

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

        • ширина отката – 10, 50, max (рассматриваются все «работы-кандидаты»)

        • глубина отката – 1, 3, 5

        • критерий сортировки списка «работ-кандидатов»:

  1. минимальное количество групп в работе;

  2. максимальное количество возможных размещений для «работы-кандидата»;

  3. минимальное количество возможных размещений для «работы-кандидата»
^

8.2.2Результаты испытаний


Таблица 2. Результаты численных исследований.

Ширина

Глубина

Критерий сортировки

Загрузка аудиторий, %

50

65

80

10

1

A

100

99.1

96.8

10

3

A

100

99.2

92.3

50

1

A

100

99.1

98.1

Max

1

A

100

99.5

98.1

Max

3

A

100

99.5

90

Max

5

A

100

99.5

94.9

10

1

B

100

98.3

97.3

50

1

B

100

99

97.9

50

3

B

100

99.4

98.3

Max

1

B

100

99

97.9

10

1

C

99.7

99

97.1

50

1

C

100

99.4

97.3

Max

1

C

100

99.4

97.3

1-й алгоритм

96.3

92.3

71.2

2-й алгоритм

99.4

93.5

73.5


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

9Заключение


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

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

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

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

10Список литературы


  1. Ерунов В.П., Морковин И.И. Формирование оптимального расписания учебных занятий в ВУЗе // Вестник ОГУ. Оренбург: ОГУ, 2001. №3. С.55-63.

  2. Marte M. Models and Algorithms for School Timetabling – A Constraint Programming Approach. // Dissertation. Fakultät für Mathematik, Informatik und Statisitk der Ludwig-Maximilians-Universität, München. 2002.

  3. Теория расписаний и вычислительные машины/ Под ред. Э.Г.Коффмана. М.: Наука, 1984.

  4. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

  5. Костенко В.А. Принципы построения генетических алгоритмов и их использование для решения задач оптимизации. // Труды IV Международной конференции «Дискретные модели в теории управляющих систем» (19-25 июня 2000 г.). М.: МАКС Пресс, 2000. С.49-55.

  6. Lalescu L. Timetabling Experiments Using Genetic Algorithms. // Lucrare de Diploma. Facultatea de Automatica, Calculatoare si Electronica, Universitatea din Craiova, Craiova. 2003.

  7. Каширина И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида. // Вестник ВГУ, Серия физика, математика. 2003. №1. С. 128-131.

  8. Калашников А.В., Костенко В.А. Алгоритмы локальной оптимизации расписаний // Труды первой всероссийской научной конференции «Методы и средства обработки информации» (МСО’2003, Москва, 1-3 октября 2003 г). М.: МАКС Пресс, 2003.

  9. Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. 2002. №3.

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

  11. Уоссермен Ф. Нейрокомпьютерная техника: теория и практика. М.: Мир, 1992.

  12. Матусевич О. Алгоритмы имитации отжига для задачи построения расписаний. // Дипломная работа. Московский Государственный Университет имени М.В.Ломоносова, факультет Вычислительной Математики и Кибернетики. Москва. 2004.

  13. Костенко В.А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС. // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения» (30 октября - 2 ноября 2000 г., г. Черноголовка). М.: Изд-во МГУ, 2000. С.123-127.

  14. Костенко В.А., Калашников А.В. Исследование различных модификаций алгоритмов имитации отжига для решения задачи построения расписания многопроцессорных расписаний. // Дискретные модели в теории управляющих систем. Труды VII Международной конференции. М.: МАКС Пресс, 2006. С.179-184

  15. T.Muller. Some Novel Approach to Lecture Timetabling. In Proceedings of the 4th Workshop of Constraint Programming for Decision and Control. CDPC’2002, Gliwice, 2002.

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

  17. O.Rossi-Doria, B.Paechter. An Opinion Algorithm for University Course Timetabling. Technical Report. Napier University, Edinburgh, UK, 2004.

1   ...   5   6   7   8   9   10   11   12   13

Похожие:

Дипломная Работа iconНазвание организации
Заголовок «Дипломная работа» или «Курсовая работа»: Times New Roman, 14 (вопреки П. 113), по центру. Затем – 2 пустые строки

Дипломная Работа iconДипломная работа
Степень удовлетворенности пользователей в документах по музыкальному искусству 25

Дипломная Работа iconДипломная работа
Состояние, тенденции и проблемы развития народного образования в Новом Уренгое

Дипломная Работа iconДипломная работа
Разработка анализатора системы обнаружения атак, основанного на методах кластерного анализа”

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых сессий

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых объектов

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых объектов

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых объектов

Дипломная Работа iconДипломная работа
Повышение качества результатов анонимного интернет-голосования методом анализа сетевых объектов

Дипломная Работа iconДипломная работа
Использование средств olap-технологий для построения системы Бизнес Интеллекта факультета



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница