2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.