结合Ising模型的AEIPSO算法优化数字组合逻辑电路

The AEIPSO Algorithm Based on Ising Model Optimizes the Digital Combinational Logic Circuit

摘要: 粒子群优化算法(PSO)源于人工生命和复杂的自适应系统，近年来在数字电路的设计和优化中得到了应用。人们通过参数调节来改进PSO算法，虽然PSO算法具有参数更少、收敛速度更快等优点，但在迭代进化过程中容易陷入局部最优解，从而导致计算资源的低效使用。针对这一局限性，我们引入了基于Ising模型的改进自适应增强粒子群优化算法(AEIPSO)。提高了进化迭代的效率并且增强了解的多样性。同时，它保留了从PSO算法的快速收敛和卓越的全局搜索能力。实验结果表明，AEIPSO算法在组合逻辑电路的设计和优化方面优于其他PSO算法。

Abstract: Particle swarm optimization (PSO), derived from artificial life and complex adaptive systems, has been applied in the design and optimization of digital circuits in recent years. PSO algorithm is improved by parameter adjustment. Although PSO algorithm has the advantages of fewer parameters and faster convergence, it is easy to fall into local optimal solution during iterative evolution, which leads to inefficient use of computing resources. To address this limitation, we introduce an improved adaptive enhanced particle swarm optimization algorithm (AEIPSO) based on Ising model. It improves the efficiency of evolutionary iterations and increases the diversity of understanding. At the same time, it retains the fast convergence and excellent global search capability from the PSO algorithm. Experimental results show that AEIPSO algorithm is superior to other PSO algorithms in combinatorial logic circuit design and optimization.

1. 引言

组合逻辑电路(CLCs)是一种数字电路，其输出只取决于当前输出[1]。传统的人工设计数字电路方法，首先根据待实现电路的特定的逻辑功能需求而制定唯一的电路真值表。然后利用卡诺图或Quinn-McCluskey简化方法[2]进行电路设计。人工设计的效率不仅与电路规模有关，还与设计者的经验密切相关。同时，具有同一逻辑功能的组合逻辑电路可以对应多种不同形式的电路实现方案。这使得电路设计成为一个优化问题，即用最少的门来实现相同的功能[3]。为了减少人力资源，研究人员倾向于开发自动化方法。一个较大的分支是演化电路，通常具有更高的效率和精确度[4]。粒子群算法(PSO) [5]、遗传算法(GA) [6]、灰狼算法(ACO) [7]等算法已广泛应用于数字CLCs [8]的设计与优化中。

PSO算法最早是由J. Kenney与R. Eberhart通过研究鸟群使用信息共享来进行觅食、探寻栖息地等行为，而提出的一种基于群的优化算法，算法被广泛应用于多种优化领域[9]。考虑到数字CLCs的众多设计方案，寻找具有最小门级的最优解符合PSO算法的探索策略。Coello将PSO算法扩展到CLCs的设计中，验证了其优于手工设计方法和遗传算法[10]。Sagar进行了对比分析，评估了PSO、遗传算法(GA)和蚁群算法(ACO)在设计CLCs [11]时的性能差异。实验结果表明，PSO算法能够在最短的时间内，以最少的电路门数高效地找到满足设计要求的可行解。

与遗传算法等启发式算法相比，经典的PSO算法具有收敛速度快、迭代次数少的特点。然而，这种效率是以整个迭代过程中粒子解的多样性减少，即增加了陷入局部最优解的可能性为代价的。因此，这增加了与电路演化设计相关的时间和计算资源成本。将物理模型中的伊辛模型(Ising model)与改进的自适应增强粒子群优化算法(AEPSO) [12]-[14]集成是一种缓解PSO算法缺陷的策略。在AEPSO算法中，粒子的新位置和速度的更新方向，依赖于粒子个体历史最优位置以及种群中多个适应度较优层次中的粒子引导。这种进化策略使AEPSO算法对解空间有更广泛的探索，并增强了解的多样性。此外，AEPSO算法[15]-[18]采用非线性方法自适应调整加速系数，提高了算法的收敛速度和精度。这种自适应调整加快了算法寻找最优解的速度，从而提高了算法的整体效率。

与标准PSO算法在迭代完成之后抛弃粒子较差解的做法不同，我们在AEPSO算法的基础上进一步引入了伊辛模型和Metropolis采样算法，用于解决粒子如何以较少的迭代次数跳出局部最优解的问题以及粒子在迭代过程中如何处理迭代过程中较差解的问题。之前就曾有研究将伊辛模型引入到PSO算法中，最终的实验结果相较于直接使用PSO算法的实验结果更加出色[19]。综上所述，本文提出一种全新的算法，我们将其称为AEIPSO算法。

本文其余部分组织如下：第二节我们将详细介绍本文采用的AEIPSO算法的原理，第三节将详细介绍AEIPSO算法对组合逻辑电路的优化设计过程，第四节将介绍CEC基准优化函数集实验的过程，第五节是实际组合逻辑电路优化设计过程。第六节是本文的结论和讨论。

2. AEIPSO算法的原理

AEIPSO算法首先初始化一组粒子，每个粒子都有对应的初始速度与位置。迭代过程中，粒子的速度将会随之变化，粒子当前位置变化由粒子当前的速度和先前位置共同影响，算法会根据伊辛模型能量公式计算并比较粒子当前位置和先前位置对应的能量值，得出个体最优解对应位置$P_{best}$ 。

根据种群中粒子的能量大小分布，将粒子的解分为四个梯度层。筛选前三个层次的最优解$P_{g_{\left(1,2,3\right)}}$ 参与引导粒子在解空间中的搜索方向。随后，根据公式(1)，粒子当前位置$X_i\left(t\right)$ ，前三个能量分布层次的最优解$P_{g_{\left(1,2,3\right)}}$ 以及公式(2)中的收敛因子A计算前三个层次对应的种群粒子参考位置$X_{re{f}_{\left(1,2,3\right)}}$ 。

粒子更新位置和速度向量遵循公式(4)和公式(3)，其中公式(3)中的$\omega$ 代表惯性权重，其值随着迭代次数的增加而变化，r₁~r₃代表0到1之间的随机数。

$X_{re{f}_{\left(1,2,3\right)}}=P_{g_{\left(1,2,3\right)}}\left(t\right)-A*\left|C_{\left(1,2,3\right)}\left(t\right)*P_{g_{\left(1,2,3\right)}}\left(t\right)-\omega *X_i\left(t\right)\right|$ (1)

$A=\left(2-Iter*\left(2/Ite{r}_{\max }\right)\right)*\left(2*r_1-1\right)$ (2)

$\begin{array}{c}{V}_i\left(t+1\right)=\omega *(V_i\left(t\right)+C_1\left(t\right)*r_1*\left(X_{re{f}_1}\left(t\right)-X_i\left(t\right)\right)+C_2\left(t\right)*r_2*\left(X_{re{f}_2}\left(t\right)-X_i\left(t\right)\right)\\ +C_3\left(t\right)*r_3*\left(X_{re{f}_3}\left(t\right)-X_i\left(t\right)\right)+C_4\left(t\right)*r_4*\left(P_{\text{best }}\left(t\right)-X_i\left(t\right)\right))\end{array}$ (3)

$X_i\left(t+1\right)=X_i\left(t\right)+V_i\left(t+1\right)$ (4)

$X_i\left(t+1\right)$ 为粒子迭代后的位置，$V_i\left(t+1\right)$ 为粒子迭代后的速度值。不同的是，AEIPSO算法在粒子在进行位置更新时，同时考虑粒子个体认知部分和粒子社会认知部分，从而使种群中粒子之间的信息共享更加充分。最后，我们在AEIPSO算法的速度更新和参考位置更新公式中引入了随粒子能量值变化而动态变化的加速度系数$C_{\left(1,2,3\right)}\left(t\right)$ ，从而根据粒子所处迭代更新阶段的不同，进行加速度系数的动态调整。在解空间搜索的初始阶段，由于粒子探索解的情况较少，所以应该有较大的$C_4\left(t\right)$ 和较小的$C_{\left(1,2,3\right)}\left(t\right)$ ，有利于粒子在整个解空间内搜索，在解空间搜索的后期阶段，为使粒子探索解加速收敛，则应该有较小的$C_4\left(t\right)$ ,和较大的$C_{\left(1,2,3\right)}\left(t\right)$ ，具体公式如下。

$C_{1,2,3}\left(t\right)=1-\text{exp}\left(-a\left|E_a\left(t\right)-E_g\left(t\right)\right|\right)$ (5)

$C_4\left(t\right)=1-C_1\left(t\right)$ (6)

$E_a\left(t\right)$ 为种群中所有粒子能量值的平均值，$E_g\left(t\right)$ 为每次迭代更新后粒子群中最优解位置对应的粒子能量值，a为控制系数。${\omega }_{\min }$ 为最小惯性权重，${\omega }_{\max }$ 为最大惯性权重。Iter为当前迭代次数，Iter_max为最大迭代次数。惯性权重$\omega$ 的计算公式如下所示：

$\omega ={\omega }_{\min }+\left({\omega }_{\max }-{\omega }_{\min }\right)\frac{\left( {\text{Iter}}_{\max }-\text{Iter}\right)}{ {\text{Iter}}_{\max }}$ (7)

为了解决AEIPSO算法中的粒子的较差解的处理问题，我们结合Ising模型和Metropolis采样算法，让粒子以一定概率接受较差解，增加解的多样性，减少粒子跳出局部最优解需要的迭代次数。这一方法的思路主要源于寻找伊辛模型最低能量构型过程和寻找组合优化问题的全局最优解过程之间的映射[18]，将种群中粒子对应的电路方案映射为伊辛模型，伊辛模型中的能量就相当于组合优化问题中的目标函数，而伊辛模型中的最低能量构型就相当于组合优化问题中的全局最优解[19]。在伊辛模型内部粒子的之间存在相互作用，模型中不同方向粒子之间的相互作用形成了伊辛模型的整体能量。本文中的每种电路输入组合对应的电路输出映射为伊辛模型的粒子之间的相互作用，而粒子之间的相互作用形成了电路方案映射成的伊辛模型的整体能量。在本文中，粒子的能量函数计算公式如下：

$E_a\left(t\right)=\frac{1}{N}{\displaystyle \sum }_{i=1}^N{E}_{\left(S_i\right)}\left(X_i\left(t\right)\right)$ (8)

$E_g\left(t\right)=E_{\left(S_i\right)}\left(P_{g_1}\left(t\right)\right)$ (9)

$E_{\left(S_i\right)}=-J{\displaystyle \sum }_{\langle i,j\rangle }{S}_i{S}_j$ (10)

$F_{\left(S_i\right)}={\displaystyle \sum }_{\langle i,j\rangle }{S}_i{S}_j$ (11)

$E_a\left(t\right)$ 是种群粒子能量的平均值，$E_g\left(t\right)$ 是每次迭代后种群最优位置对应的能量值，两者的公式如公式(8)和公式(9)所示，$E_{\left(S_i\right)}$ 为第i个粒子对应的组合逻辑电路方案的能量值，J为能量耦合常数，$F_{\left(S_i\right)}$ 为PSO算法实验中第i个粒子对应的适应度值。$F_{\left(S_i\right)}$ 的计算规则类似于$E_{\left(S_i\right)}$ 计算规则，但不具有交换相互作用常数J。$S_i$ 和$S_j$ 分别为进化电路真值表的输出值和目标真值表的输出状态(在数字电路中系统的输出状态只有两种分别为：1和0)，相当于伊辛模型中自旋粒子的两种状态。如果进化电路的真值表与目标真值表完全对应，且J为正，则粒子的能量将是数值范围内的最优值。

粒子在迭代完成后是否接受更新后的位置值要根据两条判断原则进行判断，如果粒子在位置更新后对应的能量值减小，则接受更新后的位置。若更新后的能量值未减小但计算Metropolis采样算法中概率值$P_{(si)}$ 大于rand(0, 1)的随机数则同样接受该位置变化。其中$\Delta E$ 为粒子迭代前后的能量值差值，K为常数，T为调整概率变化的温度值，T的值随着迭代次数的增加而发生改变，迭代更新次数增大，T值变小，当能量差值为正值时，代表能量增长为负方向。如果此时处在粒子迭代变化前期，因为种群粒子探索的解空间为多峰解空间，峰值的不同对应的较优解不用。所以我们更希望提高前期接受较差解的概率，使粒子能够充分探索解空间，探索不同峰值对应的解。判断原则以及概率计算公式如公式(12)所示。

$x_i\left(t+1\right)=\{\begin{array}{l}{x}_i{\left(t+1\right)}^{\prime },E_{\text{(sj)}}<E_{(si)}\\ x_i{\left(t+1\right)}^{\prime },E_{(sj)}>E_{(si)}\text{ and }{p}_{(si)}>\text{random}\left(0,1\right)\\ x_i\left(t\right),E_{(sj)}>E_{(si)}\text{ and }{p}_{(si)}<=\text{random}\left(0,1\right)\end{array}$ (12)

$p\left(s_i\right)=\exp \left(-\frac{\Delta E}{KT}\right)$ (13)

在每一次迭代过程中温度值T改变之后引起的粒子位置更新，就相当于伊辛模型中粒子构型随着温度T的变化而改变。其中温度值T的计算公式如下，初始值$T_0$ 取决于$\left|E_{\max }-E_{\min }\right|$ ：

$T\text{=}{T}_0\text{*}\left[\left({\text{Iter}}_{\max }-\text{Iter}\right)/{\text{Iter}}_{\max }\right]$ (14)

3. AEIPSO算法用于电路设计的过程

本文利用MATLAB对粒子的初始化、更新迭代、能量计算等过程进行程序编写和运行，最后根据电路矩阵编码规则(表1和表2)以及迭代完成得到的电路矩阵直接获得满足设计要求的数字组合逻辑电路。

每次实验开始时，首先初始化一组数量为N的粒子，每个粒子有对应的初始速度与初始位置。初始位置按照一定的矩阵编码规则生成，初始速度为零矩阵，速度矩阵规模与位置矩阵相同。每一个粒子的位置矩阵都代表一种组合逻辑电路方案。电路矩阵的输入信号和逻辑运算编码规则如表1、表2所示：

Table 1. Matrix input signal coding rules

表1. 矩阵输入信号编码规则

矩阵第一列和第三列的矩阵元素值	输入信号
1	A
2	$\overline{A}$
3	B
4	$\overline{B}$
5	C
6	$\overline{C}$
7	L11
8	L12
9	L13
10	L21
11	L22
12	L23
13	L3

Table 2. Encoding rules for matrix logic operations

表2. 矩阵逻辑运算编码规则

矩阵第二列矩阵元素值	逻辑门类型
1	AND
2	OR
3	XOR
4	NOT
5	WIRE

将组合逻辑电路编码为矩阵，矩阵的每一行代表一种数字组合逻辑电路的逻辑操作，其中每一行的第一列元素代表第一位输入，第三列元素代表第二位输入，第二列元素代表逻辑运算。其中逻辑运算共有五种分别为：1代表逻辑与、2代表逻辑或、3代表逻辑异或、4代表逻辑非、5代表导线连接，而输入量由数字1~13代替。每次迭代更新时，程序将遍历矩阵每一行并进行元素更新。我们在程序编写过程中为每一行的元素设定了对应的上下限，保证矩阵元素在更新迭代过程中不会超出取值范围。

电路矩阵中的每一行相当于组合逻辑电路结构中不同的层级，每个层级之间相互联系，上一个层级的逻辑输出可能作为下一个层级的逻辑输入。具体组合逻辑电路结构图如图1所示，其中INPUT层代表电路的输入端，OUTPUT层代表电路的输出端。图1中每一个网格代表组合逻辑电路的一个逻辑单元，每个逻辑单元有两个输入，一个输出，其中L1层的输入来自电路的输入端输入，而L2层、L3层的输入来自上一级的输入。例如：L1层包含L11、L12、L13逻辑单元，其它层同理。逻辑单元的数目、层级的数目以及电路输入端输入量的数目不固定，可以根据自己的需求添加输入量数目，因为电路的层级之间相互联系，因此当输入量发生变化时，其它层级也要随之发生变化。

Figure 1. Schematic diagram of a combinational circuit connection. The INPUT and OUTPUT layers represent the input and output terminals of the circuit, and L1, L2, and L3 represent three layers with three logic units in each layer

图1. 组合电路连接形式图。INPUT、OUTPUT层分别代表电路的输入端和输出端，L1、L2、L3分别代表三个层级，每个层级分别有三个逻辑单元

粒子初始化完成之后，根据公式(10)计算每个粒子位置对应的能量值并将其设定为初始个体最优位置$P_{\text{best}}$ 。

并将粒子按照能量分为四个层次，挑选前三个层次中个体最优位置设为初始种群最优位置$P_{g_{\left(1,2,3\right)}}$ 。

随后根据位置更新迭代公式(4)和速度迭代更新公式(3)对每个粒子相应的速度矩阵和位置矩阵进行更新迭代，并根据粒子能量计算公式(10)计算迭代后种群中每个粒子的能量值大小，直到得到理想输出值或迭代达到最大迭代次数为止。

本文参考以往研究人员的有关粒子群优化算法参数选择的论文[19]。按照本文的应用环境对应的参数选择以及本文具体的研究目的，在实验的初始化部分对更新迭代公式中的一些固定参数和变化参数的初始值进行的设置，其中种群中每个粒子的初始速度$V_i$ 为0，惯性权重最大值${\omega }_{\max }$ 为0.9，惯性权重最小值${\omega }_{\min }$ 为0.4，最大迭代次数Iter_max为20，控制系数a设置为1，加速度系数C₁和加速度系数C₂的初始值都设为2，r₁~r₃设置为0~1的随机数，其数值在每次迭代过程随机产生。实验中采用的对比算法PSO，IPSO算法同属于粒子群优化算法，为了公平体现算法之间的差异，因此采用相同的参数设置，上述参数取值采用了论文[19]中经过大量实验所得出推荐参数范围内。

4. CEC基准优化函数集实验

为了进一步比较本文提出的AEIPSO算法与其他粒子群优化算法的性能差异。使用MATLAB 2020a对cec2020中的基准优化函数测试集以及针对实际问题的优化函数测试集中的电子电路优化问题进行测试，并对比了AEIPSO、IPSO和PSO算法在上述优化函数上运行的结果。用于测试的计算机配置包括以下规格：软件环境是Windows 10 (64位)，硬件环境是Intel(R) Core (TM) i7-8750H CPU @ 2.20 GHz，8.0 GB RAM。

4.1. CEC基准问题

为了充分反映AEIPSO算法与其他算法的在CEC2020基准优化函数测试集上的性能表现差异，我们选取CEC2020测试函数集中的单峰、多峰、混合和组合类型函数，从收敛速度、解的多样性以及对复杂问题的求解性能等方面对算法的性能进行测试，测试函数的详细信息如表3所示。

Table 3. Baseline optimization functions

表3. 基准优化函数

函数编号	搜索范围	维度	优化目标值
F2	[−100, 100]	10	1100
F5	[−100, 100]	10	1700
F6	[−100, 100]	10	1600
F9	[−100, 100]	10	2400
F10	[−100, 100]	10	2500

4.2. 实验过程

为了尽量减少实验偶然性对实验结果的影响，我们将每个算法的程序运行100次，取100次运行后，平均最优函数值随迭代次数变化的收敛曲线用来与其他算法作对比。此外，迭代次数的设置与算法结果在每个基准优化测试函数中的收敛程度有关，我们在实验开始前，为每个算法设置足够的迭代次数，使每种算法都能收敛到各自的稳定且最优函数值。

4.3. 实验结果和讨论

从附录A的结果图中可以看出，AEIPSO在收敛速度上比其他算法有很大的优势，并且在除F10之外的所有测试函数上都取得了更好的最终优化结果。在F10测试函数中，虽然AEIPSO取得的最终优化结果与其他算法相差不大，但仍有优势。总体而言，与其他算法相比AEIPSO算法表现出最好的性能。

5. 组合逻辑电路优化设计实验

为了评估AEIPSO算法在组合逻辑电路优化设计方面的性能，进行了三个实际组合逻辑电路优化设计实验。这些实验包括一个数据选择器、一个全加法器和一个四输入一输出电路。

实验过程中，通过统计IPSO、PSO和AEIPSO三种算法的适应度值以及能量值(AEIPSO、IPSO)随着迭代次数的变化，来检验和比较它们在数字组合逻辑电路设计中的性能。

5.1. 实验建立过程

Table 4. Data selector circuit truth table

表4. 数据选择器电路真值表

Inputs			Outputs
A	B	C	Out
0	0	0	0

续表

0	1	0	1
1	0	0	0
1	1	0	1
0	0	1	0
0	1	1	0
1	0	1	1
1	1	1	1

以数据选择器电路为例，我们在仅给出表4真值表的前提下分别通过执行AEIPSO、IPSO、PSO算法程序得出具体的数据选择器电路。

在本文实验中，我们首先根据编码规则初始化50个粒子。其中六个粒子P1到P6的位置矩阵具体形式如图2所示：

Figure 2. AEIPSO algorithm initializes the circuit matrix

图2. AEIPSO算法初始化电路矩阵

如表5所示，每个粒子使用公式10计算粒子初始能量值。在实际过程中，种群的每个粒子在初始化过程都需要经过位置矩阵初始化和计算初始能量值的过程。

Table 5. Initial particle energy value of AEIPSO algorithm

表5. AEIPSO算法初始粒子能量值

	P1	P2	P3	P4	P5	P6
Energy	8	8	8	8	0	8

剩余两种组合逻辑电路的实验建立过程与数据选择器电路实验建立过程一致，不同的地方在于期望电路的真值表不同，具体期望电路真值表分别如表6、表7所示：

Table 6. Four-input-one-output circuit truth table

表6. 四输入一输出电路真值表

Inputs				Outputs
A	B	C	D	Y
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

Table 7. Full adder circuit truth table

表7. 全加器电路真值表

Inputs			Outputs
A	B	C	Sum	Carry
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

以数据选择器电路为例，在本实验中，IPSO算法和PSO算法对应的初始粒子位置矩阵所对应的初始能量值分别如表8、表9所示：

Table 8. Initial particle energy value of IPSO algorithm

表8. IPSO算法初始粒子能量值

	P1	P2	P3	P4	P5	P6
Energy	8	0	8	0	8	2

Table 9. Table of initial particle fitness values of PSO algorithm

表9. PSO算法初始粒子适应度值表

	P1	P2	P3	P4	P5	P6
Energy	−8	−8	−8	0	−8	0

5.2. 组合逻辑电路设计实验过程

如果粒子初始化过程完成后，没有粒子达到最小能量值和最大适应度值。然后，根据算法的速度和位置更新规则，在每次迭代过程中更新粒子的位置和速度，并计算每个粒子的能量或适应度值；直到达到最小能量值和最大适应度值，或达到实验中设置的最大迭代次数Itermax时，算法程序的执行过程才会终止。

以下是AEIPSO、IPSO和PSO算法在不同实验中通过迭代更新得到的实验结果。为降低实验结果的偶然性，我们也重复进行了多次实验，得出多次运行下的，平均适应度或能量值随迭代次数的变化图。

本节将先给出单次运行下得出的粒子能量值以及对应的满足最优适应度值和能量值的电路方案。随后在本文的附录B给出多次运行下的平均适应度值和能量值随迭代次数变化的曲线图。

5.2.1. 数据选择器电路

1. AEIPSO算法：

在AEIPSO算法的实验中，粒子P2经过4次迭代后达到最小能量。其相应的电路图如图3所示。同时，P1~P6粒子的能量值如表10所示。

Table 10. Energy values of particles after the 4th iteration

表 10. 第4次迭代后粒子的能量值

	P1	P2	P3	P4	P5	P6
Energy	0	−8	0	−2	−4	0

Figure 3. Using AEIPSO algorithm, the circuit optimization results are updated after 4 iterations, and the left side of the circuit shows the updated circuit matrix iteration results

图3. 使用AEIPSO算法，电路优化结果在4次迭代后更新，电路左侧为更新后的电路矩阵迭代结果

2. IPSO算法：

在IPSO算法的实验中，粒子P4经过11次迭代后达到最小能量。P4相应的电路图如图4所示。同时，P1~P6粒子的能量如表11所示。

Table 11. Energy values of particles after the 11th iteration

表11. 第11次迭代后粒子的能量值

	P1	P2	P3	P4	P5	P6
Energy	0	−3	0	−8	0	2

Figure 4. IPSO algorithm is used to update the circuit optimization results after 11 iterations, and the left side of the obtained circuit is the updated circuit matrix iteration results

图4. 采用IPSO算法，经过11次迭代更新电路优化结果，得到电路的左侧是更新后的电路矩阵迭代结果

3. PSO算法：

在PSO算法的实验中，粒子P4经过18次迭代后达到最大适应度值，满足最大适应度值的粒子P4的电路图及电路矩阵如图5所示，粒子P1~P6的适应度值如表12所示。

Table 12. Fitness of particles after the 18th iteration

表12. 第18次迭代后粒子的适应度

	P1	P2	P3	P4	P5	P6
Energy	0	2	0	8	5	3

Figure 5. PSO algorithm is used to update the circuit optimization results after 18 iterations, and the left side of the obtained circuit is the updated circuit matrix iteration results

图5. 采用PSO算法，经过18次迭代更新电路优化结果，得到电路的左侧是更新后的电路矩阵迭代结果

实验中使用的三种算法的适应度值或能量值随种群迭代次数变化的整体过程，如图6所示。

Figure 6. Schematic diagram of IPSO, PSO, and AEIPSO algorithm iterative process. Where, the abscissa is the number of iterations of the algorithm, and the left and right axes of the ordinate are the energy value and fitness value of the particles corresponding to the number of iterations

图6. IPSO、PSO和AEIPSO算法迭代过程示意图。其中，横坐标为算法的迭代次数，纵坐标的左右轴分别为迭代次数所对应的粒子的能量值和适应度值

5.2.2. 四输入一输出电路

1. AEIPSO算法：

在AEIPSO算法的实验中，粒子P6经过28次迭代后达到最小能量。其相应的电路图如图7所示。同时，P1~P6粒子的能量值如表13所示。

Table 13. Energy values of particles after iteration 28

表13. 第28次迭代后粒子的能量值

	P1	P2	P3	P4	P5	P6
Energy	0	−4	2	−12	−11	−16

Figure 7. Using AEIPSO algorithm, the circuit optimization results are updated after 28 iterations, and the left side of the circuit shows the update iteration results of the circuit matrix

图7. 使用AEIPSO算法，电路优化结果经过28次迭代后更新，电路左侧为电路矩阵的更新迭代结果

2. IPSO算法：

在IPSO算法的实验中，粒子P5经过39次迭代后达到最小能量。其相应的电路图如图8所示。同时，P1~P6粒子的能量值如表14所示。

Table 14. Energy values of particles after the 39th iteration

表14. 第39次迭代后粒子的能量值

	P1	P2	P3	P4	P5	P6
Energy	0	6	−14	−2	−16	−10

Figure 8. The circuit optimization results are updated after 39 iterations using the IPSO algorithm, and the left side of the circuit shows the update iteration results of the circuit matrix

图8. 使用IPSO算法，电路优化结果经过39次迭代后更新，电路左侧为电路矩阵的更新迭代结果

3. PSO算法：

在PSO算法的实验中，粒子P3经过48次迭代后达到最大适应度。其相应的电路图如图9所示。同时，P1~P6粒子的适应度如表15所示

Table 15. Fitness values of particles after the 48th iteration

表15. 第48次迭代后粒子的适应度值

	P1	P2	P3	P4	P5	P6
Energy	2	10	16	2	13	0

Figure 9. The PSO algorithm is used to update the circuit optimization results after 48 iterations, and the left side of the circuit is the update iteration results of the circuit matrix

图9. 使用PSO算法，经过48次迭代更新电路优化结果，电路左侧为电路矩阵的更新迭代结果

最后，我们统计分析了实验中使用的三种算法的适应度值或能量值随种群迭代次数变化的整体过程，如图10所示。

Figure 10. Schematic diagram of IPSO, PSO, and AEIPSO iterative process. Where the abscissa is the number of iterations of the algorithm, and the left and right axes of the ordinate are the energy value and fitness value of the particles corresponding to the number of iterations

图10. IPSO、PSO和AEIPSO迭代过程示意图。其中横坐标为算法的迭代次数，纵坐标的左右轴分别为迭代次数对应的粒子的能量值和适应度值

5.2.3. 全加器电路

1. AEIPSO算法：

在AEIPSO算法的实验中，粒子P2经过33次迭代后达到最小能量。其相应的电路图如图11所示。同时，P1~P6粒子的能量值如表16所示。

Table 16. Energy of particles after iteration 33

表16. 第33次迭代后粒子的能量

	P1	P2	P3	P4	P5	P6
Energy	0	−16	3	−12	−10	−4

Figure 11. Using AEIPSO algorithm, the circuit optimization result is updated after 33 iterations, and the left side of the circuit is the update iteration result of the circuit matrix

图 11. 使用AEIPSO算法，在33次迭代后更新电路优化结果，电路左侧为电路矩阵的更新迭代结果

2. IPSO算法：

在IPSO算法的实验中，粒子P1经过42次迭代后达到最小能量。其相应的电路图如图12所示。同时，P1~P6粒子的能量值如表17所示。

Table 17. Energy of particles after iteration 42

表17. 第42迭代后粒子的能量

	P1	P2	P3	P4	P5	P6
Energy	−16	−3	3	−13	0	−4

Figure 12. Using IPSO algorithm, the circuit optimization results are updated after 42 iterations, and the left side of the circuit shows the updated iteration results of the circuit matrix

图 12. 使用IPSO算法，在42次迭代后更新电路优化结果，电路左侧为电路矩阵的更新迭代结果

3. PSO算法：

在PSO算法的实验中，粒子P4经过57次迭代后达到最小能量。其相应的电路图如图13所示。同时，P1~P6粒子的能量值如表18所示。

Table 18. Fitness of particles after iteration 57

表18. 第57次迭代后粒子的适应度

	P1	P2	P3	P4	P5	P6
Energy	0	12	3	16	8	4

Figure 13. The circuit optimization results are updated after 57 iterations using the PSO algorithm, and the left side of the circuit shows the update iteration results of the circuit matrix

图13. 使用PSO算法，电路优化结果经过57次迭代后更新，电路左侧为电路矩阵的更新迭代结果

我们统计分析了实验中使用的三种算法的适应度值或能量值随种群迭代次数变化的整体过程，如图14所示。

Figure 14. Schematic diagram of the iterative process of the three algorithms IPSO, PSO, and AEIPSO. Where the abscissa is the number of iterations of the algorithm, and the left and right axes of the ordinate are the energy value and fitness value of the particles corresponding to the number of iterations

图14. IPSO、PSO和AEIPSO三种算法的迭代过程示意图；其中横坐标为算法的迭代次数，纵坐标的左右轴分别为迭代次数对应的粒子的能量值和适应度值

6. 结论与讨论

本文分别使用PSO、IPSO和AEIPSO算法在前述实验中成功生成了满足要求的电路方案。然而，与IPSO和AEIPSO算法相比，PSO算法容易陷入局部最优解场景，需要更多的迭代次数才能跳出局部最优解场景，导致最终解的多样性较差。

在Ising模型和Metropolis采样算法的作用下，AEIPSO算法需要更少的迭代就能使粒子跳出进化迭代过程中的局部最优解，从而增加了最终解的多样性。此外，AEIPSO算法还在粒子速度更新规则中增加了除粒子先前位置以外的两种加权因子，第一种加权因子是粒子历史最优位置和粒子当前位置之间的差异，另一种加权因子是种群粒子能量分布的前三层次中的粒子位置和粒子当前位置之间的差异。这种改进增加了粒子迭代进化的引导因素种类，粒子的进化方向不再只由种群中唯一的最优粒子引导，而是能够在迭代的不同时期进行合理的解空间探索，并且考虑多个层次最优粒子的影响。

迄今为止，智能优化算法已经产生了许多应用于不同场景的变体算法，继续寻找性能更好的优化算法并将其应用于数字组合逻辑电路的设计与优化方面，将是我们未来要继续开展的工作。

附 录

附录A：

Figure (a). Iterative change curve of F2 optimization function value

图(a). F2优化函数值迭代变化曲线

Figure (b). Iteration change curve of F5 optimization function value

图(b). F5优化函数值迭代变化曲线

Figure (c). Graph of iterative change of F6 optimization function value

图(c). F6优化函数值迭代变化曲线图

Figure (d). Iterative change curve of F9 optimization function value

图(d). F9优化函数值迭代变化曲线

Figure (e). Iterative change curve of F10 optimization function value

图(e). F10优化函数值迭代变化曲线

附录B：

Figure (a). Data selector circuit average energy (fitness value) iteration change curve

图(a). 数据选择器电路平均能量(适应度值)迭代变化曲线

Figure (b). Iterative change curve of average energy (fitness value) of four-input-one-output circuit

图(b). 四输入一输出电路平均能量(适应度值)迭代变化曲线

Figure (c). Iterative variation curve of the average energy (fitness value) of a one-bit full adder circuit

图(c). 一比特位全加器电路的平均能量(适应度值)迭代变化曲线

NOTES

^*通讯作者。