Статья

Название статьи КО-ЭВОЛЮЦИОННЫЙ АЛГОРИТМ ТРАССИРОВКИ, ОСНОВАННЫЙ НА МЕТОДЕ МУРАВЬИНОЙ КОЛОНИИ
Автор Б. К. Лебедев, О. Б. Лебедев, Е. О. Лебедева
Рубрика РАЗДЕЛ I. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 04, 2018
Индекс УДК 004.896
DOI
Аннотация Для решения задачи канальной трассировки (ЗКТ) предложен ко-эволюционный алгоритм, основанный на методе муравьиной колонии. Ко-алгоритм предполагает параллельное функционирование заданного числа субалгоритмов муравьиной колонии, которые используют различные, но изоморфные стратегии поиска. Предложенный подход позволяет организовать систему коллективной адаптации с высокой степенью целесообразного поведения и сходимости. Ключевая проблема, которая была решена в данной работе, связана с разработкой принципов взаимодействия субпопуляций, отличающиеся стратегиями поиска интерпретаций решений в изоморфных средах функционирования. Периодически агенты мигрируют из одной субпопуляции в другую, передавая свой опыт. В качестве интерпретации решения ЗКТ используется список. Каждый список фактически является косвенной (числовой) схемой кодирования решения ЗКТ. Декодер – оператор, осуществляющий укладку горизонтальных фрагментов по заложенным в нем правилам, позволяющий перейти от косвенной (числовой) схемы кодирования решения задачи к фенотипу. Список декодируется в графическое представление решения (эскиз) только с использованием соответствующей ему стратегии. Основная цель сводится к нахождению такого списка, для которого с помощью последовательной процедуры декодирования фрагменты цепей размещаются в минимальном числе магистралей. Для построения конструктивной (встроенной) процедуры поиска решения муравьем используется модифицированный алгоритм левого конца. Последовательное построение маршрута фактически является процессом последовательного размещения горизонтальных фрагментов в магистралях. Для усиления сходимости алгоритма и способности выхода из локальных оптимумов разработана комбинированная оценка, характеризующая преимущество выбора данной вершины, для включения ее в формируемый маршрут. В основу расчета вероятности включения вершины в формируемый маршрут положены эвристические соображения о предпочтениях того, что вершина входит в состав оптимального маршрута. Ко-эволюционный подход обеспечивает более широкий обзор пространства решений и более высокую вероятность локализации глобального экстремума задачи. По сравнению с существующими алгоритмами достигнуто улучшение качества решений до 5 %.

Скачать в PDF

Ключевые слова Биоинспирированная оптимизация; ко-эволюционный алгоритм; муравьиный алгоритм; гибридизация; субпопуляция; канальная трассировка; декодер.
Библиографический список 1. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. – Таганрог: Изд-во ТРТУ, 2003. – 96 с.
2. Sarrafzadeh M. and Wong C.K. An Introduction to VLSI Physical Design. – New York: McGraw Hill, 1996. – 198 р.
3. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. – М.: Высш. шк., 2002. – 156 с.
4. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 448 с.
5. Dorigo M. and Stützle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004. – 187 р.
6. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. – Таганрог: Изд-во ЮФУ, 2013. – 199 с.
7. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation. Helsinki University of Technology, TKK Dissertations, Espoo, 2009. – 161 p.
8. Лебедев Б.К., Лебедев О.Б., Лебедев В.Б. Гибридизация роевого интеллекта и генетической эволюции на примере размещения // Программные продукты, системы и алгоритмы. – 2017. – № 4.
9. Воробьева Е.Ю., Карпенко А.П., Селиверстов Е.Ю. Ко-гибридизация алгоритмов роя частиц // Наука и образование. – 2012. – № 4. – Режим доступа: http://www.technomag.edu.ru/doc/355729.html.
10. Лебедев О.Б. Трассировка в канале методом муравьиной колонии // Известия ЮФУ. Технические науки. – 2009. – № 2 (91). – С. 46-52.
11. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 37-44.
12. Cong J., Romesis M., and Xie M. Optimality, Scalability and Stability Study of Partitioning and Placement Algorithms // Proc. of the International Symposium on Physical Design, Monterey, CA. – 2003. – P. 88-94.
13. MCNC Electronic and Information Technologies (Online). Available: www.mcnc.org.
14. Yoshimura T. аnd Kuh E.S. Efficient algorithms for channel routing // IEEE Trans. Computer Aided Design Integrated Circuits & Syst. – 1982. – Vol. 1, No. 1. – P. 25-35.
15. Yan T. and Wong M.D.F. BSG-Route: A Length-Constrained Routing Scheme for General Planar Topology // In Proc. Int. Conf. Comp.- Aided Des. – 2008. – P. 499-505.
16. Кныш Д.С., Курейчик В.М. Генетический алгоритм трассировки коммутационных блоков // Известия вузов. Электроника. Схемотехника и проектирование. – 2009. – № 5 (79). – C. 28-34.
17. Лебедев Б.К., Лебедев О.Б., Лебедева Е.О. Модифицированный муравьиный алгоритм построения минимального дерева Штейнера // Известия ЮФУ. Технические науки.
–2017. – № 7 (192). – С. 38-53.
18. Лебедев О.Б., Пурчина О.А. Роевой алгоритм трассировки в приканальной надъячеечной области // Известия ЮФУ. Технические науки. – 2015. – № 6 (167). – С. 41-51.
19. Kureichik V.M., Lebedev В.К., Lebedev O.B. Channel Routing Based on Ant Colony Adaptive Behavior Model // Journal of Computer and Systems Sciences International. – 2015. – Vol. 54, No. 2. – P. 278-293. ISSN 10642307.
20. Лебедев О.Б., Лебедева Е.М., Орлов А.Н. Решение задачи трассировки с помощью ортогональных деревьев Штейнера // Информатика, вычислительная техника и инженерное образование. – 2014. – № 2 (17).

Comments are closed.