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 = C₁x + C₂) prin crearea de stringuri de biti independenti pentru cele doua constante necunoscute C₁ si C₂ 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 2ⁿ-1. Numarul 10 va arata ca 1010, 2³ + 2¹ = 10, formand un string de 4 biti. Acest string de biti poate fi mapat pentru valoarea unui parametru fie el C_i, 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
• C_max si C_min sunt constante definite de utilizator intre care C₁ si C₂ varieaza liniar.

Parametrii C₁ si C₂ 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.

Pentru a realiza o linie (y = C₁x + C₂) mai intai vom codifica multimea parametru (C₁ , C₂) 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 C₁ iar urmatorii 6 biti codifica parametrul C₂. Coloanele 3 si 5 din tabelul 1 arata echivalentul zecimal al codificarilor binare. Aceste valori binare pentru C₁ si C₂ sunt apoi mapate in valori relevante pentru problema utilizand modelul numeric prezentat in ecuatia 1. Vom presupune ca valoarea minima pentru care vom excepta C₁ si C₂ va fi -2 iar valoarea maxima va fi 5. Alegerea acestor valori este pur si simplu aleatoare. Deci in ecuatia 1 C_{min i} = -2 iar C_{max i} = 5. Utilizand aceste valori putem calcula C₁ si C₂ 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 = C₁x + C₂, utilizand valorile C₁ si C₂ 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.