A multi-objective evolutionary algorithm for channel routing problems

Abstract

The channel routing problem (CRP) is derived from detailed routing model in VLSI design. The objectives of the problem can vary from reducing the number of horizontal tracks to minimizing the number of vias, length of wires used etc. It is not known how these objectives interact with one another, although it is believed that they are conflicting in nature. Unlike traditional single-objective optimization approaches, this paper presents a multiobjective evolutionary algorithm (MOEA) for CRP. Specialized genetic operators for solving the CRP are devised. In addition, a new method of random routing is introduced for better routing performance. Some standard benchmark problems are solved in this paper using the proposed algorithm to validate its performance. It is shown that the proposed algorithm is consistent and is able to obtain very competitive results as compared to well-known approaches. © Springer-Verlag Berlin Heidelberg 2007.