Genetic Algorithms for the Variable Ordering Problem of Binary Decision Diagrams

Wolfgang LendersWolfgang Lenders, Christel BaierChristel Baier

DOI Link

Wolfgang Lenders, Christel Baier
Genetic Algorithms for the Variable Ordering Problem of Binary Decision Diagrams
Proc. of the 8th International Workshop on Foundations of Genetic Algorithms (FOGA), volume 3469 of Lecture Notes in Computer Science, 1--20, 2005. Springer

Details
Bibtex

KurzfassungAbstract
Ordered binary decision diagrams (BDDs) yield a data structure for switching functions that has been proven to be very useful in many areas of computer science. The major problem with BDD-based calculations is the variable ordering problem which addresses the question of finding an ordering of the input variables which minimizes the size of the BDD-representation. In this paper, we discuss the use of genetic algorithms to improve the variable ordering of a given BDD. First, we explain the main features of an implementation and report on experimental studies. In this context, we present a new crossover technique that turned out to be very useful in combination with sifting as hybridization technique. Second, we provide a definition of a distance graph which can serve as formal framework for efficient schemes for the fitness evaluation.
Forschungsgruppe:Research Group: Verifikation und formale quantitative Analyse„Verifikation und formale quantitative Analyse“ befindet sich nicht in der Liste (Computational Logic, Automatentheorie, Wissensverarbeitung, Knowledge-Based Systems, Knowledge Systems, Wissensbasierte Systeme, Logische Programmierung und Argumentation, Algebra und Diskrete Strukturen, Knowledge-aware Artificial Intelligence, Algebraische und logische Grundlagen der Informatik) zulässiger Werte für das Attribut „Forschungsgruppe“.Algebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/11513575_1.

@inproceedings{LB2005,
  author    = {Wolfgang Lenders and Christel Baier},
  title     = {Genetic Algorithms for the Variable Ordering Problem of Binary
               Decision Diagrams},
  booktitle = {Proc. of the 8th International Workshop on Foundations of Genetic
               Algorithms (FOGA)},
  series    = {Lecture Notes in Computer Science},
  volume    = {3469},
  publisher = {Springer},
  year      = {2005},
  pages     = {1--20},
  doi       = {10.1007/11513575_1}
}