Converting an evolutionary algorithm to genetic

0
votes

From what I can tell one of the biggest differences between evolutionary and genetic algorithms is that evolutionary employs a mutate function to generate a new population while a genetic used a crossover function.

I found an evolutionary algorithm that trys to generate a target string through mutations like this:

  private static double newMutateRate(){
    return (((double)perfectFitness - fitness(parent)) / perfectFitness * (1 - minMutateRate));
  }

  private static String mutate(String parent, double rate){
    String retVal = "";
    for(int i = 0;i < parent.length(); i++){
      retVal += (rand.nextDouble() <= rate) ?
        possibilities[rand.nextInt(possibilities.length)]:
        parent.charAt(i);
    }
    return retVal;
  }

I wrote this crossover function to replace the mutation function:

private static String crossOver(String parent)
{
    String newChild = "";
    for(int i = 0;  i < parent.length(); i++)
    {
        if(parent.charAt(i) != target.charAt(i))
            newChild += possibilities[rand.nextInt(possibilities.length)];
        else
            newChild += parent.charAt(i);
    }
    return newChild;
}

Which works great. But I'm wondering if its a valid crossover function. I feel like, from my experience with genetic algorithms, that the crossover function should be generating more random populations than what I have written in other words knowing exactly which bit not to change seems almost like cheating.

3
javaalgorithmgenetic-algorithmevolutionary-algorithm
The assumption in your first paragraph ("that evolutionary employs a mutate function to generate a new population while a genetic used a crossover function") is wrong. The difference is that genetic algorithm are a subtype of evolutionary algorithms that explicitly use "genes" to model an individual's characteristics. Read this Wikipedia section for a comparison of EAs. - Junuxx
@Junuxx this problem is not the most practical problem to be solved by GA but only learning purpose one as u already know the optimal target string which used for calculation of fitness. - Vikram Bhat

3 Answers

1
votes

No, your crossover function does not fit the conventional meaning of the term. Crossover should take genes from two parents. What you have now is more like a mutation function.

Uniform crossover is a common crossover implementation of two genomes where the child gets approximately 50% of the genes of each parent. Here I assume the genome length is fixed.

private String crossover(String parent1, String parent2){

    String child = "";
    for(int i = 0; i < parent1.length(); i++){
        if (rand.nextFloat() >= 0.5){
            child += parent1[i];
        }
        else {
            child += parent2[i];
        }
    }
}
1
votes

I think it is not appropriate to use the target to construct crossover function but you should use two best strings in the current population for crossover.

Here is pseudo code for one such crossover:-

Crossover(String parent1,String parent2) {

 for(i=0;i<parent1.length;i++) {

       if(parent1[i]==target[i]) {
              child[i] = parent1[i]
       }
       else if(parent2[i]==target[i]) {
            child[i] = parent2[i]
       }
 } 

 insert remaining elements into child randomly

}

The above method is called a greedy crossover

0
votes

I agree with Junuxx, I just like to add one thing. It happens that genetic algorithms tend to use crossover operators more than other evolutionary algorithms, but it's not the reproduction operator that makes an algorithm genetic! I found that the Lawnmower example explains it very well (don't worry about the implementation code, just read the explanation):

Lawnmower Problem Solver