Thread: Help with a simple Genetic Algorithm

I've been working for quite some time on a genetic algorithm and I can't quite seem to figure out what's wrong with it. Am I simply not allowing enough time for the algorithm to run and give good results, or is there something wrong with the code that won't allow my GA to adequately make its members stronger each generation?

I was attempting to create a program that takes in user input as a string of 1s and 0s and then compares that user input to a string of 1s and 0s that serve as "chromosomes." The string of 1s and 0s closest to the User's input would have the highest fitness (if a 1 is in the same place as the user's string of 0s and 1s and the chromosome's, that chromosome's fitness is raised).

For now, I have commented out the user portion and am using a string of straight 0s to test my programs effectiveness to converge on such a string, but so far, my program does a brilliant job of converging on the exact average (a fitness rating of 64) instead of increasing its fitness rating. Am I missing something about genetic algorithms, is it simply reproducing too fast, is the POPSIZE to small, am I not crossing over enough, or is there something wrong with one of those methods? Or have I just not let it run for a long enough period?

I would love to have some help on this. Thanks!

import java.util.*;
public class ScrewingWithGA {
	private final int POPSIZE = 100;
	private int[][] population;
	private int[] userNumber;
	int indexA = 0, indexB = 0;
	private final byte CHROMSIZE = 127;
	Random r = new Random();
	Scanner s = new Scanner(System.in);
	public enum parent {
		A, B
	}
	//creates a new 2D Array, which will serve as the population and hold each individuals' "DNA," strings of 0s and 1s. Each # is a separate gene.
	//creates a new array which will store data from the user.
	public void createArrays(){
		population = new int[POPSIZE][CHROMSIZE];
		userNumber = new int[CHROMSIZE];
	}
	//fills the array with pseudo-random 0s and 1s, to create the starting population.
	public void createIndividuals(){
		for (int i = 0; i < POPSIZE; i++) {
			//Starts at 1 to preserve the first int space for the chromosome's score.
			for(int j = 1; j < CHROMSIZE; j++){
				population[i][j] = r.nextInt(2);
 
			}
		}
	}
	//The mutation method will randomly replace a gene with its opposite; if the gene is a 0 it is replaced with a 1; if it is 1, a 0.
	public void mutate(double randFactor){
		double mutateChecker;
		for (int i = 0; i < POPSIZE; i++) {
			//Again, starts at 1 to preserve the int space for the chromosome's score.
			for (int j = 1; j < CHROMSIZE; j ++) {
				mutateChecker = r.nextInt(10000);
				randFactor *= 100;
				if (mutateChecker < randFactor) {
					if (population[i][j] == 0)
						population[i][j] = 1;
					else
						population[i][j] = 0;
 
				}
			}
		}
	}
	public void bubbleSort(){
		int i, j, t=0;
		int[] temp = new int[CHROMSIZE];
			for(i = 0; i < POPSIZE ; i++ ){
				for(j = 1; j < (POPSIZE-i) ; j++){
					if( population[j-1][0] < population[j][0] ){
						t = population[j-1][0];
						for (int k = 1; k < CHROMSIZE; k++){
							temp[k] = population[j-1][k];
						}
						population[j-1][0] = population[j][0];
						for (int k = 1; k < CHROMSIZE; k++){
							population[j-1][k] = population[j][k];
						}
						population[j][0] = t;
						for (int k = 1; k < CHROMSIZE; k++){
							population[j][k] = temp[k];
						}
					}
				}
			}
	}
	public double getAverage(){
		int total = 0;
		for (int i = 0; i < POPSIZE; i++){
			total += population[i][0];
		}
		double average = total / POPSIZE;
		return average;
	}
	public int getBest(){
		return population[0][0];
	}
	public void runHumanInputTrial() {
		//System.out.println("Enter a string of 1s and 0s that is 128 digits long under the next line (use the line as reference).");
		//System.out.println("--------------------------------------------------------------------------------------------------------------------------------");
		//String userEntered = s.nextLine();
		String userEntered =("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
		for (int i = 0; i < CHROMSIZE; i++){
			userNumber[i] = Integer.parseInt(userEntered.substring(i, i + 1));
		}
		for (int i = 0; i < POPSIZE; i++){
			for (int j = 0; j < CHROMSIZE; j++){
				if (userNumber[j] == population[i][j]){
					population[i][0]++;
				}
			}
		}
	}
	private void checkCrossOver(){
		int highScore = population[0][0];
		int relFitness, parentTest = 0;
		parent p = parent.A;
		for (int i = 0; i < POPSIZE; i++){
			relFitness = highScore - population[i][0];
			if (i > 10){
				if (relFitness == 0)
					relFitness = 1;
				parentTest = r.nextInt(relFitness);
				if (parentTest == 0 && p == parent.A){
					indexA =i;
					p = parent.B;
				}
				else if (parentTest == 0 && p == parent.B){
					indexB = 1;
					crossOver();
					p = parent.A;
				}
			}
			else {
				relFitness =r.nextInt(100);
				if (relFitness < 90)
					crossOver();
			}
			int AorB = r.nextInt(2);
			if (AorB == 0) {
				for (int j = 0; j < CHROMSIZE; j++){
					population[POPSIZE-1][j] = population[indexA][j];
				}
			}
			else {
				for (int j = 0; j < CHROMSIZE; j++){
					population[POPSIZE-1][j] = population[indexA][j];
				}
			}
		}
	}
	private void crossOver(){
		int strandPointerA = r.nextInt(CHROMSIZE);
		int strandPointerB = r.nextInt(CHROMSIZE);
		int[] temp = new int[CHROMSIZE];
		if (strandPointerA < strandPointerB){
			for(int i = strandPointerA; i < strandPointerB; i++){
				temp[i] = population[indexA][i];
				population[indexA][i] = population[indexB][i];
				population[indexB][i] = temp[i];
			}
		}
		if (strandPointerB < strandPointerA){
			for(int i = strandPointerB; i < strandPointerA; i++){
				temp[i] = population[indexA][i];
				population[indexA][i] = population[indexB][i];
				population[indexB][i] = temp[i];
			}
		}	
	}
	public void reproduce(){
		checkCrossOver();
	}
	public void readyForNext(){
		for(int i = 0; i < POPSIZE; i ++){
			population[i][0]= 0;
		}
	}
	public static void main(String[] args){
		ScrewingWithGA g = new ScrewingWithGA();
		System.out.print("Mutation chance (as a percent, max 2 places after the point): ");
		double randFactor = Double.parseDouble(g.s.nextLine());
		g.createArrays();
		g.createIndividuals();
		double total = 0;
		int j = 0;
		while (g.getAverage() < 90){
		g.runHumanInputTrial();
		g.bubbleSort();
		total += g.getAverage();
		j++;
		if (j == 100){
			j = 0;
			total = total/100;
			System.out.println("Average 100 Year Fitness: " + total);
		}
		//System.out.println(g.population[0][0]);
		//System.out.println("Average fitness: " + g.getAverage());
		//System.out.println("Best score this round: " + g.getBest());
		//for (int i = 0; i < g.POPSIZE; i++){
		//	System.out.print(g.population[i][0] + " ");
		//	for (int j = 1; j < g.CHROMSIZE; j++){
		//		System.out.print(g.population[i][j] + "");
		//	}
		//	System.out.println();
		//}
		g.mutate(randFactor);
		g.reproduce();
		g.readyForNext();
		}
	}
}

Thanks, I actually fixed the code, and it has successfully run, finding the answer of a full string of 0s anywhere from 107 to 141 rounds. I will place the new code here for reference, and so anyone else with similar problems can look at the completed code for reference. the problem was in my mutation for loop; I accidentally incremented the rand factor by 100 each time instead of only once, which resulted in every gene ALWAYS mutating, which is why it converged on the average rather than the best answer. thanks for your help, and for the advice.

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
public class ScrewingWithGA {
	private final int POPSIZE = 100;
	private int[][] population;
	private int[] userNumber;
	int indexA = 0, indexB = 0;
	private final byte CHROMSIZE = 127;
	Random r = new Random();
	Scanner s = new Scanner(System.in);
	PrintWriter p;
	public enum parent {
		A, B
	}
	//creates a new 2D Array, which will serve as the population and hold each individuals' "DNA," strings of 0s and 1s. Each # is a separate gene.
	//creates a new array which will store data from the user.
	public void createArrays(){
		population = new int[POPSIZE][CHROMSIZE];
		userNumber = new int[CHROMSIZE];
	}
	//fills the array with pseudo-random 0s and 1s, to create the starting population.
	public void createIndividuals(){
		for (int i = 0; i < POPSIZE; i++) {
			//Starts at 1 to preserve the first int space for the gene's score.
			for(int j = 1; j < CHROMSIZE; j++){
				population[i][j] = r.nextInt(2);
 
			}
		}
	}
	//The mutation method will randomly replace a gene with its opposite; if the gene is a 0 it is replaced with a 1; if it is 1, a 0.
	public void mutate(double randFactor){
		double mutateChecker;
		randFactor = randFactor * 100;
		for (int i = 0; i < POPSIZE; i++) {
			//Again, starts at 1 to preserve the int space for the gene's score.
			for (int j = 1; j < CHROMSIZE; j ++) {
				mutateChecker = r.nextInt(10000);
				if (mutateChecker < randFactor) {
					if (population[i][j] == 0)
						population[i][j] = 1;
					else
						population[i][j] = 0;
 
				}
			}
		}
	}
	public void bubbleSort(){
		int i, j, t=0;
		int[] temp = new int[CHROMSIZE];
			for(i = 0; i < POPSIZE ; i++ ){
				for(j = 1; j < (POPSIZE-i) ; j++){
					if( population[j-1][0] < population[j][0] ){
						t = population[j-1][0];
						for (int k = 1; k < CHROMSIZE; k++){
							temp[k] = population[j-1][k];
						}
						population[j-1][0] = population[j][0];
						for (int k = 1; k < CHROMSIZE; k++){
							population[j-1][k] = population[j][k];
						}
						population[j][0] = t;
						for (int k = 1; k < CHROMSIZE; k++){
							population[j][k] = temp[k];
						}
					}
				}
			}
	}
	public double getAverage(){
		int total = 0;
		for (int i = 0; i < POPSIZE; i++){
			total += population[i][0];
		}
		double average = total / POPSIZE;
		return average;
	}
	public int getBest(){
		return population[0][0];
	}
	public void runHumanInputTrial() {
		//System.out.println("Enter a string of 1s and 0s that is 127 digits long under the next line (use the line as reference).");
		//System.out.println("--------------------------------------------------------------------------------------------------------------------------------");
		//String userEntered = s.nextLine();
		String userEntered =("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
		for (int i = 1; i < CHROMSIZE; i++){
			userNumber[i] = Integer.parseInt(userEntered.substring(i-1, i));
		}
		for (int i = 0; i < POPSIZE; i++){
			for (int j = 1; j < CHROMSIZE; j++){
				if (userNumber[j] == population[i][j]){
					population[i][0]++;
				}
			}
		}
	}
	private void checkCrossOver(){
		int highScore = population[0][0];
		int relFitness, parentTest = 0;
		parent p = parent.A;
		for (int i = 10; i < POPSIZE; i++){
			relFitness = highScore - population[i][0];
			if (i > 10){
				if (relFitness == 0)
					relFitness = 1;
				parentTest = r.nextInt(relFitness);
				if (parentTest == 0 && p == parent.A){
					indexA =i;
					p = parent.B;
				}
				else if (parentTest == 0 && p == parent.B){
					indexB = 1;
					crossOver();
					p = parent.A;
				}
			}
			else {
				for (i = 10; i < 20; i+=2){
					relFitness =r.nextInt(100);
					indexA = i;
					indexB = i +1;
				if (relFitness < 90)
					crossOver();
				}
			}
		}
	}
	private void crossOver(){
		int strandPointerA = r.nextInt(CHROMSIZE);
		int strandPointerB = r.nextInt(CHROMSIZE);
		int[] temp = new int[CHROMSIZE];
		if (strandPointerA < strandPointerB){
			for(int i = strandPointerA; i < strandPointerB; i++){
				temp[i] = population[indexA][i];
				population[indexA][i] = population[indexB][i];
				population[indexB][i] = temp[i];
			}
		}
		if (strandPointerB < strandPointerA){
			for(int i = strandPointerB; i < strandPointerA; i++){
				temp[i] = population[indexA][i];
				population[indexA][i] = population[indexB][i];
				population[indexB][i] = temp[i];
			}
		}	
	}
	public void reproduce(){
		checkCrossOver();
		for (int i = 0; i < 10; i ++){
			for (int j = 0; j < CHROMSIZE; j ++){
			population[POPSIZE - 1 - i][j] = population[i][j];
			}
		}
	}
	public void readyForNext(){
		for(int i = 0; i < POPSIZE; i ++){
			population[i][0]= 0;
		}
	}
	public static void main(String[] args){
		ScrewingWithGA g = new ScrewingWithGA();
		try {
		g.p = new PrintWriter(new File("Data"));
		}
		catch(IOException e){
		}
		System.out.print("Mutation chance (as a percent, max 2 places after the point): ");
		double randFactor = Double.parseDouble(g.s.nextLine());
		g.createArrays();
		g.createIndividuals();
		double h = 0;
		int y = 0;
		while (h < 126){
			y++;
			g.runHumanInputTrial();
			g.bubbleSort();
			for (int i = 0; i < g.POPSIZE; i++){
				g.p.print(g.population[i][0] + " ");
				for (int j = 1; j < g.CHROMSIZE; j++){
					g.p.print(g.population[i][j] + "");
				}
				g.p.println();
			}
			h = g.getBest();
			System.out.println("Round: " + y);
			System.out.println("Average fitness: " + g.getAverage());
			System.out.println("Best score this round: " + h);
			g.mutate(randFactor);
			g.reproduce();
			g.readyForNext();
		}
		g.p.close();
	}