| Referate informatica | Bac 2008 informatica | Recomanda unui prieten

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.