Swarm intelligence versus direct cover algorithms in synthesis of Multi-Valued Logic functions

Abstract

Ant Colony Optimization and Particle Swarm Optimization represent two widely used Swarm Intelligence (SI) optimization techniques. Information processing using Multiple-Valued Logic (MVL) is carried out using more than two discrete logic levels. In this paper, we compare two the SI-based algorithms in synthesizing MVL functions. A benchmark consisting of 50,000 randomly generated 2-variable 4-valued functions is used for assessing the performance of the algorithms using the benchmark. Simulation results show that the PSO outperforms the ACO technique in terms of the average number of product terms (PTs) needed. We also compare the results obtained using both ACO-MVL and PSO-MVL with those obtained using Espresso-MV logic minimizer. It is shown that on average, both of the SI-based techniques produced better results compared to those produced by Espresso-MV. We show that the SI-based techniques outperform the conventional direct-cover (DC) techniques in terms of the average number of product terms required.

Citation

Abd-El-Barr, M., Qureshi, K. and Sarif, B. (2024), "Swarm intelligence versus direct cover algorithms in synthesis of Multi-Valued Logic functions", Applied Computing and Informatics, Vol. 20 No. 1/2, pp. 2-19. https://doi.org/10.1016/j.aci.2020.03.002

1. Introduction

It is widely recognized by researchers as well as the chip industry that on-chip complex binary systems exhibit a number of curbs, such as large layout area for interconnections, limitations of data storage, increased power consumption, and limitation of available bandwidth. These limitations can be mostly overcome by using Multiple-Valued Logic (MVL) systems [1–3]. Digital information processing using MVL is carried out using more than two discrete logic levels. MVL-based information processing include arithmetic operations/processors, memory, and special purpose processors [1]. Reported MVL (sub)-systems have shown considerable reduction both in time and speed compared to their binary counterparts [2–5]. It should however be noted that the search space for MVL synthesis problem is huge when compared to the binary one. There are r(rn)=442=232 2-variable 4-valued functions as compared to 16 2-variable binary functions. This makes exact minimization of MVL functions prohibitively expensive both in time and complexity. Therefore, modern heuristic optimization techniques were employed. These algorithms can be classified into iterative based [6], decomposition-based [7], algebraic based [8], direct cover-based [9–11], and evolutionary-based algorithms. The latter include Genetic algorithms (GAs) [12–13], Ant Colony (ACO) [14–15], and PSO-based [16]. Fuzzy-based synthesis of MVL functions has also been reported in the literature [21].

The Direct Cover (DC) algorithm is an iterative heuristic in the synthesis of MVL functions [9–11]. Swarm intelligence models (SIMs) are computational models inspired by real life swarm systems. The two main SIMs are the Ant Colony Optimization (ACO) [25] and the Particle Swarm Optimization (PSO) [26]. The main idea in the ACO is to model a given problem as a search conducted by ants for the optimal path guided by a substance deposited on the path called pheromone. Real ants were found to be skillful in finding the shortest path between their nests and a food source in the presence of hurdles. Particle swarm optimization (PSO) is inspired by the observation that birds fly in large groups and for long distances without collision. It is hypothesized that birds are able to achieve that through experience-sharing by maintaining an optimum distance between themselves and their neighbors. Hence, PSO is a search strategy that uses a set of flying particles with velocities that are dynamically adjusted based on past experience of individual particle and that of their neighbors in the search space. The PSO algorithm was first introduced in 1995 [21] and was later on extended as in [22,23]. There has been growing interest in the use of PSO for optimization problems [25,28,29,35–40,44–46] and in synthesis of circuits [26,27]. A number of recent research work, books, and book chapters on the issue of swarm and nature-inspired algorithms have been published in the literature [47–49]. However, very few articles were reported on the synthesis of MVL functions, see for example [16].

The paper provides a concise coverage and comparison of both the conventional synthesis techniques of MVL functions represented by the Direct Cover algorithm and those based on the emerging functional synthesis techniques using the swarm intelligent-based algorithms. We aim to provide a useful data analytics for researchers in the area of digital synthesis for high-radix (beyond binary) logic functions. The paper also illustrates the adaptation of the discrete PSO algorithms in the area of MVL functional synthesis while showing the adopted processes used in the selection of the appropriate minterms and the appropriate implicants (product terms) to cover them. We also provide a comparison among the ACO and the PSO on one hand and the Espresso-MV standard algorithm on the other hand.

It should be noted that the two swarm intelligence based algorithms ACO and the PSO are selected in this work because of them being among the well-known swarm intelligence techniques and also in order to align our work with similar research work identified in the literature, e.g. [50].

The paper is organized as follows. Section 2 provides some background material. In Section 3 we provide a coverage of the related work published in the literature. Section 4 covers simulation results conducted using the ACO and the PSO algorithms using a benchmark consisting of 50,000 4-valued 2-varaible functions. In Section 5 we provide comparison among the results obtained out of the simulation conducted in Section 4. In Section 6 we provide a number of concluding remarks.

2. Background material

This section provides enough of the foundation material needed to make the paper self-stand and to help the reader to follow through the paper easily and with the minimum interruption.

Table 1 shows the MVL logic operators used in this paper [15].

Definition 1

[15]: Define an n-variable r-valued function, f(X), as a mapping f:Rn→R.

In the above definition R={0,1,⋯,r−1} is a set of = r logic values with r≥2 and X={x1,x2,⋯,xn} is a set of r-valued n variables. An example 4-valued (r4), 2-variable (n = 2) function is shown in Figure 1.

Definition 2

[15]: Define a product term (PT), P(x1,x2,⋯,xn), as the minimum of a set of window literals such that P(x1,x2,…,xn)=C·a1x1b1·a2x2b2·anxnbn=min(C,a1x1b1,a2x2b2,…,anxnbn) where ai,bi∈R,ai≤bi and c∈{1,2,…,r−1} is the value of the product term.

Example: the product terms in Figure 1 include 1, 1·2x13·1x22,2·0x10·0x23, and 3·1x12·1x22. In the first case c=1, a1=2, b1=3, a2=1, b2=2, in the second case c=2, a1=0,b1=0, a2=0, b2=3 and in the third case c=3, a1=1, b1=2, a2=1, b2=2.

Definition 3

[15]: Define a minterm as the assignment x1=a1, x2=a2,⋯,xn=an, in an MVL function f(x1, x2,⋯,xn) if and only if:f(x1, x2,⋯,xn)≠0.

In the above definition ai∈{0,1,…,r−1}. If the value of a minterm is r, then it is considered as don’t care and is represented as d. There are 12 minterms in the function shown in Figure 1.

Definition 4

[15]: A PT, I(x1,x2,⋯,xn) of a function f(x1,x2,⋯,xn) is called an implican if f(x1,x2,⋯,xn)≥I(x1,x2,⋯,xn) for all assignments of xi’s.

Example: Figure 1 shows an example 4-valued 2-varaibale function.

The objective of MVL synthesis to find the minimum form of an MVL function that can be completely or incompletely specified. As indicated above exact minimization of MVL functions is prohibitively expensive both in time and complexity and that a number of modern heuristic optimization techniques were employed. These include the direct cover-based (DC) [9–11], the Ant Colony (ACO) [14,15], and PSO-based [16]. In Section 5 we provide a comparison of the performance of the ACO and the PSO in the context of synthesis of MVL functions. However the following table (adapted from [50]) illustrates the fundamental difference between the two models of computation.

Criteria	ACO	PSO
Communication Mechanism	Indirect communication through the environment (Stigmergy).	Direct communication.
Problem Type	Both discrete (combinatorial) and continuous optimization problems.	Both Continuous and discrete (combinatorial) optimization problems.
Problem Representation	Using weighted (construction) graph.	Set of n-dimensional points.
Algorithm Applicability	Problems with predefined source and destination	Problems where previous and next particle positions at each point are uniquely defined.

Having covered the needed background material, we provide a coverage of the DC, ACO, and the PSO algorithms in Section 3.

3. Related work

3.1 The Direct cover heuristic algorithm for synthesis of MVL functions

The Direct Cover (DC) algorithm is an iterative heuristic in the synthesis of MVL functions [9–11]. Figure 2 shows an adapted version of the DC.

A detailed analysis of the DC-based algorithms has been conducted jointly by the author in [17]. The results of such analysis have indicated that improvements to the conventional DC are still possible [20] and [24]. In the next section, we present the SI-based improvements of the DC in the form of the Ant Colony (ACO) and the Particle Swarm Optimization (POS).

3.2 The ACO algorithm for synthesis of MVL functions

The main idea in the ACO is to model a given problem as a search conducted by ants for the optimal path guided by a substance deposited on the path called pheromone. Real ants were found to be skillful in finding the shortest path between their nests and a food source in the presence of hurdles. The search is made possible by an indirect communication amongst the ants. While traveling their way, ants deposit a chemical substance, called pheromone, on the ground. When they arrive at a decision point, they make a probabilistic choice, biased by the intensity of pheromone they smell, see Figure 3(a). This behavior has an autocatalytic effect since choosing a given path increases the likelihood that the same path will be chosen again by future ants. On their way back, ants are expected to choose the same path with high probability (due to the increase in the amount of pheromone), see Figure 3(b). As further pheromone is released, the chosen path will become more attractive for future ants. See Figure 3(c) [34].

The basic algorithmic steps in an ACO are shown in Figure 4.

A key point in the development of ACO is the selection of an appropriate fitness function. The fitness function is often formulated as cost minimization of the solution of the given problem. The ACO algorithm has received much attention and has been incorporated in a number of optimization problems [16–21,30–33,43].

3.3 The PSO algorithm for synthesis of MVL functions

Particle swarm optimization (PSO) is inspired by the observation that birds fly in large groups and for long distances without collision. It is hypothesized that birds are able to achieve that through experience-sharing by maintaining an optimum distance between themselves and their neighbors. Hence, PSO is a search strategy that uses a set of flying particles with velocities that are dynamically adjusted based on past experience of individual particle and that of their neighbors in the search space. The PSO algorithm was first introduced in 1995 [21] and was later on extended as in [22,23]. There has been growing interest in the use of PSO for optimization problems [25,28,29,35–40] and in synthesis of circuits [26,27]. However, very few articles were reported on the synthesis of MVL functions, see for example [16]. The basic algorithmic steps in a PSO are shown in Figure 5.

4. Simulation of the algorithms

In this section we present a coverage of the simulation process conducted using the ACO and the PSO algorithms introduced in Section 3 above. The simulation conducted among the algorithms is made using a set of a benchmark consisting of 50,000 randomly generated 2-variable 4-valued functions. The main characteristics of the generated benchmark are illustrated below. As can be seen the number of minterms in the benchmark ranges from 6 to 16. The number of functions in each range is illustrated in the table below. For example there are 500 functions each has 16 minterms, 9000 function seach has 11 minterms, and 75 functions each has 6 minterms.

# functions	500	2700	6600	1050	1130	9000	5450	2500	1100	275	75
# minterms	16	15	14	13	12	11	10	9	8	7	6

4.1 Ant Colony synthesis technique (ACO-MVL)

In the ACO-MVL, use is made of the ants searching strategy in finding the best minterms cover using the right set of implicants. The minterms coverage process is performed iteratively, until all minterms in the table is covered. Upon selecting a minterm (or an implicant) an ant puts some pheromone trails on it. This will cause the next ant performs selection based on the additional pheromone information. This positive feedback process drives the selection to the best solution (see Figure 6) [15].

The daemon_action( ) function is used to initialize the pheromone value at the beginning of all ant’s movement and also whenever stagnancy in the solution is found. Based on the output of the fitness calculations the selected minterms and implicants are updated. The next generation of ants will then use the newly updated pheromone values to guide their selection.

4.1.1 Solution representation

According to the ACO-MVL, a tabular form is used to represent a given MVL function. A bag whose size is equal to the size of the function’s truth table is used to store all selected implicants. Each implicant is represented by a string of integers consisting five integer attributes as follows (in sequence): the constant value of the implicant, the first and second value of the literal (a and b in Table 1) of the first variable in the implicant representation, and followed by the first and second value of the literal (a and b in Table 1) of the second variable in the implicant representation. For example, if the implicant is 1.x112.x213, then the five integer attributes would be 1 1 2 1 3.

It should be noted that performance of the ACO algorithm is dependent on the selection of a number of parameters including the expectation heuristic factor, the pheromone evaporation rate, and the number of ants. The ACO parameter selection techniques differ from a study to the other depending on the types of optimization and the scales of the problem considered. In our case we have conducted experimentations on the parameter value selection using the (expectation) heuristic value η_M and the pheromone evaporation τ_M and we have developed a measure of the probability of choosing a minterm M as explained below in Eq. (1). We have also adopted a similar approach in the selection of the parameters for the implicant (product term) and have developed to measure the probability for choosing an implicant, L as explained below in Eq. (2). Our approach in developing the measures below is inspired by the approach used in [51].

4.1.2 Minterm selection

A stochastic process of Roulette Wheel is used in the selection of a minterm. Two factors affect the probability of choosing a minterm. These are the pheromone value and a heuristic value. The first factor is obtained from pheromone trails of previous ants. The second factor is the fuzzy weighted averaging of minterm’s selection criteria. The probability of choosing minterm M is computed as:

(1)p=τM·ηM∑τM·ηM

where τ_M represents the pheromone value of the minterm M and η_M represents the heuristic value of minterm M.

4.1.3 Implicant selection

A stochastic process of Roulette Wheel is used in the selection of an implicant. Two factors affect the probability of choosing an implicant. These are the pheromone value and a heuristic value. The first factor is obtained from pheromone trails of previous ants. The second factor is the fuzzy weighted averaging of implicants’s selection criteria. The probability of choosing implicant L is computed as:

(2)p=τL·ηL∑τL·ηL

where τL represents the pheromone value of implicant L and ηL represents the heuristic value of literal L (fuzzy weighted averaging of literal’s L selection criteria).

4.1.4 Fitness function

The Functional fitness, Ff=Nh−Nm, where N_h = the number of minterm matching between the two truth tables and Nm= the number of mismatch between the two truth tables. The Objective Fitness, Fo=(100−Np)/100, where Np is the number of product terms needed to cover the function. A chromosome with the highest functional fitness is considered as the best solution. In case of a tie, the chromosome with the highest objective functional is selected.

4.1.5 Numerical results

The ACO-MVL algorithm was applied to a benchmark consisting of 50,000 randomly generated 2-variable 4-valued functions. The following parameters were used:

Number of populations (NP) = 20

Maximum number of Iterations (MI) = 100

Maximum number of Runs = (MR) 10

Pheromone evaporation rate (RHO) = 0.95

The following two measures were recorded:

• 1.

  SRµ ≡ Successful Rate (number of successful iterations divided by the total number of runs)

• 2.

  PT ≡ Number of Product Terms.

Table 2 shows the average number of Product Terms (#PT) needed with respect to the number of minterms of the MVL function used in the benchmark (functions with minterms ranging from 6 to 16 are used) as well as for the conventional DC-based algorithms (ARM [11], BS [9], and DM [10]).

The results in the table show the ACO-MVL algorithm outperforms the DC-based algorithms for all cases. The table also shows that the maximum percentage improvement and the minimum percentage improvement achieved by the ACO-MVL are 12.8% and 0.3%, respectively. It should be noted that the achieved improvements should be considered in the context that the simulated benchmark is representing a population of 4¹⁶ functions. Figure 7 illustrates this comparison. An overall comparison between the SI-based techniques and the espresso-MV logic minimizer tools is provided in Section 3.

4.2 The particle swarm synthesis technique (PSO-MVL)

We motivate the discussion in this section by considering the function given in Figure 8.

Notice that based on the representation introduced in [13], the MVL function shown in Figure 8 is represented as: ‘0000000023102200. The coverage relation between the minterms of the function and the implicants is depicted in Figure 9.

4.2.1 Particle representation

A string consisting of five numbers is used to represent an implicant [13]: the first number represents the value of the implicant, the next two numbers represent the range of the literal of the first variable (a and b in Table 1) while the last two numbers represent the range of the literal of the second variable (a and b in Table 1). Consider, for example, the 4-valued function given in Figure 9. The two implicants (fully or partially) that cover the minterm 31,122 are 11,222 and 20,123 (see Figure 10).

It should be that the performance of the PSO algorithm is dependent on a number of parameters including the swarm size, the particles velocities, the cognitive coefficient, and the particle positions. In our case, we have used the same list of parameters except that for the particle velocities. In our extermination and due to the discrete nature of the MVL synthesis problem we have adopted the discrete PSO approach introduced in [22,23]. Accordingly, we introduce the term particle displacement (rather than particle velocity) and used it instead. Please refer to the set of Eq. (4) in the paper. We have presented the obtained results due to the effect of the swarm size and the number of iterations in Table 4 in the paper. In our test we used: c1 = 1, c2 = c3 = 0.5 and the number of runs = 10. Notice that c1 and c2 represent the cognitive coefficients. As a result of our experimentations, we found out that most appropriate value for V_max is either 4 or 5. A value of V_max = 5 has been used in testing the PSO-MVL Algorithm. Our developed model to compute the particle displacement is shown below in Eq. (4).

4.2.2 Particle fitness function

The Functional fitness is computed as Ff=Nh−Nm, where Nh is the number of minterm match and Nm is the number of minterms mismatch between the truth table of the original and the obtained functions. The objective fitness is computed as Fo = (100 − Np)/100, where Np is the number of product terms needed to cover the function. The selection of the best obtained solution is done on two levels: First the highest functional fitness function and in case of a tie the value of objective fitness will used.

Example:. Figure 10 shows an example of three particles in the swarm whose elements at time t.

Table 3 illustrates the computation of the particle fitness function as explained above.

The results displayed in Table 3 indicate that particles 2 and 3 supersede particle 1 in representing the example function. Although the functional fitness of the two particles show a tie (a score of 16 in each) however the overall fitness shows superiority of particle 3 due to the weight added by the objective function. Therefore, particle 3 is considered the best possible solution for the given MVL function.

4.2.3 Particle movement

The discrete nature of the MVL synthesis problem necessitates adopting the discrete PSO approach introduced in [22,23]. Accordingly, we introduce the term particle displacement (rather than particle velocity) and introduce the following to compute the particle displacement (D_t+1,i):

(4)DSt,i=c2r2(Pi,t−Xt,i)DGt,i=c3r3(Pg,t−Xt,i)Dt+1,i=c1Dt,i+DSt,i+DGt,i

In the above computation we use DS_t,i to represent the displacement of particle i at time step t due to particle best self- experience and DG_t,i to represent the displacement of particle i at time step t due to the global experience. We use X_t,i to represent the position of particle i at time step t, P_i,t to represent the current best position at time step t, and P_g,t to represent the current global best position at time step t, while c_1, c_2, c₃ represent the social/cognitive confidence coefficients, and r_2, r₃ are two random numbers.

As can be seen, the particle displacement (D_t+1,i) consists of three components: (D_t,i), (DS_t,i), and (DG_t,i). The new particle position is formulated as follows:

(5)Xt+1,i=(Xt,i+DSt,i)+DGt,i+c1Dt,i.

The PSO algorithm is illustrated in Figure 11 [16].

4.2.4 Numerical results

We have tested the proposed PSO-MVL algorithm using a bench mark consisting of 50,000 randomly generated 2-variable 4-valued functions. The results obtained are reported in Table 4.

We report in this table the average number of product terms (PTs) needed to cover a given function. We report the obtained results for different number of particles and different number of iterations. In our test we used: c1 = 1, c2 = c3 = 0.5 and the number of runs = 10. As a result of our experimentations, we found out that most appropriate value for V_max is either 4 or 5. A value of V_max = 5 has been used in testing the PSO-MVL Algorithm. It should be noted that a gradual decrease in the number of product terms (PTs) needed to synthesize a given function occurs as we increase the number of particles and/or iterations used.

4.2.4.1 An observation that lead to a modification in the PSO-MVL

Two example 4-valued 2-variable functions are shown in Figure 12. Notice that F2 is the complement of F1. While F1requires at least six implicants to represent, F2 requires only four implicants (circled in the figure). If we synthesize F2 and use an extra inverter we will need a total of 5 gates. This is still less than synthesizing F1. We have made use of such cases by modifying PSO-MVL algorithm in a way to synthesize both the given MVL function and its complement and collect the synthesis which requires less number of implicants taking into consideration the extra inverter gate needed if the complement of the function is synthesized.

Table 5 shows the results obtained using the modified PSO-MVL in comparison with the DC-based conventional heuristics for different functions having different number of minters.

In this table we present the average number of minterms required to synthesize a bench mark consisting of 50,000 2-variable 4-valued functions having minterms ranging from 6 to 16. For a comparison purpose, we also report the results obtained for three other synthesis algorithms: the ARM [11], the BS [9], and the DM [10]. The maximum and minimum percentage improvement for each of the 11 categories of functions is also computed and reported in the table. The maximum improvement achieved by the modified PSO-MVL is 31.2% (in the case of functions having 11 minterms) and the minimum improvement achieved is 7.9% (in the case of functions having 6 minterms). The results shown in Table 5 is illustrated in Figure 13.

5. A comparison

In this section we provide two main comparisons. The first is among the two Swarm Intelligence based algorithms used for synthesis of MVL functions, i.e. the ACO-MVL and the PSO-MVL. The second comparison is among the PSO-MVL and ACO-MVL on one side with the results obtained using espresso-MVL logic minimizer. Our basis for comparison is the benchmark consisting of 50,000 2-variable 4-vauled randomly generated function. Table 6 shows a summary of the results obtained for the results obtained for PSO-MVL and those obtained for ACO-MVL for synthesizing the 50,000 benchmark functions.

The results shown in Table 6 indicate that on average the number of product terms (#PTs) needed to synthesize a given function using the PSO-MVL is lower than the number of those needed to synthesize the same function using ACO-MVL. The maximum percentage improvement in the number of product terms obtained using PSO-MVL over the ACO-MVL is 16.3% (in the case of functions with 16 minterms) while the minimum percentage improvement is 3.9% (in the case of functions having 7 minterms). Over all simulated 50,000 functions, the average percentage improvement is 5.4%. It should be noted that 5.4% represents a considerable improvement given that the simulated randomly generated functions are representative of a population consisting of 416 functions. We also observe that as the number of minterms in a given function increases, the percentage improvement decreases. This can be attributed to the observation that as the number of minterms increases, the likelihood of an ant finding a solution increases and hence the improvement in the number of PTs achieved by the ACO-MVL algorithm. Figure 14 illustrates this comparison.

The results show that on average both ACO-MVL and PSO produce better number of product terms for the benchmark functions. The average percentage improvement is 6% in the case of ACO-MVL and it is 11.9% in the case of the PSO-MVL. Figure 15 illustrates this comparison.

6. Concluding remarks

This paper provides a review and comparison on the performance evaluation of the Ant Colony (ACO) and the Particle Swarm Optimization (PSO) heuristic techniques in the synthesis of MVL functions. This evaluation is provided on two levels: Swarm-Intelligence (SI)-based versus conventional Direct-Cover (DC)-based algorithms and between the two SI-based algorithms. The covered algorithms were simulated and tested using a benchmark consisting of 50,000 randomly generated 2-variable 4-valued functions. The average #PTs needed is used as a criterion in comparing the performance of all considered algorithms. The results obtained indicate that the SI-based techniques outperform the conventional DC in terms of the average #PTs required to realize a given MVL function. Between the two SI-based algorithms, the technique based on the PSO produces better overall results. The performance evaluation show also that the results obtained using both the SI-based algorithms outperform the results obtained using the espresso-MVL logic minimizer. It is shown that both the ACO and the PSO outperform the Espresso-MVL algorithm in the minimization of MVL functions. The work presented in this publication considers using ACO and PSO in the synthesis of 4-valued logic functions and compares the results to those obtained conventional using the direct-cover techniques. Application of other swarm intelligence techniques, e.g. Genetic Algorithms or Artificial Bee Colony for 4-valued or higher-radix logic is not covered in the article.

Figures

Figure 1

An example 2-variable 4-valued function.

Figure 2

Algorithm for synthesis of MVL functions using DC heuristics.

Figure 3

Illustration of the ants’ behavior [34].

Figure 4

ACO basic algorithmic steps.

Figure 5

PSO basic algorithmic steps.

Figure 6

ACO-MVL algorithm.

Figure 7

Average #PTs using ACO-MVL versus those achieved using DC-based technique.

Figure 8

Example MVL function.

Figure 9

Coverage relation between minterms and implicants for function shown in Figure 8.

Figure 10

Example of particle representation.

Figure 11

The PSO algorithm for MVL synthesis.

Figure 12

Example function and its complement function.

Figure 13

Average #PTs achieved using PSO versus those achieved using existing synthesis techniques.

Figure 14

Average PT achieved using ACO-MVL and PSOThe second comparison we have conducted was to compare the results obtained using both of the Swarm-Intelligence-based techniques against those obtained using Espresso-MV logic minimizer [40].

Figure 15

Average #PT achieved using ACO-MVL and PSO-MVL versus those achieved using Espresso-MV.

Table 1

MVL operators.

The operator	The logic equation
The window literal	axb={(r−1)if(a≤x≤b)0otherwise
	where a,b∈R and a≤b. It should be noted that r = 4 for 4-valued logic.
The truncated sum (tsum)	tsum(a1,a2,…,an)=a1⊕a2⊕…⊕an={a1+a2+…+anif a1+a2+…+an<r−1r−1otherwise
	Where ai ∈ R and ⊕ represents the truncated sum operation.
The maximum (MAX) of two MVL variables	MAX(x1,x2)={x1if x1≥x2x2otherwise
The minimum (MIN) of two MVL variables	MIN(x1,x2)={x1if x1≤x2x2otherwise

Table 2

Average #PTs needed for realization of MVL Functions of the benchmark.

# minterms	16	15	14	13	12	11	10	9	8	7	6
# functions	500	2700	6600	1050	1130	9000	5450	2500	1100	275	75
#PT (ARM) [11]	7.59	8.30	8.36	8.28	8.05	7.71	7.32	6.87	6.31	5.73	5.13
#PT (BS) [9]	7.56	8.31	8.41	8.35	8.10	7.76	7.37	6.88	6.32	5.75	5.15
#PT (DM) [10]	7	7.51	7.57	7.54	7.38	7.13	6.83	6.47	6.02	5.53	4.97
#PT (ACO-MVL) [14]	6.73	7.05	7.16	7.18	7.09	6.9	6.66	6.36	5.93	5.48	4.96
Max improvement (%)	12.8	12.4	12.4	12.4	12.4	12.4	12.4	12.4	12.4	12.4	12.4
Min improvement (%)	4	6.5	5.7	5	4.2	3.3	2.6	1.8	1.5	0.9	0.3

Table 3

Fitness calculation for particle shown in Figure 11.

Particle	The obtained Truth Table	Nh	Nm	Ff	NP	Fo	Fitness
1	0000000033102200	15	1	14	3	0.97	14.97
2	0000000023102200	16	0	16	4	0.96	16.96
3	0000000023102200	16	0	16	2	0.98	16.98

Table 4

Average numbers of PTs for different values of particles and iterations.

Number of iterations	Number of Particles
	20	50	100
1000	7.92	7.59	7.40
2000	7.67	7.39	7.25
5000	7.40	7.20	7.11

Table 5

Average PT with Respect to Different Number of Minterms of MVL Functions.

# minterms	16	15	14	13	12	11	10	9	8	7	6
# functions	500	2700	6600	10,500	11,300	9000	5450	2500	1100	275	75
#PT (ARM) [11]	7.59	8.30	8.36	8.28	8.05	7.71	7.32	6.87	6.31	5.73	5.13
#PT (BS) [9]	7.56	8.31	8.41	8.35	8.1	7.76	7.37	6.88	6.32	5.75	5.15
#PT (DM) [10]	7	7.51	7.57	7.54	7.38	7.13	6.83	6.47	6.02	5.53	4.97
#PT (PSO-MVL) [15]	5.79	6.86	6.93	6.89	6.76	6.57	6.33	6.06	5.70	5.27	4.73
Max improvement (%)	31.2	30.7	30.7	30.7	30.7	31.2	30.7	30.7	30.7	30.7	30.7
Min improvement (%)	21	21	21	21	21	9.5	9.3	9.5	9.2	8.5	7.9

Table 6

Comparison between ACO-MVL and PSO-MVL in synthesis of the benchmark functions.

#minterms	# functions	#PTS (ACO-MVL)	#PTs (PSO-MVL)	(%) improvement
16	500	6.730	5.786	16.3
15	2700	7.054	6.860	2.8
14	6600	7.163	6.927	3.4
13	10,500	7.182	6.886	4.3
12	11,300	7.086	6.762	4.8
11	9000	6.904	6.569	5.1
10	5450	6.660	6.331	5.
9	2500	6.356	6.055	5.0
8	1100	5.934	5.697	4.2
7	275	5.480	5.274	3.9
6	75	4.960	4.733	4.8
	Total = 50000			Average = 5.4%

Table 7

Comparison among ACO-MVL, PSO-MVL, and Espresso-MV in synthesis of the benchmark.

# minterms	# functions	#PTs ACO-MVL	#PTs PSO-MVL	#PTs Espresso-MV	% Improvement ACO-MVL vs. Espresso-MV	% Improvement PSO vs. Espresso-MV
16	500	6.730	5.786	8.36	24.2	44.5
15	2700	7.054	6.860	8.06	14.3	17.5
14	6600	7.163	6.927	7.76	8.3	12.0
13	10,500	7.182	6.886	7.47	4.0	8.5
12	11,300	7.086	6.762	7.16	1.0	5.9
11	9000	6.904	6.569	7.48	8.3	13.9
10	5450	6.660	6.331	6.80	2.1	7.4
9	2500	6.356	6.055	6.41	0.8	5.9
8	1100	5.934	5.697	5.99	0.9	5.1
7	275	5.480	5.274	5.53	0.9	4.9
6	75	4.960	4.733	5.01	1.0	5.9
	Total = 50000				Average = 6.0	Average = 11.9