thieu1995 / mealpy

A Collection Of The State-of-the-art Metaheuristic Algorithms In Python (Metaheuristic/Optimizer/Nature-inspired/Biology)
https://mealpy.readthedocs.io
GNU General Public License v3.0
895 stars 186 forks source link

[FEAT]: Can you please add Elitism in GA algorithm? #81

Closed Qiuyi-Hong closed 2 years ago

Qiuyi-Hong commented 2 years ago

Description

Thanks for the useful python library for doing evolutionary algorithms. However, for the GA algorithm, I noticed that there is no Elitism included. Could you please add this feature to the GA algorithm?

Additional Information

No response

thieu1995 commented 2 years ago

Hi @Qiuyi-Hong ,

What do you mean Elitism in GA. Could you send me the pseudo code for that version?

Qiuyi-Hong commented 2 years ago

Hello @thieu1995 ,

Thanks for the reply!

Please see the description. Basically, Elitism is the strategy that keeps the best one or two solutions to the next generation. I would like to know if this strategy has been included in the python library.

Many thanks, Qiuyi

thieu1995 commented 2 years ago

Hi @Qiuyi-Hong ,

Thanks for the link. Currently, the Elitism is not applied in 2 versions of GA. I will add the Elitism of GA in the next version.

Qiuyi-Hong commented 2 years ago

Hello @thieu1995 ,

Many thanks for the update. Please let me know if you need anything to get the job done.

thieu1995 commented 2 years ago

@Qiuyi-Hong,

Indeed, you can clarify this sentence for me. I was reading your sent link. In section 4.1. Tuning Elitism in Evolutionary Algorithms. The author stated that: The worst 50% of individuals in the elite group crossover with non-elite individuals.

So this means we select dad from 50% worst (of the elite group) and mom from non-elite individuals to do the crossover. Or, we place all 50% worst (of the elite) and non-elite groups as pop2, mixed it up. Then we select dad and mom from that pop2 to do crossover?

Qiuyi-Hong commented 2 years ago

Hello @thieu1995 ,

Thanks for letting me know about the problem.

I prefer your first understanding. The reason is that, even though they are the worst 50% of individuals in the elite group, they are still the best 10% of individuals of the entire population in the generation. Therefore, it's better to treat them as dads and do a crossover with other individuals in the non-elite group. If we select the dad and mom following your second understanding, however, there is a high possibility that the worst 50% of individuals in the elite group are not selected to do a crossover, since the size of the entire elite group is small. Therefore, the baby from the crossover may not inherit good genes from the individuals in the elite group.

Please let me know if you have further opinions.

thieu1995 commented 2 years ago

@Qiuyi-Hong ,

Thanks for your comments. I've implemented both cases, you can select using parameter "strategy". I also implemented the elite version for both SingleGA and MultiGA. You can found it here. https://github.com/thieu1995/mealpy/blob/dev/2.5.1/mealpy/evolutionary_based/GA.py#L441

The results will depend on your problem tho. To some problems, the first strategy give better result. To other problems, the second strategy give better result.

Qiuyi-Hong commented 2 years ago

Hi @thieu1995 ,

Many thanks for the implementation. There is another question I would like to ask related to mutation. The "flip" strategy of mutation can be easily implemented with binary inputs. However, how did you implement this strategy with floating point inputs?
Also, please let me know the difference between one-point mutation and multi-point mutation, and why there are no "scramble" and "inversion" strategies in multi-point mutation.

Many thanks, Qiuyi

thieu1995 commented 2 years ago

@Qiuyi-Hong ,

I followed the tutorial from here: https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_mutation.htm

Qiuyi-Hong commented 2 years ago

Hi @thieu1995

Many thanks for your interpretation and the implementation. I appreciate your help.