Referat Algoritmii Genetici

Mai jos puteti citi fragmente din Referat Algoritmii Genetici si de asemenea puteti face Download Referat Algoritmii genetici

Citeste fragmente din Referat Algoritmii Genetici

ALGORITMII GENETICI ALGORITMII GENETICI sunt o familie de modele inspirate de teoria evoluţiei, sunt programe inteligente capabile să soluţioneze probleme folosind un conceptul al 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ă. 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. Sarcina unui algoritm genetic e să descopere cromozomi din ce în ce mai buni, până la atingerea unei valori a raportului dintre evaluarea asociată unui şir şi evaluarea medie a tuturor şirurilor populaţiei (fitness) despre care se ştie că este optimală, sau până când algoritmul genetic nu mai poate aduce îmbunătăţiri. Implementarea unui algoritm genetic începe cu o populaţie de cromozomi (aleasă aleator). Se evaluează, apoi, aceste structuri şi se alocă facilităţi reproductive astfel încât acei cromozomi, care reprezintă o soluţie mai bună pentru problema ţintă, să aibă mai multe şanse de a se reproduce decât acei cromozomi care sunt soluţii mai puţin bune. Definirea unei soluţii bune se face în raport cu populaţia curentă. Î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. Adevăraţii profesionişti combină adesea cele mai variate tehnologii inteligente în scopul exploatării avantajelor fiecăreia, obţinând aşa-numitele sisteme hibride. Sunt posibile combinări de genul: folosirea reţelelor neuronale la ajustarea parametrilor în sistemele expert fuzzy, extragerea cunoaşterii din reţele neuronale pentru a fi utilizată în sistemele expert, folosirea algoritmilor genetici la crearea unor reţele neuronale mai compacte şi mai eficiente, folosirea unei reţele neuronale pentru asistarea funcţionării unui algoritm genetic, folosirea algoritmilor genetici la reglarea parametrilor unui sistem expert fuzzy pentru controlul proceselor, îmbunătăţirea performanţei unui sistem expert prin încorporarea raţionamentului bazat pe cazuri, etc. Asemenea cercetări sunt în prezent în mare vogă în cele mai specializate laboratoare ale lumii ştiinţifice. Cîteva subiecte ale conceptelor de bază : probleme de optimizare - doar două componente principale sunt dependente de problema de rezolvat : codificarea şi funcţia de evaluare. Scopul este de a fixa parametrii în aşa fel încât ieşirea să fie optimă. Variabilele desemnând parametrii sunt reprezentaţi prin şiruri binare iar funcţia de evaluare este parte a descrierii problemei. algoritmul genetic canonic – constă în generarea populaţiei iniţiale. Se aplică acestei populaţii selecţia pentru a obţine o populaţie intermediară. Apoi se aplică recombinarea şi mutaţii pentru a crea o populaţie următoare (next population). Acest proces de trecere de la populaţia curentă la populaţia următoare reprezintă o generaţie în execuţia unui algoritm genetic. selecţia hiperplanelor – nu este afectată de extremele locale. Creşterea ratei de selecţie a hiperplanelor peste medie nu garantează convergenţa către un optim global, ce ar putea fi un vârf relativ izolat. teorema schemei – furnizează o margine inferioară a schimbării ratei de selecţie pentru un singur hiperplan de la generaţia t la generaţia t+1. alfabetele binare – utilizarea lor va rezulta în urma unor calcule simple. Un alfabet minimal maximizează numărul de hiperplane utilizabile pentru codificarea procesării critica teoremei schemei – inexactitatea inegalităţii face ca încercarea de a prezice pe baza teoremei reprezentarea unui anumit hiperplan de-a lungul generaţiilor, să fie fără succes. Aplicaţii ale algoritmilor genetici – Algoritmii genetici reprezintă o metodă cu care pot fi atacate relativ uşor probleme dificile de optimizaresau control, cu rezultate bune sau chiar optimale. Când se vorbeşte 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 funcţionează la instalaţia de maleabilizare a unui laminor de platbande de oţel, unde operatorul unei macarale este ajutat să decidă unde să pună oţelul laminat înainte de maleabilizare, cum să grupeze şarjele în cuptorul de maleabilizare şi cum să aranjeze oţelul laminat maleabilizat pentru a fi expediat în funcţie de comenzile primite. Un alt exemplu este aceea de a realiza optimizarea unor obiective variate în alcătuirea orarelor pentu cursuri sau examene. Aplicaţii ale algoritmilor genetici este de exemplu controlul curgerii de gaz printr-o conductă, în regim staţionar şi în regim tranzitoriu. De-a lungul conductei, presiunea gazului descreşte în mod natural şi trebuie mărită cu ajutorul unor compresoare. Obiectivul constă în menţinerea presiunii în punctele de livrare la nivelul dorit, cu minimizarea energiei folosite în compresoare şi ăndeplinirea altor restricţii. De asemenea, este necesară detectarea, pe baza măsurării presiunii, a scurgerilor probabile, evitând, pe cât posibil, alarmele false. Alţi cercetători descriu o aplicaţie în proiectarea reţelelor de comunicaţii ăntre staţii aflate la mare distanţă. Optimizarea planificărilor - utilizarea algoritmilor pentru planificarea examenelor – se dau un set de examene şi un număr fix de căsuţe libere în orar : obiectivul e de a aşeza fiecare examen într-una dintre casuţe, asfel încât nici un student să nu aibă examene aflate în casuţe consecutive, nici prea multe examene în aceeaşi zi. De asemenea, anumite examene nu pot fi puse în anumite casuţe. 0 p ᤀoritatea cromozomilor generaţi aleator vor încălca mai multe restricţii. Funcţia de fitness conţine termini de penalizare pentru fiecare restricţie încălcată şi se dovedeşte stabilă faţă de valorile efective ale acestor termeni. Algoritmul genetic are deci o formă convenţională, cu excepţia unui operator de mutaţie mai deosebit. Acesta exercită o uşoară presiune pentru îmbunătăţirea orarului. Implementarea unui operator mai tare, care efectuează acea schimbare care duce la cea mai bună îmbunătăţire a unui cromozom, se dovedeşte extrem de dăunătoare. Algoritmul genetic a găsit o soluţie în care doar unul dintre studenţi a avut de susţinut două examene consecutive. Algoritmul a obţinut o astfel de soluţie, nu întotdeauna aceeaşi, în 50% din rulări. S-a aplicat metode similare pentru a genera orarul cursurilor; aici un cromozom reprezintă, pentru fiecare curs, ora de începere şi locul de desfăşurare, existând penalizări pentru lipsa de spaţiu în sala de curs, pentru distanţe prea mari între sălile unde se desfăşoară două cursuri consecutive. Metodele tardiţionale de plnificare, sun mai rapide dacă restricţiile sunt de tip “aceste evenimente nu pot avea loc simultan”, dar algoritmii genetici reprezintă o soluţie superioară dacă există şi alte restricţii mai complicate. Numeroase articole, programe pot fi găsite pe internet la adresele : garbo.uwasa.fi:pc/reseach/2500Garefs.ps.gz HYPERLINK "ftp://ftp.cs.cuhk:pub/EC" ftp.cs.cuhk:pub/EC HYPERLINK "ftp://ftp.germany.eu.net:pub/research/softcomp/EC" ftp.germany.eu.net:pub/research/softcomp/EC alife.sanatatefe.edu:pub/USER-AREA/EC HYPERLINK "ftp://ftp.dcs.warwick.ac.uk:pub/mirrors/EC" ftp.dcs.warwick.ac.uk:pub/mirrors/EC SISTEME INTELIGENTE BAZATE PE ALGORITMI GENETICI Mecanismul specific acestor sisteme este inspirat din funcţionare sistemelor biologice, în sensul că încurajează soluţiile candidat capabile să rezolve o problemă şi penalizează soluţiile fără succes. În felul acesta se obţin, după mai multe generaţii, soluţii foarte bune pentru probleme de optimizare complexe, cu un mare număr de parametri. Ideea de bază a unui algoritm genetic constă în a începe cu o populaţie de soluţii, fiecare mai performantă decât precedentele. Fazele ciclului prin care operează un asemenea algoritm sunt: creearea unei populaţii de “membri”,(soluţii candidat la rezolvrea unei probleme), selecţia membrilor care s-au adaptat cel mai bine necesităţilor problemei de soluţionat, reproducerea (se folosesc operatorii genetici de încrucişare şi mutaţie, pentru a obţine noi membri), evaluarea gradului în care noii membri corespund mai bine soluţionării problemei, abandonarea populaţiei vechi prin înlocuirea ei cu populaţia nouă din noua generaţie. Un asemenea ciclu se repetă până când este identificată cea mai bună soluţie la problema în cauză. fazele ciclului algoritmilor genetici Datorită structurii lor inerent paralele, sisteme inteligente bazate pe algoritmi genetici s-au dovedit performante în problemele de căutare şi identificare a structurilor şi relaţiilor specifice în cadrul bazelor de date şi bazelor de cunoştinţe voluminoase (data mining). Un succes particular s-a obţinut cu ele în problemele de optimizare referitoare la selectrea personalului şi selectrea portofoliilor. Şi aceste sisteme, deorece pot învăţa relaţii şi structuri complexe în cadrul seturilor de informaţii şi cunoştinţe incomplete, se pot adapta schimbărilor survenite în mediile în care funcţionează, şi pot fi utilizate ca instrumente pentru descoperirea unor cunoştinţe noi.Ele pot oferi explicaţii la deciziile luate într-un format perceptibil de către om. Aplicaţiile acestor sisteme s-au diversificat rapid şi s-au dovedit utile domeniul afacerilor financiare, comerţului cu titluri, evaluării creditelor, detecţiei fraudelor şi predicţiei falimentului. De exemplu, unii cercetători au folosit asemenea sisteme la inferarea unor reguli pentru predicţia falimentului întreprinderilor, pe baza indicatorilor financiari obţinuţi din bilanţ (financial ratios). Alţi cercetători descriu modul de utilizare a algoritmilor genetici în alocarea bugetară, în vederea asistării guvernelor şi administraţiilor locale la adoptarea celor mai bune decizii. Problemă : Se consideră {0,1}L mulţimea şirurilor binare de lungime L. Pentru un şir s din această mulţime notăm cu s1 numărul de componente egale cu 1 ale şirului. Fie N un număr natural nenul mai mic decât L, şi f o funcţie care asociază fiecărui şir s o valoare egală cu s1 dacă s1 nu este multiplu de N, şi 2s1 în caz contrar. Să se găsească un şir s* care maimizează f. Se va lua valorile L=10 şi N=3. Exemplu de utilizare : Program ce constă în maximizarea unei funcţii definite f(s)=s1 Se deschide fişierul ex1.prj din Borland şi se modifică fişierul ex1.c. Fişierul rezultat va avea forma : #include #include”sugar.h” int 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=result return 0; } Modificările au fost făcute în funcţia de evaluare. Pentru a seta parametrii algoritmului genetic am schimbat liniile fişierului ex1.cfg după cum urmează : generation 10 population 10 length 10 în generation 100 population 50 length 10 (întâmplător, lungimea şirului binar era predefinită ca 10, în general ea va trebui modificată). Rularea algoritmului se face prin comanda ex1.exe. În urma rulării programul obţine valoarea 1101111111, una dintre cele care maximizează f. Concuzie - Puterea algoritmilor genetici constă în uşurinţa cu care sunt implementaţi şi în faptul că dau de multe ori rezultate bune, chiar dacă nu găsesc întotdeauna optimul global. PAGE PAGE 1 Abandonarea Populaţia Evaluarea Reproducerea Selecţia 쥁@