Algoritmi Genetici

Algoritmii Genetici sunt strategii de rezolvare a problemelor cu ajutorul computerelor bazate pe teorii evoluţioniste. Soluţiile potenţiale sunt forţate să conlucreze într-un anumit mediu, având ca rezultat soluţiile cele mai bune în timp. Unul din principalele beneficii ale algoritmilor genetici este acela, că pentru a rezolva o anumită problemă este nevoie de o cunoaştere a evoluţiei soluţiilor potenţiale şi nu construirea dinainte a uneia optime. Acest lucru devine evident cu cât complexitatea unei probleme se măreşte, soluţia optimă în acest caz este mult mai greu de determinat, o astfel de abordare fiind mult mai bună. În plus metodele utilizate de algoritmii genetici sunt utilizate şi în rezolvarea problemelor de către oameni.

Un algoritm genetic poate căuta foarte eficient soluţia în spatiul soluţiilor unei probleme date şi ajunge la o soluţie bună folosind o strategie inteligentă de cautare.

Algoritmii genetici reprezintă o modalitate de a căuta, în mod aleator, răspunsuri la probleme curente. Principiul de funcţionare al unui algoritm genetic se bazează pe tendinţa de creştere a performanţei unei populaţii de soluţii candidat, în timp, determinată de competiţia pentru resursele mediului şi propagarea materialului genetic de către cei mai buni indivizi ai populaţiei. Noţiunea cheie a algoritmilor genetici este performanţa indivizilor, determinată de funcţia obiectiv şi de restricţiile problemei.

Se poate spune ca algoritmii genetici sunt proceduri de căutare bazate pe mecanisme naturale de selecţie naturală şi genetică.

Enuntul problemei :

Fie un program alcatuit din 10 actiuni. Se cere accelerarea acestuia la un cost minim, adica duratele cu care cele 10 actiuni pot fi reduse astfel incat costul total al accelerarii sa fie minim, stiind ca accelerarea atrage dupa sine cresteri de cost. Duratele maxime de accelerare ale celor 10 actiuni (d max) si cresterile de cost unitare pricinuite de accelerarea actiunilor (c u) sunt date in tabelul urmator:

Actiune 1 2 3 4 5 6 7 8 9 10

D max (min) 5 4 2 5 7 10 21 3 1 13

C u (u.m./min) 2 3 2 2 4 7 7 5 4 8

Functia cost se va determina cu formula : ∑_(i=1)^10〖di*Cui〗, unde di este durata cu care se accelereaza actiunea i(valoarea genei i).

De exemplu, individual (2 4 0 1 6 8 14 2 0 11) va avea valoarea functiei obiectiv

2*2+4*3+0*2+1*2+6*4+8*7+14*7+2*5+0*4+11*8

Datele de intrare :

Datele de intrare se impart in doua categorii:

Datele de intrare se impart in doua categorii :

Date de intrare specifice problemei :

N care are 2 roluri :

N=numarul de indivizi

N=numarul de actiuni

Parametrii de aplicare a algoritmilor genetici :

- dimensiunea initiala a populatiei (N_init);

- dimensiunea maxima a populatiei (N_max);

- numarul maxim de generatii (Gen_max);

- rata de incrucisare (Rc);

- rata de mutatie (Rm);

1.5. Evaluarea indivizilor

Functia ce va determina performanta este data de functia individ care trebuie maximizata.

In limbajul C, codul aferent acesteia este:

int Fitness(Individ ind)

{

int f=0;

int i,j;

for(i=0;i<n;i++)

for(j=0;j<i;j++)

if (a[ind.cromozom[i]-1][ind.cromozom[j]-1]==1)

f=f+1;

return f;

}

1.6. Operatorii genetici

Selectie

Modelele de selectie cel mai frecvent apelate sunt: ruleta, turneu, elitista si aleatoare.

Pentru problema de fata selectia aleasa este selectia turneu. Aceasta consta in sortarea indivizilor din populatia curenta dupa performanta si se aleg drept parinti cei mai buni indivizi.

Consider dt ca fiind dimensiunea turneului. Aleg la intamplare dt indivizi si cel cu fitness-ul cel mai mare se adauga la populatia selectata si procesul se repeta pana cand vor fi epuizati toti indivizii.

Functia fitness este functia de evaluare a individului (eficienta lui). Aceasta trebuie maximizata si reprezinta numarul de precedente respectate.

Codul specific in limbajul C este:

void SelectieIndivizi(int nr)

{

int i,j,indice,poz,max;

Individ participanti[10];

for(i=0;i<nr;i++)

{

for(j=0;j<dt;j++)

{

poz=random(dimensiune);

participanti[j]=populatie[poz];

}