Operatorii genetici

Descriem în continuare operatorii genetici folosiţi, de obicei, într-un algoritm genetic.

Operatorul de reproducere

Rolul operatorului de reproducere este de a menţine soluţiile promiţătoare din populaţie şi de a le elimina pe cele mai puţin promiţătoare, păstrând constantă dimensiunea populaţiei. Aceasta se realizează astfel:

• se identifică soluţiile promiţătoare din populaţie;

• se creează mai multe copii ale soluţiilor promiţătoare;

• se elimină soluţiile mai puţin promiţătoare din populaţie astfel încât multiplele copii ale soluţiilor promiţătoare să poată fi plasate în populaţie.

Există mai multe moduri de a realiza acest lucru. Cele mai uzuale metode sunt selecţia proporţională, selecţia prin turnir şi selecţia prin ordonare.Este uşor de observat că soluţiile promiţătoare au mai mult de o copie în populaţia intermediară Operatorul de încrucişare Operatorul de încrucişare este aplicat asupra indivizilor din populaţia intermediară. În exemplul nostru, va fi aplicat asupra reprezentării binare a celor şase elemente pe care le avem în populaţia intermediară. Operatorul de încrucişare acţionează în felul următor: sunt aleşi aleator doi indivizi din populaţia intermediară (care se mai numeşte şi piscină de încrucişare) şi anumite porţiuni din cei doi indivizi sunt interschimbate. Operatorul imită încrucişarea intercromozomială naturală. De regulă, se utilizează operatori de încrucişare de tipul (2, 2), adică doi părinţi dau naştere la doi descendenţi. Încrucişarea realizează un schimb de informaţie între cei doi părinţi. Descendenţii obţinuţi prin încrucişare vor avea caracteristici ale ambilor părinţi.

Încrucişarea cu un punct de tăietură

Fie r lungimea cromozomilor. Un punct de tăietură este un număr întreg k ∈ {1, 2,…, r – 1}. Numărul k indică poziţia din interiorul cromozomului unde secvenţa cromozomială se rupe pentru ca segmentele obţinute să se recombine cu alte segmente provenite de la alţi cromozomi.

Considerăm doi cromozomi: x = x1x2…xkxk+1…xr şi y = y1y2…ykyk+1…yr.În urma recombinării se schimbă între cei doi cromozomi secvenţele aflate în dreapta punctului de tăietură k. Cromozomii fii vor fi: x’ = x1x2…xkyk+1…yr şi y’ = y1y2…ykxk+1…xr.

Trebuie reţinut faptul că încrucişarea nu generează descendenţi aleatori. Deşi este improbabil ca fiecare încrucişare între două soluţii din populaţie să genereze soluţii fii mai promiţătoare decât soluţiile părinte, totuşi în scurt timp devine clar că şansa de a crea soluţii mai promiţătoare este mai mare decât în cazul căutării aleatoare. Din încrucişarea cu un singur punct de tăietură a unei perechi de şiruri binare, se pot crea doar două şiruri pereche diferite care vor avea în componenţă biţi combinaţi din ambii părinţi; soluţiile fiu create sunt, probabil, şiruri cel puţin la fel de promiţătoare. Prin urmare, nu fiecare încrucişare poate crea soluţii la fel de promiţătoare, dar nu vor fi mai puţin promiţătoare decât părinţii. Dacă a fost obţinută o soluţie mai puţin promiţătoare, atunci aceasta nu va mai apărea când se va aplica următorul operator de reproducere şi astfel va avea o viaţă scurtă. Dacă este creată o soluţie mai promiţătoare, atunci este probabil ca ea să aibă mai multe copii la următoarea aplicare a operatorului de reproducere. Pentru a păstra o astfel de selecţie a şirurilor promiţătoare în timpul aplicării operatorului de reproducere, nu toate şirurile din populaţie sunt folosite pentru încrucişare.

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