?

Details
Table Card RUSMARC
Title: Исследование роевых алгоритмов оптимизации для решения задачи поиска кратчайшего пути: выпускная квалификационная работа бакалавра: направление 09.03.04 «Программная инженерия» ; образовательная программа 09.03.04_01 «Технология разработки и сопровождения качественного программного продукта»
Creators: Назаренко Алёна Вячеславовна
Scientific adviser: Черноруцкий Игорь Георгиевич
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт компьютерных наук и технологий
Imprint: Санкт-Петербург, 2023
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: методы оптимизации; кратчайший путь; роевые алгоритмы; бактериальная оптимизация; муравьиный алгоритм; алгоритм интеллектуальных капель воды; алгоритм Дейкстры; optimization methods; shortest path; swarm algorithms; bacterial optimization; ant algorithm; intelligent water drops algorithm; Dijkstras algorithm
Document type: Bachelor graduation qualification work
File type: PDF
Language: Russian
Level of education: Bachelor
Speciality code (FGOS): 09.03.04
Speciality group (FGOS): 090000 - Информатика и вычислительная техника
DOI: 10.18720/SPBPU/3/2023/vr/vr23-3429
Rights: Доступ по паролю из сети Интернет (чтение, печать)
Record key: ru\spstu\vkr\22812

Allowed Actions: –

Action 'Read' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

Данная работа посвящена исследованию применимости роевых алгоритмов оптимизации для нахождения оптимального пути. В ходе исследования были изучены, реализованы и протестированы следующие роевые алгоритмы: - Бактериальной оптимизации; - Муравьиной оптимизации; - Интеллектуальных капель воды. Для того, чтобы оценить эффективность работы роевых алгоритмов при поиске кратчайшего пути, был также реализован популярный алгоритм Дейкстры. Реализация была выполнена на языке C++ в среде разработки Visual Studio 2019. Тестирование проводилось на графах, содержащих маленькое и большое число вершин и рёбер. Также был проведён анализ и подбор параметров, необходимых для работы алгоритмов. На основе полученных результатов были сделаны выводы о применимости роевых алгоритмов оптимизации в задаче поиска оптимального пути.

This work is devoted to the study of the applicability of swarm optimization algorithms for finding the optimal path. During the study, the following swarm algorithms were studied, implemented, and tested: - Bacterial optimization; - Ant optimization; - Intelligent water drops. To evaluate the performance of swarm algorithms in finding the shortest path, Dijkstras popular algorithm was also implemented. The implementation was performed in C++ in the Visual Studio 2019 development environment. Testing was carried out on graphs containing a small and large number of vertices and edges. Also, an analysis and selection of the parameters necessary for the operation of the algorithms was carried out. Based on the results obtained, conclusions were drawn about the applicability of swarm optimization algorithms in the problem of finding the optimal path.

Document access rights

Network User group Action
ILC SPbPU Local Network All Read Print
Internet Authorized users SPbPU Read Print
-> Internet Anonymous

Table of Contents

  • РЕФЕРАТ
  • ABSTRACT
  • ВВЕДЕНИЕ
  • ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ
    • 1.1. Роевые алгоритмы оптимизации
    • 1.1.1. Алгоритм поиска пищи бактериями
    • 1.1.2. Муравьиный алгоритм оптимизации
    • 1.1.3. Алгоритм интеллектуальных капель воды
    • 1.3. Популярные не роевые алгоритмы нахождения кратчайшего пути в графах
    • 1.3.1. Алгоритм Дейкстры
  • ГЛАВА 2. РАЗРАБОТКА ПРОГРАММЫ
    • 2.1. Выбор технологий и средств разработки
    • 2.2. Реализация алгоритма бактериальной оптимизации
    • 2.3. Реализация алгоритма муравьиной оптимизации
    • 2.4. Реализация интеллектуальных капель воды
    • 2.5. Реализация алгоритма Дейкстры
    • 2.6. Описание архитектуры программы
    • 2.7. Обработка исключений
  • ГЛАВА 3. ПРОВЕДЕНИЕ ТЕСТИРОВАНИЯ ПРОГРАММЫ И РЕЗУЛЬТАТЫ
    • 3.1. Тестирование на графе с малым числом вершин
    • 3.2. Тестирование на графе с большим числом вершин
  • ЗАКЛЮЧЕНИЕ
  • СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Usage statistics

stat Access count: 2
Last 30 days: 0
Detailed usage statistics