Crossover and Mutation functions for Genetic Algorithm

Question

I'm writing a decryption algorithm using GA with crossover and mutation. My performance is (very) poor, often stagnating early or converging to the incorrect solution. I just want some other people to look at my crossover and mutation methods to see if something is amiss.

Note: crossRate and mutatRate are the crossover and mutation rates respectively and are within the range of [0.00, 1.00]. options is a string of valid genes.

/**
 * method to perform crossover on chromosome
 * @param m - the first parent
 * @param f - the second parent
 * @return - a crossovered chromosome string
 */
private String crossChromosome(String m, String f) {
 StringBuilder chrString = new StringBuilder();
 // if crossover procs
 if (rnd.nextInt(100) < crossRate*100) {
 /**
 * to avoid full reduplication of chromosome
 * set the bound to 2..len-2 otherwise you could
 * get duplication of parent, bypassing crossover entirely
 */ 
 int crossPoint = rnd.nextInt(m.length()-2)+2;
 // when 2P is used, need a second pivot
 int nextCrossPoint = rnd.nextInt(m.length()-crossPoint)+crossPoint;
 boolean condition;
 for (int i = 0; i < f.length(); i++) { // for each gene
 if (crType == 1) {
 /**
 * if one point crossover, find one point
 * in the chromosome where genes before that
 * point are from parent1 and after, from parent2
 */
 condition = (i < crossPoint);
 } else {
 /**
 * if two point, however, find two pivot points
 * and go F,M,F based on the pivot points
 */
 condition = (i < crossPoint || i >= nextCrossPoint);
 }
 if (condition) { 
 chrString.append(f.charAt(i)); 
 } else { 
 chrString.append(m.charAt(i)); 
 }
 }
 } else {
 // if no crossover is happening, random parent is used
 return (rnd.nextInt(2) == 1) ? f : m;
 }
 // return the crossovered chromosome
 return chrString.toString();
}
/**
 * method to mutate a chromosome with random genes
 * @param k - the input chromosome
 * @return - the mutated chromosome
 */
private String mutateChromosome(String k) {
 StringBuilder chrString = new StringBuilder();
 for (int i = 0; i < k.length(); i++) { // for each gene
 // if mutation procs
 if (rnd.nextInt(100) < mutatRate*100) {
 // assign a random gene as mutation
 chrString.append(options.charAt(rnd.nextInt(27)));
 } else {
 // otherwise, use verbatim
 chrString.append(k.charAt(i));
 }
 }
 return chrString.toString();
}

There's option of 1-point and 2-point crossover in there.

Answer 1

I rewrote parts of your code obtaining an equivalent version with the focus of relying on char arrays instead of String objects to obtain a simpler code. I noticed you use the number 100 in both methods you posted, it could be preferrable declaring a const value like below:

private static final int BOUND = 100;

Your method crossChromosome is structured like the code below:

private String crossChromosome(String m, String f) {
 if (rnd.nextInt(100) < crossRate*100) { 
 //here the body
 }
 else { return (rnd.nextInt(2) == 1) ? f : m; }
 return chrString.toString();
}

You can directly put the else body at the beginning of the method with the negation of the condition like the code below:

private String crossChromosome(String m, String f) {
 if (rnd.nextInt(BOUND) >= crossRate * BOUND) {
 return (rnd.nextInt(2) == 1) ? f : m;
 }
 //here the instructions of the body of your case
 return chrString.toString();
}

You can use char arrays instead of String objects avoiding calls of String methods like the code below:

char[] mArr = m.toCharArray();
char[] fArr = f.toCharArray();
final int mLength = mArr.length;
final int fLength = fArr.length;
final int crossPoint = rnd.nextInt(mLength - 2) + 2;
final int nextCrossPoint = rnd.nextInt(mLength - crossPoint) + crossPoint;

You can rewrite the loop of your method like below:

StringBuilder chrString = new StringBuilder();
for (int i = 0; i < fLength; i++) { 
 boolean condition = (i < crossPoint);
 if (crType != 1 && !condition) {
 condition = (i >= nextCrossPoint);
 }
 char ch = condition ? fArr[i] : mArr[i];
 chrString.append(ch);
}
return chrString.toString();

Below the code of your method crossChromosome:

private String crossChromosome(String m, String f) {
 if (rnd.nextInt(BOUND) >= crossRate * BOUND) {
 return (rnd.nextInt(2) == 1) ? f : m;
 }
 char[] mArr = m.toCharArray();
 char[] fArr = f.toCharArray();
 final int mLength = mArr.length;
 final int fLength = fArr.length;
 final int crossPoint = rnd.nextInt(mLength - 2) + 2;
 final int nextCrossPoint = rnd.nextInt(mLength - crossPoint) + crossPoint;
 StringBuilder chrString = new StringBuilder();
 for (int i = 0; i < fLength; i++) { 
 boolean condition = (i < crossPoint);
 if (crType != 1 && !condition) {
 condition = (i >= nextCrossPoint);
 }
 char ch = condition ? fArr[i] : mArr[i];
 chrString.append(ch);
 }
 return chrString.toString();
}

I put condition inside the loop and used the ternary operator. Same suggestions for the method mutateChromosome, below my version:

private String mutateChromosome(String k) {
 final int mutatRateMulBound = mutatRate * BOUND;
 char[] kArr = k.toCharArray();
 StringBuilder chrString = new StringBuilder();
 for (char c : kArr) { 
 boolean condition = rnd.nextInt(BOUND) < mutatRateMulBound;
 char ch = condition ? options.charAt(rnd.nextInt(27)) : c;
 chrString.append(ch);
 }
 return chrString.toString();
}