The Efficient Hybrid Approach to Channel Routing Problem
Known as an NP-Complete problem, the channel routing problem is very important in the automatic layout design of VLSI circuit and printed circuit boards. A distributed hybrid algorithm for this channel routing problem is presented in MPI environments. This system is implemented on a network of personal computers running Linux operating system connected via 100Mbps Ethernet. Each slave processor generates its own sub-population using genetic operations and communicates with the master processor in an asynchronous manner to form the global population. The proposed hybrid algorithm of mean field annealing and simulated annealing-like genetic algorithm combines the benefit of rapid convergence property of MFA and the effective genetic operations of SGA.