To search, Click below search items.


All Published Papers Search Service


Quantum Genetic Algorithm for Binary Decision Diagram Ordering Problem


Abdesslem Layeb, Djamel-Eddine Saidouni


Vol. 7  No. 9  pp. 130-135


The Binary Decision Diagram (BDD) is used to represent in symbolic manner a set of states. It’s largely used in the field of formal checking. The variable ordering is a very important step in the BDD optimization process. A good order of variables will reduce considerably the size of a BDD. Unfortunately, the search for the best variables ordering has been showed NP-difficult. In this article, we propose a new iterative approach called QGABDD based on a Quantum Genetic Algorithm. QGABDD is based on a basic core defined by a suitable quantum representation and an adapted quantum evolutionary dynamic. The obtained results are encouraging and attest the feasibility and the effectiveness of our approach. QGABDD is distinguished by a reduced population size and a reasonable number of iterations to find the best order, thanks to the principles of quantum computing.


Combinatorial problem, Quantum computing, Quantum Genetic Algorithm, Binary Decision Diagram