mihaispr
Administrator
 Inregistrat: acum 18 ani
Postari: 2142
|
|
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:
1. folosirea reţelelor neuronale la ajustarea parametrilor în sistemele expert fuzzy,
2. extragerea cunoaşterii din reţele neuronale pentru a fi utilizată în sistemele expert,
3. folosirea algoritmilor genetici la crearea unor reţele neuronale mai compacte şi mai eficiente,
4. folosirea unei reţele neuronale pentru asistarea funcţionării unui algoritm genetic,
5. folosirea algoritmilor genetici la reglarea parametrilor unui sistem expert fuzzy pentru controlul proceselor,
6. î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.
Reprezentarea folosită este naturală : există o genă pentru fiecare examen, allele fiind date de mulţimea casuţelor din orar. Evident, majoritatea 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
•:pub/EC
•:pub/research/softcomp/EC
• alife.sanatatefe.edu:pub/USER-AREA/EC
•:pub/mirrors/EC
|
|
