Search code examples
algorithmgenetic-algorithmevolutionary-algorithm

Elistism in GA: Do I need apply generator operator for that step


I am using elistism to maintain \tau proportion of parent. I am confusing that after copy \tau proportion individual from parent for next generation. Do I need apply generation operator (crossover+mutation) for these individuals. For more detail, I show two algorithm. Which is correct for require "overlap elitism/overlap selection with pair-wise tournament replacement"

Algorithm 1:

P=initial_individual
Fitness_raw=evaluate_raw_fitness(P)
Fitness_Adjust=evaluate_adjust_fitness(Fitness_raw,P) //adjust by Hamming distance
While(t<300)
       P_old=P;
       Tmp_P=Selection_by_Pair_wise(P, Fitness_Adjust)
       Tmp_P=cross_over(Tmp_P)
       P=mutation(tmp_P)
       //Copy 50% top from P_old ---without mutation and crossover
      P=[P_old(1:N/2) P(N/2 N)] 
       Fitness_raw=evaluate_raw_fitness(P)
       Fitness_Adjust=evaluate_adjust_fitness(Fitness_raw,P) //adjust by Hamming distance
End

That means the P after mutation step is construct by original P at ith generation and output of generation operation. Is it right? Algorithm2:

P=initial_individual
Fitness_raw=evaluate_raw_fitness(P)
Fitness_Adjust=evaluate_adjust_fitness(Fitness_raw,P) //adjust by Hamming distance
While(t<300)
       P_old=P;
       Tmp_P=Selection_by_Pair_wise(P, Fitness_Adjust)
       Tmp_P =[P_old(1:N/2) Tmp_P(N/2 N)] 
       Tmp_P=cross_over(Tmp_P)
       P=mutation(tmp_P)
       //Copy 50% top from P_old ---without mutation and crossover
       Fitness_raw=evaluate_raw_fitness(P)
       Fitness_Adjust=evaluate_adjust_fitness(Fitness_raw,P) //adjust by Hamming distance
End

That means it will copy tau=50% top and 50% rest of populations are replaced by pair-wise. After that, we applied cross_over and mutation in the Tmp_P. Note that 50% top is selected by raw_fitness and 50% last is selected by adjust_fitness for both algorithm.


Solution

  • Elitism means taking explicit measures to preserve good individuals from the current generation to the next. As a result, degradation will not happen. Your first algorithm guarantees that the best 50% individuals of the current population are preserved to the next generation. The second algorithm guarantees nothing. As a result, there may be the case that the best individual in the next generation is even worse than the worst individual in the current generation, obvious degradation. To conclude, your first algorithm, not the second, implements elitism.