Введение 3
1. Теоретический обзор 4
1.1 Краткое описание генетического алгоритма 4
1.2 Место генетического алгоритма в теории расписаний 6
1.3 Модель решения задачи расписания 10
1.3.1 Составление начальной популяции 12
1.3.2 Генетические операторы 12
1.3.3 Формирование новой популяции 14
1.3.4 Критерий останова 14
1.4 Пути улучшения генетического алгоритма 15
2. Практическая реализация алгоритма 19
2.1 Выбор структуры хранения данных 19
2.2 Описание алгоритма работы программы 20
2.3 Инструкция пользователя 23
2.4 Оценка сложности 23
2.5 Результаты работы приложения 25
2.6 Тестирование дополнений к генетическому алгоритму 27
2.6.1 Размер популяции 27
2.6.2 Равномерное скрещивание 28
2.6.3 Улучшающий ГА 28
2.6.4 Элитизм 29
2.6.5 Сравнение первой и последней моделей 30
Заключение 32
Список использованной литературы 33
Приложения 34
Курсовая работа «Система автоматического создания школьного расписания на основе генетического алгоритма» посвящена созданию рабочей программы, позволяющей составлять школьное расписание, проведению серии испытаний и улучшению системы автоматического создания расписания.
Составление расписания занятий – трудоемкая задача, с которой каждый год приходится сталкиваться системе управления учебного заведения. Это непростой процесс, в котором необходимо учитывать правила организации учебного процесса, требования СанПин и пожелания учителей. Проблему автоматизации создания школьного расписания решает генетический алгоритм. Этот метод активно используется для решения комбинаторных задач и способен обрабатывать огромное пространство поиска, которое возникает в задаче планирования.
Данная курсовая работа имеет практическое применение: при небольшой модификации данного проекта можно создать приложение, которое упростит задачу составления расписания для руководства школьного учебного заведения.
Таким образом, в процессе создания курсовой работы разработано приложение, реализующее генетический алгоритм для решения задачи составления расписания. Приложение имеет ряд недостатков:
1. Возможно улучшение пользовательского интерфейса, который сделает возможным более быстрый ввод данных.
2. Возможно дополнение вывода, добавление в расписание название предметов, можно выгружать сразу несколько особей с наивысшими оценками приспособленности, чтобы у пользователя оставался выбор конечного решения проблемы расписания.
Следует так же отметить, что реализованный алгоритм наиболее часто применяется для решения проблемы составления расписания. Это только доказывает, что внимание уделено алгоритму, занимающему ведущее место в решении данной задачи.
