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!
Code Java:
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();
}
}
}
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.
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. :)
Code Java:
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();
}
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.
