Programare evolutivă și algoritmi genetici

Introducere

Ideea de a aplica principiile darwiniste ale evolutiei in rezolvarea automata a problemelor (Problem Solving - PS) dateaza din anii 1940, inaintea aparitiei calculatoarelor electronice. In 1948 Turing propunea o tehnica de rezolvare a problemelor numita cautare genetica sau evolutiva. In anii 1960 Fogel, Qwens si Walsh introduceau conceptul de programare evolutiva (sau evolutionista), in timp ce Holland dezvolta algoritmii genetici. In aceeasi perioada, Rechenberg si Schwefel introduceau strategiile evolutive (evolutioniste) ca modalitati alternative de rezolvare automata a problemelor. In anii 1990, Koza dezvolta o noua tehnica de cautare in spatiul solutiilor, programarea genetica. In terminologia actuala, intregul spectru de metode de rezolvare automata de inspiratie darwinista este desemnat prin termenul de calcul evolutiv (evolutionist) si include subdomeniile: programare evolutiva, strategii evolutive, algoritmi genetici si programare genetica.

Calculul evolutiv este un domeniu al informaticii inspirat din procesul evolutiei naturale; ideea care sta la baza calculului evolutiv este conexiunea evolutie naturala - tehnica de rezolvare a problemelor de tip experiment-eroare (sau generare-testare). Cu alte cuvinte, intr-un mediu dat, indivizii constituiti intr-o populatie intra in competitie pentru a supravietui si a se reproduce. Abilitatea indivizilor de a-si atinge aceste scopuri in mediul in care traiesc este strict corelata cu sansele lor de supravietuire si multiplicare si determina evolutia in timp a populatiei. In contextul modalitatii de rezolvare a problemelor de tip generare-testare stochastice, populatia este modelata ca o colectie de elemente candidat la solutie. Calitatea candidatilor la solutie, definita in termenii gradului in care fiecare element rezolva problema, determina sansa lor de a fi mentinuti si utilizati pentru construirea unor noi candidati.

Suportul de natura biologica al calculului evolutiv

Teoria evolutionista a lui Darwin ofera o explicatie a diversitatii biologice si a mecanismului care sta la baza acesteia. In centrul interpretarii macroscopice a evolutiei este plasata selectia naturala. Considerand un mediu care poate sustine un numar limitat de indivizi si instinctul primar al fiecarui individ de a se reproduce, procesul de selectie este esential si inevitabil in controlul dimensiunii populatiei. Selectia naturala favorizeaza indivizii cei mai competitivi in insusirea resurselor, adica acei indivizi care sunt cel mai bine adaptati conditiilor de mediu. Fenomenul este cunoscut drept supravietuirea celor mai bine adaptati/ potriviti (survival of the fittest).

Teoria evolutiei are ca principii fundamentale selectia bazata pe competitie si variatiile de fenotip in randul membrilor populatiei. Fenotipul este ansamblul de insusiri si caractere care se manifesta in mod vizibil la un individ si care este determinat pe baza ereditara si de conditiile de mediu (DEX). Caracteristicile fenotipului unui individ determina gradul lui de adaptabilitate la conditiile de mediu (fitness). Fiecare individ reprezinta o combinatie unica de caracteristici ale fenotipului si este evaluat de conditiile de mediu. Daca evaluarea este favorabila, atunci fenotipul individului este propagat spre urmasi (progenituri), altfel caracteristicile fenotipului dispar si individul moare fara a se putea reproduce. Viziunea lui Darwin despre evolutie este aceea ca, in procesul trecerii de la o generatie la alta prin reproducere, apar mutatii (variatii) mici, aleatoare, in caracteristicile fenotipului. Ca rezultat al acestor variatii, apar si sunt evaluate noi combinatii de caracteristici ale fenotipului. Cele mai bune dintre ele supravietuiesc si se reproduc si in acest mod evolutia conduce la progres.

Modelul primar poate fi deci rezumat dupa cum urmeaza. O populatie este formata dintr-un numar de indivizi, priviti ca unitati de selectie; succesul fiecarui individ in incercarea de a se reproduce depinde de cat de bine este adaptat conditiilor de mediu comparativ cu restul indivizilor. Pe parcursul reproducerii celor mai buni (bine adaptati la mediu) indivizi, apar mutatii ocazionale, care genereaza noi indivizi, ce vor fi ulterior evaluati. In consecinta, pe masura ce timpul trece, se produc schimbari in structura populatiei, cu alte cuvinte populatia reprezinta o unitate a evolutiei. Intregul proces poate fi asimilat din punct de vedere intuitiv cu modelul unui peisaj adaptiv (dinamic) (respectiv o suprafata adaptive) in spatiul 3D (0-x-y-z). Fiecare punct p(x,y,z) al suprafetei este asimilat unui individ, unde in planul x-y este figurata combinatia de caracteristici ale fenotipului individului, iar altitudinea lui p (valoarea lui pe axa 0z) corespunde nivelului de adaptabilitate (fitness) a individului reprezentat de p. In acest context, evolutia este procesul de "avans" al populatiei spre zone aflate la o altitudine mai mare, acest avans fiind realizat pe baza mutatiilor si selectiei naturale. Este obtinuta astfel legatura cu conceptul de probleme multimodale, adica probleme in care exista o multime de puncte de optim local (superioare tuturor solutiilor din vecinatatea lor), cel mai bun element al multimii fiind optimul global. O problema in care exista un singur optim local este numita unimodala.

Legatura dintre procesul evolutiei si un proces de optimizare este pe cat de directa, pe atat de inselatoare, pentru ca evolutia nu presupune intotdeauna cresterea globala a calitatii populatiei (in termenii functiei de fitness). Deoarece, la fiecare epoca, populatia este finita si operatorii de selectie si mutatie includ componente aleatoare, poate fi constatata o inactivitate genetica, manifestata fie prin disparitia din populatie a unor indivizi foarte adaptati conditiilor de mediu, fie prin variatia foarte mica sau chiar lipsa de variatie a unor caracteristici ale fenotipului indivizilor din populatie. Unul din efectele posibile este acela al concentrarii indivizilor intr-o zona de adaptabilitate scazuta. Efectul rezultat prin combinarea procesului de selectie cu inactivitatea genetica poate conduce in egala masura la cresterea nivelului de adaptabilitate globala a populatiei, respectiv la descresterea acestuia. In plus, nu exista nici o garantie ca, daca evolutia duce la cresterea calitatii populatiei, nivelul de optim local nu a fost deja atins inaintea unui fenomen de inactivitate genetica. In scopul evitarii "ciclarii" evolutiei populatiei intr-o regiune de optim local, au fost dezvoltate o serie de teorii, una dintre cele mai cunoscute fiind teoria lui Wright conform careia poate fi determinat optimul global in cazul unei suprafete fixe (teorie referita drept shifting balance).

Tipuri de probleme ce pot fi rezolvate pe baza calculului evolutiv

In literatura de specialitate sunt evidentiate doua clase de metode PS de inspiratie biologica: calculul neuronal (neurocomputing), prin intermediul caruia problemele sunt rezolvate imitand modul de functionare (rationament) a (al) creierului uman si procesele de tip evolutiv, problemele fiind rezolvate prin imitarea crearii creierului uman.

In general, un sistem functional de rezolvare automata a problemelor contine trei componente: datele de intrare, datele de iesire si modulul intern care conecteaza primele doua componente. Modalitatea de functionare a modelului permite explicarea modului de functionare a sistemului, in sensul ca, raspunsul sistemului poate fi calculat pentru orice date de intrare specificate. In functie de componentele din sistem cunoscute, pot fi diferentiate urmatoarele tipuri de probleme:

- Probleme de optimizare: sunt cunoscute modelul si datele de iesire dorite (respectiv o descriere a acestora), iar problema este de a determina datele de intrare care corespund rezultatelor dorite. Un exemplu de astfel de problema este cea a comis voiajorului (in care trebuie determinat cea mai scurta sau ieftina ruta care sa lege un numar dat de orase): modelul este cunoscut si corespunde formulei de calcul a lungimii unei rute date, in care lungimea (sau costul) calculata (calculat) este data de iesire. Proprietatea pe care rezultatul trebuie sa o indeplineasca este un criteriu de optim (lungime minima), iar problema este de a determina acea data de intrare, corespunzatoare unei rute, care sa conduca la rezultatul dorit. O problema de optimizare rezolvata cu succes prin calcul evolutiv este generarea orarului in cadrul unei universitati. In cursul unei zile sunt programate in general mii de activitati, restrictiile pe care trebuie sa la indeplineasca o