EMBRYONIC GENETIC ALGORITHM WITH RANDOM GENERATIONAL GROWING STRATEGY FOR OPTIMIZING VARIABLE ORDERING OF BDDS

  • OCTAV BRUDARU
    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
    brudaru@tuiasi.ro
  • IULIAN FURDU
    “Vasile Alecsandri” University of Bacău, Department of Mathematics and Informatics, Bacău, Romania
    ifurdu@ub.ro
  • RÜDIGER EBENDT
    German Aerospace Center, Institute of Transportation Systems, Berlin, Germany
    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.

Cuvinte cheie

BDD OBDD Optimization GA