CCGP: A Cooperative Coevolutionary Cartesian Genetic Programming Algorithm for Finite State Machine Synthesis

Abstract

The automated synthesis of sequential circuits remains a core challenge in electronic design automation. When synthesizing finite state machines (FSMs), traditional Cartesian genetic programming (CGP) typically relies on a monolithic representation that couples state and output logic into a single high-dimensional decision vector. This approach triggers a search space “curse of dimensionality” and induces significant evaluation noise due to intense variable interactions, severely limiting scalability in complex logic design. To address these issues, we propose a cooperative coevolutionary Cartesian genetic programming (CCGP) algorithm. Using the divide-and-conquer mechanism, CCGP functionally decomposes the FSM into two parallel-evolving subpopulations based on the Mealy machine model: next-state logic (NSL) and output logic (OL). To overcome the subcomponent fitness evaluation challenge in coevolution, we introduce a cross-population elite ensemble mechanism. By evaluating candidate individuals against an “elite committee” sampled from the partner population, this method significantly reduces random fitness variance and stabilizes selection pressure. Experimental evaluations across a diverse set of sequential circuit benchmarks demonstrate that CCGP significantly outperforms standard CGP and genetic programming (GP). Results show substantial improvements in both success rates and convergence stability. These findings prove that CCGP’s functional decoupling effectively prevents evolutionary stagnation caused by functional conflicts, drastically enhancing the discovery of globally optimal solutions and providing an efficient, robust new paradigm for automated sequential logic design.