Software Programming

Kunuk Nykjaer

Hybrid AI example with Java Genetic algo and NN

leave a comment »


This simple example combines Genetic algo with Neural network.
We train the xor by using the weights as the chromosome. The population is candidates of NN.
The fitness function is (1/sumOfSquaredErrors).
The NN has 2 inputs, 2 hidden and 1 output.

After 1000 evolutions, the candidates has the ‘correct’ weights. The back propagation is not used for the NN.

This is a global search. Using only NN is local search, which might get stuck in a local minimum.

Hybrid.java

import java.util.*;

public class Hybrid {

	LinkedList<NN> population = new LinkedList<NN>();
	final static int populationSize = 100;
	static Random rand = new Random();

	public Hybrid() {
		for (int i = 0; i < populationSize; i++) {
			NN c = new NN();
			population.add(c);
		}
	}

	public static void main(String[] args) {
		long BEGIN = System.currentTimeMillis();

		Hybrid h = new Hybrid();
		h.run(1000); // evolutions

		long END = System.currentTimeMillis();
		System.out.println("Time: " + (END - BEGIN) / 1000.0 + " sec.");
	}

	void run(int evolutions) {
		int count = 0;
		System.out.println("Optimal fitness value >= " + (1 / 0.001));
		System.out.println("Fitness random init");
		print();

		while (count < evolutions) {
			count++;
			produceNextGen();
		}

		System.out.println("\nFitness Result after evolutions " + evolutions);
		print();

		System.out.println("First candidate test print");
		NN nn = population.getFirst();
		nn.printAllWeights();
		System.out.println("sumSquaredErrors = " + (1 / nn.fitness()));
		nn.resultPrint();
	}

	void print() {
		System.out.println("-- print");
		for (NN c : population) {
			System.out.println(c);
		}
	}

	/**
	 * Selection strategy: Tournament method Replacement strategy: steady state
	 * find 4 random in population not same let 2 fight, and 2 fight the winners
	 * makes 2 children
	 */
	void produceNextGen() {
		LinkedList<NN> newpopulation = new LinkedList<NN>();
		while (newpopulation.size() < populationSize) {
			int size = population.size();
			int i = rand.nextInt(size);
			int j, k, l;
			j = k = l = i;
			while (j == i)
				j = rand.nextInt(size);
			while (k == i || k == j)
				k = rand.nextInt(size);
			while (l == i || l == j || k == l)
				l = rand.nextInt(size);

			NN c1 = population.get(i);
			NN c2 = population.get(j);
			NN c3 = population.get(k);
			NN c4 = population.get(l);

			double f1 = c1.fitness();
			double f2 = c2.fitness();
			double f3 = c3.fitness();
			double f4 = c4.fitness();

			NN w1, w2;

			if (f1 > f2)
				w1 = c1;
			else
				w1 = c2;
			if (f3 > f4)
				w2 = c3;
			else
				w2 = c4;

			NN child1, child2;

			// Method uniform crossover
			NN[] childs = newChilds(w1, w2);
			child1 = childs[0];
			child2 = childs[1];

			double mutatePercent = 0.01;
			boolean m1 = rand.nextDouble() <= mutatePercent;
			boolean m2 = rand.nextDouble() <= mutatePercent;

			if (m1)
				mutate(child1);
			if (m2)
				mutate(child2);

			boolean isChild1Good = child1.fitness() >= w1.fitness();
			boolean isChild2Good = child2.fitness() >= w2.fitness();

			newpopulation.add(isChild1Good ? child1 : w1);
			newpopulation.add(isChild2Good ? child2 : w2);
		}

		population = newpopulation;
	}

	void mutate(NN c) {
		int i = rand.nextInt(NN.SIZE);
		double range = getRandom() * 2; // range [-1;1[ * 2
		c.chromosome[i] = c.chromosome[i] + range;
		c.setChromosome(c.chromosome); // update
	}

	double getRandom() {
		return (rand.nextDouble() * 2) - 1; // [-1;1[
	}

	// Uniform crossover
	static NN[] newChilds(NN c1, NN c2) {
		NN child1 = new NN();
		NN child2 = new NN();

		double[] chromosome1 = new double[NN.SIZE];
		double[] chromosome2 = new double[NN.SIZE];

		for (int i = 0; i < NN.SIZE; i++) {
			boolean b = rand.nextDouble() >= 0.5;
			if (b) {
				chromosome1[i] = c1.chromosome[i];
				chromosome2[i] = c2.chromosome[i];
			} else {
				chromosome1[i] = c2.chromosome[i];
				chromosome2[i] = c1.chromosome[i];
			}
		}
		child1.setChromosome(chromosome1);
		child2.setChromosome(chromosome2);

		return new NN[] { child1, child2 };
	}
}

NN.java

import java.util.*;

public class NN {
	
	Random rand = new Random();

	// Inputs for xor problem
	final float inputs[][] = { { 1, 1 }, { 1, 0 }, { 0, 1 }, { 0, 0 } };
	// Corresponding outputs
	final float expectedOutputs[][] = { { 0 }, { 1 }, { 1 }, { 0 } };
	double resultOutputs[][] = { { -1 }, { -1 }, { -1 }, { -1 } };
	double output[];

	final int INPUT=0;
	final int HIDDEN=1;
	final int OUTPUT=2;
	
	final static int SIZE = 9; // 2 2 1 layers, gives 9 weights total
	public double[] chromosome = new double[SIZE];

	final ArrayList<Neuron> inputLayer = new ArrayList<Neuron>();
	final ArrayList<Neuron> hiddenLayer = new ArrayList<Neuron>();
	final ArrayList<Neuron> outputLayer = new ArrayList<Neuron>();
	final Neuron bias = new Neuron();
	final static int layers[] = { 2, 2, 1 }; // input, hidden, output
	final static int randomWeightMultiplier = 30;

	float learningRate = 1f;
	float momentum = 0.9f;

	public NN() {		
				
		// create all Neurons and connections
		// connections are created in the neuron class
		for (int i = 0; i < layers.length; i++) {
			if (i == INPUT) { // input layer
				for (int j = 0; j < layers[i]; j++) {
					Neuron neuron = new Neuron();
					inputLayer.add(neuron);
				}
			} else if (i == HIDDEN) { // hidden layer
				for (int j = 0; j < layers[i]; j++) {
					Neuron neuron = new Neuron();
					neuron.addInConnectionsS(inputLayer);
					neuron.addBiasConnection(bias);
					hiddenLayer.add(neuron);
				}
			}

			else if (i == OUTPUT) { // output layer
				for (int j = 0; j < layers[i]; j++) {
					Neuron neuron = new Neuron();
					neuron.addInConnectionsS(hiddenLayer);
					neuron.addBiasConnection(bias);
					outputLayer.add(neuron);
				}
			} else {
				System.out.println("!Error NeuralNetwork init");
			}
		}

		// initialize random weights
		int i = 0;
		for (Neuron neuron : hiddenLayer) {
			ArrayList<Connection> connections = neuron.getAllInConnections();
			for (Connection conn : connections) {
				double newWeight = getRandom();
				conn.setWeight(newWeight);
				chromosome[i++] = newWeight;
			}
		}
		for (Neuron neuron : outputLayer) {
			ArrayList<Connection> connections = neuron.getAllInConnections();
			for (Connection conn : connections) {
				double newWeight = getRandom();
				conn.setWeight(newWeight);
				chromosome[i++] = newWeight;
			}
		}

		// reset id counters
		Neuron.counter = 0;
		Connection.counter = 0;
	}

	// random
	double getRandom() {
		return randomWeightMultiplier * (rand.nextDouble() * 2 - 1); // [-1;1[
	}

	void setInput(float inputs[]) {
		// There is equally many neurons in the input layer as there are
		// input variables
		for (int i = 0; i < inputLayer.size(); i++) {
			inputLayer.get(i).setOutput(inputs[i]);
		}
	}

	double[] getOutput() {
		double[] outputs = new double[outputLayer.size()];
		for (int i = 0; i < outputLayer.size(); i++)
			outputs[i] = outputLayer.get(i).getOutput();
		return outputs;
	}

	/**
	 * Calculate the output of the neural network based on the input The forward
	 * operation
	 */
	void activate() {
		for (Neuron n : hiddenLayer) {
			n.calculateOutput();
		}

		for (Neuron n : outputLayer) {
			n.calculateOutput();
		}
	}

	double[] getAllWeights() {
		double[] ds = new double[SIZE];
		int i = 0;
		// weights for the hidden layer
		for (Neuron n : hiddenLayer) {
			ArrayList<Connection> connections = n.getAllInConnections();
			for (Connection con : connections) {
				double w = con.getWeight();
				ds[i++] = w;
			}
		}
		// weights for the output layer
		for (Neuron n : outputLayer) {
			ArrayList<Connection> connections = n.getAllInConnections();
			for (Connection con : connections) {
				double w = con.getWeight();
				ds[i++] = w;
			}
		}

		return ds;
	}

	// chromosome
	public void setChromosome(double[] weights) {
		chromosome = weights;
		int i = 0;
		// weights for the hidden layer
		for (Neuron n : hiddenLayer) {
			ArrayList<Connection> connections = n.getAllInConnections();
			for (Connection con : connections) {
				double w = weights[i];
				con.setWeight(w);
				i++;
			}
		}
		// weights for the output layer
		for (Neuron n : outputLayer) {
			ArrayList<Connection> connections = n.getAllInConnections();
			for (Connection con : connections) {
				double w = weights[i];
				con.setWeight(w);
				i++;
			}
		}
	}

	public void printAllWeights() {
		// weights for the hidden layer
		for (Neuron n : hiddenLayer) {
			ArrayList<Connection> connections = n.getAllInConnections();
			for (Connection con : connections) {
				double w = con.getWeight();
				System.out.println("n=" + n.id + " c=" + con.id + " w=" + w);
			}
		}
		// weights for the output layer
		for (Neuron n : outputLayer) {
			ArrayList<Connection> connections = n.getAllInConnections();
			for (Connection con : connections) {
				double w = con.getWeight();
				System.out.println("n=" + n.id + " c=" + con.id + " w=" + w);
			}
		}
	}

	double fitness() {
		double error = 0;
		for (int p = 0; p < inputs.length; p++) {
			setInput(inputs[p]);

			activate();

			output = getOutput();
			resultOutputs[p] = output;

			for (int j = 0; j < expectedOutputs[p].length; j++) {
				double err = Math.pow(resultOutputs[p][j]
						- expectedOutputs[p][j], 2);
				error += err;
			}
		}

		return 1 / error; // error can not be 0
	}

	void resultPrint() {
		for (int p = 0; p < inputs.length; p++) {
			System.out.print("INPUTS: ");
			for (int x = 0; x < layers[INPUT]; x++) {
				System.out.print(Float.toString(inputs[p][x]) + " ");
			}

			System.out.print("EXPECTED: ");
			for (int x = 0; x < layers[OUTPUT]; x++) {
				System.out.print(Float.toString(expectedOutputs[p][x]) + " ");
			}

			System.out.print("ACTUAL: ");
			for (int x = 0; x < layers[OUTPUT]; x++) {
				System.out.print(resultOutputs[p][x] + " ");
			}
			System.out.println();
		}
	}

	@Override
	public String toString() {
		return fitness() + "";
	}
}

Connection.java

public class Connection 
{	
	double weight=0;
	double prevDeltaWeight=0; // for momentum
	double deltaWeight=0;
		
	public Neuron leftNeuron;
	Neuron rightNeuron;
	public static int counter = 0;
	public int id;
	
	public Connection(Neuron fromN, Neuron toN){
		leftNeuron = fromN;
		rightNeuron = toN;
		id=counter;
		counter++;		
	}
	
	public double getWeight(){
		return weight;
	}
	public void setWeight(double w){
		weight = w;
	}
	
	public void setDeltaWeight(double w){
		prevDeltaWeight = deltaWeight;
		deltaWeight = w;
	}	
	
	public double getPrevDeltaWeight(){
		return prevDeltaWeight;
	}
		
	public Neuron getFromNeuron() {
		return leftNeuron;
	}
	public void setFromNeuron(Neuron fromNeuron) {
		this.leftNeuron = fromNeuron;
	}
	public Neuron getToNeuron() {
		return rightNeuron;
	}
	public void setToNeuron(Neuron toNeuron) {
		this.rightNeuron = toNeuron;
	}
}

Neuron.java

import java.util.ArrayList;
import java.util.HashMap;

public class Neuron 
{
	public static int counter = 0;
	public int id;
	double prevWeighted_sum;
	Connection biasConnection;
	final double bias = -1;
	double output;
	
	
	ArrayList<Connection> Inconnections = new ArrayList<Connection>();
	HashMap<Integer,Connection> connectionLookup = new HashMap<Integer,Connection>();
	
	public Neuron(){		
		id = counter;
		counter++;
	}
	
	/**
	 * Compute Sj = Wij*Aij + w0j*bias
	 * Apply activation function to get output
	 */
	public void calculateOutput(){
		double s = 0;
		for(Connection con : Inconnections){
			Neuron leftNeuron = con.getFromNeuron();
			double weight = con.getWeight();
			double a = leftNeuron.getOutput(); //output from previous layer
			
			s = s + (weight*a);
		}
		s = s + (biasConnection.getWeight()*bias);	
		output = g(s);
	}
	
	
	double g(double x) {
		return sigmoid(x);
	}

	double sigmoid(double x) {
		return 1.0 / (1.0 +  (Math.exp(-x)));
	}
	
	public void addInConnectionsS(ArrayList<Neuron> inNeurons){
		for(Neuron n: inNeurons){
			Connection con = new Connection(n,this);
			Inconnections.add(con);
			connectionLookup.put(n.getId(), con);
		}
	}
	
	public Connection getConnection(int neuronIndex){
		return connectionLookup.get(neuronIndex);
	}

	public void addInConnection(Connection con){
		Inconnections.add(con);
	}
	public void addBiasConnection(Neuron n){
		Connection con = new Connection(n,this);
		biasConnection = con;
		Inconnections.add(con);
	}
	public ArrayList<Connection> getAllInConnections(){
		return Inconnections;
	}
	
	public int getId(){
		return id;
	}
	public void setId(int i){
		id = i;
	}
	
	public double getBias() {
		return bias;
	}
	public double getOutput() {
		return output;
	}
	public void setOutput(double o){
		output = o;
	}
}

Result:

Optimal fitness value >= 1000.0
Fitness random init
— print
0.5000000009269805
0.500000232951657

Fitness Result after evolutions 1000
— print
3.3354638900410167E22
3.3354638900410167E22

First candidate test print
n=3 c=0 w=31.606277910728974
n=3 c=1 w=-50.54100092882488
n=3 c=2 w=17.775932295503686
n=4 c=3 w=49.91618475014163
n=4 c=4 w=-38.968161757863236
n=4 c=5 w=-20.253031449644787
n=5 c=6 w=55.76690734403492
n=5 c=7 w=-52.90412054261615
n=5 c=8 w=-26.253923811742883
sumSquaredErrors = 2.998083723783629E-23
INPUTS: 1.0 1.0 EXPECTED: 0.0 ACTUAL: 2.6666536854779678E-12
INPUTS: 1.0 0.0 EXPECTED: 1.0 ACTUAL: 0.9999999999997737
INPUTS: 0.0 1.0 EXPECTED: 1.0 ACTUAL: 0.9999999999960367
INPUTS: 0.0 0.0 EXPECTED: 0.0 ACTUAL: 2.6666567449509287E-12
Time: 3.411 sec.

Advertisements

Written by kunuk Nykjaer

October 23, 2010 at 12:09 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: