📄Работа №63944
Тема: Модификация муравьиного алгоритма для динамической задачи коммивояжёра
Тип работы
Бакалаврская работа
Предмет
математика
Объем:
37 листов
Год:
2016
Просмотров:
362
3850
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
1.1. ИСТОРИЯ ЗАДАЧИ TSP 4
1.2. ПОСТАНОВКА ЗАДАЧИ TSP 5
Математическая модель задачи TSP 6
1.3. ПОСТАНОВКА ЗАДАЧИ TDTSP 7
Математическая модель задачи TDTSP 7
2. ОБЗОР АЛГОРИТМОВ 9
2.1. BIOLOGY-INSPIRED ALGORITHMS 9
2.2. ANT COLONY OPTIMIZATION (ACO) 11
2.3. PARTICLE SWARM OPTIMIZATION (PSO) 13
2.4. ARTIFICIAL BEE COLONY 14
2.5. ВЫВОДЫ 15
3. МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ TDTSP 17
3.1. ПАРАМЕТРЫ ЗАДАЧИ TDTSP 17
3.2. ВРЕМЯ ПУТИ МАРШРУТА 17
3.3. ЖАДНЫЙ АЛГОРИТМ 18
3.4. АЛГОРИТМ ЛОКАЛЬНОГО ПОИСКА 19
3.5. ИНИЦИАЛИЗАЦИЯ ФЕРОМОНОВ 19
3.6. ОСНОВНАЯ ПРОЦЕДУРА 20
4. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ .22
4.1. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ ДЛЯ ЭВРИСТИЧЕСКОГО
АЛГОРИТМА 23
4.2. ПРОВЕРКА УРОВНЯ ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ 24
4.3. РЕЗУЛЬТАТЫ ПРОВЕРКИ НА ДИНАМИЧЕСКУЮ УСТОЙЧИВОСТЬ 25
5. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ 27
5.1. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ ДЛЯ АСО 27
5.2. РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ ДИНАМИЧЕСКОЙ АДАПТАЦИИ 28
5.3. АНАЛИЗ РЕЗУЛЬТАТОВ 29
6. ЗАКЛЮЧЕНИЕ 30
7. СПИСОК ЛИТЕРАТУРЫ 31
1.1. ИСТОРИЯ ЗАДАЧИ TSP 4
1.2. ПОСТАНОВКА ЗАДАЧИ TSP 5
Математическая модель задачи TSP 6
1.3. ПОСТАНОВКА ЗАДАЧИ TDTSP 7
Математическая модель задачи TDTSP 7
2. ОБЗОР АЛГОРИТМОВ 9
2.1. BIOLOGY-INSPIRED ALGORITHMS 9
2.2. ANT COLONY OPTIMIZATION (ACO) 11
2.3. PARTICLE SWARM OPTIMIZATION (PSO) 13
2.4. ARTIFICIAL BEE COLONY 14
2.5. ВЫВОДЫ 15
3. МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ TDTSP 17
3.1. ПАРАМЕТРЫ ЗАДАЧИ TDTSP 17
3.2. ВРЕМЯ ПУТИ МАРШРУТА 17
3.3. ЖАДНЫЙ АЛГОРИТМ 18
3.4. АЛГОРИТМ ЛОКАЛЬНОГО ПОИСКА 19
3.5. ИНИЦИАЛИЗАЦИЯ ФЕРОМОНОВ 19
3.6. ОСНОВНАЯ ПРОЦЕДУРА 20
4. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ .22
4.1. ДИНАМИЧЕСКАЯ УСТОЙЧИВОСТЬ ДЛЯ ЭВРИСТИЧЕСКОГО
АЛГОРИТМА 23
4.2. ПРОВЕРКА УРОВНЯ ДИНАМИЧЕСКОЙ УСТОЙЧИВОСТИ 24
4.3. РЕЗУЛЬТАТЫ ПРОВЕРКИ НА ДИНАМИЧЕСКУЮ УСТОЙЧИВОСТЬ 25
5. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ 27
5.1. ДИНАМИЧЕСКАЯ АДАПТАЦИЯ ДЛЯ АСО 27
5.2. РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ ДИНАМИЧЕСКОЙ АДАПТАЦИИ 28
5.3. АНАЛИЗ РЕЗУЛЬТАТОВ 29
6. ЗАКЛЮЧЕНИЕ 30
7. СПИСОК ЛИТЕРАТУРЫ 31
📖 Введение
Объем рынка транспортно-логистических услуг растет во всем мире, и в связи с этим решение различных задач маршрутизации становится все более актуальной проблемой. Основной целью в данных задачах является построение маршрутов для транспортных средств, обслуживающих определенное множество клиентов. При этом выбор неудачного маршрута влечёт за собой дополнительные издержки по транспортировке товара.
Класс задач маршрутизации в настоящее время является очень широким. Распространённым и самым ранним примером является задача коммивояжера или задача TSP (Travelling Salesman Problem). Для исследования была выбрана задача коммивояжера, зависящая от времени или задача TDTSP (Times Dependent Travelling Salesman Problem).
Алгоритмы, решающие данную задачу, разделяют на точные и эвристические. Так как задача коммивояжера принадлежит классу NP- трудных задач, очевидно, что точные алгоритмы применимы только для малоразмерных задач и не подходят для решения реальных задач. Поэтому, как правило, используют эвристические алгоритмы. Они генерируют решения, приближенные к оптимальному, но за меньшее по сравнению с точными методами время.
Особенностью многих эвристических алгоритмов является разнообразие решений, получаемых при применении алгоритма к одному и тому же примеру. Это обусловлено тем, что при построении маршрута различным вариантам продолжения маршрута соответствует вероятность их выбора, так как постоянный выбор наилучшего продолжения на каком-либо шаге алгоритма в итоге не всегда дает оптимальное решение. Ввиду больших расстояний, в рассматриваемых на практике задачах любое улучшение алгоритма позволит существенно уменьшить расхождение полученных решений с оптимальным.
В первой главе рассмотрены задачи TSP и TDTSP, представлены их математические модели. Во второй главе приведен обзор литературы по
природным алгоритмам и их сравнение. В третьей главе подробно рассмотрено применение муравьиного алгоритма (ACO) для построения решения задачи TDTSP. В четвертой дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В пятой главе предложен метод динамической адаптации алгоритма, а так же его сравнение с ACO. В шестой главе описана проделанная работа и полученные результаты.
Класс задач маршрутизации в настоящее время является очень широким. Распространённым и самым ранним примером является задача коммивояжера или задача TSP (Travelling Salesman Problem). Для исследования была выбрана задача коммивояжера, зависящая от времени или задача TDTSP (Times Dependent Travelling Salesman Problem).
Алгоритмы, решающие данную задачу, разделяют на точные и эвристические. Так как задача коммивояжера принадлежит классу NP- трудных задач, очевидно, что точные алгоритмы применимы только для малоразмерных задач и не подходят для решения реальных задач. Поэтому, как правило, используют эвристические алгоритмы. Они генерируют решения, приближенные к оптимальному, но за меньшее по сравнению с точными методами время.
Особенностью многих эвристических алгоритмов является разнообразие решений, получаемых при применении алгоритма к одному и тому же примеру. Это обусловлено тем, что при построении маршрута различным вариантам продолжения маршрута соответствует вероятность их выбора, так как постоянный выбор наилучшего продолжения на каком-либо шаге алгоритма в итоге не всегда дает оптимальное решение. Ввиду больших расстояний, в рассматриваемых на практике задачах любое улучшение алгоритма позволит существенно уменьшить расхождение полученных решений с оптимальным.
В первой главе рассмотрены задачи TSP и TDTSP, представлены их математические модели. Во второй главе приведен обзор литературы по
природным алгоритмам и их сравнение. В третьей главе подробно рассмотрено применение муравьиного алгоритма (ACO) для построения решения задачи TDTSP. В четвертой дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В пятой главе предложен метод динамической адаптации алгоритма, а так же его сравнение с ACO. В шестой главе описана проделанная работа и полученные результаты.
✅ Заключение
В работе была исследована одна из задач маршрутизации транспорта - динамическая задача коммивояжера. Были рассмотрены различные эвристические алгоритмы природного класса.
Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи TDTSP. Произведена оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но близких к ним, среднее значение этой величины для рассмотренных задач получилось равным 0,6504.
Принцип динамической адаптации показал, что любой алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,9608. Также среднее значение длины решений, сгенерированных алгоритмом DAACO, получилось меньше, чем классическим муравьиным алгоритмом. Средний процент улучшения решений равен 4%. Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем простого муравьиного алгоритма, за счет генерируемых маршрутов меньшей длины.
Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи TDTSP. Произведена оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но близких к ним, среднее значение этой величины для рассмотренных задач получилось равным 0,6504.
Принцип динамической адаптации показал, что любой алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,9608. Также среднее значение длины решений, сгенерированных алгоритмом DAACO, получилось меньше, чем классическим муравьиным алгоритмом. Средний процент улучшения решений равен 4%. Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем простого муравьиного алгоритма, за счет генерируемых маршрутов меньшей длины.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.