Сетевой научный журнал "Философские проблемы
информационных технологий
и киберпространства" (ISSN:2305-3763)

Применение алгоритмов муравьиной колонии в решении задачи Штейнера

DOI: 10.17726/philIT.2015.9.1.4.8

Автор: Полежаев П.Н., Миронов А.П., Поляк Р.И.

Аннотация: Статья посвящена анализу известной и актуальной NP-полной задачи Штейнера, зачастую решаемой с применением муравьиных алгоритмов. Актуальность данной задачи связана с бурным ростом компьютерных сетей, а также возможностью применения в других областях науки и техники, таких как прокладка силовых кабелей, проектирование СБИС, задачи логистики. В статье формализуется математическое описание задачи Штейнера. Рассматривается возможность применения различных эвристических «природных» алгоритмов для решения данной задачи. Проводится аналогия между поведением муравьиной колонии и работой алгоритма для решения NP-полной задачи Штейнера. Выделяются и описываются характерные особенности различных вариантов муравьиного алгоритма, разработанные другими авторами, приводятся результаты исследования их эффективности и сравнения с классической реализацией. Затрагиваются особенности реализации каждого из рассмотренных алгоритмов, включая структуру и другие параметры графов, на которых проводилось каждое из исследований. В статье приводятся ссылки на основные наборы данных, предназначенные для тестирования алгоритмов. Делается вывод об эффективности каждой из реализаций и возможности их применения на различных графах с учетом изменяющейся обстановки и характеристик графа.

Ключевые слова: задача Штейнера, алгоритм муравьиной колонии, NP-полная задача, эвристический алгоритм.

Полный текст статьи



Abstract: This article is devoted to the analysis of the well-known and relevant NP-complete Steiner problem, often solved by using ant algorithms. The relevance of this problem is related to the rapid growth of computer networks and the possibility of application in other fields of science and technology, such as the laying of power cables, VLSI design, logistics problems. Paper formalizes mathematical description of the Steiner problem. It considers the possibility of using different heuristics such as "natural" algorithms for solving this problem. In addition, it draws an analogy between the behavior of an ant colony and the work of the algorithm for solving NP-complete Steiner problem. Different variants of ant algorithms developed by other authors, the results of their effectiveness estimation and comparison with the classical implementation are described. Paper notes the implementation features of each considered algorithms, including their graph structure and its parameters. In addition, we provide links to major data sets for testing algorithms and conclude about the effectiveness of each algorithm implementations and their applicability to different graphs, including their dynamic changing.

Keywords: Steiner tree problem; Ant colony optimization; NP-complete; heuristic algorithm.



← Назад в выпуск