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

  • 06 апр. 2012 г.
  • 2130 Слова
Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

Петрозаводский государственный университет

Математический факультет

Кафедра информатики

и математического обеспечения

Курсовая работа

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

Выполнил: студент группы 22306

И. В. Дейниченко

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

доцент, к.ф-м.н., Г. С. Сиговцев

Представлена «___»________2010 г.




Оценка оформления исроков представления работы:

Оценка публичной защиты работы:

Оценка промежуточного отчета:

Оценка научного руководителя:

Оформление и срок представления:

Итоговая оценка:

Отв. преподаватель:





Петрозаводск – 2010

Оглавление

Введение 3

1 Эволюционные вычисления 4

1.1 Естественный отбор вприроде . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 История . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Генетические алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.1 Функцияприспособленности . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.2 Принцип работы алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.2.1 Создание начальной популяции . . . . . . . . . . . . 9

1.4.2.2 Отбор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.2.3 Скрещивание . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

1.4.2.4 Мутация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10

2 Постановка задачи 11

2.1 Задача о ранце . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Цели . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Текущие результаты 133.1 Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 Анализ эффективности работы алгоритма . . . . . . . . . . . . . . . . . . 15

3.2.1 Вероятностная мутация . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2.2 Принудительная мутация . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.3 Выводы . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

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




Введение

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

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



































Глава 1

Эволюционные вычисления

1. Естественный отбор в природе

Эволюционная теория утверждает, что каждый...
tracking img