Введение 3
Постановка задачи 4
Обзор литературы 6
Глава 1. Теоретическое описание применяемых методов 8
1.1. Сведение к интегро-дифференциальному уравнению 8
1.2. Метод случайных блужданий 9
1.3. Метод муравьиной колонии 11
1.4. Модификации метода муравьиной колонии 13
1.5. Метод имитации отжига 15
1.6. Квантовый отжиг 18
1.7. Стохатическое туннелирование 20
Глава 2. Результаты численных экспериментов 21
2.1. Технические детали реализации 21
2.2. Реализация метода случайных блужданий 22
2.3. Реализация метода муравьиной колонии 23
2.4. Реализация метода симуляции отжига 25
2.5. Реализация квантового отжига 27
2.6. Сравнение результатов 29
2.7. Итоговые результаты 31
Заключение 32
Список литературы 33
Задача поиска оптимальной в смысле затрат на строительство траектории дороги на рельефе местности естественным образом возникает при планировании транспортной сети и является предметом многочисленных исследований.
Основным подходом к ее решению является сведение к аналогичной задаче на графе путем построения сетки, покрывающей рельеф местности, и последующего вычисления стоимости перехода между её узлами. К полученной таким образом постановке можно применить известные алгоритмы поиска оптимального пути.
Однако, в случае, если изначально стоимость представляется значением некоторого интегрального функционала и тем самым задача поиска оптимальной траектории представляет из себя простейшую основную задачу вариационного исчисления, такие методы требуют доработки.
Данная работа посвящена исследованию, сравнению и адаптации к случаю задачи вариационного исчисления различных методов глобальной оптимизации, основанных на эвристиках или применении искусственного (роевого) интеллекта.
Результаты, полученные при выполнении данной работы, были представлены на конференциях PCI 2023 и ITTA 2024.
В ходе выполнения работы получены следующие результаты:
• Проведено сведение исходной задачи к задаче поиска кратчайшего пути;
• Рассмотрены и модифицированы под конкретную задачу существующие методы поиска кратчайшего пути;
• Получены результаты применения всех рассмотренных методов к модельной тестовой функции;
• Проведён сравнительный анализ результатов;
