Optimization of Binary Decision Diagrams by Single-Grid Cellular Genetic Algorithm

This paper presents a new approach based on cellular genetic algorithms for the problem of optimizing the variable ordering of binary decision diagrams. The initial population is placed on a bidimensional grid by means of a Kohonen self-organizing map, which acts on the associated feature vectors of chromosomes. The offspring are placed on the grid in the proximity of their parents at a distance that reflects the structural difference from them. Devouring techniques that uses the organizing of the population into clusters based on proximity ensure the selection accomplishes the survival selection. The experimental evaluation demonstrates reliable behavior across the evaluated benchmarks and represents a promising alternative heuristic for BDD minimization.