Algoritmi genetici

Algoritmi genetici

Conceptul de viata artificiala inglobeaza fenomene de baza ce au elemente comune cu agentii vietii biologice, cum ar fi reproducerea, evolutia, adaptarea, autoorganizarea, parazitismul, cooperarea si competitia. Modelul natural al evolutiei a fost propus in deceniul cinci pentru optimizarea unor procese. Dupa 1960, prin analize teoretice si experimentari pe calculator s-au obtinut scheme evolutioniste, unele radical imbunatatite fata de cele biologice, care trateaza functiile neliniare ca genotipuri supuse efectelor mutatiilor, imperecherilor si selectiei. Dupa ce a investigat matematic adaptarea, J.H. Holland dezvolta la mijlocul anilor '60 algoritmii genetici (GA - genetic algorithms), tehnici de optimizare care simuleaza evolutia naturala a speciilor. Ulterior, pe baza lor au fost dezvoltate in paralel strategiile de evolutie si programarea evolutionista, care opereaza cu reprezentari vectoriale ale codificarii genelor biologice. In anii '70, Holland extinde utilizarea GA, obtinand ca rezultat sistemele de clasificare. In fine, J. R. Koza introduce in anii '80 conceptul de programare genetica.

Algoritmii genetici sunt proceduri de cautare si optimizare bazate pe mecanismele geneticii si ale selectiei naturale. Ei combina supravietuirea artificiala a unei populatii cu aplicarea unor operatori genetici abstracti, obtinand-se un mecanism robust si eficient. Fata de tehnicile de optimizare conventionale, GA au unele particularitati distincte. Ei apeleaza la metode de cautare "oarba", care considera fiecare problema o cutie neagra si o trateaza pornind numai de la cateva ipoteze, utilizeaza populatii de solutii potentiale alcatuite din codificari ale variabilelor sub forma unor siruri generate cu operatori aleatori si exploreaza spatiul de cautare in mai multe puncte simultan, pentru a se evita atingerea unui fals optim local.

Algoritmul genetic Holland transforma o populatie initiala de obiecte matematice intr-una noua, utilizand operatiile reproducerii proportionale darwiniene, operatiile genetice de recombinarea sexuala si mici modificari efectuate prin mutatii aleatoare. Corespondenta terminologica uzual folosita in aceasta echivalenta este: cromozom-sir binar, gena-unitate binara, alela (modificare a unei gene)-valoare binara. Algoritmul are cinci componente: o reprezentarea genetica a potentialului de solutii al problemei, calea pentru crearea unei populatii initiale de indivizi solutie, functia de evaluare, operatorii care  modifica compozitia populatiei si valorile initiale pentru diferiti parametri (dimensiunea populatiei, probabilitatea de aplicare a operatorilor, criteriul de oprire, etc.).

Populatia de solutii in care algoritmul Holland executa o cautare multidirectionala la un moment dat este numita generatie. Din fiecare generatie, solutiile "bune" se reproduc, iar cele "slabe" dispar. Evaluarea calitatii unor solutii este efectuata de catre o functie obiectiv (de adecvanta sau de sanatate). Populatiile de solutii se modifica sub influenta unor operatorii genetici: selectia, incrucisarea, mutatia.

Selectia este un proces de alegere, pe baza unui criteriu de supravietuire, a celor mai adecvati (sanatosi) indivizi dintr-o populatie, pentru a forma cu acestia un grup de imperechere (sau o generatie intermediara). Functia de calitate F(x), care selecteaza indivizii, joaca rolul mediului inconjurator si este obtinuta de obicei prin transformarea functiei f(x) ce trebuie optimizata. Selectia proportionala consta in alegerea unor indivizi i a caror valoare de sanatate este F_i. Pentru individul i din generatia t, probabilitatea selectiei este p_i,t = F_i /F_t, unde F_t este media de sanatate a generatiei t. Noua generatie t+1 a populatiei se obtine prin aplicarea celorlalti doi operatori asupra setului intermediar selectat. Structura unui GA elementar este urmatoarea:

Procedure genetic - algoritm

begin

t=0

initializeaza P(t) (se creeaza o populatie aleatoare P(t));

evalueaza P(t) (calculeaza functia obiectiv pentru fiecare membru al lui P(t);

pana cand (conditie de non - terminare) executa

begin

t = t+1;

selecteaza P(t) din P(t-1);

recombina P(t);

evalueaza P(t) (evaluarea unei noi generatii);

end

end

Cea mai simpla metoda de incrucisare este cea binara (sau intr-un punct), constand dintr-o procedura in trei pasi:

1.Din populatia intermediara sunt alesi doi indivizi, numiti parinti;

2.Ambii cromozomi ai parintilor sunt despartiti in subcromozomi cu lungimi egale, drept si stang, pozitia de rupere putand fi oarecare (fiind aleasa aleator);

3.Fiecare nou fiu are subcromozomul stang de la un parinte si cel drept de la celalalt.

Generalizand, incrucisarea in m puncte divide cromozomii celor doi parinti prin m puncte aleatoare, iar fiii rezulta prin schimbarea alternativa a subgrupelor rezultate. Incrucisarea uniforma utilizeaza o masca pentru comutarea intre parinti a unor subcromozomi cu aceeasi lungime. O pozitie 1 in masca indica faptul ca respectivul bit va fi schimbat.

Operatorul de mutatie se aplica dupa incrucisare, cu scopul de a creste variabilitatea populatiei. Fiecare pozitie a fiecarui cromozom din noua populatie poate suferi o schimbare aleatoare cu o probabilitate egala cu rata de mutatie, care, pe parcursul procesului de calcul, este uzual constanta. Mutatiile binare corespund la comutarea bitului ales din 0 in 1 sau din 1 in 0. Pot fi folosite si tehnici mai sofisticate, cum ar fi mutatia adaptiva, duplicarea, inversiunea, etc.

O problema cheie in practica GA o constituie reprezentarea solutiilor. Cea mai raspandita metoda este astazi utilizarea sirurilor de caractere de lungime fixa (Holland), insa au fost propuse si alte solutii, mai sofisticate. Astfel, algoritmii messy utilizeaza siruri de lungime variabila, iar programarea genetica creste si mai mult complexitatea structurilor de reprezentare.

Dimensiunea populatiei afecteaza atat eficienta cat si performanta finala a algoritmului, pentru ca valori reduse sau prea mari ale acesteia duc la solutii suboptimale sau la o slaba convergenta. Cea mai utilizata metoda pentru creerea populatiei initiale este cea aleatoare. Totusi, daca se pot exploata anumite cunostinte initiale specifice problemei, este posibila si o alegere euristica.

Rata incrucisarilor (adica frecventa de aplicare a acestora) trebuie aleasa astfel incat sa elimine perpetuarea indivizilor neperformanti, situatie care poate aparea atunci cand aceasta este prea inalta. Convergenta este definita ca acea situatie cand algoritmul genereaza o populatie cu indivizi similari intre ei. Un nivel prea mic al mutatiilor produce convergenta prematura catre un singur individ. Convergenta poate fi accelerata utilizand o rata a mutatiilor variabila in timp. Din pacate, nu exista criterii de oprire unanim acceptate.

Masurarea performantelor GA se face prin trei parametri: performanta on-line, care reprezinta media tuturor functiilor de evaluare, performanta off-line, adica media celor mai bune siruri din fiecare generatie si cel mai bun sir gasit din fiecare generatie, care reprezinta o buna masura a calitatii functiei de optimizare.