Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » biologie
Fuzzy si algoritmii genetici

Fuzzy si algoritmii genetici



Fuzzy si algoritmii genetici

Algoritmii genetici se bazeaza pe conceptele teoriei de evolutie ale lui Darwin sa anume:

  • Reproducere
  • Crossover
  • Mutatie

Se creeaza diferite solutii de rezolvare a problemei, dupa care acestea sunt testate in vederea observarii performantelor. Din toate solutiile posibile, o fractiune de solutii bune este selectata iar celelalte solutii sunt eliminate (conceptul de supravietuire a celui mai potrivit). Solutiile selectate vor fi supuse proceselor de reproductie, crossover si mutatie pentru a crea noi generatii de solutii posibile (aceste noi solutii create se asteapta a fi mai bune decaz cele din generatia anterioara). Acest proces de reproductie a unei noi generatii si evalutia acestei noi generatii este repetat pana cand exista o convergenta intr-o generatie. Beneficiul acestei tehnici este ca el cauta o solutie pornind de la un spectru larg de solutii posibile.




Algoritmii genetici incearca sa realizeze o cautare inteligenta a unei solutii pornind de la un numar infinit de solutii. In continuare vom arata cum conceptele genetice sunt translatate in algoritmi de cautare. Intr-un algoritm genetic, multimile parametru ale problemei sunt codificate ca un string finit de biti. Spre exemplu, dandu-se o multime de date bidimensionale (x, y), dorim sa determinam o curba liniara (o linie dreapta) care sa treaca prin aceste puncte. Pentru a avea o potrivire liniara, vom codifica multimea parametru pentru o linie (y = C1x + C2) prin crearea de stringuri de biti independenti pentru cele doua constante necunoscute C1 si C2 si apoi vom concatena stringurile. Stringurile de biti sunt combinatii de 0 si 1, care reprezinta valoarea unui numar in forma binara. Un string de n biti poate reprezenta toti intregii pana la valoarea 2n-1. Numarul 10 va arata ca 1010, 23 + 21 = 10, formand un string de 4 biti. Acest string de biti poate fi mapat pentru valoarea unui parametru fie el Ci, i = 1, 2, de catre urmatoarea mapare:

(eq. 1)

unde:

  • b este numarul in forma zecimala care va fi reprezentat in forma binara
  • L este lungimea stringului de biti
  • Cmax si Cmin sunt constante definite de utilizator intre care C1 si C2 varieaza liniar.

Parametrii C1 si C2 depind de problema. Lungimea stringurilor de biti depinde de capacitatea calculatorului utilizat, trebuie sa avem o lungime aleasa in asa fel incat calculatorul sa opereze la viteza maxima.

Toti algoritmii genetici contin trei operatori de baza: reproducerea, crossover si mutatia. Vom exemplifica mai intai intregul proces al unui algoritm genetic si apoi vom incerca sa intelegem procesele de baza.

Mai intai sa consideram ca avem craeta o populatie initiala de n stringuri (pentru n parametrii) de lungime L. Stringurile sunt create intr-o maniera aleatoare astfel incat, valorile parametrilor care sunt codificati in stringuri au valori aleatoare (vom umple stringurile cu 0 si 1 intr-un mod aleator). Fiecare string este decodificat intr-o multime de parametrii care ii reprezinta. Aceasta multime de parametrii este pasata cu ajutorul unui model numeric spatiului problemei. Modelul numeric ofera o solutie bazata pe multimea intrarilor parametrilor. Pe baza calitatii solutiei obtinute, stringul este asignat unei valori de potrivire. Valorile de potrivire sunt determinate pentru fiecare string din intreaga populatie de stringuri. Cu aceste valori de potrivire, cei trei operatori genetici sunt utilizati pentru a crea noi generatii de stringuri, care se asteapta sa fie mai bune decat generatiile anterioare. Noua multime de stringuri este din nou decodificata si evaluata si o noua generatie de stringuri este creata utilizand cei trei operatori genetici. Acest proces este continuat pana cand se obtine convergenta intr-o populatie.

Reproducerea este procesul prin care stringurile cu valorile de potrivire cele mai bune primesc copiile cele mai bune corespunzatoare intr-o noua generatie, astfel incat sa fim siguri ca solutiile bune persista si contribuie la crearea de stringuri noi bune pe durata generatiilor succesive. Aceasta este o cale de a ne asigura ca stringurile cele mai bune supravietuiesc. Deoarece numarul total de stringuri din fiecare generatie este mentinut constant (pentru eficienta si economie de calcule), stringurile cu cea mai mica potrivire sunt eliminate.

Cel de-al doilea operator, crossover, este procesul in care stringurile sunt capabile de a mixa si potrivi calitatilor lor dorite intr-o maniera aleatoare. Dupa reproducere, implementarea operatorului crossover se realizeaza in trei pasi simplii. In primul pas, doua noi stringuri sunt selectate aleator (fig 1.a). In al doilea pas, a locatie aleatoare este selectata in cele doua stringuri (fig 1.b.). In pasul al treilea, portiunea de stringuri de la dreapta locatiei selectate aleatoar din cele doua stringuri este interschimbata. In acest fel informatia este interschimbata intre stringuri si portiuni de solutii de inalta calitate sunt interschimbate si combinate. Operatorii de reproducerea si crossover sunt cei care dau putere calculului genetic.

a.

b.

c.

Figura 1. Actiunea operatorului crossover intre stringuri

Cel de-al treilea operator genetic, mutatia, ajuta la cresterea puterii de cautare. Pentru a intelege necesitatea operatorului de mutatie, sa consideram cazul in care operaorii reproducere sau crossover nu sunt capabili sa gaseasca o solutie optima pentru o problema. Pe durata crearii unei generatii este posibil ca intraga populatie de stringuri sa fie lipsita de un vital bit de informatie (spre exemplu nici un string nu poseda o valoare de 1 in locatia numarul 4) care este necesar pentru determinarea corecta a unei solutii optime. Generatiile urmatoare create cu ajutorul primilor doi operatori nu reusesc sa elimine aceasta problema. In acest punct operatorul de mutatie devine foarte important. Ocazional, valoarea unei anumite locatii a unui string este schimata din 1 in 0 sau viceversa. Mutatia ne asigura ca un bit vital este introdus in noua generatie. Mutatia ca si in natura are loc foarte rar.

Exemplu.

Sa consideram tabelul de date din figura 2. Dorim sa realizam o linie care trece prin toate punctele prezentate in tabelul 1.

Nr.

x

Y

2



Pentru a realiza o linie (y = C1x + C2) mai intai vom codifica multimea parametru (C1 , C2) in stringuri de biti. Stringurile de biti sunt create cu ajutorul asignarilor aleatoare de 1 si 0 la diferite locatii de biti. Vom porni cu o populatie initiala pentru cele patru stringuri conform tabelului 1 coloana 2. Stringurile au o lungime de 12 biti. Primii 6 biti codifica parametru C1 iar urmatorii 6 biti codifica parametrul C2. Coloanele 3 si 5 din tabelul 1 arata echivalentul zecimal al codificarilor binare. Aceste valori binare pentru C1 si C2 sunt apoi mapate in valori relevante pentru problema utilizand modelul numeric prezentat in ecuatia 1. Vom presupune ca valoarea minima pentru care vom excepta C1 si C2 va fi –2 iar valoarea maxima va fi 5. Alegerea acestor valori este pur si simplu aleatoare. Deci in ecuatia 1 Cmin i = -2 iar Cmax i = 5. Utilizand aceste valori putem calcula C1 si C2 rezultatele fiind prezentate in tabelul 1 coloanele 4 si 6. Valorile prezentate in tabelul 1 coloanele 7, 8, 9 si 10 sunt calculate cu ajutorul ecuatiei y = C1x + C2, utilizand valorile C1 si C2 din coloanele 4 si 6, respectiv pentru valori diferite ale lui x asa cum sunt prezentate in tabelul initial. Aceste valori calculate pentru y sunt comparate cu valorile corecte (valorile lui y considerate in tabelul initial) si patratul erorilor in estimarea tuturor y-cilor este estimata pentru fiecare string. Aceasta insumare este scazuta dintr-un numar mare (400 in cazul nostru, tabelul 1 coloana 11) pentru a converti problema intr-o problema maximala. Valorile prezente in tabelul 1 coloana 11 sunt valorile cu cea mai buna potrivire pentru cele patru stringuri. Aceste valori de potrivire sunt adaugate. Media lor este deasemenea calculata. Valorile de potrivire pentru fiecare string sunt impartite de media valorilor de potrivire a intregii populatii a stringurilor pentru a obtine o estimare a potrivirilor relative ale fiecarui string (tabelul 1 coloana 12). Aceasta masura actioneaza deasemenea ca un ghid pentru stringurile care trebuiesc eliminate din anumite considerente pentru urmatoarea generatie si pentru care string va primi rezulatatul reproducerii in urmatoarea generatie. In cazul problemei noastre valoarea de divizare 0.8 va fi utilizata pentru acceptarea unui string intr-o noua generatie. In tabelul 1 coloana 13 se prezinta numarul de copii pentru fiecare din cele patru stringuri care vor fi utilizate in crearea urmatoarei generatii de stringuri. Tabelul 1.b. este continuarea tabelului 1.a. Prima coloana din tabelul 1.b. prezinta cele patru stringuri selectate din generatia anterioara aliniate pentru realizarea operatorului crossover la locatiile aratate in stringuri in coloane. Dupa aplicarea operatorului crossover, noile stringuri generate sunt prezentate in tabelul 1.b. coloana 2. Aceste stringuri vor suferi acelasi proces de decodificare si evaluare ca si generatia anterioara. Acest proces este prezentat in tabelul 1.b. coloanele 3 pana la 13. Trebuie notat ca media potrivirilor a celei de a doua generatii este mai mare decat cea pentru prima generatie de stringuri. Procesul de evaluare este continuat pana se va obtine convergenta solutiei intr-o generatie.

Nr.

String

C1

(bin)

C1

C2

(bin)

C2

Y1

Y2

Y3

Y4

F(x)= 400-

Nr= f/medie

Nr. actual





Suma

Media

Max

Tabelul 1.b.

Suma

Media

Max








Politica de confidentialitate

.com Copyright © 2020 - 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




Activitatea optica si strereochimia aminoacizilor
MICROBIOLOGIE
SISTEMUL NERVOS VEGETATIV
Transformarea genetica
REFERAT BIOLOGIE ANIMALA - DIVERSITATEA ECOLOGICA A PESTILOR
DIVIZIUNEA MEIOTICA
Proteinele membranare
LIMBA (LINGUA)




Termeni si conditii
Contact
Creeaza si tu