Article

Article title GLOBAL ROUTING GENETIC ALGORITHM BASED ON ALTERNATIVES OF CONSTRUCTING THE ROUTE
Authors V.B. Lebedev, A.A. Shashelov
Section SECTION I. EVOLUTIONARY MODELLING, GENETIC AND BIONIC ALGORITHMS
Month, Year 07, 2012 @en
Index UDC 681.325
DOI
Abstract In this paper, we present a new genetic algorithm for solving the global routing problem. The main idea of the algorithm is the coding alternatives of constructing the route in the vertices of the graph. This paper describes the principles for encoding and decoding of the chromosome in a compact form, also describes the genetic operators. Which distinctive line is that real placing of connection on areas is coded not, and procedure of its construction on a switching field, and a code is number in binary system of calculations. Process of construction of a route consists in consecutive moving on edges graph G from vertex to vertex, according to the set code. It considerably simplifies performance of genetic operators and reduces volume of necessary memory. Labour input coding and chromosome decoding has linear complexity O (L), where L - length of a chromosome. Experimental researches were spent on IBM PC. Compared with existing algorithms achieved better results.

Download PDF

Keywords Genetic algorithm; global routing; optimization.
References 1. Chang Y., Cheng K., Wang L. Electronic Design Automation: Synthesis, Verification, and Test. Elsevier Science, 2009.
2. Bozorgzadeh E., Kastner R., Sarrafzadeh M. Pattern routing: use and theory for increasing predictability and avoiding coupling // IEEE Trans. on CAD. – 2002. – № 21 (7). – P. 777-790.
3. Cho M., Pan D.Z., Puri R., Xiang H. Wire Density Driven Global Routing for CMP Variation and Timing, in Proc. Int. Conf. on Computer Aided Design, 2006.
4. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектировании СБИС. Монография. – Таганрог: Изд-во ТРТУ, 2000. – С. 107-128.
5. Курейчик В.М., Лебедев Б.К. Методы эволюционной адаптации при решении комбинаторных задач // Материалы XV Международной конференции по нейрокибернетике. Т. 2.
– Ростов-на-Дону: Изд-во ЮФУ, 2009. – С. 98-101.
6. Курейчик В.М., Кажаров А.А.Использование роевого интеллекта в решении NP-трудных задач // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 30-36.
7. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 28-32.
8. Лебедев О.Б. Глобальная трассировка на основе муравьиного алгоритма // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 94-102.
9. Лебедев Б.К., Лебедев В.Б.. Глобальная трассировка на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 32-39.
10. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 37-44.
11. Лебедев В.Б., Лебедев О.Б. Генетический алгоритм глобальной трассировки на основе иерархических многохромосомных представлений // Интеллектуальные системы. Коллективная монография / Под ред. В.М. Курейчика. – М.: Физматлит, 2009. – С. 88-105.
12. Лебедев О.Б. Дотрассировка (перетрассировка) соединений на основе гибридизации волнового и муравьиного алгоритмов // Труды конгресса по интеллектуальным системам и информационным технологиям «IS– IT’10». Научное издание в 4-х томах. Т. 2. – М.: Физматлит, 2011. – С. 48-56.
13. Курейчик В.М. Модифицированные генетические операторы // Известия ЮФУ. Технические науки. – 2009. – № 12 (101). – С. 7-15.
14. FGR 1.1. [Online]. Available: http://vlsicad.eecs.umich.edu/BK/FGR.

Comments are closed.