Evolvable Hardware Lab 1 Solutions

2-bit Adder Output Calculation

The target RAM needs to be loaded with the truth table of the circuit being evolved. The section of code below shows the loop that loads the truth table for the 1-bit adder.

// Iterate though all test vectors loading the correct output value (1-bit adder)
for(vector=0 ; vector<256 ; vector++)
{
   data = ((vector>>2)&0x1) + ((vector>>1)&0x1) + (vector&0x1);    // B + A + CIn
   EVOBLOCK_writeTargetRAM(data);
}

This section easily can be modified to load the truth table for the 2-bit adder. The code section below shows the altered version.

// Iterate though all test vectors loading the correct output value (2-bit adder)
for(vector=0 ; vector<256 ; vector++)
{
   data = ((vector>>3)&0x3) + ((vector>>1)&0x3) + (vector&0x1);    // B + A + CIn
   EVOBLOCK_writeTargetRAM(data);
}

This calculation uses the cell array input and output format shown in the figure below.

Cell Array Connections for the 2-bit Adder

The figure below should help explain how the calculation works. As the code comment indicates, the B, A and CIn parts are dealt with separately. Each is extracted from the same vector value. The result written into the array, data, is the sum of these three values. Two operators are used, a right shift (>>) and a bitwise and (&). The right shift moves the data toward the least significant bit (LSB), this has the effect of giving the bits the correct significance. The bitwise and is used as a mask to zero the unwanted remaining bits.

2-bit adder Truth Table Calculation

This table below provides a quick reference for the hex mask values.

Elitism

Elitism is very easily added to the GA. It simply involves directly moving the fittest individual from the currently evaluated population into the next population. The code section below shows the alteration required. The first line performs the actual elitism, copying the fittest into the next population. The next change is to make sure the tournament selection stage does not overwrite the elite individual.

// Copy fittest individual directly to next population
nextPopulation[0] = population[fittest];

// Create next population
for (tournament=1 ; tournament<POP_SIZE ; tournament++)
{
   parent1 = tournamentSelect(population, POP_SIZE, TOURNAMENT_SIZE);
   mutateArrayConfig(&population[parent1], &nextPopulation[tournament], MUTATION_RATE);
}

A slight modification of this approach is to perform a very low rate mutation on the elite individual before transferring it into the next population. This helps prevent the GA from getting stuck in a local maxima.

Crossover

There are various ways of implementing crossover. Below is a code section that shows one method.

maskBit = 0;

for (cellNum=0 ; cellNum<NUM_CELLS ; cellNum++)
{
   mask = 0;

   for (bit=0 ; bit<NUM_CONFIG_BITS ; bit++)
   {
      // If crossing over, flip mask bit
      if ((rand() & 0xFF) < crossoverRate) maskBit ^= 0x1;

      mask |= (maskBit << bit);
   }

   // Get source config
   config1 = source1->cellConfigs[cellNum];
   config2 = source2->cellConfigs[cellNum];

   // Calculate and write config to destination
   dest->cellConfigs[cellNum] = (config1 & mask) | (config2 & ~mask);
}

The first stage generates a mask, each bit of which specifies the parent from which the crossed configuration will be created. A mask bit of '1' means use config1, a '0' means config2.

The mask is initially set to all 0s. The mask is iterated over bit by bit and loaded with the value of maskBit. If the crossover is to occur, the value of maskBit is inverted. The result is a mask value which flips at crossover points.

The diagram below depicts this process. Note that the mask used in the example was generated using a high crossover rate. Also, for clarity, only eight configuration bits are shown.

Crossover

Solution Source File

A c source file with the alterations outlined on this page can be found using the link below. Although still not an optimal solution, it will still evolve a working 2-bit adder. Try altering the various parameters to speed up the evolutionary process.

As shown in the figures below, a file can be removed from a project by right-clicking on the file and selecting Remove (this will not delete the file). A file can be added into the project by right clicking on Sources and selecting Add Existing Files....

Removing a source file in XPS

Adding a source file in XPS

Example Solution

Using the code linked to above, exp2.c, the system should evolve a solution in 20% of the runs. The runs are limited to 500 generations, so this percentage would probably be higher for a larger generation limit. Below is an example array configuration for a 2-bit adder.

Solution Found, Gen: 153, fittest: 470 ( 96)
Cell  0 config: 6B277B22
Cell  1 config: 6B678CB3
Cell  2 config: 5FA96260
Cell  3 config: 396079BA
Cell  4 config: 1C1C0166
Cell  5 config: 6F924A67
Cell  6 config: 4E5A4229
Cell  7 config: 47510705
Cell  8 config: 1D5078AE
Cell  9 config: 19E33C99
Cell 10 config: 4E1A4BA0
Cell 11 config: 5DFC469C
Cell 12 config: 5CC57FEB
Cell 13 config: 591B3017
Cell 14 config: 3B7A9355
Cell 15 config: 3FA548CC
Cell 16 config: 3B35DDE3
Cell 17 config: 49190CF8
Cell 18 config: 52DAE035
Cell 19 config: 386796CA
Cell 20 config: 4E304B4D
Cell 21 config: 08D342ED
Cell 22 config: 742789DB
Cell 23 config: 2814F108
Cell 24 config: 53799536
Cell 25 config: 092530D0
Cell 26 config: 0CE17788
Cell 27 config: 451CBEBA
Cell 28 config: 167D3332
Cell 29 config: 4D3A1BF3
Cell 30 config: 348DAC2B
Cell 31 config: 0517B215
Cell 32 config: 6EF1288F
Cell 33 config: 426D6055
Cell 34 config: 53CA90B2
Cell 35 config: 0205B02C
Cell 36 config: 6F664E10
Cell 37 config: 6CDFF208
Cell 38 config: 4DBB599C
Cell 39 config: 3C7C7627