Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Ant algorithm for determining the critical linkages in VLSI

Authors
 Zaporozhets D.Yu.
 Zaruba D.V.
 Kureichik V.V.
Date of publication
 2014

Abstract
 In this article the modified ant algorithm for determining the critical VLSI paths using the traveling salesman problem and experimental investigation of its characteristics is suggested. This algorithm is a part of the swarm intelligence method, which is one of bioinspired approaches, describing the collective behavior of a decentralized self-organizing system, containing a variety of agents (ants), locally interacting with each other and with the environment. The task of definition of the traveling salesman problem is described in suggested article. The modified ant algorithm, which is capable of obtaining suboptimal solutions sets is described. Series of tests and experiments allowed to specify the theoretical estimation of the time complexity of the algorithm and optimize their behavior for various structures of graphs. In the best case, the time complexity of the algorithm ~ O (n logn), and in the worst case - O (n3).
Keywords
 optimization, traveling salesman problem, multiagent system, the ant algorithm
Library reference
 Zaporozhets D.Yu., Zaruba D.V., Kureichik V.V. Ant algorithm for determining the critical linkages in VLSI // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2014. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2014. Part 2. P. 107-112.
URL of paper
 http://www.mes-conference.ru/data/year2014/pdf/D114.pdf

Copyright © 2009-2024 IPPM RAS. All Rights Reserved.

Design of site: IPPM RAS