Применение генетических алгоритмов к решению задач дискретной оптимизации

Применение генетических методов для решения NP-трудных комбинаторных задач оптимизации полезно тогда, когда необходимый объем вычислительных затрат может оказаться большим, но скорость, с которой этот объем увеличивается при экспоненциальном росте «размерности» задачи дискретной оптимизации, часто может расти лишь линейно.

Введение 3
1 Постановки задач дискретной оптимизации 4
2 Метод исчерпывающего перебора и понятие задачи переборного 8
типа 8
3 Оценка трудности задач дискретной оптимизации 9
4 Основные понятия о генетических алгоритмах 9
4.1 Природный механизм 9
4.2 Функция приспособленности и кодирование решений 11
4.3 Алгоритм работы 13
5 Пути решения задач оптимизации 16
6 Примеры экстремальных комбинаторных задач 20
6.1 Задача об одномерном ранце 20
6.2 Задача дихотомического разбиения графа 21
6.3 Задача о назначениях 22
Заключение 23
Список использованных источников 24