Algoritmi Genetici

Extras din referat Cum descarc?

Calculul cognitiv denota o familie de metode de rezolvare a problemelor care imita inteligenta "gasita" in natura. Obiectivul comun al acestor metode este de a solutiona situatiile ce au rezistat abordarilor de tip analitic. Din aceasta categorie fac parte retelele neuronale, logica fuzzy, automatele celulare, algoritmii genetici, fractalii, teoria haosului. Fiecare din aceste metode incerca sa "simuleze soft" lumea reala si sa proceseze datele de o maniera "cat mai naturala".[1]
Este binecunoscut faptul ca organismele vii evolueaza de mii de ani, si atunci cand se vorbeste despre evolutie din punct de vedere al biologiei lucrurile sunt bine intelese. Privind in jurul nostru se poate observa ca organismele vii conlucreaza unele cu altele pentru a supravietui. Peste timp prin mutatii si evolutie, organismele s-au adaptat pentru a castiga avantaje in mediul in care traiesc. 
Transmiterea unor caracteristici generatiilor urmatoare prin intermediul genelor reprezinta un mod simplu de supravietuire si in acelasi timp de evolutie. Rezultatele acestei strategii relativ simple sunt imprevizibile.
Algoritmii Genetici sunt strategii de rezolvare a problemelor cu ajutorul computerelor bazate pe teorii evolutioniste. Solutiile potentiale sunt fortate sa conlucreze intr-un anumit mediu, avand ca rezultat solutiile cele mai bune in timp. Unul din principalele beneficii ale algoritmilor genetici este acela ca pentru a rezolva o anumita problema este nevoie de o cunoastere a evolutiei solutiilor potentiale si nu construirea dinainte a uneia optime. Acest lucru devine evident cu cat complexitatea unei probleme se mareste, solutia optima in cazul acest caz este mult mai greu de determinat, o astfel de abordare fiind mult mai buna. In plus metodele utilizate de algoritmii genetici sunt utilizate si in rezolvarea problemelor de catre oameni.[2]
Un algoritm genetic poate cauta foarte eficient solutia in spatiul solutiilor unei probleme date si ajunge la o solutie buna folosind o strategie inteligenta de cautare.
Algoritmii genetici reprezinta o modalitate de a cauta, in mod aleator, raspunsuri la probleme curente.
Se poate spune ca algoritmii genetici sunt proceduri de cautare bazate pe mecanisme naturale de selectie naturala si genetica. Algoritmii genetici au fost dezvoltati de John Holland in 1960 pentru a permite contemporanilor sai sa gaseasca solutii pentru probleme dificile, cum ar fi functiile de optimizare si inteligenta artificiala.
Algoritmi genetici si programare genetica
Organismele vii pot fi privite ca rezolvatoare de probleme si prezinta o versalitate care nu poate fi inca demonstrata de cel mai bun calculator existent (Holland, 1992). Astfel apare evident ca emularea puterii deosebite a evolutiei asa cum are ea loc in lumea animala si ca proiectarea de sisteme artificiale capabile de evolutie si adaptare ar duce la rezultate spectaculoase, un astfel de calculator fiind capabil sa invete sa se programeze singur. Trei decenii de cercetari teoretice si aplicatii practice au aratat ca imitarea procesului de selectie naturala poate duce la programe de calcul foarte robuste si eficiente, desi aceasta imitatie este o simplificare destul de departata de realitatea biologica.
Algoritmii genetici (AG) au fost dezvoltati initial de John Holland in anii '60 ca o forma de tehnica de cautare modelata dupa principiile evolutiei Darwiniste. Astazi, AG reprezinta cel mai popular model evolutionist. In continuare ne propunem sa prezentam pe scurt structura si caracteristicile unui AG simplu (AGS).
Vom incepe cu prezentarea punctelor principale prin care un AG difera de tehnicile conventionale de cautare si optimizare. Acestea sunt:
1. AG sunt "orbi"
Un AG trateaza problema de rezolvat ca pe o "cutie neagra", necesitand foarte putine informatii despre aceasta. Din acest punct de vedere, un AG reprezinta o metoda slaba de cautare. Dar se observa in practica o foarte mare eficienta, putere de rezolvare a problemei, ceea ce este o caracteristica a metodelor puternice de cautare. Deci la acest punct apare un aparent paradox: AG sunt metode slabe de cautare cu eficienta foarte ridicata. Dupa cum este argumentat in lucrarile de specialitate, AG sunt metode slabe evolutioniste ce reprezinta proprietatea de inteligenta emergenta, puterea lor venind dintr-o exploatare sofisticata a informatiilor obtinute cu un efort de cautare relativ limitat (Grefenstette, 1987).
2. AG folosesc codificari ale variabilei problemei
Fiind dat un spatiu de cautare, cu un spatiu multidimensional al solutiilor posibile, o reprezentare "cod genetic" este aleasa astfel incat fiecare punct din spatiul de cautare e reprezentat de un sir de simboluri numit genotip. In mod uzual, variabilele sunt codificate intr-un genotip de lungime fixa.
3. AG folosesc populatii de solutii potentiale
Aici apare o diferenta importanta fata de alte tehnici adaptive de cautare care lucreaza de la punct la punct, folosind informatii locale. Un AG exploreaza spatiul de cautare in mai multe puncte simultan. Aceste puncte explorate la un moment dat formeaza o populatie de solutii potentiale. Aceasta explorare a spatiului de cautare e facuta simultan cu exploatarea celor mai bune solutii la pasul curent.
4. AG folosesc operatori probabilistici
Populatia de la pasul urmator de cautare este dedusa prin aplicarea unor operatori de tip probabilistic. Aceasta caracteristica face ca AG sa fie o metoda de tip Monte-Carlo, dar trebuie sa facem observatia ca aceasta cautare realizata nu e pur aleatoare, ci o explorare "inteligenta" a spatiului de cautare.
Avand prezentate aceste caracteristici dominante ale AG in raport cu tehnicile de cautare conventionale, sa privim mai detaliat modul de functionare al unui AGS.
Inainte de a incepe o discutie despre algoritmii genetici iata o scurta descriere a termenilor cei mai importanti.
o Cromozom - utilizat pentru a referi o solutie potentiala, si consta in toate informatiile necesare pentru a descrie o solutie;
o Clona - apare atunci cand se realizeaza o duplicare a unui cromozom. Aceasta este de obicei utilizata pentru a crea un fel de mutatie care poate fi facuta fara a strica cromozomul initial;
o Crossover (incrucisare) - apare atunci cand doi cromozomi creeaza unul sau mai multi cromozomi prin amestecarea solutiilor lor;
o Fitness (potrivire) - o masura a calitatii unui anumit cromozom. Cromozomul care da cea mai buna solutie va avea cea mai buna potrivire(fitness);
o Genaratie - se refera la un ciclu complet al algoritmului genetic. Noi cromozomi sunt creati iar cai mai vechi sunt indepartati pentru a face loc celor noi.
o Mutatie - sunt utilizate in 2 contexte diferite
1. Descrie orice modificare aparuta la o populatie;
2. Modificare aparuta la un singur cromozom;
o Penalty (pedeapsa) - este o parte a potrivirii(fitness). Aceasta penalizeaza actiunile ilegale sau nedorite ale unui cromozom in spatiul solutiilor.
o Populatie - o colectie de cromozomi disponibili. In mod normal exista un numar limitat de cromozomi si acei cromozomi care sunt defecti sunt eliminati pentru a face loc altora cu performante mai bune;[7]
o Genotip - individ dintr-o populatie. Reprezentarea interna a acestui tip poate fi un sir de biti;
o Fenotip - obiectul corespunzator genotipului in problema data. Acesta este obiectul matematic.
o Gena - atom de informatie. De obicei se reprezinta ca un bit si poate reprezenta mai multe caractere ale unui individ.

Fisiere in arhiva (1):

 Algoritmi Genetici.doc