Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice


Acasa » tehnologie » electronica electricitate
Algoritmi genetici

Algoritmi genetici




Algoritmi genetici

Conceptul de viata artificiala inglobeaza fenomene de baza ce au elemente comune cu agentii vietii biologice, cum ar fi reproducerea, evolutia, adaptarea, autoorganizarea, parazitismul, cooperarea si competitia. Modelul natural al evolutiei a fost propus in deceniul cinci pentru optimizarea unor procese. Dupa 1960, prin analize teoretice si experimentari pe calculator s-au obtinut scheme evolutioniste, unele radical imbunatatite fata de cele biologice, care trateaza functiile neliniare ca genotipuri supuse efectelor mutatiilor, imperecherilor si selectiei. Dupa ce a investigat matematic adaptarea, J.H. Holland dezvolta la mijlocul anilor ’60 algoritmii genetici (GA - genetic algorithms), tehnici de optimizare care simuleaza evolutia naturala a speciilor. Ulterior, pe baza lor au fost dezvoltate in paralel strategiile de evolutie si programarea evolutionista, care opereaza cu reprezentari vectoriale ale codificarii genelor biologice. In anii ’70, Holland extinde utilizarea GA, obtinand ca rezultat sistemele de clasificare. In fine, J. R. Koza introduce in anii ’80 conceptul de programare genetica.




Algoritmii genetici sunt proceduri de cautare si optimizare bazate pe mecanismele geneticii si ale selectiei naturale. Ei combina supravietuirea artificiala a unei populatii cu aplicarea unor operatori genetici abstracti, obtinand-se un mecanism robust si eficient. Fata de tehnicile de optimizare conventionale, GA au unele particularitati distincte. Ei apeleaza la metode de cautare “oarba”, care considera fiecare problema o cutie neagra si o trateaza pornind numai de la cateva ipoteze, utilizeaza populatii de solutii potentiale alcatuite din codificari ale variabilelor sub forma unor siruri generate cu operatori aleatori si exploreaza spatiul de cautare in mai multe puncte simultan, pentru a se evita atingerea unui fals optim local.

Algoritmul genetic Holland transforma o populatie initiala de obiecte matematice intr-una noua, utilizand operatiile reproducerii proportionale darwiniene, operatiile genetice de recombinarea sexuala si mici modificari efectuate prin mutatii aleatoare. Corespondenta terminologica uzual folosita in aceasta echivalenta este: cromozom-sir binar, gena-unitate binara, alela (modificare a unei gene)-valoare binara. Algoritmul are cinci componente: o reprezentarea genetica a potentialului de solutii al problemei, calea pentru crearea unei populatii initiale de indivizi solutie, functia de evaluare, operatorii care  modifica compozitia populatiei si valorile initiale pentru diferiti parametri (dimensiunea populatiei, probabilitatea de aplicare a operatorilor, criteriul de oprire, etc.).

Populatia de solutii in care algoritmul Holland executa o cautare multidirectionala la un moment dat este numita generatie. Din fiecare generatie, solutiile “bune” se reproduc, iar cele “slabe” dispar. Evaluarea calitatii unor solutii este efectuata de catre o functie obiectiv (de adecvanta sau de sanatate). Populatiile de solutii se modifica sub influenta unor operatorii genetici: selectia, incrucisarea, mutatia.

Selectia este un proces de alegere, pe baza unui criteriu de supravietuire, a celor mai adecvati (sanatosi) indivizi dintr-o populatie, pentru a forma cu acestia un grup de imperechere (sau o generatie intermediara). Functia de calitate F(x), care selecteaza indivizii, joaca rolul mediului inconjurator si este obtinuta de obicei prin transformarea functiei f(x) ce trebuie optimizata. Selectia proportionala consta in alegerea unor indivizi i a caror valoare de sanatate este Fi. Pentru individul i din generatia t, probabilitatea selectiei este pi,t = Fi /Ft, unde Ft este media de sanatate a generatiei t. Noua generatie t+1 a populatiei se obtine prin aplicarea celorlalti doi operatori asupra setului intermediar selectat. Structura unui GA elementar este urmatoarea:

Procedure genetic - algoritm

begin

t=0

initializeaza P(t) (se creeaza o populatie aleatoare P(t));

evalueaza P(t) (calculeaza functia obiectiv pentru fiecare membru al lui P(t);

pana cand (conditie de non - terminare) executa

begin

t = t+1;

selecteaza P(t) din P(t-1);



recombina P(t);

evalueaza P(t) (evaluarea unei noi generatii);

end

end

Cea mai simpla metoda de incrucisare este cea binara (sau intr-un punct), constand dintr-o procedura in trei pasi:

1.Din populatia intermediara sunt alesi doi indivizi, numiti parinti;

2.Ambii cromozomi ai parintilor sunt despartiti in subcromozomi cu lungimi egale, drept si stang, pozitia de rupere putand fi oarecare (fiind aleasa aleator);

3.Fiecare nou fiu are subcromozomul stang de la un parinte si cel drept de la celalalt.

Generalizand, incrucisarea in m puncte divide cromozomii celor doi parinti prin m puncte aleatoare, iar fiii rezulta prin schimbarea alternativa a subgrupelor rezultate. Incrucisarea uniforma utilizeaza o masca pentru comutarea intre parinti a unor subcromozomi cu aceeasi lungime. O pozitie 1 in masca indica faptul ca respectivul bit va fi schimbat.

Operatorul de mutatie se aplica dupa incrucisare, cu scopul de a creste variabilitatea populatiei. Fiecare pozitie a fiecarui cromozom din noua populatie poate suferi o schimbare aleatoare cu o probabilitate egala cu rata de mutatie, care, pe parcursul procesului de calcul, este uzual constanta. Mutatiile binare corespund la comutarea bitului ales din 0 in 1 sau din 1 in 0. Pot fi folosite si tehnici mai sofisticate, cum ar fi mutatia adaptiva, duplicarea, inversiunea, etc.

O problema cheie in practica GA o constituie reprezentarea solutiilor. Cea mai raspandita metoda este astazi utilizarea sirurilor de caractere de lungime fixa (Holland), insa au fost propuse si alte solutii, mai sofisticate. Astfel, algoritmii messy utilizeaza siruri de lungime variabila, iar programarea genetica creste si mai mult complexitatea structurilor de reprezentare.

Dimensiunea populatiei afecteaza atat eficienta cat si performanta finala a algoritmului, pentru ca valori reduse sau prea mari ale acesteia duc la solutii suboptimale sau la o slaba convergenta. Cea mai utilizata metoda pentru creerea populatiei initiale este cea aleatoare. Totusi, daca se pot exploata anumite cunostinte initiale specifice problemei, este posibila si o alegere euristica.

Rata incrucisarilor (adica frecventa de aplicare a acestora) trebuie aleasa astfel incat sa elimine perpetuarea indivizilor neperformanti, situatie care poate aparea atunci cand aceasta este prea inalta. Convergenta este definita ca acea situatie cand algoritmul genereaza o populatie cu indivizi similari intre ei. Un nivel prea mic al mutatiilor produce convergenta prematura catre un singur individ. Convergenta poate fi accelerata utilizand o rata a mutatiilor variabila in timp. Din pacate, nu exista criterii de oprire unanim acceptate.

Masurarea performantelor GA se face prin trei parametri: performanta on-line, care reprezinta media tuturor functiilor de evaluare, performanta off-line, adica media celor mai bune siruri din fiecare generatie si cel mai bun sir gasit din fiecare generatie, care reprezinta o buna masura a calitatii functiei de optimizare.








Politica de confidentialitate


.com Copyright © 2021 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 SCHITA DE PROIECT DIDACTIC GEOGRAFIE CLASA: a IX-a - Unitatile majore ale reliefului terestru
 PROIECT DIDACTIC 5-7 ani Educatia limbajului - Cate cuvinte am spus?
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 Proiect - masurarea si controlul marimilor geometrice

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 LUCRARE DE LICENTA CONTABILITATE - ANALIZA EFICIENTEI ECONOMICE – CAI DE CRESTERE LA S.C. CONSTRUCTIA S.A TG-JIU
 Lucrare de licenta sport - Jocul de volei
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 PROIECT ATESTAT MATEMATICA-INFORMATICA - CALUTUL INTELIGENT
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM




Masurarea electrica a deplasarilor
Proiect Sisteme de Control Distribuit - Controlul a 4 intersectii semaforizate
Achizitionarea semnalelor de curent
JONCTIUNEA n-p
Necesarul de energie reactiva in unitatile industriale
Traductoare capacitive a senzorilor de proximitate
Identificarea sistemului utilizand retelele neuronale
TIRISTORUL





Termeni si conditii
Contact
Creeaza si tu