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