Referate
Algoritmii genetici
ALGORITMII GENETICI
ALGORITMII GENETICI sunt o familie de modele inspirate de teoria evolutiei, sunt programe inteligente capabile sa solutioneze probleme folosind un conceptul al evolutiei speciilor.
Acesti algoritmi codifica solutiile posibile ale unor probleme specifice într-o structura de date de tip cromozom si aplica acestor structuri operatori de recombinare, pentru a pastra informatia utila.
Voturi:0
de catre: danutza
Numar pagini: 7
Tip document: .doc
Nivel: Facultate
Dimensiune: 67.0 KB
Downloads: 1
Credite: 0
Din referat: Algoritmii genetici
ALGORITMII GENETICI
ALGORITMII GENETICI sunt o familie de modele inspirate de teoria evolutiei, sunt programe inteligente capabile sa solutioneze probleme folosind un conceptul al evolutiei speciilor.
Acesti algoritmi codifica solutiile posibile ale unor probleme specifice într-o structura de date de tip cromozom si aplica acestor structuri operatori de recombinare, pentru a pastra informatia utila.
Un cromozom este un vector sau un sir de gene.
Pozitia unei gene este numita locusul ei. Valorile pe care le poate lua o gena sunt numite alele, sunt multimi finite de numere întregi, intervale de numere reale, sau chiar structuri complexe de date.
Alele variaza de la un locus la altul.
Sarcina unui algoritm genetic e sa descopere cromozomi din ce în ce mai buni, pâna la atingerea unei valori a raportului dintre evaluarea asociata unui sir si evaluarea medie a tuturor sirurilor populatiei (fitness) despre care se stie ca este optimala, sau pâna când algoritmul genetic nu mai poate aduce îmbunatatiri.
Implementarea unui algoritm genetic începe cu o populatie de cromozomi (aleasa aleator).
Se evalueaza, apoi, aceste structuri si se aloca facilitati reproductive astfel încât acei cromozomi, care reprezinta o solutie mai buna pentru problema tinta, sa aiba mai multe sanse de a se reproduce decât acei cromozomi care sunt solutii mai putin bune.
Definirea unei solutii bune se face în raport cu populatia curenta.
Într-un sens mai larg, algoritm genetic este orice model bazat pe ideea de populatie si care foloseste selectie si operatori de recombinare pentru a genera noi puncte într-un spatiu de cautare.
Multe modele au fost introduse de cercetatori dintr-o perspectiva experimentala. Cercetatorii sunt orientati spre aplicatii, fiind interesati de algoritmii genetici doar ca mijloace de optimizare.
Ei sunt recomandati pentru aflarea solutiilor neliniare ale unor probleme atunci când nu este posibila modelarea matematica si nici euristica în domeniu.
Adevaratii profesionisti combina adesea cele mai variate tehnologii inteligente în scopul exploatarii avantajelor fiecareia, obtinând asa-numitele sisteme hibride. Sunt posibile combinari de genul:
1. folosirea retelelor neuronale la ajustarea parametrilor în sistemele expert fuzzy,
2. extragerea cunoasterii din retele neuronale pentru a fi utilizata în sistemele expert,
3. folosirea algoritmilor genetici la crearea unor retele neuronale mai compacte si mai eficiente,
4. folosirea unei retele neuronale pentru asistarea functionarii unui algoritm genetic,
5. folosirea algoritmilor genetici la reglarea parametrilor unui sistem expert fuzzy pentru controlul proceselor,
6. îmbunatatirea performantei unui sistem expert prin încorporarea rationamentului bazat pe cazuri, etc.
Asemenea cercetari sunt în prezent în mare voga în cele mai specializate laboratoare ale lumii stiintifice.
Cîteva subiecte ale conceptelor de baza :
• probleme de optimizare - doar doua componente principale sunt dependente de
problema de rezolvat : codificarea si functia de evaluare. Scopul este de a fixa parametrii în asa fel încât iesirea sa fie optima.
Variabilele desemnând parametrii sunt reprezentati prin siruri binare iar functia de evaluare este parte a descrierii problemei.
• algoritmul genetic canonic – consta în generarea populatiei initiale. Se aplica
acestei populatii selectia pentru a obtine o populatie intermediara.
Apoi se aplica recombinarea si mutatii pentru a crea o populatie urmatoare (next population).
Acest proces de trecere de la populatia curenta la populatia urmatoare reprezinta o generatie în executia unui algoritm genetic.
• selectia hiperplanelor – nu este afectata de extremele locale.
Cresterea ratei de selectie a hiperplanelor peste medie nu garanteaza convergenta catre un optim global, ce ar putea fi un vârf relativ izolat.
• teorema schemei – furnizeaza o margine inferioara a schimbarii ratei de selectie pentru un singur hiperplan de la generatia t la generatia t+1.
• alfabetele binare – utilizarea lor va rezulta în urma unor calcule simple. Un alfabet minimal maximizeaza numarul de hiperplane utilizabile pentru codificarea procesarii
• critica teoremei schemei – inexactitatea inegalitatii face ca încercarea de a prezice pe baza teoremei reprezentarea unui anumit hiperplan de-a lungul generatiilor, sa fie fara succes.
Aplicatii ale algoritmilor genetici – Algoritmii genetici reprezinta o metoda cu care pot fi atacate relativ usor probleme dificile de optimizaresau control, cu rezultate bune sau chiar optimale.
Când se vorbeste de aplicarea unei idei din software, se refera în general la un prototip care arata cum ar putea fi folosita respectiva idee într-un domeniu practic.
Un exemplu îl constituie sistemul care functioneaza la instalatia de maleabilizare a unui laminor de platbande de otel, unde operatorul unei macarale este ajutat sa decida unde sa puna otelul laminat înainte de maleabilizare, cum sa grupeze sarjele în cuptorul de maleabilizare si cum sa aranjeze otelul laminat maleabilizat pentru a fi expediat în functie de comenzile primite.
Un alt exemplu este aceea de a realiza optimizarea unor obiective variate în alcatuirea orarelor pentu cursuri sau examene.
Aplicatii ale algoritmilor genetici este de exemplu controlul curgerii de gaz printr-o conducta, în regim stationar si în regim tranzitoriu.
De-a lungul conductei, presiunea gazului descreste în mod natural si trebuie marita cu ajutorul unor compresoare.
Obiectivul consta în mentinerea presiunii în punctele de livrare la nivelul dorit, cu minimizarea energiei folosite în compresoare si andeplinirea altor restrictii. De asemenea, este necesara detectarea, pe baza masurarii presiunii, a scurgerilor probabile, evitând, pe cât posibil, alarmele false.
Alti cercetatori descriu o aplicatie în proiectarea retelelor de comunicatii antre statii aflate la mare distanta.
Optimizarea planificarilor - utilizarea algoritmilor pentru planificarea examenelor – se dau un set de examene si un numar fix de casute libere în orar : obiectivul e de a aseza fiecare examen într-una dintre casute, asfel încât nici un student sa nu aiba examene aflate în casute consecutive, nici prea multe examene în aceeasi zi.
De asemenea, anumite examene nu pot fi puse în anumite casute.
Reprezentarea folosita este naturala : exista o gena pentru fiecare examen, allele fiind date de multimea casutelor din orar. Evident, majoritatea cromozomilor generati aleator vor încalca mai multe restrictii.
Functia de fitness contine termini de penalizare pentru fiecare restrictie încalcata si se dovedeste stabila fata de valorile efective ale acestor termeni. Algoritmul genetic are deci o forma conventionala, cu exceptia unui operator de mutatie mai deosebit.
Acesta exercita o usoara presiune pentru îmbunatatirea orarului.
Implementarea unui operator mai tare, care efectueaza acea schimbare care duce la cea mai buna îmbunatatire a unui cromozom, se dovedeste extrem de daunatoare.
Algoritmul genetic a gasit o solutie în care doar
unul dintre studenti a avut de sustinut doua examene consecutive.
Algoritmul a obtinut o astfel de solutie, nu întotdeauna aceeasi, în 50% din rulari.