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
Abstract
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.