A multiple-population evolutionary approach to gate matrix layout

Abstract

This paper deals with a Very-Large-Scale Integrated systems design problem that belongs to the NP(Nondeterministic Polynomial)-hard class. The Gate Matrix Layout problem has numerous applications in the chip-manufacturing industry and in other industrial settings. A memetic algorithm is employed to solve a set of benchmark instances, and numerical comparisons with a highly competitive method—a microcanonical optimization approach—are performed. Beyond the effectiveness of the method, shown by the results obtained for these instances, an additional goal of this work is to study how the performance of the algorithm is affected by the use of multiple populations and of different individual-migration policies between such populations. The results signal a strong performance improvement of multiple populations over single population approaches. Finally, the proposed algorithm presents several refinements, like structured populations and a specially tailored local search.

Acknowledgements

This work was supported by the NBI program of the University of Newcastle, ‘Fundação de Amparo à Pesquisa do Estado de São Paulo’ (FAPESP—Brazil) and the PROPESQUISA program of the Getulio Vargas Foundation.