Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Help with a simple Genetic Algorithm

  1. #1
    Junior Member
    Join Date
    Dec 2012
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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();
    		}
    	}
    }


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: Help with a simple Genetic Algorithm

    This is a fairly complicated piece of code to have others debug. You might not like this answer, but the best advice I can give you is to make this much simpler. It seems almost like you wrote the whole program before testing the individual pieces, and now that they don't seem to be working all together, you aren't quite sure how to figure out what's going wrong.

    That's a common problem, and it's why people recommend incremental development: implement one small piece at a time, then test that piece by itself. Only when you have each piece working by itself should you think about combining them.

    You've got a lot of code here, and your choices are to either try to debug it (using a debugger, or print statement, or a piece of paper and a pencil) or to try to work your way from the ground up. I'd actually recommend starting a new project, pasting in small bits of this as you go. That will help you locate the bad logic or cause of the behavior.

    As you go, try implementing a simpler GA with more basic mutation and crossover, or even just a simple evolutionary algorithm which you can convert to a GA once you get it working.

    Much luck. It seems like you're on the right track, you just have to scale back and test things as you go.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Junior Member
    Join Date
    Dec 2012
    Posts
    3
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Help with a simple Genetic Algorithm

    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();
    	}

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default Re: Help with a simple Genetic Algorithm

    That makes a lot of sense. I figured it was a little tiny bug that was hard to find by looking at the whole thing.

    Nice work on the GA, pretty cool. And thanks for posting the updated code.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. The Following User Says Thank You to KevinWorkman For This Useful Post:

    JMeacham (December 13th, 2012)

Similar Threads

  1. Finding Chromatic Number of a Simple Graph w/ Brute Force Algorithm
    By thecrazytaco in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 15th, 2011, 09:27 PM
  2. Simple Hill Climbing algorithm?
    By RED_ in forum Algorithms & Recursion
    Replies: 1
    Last Post: April 26th, 2011, 06:36 AM
  3. urgent simple help for a very simple program
    By albukhari87 in forum Java Applets
    Replies: 4
    Last Post: June 5th, 2010, 03:43 PM
  4. Genetic algorithm
    By rpsaranya in forum Algorithms & Recursion
    Replies: 2
    Last Post: March 5th, 2010, 11:00 PM
  5. not so simple, simple swing question box
    By wolfgar in forum AWT / Java Swing
    Replies: 2
    Last Post: November 20th, 2009, 03:47 AM