CN107748912B - A Delay Optimization Method for Ternary FPRM Circuit Using Bat Algorithm - Google Patents

Abstract

The invention discloses a three-value FPRM circuit delay optimization method utilizing a bat algorithm, which optimizes the result of large-scale three-value FPRM circuit delay polarity search by utilizing the population search capability of the bat algorithm, and the bat continuously updates the speed and displacement of the bat in the population evolution iteration process and simultaneously accompanies the update change of the bat sound wave loudness and the bat pulse rate; the method has the advantage of higher search efficiency on the basis of ensuring the optimization precision.

Description

A Delay Optimization Method for Ternary FPRM Circuit Using Bat Algorithm

technical field

The invention relates to a delay optimization method of a ternary FPRM circuit, in particular to a delay optimization method of a ternary FPRM circuit using a bat algorithm.

Background technique

The n input variables of the ternary FPRM circuit correspond to 3 ⁿ logic function expressions of different polarities, and the complexity and simplicity of the logic function expressions corresponding to different polarities are not the same. The performance becomes the key to the delay optimization of the ternary FPRM circuit. Usually, small and medium-scale ternary FPRM circuits use an exhaustive algorithm to traverse all polarities to determine the optimal polarity of the circuit. However, for large-scale ternary FPRM circuits, the polarity search space increases as the input variable n increases. Exponentially increased, within a certain time range, exhaustive search has been unable to traverse all polarities to obtain the best delay.

Bat-inspired Algorithm (BA) is a swarm intelligent search algorithm proposed by British scholar YANG and others based on the echolocation ability of bats. The loudness and frequency of the impulse to locate the target. The bat algorithm simulates each solution in the search space as a bat, and sets a fitness value for all bats, so that each bat adjusts the loudness and frequency according to the current optimal bat in the iterative process, and its search efficiency is relatively high. high.

In view of this, it is of great significance to design a three-valued FPRM circuit delay optimization method using the bat algorithm with high search efficiency on the basis of ensuring the optimization accuracy.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide a ternary FPRM circuit delay optimization method using the bat algorithm with high search efficiency on the basis of ensuring the optimization accuracy.

The technical solution adopted by the present invention to solve the above-mentioned technical problems is: a ternary FPRM circuit delay optimization method utilizing the bat algorithm, comprising the following steps:

(1) The three-valued FPRM circuit with polarity q and n input variables is expressed as:

为模3乘项，a_i为模3乘项的系数，i＝0，1，2，…，3^n-1-1，

其中

Among them, x ₀ , x ₁ ,...,x _n-1 are the n input variables of the function expansion, q represents the polarity of the three-valued FPRM circuit; ⊕Σ is the modulo-3 addition symbol, "·" is the multiplication calculating signs;

is the modulo 3 multiplication term, a _i is the coefficient of the modulo 3 multiplication term, i=0, 1, 2, ..., 3 ^n-1 -1,

in

(2) Use the Huffman algorithm to decompose the coefficients of the modulo 3 multipliers that are not 0 in the function expansion of the three-valued FPRM circuit under q-polarity, and use the coefficient obtained by the final decomposition as the delay estimation data of the three-valued FPRM circuit under q-polarity ;

(3) The bat algorithm is used to optimize the delay time of the ternary FPRM circuit under the q polarity. The specific steps are as follows:

A. Establish the mapping relationship between the bat algorithm and the ternary FPRM circuit delay optimization under q polarity:

The bat algorithm includes the following key elements: bat displacement, bat speed, bat sound frequency, bat sound loudness, bat search space, bat fitness, bat displacement with the greatest fitness, and maximum fitness value;

The delay optimization of ternary FPRM circuit includes the following key elements: polarity, polarity conversion, polarity exchange, polarity mutation, polarity search space, delay of corresponding polarity, optimal polarity of delay and maximum delay good delay;

Denote bat displacement as polarity; bat velocity as polarity transformation; bat sonic frequency as polarity exchange; bat sonic loudness as polarity mutation; bat search space as polar search space; The fitness of is expressed as the delay of the corresponding polarity; the bat displacement with the largest fitness is expressed as the polarity with the optimal delay; the maximum fitness value is expressed as the best delay;

B. Set the relevant parameters of the bat algorithm:

Denote the number of bat populations as m, m is an integer greater than or equal to 40, the bat search space dimension is denoted as b, b is an integer greater than or equal to 30, and the maximum evolutionary generation of bat population evolution is denoted as N, where N is greater than or equal to 3000 Integer, set the current evolutionary generation of the bat population as the variable h;

C. Set the fitness function used to calculate the fitness of bats in the bat algorithm:

Set the fitness function for calculating the fitness of the bat in the bat algorithm: in the bat algorithm, the larger the fitness, the better the position of the bat relative to the target, but the search for the optimal delay of the ternary FPRM circuit requires that the smaller the delay, the better the position of the bat relative to the target. Well, therefore, in order to facilitate the effective combination of the two, the inverse of the delay is used to represent the fitness, and the fitness function is obtained as follows:

表示适应度放大系数，取值为大于等于500的整数；Among them, the symbol "/" represents the division operator; fitness _c represents the fitness of the c-th bat, c is an integer greater than or equal to 1 and less than or equal to m; fit _c is the lower three polar values corresponding to the displacement of the c-th bat Delay estimation data of FPRM circuit;

Indicates the fitness amplification factor, which is an integer greater than or equal to 500;

D. Denote the displacement of the c-th bat in the bat population as x _c,d , and the velocity of the c-th bat as v _c,d , where d represents the search space dimension of the c-th bat, d∈[1,b], The sound wave loudness of the c-th bat is recorded as A _c , the pulse rate of the _c -th bat is recorded as rc , and the sound wave frequency of the c-th bat is recorded as f _c . The velocity and the frequency of the bat sound wave are initialized, where the bat displacement is initialized to any value within the range of polarity values, A _C is initialized to a random number between 1 and 2, and _rc is initialized to a random number greater than 0 and less than or equal to 1, The bat sound wave frequency f _c is initialized as a random number between f _min and f _max , where f _min represents the minimum value of the bat sound wave frequency, and the value is 100, and f _max represents the maximum bat sound wave frequency, and the value is 1200. Initialize the variable h to 1;

E. Calculate the delay estimation data of the ternary FPRM circuit under the polarity corresponding to the displacement of each bat in the bat group according to steps (1) and (2), and then calculate the fitness of each bat according to the delay estimation data, and set the The bat displacement with the largest fitness value is used as the current global optimal displacement of the bat population. If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected as the current global optimal displacement of the bat population. ;

F. The first update of the h-th evolutionary generation for the bat displacement and bat velocity of the bat colony: First, use a random function to generate uniformly distributed random variables α, α∈[0,1], and then update the h-th generation through formula (1). The bat sound frequency f _c of the round evolutionary generation, and then the bat displacement x _c,d and the bat velocity v _c,d are updated by combining equations (2) and (3):

f _c =f _min +(f _max -f _min )*α (1)

表示在第h轮进化代第c个蝙蝠速度的首次更新值，

表示在第h轮进化代第c个蝙蝠位移的首次更新值；in,

represents the first update value of the cth bat velocity in the hth evolutionary generation,

represents the first update value of the displacement of the cth bat in the hth evolutionary generation;

为第c个蝙蝠速度的初始值，

为第c个蝙蝠位移的初始值，P^h-1为蝙蝠种群的当前全局最优位移的初始值；If the current value of h is 1, then

is the initial value of the cth bat speed,

is the initial value of the cth bat displacement, and P ^h-1 is the initial value of the current global optimal displacement of the bat population;

为在第h-1轮进化代第c个蝙蝠速度的更新值，

为在第h-1轮进化代第c个蝙蝠位移的更新值，P^h-1为在第h-1轮进化代蝙蝠种群的当前全局最优位置的更新值；If the current value of h is greater than 1, then

is the updated value of the cth bat speed in the h-1th evolutionary generation,

is the updated value of the displacement of the cth bat in the h-1th evolutionary generation, and P ^h-1 is the updated value of the current global optimal position of the bat population in the h-1th evolutionary generation;

G. Update the bat colony again, the specific process is:

G-1. Use random function to generate random number rand1, rand1∈[0,5000];

进入步骤G-3；G-2. Compare _rand1 with the pulse rate rc of the cth bat. If rand1 is smaller than _rc , the bat displacement of the bat does not need to be updated again, and the first update value of the cth bat speed is taken as its hth round The updated value of the evolutionary generation, and return to step G-1 to start updating the next bat displacement. If rand1 is greater than or equal to _rc , add the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population. After 1 as the local optimal bat displacement, denoted as

Go to step G-3;

对应的适应度值；G-3. Calculate bat displacement

the corresponding fitness value;

G-4. Use random functions to generate random numbers rand2, rand2∈[0, 3000];

对应的适应度值大于或等于第c个蝙蝠当前的适应度值，则采用蝙蝠位移

再次更新蝙蝠位移x_c,d，将第c个蝙蝠速度的再次更新值作为其第h轮进化代的更新值，否则，蝙蝠位移x_c,d不进行更新，将其首次更新值作为其第h轮进化代的更新值；G-5. If rand2 is less than or equal to A _c and the bat is displaced

If the corresponding fitness value is greater than or equal to the current fitness value of the cth bat, the bat displacement is used

The bat displacement x _c,d is updated again, and the re-updated value of the c-th bat velocity is taken as the updated value of its h-th evolutionary generation. Otherwise, the bat displacement x _{c, d} is not updated, and its first updated value is taken as its first updated value. The updated value of the h-round evolutionary generation;

G-6. Follow steps G-1 to G-5 to update the bat colony again, then recalculate the fitness values of all bats in the updated bat colony, and use the bat displacement with the largest fitness value to update the bat colony If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected to update the current global optimal displacement of the bat population;

H. The h-th round update of the bat sonic loudness and bat pulse rate of the bat colony is performed by Equation (4) and Equation (5):

表示第c个蝙蝠声波响度在第h轮的更新值，

第c个蝙蝠脉冲速率在第h轮的更新值；Among them, δ is an arbitrary constant greater than 0 and less than or equal to 1, γ is a constant greater than 0, exp represents the exponential function with the natural constant e as the base,

represents the updated value of the cth bat sound wave loudness in the hth round,

The updated value of the cth bat pulse rate in the hth round;

表示第c个蝙蝠声波响度的初始值，

表示第c个蝙蝠脉冲速率的初始值；If the current value of h is equal to 1,

represents the initial value of the loudness of the cth bat sound,

represents the initial value of the cth bat pulse rate;

表示第h-1轮第c个蝙蝠声波响度的更新值，

表示第h-1轮第c个蝙蝠脉冲速率的更新值；If the current value of h is greater than 1,

represents the updated value of the loudness of the cth bat sound in the h-1th round,

Represents the updated value of the cth bat pulse rate in the h-1th round;

I. Judge whether the current value of h is equal to the maximum evolutionary algebra, if not, then use the current value of h plus 1 to update the value of h, and return to step F for the next round of update; if the current value of h is equal to The maximum evolutionary algebra, the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population is used as the polarity of the optimal delay, and the fitness value corresponding to the optimal polarity of the delay is regarded as the optimal delay .

In the described step (2), the specific process of obtaining the delay estimation data of the ternary FPRM circuit under the q polarity is:

a. According to the function expansion of the three-valued FPRM circuit under the q-polarity, determine the number of modulo-3 multipliers that are not 0 in the three-valued FPRM circuit under the q-polarity, and denote the number of modulo-3 multipliers that are not 0 as M;

b. Compare the coefficients of the M modulo-3 multiplication terms to obtain the delay estimation data of the three-valued FPRM circuit under the q polarity. The specific process is:

When M is equal to 1, the coefficient of the 1 modulo 3 multiplication term is used as the delay estimation data of the three-valued FPRM circuit under the q polarity;

When M is equal to 2, if the two coefficients are equal, select any one of the coefficients as the delay estimation data of the three-valued FPRM circuit under the q polarity. If the two coefficients are not equal, delete the smaller coefficient and keep it. The larger coefficient of the two is used to update the value of the coefficient with the value obtained by adding 1 to the value of the larger coefficient of the two, and the updated value is used as the delay estimation data of the three-value FPRM circuit under the q polarity;

When M is greater than 2, the specific comparison process is:

①Randomly select the coefficients of any two modulo 3 multipliers;

②Compare the two coefficients: if the two are equal, go back to step ① to start a new round of selection; if the two are not equal, delete the smaller coefficient of the two, keep the larger coefficient of the two, and Update the value of the coefficient with the value obtained by adding 1 to the value of the larger coefficient of the two;

③ Then randomly select a coefficient from the coefficients of the remaining modulo 3 multiplication terms, and compare the coefficient with the updated value of the larger coefficient retained in the previous step according to the method of step ②;

④ Repeat step ③ until all coefficient comparisons are completed;

⑤ Use the updated value of the last remaining larger coefficient as the delay estimation data of the three-valued FPRM circuit under the q polarity;

Compared with the prior art, the advantage of the present invention is that by using the population search capability of the bat algorithm to optimize the results of the large-scale ternary FPRM circuit delay polarity search, the bat continuously updates its own speed and displacement in the iterative process of population evolution, and at the same time. Along with the update and change of the bat sound wave loudness and the bat pulse rate, the method of the present invention has high search efficiency on the basis of ensuring the optimization accuracy.

Detailed ways

The present invention will be described in further detail below in conjunction with the embodiments.

Embodiment 1: a three-valued FPRM circuit delay optimization method utilizing the bat algorithm, comprising the following steps:

(1) The three-valued FPRM circuit with polarity q and n input variables is expressed as:

为模3乘项，a_i为模3乘项的系数，i＝0，1，2，…，3^n-1-1，

其中

Among them, x ₀ , x ₁ ,...,x _n-1 are the n input variables of the function expansion, q represents the polarity of the three-valued FPRM circuit; ⊕Σ is the modulo-3 addition symbol, "·" is the multiplication calculating signs;

is the modulo 3 multiplication term, a _i is the coefficient of the modulo 3 multiplication term, i=0, 1, 2, ..., 3 ^n-1 -1,

in

(2) Use the Huffman algorithm to decompose the coefficients of the modulo 3 multipliers that are not 0 in the function expansion of the three-valued FPRM circuit under q-polarity, and use the coefficient obtained by the final decomposition as the delay estimation data of the three-valued FPRM circuit under q-polarity ;

(3) The bat algorithm is used to optimize the delay time of the ternary FPRM circuit under the q polarity. The specific steps are as follows:

A. Establish the mapping relationship between the bat algorithm and the ternary FPRM circuit delay optimization under q polarity:

The bat algorithm includes the following key elements: bat displacement, bat speed, bat sound frequency, bat sound loudness, bat search space, bat fitness, bat displacement with the greatest fitness, and maximum fitness value;

The delay optimization of ternary FPRM circuit includes the following key elements: polarity, polarity conversion, polarity exchange, polarity mutation, polarity search space, delay of corresponding polarity, optimal polarity of delay and maximum delay good delay;

Denote bat displacement as polarity; bat velocity as polarity transformation; bat sonic frequency as polarity exchange; bat sonic loudness as polarity mutation; bat search space as polar search space; The fitness of is expressed as the delay of the corresponding polarity; the bat displacement with the largest fitness is expressed as the polarity with the optimal delay; the maximum fitness value is expressed as the best delay;

B. Set the relevant parameters of the bat algorithm:

Denote the number of bat populations as m, m is an integer greater than or equal to 40, the bat search space dimension is denoted as b, b is an integer greater than or equal to 30, and the maximum evolutionary generation of bat population evolution is denoted as N, where N is greater than or equal to 3000 Integer, set the current evolutionary generation of the bat population as the variable h;

C. Set the fitness function used to calculate the fitness of bats in the bat algorithm:

Set the fitness function for calculating the fitness of the bat in the bat algorithm: in the bat algorithm, the larger the fitness, the better the position of the bat relative to the target, but the search for the optimal delay of the ternary FPRM circuit requires that the smaller the delay, the better the position of the bat relative to the target. Well, therefore, in order to facilitate the effective combination of the two, the inverse of the delay is used to represent the fitness, and the fitness function is obtained as follows:

表示适应度放大系数，取值为大于等于500的整数；Among them, the symbol "/" represents the division operator; fitness _c represents the fitness of the c-th bat, c is an integer greater than or equal to 1 and less than or equal to m; fit _c is the lower three polar values corresponding to the displacement of the c-th bat Delay estimation data of FPRM circuit;

Indicates the fitness amplification factor, which is an integer greater than or equal to 500;

D. Denote the displacement of the c-th bat in the bat population as x _c,d , and the velocity of the c-th bat as v _c,d , where d represents the search space dimension of the c-th bat, d∈[1,b], The sound wave loudness of the c-th bat is recorded as A _c , the pulse rate of the _c -th bat is recorded as rc , and the sound wave frequency of the c-th bat is recorded as f _c . The velocity and the frequency of the bat sound wave are initialized, where the bat displacement is initialized to any value within the range of polarity values, A _C is initialized to a random number between 1 and 2, and _rc is initialized to a random number greater than 0 and less than or equal to 1, The bat sound wave frequency f _c is initialized as a random number between f _min and f _max , where f _min represents the minimum value of the bat sound wave frequency, and the value is 100, and f _max represents the maximum bat sound wave frequency, and the value is 1200. Initialize the variable h to 1;

E. Calculate the delay estimation data of the ternary FPRM circuit under the polarity corresponding to the displacement of each bat in the bat group according to steps (1) and (2), and then calculate the fitness of each bat according to the delay estimation data, and set the The bat displacement with the largest fitness value is used as the current global optimal displacement of the bat population. If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected as the current global optimal displacement of the bat population. ;

F. The first update of the h-th evolutionary generation for the bat displacement and bat velocity of the bat colony: First, use a random function to generate uniformly distributed random variables α, α∈[0,1], and then update the h-th generation through formula (1). The bat sound frequency f _c of the round evolutionary generation, and then the bat displacement x _c,d and the bat velocity v _c,d are updated by combining equations (2) and (3):

f _c =f _min +(f _max -f _min )*α (1)

表示在第h轮进化代第c个蝙蝠速度的首次更新值，

表示在第h轮进化代第c个蝙蝠位移的首次更新值；in,

represents the first update value of the cth bat velocity in the hth evolutionary generation,

represents the first update value of the displacement of the cth bat in the hth evolutionary generation;

为第c个蝙蝠速度的初始值，

为第c个蝙蝠位移的初始值，P^h-1为蝙蝠种群的当前全局最优位移的初始值；If the current value of h is 1, then

is the initial value of the cth bat speed,

is the initial value of the cth bat displacement, and P ^h-1 is the initial value of the current global optimal displacement of the bat population;

为在第h-1轮进化代第c个蝙蝠速度的更新值，

为在第h-1轮进化代第c个蝙蝠位移的更新值，P^h-1为在第h-1轮进化代蝙蝠种群的当前全局最优位置的更新值；If the current value of h is greater than 1, then

is the updated value of the cth bat speed in the h-1th evolutionary generation,

is the updated value of the displacement of the cth bat in the h-1th evolutionary generation, and P ^h-1 is the updated value of the current global optimal position of the bat population in the h-1th evolutionary generation;

G. Update the bat colony again, the specific process is:

G-1. Use random function to generate random number rand1, rand1∈[0,5000];

进入步骤G-3；G-2. Compare _rand1 with the pulse rate rc of the cth bat. If rand1 is smaller than _rc , the bat displacement of the bat does not need to be updated again, and the first update value of the cth bat speed is taken as its hth round The updated value of the evolutionary generation, and return to step G-1 to start updating the next bat displacement. If rand1 is greater than or equal to _rc , add the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population. After 1 as the local optimal bat displacement, denoted as

Go to step G-3;

对应的适应度值；G-3. Calculate bat displacement

the corresponding fitness value;

G-4. Use random functions to generate random numbers rand2, rand2∈[0, 3000];

对应的适应度值大于或等于第c个蝙蝠当前的适应度值，则采用蝙蝠位移

再次更新蝙蝠位移x_c,d，将第c个蝙蝠速度的再次更新值作为其第h轮进化代的更新值，否则，蝙蝠位移x_c,d不进行更新，将其首次更新值作为其第h轮进化代的更新值；G-5. If rand2 is less than or equal to A _c and the bat is displaced

If the corresponding fitness value is greater than or equal to the current fitness value of the cth bat, the bat displacement is used

The bat displacement x _c,d is updated again, and the re-updated value of the c-th bat velocity is taken as the updated value of its h-th evolutionary generation. Otherwise, the bat displacement x _{c, d} is not updated, and its first updated value is taken as its first updated value. The updated value of the h-round evolutionary generation;

G-6. Follow steps G-1 to G-5 to update the bat colony again, then recalculate the fitness values of all bats in the updated bat colony, and use the bat displacement with the largest fitness value to update the bat colony If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected to update the current global optimal displacement of the bat population;

H. The h-th round update of the bat sonic loudness and bat pulse rate of the bat colony is performed by Equation (4) and Equation (5):

表示第c个蝙蝠声波响度在第h轮的更新值，

第c个蝙蝠脉冲速率在第h轮的更新值；Among them, δ is an arbitrary constant greater than 0 and less than or equal to 1, γ is a constant greater than 0, exp represents the exponential function with the natural constant e as the base,

represents the updated value of the cth bat sound wave loudness in the hth round,

The updated value of the cth bat pulse rate in the hth round;

表示第c个蝙蝠声波响度的初始值，

表示第c个蝙蝠脉冲速率的初始值；If the current value of h is equal to 1,

represents the initial value of the loudness of the cth bat sound,

represents the initial value of the cth bat pulse rate;

表示第h-1轮第c个蝙蝠声波响度的更新值，

表示第h-1轮第c个蝙蝠脉冲速率的更新值；If the current value of h is greater than 1,

represents the updated value of the loudness of the cth bat sound in the h-1th round,

Represents the updated value of the cth bat pulse rate in the h-1th round;

I. Judge whether the current value of h is equal to the maximum evolutionary algebra, if not, then use the current value of h plus 1 to update the value of h, and return to step F for the next round of update; if the current value of h is equal to The maximum evolutionary algebra, the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population is used as the polarity of the optimal delay, and the fitness value corresponding to the optimal polarity of the delay is regarded as the optimal delay .

Embodiment 2: a three-valued FPRM circuit delay optimization method utilizing the bat algorithm, comprising the following steps:

(1) The three-valued FPRM circuit with polarity q and n input variables is expressed as:

为模3乘项，a_i为模3乘项的系数，i＝0，1，2，…，3^n-1-1，

其中

Among them, x ₀ , x ₁ ,...,x _n-1 are the n input variables of the function expansion, q represents the polarity of the three-valued FPRM circuit; ⊕Σ is the modulo-3 addition symbol, "·" is the multiplication calculating signs;

is the modulo 3 multiplication term, a _i is the coefficient of the modulo 3 multiplication term, i=0, 1, 2, ..., 3 ^n-1 -1,

in

(2) Use the Huffman algorithm to decompose the coefficients of the modulo 3 multipliers that are not 0 in the function expansion of the three-valued FPRM circuit under q-polarity, and use the coefficient obtained by the final decomposition as the delay estimation data of the three-valued FPRM circuit under q-polarity ;

(3) The bat algorithm is used to optimize the delay time of the ternary FPRM circuit under the q polarity. The specific steps are as follows:

A. Establish the mapping relationship between the bat algorithm and the ternary FPRM circuit delay optimization under q polarity:

The bat algorithm includes the following key elements: bat displacement, bat speed, bat sound frequency, bat sound loudness, bat search space, bat fitness, bat displacement with the greatest fitness, and maximum fitness value;

The delay optimization of ternary FPRM circuit includes the following key elements: polarity, polarity conversion, polarity exchange, polarity mutation, polarity search space, delay of corresponding polarity, optimal polarity of delay and maximum delay good delay;

Denote bat displacement as polarity; bat velocity as polarity transformation; bat sonic frequency as polarity exchange; bat sonic loudness as polarity mutation; bat search space as polar search space; The fitness of is expressed as the delay of the corresponding polarity; the bat displacement with the largest fitness is expressed as the polarity with the optimal delay; the maximum fitness value is expressed as the best delay;

B. Set the relevant parameters of the bat algorithm:

Denote the number of bat populations as m, m is an integer greater than or equal to 40, the bat search space dimension is denoted as b, b is an integer greater than or equal to 30, and the maximum evolutionary generation of bat population evolution is denoted as N, where N is greater than or equal to 3000 Integer, set the current evolutionary generation of the bat population as the variable h;

C. Set the fitness function used to calculate the fitness of bats in the bat algorithm:

Set the fitness function for calculating the fitness of the bat in the bat algorithm: in the bat algorithm, the larger the fitness, the better the position of the bat relative to the target, but the search for the optimal delay of the ternary FPRM circuit requires that the smaller the delay, the better the position of the bat relative to the target. Well, therefore, in order to facilitate the effective combination of the two, the inverse of the delay is used to represent the fitness, and the fitness function is obtained as follows:

表示适应度放大系数，取值为大于等于500的整数；Among them, the symbol "/" represents the division operator; fitness _c represents the fitness of the c-th bat, c is an integer greater than or equal to 1 and less than or equal to m; fit _c is the lower three polar values corresponding to the displacement of the c-th bat Delay estimation data of FPRM circuit;

Indicates the fitness amplification factor, which is an integer greater than or equal to 500;

D. Denote the displacement of the c-th bat in the bat population as x _c,d , and the velocity of the c-th bat as v _c,d , where d represents the search space dimension of the c-th bat, d∈[1,b], The sound wave loudness of the c-th bat is recorded as A _c , the pulse rate of the _c -th bat is recorded as rc , and the sound wave frequency of the c-th bat is recorded as f _c . The velocity and the frequency of the bat sound wave are initialized, where the bat displacement is initialized to any value within the range of polarity values, A _C is initialized to a random number between 1 and 2, and _rc is initialized to a random number greater than 0 and less than or equal to 1, The bat sound wave frequency f _c is initialized as a random number between f _min and f _max , where f _min represents the minimum value of the bat sound wave frequency, and the value is 100, and f _max represents the maximum bat sound wave frequency, and the value is 1200. Initialize the variable h to 1;

E. Calculate the delay estimation data of the ternary FPRM circuit under the polarity corresponding to the displacement of each bat in the bat group according to steps (1) and (2), and then calculate the fitness of each bat according to the delay estimation data, and set the The bat displacement with the largest fitness value is used as the current global optimal displacement of the bat population. If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected as the current global optimal displacement of the bat population. ;

F. The first update of the h-th evolutionary generation for the bat displacement and bat velocity of the bat colony: First, use a random function to generate uniformly distributed random variables α, α∈[0,1], and then update the h-th generation through formula (1). The bat sound frequency f _c of the round evolutionary generation, and then the bat displacement x _c,d and the bat velocity v _c,d are updated by combining equations (2) and (3):

f _c =f _min +(f _max -f _min )*α (1)

表示在第h轮进化代第c个蝙蝠速度的首次更新值，

表示在第h轮进化代第c个蝙蝠位移的首次更新值；in,

represents the first update value of the cth bat velocity in the hth evolutionary generation,

represents the first update value of the displacement of the cth bat in the hth evolutionary generation;

为第c个蝙蝠速度的初始值，

为第c个蝙蝠位移的初始值，P^h-1为蝙蝠种群的当前全局最优位移的初始值；If the current value of h is 1, then

is the initial value of the cth bat speed,

is the initial value of the cth bat displacement, and P ^h-1 is the initial value of the current global optimal displacement of the bat population;

为在第h-1轮进化代第c个蝙蝠速度的更新值，

为在第h-1轮进化代第c个蝙蝠位移的更新值，P^h-1为在第h-1轮进化代蝙蝠种群的当前全局最优位置的更新值；If the current value of h is greater than 1, then

is the updated value of the cth bat speed in the h-1th evolutionary generation,

is the updated value of the displacement of the cth bat in the h-1th evolutionary generation, and P ^h-1 is the updated value of the current global optimal position of the bat population in the h-1th evolutionary generation;

G. Update the bat colony again, the specific process is:

G-1. Use random function to generate random number rand1, rand1∈[0,5000];

进入步骤G-3；G-2. Compare _rand1 with the pulse rate rc of the cth bat. If rand1 is smaller than _rc , the bat displacement of the bat does not need to be updated again, and the first update value of the cth bat speed is taken as its hth round The updated value of the evolutionary generation, and return to step G-1 to start updating the next bat displacement. If rand1 is greater than or equal to _rc , add the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population. After 1 as the local optimal bat displacement, denoted as

Go to step G-3;

对应的适应度值；G-3. Calculate bat displacement

the corresponding fitness value;

G-4. Use random functions to generate random numbers rand2, rand2∈[0, 3000];

对应的适应度值大于或等于第c个蝙蝠当前的适应度值，则采用蝙蝠位移

再次更新蝙蝠位移x_c,d，将第c个蝙蝠速度的再次更新值作为其第h轮进化代的更新值，否则，蝙蝠位移x_c,d不进行更新，将其首次更新值作为其第h轮进化代的更新值；G-5. If rand2 is less than or equal to A _c and the bat is displaced

If the corresponding fitness value is greater than or equal to the current fitness value of the cth bat, the bat displacement is used

The bat displacement x _c,d is updated again, and the re-updated value of the c-th bat velocity is taken as the updated value of its h-th evolutionary generation. Otherwise, the bat displacement x _{c, d} is not updated, and its first updated value is taken as its first updated value. The updated value of the h-round evolutionary generation;

G-6. Follow steps G-1 to G-5 to update the bat colony again, then recalculate the fitness values of all bats in the updated bat colony, and use the bat displacement with the largest fitness value to update the bat colony If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected to update the current global optimal displacement of the bat population;

H. The h-th round update of the bat sonic loudness and bat pulse rate of the bat colony is performed by Equation (4) and Equation (5):

表示第c个蝙蝠声波响度在第h轮的更新值，

第c个蝙蝠脉冲速率在第h轮的更新值；Among them, δ is an arbitrary constant greater than 0 and less than or equal to 1, γ is a constant greater than 0, exp represents the exponential function with the natural constant e as the base,

represents the updated value of the cth bat sound wave loudness in the hth round,

The updated value of the cth bat pulse rate in the hth round;

表示第c个蝙蝠声波响度的初始值，

表示第c个蝙蝠脉冲速率的初始值；If the current value of h is equal to 1,

represents the initial value of the loudness of the cth bat sound,

represents the initial value of the cth bat pulse rate;

表示第h-1轮第c个蝙蝠声波响度的更新值，

表示第h-1轮第c个蝙蝠脉冲速率的更新值；If the current value of h is greater than 1,

represents the updated value of the loudness of the cth bat sound in the h-1th round,

Represents the updated value of the cth bat pulse rate in the h-1th round;

I. Judge whether the current value of h is equal to the maximum evolutionary algebra, if not, then use the current value of h plus 1 to update the value of h, and return to step F for the next round of update; if the current value of h is equal to The maximum evolutionary algebra, the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population is used as the polarity of the optimal delay, and the fitness value corresponding to the optimal polarity of the delay is regarded as the optimal delay .

In the present embodiment, the specific process of obtaining the delay estimation data of the ternary FPRM circuit under the q polarity in step (2) is:

a. According to the function expansion of the three-valued FPRM circuit under the q-polarity, determine the number of modulo-3 multipliers that are not 0 in the three-valued FPRM circuit under the q-polarity, and denote the number of modulo-3 multipliers that are not 0 as M;

b. Compare the coefficients of the M modulo-3 multiplication terms to obtain the delay estimation data of the three-valued FPRM circuit under the q polarity. The specific process is:

When M is equal to 1, the coefficient of the 1 modulo 3 multiplication term is used as the delay estimation data of the three-valued FPRM circuit under the q polarity;

When M is equal to 2, if the two coefficients are equal, select any one of the coefficients as the delay estimation data of the three-valued FPRM circuit under the q polarity. If the two coefficients are not equal, delete the smaller coefficient and keep it. The larger coefficient of the two is used to update the value of the coefficient with the value obtained by adding 1 to the value of the larger coefficient of the two, and the updated value is used as the delay estimation data of the three-value FPRM circuit under the q polarity;

When M is greater than 2, the specific comparison process is:

①Randomly select the coefficients of any two modulo 3 multipliers;

②Compare the two coefficients: if the two are equal, go back to step ① to start a new round of selection; if the two are not equal, delete the smaller coefficient of the two, keep the larger coefficient of the two, and Update the value of the coefficient with the value obtained by adding 1 to the value of the larger coefficient of the two;

③ Then randomly select a coefficient from the coefficients of the remaining modulo 3 multiplication terms, and compare the coefficient with the updated value of the larger coefficient retained in the previous step according to the method of step ②;

④ Repeat step ③ until all coefficient comparisons are completed;

⑤ Use the updated value of the last remaining larger coefficient as the delay estimation data of the three-valued FPRM circuit under the q polarity;

When M is greater than 2, if the two coefficients are equal in all comparison processes, any one coefficient is selected as the delay estimation data of the three-valued FPRM circuit under the q polarity.

In the experiment, 9 MCNC Benchmark circuits are randomly selected, and the circuits are tested by the method of the present invention and the exhaustive method respectively. The test environment is: Windows 10 (64-bit), 3.20GHz Intel Pentium CPU, 4.00GB memory, Dev-C++ software. In the method of the present invention, the relevant parameters are: the number of bat populations is 100, the dimension of the search space is 30, and the maximum evolutionary generation of the population is 3000. The experimental data are shown in Table 1, among which, column 1 and column 2 are the name of the test circuit and the number of input variables respectively; column 3 and column 4 are the circuit area and delay data obtained by exhaustive search respectively; column 5, column 6 are the circuit area and delay data obtained by the method of the present invention, respectively. According to the test data in Table 1, it can be known that the circuit area searched by the method of the present invention increases by 26.7% on average, and the delay time decreases by 11.3% on average.

Table 1

The experimental results comparing the method of the present invention (IWBA) with the PSO algorithm and the traditional bat algorithm (BA algorithm) on the delay and area optimization of the ternary FPRM circuit are shown in Table 2. Among them, column 1 and column 2 are respectively the test circuit. Names and the number of input variables; Columns 3 and 4 are the circuit area and delay data optimized based on the PSO algorithm, respectively; Columns 5 and 6 are the circuit area and delay data optimized based on the BA algorithm; Columns 7, Column 8 is the circuit area and delay data obtained by the optimization of the method of the present invention, respectively.

Table 2

Comparing the area and delay optimization results of the three methods in Table 2, it can be seen that the optimization effect of the present invention is obviously better than that of the PSO algorithm and the BA algorithm. Compared with the PSO algorithm, the method of the present invention saves 73.5% of the average area and 16.5% of the delay; compared to the BA algorithm, the method of the present invention saves 66.0% of the average area and 14.3% of the delay.

Claims (2)

1. a three-valued FPRM circuit delay optimization method utilizing bat algorithm is characterized in that comprising the following steps: (1) The three-valued FPRM circuit with polarity q and n input variables is expressed as:

Among them, x ₀ , x ₁ ,...,x _n-1 are the n input variables of the function expansion, and q represents the polarity of the three-valued FPRM circuit;

It is a modulo 3 addition symbol, and "·" is a multiplication symbol;

is the modulo 3 multiplication term, a _i is the coefficient of the modulo 3 multiplication term, i=0, 1, 2, ..., 3 ^n-1 -1,

i _j ∈{0,1,2}, where

j=0,1,...,n-1; (2) Use the Huffman algorithm to decompose the coefficients of the modulo 3 multipliers that are not 0 in the function expansion of the three-valued FPRM circuit under q-polarity, and use the coefficient obtained by the final decomposition as the delay estimation data of the three-valued FPRM circuit under q-polarity ; (3) The bat algorithm is used to optimize the delay time of the ternary FPRM circuit under the q polarity. The specific steps are as follows: A. Establish the mapping relationship between the bat algorithm and the ternary FPRM circuit delay optimization under q polarity: The bat algorithm includes the following key elements: bat displacement, bat speed, bat sound frequency, bat sound loudness, bat search space, bat fitness, bat displacement with the greatest fitness, and maximum fitness value; The delay optimization of ternary FPRM circuit includes the following key elements: polarity, polarity conversion, polarity exchange, polarity mutation, polarity search space, delay of corresponding polarity, optimal polarity of delay and maximum delay good delay; Denote bat displacement as polarity; bat velocity as polarity transformation; bat sonic frequency as polarity exchange; bat sonic loudness as polarity mutation; bat search space as polar search space; The fitness of is expressed as the delay of the corresponding polarity; the bat displacement with the largest fitness is expressed as the polarity with the optimal delay; the maximum fitness value is expressed as the best delay; B. Set the relevant parameters of the bat algorithm: Denote the number of bat populations as m, m is an integer greater than or equal to 40, the bat search space dimension is denoted as b, b is an integer greater than or equal to 30, and the maximum evolutionary generation of bat population evolution is denoted as N, where N is greater than or equal to 3000 Integer, set the current evolutionary generation of the bat population as the variable h; C. Set the fitness function used to calculate the fitness of bats in the bat algorithm: Set the fitness function for calculating the fitness of the bat in the bat algorithm: in the bat algorithm, the larger the fitness, the better the position of the bat relative to the target, but the search for the optimal delay of the ternary FPRM circuit requires that the smaller the delay, the better the position of the bat relative to the target. Well, therefore, in order to facilitate the effective combination of the two, the inverse of the delay is used to represent the fitness, and the fitness function is obtained as follows:

Among them, the symbol "/" represents the division operator; fitness _c represents the fitness of the c-th bat, c is an integer greater than or equal to 1 and less than or equal to m; fit _c is the lower three polar values corresponding to the displacement of the c-th bat Delay estimation data of FPRM circuit;

Indicates the fitness amplification factor, which is an integer greater than or equal to 500; D. Denote the displacement of the c-th bat in the bat population as x _c,d , and the velocity of the c-th bat as v _c,d , where d represents the search space dimension of the c-th bat, d∈[1,b], The sound wave loudness of the c-th bat is recorded as A _c , the pulse rate of the _c -th bat is recorded as rc , and the sound wave frequency of the c-th bat is recorded as f _c . The velocity and the frequency of the bat sound wave are initialized, where the bat displacement is initialized to any value within the range of polarity values, A _C is initialized to a random number between 1 and 2, and _rc is initialized to a random number greater than 0 and less than or equal to 1, The bat sound wave frequency f _c is initialized as a random number between f _min and f _max , where f _min represents the minimum value of the bat sound wave frequency, and the value is 100, and f _max represents the maximum bat sound wave frequency, and the value is 1200. Initialize the variable h to 1; E. Calculate the delay estimation data of the ternary FPRM circuit under the polarity corresponding to the displacement of each bat in the bat group according to steps (1) and (2), and then calculate the fitness of each bat according to the delay estimation data, and set the The bat displacement with the largest fitness value is used as the current global optimal displacement of the bat population. If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected as the current global optimal displacement of the bat population. ; F. The first update of the h-th evolutionary generation for the bat displacement and bat velocity of the bat colony: First, use a random function to generate uniformly distributed random variables α, α∈[0,1], and then update the h-th generation through formula (1). The bat sound frequency f _c of the round evolutionary generation, and then the bat displacement x _c,d and the bat velocity v _c,d are updated by combining equations (2) and (3): f _c =f _min +(f _max -f _min )*α (1)

in,

represents the first update value of the cth bat velocity in the hth evolutionary generation,

represents the first update value of the displacement of the cth bat in the hth evolutionary generation; If the current value of h is 1, then

is the initial value of the cth bat speed,

is the initial value of the cth bat displacement, and P ^h-1 is the initial value of the current global optimal displacement of the bat population; If the current value of h is greater than 1, then

is the updated value of the cth bat speed in the h-1th evolutionary generation,

is the updated value of the displacement of the cth bat in the h-1th evolutionary generation, and P ^h-1 is the updated value of the current global optimal position of the bat population in the h-1th evolutionary generation; G. Update the bat colony again, the specific process is: G-1. Use random function to generate random number rand1, rand1∈[0,5000]; G-2. Compare _rand1 with the pulse rate rc of the cth bat. If rand1 is smaller than _rc , the bat displacement of the bat does not need to be updated again, and the first update value of the cth bat speed is taken as its hth round The updated value of the evolutionary generation, and return to step G-1 to start updating the next bat displacement. If rand1 is greater than or equal to _rc , add the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population. After 1 as the local optimal bat displacement, denoted as

Go to step G-3; G-3. Calculate bat displacement

the corresponding fitness value; G-4. Use random functions to generate random numbers rand2, rand2∈[0, 3000]; G-5. If rand2 is less than or equal to A _c and the bat is displaced

If the corresponding fitness value is greater than or equal to the current fitness value of the cth bat, the bat displacement is used

The bat displacement x _c,d is updated again, and the re-updated value of the c-th bat velocity is taken as the updated value of its h-th evolutionary generation. Otherwise, the bat displacement x _{c, d} is not updated, and its first updated value is taken as its first updated value. The updated value of the h-round evolutionary generation; G-6. Follow steps G-1 to G-5 to update the bat colony again, then recalculate the fitness values of all bats in the updated bat colony, and use the bat displacement with the largest fitness value to update the bat colony If there are multiple bat displacements with the largest fitness value, one of the bat displacements with the largest fitness value is randomly selected to update the current global optimal displacement of the bat population; H. The h-th round update of the bat sonic loudness and bat pulse rate of the bat colony is performed by Equation (4) and Equation (5):

Among them, δ is an arbitrary constant greater than 0 and less than or equal to 1, γ is a constant greater than 0, exp represents the exponential function with the natural constant e as the base,

represents the updated value of the cth bat sound wave loudness in the hth round,

The updated value of the cth bat pulse rate in the hth round; If the current value of h is equal to 1,

represents the initial value of the loudness of the cth bat sound,

represents the initial value of the cth bat pulse rate; If the current value of h is greater than 1,

represents the updated value of the loudness of the cth bat sound in the h-1th round,

Represents the updated value of the cth bat pulse rate in the h-1th round; I. Judge whether the current value of h is equal to the maximum evolutionary algebra, if not, then use the current value of h plus 1 to update the value of h, and return to step F for the next round of update; if the current value of h is equal to The maximum evolutionary algebra, the bat displacement with the largest fitness value corresponding to the current global optimal displacement of the bat population is used as the polarity of the optimal delay, and the fitness value corresponding to the optimal polarity of the delay is regarded as the optimal delay . 2. a kind of ternary FPRM circuit delay optimization method utilizing bat algorithm according to claim 1, it is characterized in that in described step (2), obtain the time delay estimation data of tertiary FPRM circuit under q polarity The specific process is: a. According to the function expansion of the three-valued FPRM circuit under the q-polarity, determine the number of modulo-3 multipliers that are not 0 in the three-valued FPRM circuit under the q-polarity, and denote the number of modulo-3 multipliers that are not 0 as M; b. Compare the coefficients of the M modulo-3 multiplication terms to obtain the delay estimation data of the three-valued FPRM circuit under the q polarity. The specific process is: When M is equal to 1, the coefficient of the 1 modulo 3 multiplication term is used as the delay estimation data of the three-valued FPRM circuit under the q polarity; When M is equal to 2, if the two coefficients are equal, select any one of the coefficients as the delay estimation data of the three-valued FPRM circuit under the q polarity. If the two coefficients are not equal, delete the smaller coefficient and keep it. The larger coefficient of the two is used to update the value of the coefficient with the value obtained by adding 1 to the value of the larger coefficient of the two, and the updated value is used as the delay estimation data of the three-value FPRM circuit under the q polarity; When M is greater than 2, the specific comparison process is: ①Randomly select the coefficients of any two modulo 3 multipliers; ②Compare the two coefficients: if the two are equal, go back to step ① to start a new round of selection; if the two are not equal, delete the smaller coefficient of the two, keep the larger coefficient of the two, and Update the value of the coefficient with the value obtained by adding 1 to the value of the larger coefficient of the two; ③ Then randomly select a coefficient from the coefficients of the remaining modulo 3 multiplication terms, and compare the coefficient with the updated value of the larger coefficient retained in the previous step according to the method of step ②; ④ Repeat step ③ until all coefficient comparisons are completed; ⑤ Take the updated value of the larger coefficient retained at the end as the delay estimation data of the three-valued FPRM circuit under the q polarity.