XOR Experiment

XOR problem is not linearly separable because there is no function over a linear combination of the inputs that can separate the inputs into the proper classes. Thus, Neural Network requires at least one hidden node to solve it. The hidden node combines activation signals received from two inputs and produces an output activation signal received by the output node.

Such structural requirements make the XOR problem suitable for testing NEAT’s ability to evolve the neural network topology.

The XOR Experiment with connected inputs in the start genome

In this experiment, we will use the start (seed) genome with inputs connected to the output. Thus, it will mainly check the ability of the NEAT algorithm to grow a new hidden unit necessary for solving the XOR problem.

To run this experiment execute the following commands:

cd $GOPATH/src/github.com/yaricom/goNEAT
go run executor.go -out ./out/xor -context ./data/xor.neat -genome ./data/xorstartgenes -experiment XOR

Where:

• -context ./data/xor.neat - is the configuration options of the NEAT execution context
• -genome ./data/xorstartgenes - is the start genome configuration
• -out ./out/xor - the output directory to store experiment results

This command will run 100 trials of the XOR experiment. Each trial will run 100 epochs of the evolution and save the result into the specified output directory.

In the output directory, results are arranged by folders named using epoch ID. There would be stored several 'gen_x' files with snapshots of the population per 'print_every' generation. Additionally, the population where successful solver found also saved into this directory.

The genome of the successful solver (if found) is saved into the 'xor_winner-x-y' file. If a successful solver happens to have optimal configuration, it would be saved into the 'xor_optimal-x-y' file. The x is the number of nodes in the NN, and y stands for the number of links between them.

The optimal configuration of the XOR problem solver has five nodes:

• one bias node
• two input nodes
• one hidden node
• one output node

By examining the content of the resulting 'xor_winner-x-y' files from a series of experiments, you will find that at least one hidden unit was grown by the NEAT algorithm to solve the XOR problem. The proof that the algorithm works as expected.

At the end of the experiment execution, some statistics will be printed to the console as follows:

Solved 92 trials from 100, success rate: 0.920000
Random seed: 1620474472
Average
        Trial duration:         444.057428ms
        Epoch duration:         3.093329ms
        Generations/trial:      58.5

Champion found in 51 trial run
        Winner Nodes:           8
        Winner Genes:           18
        Winner Evals:           12868

        Diversity:              58
        Complexity:             26
        Age:                    48
        Fitness:                15.999995

Average among winners
        Winner Nodes:           7.3
        Winner Genes:           14.7
        Winner Evals:           10867.1
        Generations/trial:      54.9

        Diversity:              41.043478
        Complexity:             21.989130
        Age:                    29.097826
        Fitness:                15.858986

Averages for all organisms evaluated during experiment
        Diversity:              25.158705
        Complexity:             14.505374
        Age:                    15.462671
        Fitness:                7.904119

Efficiency score:               11.002143

>>> Start genome file:  ./data/xorstartgenes
>>> Configuration file: ./data/xor.neat

Where:

• Winner nodes/genes - is number of units and links between in produced Neural Network which was able to solve XOR problem.
• Winner evals - is the number of evaluations of intermediate organisms/genomes before winner was found.
• Mean Complexity - is an average complexity (number of nodes + number of links) of the organisms per epoch for all trials.
• Mean Diversity - is an average diversity (number of species) per epoch for all trials
• Mean Age - is an average age of surviving species per epoch for all trials
• Generations/trial - is an average epochs per trial until successful solver is found
• Efficiency score - is the composite score allowing to compare various implementations of the algorithm

The efficiency score is calculated to give higher scores based on the following assumptions. We are interested in an efficient solver search solution that takes less time per epoch, fewer generations per trial, and produces less complex winner genomes. At the same time, it should have a maximal fitness score and maximal success rate among the trials.

Additionally, to help with a detailed analysis of the algorithm performance, the collected experimental data saved to the 'XOR.npz' file. This file saved using Numpy NPZ file format, allowing us to analyze it using plenty of available statistics libraries.

For example, the collected data samples can visualized using Matplotlib as follows:

We provide example of the Jupyter notebook, which can be used to analyse the collected data samples.

The XOR experiment with disconnected inputs in the start genome

This experiment will use the start genome with inputs disconnected from outputs to check the NEAT algorithm's ability to evolve the hidden nodes and create missed connections between input nodes and the rest of the network.

To run this experiment execute the following commands:

cd $GOPATH/src/github.com/yaricom/goNEAT
go run executor.go -out ./out/xor_disconnected -context ./data/xor.neat -genome ./data/xordisconnectedstartgenes -experiment XOR

Or use Makefile provided with algorithm as follows:

cd $GOPATH/src/github.com/yaricom/goNEAT
make run-xor-disconnected

This command will execute 100 trials of the XOR (disconnected) experiment with 100 evolutionary epochs per trial. The results of the experiment execution will be saved into the output directory as in the previous experiment.

The experiment sometimes fails to produce a successful XOR solver over 100 generations, but the algorithm finds the successful solution most of the time. This experiment confirms that the algorithm can grow required hidden units and restore input connections as needed.

The example output of the command as following:

Solved 87 trials from 100, success rate: 0.870000
Random seed: 1620477873
Average
        Trial duration:         374.029795ms
        Epoch duration:         2.387591ms
        Generations/trial:      64.4

Champion found in 62 trial run
        Winner Nodes:           7
        Winner Genes:           16
        Winner Evals:           12145

        Diversity:              48
        Complexity:             23
        Age:                    17
        Fitness:                16.000000

Average among winners
        Winner Nodes:           7.1
        Winner Genes:           13.6
        Winner Evals:           11729.7
        Generations/trial:      59.1

        Diversity:              43.804598
        Complexity:             20.689655
        Age:                    26.747126
        Fitness:                15.813548

Averages for all organisms evaluated during experiment
        Diversity:              25.899478
        Complexity:             12.126319
        Age:                    16.395136
        Fitness:                7.362373

Efficiency score:               10.661602

>>> Start genome file:  ./data/xordisconnectedstartgenes
>>> Configuration file: ./data/xor.neat

As we can see from the output above, the NEAT algorithm is slightly less effective with this experiment. The calculated efficiency score is lower than in the previous experiment: 10.661602 against 11.002143.