Ant Algorithm for Determining of Critical Connections in VLSI

摘要

The paper deals with a modified ant algorithm for the determination of critical connections in VLSI using as an example a traveling salesman problem. This algorithm is a part of the swarm intelligence method, which is one of the bioinspired approaches that describe the collective behavior of a decentralized self-organizing system. It consists of a set of agents (ants) interacting with each other and with the environment. The paper presents the statement of the traveling salesman problem. The described modified ant algorithm allows to obtain sets of quasi-optimal solutions in polynomial time. Series of tests and experiments made it possible to specify theoretical estimates of the algorithms' time complexity and their behavior for graphs with different structures. The time complexity is represented as O(nlogn) at the best case, O(n3) at the worst case.