Evolving binary decision diagrams using implicit neutrality

A new algorithm is presented for evolving binary decision diagrams (BDD) that employs the neutrality implicit in the BDD representation. It is shown that an effortless neutral walk is taken; that is, a neutral walk that requires no fitness evaluations. Experiments show the algorithm to be robust and scalable across a range of n-parity problems up to n = 17, and highly efficient on a range of other functions with compact BDD representations. Evolvability and modularity issues are also discussed, and the search space is shown to be free of local optima.