论文标题
进化回路设计的笛卡尔遗传编程中的语义为导向的突变操作员
Semantically-Oriented Mutation Operator in Cartesian Genetic Programming for Evolutionary Circuit Design
论文作者
论文摘要
尽管有许多成功的应用，但笛卡尔遗传编程（CGP）的可扩展性有限，尤其是用于进化电路设计时。例如，考虑到乘数设计问题，5x5位乘数代表了从随机生成的初始种群演变而来的最复杂的电路。 CGP的效率高度取决于点突变算子的性能，但是，该操作员纯粹是随机的。这与遗传编程（GP）的最新发展形成鲜明对比，在该发展中，诸如语义感知操作员之类的先进知情方法被合并以提高GP的搜索空间探索能力。在本文中，我们提出了一个以语义为导向的突变算子（SOMO），适合组合电路的进化设计。 SOMO使用语义来确定每个突变基因的最佳价值。与常见的CGP及其变体以及最新版本的语义GP相比，所提出的方法在常见的布尔基准上收敛得更快，同时保持表型尺寸相对较小。本文提出的成功发展的实例包括10位奇偶校验，10+10位加法器和5x5位乘数。最复杂的电路在不到一小时的时间内进化，而在普通CPU上运行了单线程实现。
Despite many successful applications, Cartesian Genetic Programming (CGP) suffers from limited scalability, especially when used for evolutionary circuit design. Considering the multiplier design problem, for example, the 5x5-bit multiplier represents the most complex circuit evolved from a randomly generated initial population. 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 (SOMO) suitable for the evolutionary design of combinational circuits. SOMO uses semantics to determine the best value for each mutated gene. Compared to the common CGP and its variants as well as the recent versions of Semantic GP, 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 5x5-bit multiplier. The most complex circuits were evolved in less than one hour with a single-thread implementation running on a common CPU.
