SAGA : a unification of the genetic algorithm with simulated annealing and its application to macro-cell placement

Abstract

In this paper a stochastic optimization algorithm called SAGA is presented, which is a generalization of the genetic algorithm and the simulated annealing algorithm. Depending on the settings of its control parameters, SAGA executes as a genetic algorithm, a simulated annealing algorithm, or a mixture of these. SAGA represents an application independent approach to optimization, and the resulting search process is highly adaptive. The performance of the approach on the macro-cell placement problem is examined. It is experimentally shown that a mixture of the genetic algorithm with simulated annealing yields higher layout quality than a pure genetic algorithm. Furthermore, layout qualities obtained by SAGA on MCNC benchmarks are comparable to or better than previously published results.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>