Tehnici de calcul evoluționist

Tehnici de calcul evoluționist

Abordarea problemelor de cautare si optimizare prin metode imprumutate din teoria selectiei naturale si a geneticii a dus la dezvoltarea unor noi tehnici de calcul, mai mult sau mai putin distincte fata de abordarea prin GA.

Strategiile de evolutie (ES) sunt modele ce reprezinta evolutia naturala cu reproducere asexuata, mutatii si selectie. Ca si algoritmii genetici, ele prelucreaza vectori cu valori codificate, insa utilizeaza preponderent operatori de mutatie. Daca m este numarul parintilor, iar l este numarul de fii ai unei generatii, atunci operarea asupra populatiei de solutii se face prin strategia (l m l-fiii sunt generati de m parinti si toti cei l m indivizi sunt supusi competitiei, supravietuind in noua generatie numai cei mai buni m. Mutatiile sunt generate aleator, utilizand o distributie normala si o rata a deviatiei aleasa corespunzator. Testele numerice recomanda strategia ES (l m) ca fiind eficienta din punct de vedere al convergentei si al rapiditatii.

Procedura ES standard este urmatoarea:

genereaza o populatie initiala de m valori individuale aleatoare;

evalueaza toti indivizii pe baza unei anumite functii de sanatate;

repeat

i.      populatia intermediara =[ ];

ii.    for i = 1 la l do

begin

a.     selecteaza doi indivizi pentru imperechere cu aceeasi probabilitate;

b.     recombina componentele parintilor pentru a obtine valoarea individului-fiu;

c.     efectueaza o mutatie la fiu;

d.     insereaza in final i intr-o populatie intermediara;

end

iii.   evalueaza toti indivizii populatiei intermediare pe baza functiei de sanatate;

iv.   selecteaza cei mai buni m indivizi pentru a forma noua populatie.

until criteriu terminare.

Programarea evolutionista (EP) s-a dezvoltat paralel cu strategiile de evolutie. Problema este reprezentata intr-o modalitate top-down si are solutie unica. Fiecare sir parinte nu poate crea decat un singur fiu, obtinut in special pe baza de mutatii. Programarea evolutionista prezinta mai multe similitudini cu tehnicile ES: ambele opereaza cu populatii de solutii asupra carora se efectueaza mutatii, intreg procesul este controlat cu o functie de adecvanta conforma cu obiectivul optimizarii iar valorile reale ale parametrilor de optimizare se obtin aplicand metode gaussiene de perturbare. Exista insa si diferente notabile: in ES selectia este mai mult determinista pe cand in EP preponderent probabilistica; ES utilizeaza frecvent operatorul de recombinare, pe cand EP nu; ES elimina de obicei parintii unei populatii dupa fiecare generatie, pe cand in EP acest lucru nu este tipic. Un model al procedurii de minimizare standard EP este urmatorul:

Selecteaza o populatie initiala de m solutii x_i (i = 1,m), pe baza unei distributii aleatoare uniforme;

Marcheaza toate solutiile-parinti x_i (i =1,m), care respecta functia aleasa F(x);

Pentru fiecare parinte x_i, creeaza un fiu x_i+m, aplicand o variabila aleatoare gaussiana cu medie zero si varianta pozitiva proportionala lui F(x_i);

Marcheaza toti fii x_i(i = m+1, 2m) care respecta functia F(x). Pentru fiecare x_i (i = 1, 2m) selecteaza aleator c competitori. Prin compararea acestora cu fiecare x_i se determina un punctaj individual;

Selecteaza parintiii urmatoarei generatii: m solutii care au cel mai mare punctaj;

Daca este indeplinit criteriul de oprire, stop. Daca nu, se reia pasul 3.

Programarea genetica (GP) a fost introdusa ca o solutie a inteligentei artificiale la problemele procesarii simbolice, care impun gasirea unor programe de calcul care sa produca la intrari particulare anumite iesiri dorite. Obiectivul programarii genetice este de a cauta in spatiul posibilelor programe de calculator pe acela adecvat rezolvarii unei anumite probleme. Procesul se numeste inductia programului. Multimea de cautare este alcatuita din programe cu intrari si iesiri diverse (o formula, un plan, o procedura de calcul, o strategie de control, un model, un arbore de decizie, o functie de transfer, s.a). Obiectele manipulate in GP sunt reprezentate in maniera algoritmilor genetici, prin siruri de caractere de lungime fixa. Dupa rularea programelor cu diferite tipuri de intrari si evaluarea rezultatelor furnizate, se alege ca produs final unul din ele. Sintetizand, procedura standard a GP este urmatoarea:

Genereaza o populatie initiala de combinatii aleatoare de componente ale programelor de calcul;

Executa iterativ, functie de criteriul de terminare:

a.     ruleaza fiecare program din populatie si acorda o valoare de sanatate, in acord cu modul cum a rezolvat problema;

b.     creeaza o noua populatie de programe, astfel:

b1. Copiaza programele existente in noua populatie;

b2. Creeaza noi programe prin recombinari genetice aleatoare intre parti din doua programe deja existente;

Selecteaza ca solutie cel mai bun program din ultima populatie generata.

Pentru implementare, de obicei este preferat limbajul de programare LISP.

Sistemele de clasificare (CS) sunt mecanisme capabile sa invete, alcatuite dintr-un set de reguli, fiecare din ele executand actiuni particulare in momentul in care piesele de informatie satisfac anumite conditii. Conditiile si actiunile sunt reprezentate prin siruri binare.

Figura III.25. Structura unui sistem de clasificare cu algoritm genetic

Functionarea unui CS este asemanatoare cu cea a unei retele neurale, pentru ca se utilizeaza un model intern instruit corespunzator sa reprezinte mediul inconjurator. Sistemele de clasificare reprezinta solutii atractive pentru implementarea sistemelor inteligente de diagnosticare a defectelor, pentru proiectarea sistemelor mecanice complexe sau pentru dezvoltarea unor noi strategii in teoria jocurilor.