Approximate BDD Optimization with Prioritized ε-Preferred Evolutionary Algorithm

Saeideh Shirinzadeh, Mathias Soeken, Daniel Große, Rolf Drechsler

In: Genetic and Evolutionary Computation Conference. Genetic and Evolutionary Computation Conference (GECCO) July 20-24 Denver Colorado United States 2016.


Approximate computing has gained high attention in vari-ous applications that can benefit from a reduction in costs bylowering the accuracy. In this paper we present an optimiza-tion approach for functional approximation ofBinary Deci-sion Diagrams(BDDs) which are known for their widespreadapplications in electronic design automation and formal veri-fication. We propose a three-objectiveε-preferred evolution-ary algorithm with the first objective set to the BDD sizewhich is given higher priority to the two other objectives setto errors caused by approximation. This is highly demandedby the application to ensure that the minimum size for theapproximated BDD is accessible when the error metrics meetcertain threshold values. While BDD size minimization isguaranteed by incorporating priority, the use ofεin the pro-posed approach ensures to guide the search towards desirederror values in parallel. Experiments confirm the efficiencyof the proposed approach by a size improvement of 64.24%at a fair cost of 3.86% inaccuracy on average.


Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence