Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit design

• https://link.springer.com/article/10.1007%2Fs10710-021-09416-6

Cartesian genetic programming, Semantic operator, Semantic mutation, Evolutionary
circuit design

Cartesian genetic programming (CGP) represents the most efficient method for the
evolution of digital circuits. Despite many successful applications, however, CGP
suffers from limited scalability, especially when used for evolutionary circuit
design, i.e. design of circuits from a randomly initialized population.
Considering the multiplier design problem, for example, the 5×5-bit multiplier
represents the most complex circuit designed by the evolution from scratch. The
efficiency of CGP highly depends on the performance of the point mutation
operator, however, this operator is purely stochastic. This contrasts with the
recent developments in genetic programming (GP), where advanced informed
approaches such as semantic-aware operators are incorporated to improve the
search space exploration capability of GP. In this paper, we propose
a semantically-oriented mutation operator (SOMOk) suitable for the evolutionary
design of combinational circuits. In contrast to standard point mutation
modifying the values of the mutated genes randomly, the proposed operator uses
semantics to determine the best value for each mutated gene. Compared to the
common CGP and its variants, the proposed method converges on common Boolean
benchmarks substantially faster while keeping the phenotype size relatively
small. The successfully evolved instances presented in this paper include 10-bit
parity, 10 + 10-bit adder and 5×5-bit multiplier. The most complex circuits were
evolved in less than one hour with a single-thread implementation running on
a common CPU.