A GENETIC ALGORITHM FOR RKRO MINIMIZATION

We show that there is a close relation between Ordered Kronecker Funct ional Decision Diagrams (OKFDDs) and two-level AND/EXOR expressions. T his relation, together with efficient OKFDD algorithms, can be utilize d for exact and heuristic minimization of these AND/EXOR expressions, called Reduced Kronecker Expressions (RKROs). RKROs depend on the Vari able Ordering (VO) and Decomposition Type List (DTL) of the correspond ing OKFDD. We propose several (exact and heuristical) minimization alg orithms for fixed VO and perform experimental results. A Genetic Algor ithm (GA) is applied to minimize RKROs with respect to VO and DTL in p arallel. We applied our GA to a large set of benchmark functions to sh ow the efficiency of our approach. Copyright (C) 1997 Elsevier Science Ltd