使用符号回归优化电路结构

原理

作为一种一种监督学习方法，符号回归（symbolic regression）试图发现某种隐藏的数学公式，以此利用特征变量预测目标变量。

编码方法

公式可以写成S-表达式的形式，继而可以转化成一颗二叉树。在这个二叉树里，所有的叶节点都是变量或者常数，内部的节点则是函数。
用同构的思想不难发现：电路的本质也是表达式。
叶子节点可以是元器件（变量和常数）
内部节点可以是二元拓扑关系（函数）

元器件定义为如下形式：
\(X\Rightarrow \{O,M\}\)
\(O\)表示该器件向上层显示的接口数
\(M\)表示该器件的属性

二元拓扑关系\(P\)不妨定义为如下形式：
\(P\Rightarrow <LS,RS>\Rightarrow \{O,L,R,C\}\)
\(O\)表示该关系向上层显示的接口数
\(L\)表示该关系左儿子的接口数
\(R\)表示该关系右儿子的接口数
\(C\)表示该关系左右儿子接口的连接方式

繁殖策略

交叉

原策略：优胜者内随机选择一个子树，替换为另一棵公式树的随机子树。

新增要求：只有根节点的\(O\)数值相同的子树可以替换。

变异

子树变异（Subtree Mutation）
原策略：优胜者的一棵子树将被另一棵完全随机的全新子树代替。

新增要求：随机新子树的根节点的\(O\)数值固定。

hoist变异（Hoist Mutation）
hoist变异是一种对抗公式树膨胀（bloating，即过于复杂）的方法。
原策略：从优胜者公式树内随机选择一个子树A，再从A里随机选择一个子树B，然后把B提升到A原来的位置，用B替代A。

新增要求：子树B的根节点的\(O\)与子树A的根节点的\(O\)相同。

点变异（Point Mutation）
原策略：一个随机的节点将会被改变，比如加法可以被替换成除法，变量X0可以被替换成常数-2.5。

新增要求：\(O\)属性不能变

解码方法

DFS整棵树
遇到关系，根据左右儿子连接的接口数增加相应的net
遇到器件，增加相应器件并回溯（因为一定搜到底了）
回溯时，记录接口标号，与相应的net进行连接

初始化

因为变异和交叉过程有限制接口数，所以对搜索能力必然有大幅地减弱，为了缓解这个问题，可以先人为构建出一些合法有效的初始解，再进行深度优化。