The evolutionary design of combinational logic circuits offers an innovative approach that often surpasses traditional methods, such as the Quine-McCluskey algorithm, in both efficiency and effectiveness. Cartesian Genetic Programming (CGP) emerges as a potent technique in this domain, enabling versatile circuit designs tailored to diverse requirements such as cost, gate count, and circuit speed. In this paper, we introduce an advanced modification of CGP, termed CGP-SA, which integrates the Simulated Annealing mechanism into the selection operator. This novel approach enhances the algorithm’s ability to escape local optima, thereby fostering the discovery of more optimal solutions. We demonstrate the efficacy of CGP-SA through the design of three types of multipliers and two types of adders, utilizing diverse logic gate sets. This exploration not only reveals the flexibility of CGP-SA in handling various circuit design challenges but also highlights its adaptability to different optimization criteria.