Optimizarea Structurilor Folosind Algoritmul Genetic

1. Definiţia Optimizării

OPTIMIZÁRE, optimizări,

Raționament sau calcul care permite găsirea valorilor unuia sau mai multor parametri corespunzând maximului unei funcții.

A face să devină optim, a îmbunătăți, a face ca randamentul unei mașini, al unui sistem tehnic etc. să corespundă unor exigențe sporite.

A alege și a aplica soluția cea mai bună (optimă) dintre toate soluțiile posibile.

Ce sunt AG?

ALGORITMII GENETICI sunt o familie de modele inspirate de teoria evoluţiei, programe inteligente capabile să soluţioneze probleme folosind un concept 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 (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 cromozomii cu soluţii mai puţin bune. Definirea unei soluţii bune se face în raport cu populaţia curentă.

Cum lucrează algoritmii genetici?

Etapele implementării si utilizării unui algoritm genetic sunt următoarele:

definirea elementelor algoritmului (reprezentarea, funcţia fitness, mecanismul de selecţie, operatorii genetici, parametrii)

proiectarea experimentului

execuţia experimentului

interpretarea rezultatelor

Analiza unui algoritm evolutiv se face empiric, pe baza rezultatelor unor experimente ce urmăresc fie performanţa absolută de calcul a algoritmului studiat, fie compararea algoritmului genetic studiat cu un alt algoritm ce rezolvă aceeaşi problemă (studiu relativ).

De aceea, în faza de proiectare a experimentului trebuie avută în vedere optimizarea algoritmului genetic şi pentru al doilea caz, consideraţi alte tipuri de algoritmi decât cei genetici pentru efectuarea de comparaţii.

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.