An Adaptive Multimeme Memetic Algorithm for the VLSI Standard Cell Placement Problem

Placement has a tremendous impact on the final performance of a VLSI chip, and the problem itself is a combinatorial optimization problem. Memetic algorithms with problem-specific designs can solve the problem with high quality solutions, but they are generally time-consuming. To address this issue, adopting an adaptive strategy has become a key way to reduce the runtime of a memetic algorithm. In this paper, we present an adaptive multimeme memetic algorithm (AMMA) for the VLSI standard cell placement problem. In accordance with the distinctive features of the solution space of the problem, we propose a set of adaptive strategies to greatly improve the runtime efficiency. The main novelty of the proposed strategy lies in its constructing of crossover multimeme and the acceptance criteria of placement candidates. The experimental results and comparisons on Peko suite3 and ISPD04 benchmark circuits verified the efficacy and efficiency of the proposed adaptive strategies. Compared to the memetic algorithm without these main adaptive strategies, the AMMA reduces the runtime by around 32.58% on average.