Практическая реализация генетического алгоритма

Оглавление

Введение 5

1. Теоретический обзор 6

1.1 Краткое описание генетического алгоритма 6

1.2 Место генетического алгоритма в теории расписаний 8

1.3 Модель решения задачи расписания 12

1.3.1 Составление начальной популяции 14

1.3.2 Генетические операторы 14

1.3.3 Формирование новой популяции 15

1.3.4 Критерий останова 16

1.4 Пути улучшения генетического алгоритма 17

2. Практическая реализация алгоритма 20

2.1 Выбор структуры хранения данных 20

2.2 Описание алгоритма работы программы 21

2.3 Инструкция пользователя 24

2.4 Оценка сложности 24

2.5 Результаты работы приложения 26

2.6 Тестирование дополнений к генетическому алгоритму 27

2.6.1 Размер популяции 27

2.6.2 Равномерное скрещивание 28

2.6.3 Улучшающий ГА 29

2.6.4 Элитизм 30

2.6.5 Сравнение первой и последней моделей 31

Заключение 33

Список использованной литературы 34

Приложения 35

Введение

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

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

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

1. Теоретический обзор

1.1 Краткое описание генетического алгоритма

Генетический алгоритм получен в результате наблюдения за природными процессами, в частности, эволюцией и естественным отбором, и попыток воспроизвести их для решения задач оптимизации путем случайного подбора и комбинации входных параметров. Считается, что впервые о генетическом алгоритме высказался Дж. Холланд в 1975 г. Учёный был уверен в возможности автоматизировать алгоритм, который будет искать решение сложных задач эволюционным путем. Дж. Холланд написал программу, обрабатывающую двоичные последовательности, в которой можно выделить следующие этапы:

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

В текущей популяции необходимо найти наиболее приспособленные хромосомы. Данный процесс называется селекцией.

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

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

Вторичный поиск «хороших» хромосом через оценку их приспособленности.

Формирование нового поколения.

Цикл п.2-п.6 продолжается до тех пор, пока