A Comparative Study of Encodings to Design Combinational Logic Circuits Using Particle Swarm Optimization Carlos A. Coello Coello, Erika Hern´andez Luna CINVESTAV-IPN Evolutionary Computation Group Dpto. de Ing. Elect./Secc. Computaci´on Av. IPN No. 2508, Col. San Pedro Zacatenco M´exico, D.F. 07300, MEXICO
[email protected] [email protected]
Abstract This paper extends our original proposal to use Particle Swarm Optimization (PSO) to design combinational logic circuits [4] in which a binary representation was adopted. In this case, we study the impact of the representation adopted. For that sake, we adopt 2 integer representations (one of which is proposed by us) and we compare them with respect to our previous binary representation and with respect to a multiobjective genetic algorithm that uses an integer encoding. For our comparative study, we adopted several combinational logic circuits of one and several outputs whose designs have been previously studied in the specialized literature. Our results indicate that PSO can be a competitive algorithm for circuit design when using one of the integer representations proposed.
1 Introduction The Particle Swarm Optimization algorithm was originally proposed by Kennedy and Eberhart [7, 8] and has its roots in artificial life, social psychology, engineering and computer science. The main idea behind PSO is to simulate the movement of a flock of birds seeking food. In this simulation, the behavior of each individual gets affected by both an individual and a social factor. Each individual contains its current position in the search space as well as its velocity and the best position found by the individual so far [8]. PSO can be seen as a distributed behavioral algorithm that performs (in its more general version) multidimensional search. In the simulation, the behavior of each individual is affected by either the best local (i.e., within a certain neighborhood) or the best global individual. The ap-
Arturo Hern´andez Aguirre Center for Research in Mathematics (CIMAT) Department of Computer Science Guanajuato, Gto. 36240, MEXICO
[email protected]
proach uses a population of potential solutions (called “particles”) and a measure of performance similar to the fitness value used with evolutionary algorithms. Also, the adjustments of individuals are analogous to the use of a crossover operator. However, this approach introduces the use of flying potential solutions through hyperspace (used to accelerate convergence). Additionally, PSO allows individuals to benefit from their past experiences [8]. The past success of PSO in diverse optimization tasks motivated us to use this heuristic to design combinational circuits [4]. However, the main issue when applying PSO to combinational circuit design has to do with the encoding adopted. In our previous work, we used binary representation and we were able to find reasonably good results, but without outperforming in any way to a genetic algorithm [4]. In this paper, we adopt 2 integer representations for the use of PSO in the design of combinational logic circuits (one of which is proposed by us), and we compare them. The main goal of this work is to study the impact of the representation adopted on the performance of our PSO algorithm.
2 Description of our Approach The problem of interest to us consists of designing a circuit that performs a desired function (specified by a truth table), given a certain specified set of available logic gates. In circuit design, one can use various criteria to define minimal-cost expressions. The complexity of a logic circuit is a function of the number of gates in the circuit. The complexity of a gate generally is a function of the number of inputs to it. Because a logic circuit is a realization (implementation) of a Boolean function in hardware, reducing the number of literals in the function should reduce the num-
ber of inputs to each gate and the number of gates in the circuit—thus reducing the complexity of the circuit. Therefore, the main objective of the work reported here is to minimize the total number of gates of feasible circuits (i.e., those that match all the desired outputs expressed in their truth table). To encode a circuit, we used the same matrix representation adopted in some of our previous work [2]. Such representation is shown in Figure 1. More formally, we can say that any circuit can be represented as a bidimensional , where indicates the level of a gate, so array of gates that those gates closer to the inputs have lower values of . (Level values are incremented from left to right in Figure 1). For a fixed , the index varies with respect to the gates that are “next” to each other in the circuit, but without being necessarily connected. Each matrix element is a gate (there are 5 types of gates: AND, NOT, OR, XOR and WIRE1 ) that receives its 2 inputs from any gate at the previous column as shown in Figure 1. This sort of encoding was originally proposed by Louis [9]. The so-called “cartesian genetic programming” [11] also adopts a similar encoding to the matrix previously described. A logic circuit can be encoded using integers that correspond to the type of gate and its inputs. PSO, however, tends to deal with either binary or real-numbers representation. For our comparative study, we will adopt two integer representations: (1) Integer A (proposed by Hu et al. [5]), and (2) Integer B (proposed by us in this paper). In the PSO algorithm, the individual factor refers to the decisions that the individual has made so far and that have worked best (in terms of its performance measure). This value has an impact on its future decisions. Additionally, the social factor refers to the decisions that the other individuals (within a certain neighborhood) have made so far and that have worked best for them. This value will also affect the future decisions of the individuals in the given neighborhood. Figure 2 shows the pseudocode of the PSO algorithm that we propose for the design of combinational logic circuits. Its main difference with respect to traditional PSO has to do with the update of the position of the particle in each of its dimensions (which is marked with ** in Figure 2). Both, the Integer A and the Integer B approaches normalize the velocity of each dimension of the particle in the range 0 to 1, so that we can further determine (in a random way using a flip function F) whether we need to change the current position or not (this is done with the probability given by the velocity). If the change is required, then we copy to the particle the value of in the current position. Otherwise, the Integer A approach leaves the particle intact. When 1 WIRE basically indicates a null operation, or in other words, the absence of gate, and it is used just to keep regularity in the representation used, since otherwise would have to use variable-length strings.
Randomly initialize the population of particles, . Repeat For each particle in the population Compute the fitness of the particle If the fitness of is better than the fitness of the best particle found so far !" , Then update ! using # $ For each particle in Select the particle with the best fitness in the topological neighborhood of # and $ update the value of %& !" # For each particle in the population Compute the new velocity for each dimension of the ' particle ' ' '
(
( *) ' +-, /.1' 0 24365 798 ;:"="?" A@ B DC3 5FEG8 %H:I
