ПАРАЛЛЕЛЬНО ПОСЛЕДОВАТЕЛЬНЫЙ БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ПОСТРОЕНИЯ МИНИМАЛЬНОГО ДЕРЕВА ШТЕЙНЕРА
Аннотация
Рассматривается параллельно последовательный подход к построению минимально-
го дерева Штейнера. Разработанный алгоритм базируются на общем подходе, заключаю-
щимся на декомпозиции связывающей сети и представлении ее в виде совокупности двух-
терминальных соединений. Для цепи ti на множестве вершин Xi, |Xi|=ni графа G с помощью
алгоритма Прима строится минимальное связывающее дерево Ri={rik|i=1, 2, …, ni-1}. Для
каждого ребра rikRi формируется маршрут sik, связывающий на графе G пару вершин,
соответствующих ребру rik. Каждому маршруту sik соответствует множество Г(sik)
ребер графа G. Задача построения минимального дерева Штейнера сводится к задаче по-
строения и выбора s-маршрута sik на графе G, для каждого ребра rik. Для каждого агента,
расположенного в вершине pi, задаются координаты вершины pj к которой прокладывает-
ся s-маршрут и определяются возможные направления его перемещения по ребрам орто-
гонального графа G=(V,E), обеспечивающие построение s-маршрута минимальной длины.
Качество маршрута, построенного агентом, будет определяться наличием общих участ-
ков с маршрутами, построенными другими агентами кластера. Чем больше в составе
маршрута общих участков с маршрутами, построенными другими агентами кластера,
тем меньше суммарная длина ребер минимального дерева Штейнера. Декомпозиция задачи
в рамках параллельно-последовательного подхода позволили избежать проблемы очередно-
сти прокладки маршрутов и организовать систему коллективной адаптации с высокой
степенью целесообразного поведения и сходимости. Особенностью представленного му-
равьиного алгоритма построения минимального дерева Штейнера является то, что му-
равьиная колония разбита на кластеры и поиск конкретного решения задачи осуществля-
ется популяцией кластеров муравьев. Задача построения муравьями каждого кластера Aσ
дерева Штейнера сводится к задаче построения и выбора в графе G совокупности
Mσ s-маршрутов, покрывающих минимальное дерево Штейнера. В отличие от канониче-
ской парадигмы муравьиной колонии, предложена модифицированная жадная стратегия
построения ориентированного маршрута на модели представления решения. Концепция
коллективной адаптации (адаптивного поведения) кластера агентов, используемая в
рассмотренном выше подходе, заключается в следующем. Глобальная цель коллектива
(кластера агентов) заключается в построении минимального дерева Штейнера. Локал ь-
ная цель каждого агента заключается в построении маршрута максимальной стоимо-
сти, то есть маршрута, максимально совпадающего с маршрутами, построенными дру-
гими агентами кластера, что косвенно способствует достижению глобальной цели ко л-
лектива. Состояние каждого ребра ejE графа поиска G решений описывается двумя
параметрами hj и dj. Значения показателей hj и dj обновляются путем наращивания на
каждой итерации после построения всеми кластерами агентов деревьев Штейнера.
В работе впервые используется композитная структура феромона и дифференцирова н-
ный метод его отложения. Каждый муравей в группе метит путь (ребра маршрута)
двумя видами феромона: феромон-1 и феромон-2. Это обеспечивает более высокую ве-
роятность локализации глобального экстремума задачи. Временная сложность этого
алгоритма на одной итерации определяется как O(n2). После выполнения всех действий
на итерации находится агент с лучшим решением, которое запоминается. Далее осуще-
ствляется переход на следующую итерацию.
Литература
– Ростов-на-Дону: Изд-во РГАСХМ, 2006. – 154 с.
2. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. – Таганрог: Изд-
во ТРТУ, 2003. – 132 с.
3. Лебедев О.Б. Построение дерева Штейнера на основе метода муравьиной колонии // Тр.
конгресса по интеллектуальным системам и информационным технологиям «AIS–
IT’09». Научное издание в 4-х т. Т. 1. – М.: Физматлит, 2009. – С. 58-65.
4. Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивно-
го поведения муравьиной и пчелиной колоний // Известия ЮФУ. Технические науки.
– – 2013. – № 7 (144). – С. 41-47.
5. Rabkin M. Efficient use of Genetic Algorithms for the Minimal Steiner Tree and Arborescence
Problems with applications to VLSI Physical Design // Genetic Algorithms and Genetic Programming
at Stanford. – 2002. – № 1. – P. 195-202.
6. Калашников Р.С. Экспериментальные исследования комбинированного эвристического
алгоритм построения дерева Штейнера основанного на методе эволюционного поиска
для этапа глобальной трассировки // Известия ТРТУ. – 2005. – № 3 (47). – С. 34-41.
7. Лебедев В.Б. Построение связывающих сетей на основе роевого интеллекта и генетиче-
ской эволюции // Сб. научных трудов XIV Всероссийской научно-технической конферен-
ции «НЕЙРОИНФОРМАТИКА-2012». Ч. 2. – М.: Изд-во Физматлит, 2012. – C. 93-103.
8. Tao Huang, Evangeline F.Y. Obstacle-avoiding rectilinear Steiner minimum tree construction:
an optimal approach // Proceedings of the International Conference on Computer-Aided Design
San Jose, California. 2010. – P. 610-613.
9. Полежаев П.Н., Миронов А.П., Поляк Р.И. Применение алгоритмов муравьиной колонии
в решении задачи Штейнера // Философские проблемы информационных технологий и
киберпространства. – 2015. – Вып. № 1. – С. 96-105.
10. Patel M.K., Kabat M.R., Tripathy C.R. A hybrid ACO/PSO based algorithm for QoS multicast
routing problem // Ain Shams Engineering Journal. – 2014. – Vol. 5, Issue 1. – P. 113-120.
11. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ
им. Н.Э. Баумана, 2006. – 288 с.
12. Щемелинин В.М. Автоматизация топологического проектирования БИС. – М.: МИЭТ,
2001. – 188 с.
13. OR-Library is collection of test data for a variety of OR problem. – http://mscmga.ms.ic.ac.uk.
14. Warme D.M. A new exact algorithm for rectilinear Steiner trees. INFORMS Conf., San-Diego,
California, 1997. – P. 455-472.
15. Andrew B. Kahng and Ion Mandoiu. RMST-Pack: Rectilinear minimum spanning tree algorithms.
– http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.
16. Chen H., Qiao C., Zhou F. and Cheng C.-K. Refined single trunk tree: A rectilinear Steiner
tree generator for interconnect prediction // In Proc. ACM Intl. Workshop on System Level Interconnect
Prediction. – 2002. – P. 85-89.
17. Hai Zhou. Efficient Steiner tree construction based on spanning graphs // In Proc. Intl. Symp.
on Physical Design. – 2003. – P. 152-157.
18. Griffith J., Robins G., Salowe J.S. and Zhang T. Closing the gap: Near-optimal Steiner trees in
polynomial time // IEEE Trans. Computer-Aided Design. – 1994. – No. 13 (11). – P. 1351-1365.
19. Chris Chu. FLUTE: Fast lookup table based wirelength estimation technique // In Proc.
IEEE/ACM Intl. Conf. on Computer-Aided Design. – 2004. – P. 696–701.
20. GeoSteiner – software for computing Steiner trees. – http://www.diku.dk/geosteiner/.
21. Chu C. and Wong Y.-C. Fast and accurate rectilinear Steiner minimal tree algorithm for VLSI
design. In Proc. International Symposium on Physical Design. – ACM Press, 2005. – P. 28-35.
