ДВУХУРОВНЕВЫЙ АЛГОРИТМ РАЗБИЕНИЯ ГРАФА НА ЧАСТИ

  • В.В. Курейчик Южный Федеральный Университет
  • Д.В. Заруба Южный Федеральный Университет
Ключевые слова: Комбинированный поиск, оптимизация, графы, генетический алгоритм, агрегация фракталов

Аннотация

Рассмотрена одна из важных проблем дискретной оптимизации – решение комби-наторно-логических задач на графах. Данные задачи относятся к классу NP-сложных, NP-трудных проблем оптимизации. В статье приведено описание оптимизационной задачи разбиения графа на части и сформулирована постановка задачи. Для эффективного реше-ния данной задачи авторы предлагают новую стратегию «поиск-эволюция». На основе этой стратегии в работе предложена новая архитектура поиска, основанная на много-уровневом подходе. Принципиальным отличием предложенного подхода является разделе-ние процесса поиска на два этапа и применение на каждом из этих этапов различных ме-тодов. На первом этапе поиска предлагается выделение кластеров. На втором этапе по-иска, в качестве метода оптимизации, предложен генетический алгоритм, позволяющий производить эффективную перестановку построенных кластеров. На основе предложен-ной архитектуры разработан двухуровневый алгоритм, позволяющий распараллеливать процесс решения и получать наборы оптимальных и квазиоптимальных решений за время, сопоставимое со временем реализации итерационных алгоритмов. Разработанный алго-ритм был реализован на языке программирования C#. Проведены два вида вычислительного эксперимента на тестовых примерах бенчмарках. Это разбиение графа на 4 и 8 частей. Результаты проведенных исследований показывают, что разработанный подход доста-точно быстро позволяет получать более эффективные решения, т.к. полученные резуль-таты в среднем на 5 % лучше, чем разбиения, полученные с использованием известных ал-горитмов HMetis PGA Complex, что говорит об эффективности предложенного подхода. ВСА лежит в пределах.

Литература

1. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ им. Баумана, 2006. – 448 с.
2. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition. – Kluwer Academic Publisher, USA, 2013.
3. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. General ques-tions of automated design and engineering // Studies in Computational Intelligence. – 2009. – Vol. 212. – P. 1-22.
4. Курицкий Б.Я. Оптимизация вокруг нас. – Л.: Машиностроение, 1989. – 145 с.
5. Корниенко В.П. Методы оптимизации. – М.: Высшая школа, 2007. – 663 с.
6. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа // Известия Рос-сийской академии наук. Теория и системы управления. – 1999. – № 4. – С. 79-87.
7. Курейчик В.В., Курейчик Вл.Вл. Биоинспирированный алгоритм разбиения схем при проектировании СБИС // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 23-29.
8. Kureichik, V., Zaruba, D., Kureichik, Vl. Hybrid approach for graph partitioning // Advances in Intelligent Systems and Computing. – 2017. – Vol. 573. – P. 64-73.
9. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ. – М.: МЦМО, 2000. – 893 c.
10. Мандельброт Б. Фрактальная геометрия природы. – М.: Институт компьютерных ис-следований, 2002. – 656 с.
11. Курейчик Вл.Вл. Многоуровневый подход решения задачи размещения фрагментов СБИС на основе механизма агрегации фракталов // XII Всероссийская научная конфе-ренция молодых ученых, аспирантов и студентов «Информационные технологии, сис-темный анализ и управление» (ИТСАиУ-2015). – Ростов-на-Дону: Изд-во ЮФУ, 2015. – С. 184-188. 12. Hendrickson B., Leland R. A Multilevel Algorithm for Partitioning Graphs // Proceeding Super-computing '95 Proceedings of the 1995 ACM/IEEE conference on Supercomputing Article No. 28. 13. Schloegel K., Karypis G., Kumar V. Multilevel diffusion schemes for repartitioning of adaptive meshes // Technical Report 97-013, University of Minnesota, Department of Computer Sci-ence, 1997.
14. Barnard S.T., Simon H.D. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems // Proceedings 6th SIAM Conf. Parallel Processing for Sci-entific Computing. – 1993. – P. 711-718.
15. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации (обзор) // Кибернетика и программирование. – 2017. – № 3. – С. 51-79.
16. Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик // Программные системы и вычислительные методы. – 2016. – № 2. – С. 158-172.
17. Kurejchik V.V., Kurejchik V.M. On genetic-based control // Автоматика и телемеханика. – 2001. – № 10. – С. 174-187.
18. Holland John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. – USA: University of Michigan, 1975.
19. Курейчик Вл.Вл., Курейчик Л.В. Программная реализация гибридного подхода для реше-ния задачи размещения фрагментов СБИС // IV Всероссийская научно-техническая конференция молодых ученых, аспирантов и студентов «Фундаментальные и приклад-ные аспекты компьютерных технологий и информационной безопасности». – Ростов-на-Дону – Таганрог: Изд-во ЮФУ, 2018. – С. 301-305.
20. IBM-PLACE 2.0 benchmark suits. – http://er.cs.ucla.edu/benchmarks/ibm-place2/bookshelf/-ibm-place2-all-bookshelf-nopad.tar.gz.
21. Alpert C.J. The ISPD-98 Circuit Beanchmark Suit // in Proc. ACM/IEEE International Sympo-sium on Physical Design. – April 1998. – P. 80-85.
Опубликован
2019-07-23
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ