Mod de abordare al algoritmilor euristici in Inteligenta Artificiala

Tipuri de probleme si solutionarea lor

Tipuri de probleme

Inca de la inceput, una din directiile majore de cercetare in Inteligenta Artificiala a fost rezolvarea automata a problemelor, intr-o maniera similara cu modul in care oamenii reusesc acest lucru. Zi de zi, oamenii se confrunta cu probleme pe care trebuie sa le resolve, uneori mai usoare alteori mai dificile.

Pentru a intelege si a incerca o abordare computationala a acestei teme, trebuie mai intai sa intelegem ce este de fapt o problema si cum pot fi determinate solutiile sale in general.

O definitie data problemei de Dan Girlea si Florin Leon de la Universitatea tehnica "Gheorhe Asachi" din Iasi ar fi urmatoarea: o problema poate fi considerata o diferenta intre starea actuala, imperfecta intr-un anume sens, si o stare scop, prin a carei atingere exista posibilitatea obtinerii unui benificiu in sensul considerat. Se observa folosirea conceptului de scop vazut ca o stare ideala ce trebuie atinsa Acest scop este atins in cazul unei probleme complexe trecandu-se prin mai multe etape cu scopuri intermediare.

Rezolvarea problemelor consta in identificarea diferentelor dintre starea curenta si starea scop si selectarea operatiilor care reduc aceste diferente. Trebuie identificate seturile de operatii care pot schimba starea curenta si care sa duca la starea scop si constrangerile aplicabile acestor operatii.

Calea urmata din starea initiala pana in starea scop se numeste solutionarea problemei.

De multe ori o problema nu are un singur mod de rezolvare, dar de multe ori este necesar sa se gaseasca solutia optima care rezolva problema cu maxima eficienta. De aceea trebuie identificata, pentru fiecare problema, o tehnica de rezolvare care sa permita identificarea solutiei optime intr-un timp cat mai scurt. Astfel, pentru rezolvarea problemei generale trebuie respectati urmatorii pasi:

defnirea cat mai precisa a problemei: specificarea unei stari initiale si finale (conditii si solutii acceptabile)

analiza problemei

alegerea celei mai potrivite tehnici de rezolvare si aplicarea ei la problema curenta

Dupa gradul de constrangere la care sunt supuse operatiile necesare in rezolvare problemele sunt: bine definite si rau definite.

Problemele bine definite se caracterizeaza prin existenta unui scop explicit si a unor operatori cunoscuti. Cu alte cuvinte, avem o modalitate clara de rezolvare, toate elementele implicate in acest proces sunt specificate De multe ori, aceste probleme au solutii generale cunoscute Ele sunt rezolvate prin metode standard sau prin metode cunoscute pentru probleme similare.

De exemplu, rezolvarea unei ecuatii algebrice de gradul intai: 5x

Stim ca pentru problema generala ax = b, solutia este x = b / a, iar impartirea este o operatie cunoscuta, cu restrictia (constrangerea) a 0.

Deci, in cazul nostru, x = 12 / 5 = 2,4.

Clasa problemelor bine definite cuprinde si probleme "grele", care necesita un timp de rezolvare (sau un spatiu de solutie) non-polinomial si care devine mult prea mare atunci cand complexitatea problemei creste.

In acest caz, pentru a determina totusi o solutie, avem nevoie de o modalitate de aproximare a solutiei optime.

In cazul problemelor rau definite intervine un factor de incertitudine, spatiul problemei nu este complet definit iar uneori insusi scopul problemei este dificil de formalizat. Nu este clar de la inceput care este rezolvarea si ce solutie trebuie obtinuta. De multe ori, solutiile gasite mai pot fi inca imbunatatite si cel care rezolva problema decide daca s-a obtinut o solutie acceptabila.

Aceasta clasa include probleme care necesita solutii euristice sau aproximative pentru probleme practic nerezolvabile din punct de vedere computational. Uneori, este posibila descompunerea problemelor rau definite intr-o multime de probleme bine definite, pentru care se cunoaste rezolvarea.

2. Tipuri de solutii

Si solutiile problemelor pot fi incadrate in mai multe categorii

Solutii algoritmice

Solutii euristice

Solutii prin simulare

Solutiile algoritmice sunt cea mai veche si inca cea mai folosita forma de rezolvare a problemelor.

Ea implica utilizarea unui algoritm, adica o procedura iterativa care rezolva problema intr-un numar finit de pasi.

In acest mod se ajunge de cele mai multe ori in final la solutia optima.

Trebuie precizat insa ca solutii algoritmice nu exista decat pentru probleme bine definite.

Solutiile euristice se bazeaza pe metode de rezolvare rezultate mai mult din experienta practica, care incearca sa estimeze o solutie acceptabila, eficienta din punct de vedere computational, cat mai apropiata de solutia optima.

Etimologie: gr. ευρίσκειν", a gasi, a inventa, a descoperi (vezi εύρηκα", am gasit).

Solutiile prin simulare au aparut in ultimul timp, datorita cresterii puterii de calcul.

Cand nici rezolvarea algoritmica si nici cea euristica nu este posibila, problema este rezolvata pentru o anumita multime de parametri si apoi sunt analizate rezultatele.

Daca solutia e acceptabila, e folosita; daca nu, se simuleaza alta solutie.

Aceasta poate fi optima sau nu, insa experimentele de simulare permit explorarea spatiului solutiilor intr-o maniera de genul "ce s-ar intampla daca", adica ce s-ar obtine prin schimbarea anumitor variabile.

2. Cautarea

In general, o problema poate fi modelata ca un proces de cautare.

Structurarea acestui proces poate fi realizata cu ajutorul sistemelor de productie, care constau in:

multime de reguli, cu o parte stanga (modelul) care determina aplicabilitatea regulii si o parte dreapta, care descrie actiunea corespunzatoare regulii

una sau mai multe baze de cunostinte necesare problemei; unele cunostinte sunt generale (independente de domeniul problemei), altele sunt indicate numai pentru o anumita problema (specifice domeniului)

o strategie de control, care stabileste ordinea in care regulile vor fi aplicate bazelor de cunostinte, precum si modul de rezolvare a conflictelor, cand pot fi aplicate mai multe reguli simultan

Sistemele de productie sunt o buna modalitate de formalizare a problemelor de inteligenta artificiala, deoarece:

evidentiaza natura actiunilor inteligente bazate pe cunostinte (atunci cand se schimba continutul bazei de cunostinte se modifica si comportamentul sistemului)

noi reguli pot fi usor adaugate atunci cand apar situatii noi fara a perturba restul programului

Procesul de cautare, indiferent pe ce tehnici particulare se bazeaza, trebuie sa parcurga etapele din figura:

Figura

2. Rationamentul inainte

Ideea care sta la baza unei proceduri de cautare este descoperirea unei cai in spatiul problemei care conduce de la starea initiala la starea scop. Cand cautarea porneste din starea initiala catre starea scop, avem de-a face cu un rationament inainte. Daca procesul de cautare este modelat printr-un sistem de productie, rezolvarea problemei apare drept construirea unui arbore a operatiilor posibile. Radacina arborelui este starea initiala. Nivelul urmator al arborelui se completeaza prin determinarea tuturor regulilor a caror parte stanga se potriveste nodului radacina. Noile noduri se creeaza prin intermediul partii drepte a regulilor considerate. Procedura se repeta pentru fiecare nod, pana cand se genereaza o configuratie identica starii scop.

Pentru a exemplifica, vom considera problema canilor cu apa: avem la dispozitie 2 cani de capacitati diferite A si B.

Scopul este ca in cana A sa ramana o cantitate specificata de apa prin aplicarea a 6 operatii posibile:

umple cana A ( A)

umple cana B ( B)

toarna apa din cana A in cana B (AB)

toarna apa din cana B in cana A (BA)

varsa cana A ( A)

varsa cana B ( B)

In figura 2 se prezinta arborele rezultat prin aplicarea celor 6 operatii unei probleme concrete: cana A are capacitatea de 4l, cana B are capacitatea de 3l iar in final in cana A trebuie sa se obtina un rest de 2l.

Figura 2.

Datorita complexitatii sale, numai primul nivel a fost completat, in rest urmarindu-se drumul catre solutia optima (calea cea mai scurta catre scop); se remarca faptul ca nu exista o solutie optima unica, ea putand fi atinsa pe doua cai diferite.

2.2. Rationamentul inapoi

Figura 3.

Spatiul problemei poate fi explorat si in directie inversa fata de cea urmata in cazul anterior. Cand cautarea porneste din starea scop catre starea initiala, avem de-a face cu un rationament inapoi. Aici radacina arborelui este starea scop. Nivelul urmator al arborelui se completeaza prin determinarea tuturor regulilor a caror parte dreapta se potriveste nodului radacina. Noile noduri se creeaza prin intermediul partii stangi a regulilor considerate. Procedura se repeta pentru fiecare nod, pana cand se genereaza o configuratie identica starii initiale.

Daca vom considera acelasi exemplu, al problemei canilor cu apa, trebuie sa facem unele precizari suplimentare pentru a o rezolva prin rationament inapoi

Cand problema este rezolvata prin rationament inainte, in starea scop in cana B se poate gasi orice cantitate de apa.

Cand problema este rezolvata prin rationament inpoi, starea scop trebuie fixata pentru ca de aici va incepe rationamentul.

Sa presupunem ca dorim restul de 2l in cana A si 0l in cana B.

Figura 4

Nu toate cele 6 operatii se vor putea aplica pentru orice nod. Vor exista constrangeri, de exemplu, daca la un anumit moment in cana A sunt 0l, este imposibila aplicarea primei operatii (umple A). Ar insemna ca dupa umplerea canii, in ea sa nu existe apa, ceea ce este absurd.

3. Euristici si metode euristice

Euristicile sunt tehnici care ajuta la descoperirea unei solutii, desi nu prezinta garantia ca aceasta este solutia optima. Exista euristici specifice unor anumite situatii particulare si euristici generale, aplicabile pentru o gama larga de probleme.

Sa consideram cateva euristici pentru problema canilor cu apa generalizata (orice capacitate a canilor A si B, respectiv orice rest de obtinut in A):

Daca restul este mai mare decat capacitatea canii A, problema nu are solutie (evident).

Daca restul nu este un multiplu al celui mai mare divizor comun al capacitatilor canilor A si B, problema nu are solutie (solutia problemei rezulta din combinarea diferentelor dintre capacitatile canilor A si B - cu o cana de 6l si una de 3l nu se va obtine niciodata un rest de 2l, deoarece toate diferentele vor fi multipli de 3).

Deoarece rezolvarea se bazeaza in principal pe schimbul de apa intre cele doua cani pentru a gasi diferentele, exista doua strategii care conduc la gasirea solutiei pentru orice problema de acest tip.

Notam cu valA si valB cantitatea de apa la un moment dat in cana A, respectiv B si cu capA si capB capacitatea canii A, respectiv B.

Restul care trebuie obtinut in cana A este notat cu rest.

Strategia 1:

While (valA != rest)

Strategia 2:

While (valA != rest)

In acest mod, nu mai este necesara construirea unui arbore de solutii iar rezolvarea se face fara consum suplimentar de memorie.

Trebuie determinata insa de la caz la caz strategia adecvata, care ajunge la solutie pe calea cea mai scurta.

De exemplu, daca A are capacitatea de 6l, B are capacitatea de 5l si ne propunem sa obtinem 2l in A, prima strategie gaseste solutia in 6 pasi, pe cand cea de a doua in 14.

Daca A are 11l, B are 6l si vrem sa obtinem 7l in A, prima strategie gaseste solutia in 24 de pasi iar a doua in 8.

Metodele euristice generale sunt numite si metode slabe.

In continuare vom prezenta:

l           Metoda generare si testare

l           Metoda gradientului descendent

l           Metoda satisfacerii constrangerilor

l           Metoda analizei mijloace-scopuri

Alegerea unei strategii eficiente depinde intr-o masura foarte mare de caracteristicile problemei.

3. Metoda generare si testare

Aceasta tehnica este foarte simpla: se genereaza o solutie posibila si se testeaza daca este o solutie acceptabila; daca nu, se genereaza o alta solutie posibila si ciclul se repeta.

Metoda se poate aplica pentru probleme de complexitatate redusa, insa nu este eficienta cand spatiul problemei este mare, deoarece necesita mult timp pentru incercarea tuturor variantelor.

Exista si varianta generarii aleatorii a variantelor, insa in acest caz nu avem nici o garantie ca se va gasi o solutie.

Cand solutia nu este un punct in spatiul problemei, ci o cale de la starea initiala la starea scop, tehnica devine o procedura de cautare in adancime (depth-first), intrucat necesita generarea solutiilor complete inainte ca testarea sa fie posibila.

Daca exista o modalitate de verificare a solutiilor partiale, metoda devine o procedura backtracking.

3.2. Metoda gradientului descendent

Metoda gradientului este o varianta a metodei precedente, in care procedura de test furnizeaza informatii generatorului de solutii despre directia in care sa se efectueze in continuare cautarea.

Functia de test poate contine euristici care sa estimeze cat de aproape e varianta curenta de starea scop a problemei.

Se genereaza mai intai o solutie posibila, ca la metoda generare si testare.

Din acest punct, se aplica regulile posibile pentru generarea unei multimi de solutii propuse.

Procedura de test estimeaza care dintre aceste variante potentiale este cea mai apropiata de solutia finala.

Generatorul preia varianta respectiva si o foloseste in continuare pentru gasirea unei noi multimi de stari potentiale si procesul se repeta.

In figura 5 se prezinta aplicarea metodei gradientului pentru a gasi calea cea mai scurta intre doua puncte pe un grid.

Procedura de test calculeaza distanta euclidiana intre punctul curent si punctul scop.

Fig.5

3.3. Metoda satisfacerii constrangerilor

Metoda aceasta poate fi aplicata intr-o multitudine de probleme de inteligenta artificiala, in care solutia problemei trebuie sa respecte o serie de constrangeri.

Aici procesul de cautare a solutiei este realizat prin doua cautari concurente, una in spatiul problemei pentru a gasi o urmatoare stare posibila si cealalta in lista de constrangeri, pentru a determina daca o anumita stare este intr-adevar o stare scop.

Cautarea poate fi modelata printr-un graf.

Pentru a gasi o solutie, se alege un nod inca neexpandat si se aplica acestuia regulile de inferenta ale constrangerilor pentru a se genera toate noile constrangeri posibile.

Daca multimea constrangerilor contine o contradictie, se abandoneaza calea curenta.

Daca multimea constrangerilor descrie o solutie completa, problema a fost rezolvata.

Daca nu s-a gasit nici o contradictie si nici o solutie completa, se aplica regulile de productie ale problemei pentru generarea de noi solutii partiale consistente cu multimea curenta de constrangeri.

Aceste solutii partiale se introduc in graful de cautare si procesul se reia.

Sa consideram o problema de criptare aritmetica: ce cifre se pot asigna literelor pentru ca adunarea urmatoare sa fie corecta?

Constrangerile sunt in acest caz urmatoarele:

l           respectarea regulilor aritmetice (pentru adunare)

l           literelor diferite le corespund cifre diferite (nu exista doua litere cu aceeasi valoare)

Cfrele corespunzatoare literelor de pe rangul cel mai semnificativ sunt diferite de 0 (aici, I, B, S si O ) trebuie sa fie nenule.

Pentru problema in discutie exista 2 solutii. Una din ele este: (U=8, C=7, B=2, I=5, E=1, S=6, A=3, R=4, O=9), adica:

3.4. Metoda analizei mijloace-scopuri

Ideea care sta la baza analizei mijloace-scopuri este detectarea diferentei dintre starea curenta si starea scop si gasirea unei operatii care sa micsoreze aceasta diferenta.

Daca operatia respectiva nu poate fi aplicata in starea curenta, trebuie gasita o noua stare, potrivita acestui subscop.

Rezulta o subproblema care trebuie la randul ei rezolvata si metoda se aplica recursiv.

Acesta tehnica este deseori folosita si de oameni pentru rezolvarea problemelor.

Primul program de inteligenta artificiala care a implementat procedura a fost General Problem Solver, realizat de Allen Newell si Herbert Simon in 1963 la Universitatea Carnegie Mellon.

O caracteristica a metodei este faptul ca se bazeaza pe un set de reguli care pot transforma o stare a problemei in alta.

Regulile se reprezinta sub forma unei parti stangi, care descrie conditiile de aplicare (preconditiile) si o parte dreapta care descrie schimbarile din starea problemei care se schimba datorita aplicarii regulii.

In acest scop se elaboreaza o asa-numita tabela de diferente, in care se precizeaza ce operatie este aplicabila pentru fiecare stare a problemei.

Sa consideram de exemplu modul in care poate calatori cineva:

daca distanta care trebuie parcursa este mai mare de 20km,
ia trenul

daca distanta este intre 2 si 20km, ia autobuzul

daca distanta este mai mica de 2km, merge pe jos

Tabela de diferente este urmatoarea:

Sa presupunem ca o persoana X din Iasi vrea sa-si viziteze un prieten Y din Bucuresti