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

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

Аннотация

Рассматривается основная проблема искусственного интеллекта - разработка эф-
фективных новых и модифицированных эвристических механизмов поиска оптимального
решения. В настоящее время одним из перспективных направлений развития искусственного
интеллекта служат вопросы применения методов и моделей поведения биологических сис-
тем для решения NP-полных и NP-трудных оптимизационных задач. В статье рассмотрена
одна из актуальных задач конструкторского проектирования сверхбольших интегральных
схем (СБИС) - задача размещения. Представлена постановка задачи размещения элементов
СБИС. Задачу размещения элементов СБИС предложено решать на основе поведения биоло-
гических систем в природе, на примере алгоритма волчьей стаи. Волки являются типичными
социальными животными, имеющими четкое разделение социальной работы. Представлены
действия и правила поведения волчьей стаи в живой природе. На основе представленных
правил и действий волков, описан модифицированный алгоритм волчьей стаи. Преимущест-
вом разработанного модифицированного алгоритма является возможность улучшения каж-
дой последующей стадии решения задачи размещения. В рамках работы алгоритм волчьей
стаи был реализован на языке Java. В качестве тестовых схем использовались известные
бенчмарки фирмы IBM. Сравнения проводились с результатами работы известных алгорит-
мов: Capo 8.6, Feng Shui 2.0, Dragon 2.23. На основе проведенных исследований, разработан-
ный алгоритм волчьей стаи показал результаты выше, по сравнению с аналогами.

Литература

1. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ им.
Н.Э. Баумана, 2010.
2. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохнов-
ленные природой: учеб. пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014.
3. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов
СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
4. Sherwani N.A. Algorithms for VLSI Physical Design Automation. – Third Edition, Kluwer
Academic Publisher, USA, 2013.
5. Родзин С.И., Курейчик В.В. Состояние, проблемы и перспективы развития биоэвристик
// Программные системы и вычислительные методы. – 2016. – № 2. – С. 158-172.
6. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития
когнитивных биоинспирированных алгоритмов оптимизации (обзор) // Кибернетика и
программирование. – 2017. – № 3. – С. 51-79.
7. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов
СБИС// Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
8. Kureichik, V., Jr., Kureichik, V., Bova, V. Placement of VLSI fragments based on a multilayered
approach // Advances in Intelligent Systems and Computing. – 2016. – Vol. 464.
– P. 181-190.
9. Кулиев Э.В., Лежебоков А.А. О гибридном алгоритме размещения компонентов СБИС //
Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 188-192.
10. Кулиев Э.В., Кравченко Ю.А., Логинов О.А., Запорожец Д.Ю. Метод интеллектуального
принятия эффективных решений на основе биоинспирированного подхода // Известия
Кабардино-Балкарского научного центра РАН. – 2017. – № 6-2 (80). – С. 162-169.
11. Курейчик В.В., Бова В.В., Курейчик Вл.Вл. Биоинспирированный поиск в задачах конст-
рукторского проектирования и оптимизации // Информационные технологии в науке,
образовании и управлении / под ред. проф. Е.Л. Глориозова. – 2015. – С. 427-432.
12. Madadi M. Motlagh. Optimal Control of DC motor using Grey Wolf Optimizer Algorithm -
Technical Journal of Engineering and Applied Science. – 2014-4-04/373-379.
13. Rezaei H., Bozorg-Haddad O., Chu X. Grey wolf optimization (GWO) algorithm // Studies in
Computational Intelligence. – 2018. – Vol. 720. – P. 81-91.
14. Кулиев Э.В., Курейчик В.В., Курситыс И.О. Принятие решений в задаче размещения
компонентов СБИС на основе модели поведения стаи волков // Международная конфе-
ренция по мягким вычислениям и измерениям. – 2018. – Т. 1. – С. 712-715.
15. Кулиев Э.В., Щеглов С.Н., Пантелюк Е.А., Кулиева Н.В. Адаптивный алгоритм стаи се-
рых волков для решения задач проектирования // Известия ЮФУ. Технические науки.
– 2017. – № 7 (192). – С. 28-38.
16. Кулиев Э.В., Лежебоков А.А. О гибридном алгоритме размещения компонентов СБИС //
Известия ЮФУ. Технические науки. –2012. – № 11 (136). – С. 188-192.
17. Кулиев Э.В., Лежебоков А.А. Исследование характеристик гибридного алгоритма раз-
мещения // Известия ЮФУ. Технические науки. – 2013. – № 3 (140). – С. 255- 261.
18. IBM-PLACE 2.0 benchmark suits. – http://er.cs.ucla.edu/benchmarks/ibmplace2/
bookshelf/ibm-place2-all-bookshelf-nopad.tar.gz.
19. Adya, S.N., Markov, I.L. Combinatorial techniques for mixed-size placement // ACM Transactions
on Design Automation of Electronic Systems. – 2005. – No. 10 (1). – P. 58-90.
20. Wang M., Yang X., Sarrafzadeh M. Dragon2000: Standard-cell Placement Tool for Large Industry
Circuits – ICCAD2000. – P. 260-263.
Опубликован
2019-11-13
Выпуск
Раздел
Раздел III. Автоматизация проектирования