Sisteme Bazate pe Modele Genetice

1.Notiuni generale despre algoritmi genetici(AG)

ALGORITMII GENETICI sunt o familie de modele inspirate de teoria evoluţiei, sunt programe inteligente capabile să soluţioneze probleme folosind conceptul evoluţiei speciilor. Aceşti algoritmi codifică soluţiile posibile ale unor probleme specifice într-o structură de date de tip cromozom şi aplică acestor structuri operatori de recombinare, pentru a păstra informaţia utilă.

Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de populaţie şi care foloseşte selecţie şi operatori de recombinare pentru a genera noi puncte într-un spaţiu de căutare. Multe modele au fost introduse de cercetători dintr-o perspectivă experimentală. Cercetătorii sunt orientaţi spre aplicaţii, fiind interesaţi de algoritmii genetici doar ca mijloace de optimizare. Ei sunt recomandaţi pentru aflarea soluţiilor neliniare ale unor probleme atunci când nu este posibilă modelarea matematică şi nici euristică în domeniu.

Inceputurile algoritmilor genetici se situeaza undeva in jurul anului 1950, cand mai multi biologi au folosit calculatoarele pentru simularea sistemelor biologice. Rezultatele muncii au inceput sa apara dupa 1960, cand la Universitatea din Michigan, sub directa indrumare a lui John Holland, algoritmii genetici au aparut in forma in care sunt cunoscuti astazi.Dupa cum sugereaza si numele, algoritmii genetici folosesc principii din genetica naturala. Cateva principii fundamentale ale geneticii sunt imprumutate si folosite artificial pentru a construi algoritmi de cautare care sunt robusti si cer informatii minime despre problema. Algoritmii genetici au fost inventati folosind modelul procesului de adaptare. Ei opereaza, in principal, cu siruri binare si folosesc un operator de incrucisare si un operator de mutatie.Mare parte din teoria algoritmilor genetici se aplica in principal modelului introdus de Holland sau a unor variante denumite algoritmi genetici canonici. Progresele teoretice recente in modelarea algoritmilor genetici se refera, de asemenea, la algoritmul genetic canonic.Notiunea generala de algoritm genetic este cea prezentata mai sus ( model bazat pe ideea de populatie si care foloseste operatori de selectie si recombinare pentru a genera noi puncte intr-un spatiu de cautare ); multe modele bazate pe algoritmi genetici au fost introduse de cercetatori dintr-o perspectiva experimentala. Multi astfel de cercetatori sunt orientati spre aplicatii, fiind interesati de algoritmii genetici doar ca mijloace de optimizare.

Algoritmii genetici sunt o familie de modele computationale inspirate de teoria evolutiei. Acesti algoritmi codifica solutiile posibile ale unor probleme specifice intr-o structura de tip cromozom si aplica acestor structuri operatori de recombinare si mutatie pentru a pastra informatia utila. Desi algoritmii genetici sunt priviti deseori ca optimizand functii, domeniul de probleme la care au fost aplicati este destul de larg.Implementarea unui algoritm genetic incepe cu o populatie de cromozomi (in general aleasa aleator).Un cromozom este un vector sau un şir de gene. Poziţia unei gene este numită locusul ei. Valorile pe care le poate lua o genă sunt numite alele, sunt mulţimi finite de numere întregi, intervale de numere reale, sau chiar structuri complexe de date. Alele variază de la un locus la altul. Se evalueaza apoi, aceste structuri si se aloca facilitati reproductive astfel incat acei cromozomi, care reprezinta o solutie mai buna pentru problema tinta sa aiba mai multe sanse de a se reproduce decat acei cromozomi care sunt solutii mai proaste. Definirea unei solutii “bune” se face, in general, in raport cu populatia curenta.

Un algoritm genetic se defineste prin urmatoarele concepte:

• Individ/cromozom/lant/secventa/string:o solutie potentiala a problemei;

• Populatie:o multime de indivizi sau de puncte in spatiul de cautare;

• Mediul:spatiul de cautare;

• Functia de fitness:functia pozitiva care trebuie maximizata,scopul unui algoritm genetic fiind acela de a gasi stringul care maximizeaza functia de fitness;

Fazele AG sunt următoarele:

i. Initializarea:O populatie initiala de N cromozomi este determinata aleator (utilizand,de exemplu,metode obisnuite de generare a numerelor intamplatoare);

ii. Evaluarea:Fiecare individ (cromozom) din cadrul populatiei este codificat si apoi evaluat cu functia de fitness;

iii. Selectia:Crearea unei noi populatii de N cromozomi utilizand o metoda de selectie adecvata;

iv. Reproducerea:posibilitatea de incrucisare si mutatie in cadrul noii populatii;

v. Revenirea la faza de evaluare pana la oprirea algoritmului.Conditia de oprire este legata,in general,de atingerea unei valori a functieie de fitness care este cea mai mare comparativ cu celelalte si care nu mai creste in continuare;

Operatorii genetici

Operatorii genetici joacă cel mai important rol în cadrul algoritmilor genetici. Există trei tipuri principale de operatori genetici:

• Operatorul de selectie;

• Operatorul de incrucisare;

• Operatorul de mutatie;

A. Operatorul de selectie(numit uneori si operator de reproducere) este cel mai important operator genetic deoarece permite indivizilor dintr-o populatie sa supravietuiasca,sa se reproduca sau sa moara.Ca regula generala,probabilitatea de supravietuire a unui individ este legata direct de eficienta relativa a acestuia in cadrul populatiei respective.Exista mai jmulte metode de reproducere(selectie).Metoda cea mai cunoscuta este cea a loteriei intamplatoare(aleatoare).Conform acestei metode,fiecare individ (cromozom) va fi duplicat in noua populatie,proportional cu valoarea sa de adaptare.Se efectueaza,de cateva ori,extrageri cu revenire din cadrul multimii de indivizi ai populatiei respective.In cazul codificarii binare,se determina pentru fiecare individ(cromozom) extras fitnessul acestuia.