Генерация расписания занятий с применением распределенных генетических алгоритмов

ID работы - 743992
программирование (дипломная работа)
количество страниц - 72
год сдачи - 2002

---

СОДЕРЖАНИЕ:

---

Содержание
1. ВВЕДЕНИЕ 4
1.1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 4
1.2. ОСНОВНЫЕ ПОНЯТИЯ 6
1.3. НЕФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 8
1.4. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ 9
1.4.1. Подходы к решению задачи 9
1.4.2. Сравнение различных методов решения задачи 9
1.4.3. Краткий обзор продуктов сторонних разработчиков 11
1.4.4. Создание собственной программы 12
2. ТРЕБОВАНИЯ К ОКРУЖЕНИЮ 14
2.1. ТРЕБОВАНИЯ К АППАРАТНОМУ ОБЕСПЕЧЕНИЮ 14
2.2. ТРЕБОВАНИЯ К ПРОГРАММНОМУ ОБЕСПЕЧЕНИЮ 14
2.3. ТРЕБОВАНИЯ К ПОЛЬЗОВАТЕЛЯМ 14
3. АРХИТЕКТУРА СИСТЕМЫ 15
4. СПЕЦИФИКАЦИЯ ДАННЫХ 17
4.1. ИСХОДНЫЕ ДАННЫЕ 17
4.1.1. Структура файла со схемой расписания 18
4.1.2. Структура файла состояния 20
4.2. ПРОТОКОЛ ОБМЕНА ИНФОРМАЦИЕЙ МЕЖДУ СЕРВЕРОМ И КЛИЕНТАМИ 21
4.3. ВЫХОДНЫЕ ДАННЫЕ 23
5. ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ 24
5.1. СЕРВЕРНАЯ ЧАСТЬ 24
5.2. КЛИЕНТСКАЯ ЧАСТЬ 29
5.3. РЕДАКТОР СХЕМЫ РАСПИСАНИЯ 33
6. ТРЕБОВАНИЯ К ИНТЕРФЕЙСУ 35
6.1. ИНТЕРФЕЙС СЕРВЕРНОЙ ЧАСТИ 35
6.2. ИНТЕРФЕЙС КЛИЕНТСКОЙ ЧАСТИ 41
6.3. ИНТЕРФЕЙС РЕДАКТОРА СХЕМ РАСПИСАНИЙ 43
7. ПРОЕКТ 48
7.1.ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В РЕШЕНИИ ЗАДАЧИ 48
7.2. ГЕНЕРАЦИЯ НАЧАЛЬНОГО ПОКОЛЕНИЯ 52
7.3. МЕТОДЫ ЭВОЛЮЦИИ 53
7.3.1. Проверка правильности хромосом 53
7.3.2. Кроссовер 53
7.3.3. Мутация 54
7.3.4. Схема эволюции 55
7.3.5. Весовая функция 55
7.4. ВЗАИМОДЕЙСТВИЕ КЛИЕНТОВ С СЕРВЕРОМ 58
8. РЕАЛИЗАЦИЯ 59
8.1. ХАРАКТЕРИСТИКИ СИСТЕМЫ 59
8.2. ТЕСТИРОВАНИЕ 60
8.3. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ 61
ЗАКЛЮЧЕНИЕ 62
СПИСОК ЛИТЕРАТУРЫ 63
ПРИЛОЖЕНИЯ 66
ПРИЛОЖЕНИЕ 1. ЧТО ТАКОЕ «ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ» 66
ПРИЛОЖЕНИЕ 2. ИСПОЛЬЗОВАНИЕ DIRECTPLAY 70

---

ВВЕДЕНИЕ:

---

1. Введение
1.1. Описание предметной области
Задача составления расписания занятий для учебных заведений имеет давнюю историю. Она интересовала людей, занятых в процессе формирования учебного процесса с момента появления образовательных учреждений массового характера: школ, гимназий, колледжей, институтов и университетов.
Традиционно эта задача решалась вручную каким-либо человеком, который, на основании определенных критериев, вручную чертил на бумаге расписание, традиционно имеющее вид таблицы, удовлетворяющее определенным свойствам.
С появлением новых предметов, с увеличением числа преподавателей и студентов, с делением студентов на группы и подгруппы, с появлением таких понятий как потоковые лекции, номера аудиторий, выходные дни, максимальная нагрузка в день, пожелания преподавателей на возможность проведения лекций, приглашение на проведение некоторых лекций преподавателей из других учебных заведений и невозможность их присутствия в определенные дни/часы, а также многие другие факторы привели к значительному усложнению проблемы составления расписания.
Хотя за довольно долгий срок существования данной проблемы были выработаны некоторые методические указания и рекомендации по разработке и формированию расписания занятий, но при достаточно большом наборе исходных данных и при множестве ограничивающих факторов (критериев), они довольно часто оказывают мало пользы, и процесс формирования расписания продолжает оставаться довольно сложным и трудоемким занятием.
Хотя имеющиеся математические достижения в области исследования операций и методах оптимизации можно довольно успешно использовать при относительно небольшой сложности задачи, то при значительном увеличении количества критериев, по которым проводится оптимизация, как в случае составления расписания занятий для университетов, эти методы оказываются не очень эффективными (а очень часто даже и очень неэффективными), хотя для таких образовательных учреждений как школа эти методы вполне приемлемы [19].
Следуют заметить, что в наше время всеобщей автоматизации и компьютеризации производства и общества в целом во многих образовательных учреждениях задача составления расписания решается по старинке, т.е. вручную.
Составить оптимальное расписание, удовлет¬воряющее всем дидактическим требованиям, по¬зволяющим реализовать все возможности струк¬турно-логических схем и обеспечивающим мето¬дически правильное планирование учебной рабо¬ты на семестр студентам и преподавателям, с ис¬пользованием известных алгоритмов и подходов очень сложно, так как необходимо учесть много ограничивающих факторов: число учебных ауди¬торий и их структуру, число лекторов, пропуск¬ную способность учебных аудиторий и их особен¬ности, требования, обеспечивающие качество, и выполнить большое количество заявок препода¬вателей по планированию их рабочего дня [8].
Поэтому основной задачей при составлении расписания является планирование и обеспечение методически правильного процесса изучения всех учебных дисциплин учебного плана: их взаимосвязи, правильной последовательности и чередования всех форм учебной работы по дисциплинам на основе учета множества факторов [18].
Из описания проблемы видно, что она не является чем-то новым, но явно нуждается в упрощении труда человека, занятого ее решением. Т.е. налицо необходимость автоматизации решения данной задачи посредством разработки и реализации компьютерной программы.

1.2. Основные понятия
Расписание учебных занятий – это документ, регламентирующий работу студентов, преподавателей, всего учебного заведения, распределяющий содержание учебного плана и рабочих программ по календарным дням учебного года и обеспечивающий их реализацию. Расписание учебных занятий должно удовлетворять педагогическим требованиям, основанным на принципах аналитической дидактики и кибернетической аналогии. Оптимально составленное расписание учебных занятий не должно изменяться в течение семестра или учебного цикла, чтобы не нарушить учтенные в расписании межпредметные связи и выполненные требования [8].
Целью задачи генерации расписания является задача оптимизации, в которой из имеющего множества порожденных расписаний необходимо выделить то, которое имеет целевую функцию с наименьшим значением (наиболее близким к нулю), т.е. задачей всего процесса является минимизация значения целевой функции.
Основными условиями, определяющими корректность расписания, являются:
• Соответствие требуемого количества пар в неделю каждого предмета каждого преподавателя их количеству в расписании;
• Невозможность ведения одним преподавателем в одно и то же время различных предметов у нескольких групп;
• Соответствие количества пар в единицу времени (равной продолжительности одной пары) у всего института количеству свободных аудиторий в эту же единицу времени.
• Свободность (незанятость) аудитории, в которой проводится лекция, в определенное время;
• Проверка на «вмещаемость» группы в аудиторию (либо нескольких групп в аудиторию при проведении потоковых лекций);
• Необходимость проведения лекции в определенной аудитории (например, это может быть химическая лаборатория или компьютерный класс);
• Возможность проведения потоковых лекций;
• Возможность проведения лекций по числителю/знаменателю;
• Необходимость проведения лекций в строго фиксированное время (в конкретное время в определенный день недели);
• Возможность задания дня, в который нельзя проводить занятия (например, если в этот день у группы должна проводиться Военная подготовка, которая занимает весь учебный день и место ее проведения находится достаточно далеко от здания университета);
• Желание преподавателя вести определенные пары в определенные интервалы времени;
• Невозможность или какие-либо затруднения у преподавателя с прибытием к какому-то времени в определенные дни;
• Добиться оптимального распределения количества пар по дням для каждой из групп (не сильно мало и не сильно много);
• Одинаковые пары желательно проводить непосредственно друг за другом;
• Стараться избегать «окон», т.е. такого времени между парами, когда у группы нет занятий.

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

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

1.3. Неформальная постановка задачи
Требуется разработать программу генерации семестрового расписания занятий для факультета, в которой, для увеличения производительности работы, предполагается использование генетических алгоритмов в совокупности с распределенными вычислениями.
Под распределенными вычислениями будем понимать процесс одновременного решения задачи на нескольких терминалах с использованием технологии клиент-сервер.
Для достижения поставленной цели предлагается создать два различных приложения: клиент и сервер, при взаимодействии которых стало бы возможным получение желаемого результата.
Клиенты запускаются на различных машинах и занимаются непосредственно генерацией расписания, а сервер синхронизирует их действия, т.е. управляет ими с помощью механизма обмена сообщениями по одному из сетевых протоколов.
На основании результатов, полученных сервером от клиентов, пользователь может выбрать наиболее удовлетворяющее его критериям решение, сохранить его для дальнейшей обработки, либо экспортировать в формат Microsoft Excel для просмотра, редактирования и распечатки.

1.4. Обзор существующих методов решения
1.4.1. Подходы к решению задачи

---

СПИСОК ЛИТЕРТУРЫ:

---

Список литературы 1. Акимов Е. Школьный диспетчер. Руководство пользователя , Санкт-Петербург, 1999, 32 стр. 2. Андреев Ю.А. Программа 1Я – Методист (Расписание занятий). Руководство пользователя, 2002, 11 стр. 3. Ахо А.В., Хоркрофт Дж.Э., Ульман Дж.Д. Структуры данных и алгоритмы, М., Спб., Киев: Вильямс, 2001 4. Барьер П.Л. Метод динамического программирования, как алгоритмическое выражение достаточно общей теории управления, апрель 2000, http://www.kobro.com/basis/mertvoda/mvt2-11.htm 5. Гермейер Ю.Б. Введение в теорию исследования операций, М., Наука, 1971 6. Горбунов А. Расписание-замены, май 2002, http://sched2001.narod.ru/ 7. Губенко И.О. Cистема автоматического расписания АВТОР-2+, май 2002, http://sch297.portal.ru/ 8. Ерунов В.П. Некоторые вопросы формирования автоматизированной системы управления учебным процессом. Технология образовательного процесса: тез. докл. Межвузовской научн.-метод. конф., г.Оренбург, ОГУ, 1997 9. Зайченко Ю.П. Исследование операций, М., Машиностроение, 1973 10. ИКИ РАН (Space Research Institute). Генетические алгоритмы, май 1999, http://www.iki.rssi.ru/ehips/genetic.htm 11. Исаев С.А. Популярно о генетических алгоритмах, март 2000, http://www.chat.ru/~saisa/ga/ga-pop.html 12. Исаев С.А. Обоснованно о генетических алгоритмах, март 2000, http://www.chat.ru/~saisa/ga/text/part1.html 13. Как составить качественное расписание, (с) 2001 InfoSchool, http://infoschool.at.tut.by/ 14. Калашников М.А. Школьный диспетчер, март 2002, http://dispet.narod.ru/111.htm 15. Капустин Е. Программа расписание 4.0, май 2002, http://www.aha.ru/~timetab/intro/ 16. Карманов В.Г. Математическое программирование, М., Наука, 1986 17. Клемент Р. Генетические алгоритмы: почему они работают? Когда их применять?, Компьютерра, №11/1999 18. Краковский В., Матусевич О. Зачем завучу "машина"? Компьютерное составление расписания занятий в образовательных учреждениях, Учительская газета, №22/2001 19. Мальцев М.В. Автоматизация управления учебным процессом, май 2002, http://www.nsu.ru/archive/conf/nit/96/sect1/node12.html 20. Методист - Технические характеристики, (c) Direx, март 2002, http://www.direx.com.ua/page.php 21. НейроПроект. Аналитические технологии для прогнозирования и анализа данных, март 1999, http://www.neuroproject.ru/oglavl.htm 22. НейроПроект. Генетические алгоритмы, февраль 1999, http://www.neuroproject.ru/genealg.htm 23. Программа составления расписания занятий для школ и учебных заведений, (c) НИКА-SOFT, март 2002, http://www.nikasoft.ru/nikasoft.html 24. Программа составления расписания занятий для общеобразовательной школы, март 2002, http://infoschool.at.tut.by/default.html 25. Редько В.Г. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма, http://www.keldysh.ru/BioCyber/Lecture1.html 26. Редько В. Г. Эволюционная биокибернетика, Компьютерра, №11/2000 27. Редько В. Г. Эволюционная биокибернетика. Почему так медленно развивается актуальная наука?, апрель 2000, www.iph.ras.ru/~mifs/Redko1R.htm 28. Сердцев А. Программа "Расписание занятий", май 2002, http://serdtsev.narod.ru/ 29. Смелянский Р.Л. Модель функционирования распределённых вычислительных систем// Вестник МГУ, сер.15, Вычислительная математика и кибернетика, №3/1990 30. Смыкалов П. Программа составления расписания "Ректор", май 2002, http://www.rector.spb.ru/ 31. Составление расписания с помощью программного пакета «Хронограф», (c) 2001 Хронобус, http://www.chronobus.ru 32. Струнков Т. Что такое генетические алгоритмы, PC Week RE, №19/1999 33. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации, М., Наука, 1986 34. Третьяков П.И. Модульная технология как один из путей повышения эффективности учебно-воспитательного процесса. Модульное построение учебных занятий, апрель 2002, http://www.iro.yar.ru:8100/resource/distant/society_sciense/katsch/kat1.htm 35. Genetic Programming FAQ, February 1996, http://www.cs.ucl.ac.uk/research/genprog/gp2faq/gp2faq2.html 36. MSDN 2001. Platform SDK: DirectX 8.0 for C/C++. Introduction To DirectPlay. Microsoft Corporation, April 2001 37. MSDN 2001. Platform SDK: DirectX 8.0 for C/C++. Understanding DirectPlay. Microsoft Corporation, April 2001 38. MSDN 2001. Platform SDK: DirectX 8.0 for C/C++. Using DirectPlay. DirectPlay. Microsoft Corporation, April 2001 39. Obitko M., Genetic Algorithm, September 1998, http://ulm.uni.udm.ru/~ilya/ga/about.html
Цена: 1050.00руб.