LOGIC CIRCUITS

Logic gates are the basic building blocks of logic circuits. In this chapter we’re going to use a genetic algorithm to combine logic gates into circuits that can do work.

Circuit infrastructure

As in the Lawnmower project it makes sense that our phenotype should have behaviors, so we’ll use objects. Also like that project we’ll build the infrastructure in a separate file. We’ll start with providing built-in gates for NOT and AND.

NOT and AND gates

The NOT gate takes one Boolean input and returns its opposite, so True if the input is False, otherwise False.

NOT gate truth table  (0=False, 1=True)
  input  |  output
--------------------
    0    |     1
    1    |     0

Since our input will not be a bare Boolean value but an upstream gate in the circuit, when asked for its output the NOT gate will first ask the upstream gate its value, then return the opposite.

circuits.py

class Not:
    def __init__(self, input):
        self._input = input

    def get_output(self):
        return not self._input.get_output()

The AND gate takes two Boolean inputs, A and B, and returns True if they are both True, otherwise False.

AND gate truth table (0=False, 1=True)
  inputs   |  output
  A  |  B  |
----------------------
  0  |  0  |     0
  0  |  1  |     0
  1  |  0  |     0
  1  |  1  |     1

Like the NOT gate, the AND gate must ask the gates that feed into it for their values before it can provide its output.

class And:
    def __init__(self, inputA, inputB):
        self._inputA = inputA
        self._inputB = inputB

    def get_output(self):
        aValue = self._inputA.get_output()
        bValue = self._inputB.get_output()
        return aValue and bValue

In addition to logic gates the circuit will also contain references to the actual A and B source inputs we’re testing. We need to be able to change the source values to check the fitness of the circuit, so we’ll give it a reference to a container whose contents we can modify externally.

class Source:
    def __init__(self, sourceId, sourceContainer):
        self._sourceId = sourceId
        self._sourceContainer = sourceContainer

    def get_output(self):
        return self._sourceContainer[self._sourceId]

We’ll use a new structure for the genotype, a tree node that contains the type of gate and indexes to 2 child tree nodes (potential inputs).

circuitTests.py

class Node:
    def __init__(self, createGate, indexA=None, indexB=None):
        self.CreateGate = createGate
        self.IndexA = indexA
        self.IndexB = indexB

Nodes to circuit

Now we’ll write the function that builds the circuit.

def nodes_to_circuit(nodes):
    circuit = []

It loops through all the nodes starting with the leaf nodes and rolling toward the root while connecting the logic gates together.

    for i, node in enumerate(nodes):

Using what we learned in the last chapter we can prevent recursion by design with the convention that child indexes are only valid if they are lower than the node index.

        inputA = circuit[node.IndexA] if node.IndexA is not None \
                                         and i > node.IndexA else None
        inputB = circuit[node.IndexB] if node.IndexB is not None \
                                         and i > node.IndexB else None

Lastly we update the circuit by creating the gate. The circuit we’ll use ends up fully connected and in the last index of the array. There may be latent circuits in the array as well when we’re done.

        circuit.append(node.CreateGate(inputA, inputB))
    return circuit[-1]

Note that since inputA and inputB can both be None it can cause NOT and AND gates to be instantiated with None inputs, so we need to handle that situation. A None input makes the gate output invalid so we’ll make it return None when that happens.

circuits.py

class And:
...
    def get_output(self):
        if self._inputA is None or self._inputB is None:
            return None
        aValue = self._inputA.get_output()
        bValue = self._inputB.get_output()
        return aValue and bValue

class Not:
...
    def get_output(self):
        if self._input is None:
            return None
        return not self._input.get_output()

That change forces us to also handle the possibility that the input gate is not None but returns None:

class Not:
...
    def get_output(self):
        if self._input is None:
            return None
        value = self._input.get_output()
        if value is None:
            return None
        return not value

class And:
...
    def get_output(self):
        if self._inputA is None or self._inputB is None:
            return None
        aValue = self._inputA.get_output()
        if aValue is None:
            return None
        bValue = self._inputB.get_output()
        if bValue is None:
            return None
        return aValue and bValue

Now we have what we need to build a circuit, provide inputs to a circuit and check the output. We’re ready to test.

Generate OR

For the first test we’re going to use a genetic algorithm to generate a circuit that behaves like an OR gate. An OR gate takes two Boolean inputs and returns True if either is True otherwise False. We can use the following truth table to see the expected output for each combination of inputs.

OR gate truth table (0=False, 1=True)
  inputs   |  output
  A  |  B  |
----------------------
  0  |  0  |     0
  0  |  1  |     1
  1  |  0  |     1
  1  |  1  |     1

In our test function we convert the table to an array of rules that can be used to evaluate a circuit’s fitness.

circuitTests.py

import unittest

class CircuitTests(unittest.TestCase):
    def test_generate_OR(self):
        rules = [[[False, False], False],
                 [[False, True], True],
                 [[True, False], True],
                 [[True, True], True]]
...
        self.find_circuit(rules, optimalLength)

That implies find_circuit

    def find_circuit(self, rules, expectedLength):
        def fnGetFitness(genes):
            return get_fitness(genes, rules, self.inputs)
...

and self.inputs, which is created before the first test runs.

class CircuitTests(unittest.TestCase):
    @classmethod
    def setUpClass(cls):
        cls.inputs = dict()
...

Now we have what we need to build the fitness function.

Fitness

To calculate the fitness we need to build the circuit from the nodes then use each rule’s inputs to test the circuit and count how many rules the circuit can satisfy.

def get_fitness(genes, rules, inputs):
    circuit = nodes_to_circuit(genes)
    sourceLabels = "AB"
    rulesPassed = 0
    for rule in rules:
        inputs.clear()
        inputs.update(zip(sourceLabels, rule[0]))
        if circuit.get_output() == rule[1]:
            rulesPassed += 1
    return rulesPassed

Display

We want to output the matching circuit, so we need to add str functions to the source and gate classes. If the gate has invalid inputs then we’ll show a question mark.

circuits.py

class Not:
...
    def __str__(self):
        if self._input is None:
            return "Not(?)"
        return "Not({})".format(self._input)

class And:
...
    def __str__(self):
        if self._inputA is None or self._inputB is None:
            return "And(?)"
        return "And({} {})".format(self._inputA, self._inputB)

class Source:
...
    def __str__(self):
        return self._sourceId

This produces output like the following:

sample output

Not(And(Not(B) And(Not(A) Not(B))))

Now we will bring it all together in the display function:

circuitTests.py

import datetime
...
def display(candidate, startTime):
    circuit = nodes_to_circuit(candidate.Genes)
    timeDiff = datetime.datetime.now() - startTime
    print("{}\t{}\t{}".format(
        circuit,
        candidate.Fitness,
        timeDiff))

    def find_circuit(self, rules, expectedLength):
        startTime = datetime.datetime.now()

        def fnDisplay(candidate):
            display(candidate, startTime)
...

Create

Our gene objects are complex, so we’ll use a special function to create them.

    def find_circuit(self, rules, expectedLength):
...
        def fnCreateGene(index):
            return create_gene(index, self.geneset)
...

Now we can complete the test harness by populating the gene set.

import circuits
...
class CircuitTests(unittest.TestCase):
...
    def setUpClass(cls):
        cls.inputs = dict()
        cls.geneset = [[circuits.And, circuits.And],
                       [lambda i1, i2: circuits.Not(i1), circuits.Not],
                       [lambda i1, i2: circuits.Source('A', cls.inputs),
                        circuits.Source],
                       [lambda i1, i2: circuits.Source('B', cls.inputs),
                        circuits.Source]]
...

It will pick child index values relative to the index where the node will be inserted so they’re more likely to be valid when converted to a circuit. We’ll also try to make the input indexes different so we reduce the waste from gates like And(A A).

import random
...
def create_gene(index, geneset):
    gateType = random.choice(geneset)
    indexA = indexB = None
    if gateType[1].input_count() > 0:
        indexA = random.randint(0, index)
    if gateType[1].input_count() > 1:
        indexB = random.randint(0, index) if index > 1 else 0
        if indexB == indexA:
            indexB = random.randint(0, index)
    return Node(gateType[0], indexA, indexB)

That implies the addition of an input_count function to the source and gate classes.

circuits.py

class Source:
...
    @staticmethod
    def input_count():
        return 0

class Not:
...
    @staticmethod
    def input_count():
        return 1

class And:
...
    @staticmethod
    def input_count():
        return 2

Mutate

Next we’ll add a custom mutate function.

circuitTests.py

    def find_circuit(self, rules, expectedLength):
...
        def fnMutate(genes):
            mutate(genes, fnCreateGene)
...

To be efficient in the mutate function, we only want to change the nodes that we actually use in the circuit. We can accumulate those while we’re building the circuit. The change in nodes_to_circuit is to add a tracking array where each element contains the set of node indexes that are used to build the corresponding circuit.

def nodes_to_circuit(genes):
    circuit = []
    usedIndexes = [] ①
    for i, node in enumerate(genes):
        used = {i} ②
        inputA = inputB = None
        if node.IndexA is not None and i > node.IndexA:
            inputA = circuit[node.IndexA]
            used.update(usedIndexes[node.IndexA]) ③
            if node.IndexB is not None and i > node.IndexB:
                inputB = circuit[node.IndexB]
                used.update(usedIndexes[node.IndexB]) ④
        circuit.append(node.CreateGate(inputA, inputB))
        usedIndexes.append(used) ⑤
    return circuit[-1], usedIndexes[-1] ⑥

That requires a corresponding change to the fitness function

def get_fitness(genes, rules, inputs):
    circuit = nodes_to_circuit(genes)[0]
...

and display function.

def display(candidate, startTime):
    circuit = nodes_to_circuit(candidate.Genes)[0]
...

Now we can call nodes_to_circuit to get the list of node indexes to use as mutation candidates.

def mutate(childGenes, fnCreateGene):
    count = random.randint(1, 5)
    while count > 0:
        count -= 1
        indexesUsed = [i for i in nodes_to_circuit(childGenes)[1]]
        index = random.choice(indexesUsed)
        childGenes[index] = fnCreateGene(index)

Create

We also need a custom create function. It is simple enough to be added inline.

    def find_circuit(self, rules, expectedLength):
...
        maxLength = expectedLength

        def fnCreate():
            return [fnCreateGene(i) for i in range(maxLength)]
...

Optimal OR circuit

To build the optimal solution let’s refer back to the OR gate truth table.

OR gate truth table (0=False, 1=True)
  inputs   |  output
  A  |  B  |
----------------------
  0  |  0  |     0
  0  |  1  |     1
  1  |  0  |     1
  1  |  1  |     1

If we could negate the first row we’d have a circuit that works for all four rules. NOT A anded with NOT B would get False. If we NOT that we get a circuit that works for all four rules, like this:

We’ll use the node count in that circuit to limit the number of nodes we use.

    def test_generate_OR(self):
...
        optimalLength = 6
        self.find_circuit(rules, optimalLength)

Finally we call the genetic engine.

import genetic
...
    def find_circuit(self, rules, expectedLength):
...
        best = genetic.get_best(fnGetFitness, None, len(rules), None,
                                 fnDisplay,fnMutate, fnCreate, poolSize=3)
        self.assertTrue(best.Fitness == len(rules))
        self.assertFalse(len(nodes_to_circuit(best.Genes)[1])
                         > expectedLength)

Run

When we run the test it finds the optimal solution every time.

Not(And(?))	0	0:00:00
Not(B)	1	0:00:00
And(B B)	3	0:00:00.001004
Not(And(Not(A) Not(B)))	4	0:00:09.581228

Great!

Generate XOR

Now let’s see if we can generate a circuit that behaves like an XOR (exclusive-or) gate. An XOR gate returns True if the inputs are different, otherwise False.

XOR gate truth table (0=False, 1=True)
  inputs   |  output
  A  |  B  |
----------------------
  0  |  0  |     0
  0  |  1  |     1
  1  |  0  |     1
  1  |  1  |     0

We’ll start by building a new test with those rules.

    def test_generate_XOR(self):
        rules = [[[False, False], False],
                 [[False, True], True],
                 [[True, False], True],
                 [[True, True], False]]
...

By comparing the XOR gate truth table with that of the OR gate we notice that the only difference is the last rule. This means that in order to determine the optimal solution for the XOR gate we can start with the circuit for the OR gate, Not(And(Not(A) Not(B))) (in blue below), and AND that with the opposite of a circuit that produces the fourth rule, Not(And(A B)). Here’s a visual representation:

The strict number of nodes in the circuit is 9, or 11 if we double count the source (A and B) nodes. That lets us finish writing the XOR test:

...
        self.find_circuit(rules, 9)

Run

Run the test and it almost always stalls.

And(B And(B B))	2	0:00:00.001003
Not(And(B A))	3	0:00:00.014127
And(Not(And(Not(A) Not(B))) Not(And(A B)))	4	0:09:44.378545

Can you think of any ways in which we can take advantage of our knowledge of the problem space to improve the performance of the genetic algorithm? Before reading further take about half an hour to experiment.

Performance improvement

The following is one of the easiest improvements to implement. Notice that the sources take up 2 of the 4 slots in the gene set. This means that on average they end up taking half the slots in the Chromosome, which makes it very difficult for the engine to build a complex circuit. The solution is to separate the sources from the gates and use only one copy of each of the sources because they can be referenced by index from any node with a higher index.

class CircuitTests(unittest.TestCase):
    @classmethod
    def setUpClass(cls):
        cls.inputs = dict()
        cls.gates = [[circuits.And, circuits.And],
                     [lambda i1, i2: circuits.Not(i1), circuits.Not]]
        cls.sources = [[lambda i1, i2: circuits.Source('A', cls.inputs),
                        circuits.Source],
                       [lambda i1, i2: circuits.Source('B', cls.inputs),
                        circuits.Source]]

Then pass both to create_gene:

    def find_circuit(self, rules, expectedLength):
...
        def fnCreateGene(index):
            return create_gene(index, self.gates, self.sources)
...

Next change create_gene so that sources are only added at the start of the node array, leaving the rest of the indexes for gates.

def create_gene(index, gates, sources):
    if index < len(sources): ①
        gateType = sources[index]
    else:
        gateType = random.choice(gates)
...
    if gateType[1].input_count() > 1:
        indexB = random.randint(0, index) \
            if index > 1 and index >= len(sources) else 0 ②
        if indexB == indexA:
...

We can also use our knowledge of the source locations in the gene sequence to reduce waste by preventing mutate from touching those nodes.

    def find_circuit(self, rules, expectedLength):
...
        def fnMutate(genes):
            mutate(genes, fnCreateGene, fnGetFitness, len(self.sources))
...

We’ll also check the fitness and return early if we find an improvement.

def mutate(childGenes, fnCreateGene, fnGetFitness, sourceCount):
    count = random.randint(1, 5)
    initialFitness = fnGetFitness(childGenes) ③
    while count > 0:
        count -= 1
        indexesUsed = [i for i in nodes_to_circuit(childGenes)[1] ④
                       if i >= sourceCount]
        if len(indexesUsed) == 0:
            return
        index = random.choice(indexesUsed)
        childGenes[index] = fnCreateGene(index)
        if fnGetFitness(childGenes) > initialFitness: ⑤
            return

These changes make it possible for the engine to find the solution every time.

And(?)	0	0:00:00.001005
Not(And(B Not(B)))	2	0:00:00.001005
And(Not(B) Not(Not(A)))	3	0:00:00.004011
And(Not(And(Not(B) Not(A))) Not(And(B A)))	4	0:00:02.235138

Very good!

Generate A XOR B XOR C

We’ve seen that the genetic algorithm can generate a circuit that passes the 4 rules required for 2 sources. Let’s try a circuit that uses 3 sources. This means it will have 2³ (8) rules. The circuit we’ll try to reproduce is A XOR B XOR C.

A `XOR` B `XOR` C truth table (0=False, 1=True)
      inputs     |  output
  A  |  B  |  C  |
----------------------------
  0  |  0  |  0  |     0
  0  |  0  |  1  |     1
  0  |  1  |  0  |     1
  0  |  1  |  1  |     0
  1  |  0  |  0  |     1
  1  |  0  |  1  |     0
  1  |  1  |  0  |     0
  1  |  1  |  1  |     1

Given that information, we can start writing the test.

    def test_generate_AxBxC(self):
        rules = [[[False, False, False], False],
                 [[False, False, True], True],
                 [[False, True, False], True],
                 [[False, True, True], False],
                 [[True, False, False], True],
                 [[True, False, True], False],
                 [[True, True, False], False],
                 [[True, True, True], True]]
        self.sources.append(
            [lambda l, r: circuits.Source('C', self.inputs),
             circuits.Source])
...

That means we need to add C to the source labels in get_fitness too:

def get_fitness(genes, rules, inputs):
    circuit = nodes_to_circuit(genes)[0]
    sourceLabels = "ABC"
...

Since we know we can build OR from AND and NOT we’ll add OR to the gates so we can use it to help keep the final circuit relatively short.

    def test_generate_AxBxC(self):
...
        self.gates.append([circuits.Or, circuits.Or])
...

The OR gate implementation would be almost identical to that of the AND gate, so let’s extract a base class.

circuits.py

class GateWith2Inputs:
    def __init__(self, inputA, inputB, label, fnTest):
        self._inputA = inputA
        self._inputB = inputB
        self._label = label
        self._fnTest = fnTest

    def get_output(self):
        if self._inputA is None or self._inputB is None:
            return None
        aValue = self._inputA.get_output()
        if aValue is None:
            return None
        bValue = self._inputB.get_output()
        if bValue is None:
            return None
        return self._fnTest(aValue, bValue)

    def __str__(self):
        if self._inputA is None or self._inputB is None:
            return "{}(?)".format(self._label)
        return "{}({} {})".format(self._label, self._inputA, self._inputB)

    @staticmethod
    def input_count():
        return 2

That simplifies the AND gate implementation to:

class And(GateWith2Inputs):
    def __init__(self, inputA, inputB):
        super().__init__(inputA, inputB, type(self).__name__,
                         lambda a, b: a and b)

The OR gate implementation is just as easy:

class Or(GateWith2Inputs):
    def __init__(self, inputA, inputB):
        super().__init__(inputA, inputB, type(self).__name__,
                         lambda a, b: a or b)

Next we need to solve the problem of figuring out what the optimal solution is. We could use a Karnaugh Map to reduce those 8 rules to a minimal circuit but doing so for circuits with many inputs becomes messy. So, let’s find another way. Historically we’ve used a variable length gene sequence when we didn’t know how many genes were needed, but as you may have observed, using tree nodes already makes the length adaptive if we give it enough indexes to work with. So we’re going to take this opportunity to introduce a new machine learning technique.

Hill climbing

Hill climbing is a popular problem space exploration technique where one feature of the Chromosome is incrementally adjusted until a better solution is found or a local minimum or maximum is detected, at which point the process repeats with a different feature. Some variants change any feature as long as it only affects a single piece of data, which may be smaller than a gene. An example from our current project would be to only change the gate type or just one of the indexes in a node rather than replacing the entire node as we’re doing now. Be aware that hill climbing doesn’t always find the optimal solution so it may need to be supplemented with simulated annealing.

We’ll implement hill climbing in the genetic module so that it is reusable. Starting with the function definition, it includes the optimization function it will call, a function to test whether an improvement has been found, a function to test whether the improvement is optimal so we can stop, a function that gets the next feature value, a display function, and the initial value of the feature we’re trying to optimize.

genetic.py

def hill_climbing(optimizationFunction, is_improvement, is_optimal,
                  get_next_feature_value, display, initialFeatureValue):

We get the initial result. Then, to keep it from being chatty, we redirect the output just like we do when benchmarking, and only restore it for calls to display.

    best = optimizationFunction(initialFeatureValue)
    stdout = sys.stdout
    sys.stdout = None

Once we have a result we’re going to enter a loop where we keep getting new results until we find an optimal one.

    while not is_optimal(best):
        featureValue = get_next_feature_value(best)
        child = optimizationFunction(featureValue)

When we find an improvement it becomes the new best value and we display it.

        if is_improvement(best, child):
            best = child
            sys.stdout = stdout
            display(best, featureValue)
            sys.stdout = None

If we find the optimal solution we return it.

    sys.stdout = stdout
    return best

Add hill climbing to the test harness

Now we need to build the inputs we’re going to pass to the hill_climbing function. We’ll start by wrapping the current call to get_best in a new function. This will be the optimization function. We’ll give it a maximum of 50 gates to work with and see what it finds.

circuitTests.py

   def find_circuit(self, rules, expectedLength):
...
        maxLength = 50
...
        def fnOptimizationFunction(variableLength):
            nonlocal maxLength
            maxLength = variableLength
            return genetic.get_best(fnGetFitness, None, len(rules), None,
                                    fnDisplay, fnMutate, fnCreate,
                                    poolSize=3, maxSeconds=30)

I gave it 30 seconds to try to find an improvement, but you might be able to use a lower value. The feature we’re optimizing is the number of nodes in the circuit. We need to get that to the create_gene function. We’ll do that by transferring it to the existing maxLength variable that is already passed to that function.

Next we need a function that can tell whether the new result is better than the current best. We return True if all the rules pass and the number of gates used in the new result if less than that of the current best result, otherwise False.

        def fnIsImprovement(currentBest, child):
            return child.Fitness == len(rules) and \
                   len(nodes_to_circuit(child.Genes)[1]) < \
                   len(nodes_to_circuit(currentBest.Genes)[1])

We also need a function that can tell whether we’ve found the known optimal solution (expectedLength). Note that if we don’t know the optimal value we could simply use an impossibly low value and let it run until we’re ready to stop it.

        def fnIsOptimal(child):
            return child.Fitness == len(rules) and \
                   len(nodes_to_circuit(child.Genes)[1]) <= expectedLength

As for display, we can simply add an optional parameter to the existing fnDisplay for the feature value. When it is set we show the number of nodes used in the new best circuit.

        def fnDisplay(candidate, length=None):
            if length is not None:
                print("-- distinct nodes in circuit:",
                      len(nodes_to_circuit(candidate.Genes)[1]))
            display(candidate, startTime)

When an improvement is found we’ll make the number of nodes in that circuit the new value to beat.

        def fnGetNextFeatureValue(currentBest):
            return len(nodes_to_circuit(currentBest.Genes)[1])

At the end we call the hill climbing function.

        best = genetic.hill_climbing(fnOptimizationFunction,
                                     fnIsImprovement, fnIsOptimal,
                                     fnGetNextFeatureValue, fnDisplay,
                                     maxLength)
        self.assertTrue(best.Fitness == len(rules))
        self.assertFalse(len(nodes_to_circuit(best.Genes)[1])
                         > expectedLength)

Now we’re finally able to finish the test implementation.

    def test_generate_AxBxC(self):
...
        self.find_circuit(rules, 12)

Run

Let’s first verify that the OR and XOR tests work.

sample OR test result

And(And(And(And(?) Not(And(?))) Not(Not(And(?)))) And(Not(And(?)) Not(And(?))))	0	0:00:00
Not(Not(B))	3	0:00:00.004012
Not(And(Not(And(Not(A) B)) And(Not(Not(Not(Not(Not(A))))) Not(B))))	4	0:00:00.013128
-- distinct nodes in circuit: 8
Not(And(Not(B) And(Not(B) Not(A))))	4	0:00:00.021112
-- distinct nodes in circuit: 6
Not(And(Not(A) Not(B)))	4	0:00:00.080303

sample XOR test result

Not(And(?))	0	0:00:00.001003
Not(And(And(Not(And(A B)) And(Not(Not(And(A B))) Not(And(A B)))) A))	2	0:00:00.003008
And(Not(And(A And(A B))) Not(Not(Not(And(A B)))))	3	0:00:00.007047
And(Not(And(Not(A) Not(B))) Not(And(And(And(B And(B A)) And(B A)) Not(Not(And(B A))))))	4	0:00:00.287776
-- distinct nodes in circuit: 9
And(Not(And(B A)) Not(And(Not(B) Not(A))))	4	0:00:02.833747

Now let’s see how it does on A XOR B XOR C.

And(Or(?) Not(Not(C)))	0	0:00:00.001001
And(And(Not(C) And(And(Not(A) B) Not(Not(Not(C))))) Not(A))	5	0:00:00.006120
And(And(Not(And(B Or(A C))) Not(A)) Not(And(Not(C) Not(Or(B And(B Or(A C)))))))	6	0:00:00.470108
And(Or(Not(Or(And(A And(A C)) And(Or(A C) B))) And(And(And(And(A C) Or(A C)) B) And(Not(Not(Or(And(A And(A C)) And(Or(A C) B)))) And(Or(A C) B)))) Or(And(Or(A C) Not(Or(And(A And(A C)) And(Or(A C) B)))) B))	8	0:00:02.133227
-- distinct nodes in circuit: 13
And(Not(And(Or(B C) And(A Or(Not(C) Not(B))))) Or(A And(Or(Not(C) Not(B)) Or(B C))))	8	0:00:50.958561
-- distinct nodes in circuit: 12
Or(And(Or(A C) Not(Or(And(A C) B))) And(B Or(And(A C) Not(Or(A C)))))	8	0:01:04.648605

Excellent!

If it takes an excessively long time to find the result on your box, you may need to increase the number of seconds you let it run on each optimization pass.

Generate a 2-bit adder

Now for something more interesting, a 2-bit adder. A 2-bit adder can add two numbers in the range 0..3 to get a result in the range 0..6. This means we need 4 sources, A and B for the first number, and C and D for the second. We also need 3 result bits for the 4’s, 2’s and 1’s result bits. 4 source-inputs means we’ll have 2⁴ (16) rules. Here’s the truth table.

2 bit adder truth table (0=False, 1=True)
      inputs 1     |     input 2       |    outputs   | equation
 A (2's) | B (1's) | C (2's) | D (1's) |  4's 2's 1's |
----------------------------------------------------------------
    0    |    0    |    0    |    0    |  0   0   0   |  0 + 0 = 0
    0    |    0    |    0    |    1    |  0   0   1   |  0 + 1 = 1
    0    |    0    |    1    |    0    |  0   1   0   |  0 + 2 = 2
    0    |    0    |    1    |    1    |  0   1   1   |  0 + 3 = 3
    0    |    1    |    0    |    0    |  0   0   1   |  1 + 0 = 1
    0    |    1    |    0    |    1    |  0   1   0   |  1 + 1 = 2
    0    |    1    |    1    |    0    |  0   1   1   |  1 + 2 = 3
    0    |    1    |    1    |    1    |  1   0   0   |  1 + 3 = 4
    1    |    0    |    0    |    0    |  0   1   0   |  2 + 0 = 2
    1    |    0    |    0    |    1    |  0   1   1   |  2 + 1 = 3
    1    |    0    |    1    |    0    |  1   0   0   |  2 + 2 = 4
    1    |    0    |    1    |    1    |  1   0   1   |  2 + 3 = 5
    1    |    1    |    0    |    0    |  0   1   1   |  3 + 0 = 3
    1    |    1    |    0    |    1    |  1   0   0   |  3 + 1 = 4
    1    |    1    |    1    |    0    |  1   0   1   |  3 + 2 = 5
    1    |    1    |    1    |    1    |  1   1   0   |  3 + 3 = 6

We could change the code to work with N-result bits, essentially N-circuits, but we can get the same result without that complexity by searching for each result bit’s circuit in a separate test and sharing the setup code between them. We can build the setup function from the truth table above.

    def get_2_bit_adder_rules_for_bit(self, bit):
        rules = [[[0, 0, 0, 0], [0, 0, 0]],  # 0 + 0 = 0
                 [[0, 0, 0, 1], [0, 0, 1]],  # 0 + 1 = 1
                 [[0, 0, 1, 0], [0, 1, 0]],  # 0 + 2 = 2
                 [[0, 0, 1, 1], [0, 1, 1]],  # 0 + 3 = 3
                 [[0, 1, 0, 0], [0, 0, 1]],  # 1 + 0 = 1
                 [[0, 1, 0, 1], [0, 1, 0]],  # 1 + 1 = 2
                 [[0, 1, 1, 0], [0, 1, 1]],  # 1 + 2 = 3
                 [[0, 1, 1, 1], [1, 0, 0]],  # 1 + 3 = 4
                 [[1, 0, 0, 0], [0, 1, 0]],  # 2 + 0 = 2
                 [[1, 0, 0, 1], [0, 1, 1]],  # 2 + 1 = 3
                 [[1, 0, 1, 0], [1, 0, 0]],  # 2 + 2 = 4
                 [[1, 0, 1, 1], [1, 0, 1]],  # 2 + 3 = 5
                 [[1, 1, 0, 0], [0, 1, 1]],  # 3 + 0 = 3
                 [[1, 1, 0, 1], [1, 0, 0]],  # 3 + 1 = 4
                 [[1, 1, 1, 0], [1, 0, 1]],  # 3 + 2 = 5
                 [[1, 1, 1, 1], [1, 1, 0]]]  # 3 + 3 = 6
        bitNRules = [[rule[0], rule[1][2 - bit]] for rule in rules]
...

Here we take advantage of a Python feature that equates 0 with False and 1 with True to simplify the implementation. We also need to add C and D to the sources, and to keep the results short we’ll use both an OR gate and an XOR gate.

...
        self.gates.append([circuits.Or, circuits.Or])
        self.gates.append([circuits.Xor, circuits.Xor])
        self.sources.append([lambda l, r: circuits.Source('C', self.inputs),
                             circuits.Source])
        self.sources.append([lambda l, r: circuits.Source('D', self.inputs),
                             circuits.Source])
        return bitNRules

Next add D to the source labels in get_fitness.

def get_fitness(genes, rules, inputs):
    circuit = nodes_to_circuit(genes)[0]
    sourceLabels = "ABCD"
...

Here’s the implementation of the XOR gate.

circuits.py

class Xor(GateWith2Inputs):
    def __init__(self, inputA, inputB):
        super().__init__(inputA, inputB, type(self).__name__,
                         lambda a, b: a != b)

Tests

Now we’re ready to add the tests that find the circuit for each bit.

circuitTests.py

    def test_2_bit_adder_1s_bit(self):
        rules = self.get_2_bit_adder_rules_for_bit(0)
        self.find_circuit(rules, 3)

    def test_2_bit_adder_2s_bit(self):
        rules = self.get_2_bit_adder_rules_for_bit(1)
        self.find_circuit(rules, 7)

    def test_2_bit_adder_4s_bit(self):
        rules = self.get_2_bit_adder_rules_for_bit(2)
        self.find_circuit(rules, 9)

Run

It can quickly generate the optimal solution for the 1’s bit

sample solution for 1’s bit

Not(Or(And(?) C))	0	0:00:00.001003
Not(Or(Or(A C) C))	8	0:00:00.002006
And(Not(And(Xor(D Not(Not(Or(And(B D) C)))) And(A D))) Not(Not(Xor(D And(A And(B D))))))	9	0:00:00.007068
And(Not(Xor(Xor(Xor(D And(A And(B D))) A) Or(Xor(And(B D) Xor(D And(A And(B D)))) Not(Or(And(B D) C))))) Not(Not(Xor(D And(A And(B D))))))	10	0:00:00.009073
And(Not(Xor(Xor(Xor(D Xor(And(A D) B)) A) Or(Not(A) Not(Or(And(B D) C))))) Not(Not(Xor(D Xor(And(A D) B)))))	11	0:00:00.014086
Or(Xor(D B) Xor(And(Xor(D B) Not(D)) A))	12	0:00:00.032165
Or(Xor(D B) And(Not(D) Xor(D B)))	16	0:00:00.035143
-- distinct nodes in circuit: 3
Xor(D B)	16	0:00:00.036146

the 2’s bit

sample output for 2’s bit

Xor(Not(Not(B)) Xor(Or(?) Not(Not(B))))	0	0:00:00.001010
Xor(Not(Not(B)) Xor(Not(B) Not(Not(B))))	8	0:00:00.003009
Xor(Not(Not(And(A Or(C A)))) Xor(Xor(B Xor(A C)) And(A Or(C A))))	12	0:00:00.006119
Xor(Xor(Xor(And(A D) B) And(And(B A) B)) Xor(Xor(B Xor(A C)) Or(And(B A) Xor(And(A D) B))))	14	0:00:00.046253
Xor(Xor(Xor(And(B D) A) And(Xor(Not(C) C) B)) Xor(Xor(B Not(C)) Or(Xor(Not(C) C) Xor(And(B D) A))))	16	0:00:00.338064
-- distinct nodes in circuit: 8
Xor(And(B And(D B)) Xor(A C))	16	0:00:00.431277
-- distinct nodes in circuit: 7
Xor(Xor(And(D B) C) A)	16	0:00:30.907710

and the 4’s bit.

sample solution for 4’s bit

Or(Or(Or(Or(?) B) A) A)	0	0:00:00.001004
Not(Xor(Not(Not(A)) Not(Not(Or(Xor(A C) Not(A))))))	8	0:00:00.002005
Not(Not(And(And(D And(D C)) And(A D))))	12	0:00:00.007520
And(C Xor(Xor(B C) Or(Not(D) Not(And(And(A A) And(Xor(B C) Xor(B C)))))))	13	0:00:00.193725
And(C Xor(Not(A) Or(And(A A) Not(A))))	14	0:00:00.224307
And(C Or(Not(Or(Not(A) Xor(A C))) And(B D)))	15	0:00:01.020520
And(And(Or(D And(C A)) Or(Not(Or(A Xor(Not(B) C))) Or(C And(Not(And(A Not(B))) B)))) Or(A Xor(Not(B) C)))	16	0:00:11.065914
-- distinct nodes in circuit: 13
And(Or(And(A C) And(Not(Not(D)) B)) Or(Xor(And(Not(Not(D)) A) Not(D)) C))	16	0:00:15.089580
-- distinct nodes in circuit: 10
Or(And(C A) And(And(B D) Or(Xor(A C) A)))	16	0:00:28.089024
-- distinct nodes in circuit: 9
And(Or(C And(D B)) Or(And(C And(D B)) A))	16	0:01:15.223721

Outstanding!

Retrospective

Tree nodes are often used instead of arrays in genetic programming because it is much easier to inject new functionality between two nodes. You should be able to adapt the way tree nodes are used in this chapter to the Lawnmower Problem. One way would be for all nodes to use the first child node to point to the next instruction. Then each func instruction could define its instructions on the second child node, making it easier for the genetic algorithm to modify the contents of the function.

You might also implement NAND and NOR gates to see if they improve upon the optimal solutions we found in this chapter.

Summary

This chapter showed how tree nodes can be used in a genetic algorithm for both fixed- and variable-length genotypes. It also introduced hill climbing, a very useful but potentially time consuming optimization technique.

Final Code

The final code for this chapter is available from:

https://github.com/handcraftsman/GeneticAlgorithmsWithPython/tree/master/ch16