Algoritmi Genetici

[2] Algoritmii genetici sunt tehnici adaptive de căutare euristică, bazate pe principiile geneticii si le selecţiei naturale, enunţate de Darwin (supravieţuieste cel mai bine adaptat). Mecanismul este similar procesului biologic al evoluţiei. Acest proces posedă o trăsătură prin care numai speciile care se adaptează mai bine la mediu sunt capabile să supravieţuiască si să evolueze peste generaţii, în timp ce acelea mai puţin adaptate nu reusesc să supravieţuiască si cu timpul dispar, ca urmare a selecţiei naturale. Probabilitatea ca specia să supravieţuiască si să evolueze peste generaţii devine cu atât mai mare cu cât gradul de adaptare creste, ceea ce în termeni de optimizare înseamnă că soluţia se apropie de optim. Ca si aplicaţii practice, algoritmii genetici sunt cel mai adesea utilizaţi în rezolvarea problemelor de optimizare, planificare ori căutare. Condiţia esenţială pentru succesul unei aplicaţii cu agenţi inteligenţi este ca problema de rezolvat să nu ceară obţinerea soluţiei optime, ci să fie suficientă si o soluţie apropiată de optim.

[1]Elementele unui algoritm genetic

Un algoritm genetic trebuie sa aiba definite urmatoarle elemente pentru rezolvarea unei problem:

• O reprezentare (genotip) a solutiilor candidat;

• O procedura de initializare (creare) a populatiei initiale de solutii candidat;

• O functie de evaluare (functie fitness) care joaca rolul mediului si care este utilizata pentru a masura calitatea solutiilor in termeni de potrivire/acomodare;

• O schema de selectie (inclocuirea generatiilor);

• Operatorii genetici (mutatia, incrucisarea,…)

• Parametrii numerici.

[3] Algoritmii genetici reprezinta o familie de modele inspirate de teoria evolutiei, adica sunt programe inteligente care sunt capabile de a solution problemele folosind un concept al evolutiei speciilor.Respectiv acesti algoritmi codifica solutiile posibile ale unor problem specific intr-o structura de date de tip cromozom dupa care acestor structure li se aplica operatori de recombinare, pentru a pastra informatia utila.

Ce este un cromozom? Un cromozom nu este nimik altceva decit un vector sau un sir de gene.Pozitia unei gene poarta numele de locusul ei, iar valorile pe car ele poatelua o gena poarta denumirea de allele, care reprezinta multimile finite de numere intregi, interval de numere reale de pe acelasi cromozom, variind de la un locus la altul.

Care este scopul unui algoritm genetic aici? Sarcina lui este de a descoperi cromozomii din ce in ce mai buni, pina la atingerea unei valori a raportului dintre evaluarea asociata unui sir si evaluarea medie a tuturor sirurilor populatie despre care se stie ca este optimala, sau pina cind algoritmul genetic nu mai poate aduce imbunatatiri.

Solutia gasita de algoritmii genetici nu intotdeaua etse cea mai buna dar se afla intr-o vecinatate a solutiei optime.