# Power Optimization for Mixed Polarity Reed–Muller Circuits Based on Multilevel Adaptive Memetic Algorithm

Authors: Yuhao Zhou; Zhenxue He; Yan Zhang; Jia Liu; Tao Wang; Limin Xiao; Xiang Wang
Journal: International Journal of Intelligent Systems
 (2023)

---

## Abstract

Power optimization can reduce heat dissipation costs and has become an important step of circuit logic synthesis. Because the power optimization for mixed polarity Reed–Muller (MPRM) circuits is a combinatorial optimization problem, in this paper, we first propose a multilevel adaptive memetic algorithm (MAMA), which includes global exploration optimizer, local heuristic optimizer, and initial population optimizer. We use the proposed differential evolution optimization, simulated annealing optimization, and data matching algorithm to make the population evolve. Moreover, based on the proposed matrix decomposition strategy and parallel polarity conversion algorithm, we propose a power optimization approach (POA) for MPRM circuits, which searches for an MPRM circuit with a minimum power using the MAMA. Experimental results demonstrated the effectiveness and superiority of the POA in optimizing the power of MPRM circuits.


---

## Body

## 1. Introduction

With the development of nanotechnology, the design and manufacture of integrated circuits play an increasingly important role in digital systems, communication equipment, national defense modernization, and software application. However, with the continuous improvement of chip integration, the problem of chip power has become increasingly prominent. The increase in power will lead to an increase in heat dissipation cost and packaging cost [1, 2]. Therefore, the technology of circuit power optimization becomes an essential step in chip design.Logic functions can be expressed either in AND/OR/NOT based Boolean logic or in XNOR/OR or XOR/AND based Reed–Muller (RM) logic [3]. With the emergence of XNOR and XOR gates, RM logic has attracted more and more attention. Circuits based on RM logic (such as arithmetic logic circuits and parity check circuits) show more obvious advantages in circuit power, area, and speed and have excellent testability [4–7]. Fixed polarity Reed–Muller (FPRM) expression and mixed polarity Reed–Muller (MPRM) expression are two common RM logic expansions [8]. MPRM logic circuits with n input variables have 3n different polarities; that is, different polarities correspond to different MPRM expressions, but the optimization space of the FPRM logic circuits is 2n [9], which is a subset of the MPRM optimization space. Therefore, more results can be obtained based on the power optimization of the MPRM logic circuits.However, the huge polarity search space of MPRM circuits also leads to higher time and space complexity for circuit performance optimization than FPRM circuits. In small-scale circuits, the ideal polarity can be found by exhaustive approaches because the search space is small [10, 11]. However, as the number of input variables increases, the polarity search space increases dramatically, so the exhaustive search time will be too long, which is not feasible in terms of time. Therefore, new breakthroughs are urgently needed in the theoretical research and optimization approach of MPRM logic circuits. Many researchers have introduced intelligent optimization algorithms to optimize circuit power. Recently, a lot of work focusing on the power optimization for RM circuits based on XOR/AND has been proposed, including exhaustive approaches [12], genetic algorithms (GAs) [13, 14], particle swarm optimization (PSO) [15], and many others [16, 17] for power optimization.Compared with expressions based on XOR/AND, some circuit expressions based on XNOR/OR are more concise [14]. However, there are few studies on XNOR/OR-based MPRM circuit power optimization. First, the size of the MPRM space is larger than that of the FPRM space. Second, Polarity conversion is a necessary step in judging each polarity. As far as we know, there are no approaches to switching between polarities currently. Researchers need to convert from Boolean functions to arbitrary polarity, which can take a lot of time. Finally, the multiextreme nature of the search space can mislead the search algorithm [18, 19]. In [17], a hybrid genetic algorithm (HGA) considering the polarity conversion sequence for power optimization is proposed. Because using HGA requires searching for the best polarity switch sequence, it takes a lot of time. In [20], the authors proposed a power optimization approach based on an adaptive PSO algorithm for XNOR/OR-based MPRM circuits. However, the mutation control parameters are so sensitive that the global convergence speed of the algorithm is affected. Generally speaking, the MPRM expressions are derived from the Boolean logic expressions by using the polarity conversion approaches such as the tabular technique [21] or ordered functional decision diagram-based technique [22]. Yu et al. [21] proposed an algorithm to convert from Boolean function to arbitrary polarity, and the effectiveness of the algorithm was proved by experiments. However, it has poor efficiency when dealing with medium and large-scale circuits due to the maximum term increase. In [23], He et al. proposed a novel binary differential evolution algorithm for RM logic circuit optimization. In [24], Al Jassani et al. analyzed the characteristics of Boolean logic circuits and proposed a genetic algorithm to optimize expression. However, the above two related works are all oriented to small-scale circuits, and the control parameters tend to exceed the boundary value, so it is difficult to get the optimal solution.Power optimization for MPRM circuits is a large-scale multiextremum optimization problem. Existing optimization approaches for MPRM circuits based on XNOR/OR have poor optimization performance when dealing with large circuits with multiple input variables. In addition, the existing polarity conversion approaches consume a lot of time. To solve these problems, we propose a power optimization approach for MPRM circuits based on the proposed multilevel adaptive memetic algorithm (MAMA), proposed matrix decomposition strategy (MDS), and proposed parallel polarity conversion algorithm (PPCA). The contributions of this paper are summarized as follows:(1)
We propose a PPCA that can not only convert Boolean functions to any polarity but also convert any two polarities. Polarity conversion is the premise of solving the power under a certain polarity and directly affects the efficiency of the whole optimization scheme. PPCA not only solves the problem of variable limitation but also is more efficient than traditional Boolean conversion. As far as we know, this is the first time that an XNOR/OR-based MPRM circuits parallel polarity conversion algorithm has been proposed.(2)
We propose a MAMA, which includes a global exploration optimizer, local heuristic optimizer, and initial population optimizer. The first level of adaptive is reflected in the zoom factor, and the second level of adaptive is reflected in the crossover probability. Moreover, the global exploration optimizer is evolved by using the proposed differential evolution optimization (DEO); the DEO takes full account of the relationship between individual fitness value, iteration times, and upper and lower limits of the target vector to solve the corresponding probability value; the local heuristic optimizer is evolved by using the proposed simulated annealing optimization (SAO), the SAO combines with the probability jump property to find the global optimal solution of the objective function in the solution space; and the initial population optimizer by data matching algorithm (DMA), the DMA is an approach based on the Hamming distance, which aims to maintain the diversity of the population. MAMA can be a useful CAD tool for solving other combinatorial optimization problems.(3)
We propose a power optimization approach (POA) for MPRM circuits based on the MAMA, MDS, and PPCA. The MDS includes the OR gates decomposition strategy and the XNOR gates decomposition strategy. The POA uses the PPCA to convert to MPRM relative polarity, uses the MDS to calculate the minimum power of MPRM circuits, and searches for the best polarity corresponding to an MPRM circuit with the minimum power using the MAMA. All experiments used MCNC benchmark circuits and proved the effectiveness and superiority of POA.The remaining of this article is organized as follows: In Section2, we introduce a few preliminaries that are relevant to our study. In Section 3, the MDS for MPRM circuits is provided in detail. In Section 4, the PPCA for MPRM circuits is provided in detail. Then, a MAMA is proposed in Section 5. In Section 6, a power optimization approach for MPRM circuits is proposed. In Section 7, the experimental results are shown. Finally, Section 8 concludes this article. In addition, in the appendices at the end of the article, we give a reference table (i.e., Table 1) of all abbreviated terms.Table 1
Reference table of abbreviated terms.
MPRMMixed polarity Reed–MullerMAMAMultilevel adaptive memetic algorithmPOAPower optimization approachRMReed–MullerFPRMFixed polarity Reed–MullerGAGenetic algorithmHGAHybrid genetic algorithmPSOParticle swarm optimizationMDSMatrix decomposition strategyPPCAParallel polarity conversion algorithmDEODifferential evolution optimizationSAOSimulated annealing optimizationDMAData matching algorithmDDEADiscrete differential evolution algorithmBDEABinary differential evolution algorithmCAConversion algorithmMCNCMicroelectronics center of North Carolina


## 2. Preliminaries

### 2.1. MPRM Expression

In the mixed polarity XNOR/OR circuits, the XNOR/OR expansion corresponding to the logic function of anyn-variable is expressed as follows:(1)fPxn−1,xn−2,⋯,x0=⊙∏i=02n−1di+Si,where P is the polarity, and its ternary number is expressed in the form (pn−1pn−2⋯p0); the subscript i can be expressed in a binary form as i = (in−1in−2 …i0); di∈ {0,1}, dj = 0 indicates that the term Si appears in the expression, and dj = 1 indicates that the term Si does not appear in the following expression:⊙∏ is the XNOR operator and + represents the logical sum.


### 2.2. Power Estimation Model

The previous section introduced the MPRM circuits, which require an expression to calculate the power of each polarity. In addition, two-input XNOR gates are critical for standard power values. We briefly list CMOS structure-based two-input XNOR gates and briefly analyze them as follows:Figure1 is based on CMOS. It is more convenient for the design of power circuits and test voltages. Compared with double pass-transistor logic and pass-transistor logic, CMOS has a stronger ability to drive loads and does not require additional logic stages. In addition, this structure has the advantages of the full swing of the output voltage and a symmetrical structure. It is well known that a large part of the power on the chip due to the charge and discharge of the load capacitor is caused by the dynamic power at the gate. In a digital CMOS circuit consisting of n gates, the total dynamic power can be expressed as follows:(2)Esωd=12Vdd2fclk∑ni=1CLiEsωdi,where Vdd is the supply voltage, fclk is the clock frequency, and CLi is the output load capacitance of gate i. ESωdi (referred to as switching activity) is the number of transitions per cycle at gate i. In the logic synthesis stage, only ESωdi is controllable, and there is a proportional relationship with the power, so the size of the switching activity directly reflects the size of the circuit power. The switching activity of gate circuits can be obtained by the signal probability of its output terminal. Dynamic logic is more common in CMOS circuits. Therefore, the calculation of switching activity in this article will focus on dynamic logic. The switching activity calculation formula is as follows:(3)ESωdi=2⋅Prg.Figure 1
CMOS-based dual-input XNOR gates.Two-input OR gates signal probability can be expressed as follows:(4)Prg=Prx+Pry−Prx⋅Pry.Two-input XNOR gates signal probability can be expressed as follows:(5)Prg=1+2⋅Prx⋅Pry−Prx−Pry,where Pr (g) represents the output signal probability of the node, which can be calculated by the input signal probability of (4) and (5). The basic algorithm for low-power mapping is the Huffman algorithm, which is used to construct a binary tree with the minimum average weighted path length [25]. The multiinput XNOR terms and OR terms are decomposed into a series of two-input XNOR terms and OR terms. The different decomposition approaches are used to solve the output signal probability as shown in the figure below. Where Figures 2(a) and 2(b) represent the two different decomposition strategies for OR gates, respectively, and Figures 3(a) and 3(b) represent the two different decomposition strategies for XNOR gates, respectively.Figure 2
Two different decomposition strategies for OR gates.
(a)(b)Figure 3
Two different decomposition strategies for XNOR gates.
(a)(b)


## 2.1. MPRM Expression

In the mixed polarity XNOR/OR circuits, the XNOR/OR expansion corresponding to the logic function of anyn-variable is expressed as follows:(1)fPxn−1,xn−2,⋯,x0=⊙∏i=02n−1di+Si,where P is the polarity, and its ternary number is expressed in the form (pn−1pn−2⋯p0); the subscript i can be expressed in a binary form as i = (in−1in−2 …i0); di∈ {0,1}, dj = 0 indicates that the term Si appears in the expression, and dj = 1 indicates that the term Si does not appear in the following expression:⊙∏ is the XNOR operator and + represents the logical sum.


## 2.2. Power Estimation Model

The previous section introduced the MPRM circuits, which require an expression to calculate the power of each polarity. In addition, two-input XNOR gates are critical for standard power values. We briefly list CMOS structure-based two-input XNOR gates and briefly analyze them as follows:Figure1 is based on CMOS. It is more convenient for the design of power circuits and test voltages. Compared with double pass-transistor logic and pass-transistor logic, CMOS has a stronger ability to drive loads and does not require additional logic stages. In addition, this structure has the advantages of the full swing of the output voltage and a symmetrical structure. It is well known that a large part of the power on the chip due to the charge and discharge of the load capacitor is caused by the dynamic power at the gate. In a digital CMOS circuit consisting of n gates, the total dynamic power can be expressed as follows:(2)Esωd=12Vdd2fclk∑ni=1CLiEsωdi,where Vdd is the supply voltage, fclk is the clock frequency, and CLi is the output load capacitance of gate i. ESωdi (referred to as switching activity) is the number of transitions per cycle at gate i. In the logic synthesis stage, only ESωdi is controllable, and there is a proportional relationship with the power, so the size of the switching activity directly reflects the size of the circuit power. The switching activity of gate circuits can be obtained by the signal probability of its output terminal. Dynamic logic is more common in CMOS circuits. Therefore, the calculation of switching activity in this article will focus on dynamic logic. The switching activity calculation formula is as follows:(3)ESωdi=2⋅Prg.Figure 1
CMOS-based dual-input XNOR gates.Two-input OR gates signal probability can be expressed as follows:(4)Prg=Prx+Pry−Prx⋅Pry.Two-input XNOR gates signal probability can be expressed as follows:(5)Prg=1+2⋅Prx⋅Pry−Prx−Pry,where Pr (g) represents the output signal probability of the node, which can be calculated by the input signal probability of (4) and (5). The basic algorithm for low-power mapping is the Huffman algorithm, which is used to construct a binary tree with the minimum average weighted path length [25]. The multiinput XNOR terms and OR terms are decomposed into a series of two-input XNOR terms and OR terms. The different decomposition approaches are used to solve the output signal probability as shown in the figure below. Where Figures 2(a) and 2(b) represent the two different decomposition strategies for OR gates, respectively, and Figures 3(a) and 3(b) represent the two different decomposition strategies for XNOR gates, respectively.Figure 2
Two different decomposition strategies for OR gates.
(a)(b)Figure 3
Two different decomposition strategies for XNOR gates.
(a)(b)


## 3. MDS for MPRM Circuits

As mentioned in Section2, to accurately evaluate the power of MPRM circuits, multiinput XNOR gates, and OR gates need to be decomposed as two-input gates circuits, respectively. It is worth mentioning that different decomposition strategies result in different power, as shown in Example 1.Example 1.
Given a four-input OR gatesxi (i = 0, 1, 2, 3), the probability of input signal is 0.2, 0.4, 0.6, and 0.9, respectively. According to the different decomposition strategies (A, B) in Section 2, two circuit structure drawings are established and the corresponding switching activity is calculated. As is shown in figures where Figures 4(a) and 4(b) represent the two different circuit structures for OR gates, respectively, and Figures 5(a) and 5(b) represent the two different circuit structures for XNOR gates, respectively.
Therefore, to minimize the power of the MPRM circuits, a matrix decomposition strategy (MDS) is proposed to calculate the minimum power of the MPRM circuits. The MDS is shown in Algorithm1. The following operators are implemented until there is only one tree in the distance matrix A: initialize n input signals into n single-node trees, and record the input probability Pr (g) of each signal in the root of the tree as the probability of the tree. To reduce the storage space and search time of A, an upper triangular matrix with A of (n−1) (n−1) can be constructed. The distance between two trees was represented by switching activity Esωd, and the distance matrix A was calculated; we searched the two nearest trees and make them as subtrees to form a binary tree; we calculated the probability Pr (g) of the new tree and write it in the tree root as the probability of the tree; we added the distance between the two subtrees to Esωd; we updated the distance matrix A. The implementation details of MDS are illustrated in Examples 2 and 3.Algorithm 1: The MDS.
Input: number of variables with n input gates, and let y = n.Output: total switching activity Esωd(1)
fori = 0 to ndo(2)
forj = i+1 to n do(3)
Calculate the values of each elementxi,y in the distance matrix Ay−1y−1(4)
end for(5)
end for(6)
y = y−1(7)
while (y! = NULL)(8)
Search for the smallest element in the distance matrix, set asbi,y(9)
Esωd = Esωd + bi,y(10)
Replacei and y input probabilities with bi,y(11)
Calculate a new distance matrixAy−1y−1(12)
end while(13)
Esωd = Esωd + b0,0(14)
returnEsωdFigure 4
The corresponding circuit structure of OR gates.
(a)(b)Figure 5
The corresponding circuit structure of XNOR gates.
(a)(b)


### 3.1. The MDS for OR Gates Decomposition

The four input OR gates and four input XNOR gates in dynamic logic are respectively taken as examples to illustrate the multiinput gates decomposition process of the MDS.Example 2.
Let the probabilities of the input signalxi (i = 0, 1, 2, 3) of the four input OR gates be 0.66, 0.02, 0.51, and 0.23, respectively. As shown in Figure 6, first, establish the distance matrix as shown in A. A is the upper triangular matrix, and the “−1” in the lower-left corner indicates that the data in the corresponding unit is invalid. The search found that a1,3 is the minimum value in the A matrix. Second, the signals x1 and x3 are used as subtrees to form a binary tree, a1,3 (=0.4908) is added to Esωd, and a1,3 is inversely inferred to get the probability (0.2454) of the new binary tree. Third, the probability of the new tree is added to the probability sequence, and the probabilities corresponding to the original signals x1 and x3 are deleted; for the new probability sequence 0.66, 0.51, and 0.2454, a new distance matrix is established as shown in A′. Repeating the above steps, the distance between the two subtrees of the last binary tree will be shown as A″. After the original four-input gates are decomposed, the total switching activity Esωd is 3.4999 (=0.4908 + 1.2605 + 1.7486). Moreover, Figure 7 represents the corresponding Huffman tree structure.Figure 6
Four input OR gates distance matrix: (a) distance matrix A; (b) distance matrix A′; (c) distance matrix A″.
(a)(b)(c)Figure 7
Huffman tree structure for OR gates.


### 3.2. The MDS for XNOR Gates Decomposition

Example 3.
Let the probability distribution of the input signalxi (i = 0, 1, 2, 3) of the XNOR gates be 0.7235, 0.3999, 0.8322, and 0.3986, and the corresponding distance matrix and Huffman tree structure are shown in Figures 8 and 9, respectively. The total switching activity of the original XNOR gates after decomposition is 2.804 (=0.8734 + 0.9224 + 1.0082).Figure 8
Four input XNOR gates distance matrix: (a) distance matrix A; (b) distance matrix A′; (c) distance matrix A″.
(a)(b)(c)Figure 9
Huffman tree structure for XNOR gates.


## 3.1. The MDS for OR Gates Decomposition

The four input OR gates and four input XNOR gates in dynamic logic are respectively taken as examples to illustrate the multiinput gates decomposition process of the MDS.Example 2.
Let the probabilities of the input signalxi (i = 0, 1, 2, 3) of the four input OR gates be 0.66, 0.02, 0.51, and 0.23, respectively. As shown in Figure 6, first, establish the distance matrix as shown in A. A is the upper triangular matrix, and the “−1” in the lower-left corner indicates that the data in the corresponding unit is invalid. The search found that a1,3 is the minimum value in the A matrix. Second, the signals x1 and x3 are used as subtrees to form a binary tree, a1,3 (=0.4908) is added to Esωd, and a1,3 is inversely inferred to get the probability (0.2454) of the new binary tree. Third, the probability of the new tree is added to the probability sequence, and the probabilities corresponding to the original signals x1 and x3 are deleted; for the new probability sequence 0.66, 0.51, and 0.2454, a new distance matrix is established as shown in A′. Repeating the above steps, the distance between the two subtrees of the last binary tree will be shown as A″. After the original four-input gates are decomposed, the total switching activity Esωd is 3.4999 (=0.4908 + 1.2605 + 1.7486). Moreover, Figure 7 represents the corresponding Huffman tree structure.Figure 6
Four input OR gates distance matrix: (a) distance matrix A; (b) distance matrix A′; (c) distance matrix A″.
(a)(b)(c)Figure 7
Huffman tree structure for OR gates.


## 3.2. The MDS for XNOR Gates Decomposition

Example 3.
Let the probability distribution of the input signalxi (i = 0, 1, 2, 3) of the XNOR gates be 0.7235, 0.3999, 0.8322, and 0.3986, and the corresponding distance matrix and Huffman tree structure are shown in Figures 8 and 9, respectively. The total switching activity of the original XNOR gates after decomposition is 2.804 (=0.8734 + 0.9224 + 1.0082).Figure 8
Four input XNOR gates distance matrix: (a) distance matrix A; (b) distance matrix A′; (c) distance matrix A″.
(a)(b)(c)Figure 9
Huffman tree structure for XNOR gates.


## 4. Parallel Polarity Conversion Algorithm

Polarity conversion is the premise of power optimization of MPRM logic circuits. Efficient polarity conversion can shorten the time of searching for the optimal polarity. Polarity conversion is to switch from the current max-terms to another polarity. Nowadays, the approaches of XNOR/OR-based MPRM polarity conversion are only from Boolean to any polarity. Because the Boolean function has many max-terms, each conversion takes a lot of time. To overcome the disadvantage of traditional conversion, we first propose the parallel polarity conversion algorithm (PPCA), which can not only convert Boolean functions to any polarity but also convert any two polarities. Because the max-terms form of the Boolean function can appear in the true or complementary form at the same time, the Boolean function can be corresponding to the polarity (2222…2). The PPCA is shown as Algorithm2.Algorithm 2: The PPCA.
Input: the n input polarity r=rnrn−1⋯r1 or polarity (2…2). The list column is xjx^j,x¯j,1≤j≤n. The list line is <cncn−1⋯c1>,cj∈0,1. Let h=n.Output: all maximum terms of polarity P(1)
for j = h to 1 do(2)
ifmj = rjthen(3)
continue;(4)
else ifrj==0,pj==1rj==1,pj==0rj==2,pj==1 and the list line is in−1⋯ij+10ij−1⋯i0then generate a new list line in−1⋯ij+11ij−1⋯i0(5)
else ifrj==2,pj==0rj==0,pj==2rj==1,pj==2 and the list line is in−1⋯ij+11ij−1⋯i0then generate a new list line in−1⋯ij+10ij−1⋯i0(6)
end if(7)
for all new list lines do(8)
if the new list line is the same as the original list line then(9)
Delete the new list line and the original list line(10)
else(11)
Add the new list line to the original list line(12)
end if(13)
end for(14)
ifrj == 1, pj == 2||rj == 2, pj == 1 then(15)
Thecj in the list row <cncn−1⋯c1>, is reversed(16)
end if(17)
end forExample 4.
Suppose that 0 polarityf 0 (x4, x3, x2, x1) = ⊙∏ (0, 4, 5, 7, 9, 12, 15), find the mixed polarity XNOR/OR expression with polarity 25. First, the 0 polarity max-terms are displayed in the first column. Since the polarity number is 25 (the ternary form is 0221), we only generate new terms for x3, x2, and x1. According to Algorithm 2, we can derive the MPRM expression with the required polarity. As shown in Figure 10, we have(6)f25x4,x3,x2,x1=⊙∏x4+x3+x2¯⊙x4+x3¯+x2+x1¯⊙x4+x3¯+x2⊙x4+x3¯+x2¯⊙x3¯+x2¯+x1¯⊙x3+x2⊙x3+x2¯⊙x3¯+x2+x1¯⊙x3¯+x2¯.Figure 10
Mixed polarity conversion using parallel polarity conversion algorithm.


## 5. Multilevel Adaptive Memetic Algorithm

Finding the optimal polarity of the MPRM circuits with the smallest power from the huge polarity optimization space is not only a multiextreme problem but also a combinatorial optimization problem. In recent years, many optimization algorithms combining heuristic theory and swarm intelligence algorithms have been proposed, such as fireworks algorithm [26], hybrid memetic algorithm [27], memetic algorithm (MA) based on genetic algorithm [28], and memetic algorithms based on greedy search strategy and constrained optimization [29–32]. Compared with the traditional swarm intelligence algorithm, the biggest characteristic of MA is the complementary advantages of various algorithms. Therefore, MA has the ability to search globally and jump out of the local optimum. In this section, we propose a MAMA that mainly consists of a global exploration optimizer devised by DEO, a local heuristic optimizer devised by SAO, and an initial population optimizer devised by DMA. It is worth mentioning that the first-level adaptive is embodied in the zoom factor Fi, and the second-level adaptive is embodied in the crossover probability cri. The details of MAMA are described as follows.


### 5.1. Global Exploration Optimizer

The essence of differential evolution optimization (DEO) is to solve the global optimal solution of the continuous optimization problem in multidimensional space [33, 34]. Reference [35] proved the optimization performance of DEO by discussing all the mutation theories and analyzing the convergence behavior. In [36], Cui et al. proposed an adaptive multiple-elites-guided composite differential evolution algorithm with a shift mechanism to solve the problem of premature convergence. Reference [37] proposed a memetic framework based on differential evolution. In the proposed framework, differential evolution with linear population size reduction and semiparameter adaptation is used for global exploration, and its effectiveness is verified for large-scale global optimization problems. Similarly, in [38], Wang et al. conducted targeting experiments on specific genes in candidate solutions to balance the excessive dimensions of DEO and get rid of the limitation of bottleneck dimensions. In [39], Li et al. proposed a novel three-layer distributed differential evolution framework with adaptive resource allocation for allocating fitness evaluation budget resources in multiple populations. Experiments have proved the effectiveness of this approach. The conclusion of the above literature proved that DEO has the ability to distribute parallel optimization and good global search ability. However, the above works are to solve the problems of continuity optimization. The power optimization of MPRM logic circuits is a high-dimension combinatorial optimization problem, and the information on each dimension is crucial. Therefore, we propose a global exploration optimizer based on improved DEO for the power optimization of MPRM logic circuits. In the mutation operator, the zoom factor F∈ [0.1, 0.9] determines the size of the individual difference step in the population. As shown in the following formula, we list several mutation vectors Vig.(7)Rand/DE/:Vig=Xp1g+F⋅Xp2g−Xp3g,(8)Optimal/DE/:Vig=Xbestg+F⋅Xp1g−Xp2g,(9)Currenttobest/DE/:Vig=Xig+F⋅Xbestg−Xig+F⋅Xp1g−Xp2g,(10)Optimal/DE/:Vig=Xbestg+F⋅Xp1g−Xp2g+F⋅Xp3g−Xp4g,(11)Optimal/DE/:Vig=Xp1g+F⋅Xp2g−Xp3g+F⋅Xp4g−Xp5g.As shown in the aforementioned formulas, especially the (7), small F will affect the difference between individuals in the population and make the algorithm result fall into local optimal. The F overlarge increase will enhance the global search ability of the algorithm but will affect the convergence speed of the algorithm and destroy the structure of the optimal solution. Therefore, to balance the global search for the optimal solution and convergence rate, the value of Fi adaptively changes according to the two individuals that generate the difference vector. The adaptive zoom factor Fi of the ith individual can be defined as follows:(12)Fi=Fl+Fu−Flfp2−fp1fp3−fp1.The three randomly selected individuals in the mutation operator were ranked according to the fitness value from the best to the worst, andXp1, Xp2, and Xp3 are obtained, where fp1, fp2, and fp3 are fitness values from the best to the worst, respectively; Fu and Fl are the upper and lower limits of the mutation interval, respectively. It can be derived from (12) that the larger the similarity between individuals, the larger the zoom factor Fi, the Vig needs to be increased to improve population diversity. In contrast, the smaller the similarity between individuals, the smaller the zoom factor Fi, the Vig needs to be reduced to improve the convergence speed.In the crossover operator, it is necessary to cross the target vectorXi (g) and the Vig to generate the experimental vector ui.g=ui.g=ui1.g,ui2.g,…,uiD.g, and ui,g is shown as follows:(13)u=vij,g,ifrand0,1≤criorj=jrand,xij,g,otherwise.To avoid falling into local optimal, we prevent the optimal solution from being destroyed and speed up convergence, we propose adaptive crossover probabilitiescri based on the best (fmax) and worst (fmin) individuals in the population. In addition, our proposed adaptive crossover probability is also applied in the next section. The adaptive crossover probability cri of ith individual can be defined as follows:(14)cri=crl+cru−crlfi−fminfmax−fmin,iffi>f,¯crl,iffi<f¯,where jrand is a dimension randomly selected from the set {1, 2, …, D} to ensure that at least one dimension of Vi is preserved, f¯ is the average fitness value of the population, cru and crl are the upper and lower limits of the crossover interval, respectively. The overview of DEO is depicted in Algorithm 3.Algorithm 3: The DEO algorithm.
Input: population: M; dimension: D; genetation: TOutput: the best vector (solution) −∆(1)
t ← 1 (initialization)(2)
fori = 1 to Mdo(3)
forj = 1 to Ddo(4)
xi,tj=xminj+rand0,1⋅xmaxj−xminj(5)
end for(6)
end for(7)
whilef∆≥εort≤Tdo(8)
fori = 1 to Mdo(9)
(Adaptive mutation and adaptive crossover)(10)
forj = 1 to Ddo(11)
vi,tj=adaptivemutationxi,tj(12)
ui,tj=adaptivecrossoverxi,tj,vi,tj(13)
end for(14)
Greedy selection(15)
iff (ui,t) < f (xi,t) then(16)
xi,t ← ui,t(17)
iff (xi,t) < f (∆) then(18)
∆ ← xi,t(19)
end if(20)
else(21)
xi,t ← xi,t(22)
end if(23)
t ← t + 1(24)
end while(25)
return the best vector ∆


### 5.2. Local Heuristic Optimizer

At the end of each iteration, the information of the optimal individual besti in the population is worth developing again to jump out of the local optimal solution. To solve the problem, we propose a local heuristic optimizer based on simulated annealing optimization (SAO). SAO makes full use of the effective information of the besti and improves the optimization capability of the algorithm. The SAO for local heuristic optimizer consists of two parts, the metropolis algorithm, and the annealing process. The metropolis algorithm is a sampling approach that accepts new states with probabilities, known as the metropolis criterion. SAO is used for heuristic search as shown in Figure 11.Figure 11
Local heuristic search.Where B, C, and E denote the local solution, and D denotes the globally optimal solution near the local solution. It can be seen that SAO will carry out local exploration with a certain probability. So the design of this probability is very important; it has to do with the current state, the energy, and so on. The state sequence of the SAO is determined by (15) and (16). The metropolis criterion is also called the equilibrium probability equation.(15)p=1,fj<fi,exp−fj−fit,fj≥fi,(16)tk+1=λ×tk,k=0,1,2,…where tk is the current solid temperature, t0 is set to 100, λϵ0,1 is the temperature cooling rate, and the usual value range of λ is 0.85 < λ < 0.95. When set at state j, the fitness value of the best vector in generation j is expressed by fj. Comparing the fitness of the two states, if the fitness of state j is greater than that of state i, that is, fj > fi, then state j is an acceptable state. Otherwise, then state j is a nonideal state. At this time, the probability p of accepting this nonideal state solution is calculated according to (15). To avoid excessive destruction of the structure of the optimal solution at the beginning of the algorithm, random numbers should be adaptively generated. As the temperature decreases, the probability of accepting acceptable solutions gradually decreases.The probability value off (v) conforms to the Boltzmann distribution [33, 40], as shown in (17). In the equation, m is the particle mass and kT is the product of Boltzmann’s constant and thermodynamic temperature. In the SAO algorithm in this section, the movement of the best vector in the large search space Ω forms a finite-length Markov chain, and its probability distribution p is shown in (18). The overview of SAO is depicted in Algorithm 4.(17)fv=m2πkT34πv2e−mv2/2kT,(18)p=efi/tk∑j∈Ωefj/tk,Algorithm 4: The SAO algorithm.
Input: the best vector (solution) −∆; minimum temperature: TminOutput: new best vector (solution) −∆′(1)
while T > Tmindo(2)
de = f (∆ + i) − f (∆)(3)
if (de ≥ 0) then(4)
f (∆ + i) = f (∆)(5)
else if (exp (−de/T) > random (0, −1)) according to equations (14) and (15) then(6)
f (∆ + i) = f (∆)(7)
end if(8)
T =λ ∗ T(9)
i++(10)
end while(11)
return the New best vector ∆′


### 5.3. Initial Population Optimizer

A good initial population will not only make the individual distribution more uniform but also increase the diversity of the population. At present, some researchers use point sets, orthogonal design, and other approaches to initialize the population, but these approaches have certain defects. For example, the directionality of the point set will interfere with the searchability of the algorithm, and the orthogonal design approach cannot be used to solve large-scale problems. The data matching algorithm (DMA) based on Hamming distance [41] is suitable for combinatorial optimization problems. It is not only fast in implementation but also more suitable for multidimensional problems. Therefore, this paper uses the DMA for initialization to increase population diversity.The main idea of DMA is to calculate the Hamming distance between the sampled data and the detection data in the detection set. If it is less than the threshold valueε, it is nonself-data; otherwise, for self-data. Here, The Hamming distance Dis (P, Qi) between individual P=p1,p2,⋯pn and individual Qj = (q1j, q2j, …, qnj) in the population is defined as follows:(19)DisP,Qj=∑ni=1pi∧qij,where 0 ∧ 0 = 0, 0 ∧ 1 = 1, 0 ∧ 2 = 1, 1 ∧ 1 = 0, 1 ∧ 2 = 1, 0 ∧ 0 = 0, n is the dimension of the detection set, P represents the sampling data, and Qj represents the jth test data of the test set. When generating the initial population data, the sampled data is the input data generated randomly, and the detection data is the initial data generated in the initial population. The matching threshold ε determines the degree of similarity between the sampled data and the test set data.Example 5.
Suppose the sampling data a ⟶ 22, b ⟶ 16, c ⟶ 7 is given; If the test data is a ⟶ 24, b ⟶ 20, c ⟶ 8, the calculation process of DMA is shown in Figure12.
Because in the DMA, the degree of similarity of each individual is guaranteed to be low, so the DMA can make the initial population distribution more uniform.Figure 12
DMA calculation process.


### 5.4. Algorithm Description

MAMA is illustrated in Algorithm5, the n and G represent the population scale of MAMA and the maximum number of iterations of MAMA, respectively.Algorithm 5: Multilevel adaptive memetic algorithm.
Input: Population scale n, maximum number of iterations G, iterations g = 0, best individual best.Output: The best solution(1)
Initialize the population based on the DMA(2)
fori = 1: ndo(3)
Individual fitness values were calculated(4)
end for(5)
whileg < = G do(6)
fori = 1: ndo(7)
Perform adaptive mutation based on the DEO(8)
Perform adaptive crossover based on the DEO(9)
Perform Greedy selection based on the DEO(10)
Individual fitness values were calculated(11)
Perform elitist preservation (fbest)(12)
end for(13)
Perform local exploitation based on the SAO(14)
g ← g + 1(15)
end while(16)
The best solution is the output


## 5.1. Global Exploration Optimizer

The essence of differential evolution optimization (DEO) is to solve the global optimal solution of the continuous optimization problem in multidimensional space [33, 34]. Reference [35] proved the optimization performance of DEO by discussing all the mutation theories and analyzing the convergence behavior. In [36], Cui et al. proposed an adaptive multiple-elites-guided composite differential evolution algorithm with a shift mechanism to solve the problem of premature convergence. Reference [37] proposed a memetic framework based on differential evolution. In the proposed framework, differential evolution with linear population size reduction and semiparameter adaptation is used for global exploration, and its effectiveness is verified for large-scale global optimization problems. Similarly, in [38], Wang et al. conducted targeting experiments on specific genes in candidate solutions to balance the excessive dimensions of DEO and get rid of the limitation of bottleneck dimensions. In [39], Li et al. proposed a novel three-layer distributed differential evolution framework with adaptive resource allocation for allocating fitness evaluation budget resources in multiple populations. Experiments have proved the effectiveness of this approach. The conclusion of the above literature proved that DEO has the ability to distribute parallel optimization and good global search ability. However, the above works are to solve the problems of continuity optimization. The power optimization of MPRM logic circuits is a high-dimension combinatorial optimization problem, and the information on each dimension is crucial. Therefore, we propose a global exploration optimizer based on improved DEO for the power optimization of MPRM logic circuits. In the mutation operator, the zoom factor F∈ [0.1, 0.9] determines the size of the individual difference step in the population. As shown in the following formula, we list several mutation vectors Vig.(7)Rand/DE/:Vig=Xp1g+F⋅Xp2g−Xp3g,(8)Optimal/DE/:Vig=Xbestg+F⋅Xp1g−Xp2g,(9)Currenttobest/DE/:Vig=Xig+F⋅Xbestg−Xig+F⋅Xp1g−Xp2g,(10)Optimal/DE/:Vig=Xbestg+F⋅Xp1g−Xp2g+F⋅Xp3g−Xp4g,(11)Optimal/DE/:Vig=Xp1g+F⋅Xp2g−Xp3g+F⋅Xp4g−Xp5g.As shown in the aforementioned formulas, especially the (7), small F will affect the difference between individuals in the population and make the algorithm result fall into local optimal. The F overlarge increase will enhance the global search ability of the algorithm but will affect the convergence speed of the algorithm and destroy the structure of the optimal solution. Therefore, to balance the global search for the optimal solution and convergence rate, the value of Fi adaptively changes according to the two individuals that generate the difference vector. The adaptive zoom factor Fi of the ith individual can be defined as follows:(12)Fi=Fl+Fu−Flfp2−fp1fp3−fp1.The three randomly selected individuals in the mutation operator were ranked according to the fitness value from the best to the worst, andXp1, Xp2, and Xp3 are obtained, where fp1, fp2, and fp3 are fitness values from the best to the worst, respectively; Fu and Fl are the upper and lower limits of the mutation interval, respectively. It can be derived from (12) that the larger the similarity between individuals, the larger the zoom factor Fi, the Vig needs to be increased to improve population diversity. In contrast, the smaller the similarity between individuals, the smaller the zoom factor Fi, the Vig needs to be reduced to improve the convergence speed.In the crossover operator, it is necessary to cross the target vectorXi (g) and the Vig to generate the experimental vector ui.g=ui.g=ui1.g,ui2.g,…,uiD.g, and ui,g is shown as follows:(13)u=vij,g,ifrand0,1≤criorj=jrand,xij,g,otherwise.To avoid falling into local optimal, we prevent the optimal solution from being destroyed and speed up convergence, we propose adaptive crossover probabilitiescri based on the best (fmax) and worst (fmin) individuals in the population. In addition, our proposed adaptive crossover probability is also applied in the next section. The adaptive crossover probability cri of ith individual can be defined as follows:(14)cri=crl+cru−crlfi−fminfmax−fmin,iffi>f,¯crl,iffi<f¯,where jrand is a dimension randomly selected from the set {1, 2, …, D} to ensure that at least one dimension of Vi is preserved, f¯ is the average fitness value of the population, cru and crl are the upper and lower limits of the crossover interval, respectively. The overview of DEO is depicted in Algorithm 3.Algorithm 3: The DEO algorithm.
Input: population: M; dimension: D; genetation: TOutput: the best vector (solution) −∆(1)
t ← 1 (initialization)(2)
fori = 1 to Mdo(3)
forj = 1 to Ddo(4)
xi,tj=xminj+rand0,1⋅xmaxj−xminj(5)
end for(6)
end for(7)
whilef∆≥εort≤Tdo(8)
fori = 1 to Mdo(9)
(Adaptive mutation and adaptive crossover)(10)
forj = 1 to Ddo(11)
vi,tj=adaptivemutationxi,tj(12)
ui,tj=adaptivecrossoverxi,tj,vi,tj(13)
end for(14)
Greedy selection(15)
iff (ui,t) < f (xi,t) then(16)
xi,t ← ui,t(17)
iff (xi,t) < f (∆) then(18)
∆ ← xi,t(19)
end if(20)
else(21)
xi,t ← xi,t(22)
end if(23)
t ← t + 1(24)
end while(25)
return the best vector ∆


## 5.2. Local Heuristic Optimizer

At the end of each iteration, the information of the optimal individual besti in the population is worth developing again to jump out of the local optimal solution. To solve the problem, we propose a local heuristic optimizer based on simulated annealing optimization (SAO). SAO makes full use of the effective information of the besti and improves the optimization capability of the algorithm. The SAO for local heuristic optimizer consists of two parts, the metropolis algorithm, and the annealing process. The metropolis algorithm is a sampling approach that accepts new states with probabilities, known as the metropolis criterion. SAO is used for heuristic search as shown in Figure 11.Figure 11
Local heuristic search.Where B, C, and E denote the local solution, and D denotes the globally optimal solution near the local solution. It can be seen that SAO will carry out local exploration with a certain probability. So the design of this probability is very important; it has to do with the current state, the energy, and so on. The state sequence of the SAO is determined by (15) and (16). The metropolis criterion is also called the equilibrium probability equation.(15)p=1,fj<fi,exp−fj−fit,fj≥fi,(16)tk+1=λ×tk,k=0,1,2,…where tk is the current solid temperature, t0 is set to 100, λϵ0,1 is the temperature cooling rate, and the usual value range of λ is 0.85 < λ < 0.95. When set at state j, the fitness value of the best vector in generation j is expressed by fj. Comparing the fitness of the two states, if the fitness of state j is greater than that of state i, that is, fj > fi, then state j is an acceptable state. Otherwise, then state j is a nonideal state. At this time, the probability p of accepting this nonideal state solution is calculated according to (15). To avoid excessive destruction of the structure of the optimal solution at the beginning of the algorithm, random numbers should be adaptively generated. As the temperature decreases, the probability of accepting acceptable solutions gradually decreases.The probability value off (v) conforms to the Boltzmann distribution [33, 40], as shown in (17). In the equation, m is the particle mass and kT is the product of Boltzmann’s constant and thermodynamic temperature. In the SAO algorithm in this section, the movement of the best vector in the large search space Ω forms a finite-length Markov chain, and its probability distribution p is shown in (18). The overview of SAO is depicted in Algorithm 4.(17)fv=m2πkT34πv2e−mv2/2kT,(18)p=efi/tk∑j∈Ωefj/tk,Algorithm 4: The SAO algorithm.
Input: the best vector (solution) −∆; minimum temperature: TminOutput: new best vector (solution) −∆′(1)
while T > Tmindo(2)
de = f (∆ + i) − f (∆)(3)
if (de ≥ 0) then(4)
f (∆ + i) = f (∆)(5)
else if (exp (−de/T) > random (0, −1)) according to equations (14) and (15) then(6)
f (∆ + i) = f (∆)(7)
end if(8)
T =λ ∗ T(9)
i++(10)
end while(11)
return the New best vector ∆′


## 5.3. Initial Population Optimizer

A good initial population will not only make the individual distribution more uniform but also increase the diversity of the population. At present, some researchers use point sets, orthogonal design, and other approaches to initialize the population, but these approaches have certain defects. For example, the directionality of the point set will interfere with the searchability of the algorithm, and the orthogonal design approach cannot be used to solve large-scale problems. The data matching algorithm (DMA) based on Hamming distance [41] is suitable for combinatorial optimization problems. It is not only fast in implementation but also more suitable for multidimensional problems. Therefore, this paper uses the DMA for initialization to increase population diversity.The main idea of DMA is to calculate the Hamming distance between the sampled data and the detection data in the detection set. If it is less than the threshold valueε, it is nonself-data; otherwise, for self-data. Here, The Hamming distance Dis (P, Qi) between individual P=p1,p2,⋯pn and individual Qj = (q1j, q2j, …, qnj) in the population is defined as follows:(19)DisP,Qj=∑ni=1pi∧qij,where 0 ∧ 0 = 0, 0 ∧ 1 = 1, 0 ∧ 2 = 1, 1 ∧ 1 = 0, 1 ∧ 2 = 1, 0 ∧ 0 = 0, n is the dimension of the detection set, P represents the sampling data, and Qj represents the jth test data of the test set. When generating the initial population data, the sampled data is the input data generated randomly, and the detection data is the initial data generated in the initial population. The matching threshold ε determines the degree of similarity between the sampled data and the test set data.Example 5.
Suppose the sampling data a ⟶ 22, b ⟶ 16, c ⟶ 7 is given; If the test data is a ⟶ 24, b ⟶ 20, c ⟶ 8, the calculation process of DMA is shown in Figure12.
Because in the DMA, the degree of similarity of each individual is guaranteed to be low, so the DMA can make the initial population distribution more uniform.Figure 12
DMA calculation process.


## 5.4. Algorithm Description

MAMA is illustrated in Algorithm5, the n and G represent the population scale of MAMA and the maximum number of iterations of MAMA, respectively.Algorithm 5: Multilevel adaptive memetic algorithm.
Input: Population scale n, maximum number of iterations G, iterations g = 0, best individual best.Output: The best solution(1)
Initialize the population based on the DMA(2)
fori = 1: ndo(3)
Individual fitness values were calculated(4)
end for(5)
whileg < = G do(6)
fori = 1: ndo(7)
Perform adaptive mutation based on the DEO(8)
Perform adaptive crossover based on the DEO(9)
Perform Greedy selection based on the DEO(10)
Individual fitness values were calculated(11)
Perform elitist preservation (fbest)(12)
end for(13)
Perform local exploitation based on the SAO(14)
g ← g + 1(15)
end while(16)
The best solution is the output


## 6. Power Optimization for MPRM Circuits Based on XNOR/OR

In this section, we propose a power optimization approach (POA) for MPRM circuits, which uses MDS to decomposition MPRM circuits, and uses PPCA to get the max-terms of polarity and searches for the best polarity corresponding to an MPRM circuit with minimum power using the MAMA.


### 6.1. Encoding Scheme

Whether each polarity bit of the MPRM expression is displayed depends on whether the variable is true, complemented, or mixed; specifically, it is represented by 0, 1, and 2.Example 6.
Given a 7-variables MPRM expression, the ternary polarity “1212011” can be encoded as a 7-bits chromosome as shown in Figure13.Figure 13
Polarity encoding.


### 6.2. POA Description

The flow of POA is depicted in Figure14.Step 1. Read the Boolean logic circuits of then input variable.Step 2. Initialize the parameters of the POA. The parameters include the population scalePX,g, the termination condition, and the temperature cooling rate λ.Step 3. The initial population is generated based on DMA as shown byX0,g in the flow chart, individuals (i.e., polarities for MPRM circuits) are encoded as ternary bits, and the ternary chromosome number is shown in Figure 13.Step 4. The work of this paper is power optimization of MPRM circuits based on XNOR/OR, so the smaller the power, the larger the fitness value. Therefore, the fitness function is defined as follows:(20)fXi=1powerXi, where f (Xi) denotes the fitness value of polarity Xi and power (Xi) denotes the power of the polarity Xi. First, the proposed PPCA is used to convert the Boolean logic circuits into an MPRM expression corresponding to the target polarity. Second, the proposed MDS is used to minimize the power of OR gates in the MPRM expression. Then, the MDS is implemented to further minimize the power of the MPRM expression. Finally, the fitness value f (Xi) of the target polarity Xi,g is obtained according to equation (20).Step 5. The adaptive scaling factorFi is calculated according to the proposed DEO, and the weighted object vector Vi,g is calculated. Individuals in the population perform the above steps in turn and finally, obtain the variation population PV,g in the flow chart.Step 6. The adaptive crossover factorCr,i is used in the crossover operator to generate the experimental vector Ur,g. A new population Px,g+1 was generated by comparing the experimental vector Ur,g and target vector Xr,g. All polarity global explorations are based on DEO.Step 7. Elite local exploration is performed based on the proposed SAO. SAO starts from a certain higher temperature, with the continuous decrease of temperature parameters, combined with the equilibrium probability equation (15) to find the global optimal solution of the objective function in the solution space.Step 8. If the termination condition is met, the optimal polarityXi,g+1 corresponding to the MPRM expression with the smallest power is output; otherwise, skip to Step 4.Figure 14
Overview of POA.


## 6.1. Encoding Scheme

Whether each polarity bit of the MPRM expression is displayed depends on whether the variable is true, complemented, or mixed; specifically, it is represented by 0, 1, and 2.Example 6.
Given a 7-variables MPRM expression, the ternary polarity “1212011” can be encoded as a 7-bits chromosome as shown in Figure13.Figure 13
Polarity encoding.


## 6.2. POA Description

The flow of POA is depicted in Figure14.Step 1. Read the Boolean logic circuits of then input variable.Step 2. Initialize the parameters of the POA. The parameters include the population scalePX,g, the termination condition, and the temperature cooling rate λ.Step 3. The initial population is generated based on DMA as shown byX0,g in the flow chart, individuals (i.e., polarities for MPRM circuits) are encoded as ternary bits, and the ternary chromosome number is shown in Figure 13.Step 4. The work of this paper is power optimization of MPRM circuits based on XNOR/OR, so the smaller the power, the larger the fitness value. Therefore, the fitness function is defined as follows:(20)fXi=1powerXi, where f (Xi) denotes the fitness value of polarity Xi and power (Xi) denotes the power of the polarity Xi. First, the proposed PPCA is used to convert the Boolean logic circuits into an MPRM expression corresponding to the target polarity. Second, the proposed MDS is used to minimize the power of OR gates in the MPRM expression. Then, the MDS is implemented to further minimize the power of the MPRM expression. Finally, the fitness value f (Xi) of the target polarity Xi,g is obtained according to equation (20).Step 5. The adaptive scaling factorFi is calculated according to the proposed DEO, and the weighted object vector Vi,g is calculated. Individuals in the population perform the above steps in turn and finally, obtain the variation population PV,g in the flow chart.Step 6. The adaptive crossover factorCr,i is used in the crossover operator to generate the experimental vector Ur,g. A new population Px,g+1 was generated by comparing the experimental vector Ur,g and target vector Xr,g. All polarity global explorations are based on DEO.Step 7. Elite local exploration is performed based on the proposed SAO. SAO starts from a certain higher temperature, with the continuous decrease of temperature parameters, combined with the equilibrium probability equation (15) to find the global optimal solution of the objective function in the solution space.Step 8. If the termination condition is met, the optimal polarityXi,g+1 corresponding to the MPRM expression with the smallest power is output; otherwise, skip to Step 4.Figure 14
Overview of POA.


## 7. Experiments and Results

We verified the effectiveness of the proposed power optimization approach (POA) through a series of experiments, which are described in detail in the following sections.


### 7.1. Algorithm Settings

Some intelligent algorithms-based POAs must be included in the comparison algorithms to prove MAMA effectiveness in optimizing MPRM circuit power. Therefore, three related works, namely, discrete differential evolution algorithm (DDEA)-based POA [42], binary differential Evolution algorithm (BDEA)-based POA [23], and GA-based POA [24], were chosen. Furthermore, to verify the validity of the PPCA and DMA, the conversion algorithm (CA) based on the tabular technique [21] and random initialization method (RIM) [17] were used for comparison. All experimental settings are fixed and the parameters of each comparison algorithm are set according to the original publication. Through repeated experiments, the parameters setting of the POA are listed in Table 2.Table 2
Parameters settings for power optimization approach.
ParameterValuePopulation size30Cooling rate0.6Acceptable time (min)5Minimum temperature1


### 7.2. Experimental Protocol

Microelectronics Center of North Carolina (MCNC) benchmark circuits were chosen as the test circuits, and the experimental results were obtained by using a PC with Intel Core i7 2.20 GHz with 8 G RAM. The scale of the test circuits represents the scale of the polarity search space, which is based on the input variablen. Moreover, experiments 2–7 used the same termination conditions; that is, there is no improvement in the optimal solution in population over ten iterations in an acceptable time. In addition, due to the randomness of all experimental approaches, 10 times were repeated on each test circuit, and the optimal value and average value were taken as experimental data.


### 7.3. Results and Analyses

The analysis of this paper is divided into seven parts.


#### 7.3.1. PPCA Verification

To further demonstrate the superiority of the PPCA (Algorithm2), in this subsection, we compare Algorithm 2 with the currently recognized convenient and effective conversion algorithm (CA) proposed in 2013 [21]. We test the correctness of PPCA and CA by using whether the same area is obtained under 0 polarity and take the time for all polarities in the population to complete polarity conversion as experimental data. For a fair comparison, we use circuits with different input scales and different population sizes, and the results are shown in Table 3.Table 3
Comparison of PPCA and CA.
CircuitsValuesao2amdbccScale—3∧103∧163∧260 polarityArea841909471N = 10CA (s)0.1266.780939.166PPCA (s)0.0993.45620.908N = 50CA (s)0.2149.998>3000PPCA (s)0.1575.10060.144N = 100CA (s)0.28430.451>5000PPCA (s)0.19513.828100.412SaveSave (N = 10)21%49%98%Save (N = 50)27%49%>99%Save (N = 100)31%55%>99%In Table3, line 1 is the name of the test circuits, line 2 is the size of the solution space, line 3 is the area of 0 polarity under this test circuit, N is the population size, and save is the time-saving rate.For example, 21% is the time-saving rate of CA compared to PPCA in sao2 circuits whereN is 10. From the results, we can see that on the larger scale of the circuits, PPCA can show a huger advantage, and the time-saving rate can reach more than 99%. The above results can be explained by the following reasons:(a)
The CA can only be converted from Boolean to any polarity and Boolean functions have many maximum terms, which can take a lot of time.(b)
In addition, earlier studies required the conversion between XOR logic and XNOR logic through De Morgan’s law, which took a lot of time. Through PPCA, not only can the Boolean logic be directly and quickly converted to XNOR logic but also the conversion between polarities can be realized, which greatly improves the running time and reduces the power of the device.


#### 7.3.2. DMA Verification

To verify the validity of the data matching algorithm (DMA) and the fairness of the selected algorithm, the genetic algorithm with the data matching algorithm (GA-DMA) was compared with the GA without the data matching algorithm on the search capability (i.e., the ability to find the minimum power). To ensure the fairness of the experiment, five test circuits were randomly selected, and all of them are continually used as the test circuits, including rd53, 5xp1, sao2, b2, and bcc. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of GA-DMA and GA is shown in Table4; the optimal value and average value obtained by GA are listed in columns 3 and 4; the optimal value and average value obtained by GA-DMA are listed in columns 5 and 6; the saving rate of GA-DMA on the optimal value and the average value compared with GA are represented in columns 7 and 8.Table 4
Comparison of GA-DMA and GA.
GAGA-DMASave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5531.8029.5531.80005xp13∧760.1164.1960.1163.1401.64sao23∧10305.93350.68300.11330.121.95.86b23∧162885.293790.752542.003120.311.917.69bcc3∧2694.35152.2185.21136.229.6910.51It can be seen from Table4 that for five circuits, the best value and average value obtained by GA-DMA are smaller than the value obtained by GA, namely, GA-DMA has a greater superiority in searching for optimal solutions compared with GA. Compared with the GA, GA-DMA has the maximum saving rate of 11.9% and 17.69% on the best value and average value. The main reason for the experimental results in Table 4 is that DMA adaptively adjusts the population diversity by fully considering the threshold between detection data and increasing the search area.


#### 7.3.3. DEO Verification

To verify the validity of the DEO, the traditional memetic algorithm (MA) with the DEO (MA-DEO) was compared with the MA without DEO (MA) on the search capability (i.e., the ability to find the minimum power). To ensure the fairness of the experiment, five test circuits were randomly selected, and all of them were continually used as test circuits. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of MA-DEO and MA is shown in Table5. The details in Table 5 are described in the previous section.Table 5
Comparison of MA-DEO and MA.
MAMA-DEOSave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5529.5529.5529.55005xp13∧760.1165.1160.1163.9901.72sao23∧10316.66377.3303.2341.24.259.57b23∧163002.13992.412469.082999.217.7524.88bcc3∧26110.2175.3384.63125.323.228.53From Table5, the best value and average value obtained by MA-DEO are smaller than the value obtained by MA, namely, MA-DEO has a greater superiority in searching for optimal solutions. Compared with the MA, MA-DEO has the maximum saving rate of 23.2% and 28.53% on the best value and average value. The main reason for the experimental results is that DEO can fully consider the relationship between individual fitness, population diversity, and iterations and improve the convergence speed and global search ability of the algorithm.


#### 7.3.4. SAO Verification

To verify the validity of the SAO, the traditional memetic algorithm (MA) with the SAO (MA- SAO) was compared with the MA without SAO (MA) on the search capability. Five test circuits were randomly selected, and all of them are continually used as test circuits. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of MA-SAO and MA is shown in Table6.Table 6
Comparison of MA-DEO and MA.
MAMA-SAOSave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5529.5529.5529.55005xp13∧760.1165.1160.1160.1107.68sao23∧10316.66377.3300.1321.335.2314.83b23∧163002.13992.412400.742856.3320.0328.46bcc3∧26110.2175.3384.3117.6223.532.92From Table6, the best value and average value obtained by MA-SAO are smaller than the value obtained by MA, namely, MA-SAO has a greater superiority in searching for optimal solutions. Compared with the MA, MA-SAO has the maximum saving rate of 23.5% and 32.92% on the best value and average value. The main reason for the above experimental results is that SAO can make the algorithm jump out of the local optimal and avoid excessive damage to the optimal solution structure.


#### 7.3.5. Comparison of DDEA, BDEA, GA, and POA on the Power

The comparison of DDEA, BDEA, GA, and POA on the power is listed in Table7. The best and ave represent the minimum power of the search and the average of the minimum power of ten searches. In Save_best, save1, save2, and save3 are the minimum power reduction rate of POA relative to DDEA, BDEA, and GA. In Save_average, save1, save2, and save3 are the average of the minimum power saving rate of POA relative to DDEA, BDEA, and GA.Table 7
Experimental results on the power.
CircuitValuerd535xp1rd84Clipsao2br1Table4alu4b2Table6bccbcde64Scale—3∧53∧73∧83∧93∧103∧123∧133∧143∧163∧173∧263∧263∧65DDEABest29.5366.6990.47460.88302.01261.463952.01823.122654.38121.91160.3194.01694.1Ave33.7090.11188.57561.89341.39318.624071.361782.003472.33184.60241.4232.431003.5BDEABest29.5361.6190.1420.85302.01241.762656.55824.092738.39120.7113.79231.16786.3Ave33.0383.10116.93499.44371.74280.563720.941049.273723.89173.89185.74231.46975.11GABest29.5560.1188.19420.94305.93243.893275.09812.292885.29120.794.35131.86600.3Ave31.8064.1990.38505.00350.68282.303979.55850.533790.75172.38152.21202.29800.36POABest29.5360.1160.16418.02293.95220.522375.64710.172174.7890.1159.0789.16364.11Ave31.2062.9763.36446.48318.35256.572947.05819.292730.79145.69109.75138.04523.2Save_best (%)Save10.009.8733.509.302.6715.6639.8913.7218.0726.0863.1554.0447.54Save20.002.4333.230.672.678.7910.5713.8220.5825.3448.0961.4353.69Save30.070.0031.780.693.929.5827.4612.5724.6325.3437.3932.3839.35Save_ave (%)Save17.4230.1266.4020.546.7519.4727.6254.0221.3621.0754.5440.6147.86Save25.5424.2245.8110.6014.368.5520.8021.9226.6716.2140.9140.3646.34Save31.891.9029.9011.599.229.1125.953.6727.9615.4827.9031.7634.63Table7 shows that for the 12 test circuits, the best values and average values of the power obtained by POA are smaller than those of DDEA, BDEA, and GA. Therefore, POA is superior to DDEA, BDEA, and GA in terms of performance and stability. Compared with DDEA, POA has a maximum saving rate of 63.15% and 66.40% on the best value and average value, respectively. Similarly, compared with BDEA, the saving rate of POA is 61.43% and 46.34%, respectively; compared with GA, the saving rate of POA is 39.35% and 34.63%, respectively. The experimental results can be explained by the following reasons:(a)
The power optimization for XNOR/OR-based MPRM logic circuits is a computationally difficult problem, and its computational complexity increases exponentially as the number of input variables increases. The previous intelligent optimization algorithms cannot fully consider the relationship of individual diversity, which lead to poor population diversity and wastes a lot of time in the early convergence process of the algorithm.(b)
The DMA adaptively adjusts the population diversity and increases the search area. In addition, using the proposed multilevel adaptive algorithm, DEO can fully consider the relationship between individual fitness, population diversity, and the number of iterations for probabilistic selection, which further improves the convergence speed and global search ability of POA.(c)
The SAO prevents POA from falling into the local optimum and avoids excessive destruction of the structure of the optimal solution.


#### 7.3.6. Statistical Significance Test

Wilcoxon signed ranks test with a significance level of 5% was used to judge whether there is a significant difference between POA and other comparison algorithms. We use MATLAB to calculate thep value which is shown in Table 8. “+/=/−” are used to indicate that POA’s performance in a test circuit is “significantly better/similar/significantly worse than” a comparison algorithm, respectively.Table 8
Experimental results of the statistical significance test by using the Wilcoxon signed ranks test.
CircuitsPOA vs. DDEAPOA vs. BDEAPOA vs. GArd533.900E − 03+7.420E − 02=3.750E − 01=5xp12.000E − 03+2.000E − 03+5.566E − 01=rd842.000E − 03+2.000E − 03+2.000E − 03+Clip3.900E − 03+1.309E − 01=4.880E − 02+sao22.754E − 01=4.880E − 02+3.900E − 03+br11.370E − 02=1.934E − 01=1.309E − 01=Table42.000E − 03+9.800E − 03+1.370E − 02+alu42.000E − 03+1.950E − 02=1.309E − 01=b22.000E − 03+3.900E − 03+3.900E − 03+Table63.223E − 01=3.223E − 01=1.309E − 01=Bcc2.000E − 03+1.950E − 02+4.880E − 02+Bcd2.000E − 03+2.000E − 03+1.950E − 02+e641.370E − 02=2.000E − 03+9.800E − 03++/=/−9/4/08/5/08/5/0From Table8, The p-value of POA in many test circuits is less than the significance level, indicating that there is a significant difference between the algorithms; that is, POA is far superior to comparison algorithms. Especially in large-scale circuits with more input variables, the convergence of POA will be stronger due to the large search space, so the significant difference between POA and other algorithms is more obvious.


#### 7.3.7. Comparison of DDEA, BDEA, GA, and POA on the Convergence

The convergence curves of the four approaches on six randomly selected test circuits (i.e., 5xp1, sao2, Table4, alu4, b2, and bcc) are displayed in Figures 15–20, where the horizontal axis shows the number of iterations and the vertical axis shows the power. As can be seen from Figures 15–20, the proposed POA has the fastest convergence speed, followed by the GA and BDEA, and the DDEA has the slowest convergence speed. The main reason for the rapid convergence of POA is that DMA can adapt to the diversity of the population and expand the search area. DEO and SAO can fully mine the effective information carried by individuals in the population so that the algorithm can converge quickly in a promising direction.Figure 15
5xp1 circuit.Figure 16
sao2 circuit.Figure 17
Table4 circuit.Figure 18
alu4 circuit.Figure 19
b2 circuit.Figure 20
bcc circuit.


## 7.1. Algorithm Settings

Some intelligent algorithms-based POAs must be included in the comparison algorithms to prove MAMA effectiveness in optimizing MPRM circuit power. Therefore, three related works, namely, discrete differential evolution algorithm (DDEA)-based POA [42], binary differential Evolution algorithm (BDEA)-based POA [23], and GA-based POA [24], were chosen. Furthermore, to verify the validity of the PPCA and DMA, the conversion algorithm (CA) based on the tabular technique [21] and random initialization method (RIM) [17] were used for comparison. All experimental settings are fixed and the parameters of each comparison algorithm are set according to the original publication. Through repeated experiments, the parameters setting of the POA are listed in Table 2.Table 2
Parameters settings for power optimization approach.
ParameterValuePopulation size30Cooling rate0.6Acceptable time (min)5Minimum temperature1


## 7.2. Experimental Protocol

Microelectronics Center of North Carolina (MCNC) benchmark circuits were chosen as the test circuits, and the experimental results were obtained by using a PC with Intel Core i7 2.20 GHz with 8 G RAM. The scale of the test circuits represents the scale of the polarity search space, which is based on the input variablen. Moreover, experiments 2–7 used the same termination conditions; that is, there is no improvement in the optimal solution in population over ten iterations in an acceptable time. In addition, due to the randomness of all experimental approaches, 10 times were repeated on each test circuit, and the optimal value and average value were taken as experimental data.


## 7.3. Results and Analyses

The analysis of this paper is divided into seven parts.


### 7.3.1. PPCA Verification

To further demonstrate the superiority of the PPCA (Algorithm2), in this subsection, we compare Algorithm 2 with the currently recognized convenient and effective conversion algorithm (CA) proposed in 2013 [21]. We test the correctness of PPCA and CA by using whether the same area is obtained under 0 polarity and take the time for all polarities in the population to complete polarity conversion as experimental data. For a fair comparison, we use circuits with different input scales and different population sizes, and the results are shown in Table 3.Table 3
Comparison of PPCA and CA.
CircuitsValuesao2amdbccScale—3∧103∧163∧260 polarityArea841909471N = 10CA (s)0.1266.780939.166PPCA (s)0.0993.45620.908N = 50CA (s)0.2149.998>3000PPCA (s)0.1575.10060.144N = 100CA (s)0.28430.451>5000PPCA (s)0.19513.828100.412SaveSave (N = 10)21%49%98%Save (N = 50)27%49%>99%Save (N = 100)31%55%>99%In Table3, line 1 is the name of the test circuits, line 2 is the size of the solution space, line 3 is the area of 0 polarity under this test circuit, N is the population size, and save is the time-saving rate.For example, 21% is the time-saving rate of CA compared to PPCA in sao2 circuits whereN is 10. From the results, we can see that on the larger scale of the circuits, PPCA can show a huger advantage, and the time-saving rate can reach more than 99%. The above results can be explained by the following reasons:(a)
The CA can only be converted from Boolean to any polarity and Boolean functions have many maximum terms, which can take a lot of time.(b)
In addition, earlier studies required the conversion between XOR logic and XNOR logic through De Morgan’s law, which took a lot of time. Through PPCA, not only can the Boolean logic be directly and quickly converted to XNOR logic but also the conversion between polarities can be realized, which greatly improves the running time and reduces the power of the device.


### 7.3.2. DMA Verification

To verify the validity of the data matching algorithm (DMA) and the fairness of the selected algorithm, the genetic algorithm with the data matching algorithm (GA-DMA) was compared with the GA without the data matching algorithm on the search capability (i.e., the ability to find the minimum power). To ensure the fairness of the experiment, five test circuits were randomly selected, and all of them are continually used as the test circuits, including rd53, 5xp1, sao2, b2, and bcc. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of GA-DMA and GA is shown in Table4; the optimal value and average value obtained by GA are listed in columns 3 and 4; the optimal value and average value obtained by GA-DMA are listed in columns 5 and 6; the saving rate of GA-DMA on the optimal value and the average value compared with GA are represented in columns 7 and 8.Table 4
Comparison of GA-DMA and GA.
GAGA-DMASave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5531.8029.5531.80005xp13∧760.1164.1960.1163.1401.64sao23∧10305.93350.68300.11330.121.95.86b23∧162885.293790.752542.003120.311.917.69bcc3∧2694.35152.2185.21136.229.6910.51It can be seen from Table4 that for five circuits, the best value and average value obtained by GA-DMA are smaller than the value obtained by GA, namely, GA-DMA has a greater superiority in searching for optimal solutions compared with GA. Compared with the GA, GA-DMA has the maximum saving rate of 11.9% and 17.69% on the best value and average value. The main reason for the experimental results in Table 4 is that DMA adaptively adjusts the population diversity by fully considering the threshold between detection data and increasing the search area.


### 7.3.3. DEO Verification

To verify the validity of the DEO, the traditional memetic algorithm (MA) with the DEO (MA-DEO) was compared with the MA without DEO (MA) on the search capability (i.e., the ability to find the minimum power). To ensure the fairness of the experiment, five test circuits were randomly selected, and all of them were continually used as test circuits. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of MA-DEO and MA is shown in Table5. The details in Table 5 are described in the previous section.Table 5
Comparison of MA-DEO and MA.
MAMA-DEOSave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5529.5529.5529.55005xp13∧760.1165.1160.1163.9901.72sao23∧10316.66377.3303.2341.24.259.57b23∧163002.13992.412469.082999.217.7524.88bcc3∧26110.2175.3384.63125.323.228.53From Table5, the best value and average value obtained by MA-DEO are smaller than the value obtained by MA, namely, MA-DEO has a greater superiority in searching for optimal solutions. Compared with the MA, MA-DEO has the maximum saving rate of 23.2% and 28.53% on the best value and average value. The main reason for the experimental results is that DEO can fully consider the relationship between individual fitness, population diversity, and iterations and improve the convergence speed and global search ability of the algorithm.


### 7.3.4. SAO Verification

To verify the validity of the SAO, the traditional memetic algorithm (MA) with the SAO (MA- SAO) was compared with the MA without SAO (MA) on the search capability. Five test circuits were randomly selected, and all of them are continually used as test circuits. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of MA-SAO and MA is shown in Table6.Table 6
Comparison of MA-DEO and MA.
MAMA-SAOSave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5529.5529.5529.55005xp13∧760.1165.1160.1160.1107.68sao23∧10316.66377.3300.1321.335.2314.83b23∧163002.13992.412400.742856.3320.0328.46bcc3∧26110.2175.3384.3117.6223.532.92From Table6, the best value and average value obtained by MA-SAO are smaller than the value obtained by MA, namely, MA-SAO has a greater superiority in searching for optimal solutions. Compared with the MA, MA-SAO has the maximum saving rate of 23.5% and 32.92% on the best value and average value. The main reason for the above experimental results is that SAO can make the algorithm jump out of the local optimal and avoid excessive damage to the optimal solution structure.


### 7.3.5. Comparison of DDEA, BDEA, GA, and POA on the Power

The comparison of DDEA, BDEA, GA, and POA on the power is listed in Table7. The best and ave represent the minimum power of the search and the average of the minimum power of ten searches. In Save_best, save1, save2, and save3 are the minimum power reduction rate of POA relative to DDEA, BDEA, and GA. In Save_average, save1, save2, and save3 are the average of the minimum power saving rate of POA relative to DDEA, BDEA, and GA.Table 7
Experimental results on the power.
CircuitValuerd535xp1rd84Clipsao2br1Table4alu4b2Table6bccbcde64Scale—3∧53∧73∧83∧93∧103∧123∧133∧143∧163∧173∧263∧263∧65DDEABest29.5366.6990.47460.88302.01261.463952.01823.122654.38121.91160.3194.01694.1Ave33.7090.11188.57561.89341.39318.624071.361782.003472.33184.60241.4232.431003.5BDEABest29.5361.6190.1420.85302.01241.762656.55824.092738.39120.7113.79231.16786.3Ave33.0383.10116.93499.44371.74280.563720.941049.273723.89173.89185.74231.46975.11GABest29.5560.1188.19420.94305.93243.893275.09812.292885.29120.794.35131.86600.3Ave31.8064.1990.38505.00350.68282.303979.55850.533790.75172.38152.21202.29800.36POABest29.5360.1160.16418.02293.95220.522375.64710.172174.7890.1159.0789.16364.11Ave31.2062.9763.36446.48318.35256.572947.05819.292730.79145.69109.75138.04523.2Save_best (%)Save10.009.8733.509.302.6715.6639.8913.7218.0726.0863.1554.0447.54Save20.002.4333.230.672.678.7910.5713.8220.5825.3448.0961.4353.69Save30.070.0031.780.693.929.5827.4612.5724.6325.3437.3932.3839.35Save_ave (%)Save17.4230.1266.4020.546.7519.4727.6254.0221.3621.0754.5440.6147.86Save25.5424.2245.8110.6014.368.5520.8021.9226.6716.2140.9140.3646.34Save31.891.9029.9011.599.229.1125.953.6727.9615.4827.9031.7634.63Table7 shows that for the 12 test circuits, the best values and average values of the power obtained by POA are smaller than those of DDEA, BDEA, and GA. Therefore, POA is superior to DDEA, BDEA, and GA in terms of performance and stability. Compared with DDEA, POA has a maximum saving rate of 63.15% and 66.40% on the best value and average value, respectively. Similarly, compared with BDEA, the saving rate of POA is 61.43% and 46.34%, respectively; compared with GA, the saving rate of POA is 39.35% and 34.63%, respectively. The experimental results can be explained by the following reasons:(a)
The power optimization for XNOR/OR-based MPRM logic circuits is a computationally difficult problem, and its computational complexity increases exponentially as the number of input variables increases. The previous intelligent optimization algorithms cannot fully consider the relationship of individual diversity, which lead to poor population diversity and wastes a lot of time in the early convergence process of the algorithm.(b)
The DMA adaptively adjusts the population diversity and increases the search area. In addition, using the proposed multilevel adaptive algorithm, DEO can fully consider the relationship between individual fitness, population diversity, and the number of iterations for probabilistic selection, which further improves the convergence speed and global search ability of POA.(c)
The SAO prevents POA from falling into the local optimum and avoids excessive destruction of the structure of the optimal solution.


### 7.3.6. Statistical Significance Test

Wilcoxon signed ranks test with a significance level of 5% was used to judge whether there is a significant difference between POA and other comparison algorithms. We use MATLAB to calculate thep value which is shown in Table 8. “+/=/−” are used to indicate that POA’s performance in a test circuit is “significantly better/similar/significantly worse than” a comparison algorithm, respectively.Table 8
Experimental results of the statistical significance test by using the Wilcoxon signed ranks test.
CircuitsPOA vs. DDEAPOA vs. BDEAPOA vs. GArd533.900E − 03+7.420E − 02=3.750E − 01=5xp12.000E − 03+2.000E − 03+5.566E − 01=rd842.000E − 03+2.000E − 03+2.000E − 03+Clip3.900E − 03+1.309E − 01=4.880E − 02+sao22.754E − 01=4.880E − 02+3.900E − 03+br11.370E − 02=1.934E − 01=1.309E − 01=Table42.000E − 03+9.800E − 03+1.370E − 02+alu42.000E − 03+1.950E − 02=1.309E − 01=b22.000E − 03+3.900E − 03+3.900E − 03+Table63.223E − 01=3.223E − 01=1.309E − 01=Bcc2.000E − 03+1.950E − 02+4.880E − 02+Bcd2.000E − 03+2.000E − 03+1.950E − 02+e641.370E − 02=2.000E − 03+9.800E − 03++/=/−9/4/08/5/08/5/0From Table8, The p-value of POA in many test circuits is less than the significance level, indicating that there is a significant difference between the algorithms; that is, POA is far superior to comparison algorithms. Especially in large-scale circuits with more input variables, the convergence of POA will be stronger due to the large search space, so the significant difference between POA and other algorithms is more obvious.


### 7.3.7. Comparison of DDEA, BDEA, GA, and POA on the Convergence

The convergence curves of the four approaches on six randomly selected test circuits (i.e., 5xp1, sao2, Table4, alu4, b2, and bcc) are displayed in Figures 15–20, where the horizontal axis shows the number of iterations and the vertical axis shows the power. As can be seen from Figures 15–20, the proposed POA has the fastest convergence speed, followed by the GA and BDEA, and the DDEA has the slowest convergence speed. The main reason for the rapid convergence of POA is that DMA can adapt to the diversity of the population and expand the search area. DEO and SAO can fully mine the effective information carried by individuals in the population so that the algorithm can converge quickly in a promising direction.Figure 15
5xp1 circuit.Figure 16
sao2 circuit.Figure 17
Table4 circuit.Figure 18
alu4 circuit.Figure 19
b2 circuit.Figure 20
bcc circuit.


## 7.3.1. PPCA Verification

To further demonstrate the superiority of the PPCA (Algorithm2), in this subsection, we compare Algorithm 2 with the currently recognized convenient and effective conversion algorithm (CA) proposed in 2013 [21]. We test the correctness of PPCA and CA by using whether the same area is obtained under 0 polarity and take the time for all polarities in the population to complete polarity conversion as experimental data. For a fair comparison, we use circuits with different input scales and different population sizes, and the results are shown in Table 3.Table 3
Comparison of PPCA and CA.
CircuitsValuesao2amdbccScale—3∧103∧163∧260 polarityArea841909471N = 10CA (s)0.1266.780939.166PPCA (s)0.0993.45620.908N = 50CA (s)0.2149.998>3000PPCA (s)0.1575.10060.144N = 100CA (s)0.28430.451>5000PPCA (s)0.19513.828100.412SaveSave (N = 10)21%49%98%Save (N = 50)27%49%>99%Save (N = 100)31%55%>99%In Table3, line 1 is the name of the test circuits, line 2 is the size of the solution space, line 3 is the area of 0 polarity under this test circuit, N is the population size, and save is the time-saving rate.For example, 21% is the time-saving rate of CA compared to PPCA in sao2 circuits whereN is 10. From the results, we can see that on the larger scale of the circuits, PPCA can show a huger advantage, and the time-saving rate can reach more than 99%. The above results can be explained by the following reasons:(a)
The CA can only be converted from Boolean to any polarity and Boolean functions have many maximum terms, which can take a lot of time.(b)
In addition, earlier studies required the conversion between XOR logic and XNOR logic through De Morgan’s law, which took a lot of time. Through PPCA, not only can the Boolean logic be directly and quickly converted to XNOR logic but also the conversion between polarities can be realized, which greatly improves the running time and reduces the power of the device.


## 7.3.2. DMA Verification

To verify the validity of the data matching algorithm (DMA) and the fairness of the selected algorithm, the genetic algorithm with the data matching algorithm (GA-DMA) was compared with the GA without the data matching algorithm on the search capability (i.e., the ability to find the minimum power). To ensure the fairness of the experiment, five test circuits were randomly selected, and all of them are continually used as the test circuits, including rd53, 5xp1, sao2, b2, and bcc. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of GA-DMA and GA is shown in Table4; the optimal value and average value obtained by GA are listed in columns 3 and 4; the optimal value and average value obtained by GA-DMA are listed in columns 5 and 6; the saving rate of GA-DMA on the optimal value and the average value compared with GA are represented in columns 7 and 8.Table 4
Comparison of GA-DMA and GA.
GAGA-DMASave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5531.8029.5531.80005xp13∧760.1164.1960.1163.1401.64sao23∧10305.93350.68300.11330.121.95.86b23∧162885.293790.752542.003120.311.917.69bcc3∧2694.35152.2185.21136.229.6910.51It can be seen from Table4 that for five circuits, the best value and average value obtained by GA-DMA are smaller than the value obtained by GA, namely, GA-DMA has a greater superiority in searching for optimal solutions compared with GA. Compared with the GA, GA-DMA has the maximum saving rate of 11.9% and 17.69% on the best value and average value. The main reason for the experimental results in Table 4 is that DMA adaptively adjusts the population diversity by fully considering the threshold between detection data and increasing the search area.


## 7.3.3. DEO Verification

To verify the validity of the DEO, the traditional memetic algorithm (MA) with the DEO (MA-DEO) was compared with the MA without DEO (MA) on the search capability (i.e., the ability to find the minimum power). To ensure the fairness of the experiment, five test circuits were randomly selected, and all of them were continually used as test circuits. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of MA-DEO and MA is shown in Table5. The details in Table 5 are described in the previous section.Table 5
Comparison of MA-DEO and MA.
MAMA-DEOSave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5529.5529.5529.55005xp13∧760.1165.1160.1163.9901.72sao23∧10316.66377.3303.2341.24.259.57b23∧163002.13992.412469.082999.217.7524.88bcc3∧26110.2175.3384.63125.323.228.53From Table5, the best value and average value obtained by MA-DEO are smaller than the value obtained by MA, namely, MA-DEO has a greater superiority in searching for optimal solutions. Compared with the MA, MA-DEO has the maximum saving rate of 23.2% and 28.53% on the best value and average value. The main reason for the experimental results is that DEO can fully consider the relationship between individual fitness, population diversity, and iterations and improve the convergence speed and global search ability of the algorithm.


## 7.3.4. SAO Verification

To verify the validity of the SAO, the traditional memetic algorithm (MA) with the SAO (MA- SAO) was compared with the MA without SAO (MA) on the search capability. Five test circuits were randomly selected, and all of them are continually used as test circuits. The above two algorithms were repeated 10 times on each test circuit, and the optimal value and average value were taken as experimental data. The comparison of MA-SAO and MA is shown in Table6.Table 6
Comparison of MA-DEO and MA.
MAMA-SAOSave_best (%)Save_ave (%)CircuitsScaleBestAveBestAverd533∧529.5529.5529.5529.55005xp13∧760.1165.1160.1160.1107.68sao23∧10316.66377.3300.1321.335.2314.83b23∧163002.13992.412400.742856.3320.0328.46bcc3∧26110.2175.3384.3117.6223.532.92From Table6, the best value and average value obtained by MA-SAO are smaller than the value obtained by MA, namely, MA-SAO has a greater superiority in searching for optimal solutions. Compared with the MA, MA-SAO has the maximum saving rate of 23.5% and 32.92% on the best value and average value. The main reason for the above experimental results is that SAO can make the algorithm jump out of the local optimal and avoid excessive damage to the optimal solution structure.


## 7.3.5. Comparison of DDEA, BDEA, GA, and POA on the Power

The comparison of DDEA, BDEA, GA, and POA on the power is listed in Table7. The best and ave represent the minimum power of the search and the average of the minimum power of ten searches. In Save_best, save1, save2, and save3 are the minimum power reduction rate of POA relative to DDEA, BDEA, and GA. In Save_average, save1, save2, and save3 are the average of the minimum power saving rate of POA relative to DDEA, BDEA, and GA.Table 7
Experimental results on the power.
CircuitValuerd535xp1rd84Clipsao2br1Table4alu4b2Table6bccbcde64Scale—3∧53∧73∧83∧93∧103∧123∧133∧143∧163∧173∧263∧263∧65DDEABest29.5366.6990.47460.88302.01261.463952.01823.122654.38121.91160.3194.01694.1Ave33.7090.11188.57561.89341.39318.624071.361782.003472.33184.60241.4232.431003.5BDEABest29.5361.6190.1420.85302.01241.762656.55824.092738.39120.7113.79231.16786.3Ave33.0383.10116.93499.44371.74280.563720.941049.273723.89173.89185.74231.46975.11GABest29.5560.1188.19420.94305.93243.893275.09812.292885.29120.794.35131.86600.3Ave31.8064.1990.38505.00350.68282.303979.55850.533790.75172.38152.21202.29800.36POABest29.5360.1160.16418.02293.95220.522375.64710.172174.7890.1159.0789.16364.11Ave31.2062.9763.36446.48318.35256.572947.05819.292730.79145.69109.75138.04523.2Save_best (%)Save10.009.8733.509.302.6715.6639.8913.7218.0726.0863.1554.0447.54Save20.002.4333.230.672.678.7910.5713.8220.5825.3448.0961.4353.69Save30.070.0031.780.693.929.5827.4612.5724.6325.3437.3932.3839.35Save_ave (%)Save17.4230.1266.4020.546.7519.4727.6254.0221.3621.0754.5440.6147.86Save25.5424.2245.8110.6014.368.5520.8021.9226.6716.2140.9140.3646.34Save31.891.9029.9011.599.229.1125.953.6727.9615.4827.9031.7634.63Table7 shows that for the 12 test circuits, the best values and average values of the power obtained by POA are smaller than those of DDEA, BDEA, and GA. Therefore, POA is superior to DDEA, BDEA, and GA in terms of performance and stability. Compared with DDEA, POA has a maximum saving rate of 63.15% and 66.40% on the best value and average value, respectively. Similarly, compared with BDEA, the saving rate of POA is 61.43% and 46.34%, respectively; compared with GA, the saving rate of POA is 39.35% and 34.63%, respectively. The experimental results can be explained by the following reasons:(a)
The power optimization for XNOR/OR-based MPRM logic circuits is a computationally difficult problem, and its computational complexity increases exponentially as the number of input variables increases. The previous intelligent optimization algorithms cannot fully consider the relationship of individual diversity, which lead to poor population diversity and wastes a lot of time in the early convergence process of the algorithm.(b)
The DMA adaptively adjusts the population diversity and increases the search area. In addition, using the proposed multilevel adaptive algorithm, DEO can fully consider the relationship between individual fitness, population diversity, and the number of iterations for probabilistic selection, which further improves the convergence speed and global search ability of POA.(c)
The SAO prevents POA from falling into the local optimum and avoids excessive destruction of the structure of the optimal solution.


## 7.3.6. Statistical Significance Test

Wilcoxon signed ranks test with a significance level of 5% was used to judge whether there is a significant difference between POA and other comparison algorithms. We use MATLAB to calculate thep value which is shown in Table 8. “+/=/−” are used to indicate that POA’s performance in a test circuit is “significantly better/similar/significantly worse than” a comparison algorithm, respectively.Table 8
Experimental results of the statistical significance test by using the Wilcoxon signed ranks test.
CircuitsPOA vs. DDEAPOA vs. BDEAPOA vs. GArd533.900E − 03+7.420E − 02=3.750E − 01=5xp12.000E − 03+2.000E − 03+5.566E − 01=rd842.000E − 03+2.000E − 03+2.000E − 03+Clip3.900E − 03+1.309E − 01=4.880E − 02+sao22.754E − 01=4.880E − 02+3.900E − 03+br11.370E − 02=1.934E − 01=1.309E − 01=Table42.000E − 03+9.800E − 03+1.370E − 02+alu42.000E − 03+1.950E − 02=1.309E − 01=b22.000E − 03+3.900E − 03+3.900E − 03+Table63.223E − 01=3.223E − 01=1.309E − 01=Bcc2.000E − 03+1.950E − 02+4.880E − 02+Bcd2.000E − 03+2.000E − 03+1.950E − 02+e641.370E − 02=2.000E − 03+9.800E − 03++/=/−9/4/08/5/08/5/0From Table8, The p-value of POA in many test circuits is less than the significance level, indicating that there is a significant difference between the algorithms; that is, POA is far superior to comparison algorithms. Especially in large-scale circuits with more input variables, the convergence of POA will be stronger due to the large search space, so the significant difference between POA and other algorithms is more obvious.


## 7.3.7. Comparison of DDEA, BDEA, GA, and POA on the Convergence

The convergence curves of the four approaches on six randomly selected test circuits (i.e., 5xp1, sao2, Table4, alu4, b2, and bcc) are displayed in Figures 15–20, where the horizontal axis shows the number of iterations and the vertical axis shows the power. As can be seen from Figures 15–20, the proposed POA has the fastest convergence speed, followed by the GA and BDEA, and the DDEA has the slowest convergence speed. The main reason for the rapid convergence of POA is that DMA can adapt to the diversity of the population and expand the search area. DEO and SAO can fully mine the effective information carried by individuals in the population so that the algorithm can converge quickly in a promising direction.Figure 15
5xp1 circuit.Figure 16
sao2 circuit.Figure 17
Table4 circuit.Figure 18
alu4 circuit.Figure 19
b2 circuit.Figure 20
bcc circuit.


## 8. Conclusion

Power optimization for XNOR/OR-based MPRM circuits is a multiextremum optimization problem. We first propose a MAMA, which includes a global exploration optimizer, local heuristic optimizer, and initial population optimizer. MAMA can adaptively adjust individual diversity and expand the search area. Moreover, based on the proposed MDS and PPCA, we propose a power optimization approach for MPRM circuits, called POA, which searches the best polarity corresponding to an MPRM circuit with minimum power using MAMA.The experiment mainly includes seven parts: comparison of PPCA on the polarity conversion, DMA verification, DEO verification, SAO verification, comparison of experimental algorithms on the power, statistical test, and comparison of experimental algorithms on the convergence. The comprehensive experimental results show the effectiveness and superiority of the POA in the power optimization of MPRM circuits and can be used as a promising CAD tool.There are several possible directions to extend this work in the future. First, with the development of delay optimization, it is necessary to study the problem of delay optimization based on XNOR/OR logic circuits. Second, multiobjective optimization is an important part of the engineering field. We can apply the proposed approaches in this paper to multiobjective optimization problems to obtain more nondominated solutions. Finally, it is also interesting work to study the characteristics of the initial populations generated when DMA is applied to different types of optimization problems.



---

*Source: 3510001-2023-03-06.xml*