Embryonic genetic algorithm with random generational growing strategy for optimizing variable ordering of BDDs

Kurzfassung

This paper addresses the problem of optimizing the variable ordering in Binary Decision Diagrams (BDDs). A new hybrid embryonic genetic algorithm is proposed for optimizing the variable ordering that combines a branch & bound technique with the basic genetic algorithm. It uses fitness based on a lower bound and embryos instead of full chromosomes. A novel growing technique introduces two new growing operators. The results of an experimental evaluation demonstrate the efficiency of the approach.