Решение проблем оптимизации генетических алгоритмов на примере задачи коммивояжера

Санкт-Петербургский государственный Политехнический Университет

кафедра прикладной математики

Курсы методы оптимизации:

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

на примере задачи коммивояжера»

Студент Кацман Виктор, группа 33601/2

Содержание

Введение

1. Постановка задачи

1.1 Общее описание задачи

1.2 Официальная ожидания

2. Общее описание генетического алгоритма

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

2.2 Общая схема алгоритма

2.3 Подробный анализ некоторых элементов алгоритма

3. Описание алгоритмов решения задачи

3.1 Алгоритм полного перебора

3.2 Алгоритм динамического программирования

3.3 Генетический алгоритм

4. Описание исследований и их результатов

4.1-Список тестировавшихся алгоритмы

4.2 Тест на проблем небольшой размер

4.3 Тест на экологические проблемы размер

4.4 Испытание на проблемы, большой размер

4.5 Тест для исследования «алгоритм повторяется приложений» генетического алгоритма

Выводы

Библиография

Введение

В этой статье рассматриваются возможности решения дискретные оптимизационные задачи с помощью генетических алгоритмов. Исследования были проведены на примере решения «несимметричной незамкнутой задачи коммивояжера» - известный комбинаторной NP-трудные задачи, для которых самая известная на данный момент точно алгоритм работы с асимптотикой O(2^n). В ходе исследования, результаты работы генетического алгоритма сравнивались с результатами раствором «несимметричной незамкнутой задачи коммивояжера» динамическое программирование по таким параметрам, как время работы, точность результата и объем памяти, используемый для различных входных данных.

1.Постановка задачи

.1 Общее описание задачи

Коммивояжер - странствующий торговец должен посетить N городов. Как известно, расходы на переезд между i-м и j-м городами, которые заданы в виде матрицы C = (c[i][j]), i = 1..N, j = 1..N. Коммивояжер должен посетить все города один раз. Это необходимо, чтобы определить, в каком порядке должны быть вокруг города, чтобы суммарные затраты были минимальными.