Статья

Название статьи МОДИФИЦИРОВАННЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ МИНИМАЛЬНОГО ДЕРЕВА ШТЕЙНЕРА
Автор Б. К. Лебедев, О. Б. Лебедев, Е. О. Лебедева
Рубрика РАЗДЕЛ I. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2017
Индекс УДК 004.896
DOI
Аннотация Предлагаются новые технологии, принципы и механизмы решения задачи построения дерева Штейнера, использующие математические методы, в которых заложены принципы природных механизмов принятия решений. Задача построения дерева Штейнера представляется в виде адаптивной системы, на основе интеграции принципов самоорганизации и муравьиного подхода к поиску решения. Известная проблема Штейнера состоит в следующем. Дано множество P точек на плоскости. Формируется ортогональная сетка путем проведения через множество точек P, расположенных на плоскости, горизонтальных и вертикальных линий. Образуется ортогональная сетка G=(V, E), где V множество точек (узлов) пересечений линий сетки. Исходная задача эквивалентна задаче отыскания в графе G=(V,E) дерева G*=(V*,E*), имеющего минимальный суммарный вес F ребер и включающего заданный набор вершин Р графа G. Построение минимального дерева Штейнера сводится к задаче построения и выбора (n-1) s-маршрутов, связывающих n основных вершин. Задача решается в два этапа. На первом этапе формируется набор альтернативных вариантов s-маршрутов, заведомо большей размерности, чем (n-1), покрывающий минимальное дерево Штейнера. На втором этапе из сформированного набора выбирается (n-1) s-маршрутов, покрывающих минимальное дерево Штейнера. В работе рассматривается комбинаторный и параллельно последовательный подходы к построению минимального дерева Штейнера: каждый из s-маршрутов строится последовательно, но все (n-1) s-маршрутов, покрывающих минимальное дерево Штейнера, строятся параллельно. Оба рассматриваемых подхода базируются на методе муравьиной колонии. В общем случае поиск решения задачи построения минимального дерева Штейнера осуществляется популяцией кластеров агентов.. На каждой итерации агенты каждого кластера строят свое конкретное дерево Штейнера. Другими словами число решений, формируемых агентами на каждой итерации равно числу кластеров агентов. В работе впервые используется метод двойного непрямого обмена информации. Метод построен на основе композитной структуры феромона и дифференцированного способа его отложения. Каждый агент в кластере Aσ метит путь (ребра маршрута) двумя видами феромона: феромон-1 и феромон-2. Тестирование производилось на бенчмарках. По сравнению с существующими алгоритмами достигнуто улучшение результатов на 6–7%. Вероятность получения глобального оптимума составила 0.94. Временная сложность алгоритма при фиксированных значениях M и T лежит в пределах О(n).

Скачать в PDF

Ключевые слова Дерево Штейнера; новые технологии; принципы; природные механизмы; принятие решений; адаптивная система; кластеры агентов; муравьиная колония; алгоритм; оптимизация.
Библиографический список 1. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ
им. Н.Э. Баумана, 2006.
2. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной ап-паратуры. – М.: Высш. шк., 2002. – 384 с.
3. Promel H.J. and Steger A. The Steiner Tree Problem: A Tour Through Graphs, Algorithms, and Complexity. Friedrich Vieweg and Son, Braunschweig, 2002.
4. Zachariasen M. and Rohe A. Rectilinear group Steiner trees and applications in VLSI design // Mathematical Programming. – 2003. – P. 407-433.
5. Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О. Основные задачи синтеза топологии СБИС. – Ростов-на-Дону: Изд-во РГАСХМ, 2006. – 184 с.
6. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. – Таганрог:
Изд-во ТРТУ, 2003. – 107 c.
7. Курейчик В.М., Лебедев Б.К. Построение минимального связывающего дерева Штейнера на основе метода ветвей и границ // Методы и программы решения оптимизационных задач на графах и сетях. Ч. 2. Материалы 2 всесоюзного совещания. – Новосибирск, 1982. – С. 82-85.
8. Щемелинин В.М. Автоматизация топологического проектирования БИС. – М.: МИЭТ, 2001. – 132 c.
9. Лисин А.В., Файзуллин Р.Т. Эвристический алгоритм поиска приближённого решения задачи Штейнера, основанный на физических аналогиях // Компьютерная оптика.
– 2013. – Т. 37, № 4. – С. 503-510.
10. Рыженко Н.В. Задача построения дерева Штейнера для этапа глобальной трассировки. «Высокопроизводительные вычислительные системы и микропроцессоры» // Труды ИМВС РАН. – М., 2003. – Вып. 4. – С. 96-105.
11. Заглядин Г.Г., Сырцов И.А., Школа А.В. Алгоритм синтеза множества остовных деревьев для выполнения глобальной трассировки заказных СБИС // Известия высших учебных заведений. Электроника. – 2010. – № 5 (85). – С. 36-40.
12. Yang, Z.-X. Geometry Experiment Algorithm Steiner Minimal Tree Problem // Journal of Ap-plied Mathematics. – 2013. – P. 1-10.
13. 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 Pro-gramming at Stanford. – 2002. – No. 1. – P. 195-202.
14. Калашников Р.С. Экспериментальные исследования комбинированного эвристического алгоритм построения дерева Штейнера основанного на методе эволюционного поиска для этапа глобальной трассировки // Известия ТРТУ. – 2005. – № 3.
15. Лебедев В.Б. Построение связывающих сетей на основе роевого интеллекта и генетиче-ской эволюции // Сборник научных трудов XIV Всероссийской научно-технической кон-ференции "Нейроинформатика-2012”. Ч. 2. – М.: Изд-во Физматлит, 2012. – C. 93-103.
16. Tao Huang, Evangeline F.Y. Obstacle-avoiding rectilinear Steiner minimum tree construction: an optimal approach // Proceeding ICCAD '10 Proceedings of the International Conference on Computer-Aided Design San Jose, California, 2010. – P. 610-613.
17. Полежаев П.Н., Миронов А.П., Поляк Р.И. Применение алгоритмов муравьиной колонии в решении задачи Штейнера // Философские проблемы информационных технологий и киберпространства. – 2015. – Вып. № 1. – С. 96-105.
18. 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.
19. OR-Library is collection of test data for a variety of OR problem. – http://mscmga.ms.ic.ac.uk.
20. Warme D.M. A new exact algorithm for rectilinear Steiner trees. INFORMS Conf., San-Diego, California, 1997.
21. Andrew B.K., Mandoiu I. RMST-Pack: Rectilinear minimum spanning tree algorithms. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.
22. 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 In-terconnect Prediction. – 2002. – P. 85-89.
23. Hai Zhou. Efficient Steiner tree construction based on spanning graphs // In Proc. Intl. Symp. on Physical Design. – 2003. – P. 152-157.
24. 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.
25. Chris Chu. FLUTE: Fast lookup table based wirelength estimation technique // In Proc. IEEE/ACM Intl. Conf. on Computer-Aided Design. – 2004. – P. 696-701.
26. GeoSteiner – software for computing Steiner trees. – http://www.diku.dk/geosteiner/.
27. 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.

Comments are closed.