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 intr-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 intregi, 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 in ce mai buni, pana 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 pana cand algoritmul genetic nu mai poate aduce imbunatatiri.

Implementarea unui algoritm genetic incepe cu o populatie de cromozomi (aleasa aleator). Se evalueaza, apoi, aceste structuri si se aloca facilitati reproductive astfel incat acei cromozomi, care reprezinta o solutie mai buna pentru problema tinta, sa aiba mai multe sanse de a se reproduce decat acei cromozomi care sunt solutii mai putin bune. Definirea unei solutii bune se face in raport cu populatia curenta.

Intr-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 intr-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 cand nu este posibila modelarea matematica si nici euristica in domeniu.

Adevaratii profesionisti combina adesea cele mai variate tehnologii inteligente in scopul exploatarii avantajelor fiecareia, obtinand asa-numitele sisteme hibride. Sunt posibile combinari de genul

1.     folosirea retelelor neuronale la ajustarea parametrilor in sistemele expert fuzzy,

2.     extragerea cunoasterii din retele neuronale pentru a fi utilizata in 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.     imbunatatirea performantei unui sistem expert prin incorporarea rationamentului bazat pe cazuri, etc.

Asemenea cercetari sunt in prezent in mare voga in cele mai specializate laboratoare ale lumii stiintifice.

Citeva 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 in asa fel incat iesirea sa fie optima.

Variabilele desemnand parametrii sunt reprezentati prin siruri binare iar functia de evaluare este parte a descrierii problemei.

• algoritmul genetic canonic - consta in 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 in 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 varf 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 in urma unor calcule simple. Un

alfabet minimal maximizeaza numarul de hiperplane utilizabile pentru codificarea procesarii

• critica teoremei schemei - inexactitatea inegalitatii face ca incercarea 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.

Cand se vorbeste de aplicarea unei idei din software, se refera in general la un prototip care arata cum ar putea fi folosita respectiva idee intr-un domeniu practic.

Un exemplu il 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 inainte de maleabilizare, cum sa grupeze sarjele in cuptorul de maleabilizare si cum sa aranjeze otelul laminat maleabilizat pentru a fi expediat in functie de comenzile primite. Un alt exemplu este aceea de a realiza optimizarea unor obiective variate in alcatuirea orarelor pentu cursuri sau examene.

Aplicatii ale algoritmilor genetici este de exemplu controlul curgerii de gaz printr-o conducta, in regim stationar si in regim tranzitoriu. De-a lungul conductei, presiunea gazului descreste in mod natural si trebuie marita cu ajutorul unor compresoare. Obiectivul consta in mentinerea presiunii in punctele de livrare la nivelul dorit, cu minimizarea energiei folosite in compresoare si andeplinirea altor restrictii. De asemenea, este necesara detectarea, pe baza masurarii presiunii, a scurgerilor probabile, evitand, pe cat posibil, alarmele false.

Alti cercetatori descriu o aplicatie in 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 in orar : obiectivul e de a aseza fiecare examen intr-una dintre casute, asfel incat nici un student sa nu aiba examene aflate in casute consecutive, nici prea multe examene in aceeasi zi. De asemenea, anumite examene nu pot fi puse in 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 incalca mai multe restrictii. Functia de fitness contine termini de penalizare pentru fiecare restrictie incalcata 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 imbunatatirea orarului. Implementarea unui operator mai tare, care efectueaza acea schimbare care duce la cea mai buna imbunatatire a unui cromozom, se dovedeste extrem de daunatoare. Algoritmul genetic a gasit o solutie in care doar

unul dintre studenti a avut de sustinut doua examene consecutive. Algoritmul a obtinut o astfel de solutie, nu intotdeauna aceeasi, in 50% din rulari.

S-a aplicat metode similare pentru a genera orarul cursurilor; aici un cromozom reprezinta, pentru fiecare curs, ora de incepere si locul de desfasurare, existand penalizari pentru lipsa de spatiu in sala de curs, pentru distante prea mari intre salile unde se desfasoara doua cursuri consecutive. Metodele tarditionale de plnificare, sun mai rapide daca restrictiile sunt de tip "aceste evenimente nu pot avea loc simultan", dar algoritmii genetici reprezinta o solutie superioara daca exista si alte restrictii mai complicate.

Numeroase articole, programe pot fi gasite pe internet la adresele

garbo.uwasa.fi:pc/reseach/2500Garefs.ps.gz

ftp.cs.cuhk:pub/EC

ftp.germany.eu.net:pub/research/softcomp/EC

alife.sanatatefe.edu:pub/USER-AREA/EC

ftp.dcs.warwick.ac.uk:pub/mirrors/EC

SISTEME INTELIGENTE BAZATE PE ALGORITMI GENETICI

Mecanismul specific acestor sisteme este inspirat din functionare sistemelor biologice, in sensul ca incurajeaza solutiile candidat capabile sa rezolve o problema si penalizeaza solutiile fara succes. In felul acesta se obtin, dupa mai multe generatii, solutii foarte bune pentru probleme de optimizare complexe, cu un mare numar de parametri.

Ideea de baza a unui algoritm genetic consta in a incepe cu o populatie de solutii, fiecare mai performanta decat precedentele. Fazele ciclului prin care opereaza un asemenea algoritm sunt

1. creearea unei populatii de membri",(solutii candidat la rezolvrea unei probleme),
2. selectia membrilor care s-au adaptat cel mai bine necesitatilor problemei de solutionat,
3. reproducerea (se folosesc operatorii genetici de incrucisare si mutatie, pentru a obtine noi membri),
4. evaluarea gradului in care noii membri corespund mai bine solutionarii problemei,
5. abandonarea populatiei vechi prin inlocuirea ei cu populatia noua din noua generatie.

Un asemenea ciclu se repeta pana cand este identificata cea mai buna solutie la problema in cauza.

fazele ciclului algoritmilor genetici

Datorita structurii lor inerent paralele, sisteme inteligente bazate pe algoritmi

genetici s-au dovedit performante in problemele de cautare si identificare a structurilor si relatiilor specifice in cadrul bazelor de date si bazelor de cunostinte voluminoase (data mining). Un succes particular s-a obtinut cu ele in problemele de optimizare referitoare la selectrea personalului si selectrea portofoliilor.

Si aceste sisteme, deorece pot invata relatii si structuri complexe in cadrul seturilor de informatii si cunostinte incomplete, se pot adapta schimbarilor survenite in mediile in care functioneaza, si pot fi utilizate ca instrumente pentru descoperirea unor cunostinte noi.Ele pot oferi explicatii la deciziile luate intr-un format perceptibil de catre om.

Aplicatiile acestor sisteme s-au diversificat rapid si s-au dovedit utile domeniul afacerilor financiare, comertului cu titluri, evaluarii creditelor, detectiei fraudelor si predictiei falimentului. De exemplu, unii cercetatori au folosit asemenea sisteme la inferarea unor reguli pentru predictia falimentului intreprinderilor, pe baza indicatorilor financiari obtinuti din bilant (financial ratios). Alti cercetatori descriu

modul de utilizare a algoritmilor genetici in alocarea bugetara, in vederea asistarii guvernelor si administratiilor locale la adoptarea celor mai bune decizii.

Problema

Se considera ^L multimea sirurilor binare de lungime L. Pentru un sir s din aceasta multime notam cu s₁ numarul de componente egale cu 1 ale sirului. Fie N un numar natural nenul mai mic decat L, si f o functie care asociaza fiecarui sir s o valoare egala cu s₁ daca s₁ nu este multiplu de N, si 2s₁ in caz contrar. Sa se gaseasca un sir s* care maimizeaza f. Se va lua valorile L 10 si N=3.

Exemplu de utilizare

Program ce consta in maximizarea unei functii definite f(s)=s₁ Se deschide fisierul ex1.prj din Borland si se modifica fisierul ex1.c. Fisierul rezultat va avea forma

#include<stdio.h>

#include"sugar.h"

int evaluate(SuChromosome*chrom,double*fitness);

main( int argc,char*arvg[] )

int evaluate (SuChromosome*chrom,double*fitness);

Modificarile au fost facute in functia de evaluare. Pentru a seta parametrii algoritmului genetic am schimbat liniile fisierului ex1.cfg dupa cum urmeaza

generation       10

population       10

length 10

in

generation       100

population       50

length 10

(intamplator, lungimea sirului binar era predefinita ca 10, in general ea va trebui modificata).

Rularea algoritmului se face prin comanda ex1.exe. In urma rularii programul obtine valoarea 1101111111, una dintre cele care maximizeaza f.

Concuzie - Puterea algoritmilor genetici consta in usurinta cu care sunt implementati si in faptul ca dau de multe ori rezultate bune, chiar daca nu gasesc intotdeauna optimul global.