EMBRYONIC GENETIC ALGORITHM WITH RANDOM GENERATIONAL GROWING STRATEGY FOR OPTIMIZING VARIABLE ORDERING OF BDDS
OCTAV BRUDARU 1, IULIAN FURDU 2, RÜDIGER EBENDT 3 1. Institute of Computer Science, Romanian Academy, Iaşi Subsidiary, “Gh. Asachi” Technical University Iaşi, Department of Management and Production Systems Engineering, Iaşi, Romania, e-mail: brudaru@tuiasi.ro
2. “Vasile Alecsandri” University of Bacău, Department of Mathematics and Informatics, Bacău, Romania, e-mail: ifurdu@ub.ro
3. German Aerospace Center, Institute of Transportation Systems, Berlin, Germany, e-mail: ruediger.ebendt@dlr.de
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.