A general global router using simulated-evolution-based optimization

This work aims to propose a general global router that is easily extendable to multi-objective global routing case. The proposed router uses a maze routing based spanning tree generation algorithm to build an initial solution. The initial solution is optimized using a Simulated Evolution (SimE)-based algorithm. The spanning tree generation algorithm can be used in any layout model (with or without obstacles). The SimE-based optimization algorithm uses selection and allocation operations to optimize the initial solution. The SimE-based optimization is extendable to multi-objective case. In the experiments, the proposed algorithm successfully solved all the test problems in the ISPD´98 suite that comprises of industrial problems.