Cell Division Genetic Algorithm for Component Allocation Optimization in Multi-Functional Placers

Solving a newly defined component allocation problem by the proposed cell division genetic algorithm (CDGA), this paper effectively optimizes all the objectives of the pickup-and-place (PAP) optimization in a multi-functional placer, which remains a formidable challenge till now. The CDGA applies a decoding heuristic that reduces the problem dimension and allocates several components of the same type as one unit, namely a component cell. When a better allocation can no longer be found by allocating the current cells, the cell division operation is performed to divide each cell into two new cells. The new cells are then used in the next round of GA optimization, which may further optimize the allocation. In experiments using the industrial PCB samples, the proposed algorithm provides a significant improvement compared to the built-in optimizer of the widely-used multi-functional placer, Samsung SM482, which demonstrates its effectiveness and superiority.