COMBINATIONAL CIRCUIT DESIGN

 

Solving combinational circuit design problems provides two valuable insights [Liu, 1996]:

• Injecting the best found solution to does not always lead to better performance
• Injecting a larger number of cases also does not always lead to better performance

A genetic algorithm can be used to design combinational circuits as described in  [Louis and Rawlins, 1991]. Consider a four-bit parity checker. It is one of different four-input one-output boolean functions. If we are trying to solve this class of problems, one way of indexing (defining similarity of problems) can be as follows: Concatenate the output bit for all possible 4-bit input combinations counting from 0 through 15 in binary. This results in a binary string of output bits, , of length 16. Strings that are one bit different from define a set of boolean functions, as do strings that are two bits different and so on. This way of naming boolean functions provides a simple distance metric and indexing mechanism for the combinational circuit design problems that we consider in this paper. Using the 4-bit parity problem as a base we define 4-1 problems to be one bit away from , while 6-4 problems are 4 bits away from a 6-bit parity checker. Problems are constructed from the parity problem by randomly choosing the output bits to be changed. The fitness of a candidate circuit is the number of correct output bits. Thus 5-bit problems would have a maximum fitness of .

Figure 2 compares the average fitness over time of a Randomly Initialized Genetic Algorithm (RIGA) with a Case Initialized Genetic AlgoRithm (CIGAR). In this figure, is the 5-bit parity checker and is a 5-8 problem. Ten percent ( ) of the initial population of the GA solving is injected with solutions to . In this experiment, we chose two kinds of 's individuals for injections:

  
Figure: Comparing average fitness of a RIGA versus CIGAR on the 5-8 problem when injecting case28 and case32.

1. case32 individuals: solutions to with fitness 32 on .
2. case28 individuals: solutions to with fitness 28 on . Note that these are not the best solutions to .

We fix the number of cases that are injected at of the population for all experiments dealing with the question of what cases to inject. Figure 2 is typical for average performance measurements across case fitnesses for a variety of problem distances and sizes. As we can see, the CIGAR performs better. As expected the initial performance difference is large. However, although the average fitness for injection with case32 starts off better than that for case28, injecting case28 results in better final performance.

Focusing on maximum fitness, the tendency for lower fitness cases to produce more improvement with increasing problem distance is emphasized on larger problems. This behavior can be seen in Figure 3 which plots maximum fitness over time on the 6-8 problem. The case64 (solution to the 6-bit parity problem) injected CIGAR does not improve at all, while the case52 CIGAR shows fairly consistent improvement in maximum fitness.

  
Figure: Comparing maximum performance of a RIGA with a CIGAR for different fitness cases on the 6-8 problem.

We explored a large number of 4, 5, and 6 bit problems and the results are reported in detail in [Liu, 1996], indicating the following general trends:

1. As the distance between problems increase, injecting or seeding cases with lower fitness (in ) results in better solutions.
2. The above tendency is emphasized with increasing problem size.
3. Injecting higher fitness individuals tends to lead to a quicker flattening out of the performance curve (average or maximum fitness versus time).

We can explain these results if we think of solutions as forming the leaves of a tree. Adapting one solution into another now means backing up to a common parent and then moving down the second solution's branch. Injecting cases closer to a common parent on the tree (lower fitness cases) shortens the path to a similar problem's solution since less backtracking is involved. The individuals generated by a genetic algorithm form such a tree with increasing schema order toward the leaves [Louis et al., 1993]. In terms of GA theory, injecting solutions that contain lower order, high fitness schema leads to the observed performance increase when problems are less similar. As problems get more similar, injecting higher order schema makes more sense. Our model thus indicates that increasing problem dissimilarity implies that we should inject cases of lower fitness corresponding to when the GA has fixed fewer positions in its population's genotypes (lower order schemas). This agrees well with the intuitive expectation that if the problems exceed a dissimilarity threshold we should simply use random initialization. Finally, increasing the problem size would also have a similar effect within this model since the tree depth increases with problem size. The last trend (item 3 in the list above) can be explained in terms of greater selection intensity causing the GA to quickly lose diversity. This is brought on by the increased fitness difference between the injected high fitness cases and the rest of the population.

Our previous results [Liu, 1996] indicate that finding the right number of cases to inject depends on a number of factors including the problem size and structure of the encoded search space. The major issue is the maintenance of diversity in the population. For our problems, when the number of injected cases passes a threshold (that depends on problem size), performance usually deteriorates over time. Since more injected cases cause the CIGAR to focus more on the sub space defined by these individuals, we would recommend going with a lower injection percentage if we are interested in long term solution quality, and with a larger percentage if we are interested in speed. A lower percentage of injected individuals allows greater population diversity leading to a more balanced exploration of the search space and thus reducing the probability of getting stuck on a local optimum. In practice, between 5 to 15 percent works well on our problems although larger percentages may also do well.