可变长图编码的电路演化设计方法

周勤 尹玲 张斐 李文浩 宋业明 李耘

(1.东莞理工学院 计算机科学与技术学院，广东东莞 523808；2.东莞理工学院 机械工程学院，广东东莞 523808；3.电子科技大学(深圳)高等研究院 人工智能工业创新研究中心，广东深圳 518110)

利用先进的电子设计自动化(electronic design automation，EDA)工具，可以方便地进行集成数字电路的设计。然而，模拟电路设计仍然受到缺乏自动设计工具的困扰，许多模拟电路模块，即使是小规模的，仍然需要有经验的专家在传统方法下进行设计[1]。因此，如何在有限的资源下设计出最优的模拟电路已成为越来越重要的问题。模拟电路演化是电子信息硬件演化领域中重要的一环，是为了解决传统方法难以处理的复杂功能电路需求而提出的。近来，谷歌的研究人员证明，通过使用人工智能(AI)技术，可以在一天甚至数个小时内完成过去需要几个星期的电路自动设计过程[2]。

常见的模拟电路自动化方案是使用进化算法对电路结构、元器件类型和元器件值进行优化，从而得到更为高效的电路模型[3]。Sussman[4]于1975年提出使用启发式检验方法来处理复杂的直流偏置电路分析问题。Koza等人[5]提出利用电路构建程序树来对电路结构进行表征，但他们没有考虑电路结构的封闭性，从而产生了大量不可正确仿真的非法电路。Goh等人[6]根据节点、类型、元器件值三部分直接对电路进行编码，该方法编码虽然简单易于实现、可表示拓扑结构范围广，但编码过程没有对非法电路拓扑进行处理，因此仍然会产生大量非法电路，浪费电路仿真时间。Lohn等人[7]利用轨迹(trail)编码对电路节点进行约束，虽然避免了非法电路的产生，但同时也降低了可表示电路拓扑的范围。何劲松等人[8]利用图的生成过程来表征电路构建过程，提出了图编码方式，该编码方式在保证电路拓扑合法的情况下，尽可能多地保留了可表示电路拓扑的范围。但其所采用的简单遗传算法无法直接对不同编码长度的电路个体直接进行交叉操作，且无法避免交叉过程中非法电路的产生。

基于上述分析，本文提出了一种可变长图编码的电路演化方法，能够对不同编码长度的电路进行表示和演化，确保交叉操作所新产生的电路个体仍然是有效电路，并且通过设计不同的变异概率和变异策略，实现对电路宏观结构和元器件参数进行同步优化，进一步加快演化算法的收敛速度。

1 电路拓扑和可变长图编码

在电路分析中，研究者们通常以图论为指导来设计电路结构图，当忽略元件的值时，几乎所有的电路结构都可以用无向图来表示[9]。本节将基于图编码[8]的方式来描述电路结构在图论中的对应表现形式，并详细介绍如何以生成闭合无向图的方式产生可用电路编码，其中电路编码包含了电路拓扑结构、元器件类型和参数信息，演化算法通过对编码进行选择、交叉、变异等操作来实现电路的自动化设计。

1.1 电路结构的拓扑图表示

本小节将描述电路结构在封闭无向图中的表示，以及如何创建从简单到复杂的结构图，并通过一定的策略来保持图的封闭性。在电路图论中，任何电路都可以用元器件和导线来表示，在忽略电路元件的情况下，电路结构图可以被映射成一个特殊的无向图，其中电路中的节点和导线分别与图论的顶点和边对应，图中两个顶点之间的任何一条边都代表构成实际电路的一个元件，对应关系如图1所示。

图1 电路结构的封闭无向拓扑图

由于电路中出现串联的情况是较为频繁的，所以在电路图的表示中允许两点之间存在多条边。此外，为了保持电路结构的封闭性，生成图中的每个节点必须连通不少于两个分量，且保证在规则电路中不存在悬浮节点，因此在映射的特殊无向图中顶点的度不能小于2。一般来说，电路中元器件的数量不超过节点数的5倍，对于边数较少的图，使用邻接表进行存储能够节约更多的存储空间。本文所使用的图编码采用邻接表来对电路结构图进行存储，有利于降低演化算法的编码长度和计算复杂度。

文献[8]设计了两种图编码方法的编码指令，分别对应电路设计中常用的串联和并联操作。第一条指令是connecting-two-nodes，用来选择两个已有的节点并用新边连接，对应于电路设计的并联操作，其中新产生的边对应了新插入的一个电路元件。另一个是inserting-new-node指令，用来在两个已有节点之间插入一个新节点，新节点将原有节点对应的边拆分为两个新边，对应于电路设计中的串联操作，其中一条新边对应原有的电路元件，另一条新边对应新插入的电路元件。在执行inserting-new-node命令之前，应该检查被选择的两个节点之间是否存在边，确保在创建新节点之前，被插入节点之间至少存在一条边，否则插入新的节点时会破坏图的封闭性。

1.2 图编码方法

可变长图编码方法使用一组操作指令实现对电路元件的修改，通过使用多组操作指令实现对完整电路的表示，且电路中元件数量和操作指令数量呈正相关。操作指令是一个由指令、节点1、节点2、元器件类型和元器件参数组成的五位实数编码，每个编码位置的解释如表1所示。第一个编码位置表示为1(connecting-two-nodes)或2(inserting-new-node)的两种操作指令中的其中一种。第二和第三个编码位置分别表示两个互不相同的候选节点，且候选节点编码来自于生成图中已经存在的节点集中。在电路初始阶段，节点集中只有0和1，分别代表地端和电源端。第四个位置代表三种基本元件类型之一，其值为1(电阻)，2(电容)或3(电感)。最后的位置代表电子元器件在E24系列标准组件库中的索引值，对于不同的元器件类型，其索引范围是不同的。

表1 演化电路元件编码

大部分电路都可以通过上述的电路编码来完成表示，例如图2所示。该初始电路由仅包含电压源和负载电阻的电路模板构成，其中包含的节点有输入节点1、输出节点2和接地节点0。一个从电源到负载之间功能电路的生成过程如下例所示：

图2 用图指令方法在电源与负载之间生成功能电路的图过程

1)当指令为1(connecting-two-nodes)且节点为1和2时，在节点1和节点2之间插入一个电感元件作为新边；

2)其次，对于2(inserting-new-node)指令，在完成节点之间边的存在性检查后，创建一个新的节点3插入到节点1和节点2之间；

3)新插入的节点将节点1和节点2对应的边拆分两个新边，其中节点1和节点3所在边对应了原有的电感元件，而节点3和节点2所在边对应了新插入的一个电感元件；

4)最后，执行指令1，在节点3和节点0之间插入一个电容。

2 可变长图编码演化算法

演化算法是电路自动进化设计的重要组成部分，本文提出的可变长图编码演化算法是基于标准遗传算法[10]进行设计的。算法的潜在解由多组操作指令组成的图编码进行表示，通过评估潜在解的适应度，然后对潜在解进行选择、可变长图编码交叉、多策略变异等操作得到更优解，其算法流程如图3所示。下文将对图中主要模块进行详细介绍。

图3 可变长演化图编码的电路设计流程

2.1 种群初始化

在图编码方法中，一组操作指令对应一个额外元器件的产生，为了灵活地对含有不同元器件数量的电路拓扑进行表示，本文使用不定长度的基因编码串来代表一个具体的电路拓扑。与固定长度编码相比，不定长度编码具有编码灵活、内存开销更小、计算更简单等优点。为了保证演化过程中电路结构是有效的个体，在初始化阶段对电路结构进行一定的约束，确保随机产生的结构为合法个体。种群初始化步骤描述如下。

③重复1.2过程，直到元器件数量等于Nsum。

④重复以上过程K次，最终得到一个规模为K的种群。

2.2 适应度评估

适应度是描述描述个体性能的主要指标，演化算法可以根据适应度的大小对个体进行优胜劣汰的选择[11]。图编码描述了电路拓扑生成过程，通过执行图编码指令能够将个体编码转换为对应的实际电路，并以网表文件格式[12]进行保存。网表文件是一种描述电路连接关系和元器件参数的文本文件，能够在SPICE电路仿真软件(如：Pspice，Hspice和LTspcie等)中进行模拟仿真，得到电路幅频响应结果，从而进行电路适应度值计算。适应度评估步骤如下所示。

①根据第1节所述的图编码方式对电路个体编码进行解码，得到包含电路信息的网表文件。

②调用SPICE电路仿真软件对网表文件中所含包含的电路进行仿真评估，得到生成滤波器产生的幅频响应H(jω)。

(1)

2.3 电路图编码交叉算子

不同电路拓扑中包含的电路节点数量往往是不同的，传统的单/多点交叉算子无法保证在交叉生成的新个体仍然为合法电路。图编码交叉算子使用两个电路个体中所拥有的公共节点作为分割点，分别对电路个体编码进行交叉位置计算，并将个体截断为两部分，使得前一部分编码不会包含公共节点以外的电路节点，从而保证了交叉之后的新个体仍然是有效的封闭电路。电路图编码交叉算子实现流程如下。

①根据交叉概率Pc随机选择两个电路编码进行交叉。

②计算被交叉电路编码A与B最大公共节点数Nc(例如A的最大节点数量为10，B为8，那么A与B的最大公共节点数Nc=8)。

③随机选择一个小于Nc的节点编号作为交叉开始节点Ns。

④以Ns在编码中的第一次出现为界，将编码分为p1A和p2A两部分。

⑤通过交叉重组拆分后的编码形成两个新的个体newA={p1A,p2B}，newB={p1B,p2A}。

2.4 多策略变异

本文针对编码位置设计了不同的变异概率以及变异操作，实现结构和元器件参数的同步优化,并采用最优精英保留策略，来加快算法收敛速度。

①对于5个指令编码位，分别独立设置每个位置的突变概率Pmi，i∈[1-5]。

②当指令类型位发生突变时，其值由1变为2或者由2变为1；当节点位置编码发生突变时，随机从节点集Q中选择一个新的节点对变异位置编码进行替换，且新节点应不同于指令中的另一节点；当元器件类型发生突变时，随机产生新的元器件类型和元器件参数；当元器件参数位置编码发生突变，随机从E24标准元器件库中选择一个元器件值索引。

③变异结束后，对发生突变的值进行合理性检验，确保突变后编码能够生成有效电路结构。

3 在电子设计自动化中的应用实例

鉴于低通无源滤波器是电路设计中最典型的电路之一，本文通过设计一个负载电容为2.2 μF的RC低通无源滤波器，来对提出的方法进行可行性验证。实验所使用的所有元器件都是二端元件，且已经存在于LTspice元件库中，元件参数参考E24系列标准元件。在实验中，最大电阻数和电容数都设置为25，即程序允许的总元器件数量最大为50，所设计的滤波器最高阶数为25，理想截止频率设置为1 000 Hz。针对此截止频率的设计要求，电路的适应度函数如上文提到的公式(1)所示。

实验在Matlab软件中对电路编码进行演化和解码，将解码之后的电路信息保存为可被仿真软件识别的网表文件；然后使用LTspice工具对网表文件表示的电路进行仿真评估；最后，该工具将仿真结果返回到Matlab中进行电路对适应度值的计算和进一步的演化。演化过程中，交叉策略的概率设置为0.6，本算法使用[0.1，0.15，0.15，0.2，0.3]的列表来表示不同编码位置的变异策概率，最大迭代数设置为200，种群大小设置为100。为了验证本文提出的方法在电路演化设计中的有效性，实验采用文献[8]所使用的简单遗传算法作为对照，除简单遗传算法的交叉概率设置为0.2以外，其他实验参数完全一致。演化过程中的适应度收敛情况如图4所示。

图4 最优个体适应度变化图

表2显示了算法和简单遗传算法的对比结果。简单遗传算法要求电路个体编码长度必须一致，因此在初始化时必须对编码长度较短的个体进行补齐，虽然操作固定长度的编码更加方便，但其引入了非必要的电路编码，需要耗费更大的存储空间。而本文提出所采用的不定长度编码无需额外的处理，所需存储空间更小。简单遗传算法所使用的交叉算子为随机单点交叉，其过程虽然简单快捷，但在执行过程中产生了840个无法进行仿真计算的非法电路。文本提出的可变长图编码交叉操作，虽然操作更加复杂，但保证了每一个新个体都是有效的电路结构，避免了无效仿真的计算开销。多策略变异算子能够同时对电路宏观结构和元器件参数进行优化，增强了个体变异能力，和单点变异相比，操作更加复杂，参数调整更加困难。从仿真时间上可以看出，虽然本文提出的演化算法更加复杂，计算操作更多，但由于程序的主要耗费时间是电路仿真时间，且总的仿真电路数量相同，因此总的程序执行时间差距较小。从表2可以看出虽然两种方法都能收敛到相近的适应度值，但本文提出的方法仅需18次迭代便可收敛，而简单遗传算法则需要81次迭代，这说明本文提出的算法能够极大地加快电路演化的收敛速度。

表2 可变长图编码演化算法和简单遗传算法对比

图5显示了所生成的最佳低通滤波器电路拓扑图，图6显示了它的幅频响应结果。从该结果来看，通过可变长图编码的演化算法得到的低通滤波器，只需使用5个电容和5个电阻，就能很好地满足设计要求。在图5中，低通滤波电路的原理图是一个简单的电路原理图，其元件的数量满足元件最大数目的限制，而且无需进行5个一阶RC电路的串联或并联，使电路的印制或集成方便有效。

图5 可变长图编码的遗传算法生成的最优低通滤波器电路

图6 生成最优滤波器的幅频响应曲线图

4 结语

针对不同电路个体的编码长度不一、常规优化容易产生非法电路结构的问题，提出了一种基于遗传算法改进的可变长图编码演化算法，设计了一种可用于不同编码长度的交叉操作，并保证了交叉所产生的新个体仍然是有效的电路结构。同时针对不同编码位置设计了多种变异概率和变异策略，来实现电路宏观结构和元器件参数的同步优化。最后，通过低通滤波器的演化设计实验，验证了该算法的有效性和实用性。结果表明，本文提出的方法能够很好的解决电路自动化设计过程中易产生非法电路个体的问题，避免无效电路仿真带来的时间和资源浪费，极大地加快了电路演化收敛速度。