Extensions of Cartesian Genetic Programming for Optimization of Complex Combinational Circuits

Evolution and optimization of digital circuits using standard Cartesian Genetic Programming (CGP) is not scalable mainly because the evaluation time grows exponentially with increasing number of circuit inputs. We propose to combine two extensions of CGP to improve post-synthesis optimization capabilities of CGP. Firstly, we replace the standard fitness function by an equivalence checking algorithm which significantly reduces the fitness evaluation time for complex circuits. Secondly, we propose to modify the selection strategy of CGP to increase the number of functionally correct solutions that can be created using a mutation operator. Proposed extensions of CGP are evaluated using the LGSynth93 benchmark circuits. Experimental results show that extended CGP can significantly reduce the number of gates (area reduced by 24% on average) in benchmark circuits for the cost of runtime in comparison to conventional methods such as SIS and ABC.