Annealing-based heuristics and genetic algorithms for circuit partitioningin parallel test generation

In this paper simulated annealing and genetic algorithms are applied to the graph partitioning problem. These techniques mimic processes in statistica l mechanics and biology, respectively, and are the most popular meta-heuris tics or general-purpose optimization strategies. A hybrid algorithm for cir cuit partitioning, which uses tabu search to improve the simulated annealin g meta-heuristics, is also proposed and compared with pure tabu search and simulated annealing algorithms, and also with a genetic algorithm. The solu tions obtained are compared and evaluated by including the hybrid partition ing algorithm in a parallel test generator which is used to determine the t est patterns for the circuits of the frequently used ISCAS benchmark set. ( C) 1998 Elsevier Science B.V. All rights reserved.