NNUGA

Neural Network Using Genetic Algorithms

By Omri Weisman and Ziv Pollack

A final project in the course Robotics 95

----------------

Using Genetic Algorithms in Computer Learning

Essentially, Genetic Algorithms (GA) are a method of "breeding" computer programs and solutions to optimization or search problems by means of simulated evolution. Processes loosely based on natural selection, crossover, and mutation are repeatedly applied to a population of binary strings which represent potential solutions. Over time, the number of above-average individuals increases, and better fit individuals are created, until a good solution to the problem at hand is found.

In NNUGA, we are using GA to find the solution to a classification problem with a neural network (NN). The neural network is a structure which is able to respond with True (1) or False (0) to a given input vector. We are trying to "teach" our neural network to correctly classify a set of input vectors, which can be thought of as learning a concept. We then expect that when the neural network will be presented with a vector P not from this set, it will tend to exhibit generalization by responding with an output similar to target vectors for input vectors close to the previously unseen input vector P.

Our genetic algorithm works with not one but multiple populations, all of which evolve seperately most of the time, except for once every several generations where we allow different populations to mix with each other.

The Neural Network

Our neural network has 2 inputs and 1 output. It is constructed from 6 neurons in the first layer and 1 neuron in a second layer.

In the first layer we have 2 neurons with atan transfer functions:

                atan( P * W + b )
2 with linear transfer functions: 
                P * W + b
and 2 with hardlim transfer functions: 
                P * W + b > 0
where P is the input vector presented to the network, W is the vector of weights and b is the bias of the neuron.

The output function of the neuron in the second layer is: 

                A * W + b > 0
where A is the vector of the outputs of the neurons in the first layer, W is the vector of weights and b is its bias. The output of this neuron is also the output of the network.

The Learning Method

As stated earlier, the neural network learns using genetic algorithms. This means that the weights and biases of all the neurons are joined to created a single vector. A certain set of vectors is a correct solution to the classification problem at hand. We are hoping to find one of these vectors using an evolutionary algorithm.

The Canonical GA (pseudo code): 

        choose initial population
        evaluate each individual's fitness
        repeat
                select individuals to reproduce
                mate pairs at random
                apply crossover operator
                apply mutation operator
                evaluate each individual's fitness
        until terminating condition
The learning loop can terminate either if a satisfactory solution is found, or the number of generations pass a preset limit, suggesting that a complete solution will not be found with this set of individuals.

In our case, we have several seperated populations, all of which evolve seperately. Once every several generations we allow cross-over from different populations.

Limitations

Sometimes it could happen that though the NN could theoretically solve a certain classification problem, our system will not return a correct solution. This is because of the random nature of the algorithm and its reliance on natural selection, mutation and cross-overs. Naturally, it could happen that a certain flow of events that would lead to a correct solution will not occure and thus a solution will not be found. However, by using several unrelated populations we have decreased the probabilty of this happening, since if some population has poor individuals the solution could still be found at another.

Our Implementation

We implemented a network with 2 inputs. The input for the neural network can be taken from a graphic user interface, by clicking on points in a board. A click with the left mouse button generates a '+' sign on the board, marking that it's a point where the NN should respond with 'True'. A click with the right mouse button generates a '-' sign on the board, marking that it's a point where the NN should respond with 'False'. When enough points have been entered, the user can click on 'Start', which will introduce these points as inputs to the NN, have it learn these input vectors and show a group of lines which corresponds to the division of the plane into regions of opposite neuron response. While the learning takes place, a textual indication of the learning process is presented on the standard output; This includes the fitness of the best individual in each population on each generation, and a schematic textual division of the plane once every 50 generations, to allow the user to inpect the progress.

Here's an example of a screen shot:

[Image: Example screen shot]

Examples

Here are more examples of screen shots.

Source Code

In order to be able to run the program, save all these files in a directory, type 'make', and use 'nnuga' to start the system.The program should run under all platforms which support Tk, though we tested it for UNIX SunOS only.

You can also grab all these files in one tarred gzipped file (8K) .

Note: This code is free and is in the public domain. You may copy, use, and change it as much as you like. However, the writers take no responsibility for the results of using this program.

See Also

Last updated August 13th 1995
Created by Omri Weisman