# Hardware Trojan Detection Based on Ordered Mixed Feature GEP

Authors: Huan Zhang; Jiliu Zhou; Dongrui Gao; Xinguo Wang; Zhefan Chen; Hongyu Wang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In the hardware Trojan detection field, destructive reverse engineering and bypass detection are both important methods. This paper proposed an evolutionary algorithm called Ordered Mixed Feature GEP (OMF-GEP), trying to restore the circuit structure only by using the bypass information. This algorithm was developed from the basic GEP through three sets of experiments at different stages. To solve the problem, this paper transformed the GEP by introducing mixed features, ordered genes, and superchromosomes. And the experiment results show that the algorithm is effective.


---

## Body

## 1. Introduction

At all stages of the life cycle of integrated circuits (IC), there are security vulnerabilities for hardware in the global business model of semiconductor supply chain. In the current hardware Trojan detection technology, destructive reverse engineering [1–3] is good but costly bypass detection [4–9] is the technology whose cost is low, which is a development key direction at present.An evolutionary algorithm called Ordered Mixed Feature GEP (OMF-GEP) is proposed in this paper. This algorithm takes a single-circuit component as a node to form a mixed feature of various logical or physical features of the node. And it can find the original circuit by using the GEP function regression ability.


## 2. Mixed Features

The logic value of a circuit or any kind of bypass information such as voltage and current can be considered as a manifestation of a characteristic of the circuit. When only one characteristic representation value is used to represent the circuit, if other constraints are not added, there will undoubtedly be a variety of circuits to meet the requirements of this single feature. The two circuits are shown in Figure1.Figure 1
Two circuits with the same logical value.
(a)(b)If you look only at the logical values, the two circuits are completely equivalent, and both of which are(1)Y=CD.You can also see that in the circuit in Figure1(b), inputs A and B are used at all; that not, the input s A and B in the first circuit do not actually affect the output.This example is only the value of the circuit logic value and the circuit bypass information detection, and there is a similar situation. Multiple different circuit structures can be obtained for the detection results of any single bypass information. It can be seen that only using logical values or bypass information to describe the circuit will lead to too much isomorphism to confirm the circuit structure.The essence of hardware Trojan horse design is to add additional circuit to normal circuits, but the performance of the whole circuit on some features (the most common is the logic value) is the same as that of the normal circuit, to realize hiding. However, this additional circuit will inevitably cause other circuit features to change.In this paper, the logic value of the circuit or any kind of bypass information such as voltage and current is called a feature. For the isomorphism of a feature, it is essentially due to the superposition of the features of the circuit elements on the feature. The features of multiple different circuit structures with the feature are similar or even the same, so that the corresponding circuit cannot be represented by the result of a feature.Then, when detecting multiple features at the same time, multiple isomorphic circuits can be obtained from the detection results of each feature, but the superposition features of different features cannot be exactly the same. These isomorphic circuits cannot be the same, where the same part is a possible real circuit.Figure2 illustrates the application of the algorithm to a diode-designed And gated circuit.Figure 2
And gate circuits.Its logical meaning is(2)Y=A⋅B.It has a lot of physical meaning. Here is description of its voltage:(3)Vy=minVA,VB+Vdio.Among them,Vy represents voltage of the output position Y; VA and VB represent the voltage values of two input locations A and B; Vdio represents the diode conduction voltage for silicon tubes, and its value is often 0.7.Then, the And gate can be expressed as(4)ylogic,yv=Gandx1_logic,x2_logic,x1_v,x2_v.Then, a measurement ofk features, n input, and single-output single-gate circuit can be expressed as Expression 1:(5)y1,y2,…,yk=Gx1,1,x1,2,…,x1,n,x2,1,x2,2,…,x2,n,…,xk,1,xk,2,…,xk,n.Among them,yii=1,…k is the output values for the adoption of the kth feature. xi,ji=1,…,k,j=1,…n is the ith input value for the adoption of the feature j.Without losing generality, let us define(6)Y=y1,y2,…yk,Xi=x1,i,x2,i,…,xn,iT,i=1,2,…,k,X=X1,X2,…,Xk.Then, Expression 1 can be expressed as(7)Y1∗k=GXn∗k,which is Expression 2.


## 3. Algorithm 1: Single-Output Circuit

### 3.1. GEP Representation

In recent years, there have been many studies based on evolutionary algorithms and multisource data such as data fusion of adaptive weighted multisource sensor [10], the research on evolutionary algorithm for symbolic network [11], the application of the genetic algorithm in multiobjective multicast routing [12], and multiplicity problems in genetic association studies [13]. Zhi and Liu [14] proposed a new GA algorithm for mechanical design optimization problems. These studies gave us the inspiration to use the evolutionary algorithms in the hardware Trojan detection.Gene expression programming (GEP) [15] is an evolutionary computing algorithm that has performed well in the study of evolutionary hardware [16–22]. It can solve the problem of tree structure very well. For the multi-input/single-output tree structure circuit, it can be described as a tree with n leaf nodes, which can be represented directly by GEP. As shown in Figure 3, the 6-input/1-output logic circuit can be easily represented as a tree structure, in which the logic gate function is replaced by the logic symbol, and the corresponding effective gene is(8)And,And,And,A,Not,And,And,B,C,Not,E,F,D.Figure 3
A single-output circuit and its expression tree.
(a)(b)


### 3.2. Algorithm of Mixed Feature GEP

One operator in GEP represents only one kind of calculation, and a GEP individual can only represent one test item, so the idea of algorithm one is to merge the multiple test results of a basic circuit into a function expression. Combined into a compound function, that is, let a function represent multiple calculations and evolve a representation close to the original circuit. Specifically, these multiple detection values are included in a function, the input of the function is multiple values, and the output result is a vector, such as the aforementioned gate circuit, which is still represented as “And” in the GEP expression tree. However, its meaning has become the following vector calculation:(9)AndA1,A2,…An=F1A1,F2A2,…,FnAn.TheAk=k=1,…n is the input value of a detection, and FkAkk=1,…n is the result of this detection Ak to the input value.For example, for this gate circuit, the symbol And means the following:(10)AndLA,LB,VA,VB,CA,CB=LALB,minVA,VB+Vdio,CA+CB.Among them,LA,LB represent the logical value (1 or 0) of voltage input of the A or B point, VA,VB represent the input voltage of the A or B point, and CA,CB represent the input current of the A or B point.Thus, when using GEP evolution, a symbolic value can simultaneously represent multiple unrelated items. This algorithm will be called Mixed Feature GEP (MF-GEP).


### 3.3. Experiment Setup

The experiment is limited to the use of simple logic gate circuits, does not involve triggers, clocks, etc., and does not consider time effects.Four groups of experiments were designed.Outputm=1,The number of features arek=1,2,2,3.Three features are used: feature 1 is the logical value, feature 2 is the voltage value, and feature 3 is the current value.As a comparative experiment, the parameters used are identical as Table1 shows.Table 1
Parameter settings for experiment 1.
ParameterValueStopFitness = 1Selection modeTournament, size = 3Population size10000Head length20Tail length21Chromosome length1Mutation rate0.05Insert rate0.1Root insert rate0.01One-point cross rate0.1Two-point cross rate0.1Input number4Output number1Function setNot, and, or


### 3.4. Design of Fitness Function

The feature data are logic data, voltage data, and current data, which have their own fitness.Logical data fitness is(11)Flogic=1−∑i=1Nyi−yN,which is Expression 3.N is the number of test data, yi is the logic value calculated according to the test data after decoding, and y is the output logic value of the test data. Because it is a logical value, the worst case is that each output decoded by the individual is opposite to the test value, that is, yi−y=1, so Flogic is among the range of 0,1.Voltage data fitness is(12)Fvol=1−∑i=1Nyi−y/NVCC−VDD,which is Expression 4.N is the number of test data, yi is the voltage value calculated according to the test data after decoding, and y is the output voltage value of the test data. At worst, each test output value is either the highest level or the lowest level, and each output decoded by the individual is opposite to the test value yi−y=VCC−VDD; therefore, Fvol is among the range of 0,1.Current data fitness is(13)Fcir=1−SSESST,which is Expression 5.Among them,(14)SSE=∑i=1myi−yˆi2,SST=∑i=1myi−y¯i2,where yi is the data observation, y^i is the estimate value of the yi which is calculated from the decoding expression, and y¯i is the average value of the variable y. That is, the SSE is the Sum of Squared Errors and the SST is the Sum of Squares in Total. Fcir the square of the multicorrelation coefficient in statistics.According to the previous algorithm description, the individual fitness should be a combination of the three; then, the individual fitness is(15)F=C1·Flogic+C2·Fvol+C3·Fcir,∑Ck=1,which is Expression 6: individual fitness expression.C1,C2,C3 are the weight of three features in the final fitness.


### 3.5. Experiment

Figure4 shows a circuit. Its Boolean expression is(16)Y=A+BCD′+BC′D.Figure 4
A circuit with a Trojan.Its calculation is(17)Y=0,ABCD<01012orABCD=01112.1,else.The input valueABCD=01112 can be seen as the Trojan trigger conditions. When there are more pins, only part of the value can be tested, and you may miss the input ABCD=01112. In the following experiment, the input data will not provide the 0111 value to trigger the Trojan, and the output of the input value will be determined by the evolved circuit.Its effective gene is(18)Or,A,Or,And,And,B,And,B,And,Not,D,C,Not,C,D.Using different combination forms, we designed 4 groups of experiments. Considering that the logic value is required to be correct first in the circuit, the voltage value and the current value must be meaningful on the basis of the correct logic value, so the logic value is included in each group of experiments, and the fitness of the individual combines several data; the logical value accounts for a larger proportion. Table2 shows the results of the experiments.Table 2
Comparison of results of 4 groups in experiment 1.
ParameterExp1ValueExp2ValueExp3ValueExp4ValueLogic gateAnd, or, notAnd, or, notAnd, or, notAnd, or, notValues providedLogic valuesLogic valuesLogic valuesLogic valuesVoltage valuesCurrent valuesVoltage valuesCurrent valuesFitness functionF=F1F=0.8·F1+0.2·F2F=0.8·F1+0.2·F3F=0.6·F1+0.2·F2+0.2·F3Exercise count100Trojan discovered count007267The experimental results show the following:(1)
Only using a single feature cannot find Trojan circuit.(2)
Using multiple features can effectively discover Trojan circuits.(3)
The features with direct correlation have no effect on the discovery probability of Trojan horse: in experiment 2, two features of logic value and voltage are used at the same time, and the Trojan horse cannot be found; in experiment 4, although three features are used, the probability of finding Trojan horse is not higher than that of real 3. The reason is that in digital circuits, the logical value itself is expressed by the voltage value; for example, the voltage value less than 3 V is considered 0, and the voltage value greater than 3 V is considered 1. Therefore, there is no difference between the logic value and voltage value.


## 3.1. GEP Representation

In recent years, there have been many studies based on evolutionary algorithms and multisource data such as data fusion of adaptive weighted multisource sensor [10], the research on evolutionary algorithm for symbolic network [11], the application of the genetic algorithm in multiobjective multicast routing [12], and multiplicity problems in genetic association studies [13]. Zhi and Liu [14] proposed a new GA algorithm for mechanical design optimization problems. These studies gave us the inspiration to use the evolutionary algorithms in the hardware Trojan detection.Gene expression programming (GEP) [15] is an evolutionary computing algorithm that has performed well in the study of evolutionary hardware [16–22]. It can solve the problem of tree structure very well. For the multi-input/single-output tree structure circuit, it can be described as a tree with n leaf nodes, which can be represented directly by GEP. As shown in Figure 3, the 6-input/1-output logic circuit can be easily represented as a tree structure, in which the logic gate function is replaced by the logic symbol, and the corresponding effective gene is(8)And,And,And,A,Not,And,And,B,C,Not,E,F,D.Figure 3
A single-output circuit and its expression tree.
(a)(b)


## 3.2. Algorithm of Mixed Feature GEP

One operator in GEP represents only one kind of calculation, and a GEP individual can only represent one test item, so the idea of algorithm one is to merge the multiple test results of a basic circuit into a function expression. Combined into a compound function, that is, let a function represent multiple calculations and evolve a representation close to the original circuit. Specifically, these multiple detection values are included in a function, the input of the function is multiple values, and the output result is a vector, such as the aforementioned gate circuit, which is still represented as “And” in the GEP expression tree. However, its meaning has become the following vector calculation:(9)AndA1,A2,…An=F1A1,F2A2,…,FnAn.TheAk=k=1,…n is the input value of a detection, and FkAkk=1,…n is the result of this detection Ak to the input value.For example, for this gate circuit, the symbol And means the following:(10)AndLA,LB,VA,VB,CA,CB=LALB,minVA,VB+Vdio,CA+CB.Among them,LA,LB represent the logical value (1 or 0) of voltage input of the A or B point, VA,VB represent the input voltage of the A or B point, and CA,CB represent the input current of the A or B point.Thus, when using GEP evolution, a symbolic value can simultaneously represent multiple unrelated items. This algorithm will be called Mixed Feature GEP (MF-GEP).


## 3.3. Experiment Setup

The experiment is limited to the use of simple logic gate circuits, does not involve triggers, clocks, etc., and does not consider time effects.Four groups of experiments were designed.Outputm=1,The number of features arek=1,2,2,3.Three features are used: feature 1 is the logical value, feature 2 is the voltage value, and feature 3 is the current value.As a comparative experiment, the parameters used are identical as Table1 shows.Table 1
Parameter settings for experiment 1.
ParameterValueStopFitness = 1Selection modeTournament, size = 3Population size10000Head length20Tail length21Chromosome length1Mutation rate0.05Insert rate0.1Root insert rate0.01One-point cross rate0.1Two-point cross rate0.1Input number4Output number1Function setNot, and, or


## 3.4. Design of Fitness Function

The feature data are logic data, voltage data, and current data, which have their own fitness.Logical data fitness is(11)Flogic=1−∑i=1Nyi−yN,which is Expression 3.N is the number of test data, yi is the logic value calculated according to the test data after decoding, and y is the output logic value of the test data. Because it is a logical value, the worst case is that each output decoded by the individual is opposite to the test value, that is, yi−y=1, so Flogic is among the range of 0,1.Voltage data fitness is(12)Fvol=1−∑i=1Nyi−y/NVCC−VDD,which is Expression 4.N is the number of test data, yi is the voltage value calculated according to the test data after decoding, and y is the output voltage value of the test data. At worst, each test output value is either the highest level or the lowest level, and each output decoded by the individual is opposite to the test value yi−y=VCC−VDD; therefore, Fvol is among the range of 0,1.Current data fitness is(13)Fcir=1−SSESST,which is Expression 5.Among them,(14)SSE=∑i=1myi−yˆi2,SST=∑i=1myi−y¯i2,where yi is the data observation, y^i is the estimate value of the yi which is calculated from the decoding expression, and y¯i is the average value of the variable y. That is, the SSE is the Sum of Squared Errors and the SST is the Sum of Squares in Total. Fcir the square of the multicorrelation coefficient in statistics.According to the previous algorithm description, the individual fitness should be a combination of the three; then, the individual fitness is(15)F=C1·Flogic+C2·Fvol+C3·Fcir,∑Ck=1,which is Expression 6: individual fitness expression.C1,C2,C3 are the weight of three features in the final fitness.


## 3.5. Experiment

Figure4 shows a circuit. Its Boolean expression is(16)Y=A+BCD′+BC′D.Figure 4
A circuit with a Trojan.Its calculation is(17)Y=0,ABCD<01012orABCD=01112.1,else.The input valueABCD=01112 can be seen as the Trojan trigger conditions. When there are more pins, only part of the value can be tested, and you may miss the input ABCD=01112. In the following experiment, the input data will not provide the 0111 value to trigger the Trojan, and the output of the input value will be determined by the evolved circuit.Its effective gene is(18)Or,A,Or,And,And,B,And,B,And,Not,D,C,Not,C,D.Using different combination forms, we designed 4 groups of experiments. Considering that the logic value is required to be correct first in the circuit, the voltage value and the current value must be meaningful on the basis of the correct logic value, so the logic value is included in each group of experiments, and the fitness of the individual combines several data; the logical value accounts for a larger proportion. Table2 shows the results of the experiments.Table 2
Comparison of results of 4 groups in experiment 1.
ParameterExp1ValueExp2ValueExp3ValueExp4ValueLogic gateAnd, or, notAnd, or, notAnd, or, notAnd, or, notValues providedLogic valuesLogic valuesLogic valuesLogic valuesVoltage valuesCurrent valuesVoltage valuesCurrent valuesFitness functionF=F1F=0.8·F1+0.2·F2F=0.8·F1+0.2·F3F=0.6·F1+0.2·F2+0.2·F3Exercise count100Trojan discovered count007267The experimental results show the following:(1)
Only using a single feature cannot find Trojan circuit.(2)
Using multiple features can effectively discover Trojan circuits.(3)
The features with direct correlation have no effect on the discovery probability of Trojan horse: in experiment 2, two features of logic value and voltage are used at the same time, and the Trojan horse cannot be found; in experiment 4, although three features are used, the probability of finding Trojan horse is not higher than that of real 3. The reason is that in digital circuits, the logical value itself is expressed by the voltage value; for example, the voltage value less than 3 V is considered 0, and the voltage value greater than 3 V is considered 1. Therefore, there is no difference between the logic value and voltage value.


## 4. Algorithm 2: Multioutput Circuit

### 4.1. GEP Representation

One circuitn input/m output can be described as a forest composed of m trees, each with 1∼n leaf nodes. The 6-input/2-output circuit in Figure 5 can be decomposed into two tree structured multi-input/single-output circuits.Figure 5
A 6-input/2-output circuit.The circuits shown in Figure6 can be divided into two independent multi-input/single-output.Figure 6
Two circuits divided by the circuit shown in Figure5.The corresponding effective genes are(19)And,And,And,A,Not,And,And,B,C,Not,E,F,D.(20)Or,And,And,And,And,And,F,C,Not,E,F,E,F,D.The combination of the two genes represents a 6-input/2-output circuit.


### 4.2. Algorithm of Ordered Mixed Feature GEP

The GEP should be modified as the following to be able to represent this kind of circuit.


#### 4.2.1. Remove the Link Function and Number the Gene

The GEP data structure has its own multigene structure. In formula mining, the basic idea of GEP is to use a polynomial approximation method, so that each independent gene can evolve a part of the final polynomial and then use a connection function (usually “+”) to form a complete polynomial. Of course, if the test data are error-free and the cost is sufficient, GEP final expression does not need to be approximated, and it is the expression from which the test data themself come.The operator such as “+” has a characteristic that there is no sequential difference between the operators. If such an operator is used, it can be considered that there is no sequential difference between the genes in GEP chromosome.We can also see that GEP can solve a problem similar toy=fx1,x2,…,xn function problem; that is, it can deal with the problem of multi-input and single-output. However, circuit combinations are often a multi-input/multi-output problem, that is, a problem as y1,y2,…,ym=fx1,x2,…,xn. This is a situation GEP cannot handle by its own algorithm.For solving the multioutput situation of combinational circuits, the GEP data structure is changed as follows:(1)
The connection function used to connect GEP to multiple genes is removed, so that a gene represents an output, and there is no association between genes; then, a chromosome withk genes represents a circuit with k outputs.(2)
According to the position number of the gene in the chromosome and the position of the gene in the chromosome, the corresponding output pin is represented; that is, the input value in the GEP is the test value of each input pin. The decoding result represents the circuit structure of an output pin. Each gene within a chromosome evolves independently.


#### 4.2.2. Record the Fitness of Each Gene

The fitness is set for each individual in the GEP, which is the basis for the calculation of various evolutionary variations. The fitness represents the approximate degree of the target on the whole of an individual. This fitness is calculated based on the expression tree decoded by an individual.In the work of this paper, because each gene in an individual is independent of each other, the whole individual decodes not an expression tree, but an expression forest, and the trees in this forest are still orderly. The fitness of an individual depends on each gene. To solve this problem, the fitness is set for each gene of the individual in the work of this paper. The fitness represents the similarity of the gene to the circuit structure of the corresponding pin. Combined with the fitness of all genes, an individual’s fitness is formed, indicating the approximation of the individual to the whole circuit structure. Therefore, this paper not only sets the fitness for each individual but also sets the fitness for each gene.


### 4.3. Materials and Methods

The relationship between chromosome fitness and gene fitness can be described as(21)fitnesschromosome=∑Fitnessgenenn,which is Expression 7: individual fitness of multigene GEP.This algorithm is Ordered Mixed Feature GEP (OMF-GEP).


### 4.4. Experiment Setup

The setting of experiment 2 is most consistent with that of experiment 1. The difference is that the number of genes is increased to 2, corresponding to the operation of gene recombination (the probability is 0.01), and the termination condition of the algorithm is changed to 100,000 times.The fitness of each gene is calculated in the same way as experiment 1. Expression 5 is used to calculate the fitness of the whole chromosome, in whichn is 2.


### 4.5. Experiment

Use the circuit of Figure5. In this circuit, Boolean expression is(22)X=AB′CD′EF,Y=EF.Among them,(23)X=1,ABCDEF<1010112,0,else.During the experiment, we deliberately hide the test cases that allowX to take a value of 1. The setup of the 4 groups of experiments is completely consistent with that of experiment 1. Table 3 shows the results.Table 3
Comparison of results of 4 groups in experiment 2.
ParameterExp1ValueExp2ValueExp3ValueExp4ValueLogic gateAnd, or, notAnd, or, notAnd, or, notAnd, or, notValues providedLogic valuesLogic valuesLogic valuesLogic valuesVoltage valuesCurrent valuesVoltage valuesCurrent valuesGene fitness functionF=F1F=0.8·F1+0.2·F2F=0.8·F1+0.2·F3F=0.6·F1+0.2·F2+0.2·F3Chromosome fitnessFchrom=Fgene1+Fgene2/2Evolution number100000Max chrom-fitness0.420.460.440.44Max evolution no. when fitness stopped advance92134112137It can be seen from the experimental results that no matter what combination of features is used, after evolution begins, the fitness cannot continue to grow after reaching a very low value, and evolution has actually stopped. The overall trend is shown in Figure7.Figure 7
The algorithm cannot converge.


## 4.1. GEP Representation

One circuitn input/m output can be described as a forest composed of m trees, each with 1∼n leaf nodes. The 6-input/2-output circuit in Figure 5 can be decomposed into two tree structured multi-input/single-output circuits.Figure 5
A 6-input/2-output circuit.The circuits shown in Figure6 can be divided into two independent multi-input/single-output.Figure 6
Two circuits divided by the circuit shown in Figure5.The corresponding effective genes are(19)And,And,And,A,Not,And,And,B,C,Not,E,F,D.(20)Or,And,And,And,And,And,F,C,Not,E,F,E,F,D.The combination of the two genes represents a 6-input/2-output circuit.


## 4.2. Algorithm of Ordered Mixed Feature GEP

The GEP should be modified as the following to be able to represent this kind of circuit.


### 4.2.1. Remove the Link Function and Number the Gene

The GEP data structure has its own multigene structure. In formula mining, the basic idea of GEP is to use a polynomial approximation method, so that each independent gene can evolve a part of the final polynomial and then use a connection function (usually “+”) to form a complete polynomial. Of course, if the test data are error-free and the cost is sufficient, GEP final expression does not need to be approximated, and it is the expression from which the test data themself come.The operator such as “+” has a characteristic that there is no sequential difference between the operators. If such an operator is used, it can be considered that there is no sequential difference between the genes in GEP chromosome.We can also see that GEP can solve a problem similar toy=fx1,x2,…,xn function problem; that is, it can deal with the problem of multi-input and single-output. However, circuit combinations are often a multi-input/multi-output problem, that is, a problem as y1,y2,…,ym=fx1,x2,…,xn. This is a situation GEP cannot handle by its own algorithm.For solving the multioutput situation of combinational circuits, the GEP data structure is changed as follows:(1)
The connection function used to connect GEP to multiple genes is removed, so that a gene represents an output, and there is no association between genes; then, a chromosome withk genes represents a circuit with k outputs.(2)
According to the position number of the gene in the chromosome and the position of the gene in the chromosome, the corresponding output pin is represented; that is, the input value in the GEP is the test value of each input pin. The decoding result represents the circuit structure of an output pin. Each gene within a chromosome evolves independently.


### 4.2.2. Record the Fitness of Each Gene

The fitness is set for each individual in the GEP, which is the basis for the calculation of various evolutionary variations. The fitness represents the approximate degree of the target on the whole of an individual. This fitness is calculated based on the expression tree decoded by an individual.In the work of this paper, because each gene in an individual is independent of each other, the whole individual decodes not an expression tree, but an expression forest, and the trees in this forest are still orderly. The fitness of an individual depends on each gene. To solve this problem, the fitness is set for each gene of the individual in the work of this paper. The fitness represents the similarity of the gene to the circuit structure of the corresponding pin. Combined with the fitness of all genes, an individual’s fitness is formed, indicating the approximation of the individual to the whole circuit structure. Therefore, this paper not only sets the fitness for each individual but also sets the fitness for each gene.


## 4.2.1. Remove the Link Function and Number the Gene

The GEP data structure has its own multigene structure. In formula mining, the basic idea of GEP is to use a polynomial approximation method, so that each independent gene can evolve a part of the final polynomial and then use a connection function (usually “+”) to form a complete polynomial. Of course, if the test data are error-free and the cost is sufficient, GEP final expression does not need to be approximated, and it is the expression from which the test data themself come.The operator such as “+” has a characteristic that there is no sequential difference between the operators. If such an operator is used, it can be considered that there is no sequential difference between the genes in GEP chromosome.We can also see that GEP can solve a problem similar toy=fx1,x2,…,xn function problem; that is, it can deal with the problem of multi-input and single-output. However, circuit combinations are often a multi-input/multi-output problem, that is, a problem as y1,y2,…,ym=fx1,x2,…,xn. This is a situation GEP cannot handle by its own algorithm.For solving the multioutput situation of combinational circuits, the GEP data structure is changed as follows:(1)
The connection function used to connect GEP to multiple genes is removed, so that a gene represents an output, and there is no association between genes; then, a chromosome withk genes represents a circuit with k outputs.(2)
According to the position number of the gene in the chromosome and the position of the gene in the chromosome, the corresponding output pin is represented; that is, the input value in the GEP is the test value of each input pin. The decoding result represents the circuit structure of an output pin. Each gene within a chromosome evolves independently.


## 4.2.2. Record the Fitness of Each Gene

The fitness is set for each individual in the GEP, which is the basis for the calculation of various evolutionary variations. The fitness represents the approximate degree of the target on the whole of an individual. This fitness is calculated based on the expression tree decoded by an individual.In the work of this paper, because each gene in an individual is independent of each other, the whole individual decodes not an expression tree, but an expression forest, and the trees in this forest are still orderly. The fitness of an individual depends on each gene. To solve this problem, the fitness is set for each gene of the individual in the work of this paper. The fitness represents the similarity of the gene to the circuit structure of the corresponding pin. Combined with the fitness of all genes, an individual’s fitness is formed, indicating the approximation of the individual to the whole circuit structure. Therefore, this paper not only sets the fitness for each individual but also sets the fitness for each gene.


## 4.3. Materials and Methods

The relationship between chromosome fitness and gene fitness can be described as(21)fitnesschromosome=∑Fitnessgenenn,which is Expression 7: individual fitness of multigene GEP.This algorithm is Ordered Mixed Feature GEP (OMF-GEP).


## 4.4. Experiment Setup

The setting of experiment 2 is most consistent with that of experiment 1. The difference is that the number of genes is increased to 2, corresponding to the operation of gene recombination (the probability is 0.01), and the termination condition of the algorithm is changed to 100,000 times.The fitness of each gene is calculated in the same way as experiment 1. Expression 5 is used to calculate the fitness of the whole chromosome, in whichn is 2.


## 4.5. Experiment

Use the circuit of Figure5. In this circuit, Boolean expression is(22)X=AB′CD′EF,Y=EF.Among them,(23)X=1,ABCDEF<1010112,0,else.During the experiment, we deliberately hide the test cases that allowX to take a value of 1. The setup of the 4 groups of experiments is completely consistent with that of experiment 1. Table 3 shows the results.Table 3
Comparison of results of 4 groups in experiment 2.
ParameterExp1ValueExp2ValueExp3ValueExp4ValueLogic gateAnd, or, notAnd, or, notAnd, or, notAnd, or, notValues providedLogic valuesLogic valuesLogic valuesLogic valuesVoltage valuesCurrent valuesVoltage valuesCurrent valuesGene fitness functionF=F1F=0.8·F1+0.2·F2F=0.8·F1+0.2·F3F=0.6·F1+0.2·F2+0.2·F3Chromosome fitnessFchrom=Fgene1+Fgene2/2Evolution number100000Max chrom-fitness0.420.460.440.44Max evolution no. when fitness stopped advance92134112137It can be seen from the experimental results that no matter what combination of features is used, after evolution begins, the fitness cannot continue to grow after reaching a very low value, and evolution has actually stopped. The overall trend is shown in Figure7.Figure 7
The algorithm cannot converge.


## 5. Algorithm 3: Superchromosome

In experiment 2, it is impossible to evolve continuously when the fitness is not high in the early stage of evolution. By analyzing the reasons, the fitness of the individual represents the approximate degree of the individual to the whole circuit, but in the design of the modified algorithm, each gene evolves alone. That is, the approximation of the circuit is divided into different parts. In the process of evolutionary calculation, such individuals will be considered poor individuals, with less chance of heredity in the next evolution, resulting in the loss of local genes already leading in evolution. This situation will lead to the efficiency of the algorithm evolution being very inefficient, or even unable to converge, because the evolution has entered a situation of almost random evolution.


### 5.1. Algorithm Description

To solve this situation, this paper introduces the concept of “superchromosome” in its work. Each individual in the population is obtained by genetic variation after initialization, but the superindividual is artificially constructed. Using the fitness of each gene that has been recorded, a superindividual is constructed after an evolution. The method is that the structure of the superindividual and the ordinary chromosome is the same, but the gene at each position is the best one in the same position in the whole population, as shown below. In this way, the superindividual concentrates the last evolutionary optimal gene at each gene location, and there is no doubt that the superindividual is the optimal individual in the population. Then, replacing the worst individuals in the population with such superchromosome to continue the later evolution can effectively avoid the elimination of local excellent genes. Figure8 shows how to compose the superchromosome.Figure 8
Composition of superchromosome.The introduction of the superchromosome was intended to avoid the elimination of excellent genes in the same individual due to the existence of “low quality” genes, but it brought an additional benefit. Evolutionary individual fitness changes can often reach a high level soon after evolution, as Figure9 shows. The reason is that the superindividual concentrates the optimal genes in each gene position, so that the whole individual can achieve very high fitness.Figure 9
Superchromosome makes the fitness rise rapidly.


### 5.2. Experimental Setup

The setting of experiment 3 is the same as that of experiment 2, but it increases the generation of superindividuals when each generation evolves. The fitness function designed is exactly as the same as experiment 2.


### 5.3. Experiment

The content of the experiment is the same as that of experiment 2. Table4 shows the results.Table 4
Comparison of results of 4 groups in experiment 3.
ParameterExp1ValueExp2ValueExp3ValueExp4ValueLogic gateAnd, or, notAnd, or, notAnd, or, notAnd, or, notValues providedLogic valuesLogic valuesLogic valuesLogic valuesVoltage valuesVoltage valuesCurrent valuesCurrent valuesGene fitness functionF=F1F=0.8·F1+0.2·F2F=0.8·F1+0.2·F3F=0.6·F1+0.2·F2+0.2·F3Chromosome fitnessFchrom=Fgene1+Fgene2/2Evolution number100000Max chrom-fitness0.720.760.940.87Max evolution no. when fitness stopped advance3242768091365The experimental results show the following:(1)
After using superindividuals, the evolution can reach a very high level in a very short time, and then the speed of evolution will be significantly reduced.(2)
Using only a single feature or feature with direct correlation, the algorithm is difficult to obtain satisfactory fitness, and the reason has been analyzed in the results of experimental 1.(3)
The use of multiple features that lack direct correlation between each other helps to achieve higher fitness.


## 5.1. Algorithm Description

To solve this situation, this paper introduces the concept of “superchromosome” in its work. Each individual in the population is obtained by genetic variation after initialization, but the superindividual is artificially constructed. Using the fitness of each gene that has been recorded, a superindividual is constructed after an evolution. The method is that the structure of the superindividual and the ordinary chromosome is the same, but the gene at each position is the best one in the same position in the whole population, as shown below. In this way, the superindividual concentrates the last evolutionary optimal gene at each gene location, and there is no doubt that the superindividual is the optimal individual in the population. Then, replacing the worst individuals in the population with such superchromosome to continue the later evolution can effectively avoid the elimination of local excellent genes. Figure8 shows how to compose the superchromosome.Figure 8
Composition of superchromosome.The introduction of the superchromosome was intended to avoid the elimination of excellent genes in the same individual due to the existence of “low quality” genes, but it brought an additional benefit. Evolutionary individual fitness changes can often reach a high level soon after evolution, as Figure9 shows. The reason is that the superindividual concentrates the optimal genes in each gene position, so that the whole individual can achieve very high fitness.Figure 9
Superchromosome makes the fitness rise rapidly.


## 5.2. Experimental Setup

The setting of experiment 3 is the same as that of experiment 2, but it increases the generation of superindividuals when each generation evolves. The fitness function designed is exactly as the same as experiment 2.


## 5.3. Experiment

The content of the experiment is the same as that of experiment 2. Table4 shows the results.Table 4
Comparison of results of 4 groups in experiment 3.
ParameterExp1ValueExp2ValueExp3ValueExp4ValueLogic gateAnd, or, notAnd, or, notAnd, or, notAnd, or, notValues providedLogic valuesLogic valuesLogic valuesLogic valuesVoltage valuesVoltage valuesCurrent valuesCurrent valuesGene fitness functionF=F1F=0.8·F1+0.2·F2F=0.8·F1+0.2·F3F=0.6·F1+0.2·F2+0.2·F3Chromosome fitnessFchrom=Fgene1+Fgene2/2Evolution number100000Max chrom-fitness0.720.760.940.87Max evolution no. when fitness stopped advance3242768091365The experimental results show the following:(1)
After using superindividuals, the evolution can reach a very high level in a very short time, and then the speed of evolution will be significantly reduced.(2)
Using only a single feature or feature with direct correlation, the algorithm is difficult to obtain satisfactory fitness, and the reason has been analyzed in the results of experimental 1.(3)
The use of multiple features that lack direct correlation between each other helps to achieve higher fitness.


## 6. Conclusion

GEP algorithm based on the mixed features is proposed in this paper, when multiple features with no direct correlation between each other are used, even if some important parameters are missing in the test case, and the abnormal structure in the circuit can be found. For multioutput circuits, if it only simply decomposed into multiple single-output circuits to evolve separately, the algorithm will fall into a complete random search and cannot converge. In this paper, the concept of superindividual is proposed to solve this problem, so that the algorithm can converge smoothly in the circuit structure facing multi-input.



---

*Source: 6682674-2021-03-18.xml*