Referat ALGORITMII GENETICI

ALGORITMII GENETICIALGORITMII GENETICI sunt o familie de modele inspirate de teoria evoluiei, sunt programe inteligente capabile s soluioneze probleme folosind un conceptul al evoluiei speciilor. Aceti algoritmi codific soluiile posibile ale unor probleme specifice ntr-o structur de date de tip cromozom i aplic acestor structuri operatori de recombinare, pentru a pstra informaia util. Un cromozom este un vector sau un ir de gene. Poziia unei gene este numit locusul ei. Valorile pe care le poate lua o gen sunt numite alele, sunt mulimi finite de numere ntregi, intervale de numere reale, sau chiar structuri complexe de date. Alele variaz de la un locus la altul.Sarcina unui algoritm genetic e s descopere cromozomi din ce n ce mai buni, pn la atingerea unei valori a raportului dintre evaluarea asociat unui ir i evaluarea medie a tuturor irurilor populaiei (fitness) despre care se tie c este optimal, sau pn cnd algoritmul genetic nu mai poate aduce mbuntiri.Implementarea unui algoritm genetic ncepe cu o populaie de cromozomi (aleas aleator). Se evalueaz, apoi, aceste structuri i se aloc faciliti reproductive astfel nct acei cromozomi, care reprezint o soluie mai bun pentru problema int, s aib mai multe anse de a se reproduce dect acei cromozomi care sunt soluii mai puin bune. Definirea unei soluii bune se face n raport cu populaia curent.ntr-un sens mai larg, algoritm genetic este orice model bazat pe ideea de populaie i care folosete selecie i operatori de recombinare pentru a genera noi puncte ntr-un spaiu de cutare. Multe modele au fost introduse de cercettori dintr-o perspectiv experimental. Cercettorii sunt orientai spre aplicaii, fiind interesai de algoritmii genetici doar ca mijloace de optimizare.Ei sunt recomandai pentru aflarea soluiilor neliniare ale unor probleme atunci cnd nu este posibil modelarea matematic i nici euristic n domeniu. Adevraii profesioniti combin adesea cele mai variate tehnologii inteligente n scopul exploatrii avantajelor fiecreia, obinnd aa-numitele sisteme hibride. Sunt posibile combinri de genul:1.folosirea reelelor neuronale la ajustarea parametrilor n sistemele expert fuzzy,2.extragerea cunoaterii din reele neuronale pentru a fi utilizat n sistemele expert,3.folosirea algoritmilor genetici la crearea unor reele neuronale mai compacte i mai eficiente,4.folosirea unei reele neuronale pentru asistarea funcionrii unui algoritm genetic,5. folosirea algoritmilor genetici la reglarea parametrilor unui sistem expert fuzzy pentru controlul proceselor,6.mbuntirea performanei unui sistem expert prin ncorporarea raionamentului bazat pe cazuri, etc.Asemenea cercetri sunt n prezent n mare vog n cele mai specializate laboratoare ale lumii tiinifice.Cteva subiecte ale conceptelor de baz :probleme de optimizare - doar dou componente principale sunt dependente de problema de rezolvat : codificarea i funcia de evaluare. Scopul este de a fixa parametrii n aa fel nct ieirea s fie optim.Variabilele desemnnd parametrii sunt reprezentai prin iruri binare iar funcia de evaluare este parte a descrierii problemei.algoritmul genetic canonic const n generarea populaiei iniiale. Se aplic acestei populaii selecia pentru a obine o populaie intermediar. Apoi se aplic recombinarea i mutaii pentru a crea o populaie urmtoare (next population). Acest proces de trecere de la populaia curent la populaia urmtoare reprezint o generaie n execuia unui algoritm genetic. selecia hiperplanelor nu este afectat de extremele locale. Creterea ratei de selecie a hiperplanelor peste medie nu garanteaz convergena ctre un optim global, ce ar putea fi un vrf relativ izolat. teorema schemei furnizeaz o margine inferioar a schimbrii ratei deselecie pentru un singur hiperplan de la generaia t la generaia t+1.alfabetele binare utilizarea lor va rezulta n urma unor calcule simple. Un alfabet minimal maximizeaz numrul de hiperplane utilizabile pentru codificarea procesrii critica teoremei schemei inexactitatea inegalitii face ca ncercarea de a prezice pe baza teoremei reprezentarea unui anumit hiperplan de-a lungul generaiilor, s fie fr succes.Aplicaii ale algoritmilor genetici Algoritmii genetici reprezint o metod cu care pot fi atacate relativ uor probleme dificile de optimizaresau control, cu rezultate bune sau chiar optimale.Cnd se vorbete de aplicarea unei idei din software, se refer n general la un prototip care arat cum ar putea fi folosit respectiva idee ntr-un domeniu practic.Un exemplu l constituie sistemul care funcioneaz la instalaia de maleabilizare a unui laminor de platbande de oel, unde operatorul unei macarale este ajutat s decid unde s pun oelul laminat nainte de maleabilizare, cum s grupeze arjele n cuptorul de maleabilizare i cum s aranjeze oelul laminat maleabilizat pentru a fi expediat n funcie de comenzile primite. Un alt exemplu este aceea de a realiza optimizarea unor obiective variate n alctuirea orarelor pentu cursuri sau examene.Aplicaii ale algoritmilor genetici este de exemplu controlul curgerii de gaz printr-o conduct, n regim staionar i n regim tranzitoriu. De-a lungul conductei, presiunea gazului descrete n mod natural i trebuie mrit cu ajutorul unor compresoare. Obiectivul const n meninerea presiunii n punctele de livrare la nivelul dorit, cu minimizarea energiei folosite n compresoare i ndeplinirea altor restricii. De asemenea, este necesar detectarea, pe baza msurrii presiunii, a scurgerilor probabile, evitnd, pe ct posibil, alarmele false.Ali cercettori descriu o aplicaie n proiectarea reelelor de comunicaii ntre staii aflate la mare distan.Optimizarea planificrilor - utilizarea algoritmilor pentru planificarea examenelor se dau un set de examene i un numr fix de csue libere n orar : obiectivul e de a aeza fiecare examen ntr-una dintre casue, asfel nct nici un student s nu aib examene aflate n casue consecutive, nici prea multe examene n aceeai zi. De asemenea, anumite examene nu pot fi puse n anumite casue. Reprezentarea folosit este natural : exist o gen pentru fiecare examen, allele fiind date de mulimea casuelor din orar. Evident, majoritatea cromozomilor generai aleator vor nclca mai multe restricii. Funcia de fitness conine termini de penalizare pentru fiecare restricie nclcat i se dovedete stabil fa de valorile efective ale acestor termeni. Algoritmul genetic are deci o form convenional, cu excepia unui operator de mutaie mai deosebit. Acesta exercit o uoar presiune pentru mbuntirea orarului. Implementarea unui operator mai tare, care efectueaz acea schimbare care duce la cea mai bun mbuntire a unui cromozom, se dovedete extrem de duntoare. Algoritmul genetic a gsit o soluie n care doar unul dintre studeni a avut de susinut dou examene consecutive. Algoritmul a obinut o astfel de soluie, nu ntotdeauna aceeai, n 50% din rulri.S-a aplicat metode similare pentru a genera orarul cursurilor; aici un cromozom reprezint, pentru fiecare curs, ora de ncepere i locul de desfurare, existnd penalizri pentru lipsa de spaiu n sala de curs, pentru distane prea mari ntre slile unde se desfoar dou cursuri consecutive. Metodele tardiionale de plnificare, sun mai rapide dac restriciile sunt de tip aceste evenimente nu pot avea loc simultan, dar algoritmii genetici reprezint o soluie superioar dac exist i alte restricii mai complicate.Numeroase articole, programe pot fi gsite pe internet la adresele :garbo.uwasa.fi:pc/reseach/2500Garefs.ps.gzftp.cs.cuhk:pub/ECftp.germany.eu.net:pub/research/softcomp/ECalife.sanatatefe.edu:pub/USER-AREA/ECftp.dcs.warwick.ac.uk:pub/mirrors/ECSISTEME INTELIGENTE BAZATE PE ALGORITMI GENETICIMecanismul specific acestor sisteme este inspirat din funcionare sistemelor biologice, n sensul c ncurajeaz soluiile candidat capabile s rezolve o problem i penalizeaz soluiile fr succes. n felul acesta se obin, dup mai multe generaii, soluii foarte bune pentru probleme de optimizare complexe, cu un mare numr de parametri.Ideea de baz a unui algoritm genetic const n a ncepe cu o populaie de soluii, fiecare mai performant dect precedentele. Fazele ciclului prin care opereaz un asemenea algoritm sunt:1.creearea unei populaii de membri,(soluii candidat la rezolvrea unei probleme),2.selecia membrilor care s-au adaptat cel mai bine necesitilor problemei de soluionat,3.reproducerea (se folosesc operatorii genetici de ncruciare i mutaie, pentru a obine noi membri),4.evaluarea gradului n care noii membri corespund mai bine soluionrii problemei,5.abandonarea populaiei vechi prin nlocuirea ei cu populaia nou din noua generaie.Un asemenea ciclu se repet pn cnd este identificat cea mai bun soluie la problema n cauz.fazele ciclului algoritmilor geneticiDatorit structurii lor inerent paralele, sisteme inteligente bazate pe algoritmigenetici s-au dovedit performante n problemele de cutare i identificare a structurilor i relaiilor specifice n cadrul bazelor de date i bazelor de cunotine voluminoase (data mining). Un succes particular s-a obinut cu ele n problemele de optimizare referitoare la selectrea personalului i selectrea portofoliilor.i aceste sisteme, deorece pot nva relaii i structuri complexe n cadrul seturilor de informaii i cunotine incomplete, se pot adapta schimbrilor survenite n mediile n care funcioneaz, i pot fi utilizate ca instrumente pentru descoperirea unor cunotine noi.Ele pot oferi explicaii la deciziile luate ntr-un format perceptibil de ctre om.Aplicaiile acestor sisteme s-au diversificat rapid i s-au dovedit utile domeniul afacerilor financiare, comerului cu titluri, evalurii creditelor, deteciei fraudelor i prediciei falimentului. De exemplu, unii cercettori au folosit asemenea sisteme la inferarea unor reguli pentru predicia falimentului ntreprinderilor, pe baza indicatorilor financiari obinui din bilan (financial ratios). Ali cercettori descriu modul de utilizare a algoritmilor genetici n alocarea bugetar, n vederea asistrii guvernelor i administraiilor locale la adoptarea celor mai bune decizii.Problem :Se consider {0,1}L mulimea irurilor binare de lungime L. Pentru un ir s din aceast mulime notm cu s1 numrul de componente egale cu 1 ale irului. Fie N un numr natural nenul mai mic dect L, i f o funcie care asociaz fiecrui ir s o valoare egal cu s1 dac s1 nu este multiplu de N, i 2s1 n caz contrar. S se gseasc un ir s* care maimizeaz f. Se va lua valorile L=10 i N=3.Exemplu de utilizare :Program ce const n maximizarea unei funcii definite f(s)=s1 Se deschide fiierul ex1.prj din Borland i se modific fiierul ex1.c. Fiierul rezultat va avea forma :#include#includesugar.hint evaluate(SuChromosome*chrom,double*fitness);main( int argc,char*arvg[] ){SuaEvaluationFunction=evaluate;SuRun( ex1.cfg,argc,argv );}int evaluate (SuChromosome*chrom,double*fitness);{int i;int N=3;int count=0;double result=0.0;for( i=0; ilength;++i )count+=SuGetBit( chrom->string,i );if(count%N==0)result=2*count;else result =count;*fitness=resultreturn 0;}Modificrile au fost fcute n funcia de evaluare. Pentru a seta parametrii algoritmului genetic am schimbat liniile fiierului ex1.cfg dup cum urmeaz :generation10population10length 10ngeneration100population50length 10(ntmpltor, lungimea irului binar era predefinit ca 10, n general ea va trebui modificat).Rularea algoritmului se face prin comanda ex1.exe. n urma rulrii programul obine valoarea 1101111111, una dintre cele care maximizeaz f.Concluzie - Puterea algoritmilor genetici const n uurina cu care sunt implementai i n faptul c dau de multe ori rezultate bune, chiar dac nu gsesc ntotdeauna optimul global.