Selecţia

Un rol important în cadrul unui algoritm genetic îl ocupă operatorul de selecţie. Acest operator decide care dintre indivizii unei populaţii vor putea participa la formarea populaţiei următoare. Scopul selecţiei este de a asigura mai multe şanse de reproducere celor mai performanţi indivizi dintr-o populaţie dată.

Prin selecţie se urmăreşte maximizarea performanţei indivizilor.

În continuare vom prezenta succint cele mai importante mecanisme de selecţie.

Selecţia proporţională

În cazul selecţiei proporţionale, probabilitatea de selecţie a unui individ depinde de valoarea performanţei acestuia. Să presupunem că avem o mulţime de cromozomi x1, x2, ÷, xn. Pentru fiecare cromozom xi vom calcula performanţa sa f(xi). Se impune condiţia ca f(xi) ≥ 0. Suma performanţelor tuturor cromozomilor din populaţie va constitui performanţa totală şi o vom nota cu F. Probabilitatea de selecţie pi a cromozomului xi este dată de relaţia:

Selecţia bazată pe ordonare

Această modalitate de selecţie constă în a calcula (pentru fiecare generaţie) valorile funcţiei de fitness şi de a aranja indivizii în ordinea descrescătoare a acestor valori. Se va atribui fiecărui individ i o probabilitate de selecţie pi care depinde de rangul său în şirul stabilit. Probabilităţile depind acum doar de poziţia cromozomului. Cel mai promiţător individ are probabilitatea 1.

Selecţia prin concurs

Selecţia prin concurs sau selecţia turnir se bazează pe compararea directă a c‚te doi cromozomi şi selectarea celui mai performant.

Operaţiile implicate sunt următoarele:

• se aleg în mod aleator doi cromozomi;

• se calculează performanţele cromozomilor selectaţi;

• cromozomul mai performant este selectat (copiat în populaţia intermediară asupra căreia se aplică operatorii genetici).

Alte mecanisme de selecţie

Un alt tip de selecţie este selecţia elitistă.În acest caz, la fiecare generaţie se păstrează cel mai promiţător sau cei mai promiţători indivizi. O altă idee ar fi ca, la fiecare generaţie, să fie înlocuită doar o parte restrânsă a populaţiei

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s