Elitism in GA

[Abbas Akkasi]

Hi,

How it is possible to consider Elitism in implemented GA in deap?

[EBo]

On May 9 2014 12:25 AM, Abbas Akkasi wrote:
> Hi,
> How it is possible to consider Elitism in implemented GA in deap?

Even thought I use DEAP for a bunch of my work, it has been years since
my primary focus was on evolutionary algorithms. I have never heard the
term "Elitism" in that context. Can you define your terms and explain
the context?

EBo --

[Abbas Akkasi]

Its not strange issue, it means to keep n- best individuals from previous generation for using in next generation, which n refers to elite size. 

[EBo]

Sorry, I had not meant to imply that was a strange question or issue, I
just had not run across the term in relation to GA's before, and was
curious...

Unless I am mistaken, this is at the heart of what GA's do -- evaluate
the fitness of the individuals and preferentially use the most fit
individuals in generating the next population. At each generation you
can sort the fitnesses and choose some arbitrary Elite N. DEAP also
keeps track of the best fit individual (what you might find referred in
relation to the "Hall Of Fame"). So if you look in the code for
references to the Holl of Fame (hof) and exampled on how to evaluate and
choose members of your population, then I think you might find what you
are looking for. Others on the list will likely to be able to direct
you better. I hope that this helps.

As a side note, for my own work I cache all individuals so that I
analyze them off-line, and allow me to restart in the event of a crash
-- my evaluation procedure sometimes take many hours for each
individual, so each run might represent 10's of thousands of CPU hours.
So, DEAP and SCOOP allow you to do some very sophisticated things with
GA's.

Best regards,

EBo --

[Abbas Akkasi]

Thanks for your nice and complete answer. I will check the code. 

[Abbas Akkasi]

Hi again,

I checked the "Hall-Of-Fame" that is  exactly what i wanted. I need to access to n-best individual in each generation, i checked given examples in Deap website including (OneMax short version, OneMax using Numpy) but i couldn't understand how can do that. my job is some thing like oneMax problem the difference is just in evaluation function. So i would really appreciate if you can help me to solve this problem.

All Bests,

Abbas

--
You received this message because you are subscribed to a topic in the Google Groups "deap-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/deap-users/FCPOYmO_enQ/unsubscribe.
To unsubscribe from this group and all its topics, send an email to deap-users+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Francois-Michel De Rainville]

Dear Abbas,

There is two separate concepts to distinguish here, the hall of fame and selection.

The Hall of Fame keeps the best individuals in an isolated archive so that at the end of the evolution you can retreive the best individual that has ever been produce. The individuals put in the Hall of Fame won't ever make it back to the population or produce offspring. The is only a kind of log of the evolution.

Selection is made every generation to select the parental population. Selection (in single objective optimization) is usually made probabilistically with operators such as tournament or roulette wheel. If you wish to have the absolute best individuals you can change it to selBest. However, be sure to use an algorithm that increases the population size such as eaMuPlusLambda or eaMuCommaLambda, otherwise selecting the 'n' best from 'n' won't do much. You can see all selection operators here : http://deap.gel.ulaval.ca/doc/default/api/tools.html#operators. 

Best regards,

François-Michel

You received this message because you are subscribed to the Google Groups "deap-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to deap-users+...@googlegroups.com.

[Abbas Akkasi]

Thanks for your answer. Actually i want to get firstly best individual and its fitness in each generation and secondly n-bests individuals at the end of each iterations.

 Also i want to know what do you mean by invalid_ ind in binary chromosomes? 

All Bests,

Abbas

[EBo]

François-Michel,

Thank you for correcting my comment and putting Abbas on the right
track.

EBo --

[Abbas Akkasi]

Hi , just to make sure about understanding of HOF;  hof is a data structure that keeps n best solution during all generations and its not responsible to carry n-best solution form previous generation to the new population in next generation ! if i understood correctly , so it doesn't implement Elitism. am i right? I am e little bit confused about it, so i would really appreciate if someone can help me.

my definition of elitism is :

"Elitism only means that n bests  of individuals are guaranteed a place in the next generation - generally without undergoing mutation. They should still be able to be selected as parents, in addition to being brought forward themselves." 

Bests,

Abbas

[EBo]

That was my understanding of François-Michel's comment. You will need
to then grab the fitnesses from the evaluations, sort them, and choose.
You should be able to do this in the function/method which generates the
next generation.

Hope that helps.

EBo --

On May 19 2014 4:46 AM, Abbas Akkasi wrote:
> Hi , just to make sure about understanding of HOF; hof is a data
> structure
> that keeps n best solution during all generations and its not
> responsible
> to carry n-best solution form previous generation to the new
> population in
> next generation ! if i understood correctly , so it doesn't implement
> Elitism. am i right? I am e little bit confused about it, so i would
> really
> appreciate if someone can help me.
> my definition of elitism is :
>

> *"Elitism only means that n bests of individuals are guaranteed a

> place in
> the next generation - generally without undergoing mutation. They
> should
> still be able to be selected as parents, in addition to being brought

> forward themselves." *

>> >> deap-users+...@googlegroups.com <javascript:>.

>> >> For more options, visit https://groups.google.com/d/optout.
>> >>
>> >>
>> >> --
>> >> You received this message because you are subscribed to the
>> Google
>> >> Groups "deap-users" group.
>> >> To unsubscribe from this group and stop receiving emails from it,

>> >> send an email to deap-users+...@googlegroups.com <javascript:>.

[François-Michel De Rainville]

Exactly, elitism is accomplished by the selection method. The selection takes the best n individual from the previous generation to the next.

Depending on what algorithm you use : eaSimple, eaMuCommaLambda or eaMuPlusLambda, you should use different type of selection.

eaSimple requires a selection method that can select multiple times the same individual (probabilistic elitism) such as the tournament selection or the roulette wheel selection (or else you won't have any selection, selecting n from n without replacement keeps the same population)

eaMuPlusLambda increases the population size by lambda individuals and reduces it to mu on each generation so you can use any selection such as best or random or nsga2 (multi-objective)

eaMuCommaLambda is little a bit of both, it completely forget about the last generation individuals and only select among the offspring. If mu = lambda you have to use a probabilistinc selection for the same reason as in eaSimple, if lamda > mu you can use any selection type.

For more informations, eaSimple is mentionned in algorithm 1.1 of Poly et al. [1] and eaMuPlus/CommaLambda is mentionned in Beyer and Schwefel [2].

[1] Riccardo Poli , William B. Langdon , Nicholas Freitag McPhee, A Field Guide to Genetic Programming, Lulu Enterprises, UK Ltd, 2008

[2] Beyer, H. G., & Schwefel, H. P. (2002). Evolution strategies–A comprehensive introduction. Natural computing, 1(1), 3-52.

To unsubscribe from this group and stop receiving emails from it, send an email to deap-users+unsubscribe@googlegroups.com.