Curs Algoritmi si programare. ALGORITMI GENETICI

Algoritmii genetici fac parte din categoria algoritmilor euristici, ei aplicandu-se cu succes in cazul problemelor ce nu admit algoritmi in timp polinomial. Algoritmii genetici, dupa cum sugereaza si numele, sunt inspirati din natura, mai precis din felul in care prin recombinari genetice se imbunatateste o specie.

Ideea algoritmilor genetici este de a reprezenta solutiile posibile ale problemei sub forma unor cromozomi, si de a lucra la fiecare pas cu un numar fix de cromozomi, care formeaza o populatie. In algoritmul de mai sus, P este o populatie de cromozomi care reprezinta solutia problemei gasita la pasul respectiv, iar P' este o populatie intermediara, generata din P prin metode specifice geneticii (incrucisari intre cromozomi si mutatii spontane). Astfel, se incearca imbunatatirea populatiei de cromozomi in limita timpului disponibil, in sensul apropierii cat mai mult de solutia optima.