1
\$\begingroup\$

I am working on a genetic algorithm using the following code. The variable best in generateNewPopulation stores the best chromosomes from the previous generation and adds it without modification to the new generation. The problem is that if I allow crossover, the "best" changes it value to the best of the current generation.It prints different values of best just before and after crossover method. The code works fine without crossover, considering only mutation.

 Random rand = new Random();
 int rand1,rand2,var;
 int numRuns=0;
 ArrayList<Pair> pop = new ArrayList<Pair>();
 ArrayList<Pair> popClone = new ArrayList<Pair>();
 boolean didRun=false;


  //Initialize population 

   public void genPop (){
   if(!didRun){

  for(int j=0; j<12;j++){  
   StringBuffer x1 = new StringBuffer();
   StringBuffer x2 = new StringBuffer();

 for (int i=0; i<10;i++){  
  rand1 = rand.nextInt(4)%2;
  rand2 = rand.nextInt(4)%2;
  x1.append(rand1);
  x2.append(rand2);
}  
   Pair p = new Pair(x1,x2);
    pop.add(p);
    }      

    System.out.println("Initial Population is ");

        for(int i=0; i<pop.size();i++){
        Pair b = pop.get(i);
        System.out.print(b.getX() + " " + b.getY() + " fitness value is " + decodedVal(b));
        System.out.println();      
        }
        didRun=true;
       Pair best = getMax(pop);
        System.out.println("best chromosome is " + best.getX() + " " + best.getY() + " fitness " + decodedVal(best) );
        System.out.println("Average fitness is " + getAverage(pop) + "\n");
   }
    generateNewPopulation(); 

}


//For creating successive generations


public void generateNewPopulation(){
    numRuns++;
    popClone.clear();
    Pair best = getMax(pop);
    popClone.add(0,best);
    popClone.addAll(rouletteWheel(pop)); 


    ArrayList<Pair> Clone = new ArrayList<Pair>(popClone); 

    popClone = crossover(popClone);  //Crossover of strings

    //Mutation of strings

    for(int k=0; k<6; k++){                 
        int randN = rand.nextInt(8)+1;
        if(checkMutate()){
            popClone.remove(randN);
            popClone.add(mutate(Clone.get(randN)));  
        }
    } 

    popClone.add(best);
    pop.clear();
    pop.addAll(popClone); 

    System.out.println("New Population Generated : No - " + numRuns );
    for(int i=0; i<pop.size(); i++){
       System.out.print(pop.get(i).getX() + " " + pop.get(i).getY() + "\n");}

    System.out.println("best chromosome is " + getMax(pop).getX() + " " + getMax(pop).getY() + " fitness " + 
        decodedVal(getMax(pop)));
System.out.println("Average fitness is " + getAverage(pop) + "\n");    
}

The roulette wheel selection that enters 11 chromosomes to new generation. Elitism adds one best from previous generation afterwards (which is not happening if I allow crossover).

 public ArrayList<Pair> rouletteWheel (ArrayList<Pair> p){
     ArrayList<Pair> popClone1 = new ArrayList<Pair>();
     double [][] values = new double[p.size()+1][4];
     double sum=0;
     double cumulative=0;
     double rands;
     values[0][0]=0;
     values[0][1]=0;
     values[0][2]=0;

 for(int i=0; i<p.size(); i++){
values[i+1][0] = decodedVal(p.get(i));
sum+= values[i+1][0];
}

for(int i=0; i<p.size(); i++){
values[i+1][1] = (values[i+1][0]/sum);
}

for(int i=0; i<p.size(); i++){
cumulative+= values[i+1][1];
values[i+1][2] = cumulative;
}

label1: for(int i=0; i<(p.size()-2); i++){     
    rands = rand.nextDouble();

for(int j=((values.length)-1); j>=0; j--){
if(values[j][2]<= rands){
    popClone1.add(p.get(j));
    continue label1;
}
else;   
      }  
}
return popClone1;

}

Why is the best value changed after calling crossover? The crossover method isn't taking the chromosome pair at index no 0 still the value is getting altered and is set to the best of current generation.

The method crossover is as follows:

public ArrayList<Pair> crossover(ArrayList<Pair>p ){
    int randNo1=1;
    int randNo2=1;
    for(int j=1; j<5; j++){   

        do{
            randNo1 = rand.nextInt(8)+1;
            randNo2 = rand.nextInt(8)+1;
        } while(randNo1== randNo2); 

        int random = rand.nextInt(8)+1; 
        char swap;

        for(int i=random; i<10; i++){
            swap = p.get(randNo1).getX().charAt(i);
            char y = p.get(randNo2).getX().charAt(i);
            p.get(randNo1).getX().setCharAt(i,y);
            p.get(randNo2).getX().setCharAt(i, swap); 
        }

        for(int i=random; i<10; i++){
            char swap2;
            swap2 = p.get(randNo1).getY().charAt(i);
            char y = p.get(randNo2).getY().charAt(i);
            p.get(randNo1).getY().setCharAt(i, y);
            p.get(randNo2).getY().setCharAt(i, swap2); 
        }   
    }

    return p;
}

This is the mutation method:

 public Pair mutate(Pair p){    

     StringBuffer newParentX = new StringBuffer(10);
     StringBuffer newParentY = new StringBuffer(10);
     StringBuffer x = p.getX();
     StringBuffer y = p.getY();

 for(int i=0; i<10;i++){  
      int randNo = rand.nextInt(2);
     char c = x.charAt(i);
   if(randNo==1){
    if(c=='0')
     newParentX.append('1');
   if(c=='1')
     newParentX.append('0');
   }
  else
     newParentX.append(x.charAt(i));
  }  

  for(int i=0; i<10;i++){  
    int randNo = rand.nextInt(2);
    char c = y.charAt(i);
 if(randNo==1){
 if(c=='0')
    newParentY.append('1');
 if(c=='1')
    newParentY.append('0');
  }
  else
     newParentY.append(y.charAt(i));
   }

     Pair newPair = new Pair(newParentX, newParentY);
     return newPair;

      }

This is getMax(), that returns the best chromosome of the population:

public Pair getMax(ArrayList<Pair>p){       

  int maxIndex=0;
  double fitnessValue;
  double maxValue= decodedVal(p.get(maxIndex));  //decodedVal gets the  fitness value of corresponding chromosome

    for(int i=0; i<p.size(); i++){
    fitnessValue = decodedVal(p.get(i));

    if(fitnessValue > maxValue){
     maxValue=fitnessValue;
      maxIndex=i;
          }  
 else;
     } 

    return p.get(maxIndex);  
   }

This is the problem i am getting in the output.The best chromosome of previous generation is not added to new generation.
New Population Generated : No - 15
0100111011 0110000101
0111001110 0010000101
0111001110 0010000101
0111001110 0010000101
1101110110 0110110010
0111001110 0010000101
0111001110 0010000101
1001001001 0110010000
0111000010 1001111010
0011001001 1111101001
1010011011 0010000101
0100111011 0110000101
best chromosome is 0100111011 0110000101 fitness 0.6773401619818802
Average fitness is 0.4868817692316813

New Population Generated : No - 16
0110011111 0110000101
1001101001 0110010000
0110011111 0110000101
0101001010 0010000101
0110011111 0110000101
0101001010 0010000101
0110011111 0110000101
0110011111 0110000101
0011100100 0001111001
1110011011 0001010100
0111110111 0110011010
0110011111 0110000101
best chromosome is 0101001010 0010000101 fitness 0.6195407585437024
Average fitness is 0.4824919712727356

\$\endgroup\$
  • \$\begingroup\$ Please show full code, not just two methods. For example, what does the getMax() method do? \$\endgroup\$ – Dave May 28 '16 at 21:43
  • \$\begingroup\$ I have posted the entire code now. Hope it helps \$\endgroup\$ – Learning May 29 '16 at 11:45
  • 1
    \$\begingroup\$ "The code works fine without crossover, considering only mutation." does that mean your code does not work as intended? I think this site only reviews code that has the desired functionality. \$\endgroup\$ – I'll add comments tomorrow May 30 '16 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.