Combinational Circuit Design with Estimation of Distribution Algorithms

Introduction

The evolutionary design of combinational circuits is a strategy well known to human designers due to the uncommon characteristics of the solutions. Since evolutionary algorithms search the space and build up solutions from the bottom-up, the delivered circuits can be found through transformations which are correct in the Boolean algebra, but basically unknown to human designers. One advantage of the solutions is the circuit size which is frequently smaller than those produced by a human designer. The strategy, however, presents several drawbacks; the most important being the scalability. That is, when the complexity of a circuit is incremented in a linear way, the resources required by an evolutionary algorithm must be exponentially incremented. The main cause of this problem can be explained through the chromosome length. A bigger circuit is represented by a longer chromosome, and unfortunately, a long chromosome translates into convergence troubles for a Genetic Algorithm (and for any other evolutionary algorithms). Since the chromosome length is indeed proportional to the size of the circuit, the approaches to solve the scaling problem can be classified into two groups: 1) special coding to reduce the chromosome length, and 2) divide and conquer algorithms.

• Use of a Special Coding: Coding with a binary alphabet favors exploration via the creation of hyperplanes. However, several experimental results on circuit design provide strong evidence that supports the use of alphabets of cardinality greater than 2. For instance, the n-cardinality encoding proposed in Coello et al. (2000) helped to reduce the representation bias, and in fact, produced the best circuits.

• Divide and Conquer Algorithms: The goal is to reduce the complexity of the problem by breaking up the whole circuit into subcircuits. Accordingly, the main circuit is automatically split into subcircuits, which are thought to be simpler problems. Once the subcircuits are designed, they are connected to assemble the circuit for the next higher level. Several recent approaches are “divide and conquer” algorithms. Examples of this approach include the Bi-directional Incremental Evolution (Kalganova, 2000), the Generalized Disjunction Decomposition (Stomeo et al., 2006), the Scalable Approach to Evolvable Hardware (Torresen, 2002; Torresen, 1998), and the Stepwise Dimensional Reduction (Li et al., 2008).

Successful approaches for evolutionary design focus on the design of primitive building blocks which can later be used to construct more complex building blocks. The collected knowledge, encoded as building blocks in a population of chromosomes, has given way to the design of new algorithms whose main goal is to find and reuse the good partial solutions available in the population. Note that this approach must not be considered as another instance of the divide and conquer strategy, mainly because the solution is not the summation of n-partial solutions. For Estimation of Distribution Algorithms (EDAs), the goal is to represent promising partial solutions, and afterwards reproduce them in the next generation. Finding promising partial solutions is a big challenge. However, the strategy of EDAs is to learn a conditional probability model of the population, which can represent both the dependencies and the structure of the data.

The goal of this chapter is twofold. The first goal is to introduce two approaches based on EDAs for combinational circuit design. The first approach uses polytrees, while the second uses Bayesian networks. The second goal is to compare design methods based on data dependency models with evolutionary methods (which do not model data dependencies). We should determine whether the knowledge about patterns encoded as correlated variables reduces the number of fitness function evaluations required to design a combinational circuit.

The organization of this chapter is as follows. In Section 2 we introduce the concepts and background of EDAs. Afterwards, we introduce the polytree model in Section 3, and the Bayesian model in Section 4. The description of the problem we are to solve is given in Section 5. A broad set of experiments is described in Section 6, and conclusion is given in Section 7.