Tipuri de GA

Tipuri de GA

In sunt trecute in revista cateva variante imbunatatite ale algoritmului genetic de baza, creat de Holland .

Algoritmul de cautare adaptiva CHC, propus de Edelman, este o versiune a strategiei de selectie elitista (conservativa), care pastreaza cei mai buni indivizi utilizand ca operator de recombinare o varianta a incrucisarii uniforme. Selectia elitista a populatiei se face prin copierea fiecarui membru al generatiei curente P(t) intr-o populatie intermediara c(t), dupa care se genereaza populatia c'(t) de fii. Noua populatie P(t+1) va rezulta printr-un procedeu de incrucisare intre generatii, selectandu-se din multimea reunita a populatiilor P(t) si c'(t) cele mai bune n structuri, astfel incat cei mai buni indivizi supravietuiesc si in noua generatie, evitandu-se disparitia lor prin mutatii sau incrucisari. Un mecanism impotriva incestului asigura evitarea imperecherii intre indivizi similari. Similitudinea se calculeaza prin distanta Hamming intre potentialii parinti. Algoritmul utilizeaza o varianta a incrucisarii uniforme (UX), numita operator de recombinare HUX. Daca incrucisarea uniforma modifica fiecare bit al parintilor dupa o masca, cu o probabilitate a schimbarii de 0.5, varianta HUX respecta acest principiu, dar schimbarile se fac in asa fel incat distanta Hamming intre parinti si fii sa fie maxima. Pentru ca selectia elitista si mecanismul impotriva incestului asigura evitarea convergentei premature, in etapa de recombinare nu au loc mutatii. Ele se inlocuiesc cu un mecanism de restartare ce consta in randomizarea partiala a populatiei, atunci cand se detecteaza o convergenta slaba.

Algoritmii genetici cu nise se bazeaza pe ideea lui Darwin din teoria speciilor, conform careia mediul inconjurator joaca un rol decisiv in evolutie. O nisa se defineste ca o regiune izolata unde traiesc diferite specii. Legaturile dintre speciile din nise diferite sunt mult mai slabe decat cele din interiorul nisei. In contextul GA, o nisa va corespunde cu diferite subpopulatii formate prin divizarea populatiei globale. Cea mai cunoscuta schema de nisare este partajarea prin potrivire (fitness sharing), in care subpopulatiile se desemneaza pe baza similitudinilor intre indivizi, masurata prin distanta Hamming.

Algoritmii genetici messy (mGA), propusi de Goldberg, recodifica sirurile care descriu indivizii unei populatii prin operatori de reordonare. Algoritmii mGA au particularitati distincte. Variabilele se reprezinta prin siruri de lungimi variabile, tehnica ce se numeste codificarea dezordonata (messy). Spre exemplu, daca utilizam notatia LISP (11)(20)(31)(41) pentru un sir de patru biti 1011, putem crea sirurile (11)(20)(31)(41)(21)(30) - supraspecificat, sau (11)(31) - subspecificat. Decodificarea sirurilor subspecificate este totusi o problema delicata. Schemele propuse, de tip sir partial-evolutie partiala (PSPE) limiteaza gama problemelor rezolvabile cu GA. Pentru depasirea acestor dificultati, se utilizeaza tipare competitive, care sunt niste "sabloane" optimale, introduse in locul bitilor lipsa din sirurile subspecificate.

Pentru ca sirurile au lungimi variabile, nu mai poate fi aplicat operatorul de incrucisare, el fiind inlocuit de doi operatori messy: taietura si imbinarea. Operatorul de taiere da probabilitatea individuala de taiere p_t = (l - 1)p_k, unde p_k este o probabilitate generala specificata si l - lungimea sirului. Pentru eventuale mutatii se utilizeaza un operator de tip alelic, care schimba cu o probabilitate fixata p_m valorile bitilor din 0 in 1 si invers. Procesul evolutionist este divizat intr-o faza primordiala si una de juxtapunere. In prima faza, populatia este initializata prin predefinirea unor componente - numite blocuri de constructie - din care vor fi alcatuite sirurile, prin combinari aleatoare. Proportia de blocuri "bune" este imbunatatita, selectand indivizii care le contin. In acest fel se obtin numai siruri cu combinatii optimale sau suboptimale. In faza de juxtapunere, se aplica procedurile obisnuite de evolutie ale GA.

Algoritmii genetici cu restrictii pot rezolva probleme de cautare sau optimizare cu restrictii de tipul:

Sa se optimizeze f(x), cu x = (x₁ ,x₂,..,x_n), tinand seama de :

- restrictii de domeniu: , i = 1 , 2,., n;

- egalitati: A x = B, unde A =(d_ij), B= ( b₁,.,b_m), i = 1,..,m; j= 1,.,n;

- inegalitati: C x D, unde C = (c_ij ), D = (d_j,..,d_j-m ), i = 1,..,q-m; j= 1,..,n.

Restrictiile au doua posibile influente asupra modului de lucru al GA: spatiul de cautare este limitat si pot fi gasite solutii care incalca restrictiile. Au fost propuse mai multe tipuri de algoritmi genetici cu restrictii.

Algoritmul cu functii de penalizare rezolva problema fara restrictii, aplicand o penalitate ponderata - ce actioneaza asupra solutiilor care ar putea viola restrictiile - printr-o functie de selectie de forma:

F(x₁ ,., x_n ) = f(x₁,.,x_n )+, unde q este numarul restrictiilor, d este coeficientul de penalitate, W_i este penalitatea relativa la restrictia i, iar e indica oeratiile de minimizare sau maximizare. Nu exista deocamdata o metoda general acceptata pentru construirea functiei de penalitate. Algoritmii cu decodoare utilizeaza modele speciale de reprezentare, numite decodoare, care garanteaza cu o anumita probabilitate o generatie de solutii fezabile. Algoritmii de reparatie detecteaza solutiile inadmisibile. Pentru ca maresc mult timpul de calcul, se pare ca ei nu au insa viitor. Algoritmii cu operatori si structuri de date specializate sunt constructii experimentale care inglobeaza restrictiile in chiar structura populatiei de solutii, nu utilizeaza operatori specifici si nu au inca o fundamentare teoretica riguroasa. Sistemul genocop lucreaza in doua etape. Mai intai se elimina egalitatile prezente in setul de restrictii, toate variabilele independente fiind exprimate in functie de alte variabile, sub forma unui set de inegalitati liniare care formeaza un spatiu convex. In etapa a doua se utilizeaza operatori speciali, care nu produc descendenti in afara spatiului solutiilor impus de restrictii, cum ar fi incrucisarea aritmetica, definita ca o combinatie liniara a doi vectori parinti x₁ si x₂ ,care permite obtinerea unor fii de forma x'₁ = ax₁ +(1-a)x₂ sau x'₂ = (1-a)x₁+ax₂, unde aI

Algoritmii genetici paraleli sunt combinatii ale unor GA secventiali clasici, implementate pe masini de calcul multiprocesor. Pentru ca ei divid o unica populatie in mai multe subpopulatii si executa in paralel evaluarile functiei de sanatate, incrucisarile si a mutatiile, acesti algoritmi se apropie mai mult de procesul evolutiei naturale a speciilor. Algoritmii paraleli pot fi clasificati dupa gradul de fragmentare al populatiilor distribuite si functie de operatorii genetici ce sunt aplicati. Astfel, algoritmul cu mica fragmentare, cunoscut si sub numele de model insular asigneaza fiecarui procesor cate o subpopulatie. Procesoarele schimba sirurile intre ele, pe baza unor mecanisme similare celor naturale, cum ar fi migratia intre insule. Algoritmii cu mare fragmentare, denumiti si celulari, reprezinta o subclasa a automatului celular. Fiecarui procesor i se aloca un singur sir. Reproducerea este limitata la indivizi apropiati. Intre procesoare se stabileste o topologie de conexiuni si o schema de inlocuire a sirurilor. Spre exemplu, daca sirul traieste intr-un spatiu bidimensional, incrucisarea se va executa cu cel mai bun "vecin" dintre cei patru posibili (stanga, dreapta, sus, jos), iar "fiul" inlocuieste individul original (daca este mai "sanatos").