ALGORITMI GENETICI

Calcul evolutiv

În general, orice sarcină abstractă care trebuie Óndeplinită, poate fi privită ca fiind rezolvarea unei probleme, care, la rândul ei, poate fi percepută ca o căutare în spaţiul soluţiilor potenţiale. Deoarece, de obicei, căutăm cea mai bună soluţie, putem privi acest proces ca fiind unul de optimizare. Pentru spaţii mici, metodele clasice exhaustive sunt suficiente; pentru spaţii mari, pot fi folosite tehnicile speciale ale inteligenţei artificiale. Metodele calculului evolutiv se numără printre aceste tehnici; ele folosesc algoritmi ale căror metode de căutare au ca model câteva fenomene naturale: moştenirea genetică şi lupta pentru supravieţuire. Cele mai cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici, strategiile evolutive, programarea genetică şi programarea evolutivă. Există şi alte sisteme hibride care încorporează diferite proprietăţi ale paradigmelor de mai sus; mai mult, structura oricărui algoritm de calcul evolutiv este, în mare măsură, aceeaşi.

 

procedura algoritm_evolutiv

t ← 0

creare P(t)

evaluare P(t)

cât timp nu condiţia de terminare

t ← t + 1

selectare P(t) din P(t-1)

modificare P(t)

evaluare P(t)

sfârşit cât timp

sfârşit procedura

 

Există unele probleme Ón cazul cărora fitness-ul trebuie să fie minimizat. O nouă populaţie (iteraţia t + 1) se formează prin selectarea mai multor potriviri individuale, aleg‚nd cei mai promiţători indivizi (pasul de selecţie) din populaţia curentă. O parte din membri populaţiei nou formate suferă transformări (pasul de modificare) prin operarea ìgeneticaî a noilor solutii. Vorbim despre o transformare unica e evoluţiei programului.

 

.2. Operatori genetici – calculul evolutiv

Operatorii genetici sunt, de fapt, proceduri care operează asupra elementelor vectorului populaţie. Există doi operatori genetici principali:

• un operator unar mi de transformare numit mutaţie, care creează un nou individ printr-o mică modificare a unui individ ales (mi: S → S);

• un operator mai puternic cj numit Óncrucişare, care creează noi indivizi combin‚nd părţi din doi sau mai mulţi indivizi (cj: S × … × S→S) (de cele mai multe ori se folosesc doi părinţi).

După un anumit număr de generaţii algoritmul converge: se speră că cel mai promiţător individ ajunge la o valoare c‚t mai apropiată de soluţia optimă. Œn ciuda similarităţilor puternice între diferitele tehnici de calcul evolutiv, există şi multe diferenţe.

Acestea sunt date, în principal, de structurile de date folosite pentru a reprezenta un individ şi de ordinea în care se aplică operatorii genetici. De exemplu, cele două linii din algoritmul de mai sus:

selectare P(t) din P(t-1)

modificare P(t)

pot apărea în ordine inversă: (în strategiile evolutive, întâi se modifică populaţia şi apoi este formată o nouă populaţie prin procesul de selecţie, în timp ce într-un algoritm genetic întâi se aplică selecţia, iar apoi intră în acţiune operatorii genetici de transformare).

Există, de asemenea, şi alte diferenţe între metode. Una dintre acestea ar fi cea referitoare la metodele de selecţie care includ:

• selecţia proporţională, unde şansa (probabilitatea) ca un individ să fie selectat este proporţională cu fitness-ul lui;

• metoda rangului, în care toţi indivizii din populaţie sunt sortaţi în funcţie de fitness, iar probabilitatea (şansa) ca ei să fie selectaţi este fixată de întreg procesul de evoluţie

(de exemplu, probabilitatea de selecţie a celui mai promiţător individ este 0.15, a individului următor este 0.14, etc.; cel mai promiţător individ are cea mai mare probabilitate şi suma totală a probabilităţilor indivizilor este1);

• selecţia prin turnir (prin concurs) unde un anumit număr de indivizi (de obicei doi) luptă pentru a fi selectaţi în noua generaţie.

Această competiţie (turnir) este repetată până sunt selectaţi un număr de indivizi egal cu dimensiunea populaţiei. Pentru fiecare dintre aceste categorii de selecţie există şi alte detalii importante.

Câteva exemple sunt:

• selecţia proporţională poate necesita folosirea unor metode de trunchiere;

• există diferite moduri pentru stabilirea probabilităţii în metoda rangului;

• dimensiunea mulţimii alese pentru concurs poate juca un rol semnificativ în metoda selecţiei prin turnir.

 

Trecerea de la o generaţie la alta poate fi efectuată în două variante:

• algoritm generaţional (noua populaţie este formată doar din descendenţi ai vechii generaţii);

• algoritm non-generaţional (în noua populaţie sunt introduşi, de obicei, cei mai promiţători indivizi din cele două populaţii, cea a părinţilor şi cea a descendenţilor).

Este posibil, de asemenea, să creăm puţini (în particular, unul singur) descendenţi, care înlocuiesc c‚ţiva (cei mai puţin promiţători) indivizi. Ca o regulă generală trebuie reţinut faptul că, în majoritatea cazurilor, este de preferat să se utilizeze un model elitist, care păstrează cei mai promiţători indivizi dintr-o generaţie şi îi adaugă automat generaţiei următoare (aceasta înseamnă că, dacă cel mai promiţător individ din generaţia curentă este pierdut datorită selecţiei sau operatorilor genetici, sistemul forţează apariţia lui Óntr-o generaţie următoare). Un astfel de model este foarte folositor pentru rezolvarea multor probleme de optimizare. Totuşi, structurile de date folosite pentru probleme particulare, împreună cu o mulţime de operatori genetici, constituie componenta esenţială a oricărui algoritm evolutiv. Acestea sunt elementele cheie care ne permit să distingem între variatele paradigme ale metodelor evolutive.

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