Genetic Simulated Annealing and Application to Non-slicing Floorplan Design 1996

Abstract:  Introduction 1 1 Introduction Most of VLSI layout problems can be formulated as combinatorial optimization problems and are proven to be NP-hard or NP-complete problems. Simulated annealing (SA) [1, 2] and Genetic algorithm (GA) [3, 4] are heuristics for combinatorial optimization problems and have been successfully used for various problems in the CAD area [5, 6, 7, 8, 9]. While SA is very powerful for searching local regions of the solution space exhaustively via stochastic hill climbing, GA is very powerful for searching large regions of the solution space roughly and globally using crossover operations. Combining the local hill climbing features of SA and the global crossover operations of GA, we propose a new optimization method, named Genetic Simulated Annealing (GSA). We apply GSA to non-slicing floorplan design problems to demonstrate the advantages of GSA over SA. The rest of the paper is organized as follows. We discuss the characteristics of SA and G