GEORG: VLSI circuit partitioner with a new genetic algorithm framework

This paper suggests a new framework of multidimensional genetic algorithm a nd applies it to the real-world problem of very large scale integration (VL SI) partitioning. The framework consists of a new multidimensional genetic operator, called geographic crossover, and a new genetic encoding scheme. G eographic crossover enables more powerful creation of new solutions by allo wing a diverse mixture of parent solutions. Its theoretical validity is pro ved based on a new view of crossover. The new genetic encoding scheme helps space search by effectively utilizing geographical linkages of genes; The new framework can be incorporated into most existing genetic algorithm (GA) implementations just by replacing the crossover module and leaving the oth er modules intact. For a test suite of 11 ACM/SIGDA VLSI circuit partitioni ng benchmark circuits, the GA under this framework significantly outperform ed recently published state-of-the-art methods as well as a previous GA on linear string.