Post on 05-Dec-2015
description
transcript
10.04.2011 1
Cap. 1. Sisteme expert
O definiţie a sistemelor expert
Sistemele expert – SE constituie o clasă particulară de sisteme informatice bazate pe inteligenţa artificială, având ca scop reproducerea cu ajutorul calculatorului a cunoştinţelor şi raţionamentelor experţilor umani.
Edward Feigenbaum de la Stanford University, considerat părintele sistemelor expert, defineşte SE ca fiind: “programe concepute pentru a raţiona în scopulrezolvării problemelor dificile pentru care, în mod obişnuit, se cere o expertiză umană considerabilă”.
10.04.2011 2
Cap. 1. Sisteme expert
Un expert uman este o persoană care posedă cunoştinţe temeinice într-un anumit domeniu, un specialist de înaltă clasă, care poate efectua o expertiză în acel domeniu.Expertul poate rezolva probleme ale domeniului, pe care
alţii nu le pot rezolva deloc sau în mod eficient. El trebuie să fie capabil să îndeplinească următoarele sarcini:
să formuleze precis problema pe baza datelor puse la dispoziţie;să determine soluţia corectă;să explice soluţia şi paşii necesari pentru obţinerea ei;să acorde asistenţă pentru implementarea soluţiei într-un domeniu particular.
10.04.2011 3
Cap. 1. Sisteme expert
Din punct de vedere funcţional, un sistem expert poate fi definit ca un program care se bazează pe o bază de cunoştinţe pentru a realiza anumite sarcini, uneori dificile, pe care de regulă le rezolvă un expert uman din domeniul respectiv.
În concluzie, un SE este un program inteligent care utilizează cunoştinţe, fapte şi tehnici de raţionament pentru a rezolva probleme care în mod normal necesită cunoştinţele experţilor umani.
10.04.2011 4
Cap. 1. Sisteme expert
Observaţii:
Performanţele programului inteligent depind de:“bogăţia” bazei de cunoştinţe;organizarea acestora, care să permită rezolvarea problemei într-un timp rezonabil.
Spre deosebire de majoritatea programelor clasice de calcul, care cer informaţii complete pentru rezolvarea problemei sau luarea deciziilor, sistemele expert sunt proiectate să găsească soluţia pe baza datelor disponibile, adesea incomplete, la fel ca un expert uman.
10.04.2011 5
Cap. 1. Sisteme expert
SE sunt sisteme de prelucrare automată a datelor conţinute într-o bază largă de date care pe lângă elementele clasice de prelucrare, conţin:
baza de cunoştinţe alcătuită din reguli şi fapte;elementele necesare manipulării cunoştinţelor sub forma mecanismului de inferenţă;elementele necesare achiziţionării şi implementării de noi cunoştinţe;componenta explicativă.
10.04.2011 6
Cap. 1. Sisteme expert
Asemănător expertului uman care, bazându-se pe cunoştinţele acumulate, prin raţionamentul propriu ajunge la anumite concluzii, un SE se bazează pe cunoştinţele înglobate în baza de cunoştinţe şi pe mecanismul de inferenţă care are funcţia de a lua decizii în urma unor raţionamente logice.Raţionamentul este o înlănţuire de judecăţi (propoziţii) în care plecând de la anumite cunoştinţe, consemnate într-un număr de propoziţii numite premise sau fapte iniţiale, se ajunge la o nouă cunoştinţă – exprimată printr-o nouă propoziţie numită concluzie. Raţionamentul este corect dacă şi numai dacă concluzia este consecinţa logică a premiselor.
Raţionamentul poate fi definit şi ca o înlănţuire de reprezentări simbolice care trebuie să conducă la atingerea unui scop: a demonstra, a convinge, a elucida, a decide, a explica etc.
10.04.2011 7
Cap. 1. Sisteme expert
SE implică următoarele caracteristici:reprezentări simbolice;inferenţă simbolică;căutare euristică,
Acestea le diferenţiază în mod esenţial de sistemele informatice convenţionale (procedurale) de prelucrare care folosesc date şi algoritmi cunoscuţi apriori pentru rezolvarea problemelor.
Metodele de rezolvare folosite de SE nu sunt proceduri matematice sau procesoare de date, ci tehnici de raţionament calitativ sau tehnici euristice, care leagă elemente între ele prin reguli de judecată precum şi prin legi şi definiţii teoretice.
10.04.2011 8
Cap. 1. Sisteme expert
Diferenţele dintre un program de calcul analitic şi un SE:sistemul expert foloseşte datele din baza de date filtrate printr-un set de cunoştinţe, înmagazinate în baza de cunoştinţe, care sunt independente de algoritmul de rezolvare utilizat;algoritmul de căutare a soluţiei, denumit motor de inferenţă, nu mai este de tip iterativ, ca în cazul programelor analitice, ci de tip convergent;datorită delimitării nete dintre elementele componente (baza de date, baza de cunoştinţe, motorul de inferenţă) un SE poate fi modificat cu uşurinţă prin simpla adăugare sau eliminare de reguli; conceperea unui SE este un proces linear, realizat prin discuţii repetate cu experţi umani pentru dezvoltarea bazei de cunoştinţe;toate operaţiile logice şi matematice care se succed în găsirea unui răspuns se aduc la cunoştinţa utilizatorului printr-un modul explicativ independent numit “interfaţa cu utilizatorul”.
10.04.2011 9
Cap. 1. Sisteme expert
Caracteristicile care califică un program dreptsistem expert
lucrează la un nivel expert de competenţă; foloseşte un mecanism de inferenţă pentru a realiza deducţiile;expertiza efectuată se bazează exclusiv pe cunoştinţe special dobândite;programarea lui implică descrierea şi reprezentarea cunoştinţelor unor experţi în domeniu, cunoştinţe ce sunt păstrate în baze de date specifice, numite baze de cunoştinţe, în scopul utilizării ulterioare.
10.04.2011 10
Cap. 1. Sisteme expert
Avantaje ale utilizării sistemelor expert
1. aria de aplicabilitate cuprinde numeroase domenii de activitate mergând de la arhitectură, arheologie, bănci, comerţ, educaţie, până la ingineria sistemelor şi medicină;
2. disponibilitatea crescută, expertiza devenind accesibilă pe orice calculator adecvat: spre deosebire de expertul uman, SE este disponibil în orice moment şi nu este afectat de emotivitate, factori de stres etc.;
3. reducerea costului, explicabilă în corelaţie cu cele menţionate la punctul anterior, dar şi cu evoluţia preţului sistemelor de calcul;
4. permanenţa, rezultată din faptul că, spre deosebire de experţii umani, SE nu au o viaţă limitată;
5. reducerea riscurilor prin incorporarea în sisteme de comandă a roboţilor industriali utilizaţi în medii periculoase pentru om;
10.04.2011 11
Cap. 1. Sisteme expert
Avantaje ale utilizării sistemelor expert
6. creştrea calităţii, prin obţinerea unei expertize complete a domeniului, ceea ce expertul uman nu realizează întotdeauna;
7. posibilitatea de explicare în detaliu a soluţiei obţinute pentru creşterea gradului de încredere al utilizatorului;
8. rapiditatea, în sensul că pe sisteme hardware şi software adecvate se pot obţine performanţe de timp mult mai bune comparativ cu cele ale experţilor umani;
9. păstrarea în siguranţă a cunoştinţelor: marile firme şi-au constituit sisteme expert pentru a fi afectate într-o mai mică măsură de plecarea unor experţi umani;
10. contribuţia la răspândirea cunoştinţelor din domeniu: un utilizator poate rula programul pentru mai multe probleme, de la simplu la complex, şi urmărind soluţiile şi explicaţiile date de SE se poate autoinstrui în domeniul respectiv.
10.04.2011 12
Cap. 1. Sisteme expert
Arhitectura unui SE
Mediu ded ezvo ltare
Inginer decunoşt inţe
Memo riea d elucru
Fapte dinamice
Uti lizator
E xpert îndomeniu
Baza dedate
Regu liselecţionate
A cţiuniConcluzii
Da te
Baza decunoşt inţe
Reg uli
Fap teSelectare
reg uli şi fapte
Moto r de in ferenţă
Ach
iziţi
e de
cunoşt
inţe
10.04.2011 13
Cap. 1. Sisteme expert
Componentele unui SE se grupează în:1. Componente de bază care alcătuiesc nucleul SE
baza de cunoştinţe; baza de date; motorul de inferenţe. (inferenţă = operaţie logică de trecere de la un enunţ la altul şi în care ultimul enunţ este dedus din primul )
2. Componente complementaremodulul de achiziţionare de cunoştinţe; interfaţa cu inginerul de aplicaţie (expertul); interfaţa cu inginerul de cunoştinţe;interfaţa cu utilizatorul; module de grafică şi de calcul.
10.04.2011 14
Cap. 1. Sisteme expert
Baza de cunoştinţe – BC
cuprinde o colecţie de cunoştinţe relevante despre un anumit domeniu şi este constituită din reguli şi fapte.
Regulile se referă la operaţiile ce pot fi efectuate asupra obiectelor conţinute în baza de date. Ele se schimbă mai rar şi în esenţă constituie un ansamblu complet şi necontradictoriu de cunoştinţe necesare rezolvării unei probleme.
Faptele reprezintă partea dinamică a bazei de cunoştinţe şi au rolul de a reprezenta starea obiectelor la un moment dat.
10.04.2011 15
Cap. 1. Sisteme expert
Reprezentarea cunoştinţelor
Reprezentarea cunoştinţelor se poate realiza prin:
regulile de producţie;reţele semantice;structuri împachetate sau frame–uri;obiecte;logica propoziţională sau a predicatelor
10.04.2011 16
Cap. 1. Sisteme expert
Reguli de producţie
Reprezentarea cunoştinţelor sub forma regulilor de producţie este specifică sistemelor de producţie şi este foarte potrivită pentru raţionamente.
Într-un sistem de producţie cunoştinţele sunt de natură procedurală şi se împart în următoarele componente:
cunoştinţe declarative sau factuale, grupate sub forma unor structuri de date memorate într-o colecţie denumită context;cunoştinţe procedurale reprezentate sub forma unor perechi de tipul condiţie –acţiune, denumite reguli de producţie, memorate în baza de reguli;cunoştinţe strategice sau de control, reprezentate sub forma unor reguli care sprijină decizia în procesul de soluţionare al problemei.
10.04.2011 17
Cap. 1. Sisteme expert
Structura generală a unei reguli de producţie este:< partea de condiţie > → < partea de acţiune >
şi este interpretată astfel: “DACĂ < partea de condiţie > este îndeplinită,
ATUNCI se poate executa < partea de acţiune >”.
Partea de condiţie, denumită şi premisă, este constituită din propoziţii logice care trebuie să fie verificate pentru ca regula să poată fi aplicată.
Partea acţiune corespunde declanşării unei concluzii sau a unei noi ipoteze.
10.04.2011 18
Cap. 1. Sisteme expert
Avantajele regulilor de producţiemodularitatea proprie a fiecărei reguli – orice regulă poate fi considerată ca o entitate structurală independentă de celelalte ceea ce conferă o uşoară întreţinere a bazei de reguli;modularitate în realizarea formalismului de rezolvare a problemei regulile putând fi asimilate cu un ansamblu de constituenţi elementari, care se adună şi se combină pentru a forma un răspuns la problema studiată;caracterul natural de exprimare ;accesibilitatea bazei de reguli, dată de facilitatea şi uniformitatea structurii utilizate pentru reprezentarea cunoştinţelor.
10.04.2011 19
Cap. 1. Sisteme expert
Dezavantajele regulilor de producţieimposibilitatea de a prevedea o desfăşurare optimă pentru o secvenţă de acţiuni;
ordinea în care sunt aplicate regulile potenţial aplicabile influenţează concluzia obţinută.
10.04.2011 20
Cap. 1. Sisteme expert
Reţele semanticeSunt structuri destinate reprezentării cunoştinţelor sub forma unui graf complex alcătuit din noduri şi arce. Nodurile reţelei/grafului sunt utilizate pentru a reprezenta obiecte, concepte, atribute, stări, evenimente etc. Arcele reprezintă relaţiile existente între obiectele ataşate nodurilor reţelei semantice şi sunt de două tipuri:
ISA – is a (este un); AKO – a kind of (un fel de).
Reţelele semantice, respectiv grafurile corespunzătoare, pot fi organizate ierarhic ceea ce permite moştenirea unor atribute de la tipurile generale la cele particulare.
10.04.2011 21
Cap. 1. Sisteme expert
Structuri împachetate (frame-uri).
O structură este un grup de atribute ce descriu un obiect dat. Fiecare atribut este stocat într-un slot (compartiment ) care conţine valoarea/valorile ataşate. Folosirea structurilor permite reprezentarea cunoştinţelor în blocuri de date, fiecare bloc fiind prezentat printr-un slot sau compartiment. Structurile reprezentând diverse obiecte pot fi înzestrate cu proprietatea de moştenire, pe baza căreia se generează legături ierarhice între acestea. Prin urmare, ele pot fi reprezentate sub forma unui arbore.
10.04.2011 22
Cap. 1. Sisteme expert
Reprezentarea orientată pe obiecte
Constituie un pas superior în reprezentarea datelor.
Caracteristica principală a reprezentării orientată pe obiecte este aceea că unifică, într–o aceeaşi unitate structurală numită "obiect", datele şi funcţiile sau metodele care acţionează asupra lor.
Din punct de vedere al tehnicii de programare tipurile structurilor amintite se definesc cu ajutorul conceptului de clasă, iar obiecte cu care operează programul sunt instaţieri ale claselor.
10.04.2011 23
Cap. 1. Sisteme expert
Logica predicatelor
Oferă un mijloc de exprimare a aserţiunilor (aserţiune = enunţ care este dat ca adevărat ) şi un cadru formal pentru realizarea de inferenţe bazate pe manipularea sintatică a formulelor logice.
O bază de cunoştinţe este constituită exclusiv dintr-o mulţime de formule care descriu universul problemelor de rezolvat numit şi universul de discurs.
10.04.2011 24
Cap. 1. Sisteme expert
Utilizarea logicii predicatelor pentru reprezentarea cunoştinţelor rezultă din posibilitatea obţinerii de noi rezultate folosind reguli de inferenţă precum:
modus ponens;modus tollens;rezoluţia etc.
Logica permite exprimarea relativ naturală a unor fapte, fiind lipsită de ambiguităţi: este un sistem formal care oferă rigoare şi claritate semantică.Avantajele oferite de rigoare şi claritate constituie în acelaşi timp dezavantaje în reprezentarea cunoştinţelor şi realizarea expertizei deoarece omul, în general, nu este atât de riguros, raţionamentele sale fiind adesea mult mai suple.
10.04.2011 25
Cap. 1. Sisteme expert
Nu există o organizare între diferitele elemente care alcătuiesc baza de cunoştinţe. Obiectele manipulate nu au o reprezentare proprie; ele există doar prin intermediul formulelor care sunt diseminate în baza de cunoştinţe (este caracteristica formalismului relaţional, opus celui obiectual.
Pe măsură ce baza de cunoştinţe se dezvoltă, lipsa de organizare generează probleme vizând coerenţa utilizării sale.
Modelarea cunoştinţelor în logica de ordinul întâi nu este întotdeauna uşor de realizat.
Pentru eliminarea dezavantajelor şi extinderea câmpului de aplicaţii al logicii s-au dezvoltat aşa numitele logici neclasicecum ar fi logicile multivalente, logicile de incertitudine, logicile modale, logicile fuzzy etc.
10.04.2011 26
Cap. 1. Sisteme expert
Consideraţii vizând reprezentarea cunoştinţelor
În dezvoltarea aplicaţiilor practice de tip SE, pentru reprezentarea cunoştinţelor se au în vedere următoareleaspecte:
regulile de producţie sunt foarte adecvate pentru dezvoltarea raţionamentelor;frame-urile (cadrele), încadrate eventual în reţele semantice, sunt adecvate pentru stocarea şi manipularea eficientă a cunoştinţelor;reprezentarea orientată pe obiecte, prin proprietăţi precum încapsularea, moştenirea şi polimorfismul, asigură o elasticitate mărită în elaborarea SE.
10.04.2011 27
Cap. 1. Sisteme expert
În afara inferenţelor folosind cunoştinţele calitative, pentru rezolvarea problemelor din viaţa reală sunt necesare şi calcule numerice. Cantitatea de calcule poate fi foarte mică în unele cazuri şi destul de mare în altele.
Necesitatea ca un sistem expert să fie capabil să apeleze programede calcul procedural.
Acestea formează o parte a bazei de cunoştinţe şi se numesc cunoştinţe cantitative. Ele pot fi reprezentate ca funcţii sau programe scrise în limbaje de programare de nivel înalt cum ar fi Fortran sau C.
În acest conrext, cele mai multe shell-uri de dezvoltare a sistemelor expert furnizează facilităţi de reprezentare atât a cunoştinţelor calitative (prin reguli, structuri etc.), cât şi a cunoştinţelor cntitative prin funcţii scrise în limbaje procedurale.
10.04.2011 28
Cap. 1. Sisteme expertBaza de fapte – BF
Constituie partea dinamică a sistemelor bazate pe cunoştinţe şi conţine informaţii relative la domeniul de aplicaţie studiat. Faptele sunt date normale de tip:
închis–deschis pentru un echipament de comutaţie;o alarmă de ieşire din funcţiune a unui echipament;o valoare sau o mărime fizică aflată în afara limitelor admisibile etc.
Ele se modifică pe măsură ce stările obiectelor cărora le sunt asociate se schimbă (de exemplu datorită unor avarii, efectuării unor manevre, schimbării configuraţiei de funcţionare a unei reţele etc.).
10.04.2011 29
Cap. 1. Sisteme expert
Un fapt are o reprezentare de forma:<Obiect>, <Relaţie>, <Valoare>
<Obiectul> reprezintă, de exemplu, un echipament a cărui stare poate fi stabilită printr–o semnalizare, verificare sau, mai general, deducţie logică;
<Relaţie> corespunde unei relaţii existente între obiecte sau între un obiect şi diferitele stări în care acesta se poate afla;
<Valoare> reprezintă cuantificarea stării obiectului la un moment dat.
Exemplu: < Întreruptorul I7 > < Este în poziţia > < Închis >
10.04.2011 30
Cap. 1. Sisteme expert
În funcţie de domeniul de aplicare, sistemul expert are la dispoziţie un anumit număr de fapte, care descriu stări sau dau informaţii de tip cantitativ. O parte din datele din baza de fapte sunt introduse cu ajutorul dialogului om–maşină, în timp ce altă parte este încărcată automat prin citirea lor dintr-o bază de date.
Prin analogie cu programele de calcul convenţionale, faptele reprezintă ” datele ” problemei. În arhitectura SE ele, alături de unele date numerice aferente modelului problemei abordate, ” baza de date ”.
10.04.2011 31
Cap. 1. Sisteme expert
Motorul de inferenţă – MI
Este un program general care implementează mecanismul prin care se construiesc raţionamentele.
Pornind de la faptele iniţiale ( datele de intrare ale problemei ), MI are ca sarcină exploatarea regulilor şi generarea răspunsurilor la întrebările puse de utilizatori în scopul determinării soluţiei problemei analizate.
10.04.2011 32
Cap. 1. Sisteme expert
În acest sens, cu regulile existente în baza de cunoştinţe se construiesc arbori de inferenţă sau de căutare care au ca noduri premisele/condiţiile, iar ca ramuri arcele care conectează diferitele premise. Există diverse procedee sau mecanisme de inferenţă care traversează acest arbore în sensuri diferite, conceptul de “CĂUTARE” fiind unul esenţial în programele de IA.Cele mai cunoscute metode de inferenţă sunt:
înlănţuirea înainte - este un proces de inferenţă deductiv, condus de date;înlănţuirea înpoi - este un proces de inferenţă inductiv, condus de scop;înlănţuirea hibridă - este un proces de inferenţă care combină inducţia înainte şi inducţia înapoi.
10.04.2011 33
Cap. 1. Sisteme expert
Principiul de funcţionare al MI.
Reguli
Sistem achizi ie de dateţ
UtilizatorFapte
Motor de inferenţe
reguli aplicabile
Reguli
Regulă
Alteacþiuni
Selectare
Folosind baza de cunoştinţe (faptele şi regulile), MI construieşte dinamic raţionamentele alegând regulile ce vor fi aplicate şi ordinea de înlănţuire a acestora până când se ajunge la scopul propus.
10.04.2011 34
Cap. 1. Sisteme expert
Ciclul de bază al motorului de inferenţă
Este independent de modul de raţionament utilizat şi comportă patru etape:
SELECŢIA: în această etapă se extrag din baza de reguli şi din baza de fapte elementele care caracterizează subdomeniul de rezolvare a problemei. Această etapă este necesară atunci când baza de cunoştinţe este mare, încercând să acopere mai multe domenii ale cunoaşterii.
Reguli posibile Faptele selecţionate
10.04.2011 35
Cap. 1. Sisteme expert
FILTRAJUL ( pattern matching ) constă în compararea premiselor regulilor selecţionate anterior cu faptele ce caracterizează problema de rezolvat, pentru a determina submulţimea regulilor declanşabile. În urma acestei etape pot rezulta:
o regulă aplicabilă care este declanşată pentru a genera noi fapte;nici o regulă aplicabilă: s-a ajuns într-o stare de eşec pe care SE o semnalează, iar utilizatorul va trebui să răspundă la o serie de întrebări în scopul datelormai multe reguli aplicabile: s-a generat o stare conflictuală care trebuie rezolvată.
10.04.2011 36
Cap. 1. Sisteme expert
REZOLVAREA CONFLICTELOR este necesară atunci când din etapa de filtraj au rezultat mai multe reguli declanşabile şi trebuie aleasă una pentru a fi executată. Pentru aceasta se utilizează diverse criterii dintre care se amintesc:
prima regulă din listă; regula cu cel mai mare număr de fapte în premisă; regula cea mai des utilizată.
De alegerea făcută în această etapă depind performanţele MI. Este dificil de indicat unul sau altul dintre criterii. Alegerea depinde de contextul în care se găseşte baza de cunoştinţe în momentul respectiv.
10.04.2011 37
Cap. 1. Sisteme expert
EXECUŢIA REGULII SELECTATE constă în adăugarea uneia sau mai multor fapte în “baza de fapte”ca o consecinţă a aplicării regulii respective. Este posibil ca în această etapă să se facă apel şi la proceduri externe ( acces la baze de date, calcul tabelar sau la proceduri de calcul scrise în limbaje de nivel înalt ) sau la întrebări puse utilizatorului.
Pentru rezolvarea unei probleme MI execută mai multe cicluri de bază şi se opreşte în funcţie de modul de raţionament utilizat.
10.04.2011 38
Cap. 1. Sisteme expert
Baza de reguli (BR)
Reguliposibile
SELEC IEŢ
Baza de fapte (BF)
Fapteselec ionateţ
FILTRAJ
Regulideclan abileş
REZOLVARECONFLICTE
Regulire inuteţ
EXECU IEREGULI
Ţ
10.04.2011 39
Cap. 1. Sisteme expert
Module complementare
Modulul de achiziţie de cunoştinţe - realizează transferul cunoştinţelor de la experţii în domeniu către sistemul expert
10.04.2011 40
Cap. 1. Sisteme expert
Extragerea cunoştinţelor de la un expert uman cu ajutorul unor mijloace specifice sau prin metoda interviurilor este un proces eterogen, numit ingineria cunoaşterii şi constă în:
Identificare: definirea corectă a problemei şi determinarea caracteristicilor sale;Conceptualizare: determinarea conceptelor care să sprijine reprezentarea cunoştinţelor;Formalizare: alegerea unor metode de reprezentare a cunoştinţelor şi a mecanismului de inferenţă; Implementare: reprezentarea propriu-zisă a cunoştinţelor în formalismul ales;Testare: verificarea cunoştinţelor şi validarea sistemului.
10.04.2011 41
Cap. 1. Sisteme expert
Interfaţa cu utilizatorul: Este partea din program care permite utilizatorului:
să pună întrebări sistemului expert;să introducă noi informaţii; să primească diferite recomandări de la SE.
Aprecierea utilizatorului asupra unui sistem expert depinde în mare măsură de asemănarea între modul de reprezentare a informaţiilor de către SE şi modelul pe care utilizatorul îl are în “mintea sa” despre problema care se rezolvă.
10.04.2011 42
Cap. 1. Sisteme expert
Modulul explicativ SE trebuie să aibă capacitatea de a furniza explicaţii operatorului în legătură cu raţionamentul folosit pentru a ajunge la o anumită recomandare sau decizie. Cu cât sunt mai explicit reprezentate cunoştinţele în baza de cunoştinţe, cu atât este mai eficient procesul explicativ, deoarece cunoştinţele şi metodele de utilizare a acestora sunt elemente fundamentale.
10.04.2011 43
Cap. 1. Sisteme expert
STRATEGII DE CĂUTARE A SOLUŢIEI
Consideraţii generaleProblemele care pot fi rezolvate folosind tehnici ale IA sunt probleme complex computaţionaleDeterminarea soluţiei se face prin deplasarea în spaţiul de definiţie al problemei denumit şi spaţiul de căutare sau universul problemei de rezolvat. Spaţiul de căutare este constituit dintr-un număr foarte mare de stări, fiecare descriind o situaţie posibilă; datorită restricţiilor problemei, o parte dintre stări sunt stări interzise în care nu se poate ajunge niciodată.
10.04.2011 44
Cap. 1. Sisteme expert
Concluzie: rezolvarea problemelor poate fi văzută ca un proces de identificare sau de construire a unui obiect având anumite caracteristici şi care reprezintă soluţia problemeiAceastă activitate implică existenţa următoarelor elemente:
O structură simbolică care să poată reprezenta descrierea iniţială a problemei si fiecare obiect candidat la soluţie (este structura folosită pentru reprezentarea cunoştinţelor)O mulţime de instrumente computaţionale capabile să transforme descrierea unui obiect (structură simbolică) într-o nouă descriere în scopul de a investiga sistematic toţi candidaţii la soluţie. Aceste instrumente sunt constituite din operatorii de transformare sau regulile de producţie
10.04.2011 45
Cap. 1. Sisteme expert
O strategie de control care să indice ordinea de aplicare a transformărilor astfel încât soluţia problemei să fie găsită cât mai repede.
Procesul de determinarea a soluţiei porneşte dintr-o stare iniţială Si cunoscută şi, prin aplicarea unor reguli (operatori de transformare) care permit trecerea dintr-o stare în altă stare, se urmăreşte ajungerea într-o stare finală Sf care constituie soluţia sau o soluţie a problemei de rezolvatDeci soluţia problemei se obţine printr-un proces de căutare şi nu prin aplicarea unei secvenţe de transformări specificate dinainte.
10.04.2011 46
Cap. 1. Sisteme expert
În procesul de căutare se utilizează grafuri: fiecare stare este reprezentată printr-un nod, iar operatorii de transformare prin arce. Definirea unei probleme de căutare se face folosind următorul formalism:
D este mulţimea stărilor sau universul problemei;T – mulţimea transformărilor;
O soluţie a problemei P, notată T*, este o secvenţă de transformări cu următoarea proprietate:
( ) ( )Ti fP S D S D= ∈ ⎯⎯→ ∈
( )( )( )* * *2 1...f n iS t t t S=
10.04.2011 47
Cap. 1. Sisteme expert
Algoritmul generic de căutare
1. Stabileşte starea/stările iniţială/iniţiale Si2. Stabileşte starea curentă 3. Repetă
3.1. Selectează un operator de transformare t posibil de aplicat stării curente Sc
3.2. Aplică operatorul t asupra stării si obţine o nouă stare
3.3. Stabileşte până când Sc este stare finală
4. Sfârşit.
c iS S←
( )'cS t S=
'cS S←
10.04.2011 48
Cap. 1. Sisteme expert
Observaţii:Algoritmul este nedeterminist deoarece pasul 3.1 nu specifică cum se selectează operatorul sau transformarea t de aplicat. Selectarea transformărilor si memorarea transformărilor efectuate constituie strategia de control. Strategia de control trebuie să fie sistematică, adică trebuie să satisfacă următoarele cerinţe:
să prezinte proprietatea de completitudine, adică să garantează faptul că strategia produce soluţia, dacă aceasta există; să asigure protecţie împotriva ineficienţei prelucrărilor repetate
Altfel spus:nu lasă nici o piatră neîntoarsă;nu întoarce nici o piatră de mai multe ori.
10.04.2011 49
Cap. 1. Sisteme expert
EXEMPLU
Se consideră un sistem aflat în starea iniţială caracterizată de proprietăţile P1, P2 şi P3.
Sistemul evoluează prin adăugarea de noi proprietăţi conform următoarelor transformări sau reguli:
t1: DACĂ (P1 ŞI P2) ATUNCI P4t2: DACĂ (P2 ŞI P3) ATUNCI P5t3: DACĂ (P1 ŞI P4) ATUNCI P6t4: DACĂ (P5 ŞI P6) ATUNCI P7t5: DACĂ (P2 ŞI P5) ATUNCI P7
10.04.2011 50
Cap. 1. Sisteme expert
Evoluţia sistemului are loc respectând convenţia: dacă între starea iniţială şi starea curentă s-a aplicat o anumită secvenţă de transformări, atunci niciuna dintre transformările folosite nu mai poate fi aplicată stării curente.
Se cere să se stabilească secvenţa de transformări ce conduce sistemul în starea finală care conţine proprietatea P7.
10.04.2011 51
Cap. 1. Sisteme expertSecvenţa de transformări şi soluţii posibile
{ }{ }
*7 1 2 5*8 2 1 5
, ,
, ,
T t t t
T t t t
=
= P , 1 P , P2 3
P , 1 P , P ,P , P , P ,
P
2 3
4 5 6
7
P , 1 P ,P ,P ,P , P
2 3
4 5 7
P , 1 P ,P ,P , P , P
2 3
4 5 6
P , 1 P ,P ,P ,P
2 3
4 5
P , 1 P ,P ,P
2 3
4
P , 1 P ,P ,P
2 3
5
P , 1 P ,P ,P , P
2 3
5 7
P , 1 P , P ,P , P
2 3
4 6
t1
t1
t2
t2
t2
t3
t3
t4
t5
t5
t5
{ }{ }{ }
*1 1 2 3 4*2 2 1 3 4*3 1 3 2 4
, , ,
, , ,
, , ,
T t t t t
T t t t t
T t t t t
=
=
=
{ }{ }{ }
*4 1 2 3 5*5 2 1 3 5*6 1 3 2 5
, , ,
, , ,
, , ,
T t t t t
T t t t t
T t t t t
=
=
=
{ }*9 2 5,T t t=
10.04.2011 52
Cap. 1. Sisteme expert
Acest exemplu evidenţiază următoarele aspecte:O parte dintre soluţii conţin aceleaşi transformări, dar în succesiuni diferite. Acest fapt implică revenirea în stări deja explorate şi apariţia unor bucle în graful de căutare. Dacă se elimină buclele rezultă patru soluţii posibile:
{ }*1 1 2 3 4, , ,T t t t t= { }*
4 1 2 3 5, , ,T t t t t=
{ }*7 1 2 5, ,T t t t= { }*
9 2 5,T t t=
Numărul transformărilor utilizate diferă de la o soluţie la alta, existând posibilitatea obţinerii soluţiei printr-un nr. minim de transformări.
10.04.2011 53
Cap. 1. Sisteme expert
Observaţii:Comportarea programelor de inteligentă artificială poate fi caracterizată ca un proces de căutare în care diverse transformări aplicabile universului problemei sunt încercate până se determina soluţia problemei. În general, pentru a determina soluţia este necesară evaluarea unui număr mare de stări intermediare (obiecte candidate la soluţie), iar folosirea căutării exhaustive este exclusă.Informaţia euristică joacă un rol foarte important în cadrul procesului de căutare contribuind la reducerea numărului de stări investigate pentru obţinerea soluţiei şi creşterea eficienţei procesului de rezolvare. Informaţia euristică este reprezentată printr-o funcţie euristică asociată fiecărei stări, care estimează cât de promiţătoare este acea stare din punct de vedere al avansului spre soluţie. Funcţiile euristice depind şi se stabilesc pe baza cunoştinţelor specifice problemei sau clasei de probleme de rezolvat.
10.04.2011 54
Cap. 1. Sisteme expert
Reprezentarea soluţiei problemeiReprezentarea soluţiei problemei
Reprezentarea soluţieiproblemei prinspaţiul stărilor
Reprezentarea soluţieiproblemei prinspaţiul stărilor
Reprezentarea soluţieiproblemei prin
grafuri SI / SAU
Reprezentarea soluţieiproblemei prin
grafuri SI / SAU
( ), ,i fS O S ( ), ,i eS O P
10.04.2011 55
Cap. 1. Sisteme expert
Reprezentarea soluţiei problemei prin spaţiul stărilorSpaţiul de căutare are forma unui graf orientat în care nodurile sunt identificate prin stări, iar arcele reprezintă aplicarea unor operatori pentru a transforma o stare în altă stareReprezentarea este formată din tripletul (Si,O, Sf) în care:
Si este starea iniţială;O - mulţimea de operatorilor aplicabili stărilor universului
problemei pentru a ajunge în noi stări: in fiecare stare dată, numai o parte din operatori pot fi aplicaţi;
Sf - mulţimea stărilor finale; aceasta poate fi constituită din una sau mai multe stări.
10.04.2011 56
Cap. 1. Sisteme expert
Prin urmare, în această reprezentare, o soluţie a problemei este o secvenţa de operatori care transformă starea iniţială în starea finală şi reprezintă o cale între aceste două stări în graf. Iniţial graful spaţiului de căutare este specificat implicit de reprezentare prin tripletul (Si, O, Sf ). Pe măsură ce procesul de căutare a soluţiei avansează o parte din acest graf devine explicită. Porţiunea din graful spaţiului de căutare astfel construită reprezintă partea explorată a spaţiului de căutare.
10.04.2011 57
Cap. 1. Sisteme expertExemplu: Problema comis voiajorului
A
B
E
D
C
7
106
10
10
136
7
5
9
(a) Harta oraselor de parcurs
{A}
{A,B} {A,C} {A,D} {A,E}
7 6 10 13
... ... ...5{A,C,D}
{A,C,D,E}
6
(b) O portiune din spatiul de cautare a solutiei
Generarea tuturor traseelor posibile şi compararea costurilor asociate pentru a găsi traseul optim este un proces ineficient din punct de vedere computaţional, mai ales în cazul unui număr mare de oraşe. De aceea, pentru rezolvarea acestei probleme se face apel la tehnicile euristice de căutare.
10.04.2011 58
Cap. 1. Sisteme expert
Există probleme care pot fi rezolvate printr-o tehnică numită descompunerea problemei în subprobleme.
Caracteristica acestei clase de probleme este aceea că problema pusă de un obiect candidat la soluţie este văzută ca o conjuncţie de subprobleme care pot fi rezolvate independent unele de altele.
Reprezentarea soluţiei problemei prin grafuri SI/SAU
10.04.2011 59
Cap. 1. Sisteme expert
Mecanismul de rezolvare a problemelor din această clasă constă în :
descompunerea problemei iniţiale în subproblemele care trebuie rezolvate;descompunerea subproblemelor în alte subprobleme;continuarea procesului până când se obţine o descompunere a problemei iniţiale in subprobleme elementare a căror rezolvare este cunoscută.
Spaţiul de căutare al unei astfel de rezolvări a problemei are forma unui graf SI/SAU. Acesta este un caz particular al unui hipergraf.
10.04.2011 60
Cap. 1. Sisteme expert
Definiţie: o reprezentare a soluţiei problemei prin grafuri SI/SAU este formată din tripletul (Si , O , Pe) în care:
Si este descrierea stării iniţiale;O – mulţimea operatorilor de transformare care
descompun problema în subprobleme; Pe – mulţimea de probleme elementare.
Observaţie: mulţimea operatorilor conţine operatori aplicabili stărilor universului problemei pentru a genera noi stări; în fiecare stare dată, numai o parte din operatori pot fi aplicaţi.
10.04.2011 61
Cap. 1. Sisteme expert
Reguli pentru generarea grafurilor SI/SAU
R1 Fiecare nod reprezintă fie o singură problemă, fie o mulţime de probleme ce trebuie rezolvate.
R2 Un nod care reprezintă o singură problemă nu are descendenţi. Problema este fie o problemă elementară, fie o problemă neelementară care nu se mai poate descompune în alte subprobleme.
R3 Nodurile care reprezintă mulţimea de subprobleme în care s-a descompus o problemă prin aplicarea unui operator de descompunere se numesc noduri SI.
R4 Nodurile ce reprezintă descompuneri alternative ale unei probleme în subprobleme se numesc noduri SAU. Aceste noduri au ca descendenţi noduri SI.
10.04.2011 63
Cap. 1. Sisteme expert
Într-un graf SI/SAU există două tipuri de noduri: noduri rezolvate noduri nerezolvabile:
Un nod este rezolvat dacă:este un nod terminal etichetat cu o problemă elementară;este un nod SI, iar toţi succesorii lui sunt noduri rezolvate;este un nod SAU si cel puţin un succesor al acestuia este nod rezolvat.
Un nod este nerezolvabil dacă:este un nod terminal etichetat cu o problemă neelementară care nu se mai poate descompune în subprobleme;este un nod SI cu cel puţin un succesor nerezolvabil;este un nod SAU cu toţi succesorii nerezolvabili.
10.04.2011 64
Concluzie O problemă are soluţie dacă există o secvenţă de operatori care fac ca nodul corespunzătordescrierii iniţiale a problemei să devină nod rezolvat.
Exemplu. Problema turnurilor din HanoiSe cere să se mute n=3 discuri de pe tija A pe tija C,
utilizând tija intermediară B cu restricţia ca un disc să fie aşezat fie pe o tija liberă, fie peste un disc de o dimensiune mai mare decât el.
10.04.2011 65
Cap. 1. Sisteme expert
A B C A B C
(a) Stare initiala (b) Stare finala
Mulţimea operatorilor de descompunere este formată dintr-un singur operator, cu trei componente şi anume:
mută n-1=2 discuri de pe tija i pe tija j, utilizând tija k;mută un disc de pe tija i pe tija k;mută n-1=2 discuri de pe tija j pe tija k, utilizând tija i.
Singura problema elementară este aceea de a muta un singur disc de peo tijă pe o altă tijă respectând restricţia problemei.Problema având un singur operator de descompunere, spaţiul de căutare va conţine numai noduri probleme elementare şi noduri SI.
10.04.2011 66
Cap. 1. Sisteme expert
n = 3A la C
n = 2 n = 2
n = 1
A la B
A la C
B la C
n = 1A la C
n = 1A la B
n = 1C la B
n = 1B la A
n = 1B la C
n = 1A la C
(c) Arborele SI/SAU de descompunere in subprobleme
O - operator de descompunere
10.04.2011 67
Cap. 1. Sisteme expert
Observaţii vizând soluţionarea problemelor de IA
Orice problemă poate fi solutionată prin ambele metode de reprezentare analizate. Totuşi, pentru o anumităproblemă este mai adecvată o reprezentare sau alta.Anumite probleme conduc în mod natural la o reprezentare a solutiei prin spatiul starilor, asa cum este problema comis voiajorului, problema mozaicului de 8 numere, problema celor 8 regine etc. O astfel de rezolvare corespunde unui rationament direct pentru a solutiona problema sau unui control condus de date.
10.04.2011 68
Cap. 1. Sisteme expert
Alte probleme, cum ar fi problema turnurilor din Hanoi,problema cintaririi monezilor, conduc in mod natural la o rezolvare prin descompunerea problemei în subprobleme. O astfel de rezolvare corespunde unui rationament invers pentru rezolvarea problemei sau unui control condus de scopuri.
10.04.2011 69
Cap. 1. Sisteme expert
Pentru alegerea unei strategii de căutare trebuie să se ţină cont de:
Completitudinea strategiei – stabileşte dacă strategia asigură sau nu găsirea soluţiei în cazul în care aceasta există.Optimalitatea soluţiei – este dată de capacitatea strategiei de a obţine o soluţie optimală, suboptimală sau pur si simplu o soluţie.Complexitatea strategiei – se referă la complexitatea exprimată în timp de calcul şi memorie (efort computaţional) a algoritmului utilizat.
Strategii de căutare de bază
10.04.2011 70
Cap. 1. Sisteme expert
Caracterizarea unei strategii de căutare se poate face după două criterii:C1: capacitatea mecanismului de rezolvare de a reveni
într-o stare intermediară anterioară:Strategii de căutare irevocabile;Strategii de căutare tentative.
C2: după cantitatea de informaţie folosită la găsirea soluţiei:
Strategii de căutare neinformateStrategii de căutare informate
10.04.2011 71
Cap. 1. Sisteme expert
Strategii de căutare irevocabile.Principiul: Un operator aplicabil este selectat şi aplicat unei stări pentru a
obţine o nouă stare, iar starea anterioară este uitată (nu este memorată) şi, prin urmare, nu se mai poate reveni în ea .
Exemplu: strategia de căutare a alpinistului. se bazează pe criterii de optim local;asemănător unui alpinist care doreşte sa ajungă repede pe vârful unui munte, strategia alege starea următoare de nivel maxim pe baza unei funcţii de evaluare a stărilor;strategia este irevocabilă deoarece pentru o stare curentă, după generarea stărilor următoare şi alegerea stării de nivel maxim ca noua stare curentă, celelalte stări sunt uitate. Deci nu se mai poate reveni într-una din stările anterioare stării curente sau într-una din alternativele stării curente. strategia alpinistului, deşi simplă si puţin consumatoare de memorie, prezintă o serie de limitări ca de exemplu blocarea intr-un maxim local fără a putea obţine maximul global.
10.04.2011 72
Cap. 1. Sisteme expert
Strategii de căutare tentative
Principiul: La aplicarea unui operator starea curentă este memorată astfel încânt procesul de căutare să poată reveni ulterior în stările anterioare stării curente.
Dacă starea anterioară la care se poate reveni în timpul căutării se află numai pe calea curentă între starea iniţială si starea finală, strategia de căutare este o strategie tentativă de tip "backtracking". Aceasta este, de exemplu, strategia utilizata de limbajul Prolog.
Dacă starea anterioară în care se poate reveni se află pe orice cale deja parcursă în expandarea spaţiului de căutare, strategia este de căutare tentativă generală pe grafuri.
10.04.2011 73
Cap. 1. Sisteme expert
Strategii de căutare neinformate.
Principiul: Considerarea stărilor următoare de inspectat se face după o ordine arbitrară, anterior stabilită.
inspectează sistematic toate stările spaţiului de căutare până în momentul găsirii stării finale.
Cele mai importante strategii de acest fel sunt: căutarea pe nivel sau căutarea în lăţime;căutarea in adâncime.
10.04.2011 74
Cap. 1. Sisteme expert
Strategii de căutare informatePrincipiul: Considerarea stărilor următoare de inspectat se face
după criterii euristice. Strategia foloseşte o funcţie de evaluare a situaţiei globale sau locale care indică starea următoare cea mai promiţătoare din punct de vedere al avansului spre soluţie.Strategiile de căutare euristice încearcă reducerea numărului de stări din spaţiul de căutare inspectate până la atingerea stării finale, pe baza diverselor criterii, cum ar fi funcţiile euristice. Exemple: strategia alpinistului, strategia de căutare "best-first", algoritmul A* si algoritmul AO*. Algoritmii A* si AO* urmăresc în principal, pe lângă reducerea numărului de stări inspectate, găsirea soluţiei optime.
10.04.2011 75
Cap. 1. Sisteme expert
Costul computaţional
Costul computaţional total al unui program de rezolvare a problemelor de IA depinde de locul unde se situează strategia de control în spectrul neinformat/informat şi are două componente:
costul aplicării operatorilor, sau costul parcurgerii spaţiului de căutare între starea iniţială si starea finală;
costul controlului, sau costul evaluării si selecţiei celei mai promiţătoare stări următoare.
10.04.2011 76
Cap. 1. Sisteme expert
Grad deinformare
CostComputational
Cost total
Cost control(cost evaluare stari)Cost parcurgere
(cost aplicareoperatori)
Neinformat Informat
10.04.2011 77
Cap. 1. Sisteme expert
Observaţii:O strategie de căutare complet neinformată implică:
un cost redus al controlului;un cost ridicat al parcurgerii spaţiului de căutare deoarece necesită aplicarea unui număr mare de operatori înaintea găsirii unei soluţii.
O strategie de control complet informată despre domeniul problemei implică:
un cost ridicat al controlului deoarece poate necesita calcule complicate pentru evaluarea meritului stărilor;un cost minim de parcurgere a spaţiului de căutare datorita numărului redus de operatori aplicaţi până la găsirea soluţiei.
Există un grad optim de informare pentru care costul total este minim.
10.04.2011 78
Cap. 1. Sisteme expert
În funcţie de aplicaţie, proiectantul programului trebuie să încerce determinarea celei mai bune variante de pondere a costurilor.
Obţinerea unui cost computaţional optim este un aspect esenţial deoarece problemele de căutare sunt probleme de complexitate timp exponenţială.
10.04.2011 79
Cap. 1. Sisteme expertCăutări neinformate în spaţiul stărilor
Formularea problemeiSe consideră:
un graf definit implicit prin mulţimea operatorilor asociaţi arcelor ;nodul sau mulţimea de noduri ce definesc starea iniţială Si, adică condiţiile iniţiale ale problemei de rezolvat ;nodul sau mulţimea de noduri ce definesc starea finală , adică obiectivele sau cerinţele problemei .
Pentru rezolvarea problemei este necesar să se găsească o cale între starea iniţială şi starea finală. Un proces de căutare
10.04.2011 80
Cap. 1. Sisteme expert
După cum s-a prezentat, principiul care se află la baza algoritmului generic de căutare constă în explorarea incrementală a căilor ce pornesc din nodurile aferente stării iniţiale şi foloseşte noţiunea de frontieră pentru a delimita nodurile explorate de cele care nu au fost încă explorate.
În parcurgerea spaţiului de căutare un nod poate fi:necunoscut - nodul aparţine părţii neexplorate a spaţiului de căutare;evaluat - nodul este cunoscut dar fie nu se cunoaşte nici un succesor al lui, fie se cunosc numai o parte dintre aceştia;expandat - nodul este cunoscut si, in plus, se cunosc toţi succesorii lui
10.04.2011 81
Cap. 1. Sisteme expert
Expandarea unui nod înseamnă generarea tuturor succesorilor săi, adică aplicarea tuturor operatorilor legali stării curente Sc aferentă nodului.
În procesul de căutare se vor folosi doua liste:
LF – lista frontieră care conţine nodurile evaluate, adică frontiera spaţiului de căutare parcurs (explicitat) spre partea necunoscută a acestuia;
LT – lista teritoriu care conţine nodurilor expandate, adică partea cunoscută a spaţiului de căutare.
10.04.2011 82
Cap. 1. Sisteme expert
STRATEGII DE CĂUTARE DE BAZĂcăutare pe nivel şi căutarea în adâncime
Ipoteze:Spaţiul de căutare este arbore, adică între starea iniţială şi cea finală există o cale unică. Rezultă că toate stările generate pe parcursul căutării sunt unice, adică nu au mai fost generate anterior.
La fiecare expandare a unui nod se stabileşte o legătură de la fiecare nod succesor la nodul expandat. In momentul descoperirii nodului stare finală aceste legaturi permit reconstruirea caii spre soluţie.
10.04.2011 83
Cap. 1. Sisteme expert
Definiţie: într-o reprezentare a soluţiei problemei prin spaţiul stărilor adâncimea unui nod se defineşte astfel:
în care Sp este predecesorul stării curente Sc.
Ad( )=0iS unde Si este nodul stare iniţială;
Ad( )=Ad( )+1c pS S
10.04.2011 84
Cap. 1. Sisteme expert
Căutarea pe nivel sau în lăţime
este o strategie de căutare care expandează stările următoare în ordinea apropierii faţă de nodul stare iniţială Si.
tratează lista frontieră LF folosind o strategie de tipul FIFO (First In First Out).
Nodul din frontieră care se elimină este primul din listă, iar succesorii săi sunt adăugaţi la sfârşitul listei.
10.04.2011 85
Cap. 1. Sisteme expert
Algoritmul strategiei căutării pe nivel în spaţiul stărilor
1. Creează listele LF ←{Si} si LT ←{}2. DACĂ LF ={} ATUNCI întoarce INSUCCES /* nu există soluţie */3. Elimină primul nod Sc din LF si-l inserează în LT4. Expandează nodul Sc
4.1. Generează toţi succesorii direcţi ai nodului Sc
4.2. Pentru fiecare succesor Sj ( 1 ≤ j ≤ m ) al lui Sc execută4.2.1. Stabileşte legătura Sj ← Sc 4.2.2. DACĂ Sj este stare finală ATUNCI:
i. soluţia este {Sj≡ Sf , Sc … Sj,}ii. întoarce SUCCES /* s-a găsit o soluţie */
4.2.3. Insereaza Sj în LF, la sfârşit5. repeta de la 2
10.04.2011 86
Cap. 1. Sisteme expert
Exempluse consideră graful din figură în care nodul n1 reprezintă starea iniţială, iar nodul n10 starea finală.ordinea în care se explorează diversele căi în graful de căutare depinde de ordinea în care se generează şi se inserează în LF succesorii nodului expandat . În cele ce urmează considerăm că succesorii unui nod se generează în ordinea indicelui numeric.
n1
n2
n4
n8 n9 n10
n5 n6 n7
n3
10.04.2011 87
Cap. 1. Sisteme expert
Pas 1. Iniţializări LF ←{n1} si LT ←{} Pas 2 . Elimină n1 din LF şi-l inserează în LT:
LF ={} si LT={n1} Pas 3. Generează succesorii lui n1 si-i inserează în LF:
LF ={n2 , n3} si LT={n1}Pas 4. Elimină n2 din LF şi-l inserează în LT:
LF ={n3} si LT={n1 , n2}Pas 5. Generează succesorii lui n2 si-i inserează în LF la sfârşit:
LF ={n3 , n4 , n5} si LT={n1 , n2}Pas 6. Elimină n3 din LF şi-l inserează în LT:
LF ={n4 , n5} si LT={n1 , n2 ,n3}Pas 7. Generează succesorii lui n3 si-i inserează în LF la sfârşit:
LF ={n4 , n5 , n6 , n7} si LT={n1 , n2 ,n3}
10.04.2011 88
Cap. 1. Sisteme expert
Pas 8. Elimină n4 din LF şi-l inserează în LT:LF ={n5 , n6 , n7} si LT={n1 , n2 , n3 , n4}Obs. Deoarece n4 nu are succesori, nu se adaugă alte noduri în lista LF.
Pas 9. Elimină n5 din LF şi-l inserează în LT:LF ={n6 , n7} si LT={n1 , n2 , n3 , n4 , n5}
Pas 10. Generează succesorii lui n5 şi-i inserează în LF la sfârşit: LF ={n6 , n7 , n8 , n9} si LT={n1 , n2 , n3 , n4 , n5}
Pas 11. Elimină n6 din LF şi-l inserează în LT: LF ={n7 , n8 , n9} si LT={n1 , n2 , n3 , n4 , n5 , n6}
Obs. Deoarece n6 nu are succesori, LF nu se modifică. Pas 12. Elimină n7 din LF şi-l inserează în LT:
LF ={n8 , n9} si LT={n1 , n2 , n3 , n4 , n5 , n6 , n7}Pas 13. Generează succesorii lui n7 şi-i inserează în LF la sfârşit:
LF ={n8 , n9 , n10} si LT={n1 , n2 , n3 , n4 , n5 , n6 , n7}
10.04.2011 89
Cap. 1. Sisteme expert
Deoarece nodul final n10 a apărut în frontieră, se consideră procesul de căutare încheiat şi se specifică soluţia: {n10 , n7 , n3 , n1}
Observaţii:
Căutarea poate fi uneori lungă şi complex computaţională din punct de vedere al spaţiului de memorie utilizat deoarece pentru fiecare nivel sunt generate toate stările succesoare posibile.
Cu toate acestea, strategia de căutare pe nivel garantează găsirea soluţiei, în cazul în care aceasta există şi, în plus, găseşte cel mai scurt drum spre soluţie în termenii numărului de tranziţii de stări executate.
10.04.2011 90
Cap. 1. Sisteme expert
Căutarea în adâncimeeste strategia cea mai frecvent utilizată în aplicaţiile practice;
expandează stările cel mai recent generate, adică nodurile din lista LF cu adâncimea cea mai mare;
această strategie parcurge o cale de la starea iniţială până la o stare ce poate fi starea finală sau care nu mai are nici un succesor. În acest ultim caz se aplică mecanismul backtracking revenindu-se pe nivelurile anterioare şi se încearcă explorarea altor căi posibile.
lista frontieră LF este tratată ca o stivă folosind o tehnică de tipul LIFO (Last In First Out).
10.04.2011 91
Cap. 1. Sisteme expert
Observaţii:Strategia căutării în adâncime nu garantează obţinerea unei soluţii a problemei, chiar în cazul în care aceasta există.
O astfel de situaţie poate să apară în cazul unui spaţiu de căutare infinit iar ramura pe care s-a plecat în căutare nu conţine soluţia.
Pentru a evita intrarea într-o buclă infinită se introduce o limită maximă a adâncimii de căutare, AdMax. Dacă această limită a fost atinsă fără a se găsi soluţia, atunci strategia revine si inspectează stări de pe nivelurile inferioare lui AdMax dar aflate pe căi diferite.
Apare următorul dezavantaj: soluţia care s-ar găsi pe calea iniţială la o adâncime mai mare decât AdMax este pierdută.
Algoritmul căutării în adâncime prezintă avantajul generării unui număr de stări mai mic comparativ cu algoritmul căutării pe nivel.
10.04.2011 92
Cap. 1. Sisteme expert
Algoritmul strategiei căutării în adâncime în spaţiul stărilor
1. Creează listele LF ←{Si} si LT ←{}2. DACĂ LF ={} ATUNCI întoarce INSUCCES /* nu există soluţie */3. Elimină primul nod Sc din LF si-l inserează în LT DACĂ Ad (Sc)=AdMax ATUNCI repetă de la 24. Expandează nodul Sc
4.1. Generează toţi succesorii direcţi ai nodului Sc
4.2. Pentru fiecare succesor Sj ( 1 ≤ j ≤ m ) al lui Sc execută4.2.1. Stabileşte legătura Sj ← Sc 4.2.2. DACĂ Sj este stare finală ATUNCI:
i. soluţia este {Sj≡ Sf , Sc … Sj,}ii. întoarce SUCCES /* s-a găsit o soluţie */
4.2.3. Insereaza Sj în LF, la început5. repeta de la 2
10.04.2011 93
Cap. 1. Sisteme expert
Exempluse consideră graful din figură în care nodul n1 reprezintă starea iniţială, iar nodul n10 starea finală.ordinea în care se explorează diversele căi în graful de căutare depinde de ordinea în care se generează şi se inserează în LF succesorii nodului expandat . În cele ce urmează considerăm că succesorii unui nod se generează în ordinea indicelui numeric.
n1
n2
n4
n8 n9 n10
n5 n6 n7
n3
10.04.2011 94
Cap. 1. Sisteme expert
Pas 1. Iniţializări LF ←{n1} si LT ←{} Pas 2 . Elimină n1 din LF şi-l inserează în LT:
LF ={} si LT={n1} Pas 3. Generează succesorii lui n1 si-i inserează în LF: conform convenţiei
adoptate se generează şi se introduce în listă n2 şi apoi n3: rezultă LF ={n3, n2} si LT={n1}
Pas 4. Elimină n3 din LF şi-l inserează în LT:LF ={n2} si LT={n1 , n3}
Pas 5. Generează succesorii lui n3 si-i inserează în LF la început:LF ={n7 , n6 , n2} si LT={n1 , n3}
Pas 6. Elimină n7 din LF şi-l inserează în LT:LF ={n6 , n2} si LT={n1 ,n3 , n7}
Pas 7. Generează succesorii lui n7 si-i inserează în LF la început: LF ={n10 , n6 , n2} si LT={n1 , n3 , n7 }
Deoarece nodul final n10 a apărut în frontieră, se consideră procesul de căutare încheiat şi se specifică soluţia: {n10 , n7 , n3 , n1}
10.04.2011 95
Cap. 1. Sisteme expert
Algoritmul de căutare în adâncime cu nivel iterativ ( algoritmul lui Korf ).
elimină dezavantajele specifice celor două strategii de căutare de bază; algoritmul realizează la început o căutare în adâncime în spaţiul stărilor cu o adâncime maximă de căutare AdMax specificată. DACĂ starea finală nu a fost găsită, ATUNCI se reia căutarea în adâncime cu AdMax+1;continuă procesul până se găseşte solţia;la fiecare iteraţie algoritmul realizează o căutare în adâncime completă corespunzătoare valorii curente AdMax. între două iteraţii succesive nu se reţine nici o informaţie despre spaţiul de căutare. se garantează găsirea soluţiei, dacă aceasta există, precum şi a drumului cel mai scurt către soluţie
10.04.2011 96
Cap. 1. Sisteme expert
În cazul în care spaţiul de căutare nu este un arbore, ci un graf oarecare, pentru a evita reconsiderarea unei stări analizate anterior, pasul de inserare a stării Sj în lista LF (pasul 4.2.3) se modifică astfel:
4.2.3‘ DACĂ ATUNCI inserează Sj în LF, la sfirsit respectiv la
început în funcţie de strategie.
jS LF LT∉ ∪
10.04.2011 97
Cap. 1. Sisteme expert
Observaţii:Ambele tipuri de căutări realizează un raţionament direct, pornind în rezolvarea problemei de la starea iniţială si generând arborele de căutare a stării finale. Acest mod de abordare corespunde raţionamentului deductiv.Pentru rezolvarea anumitor probleme se poate proceda invers, executând strategiile începând din starea finală şi căutând starea iniţială. Acest mod de abordare corespunde raţionamentului inductiv.În anumite cazuri se poate utiliza o combinaţie între raţionamentul direct si cel invers, adică un raţionament bidirecţional în care se caută soluţia pornind simultan din starea iniţială si cea finală. În cazul acestei strategii, dacă se utilizează căutarea în adâncime există pericolul ca cei doi arbori generaţi simultan, unul pe calea directă şi celălalt pe calea inversă, să nu aibă noduri intermediare comune (să nu se întâlnească).
10.04.2011 98
Cap. 1. Sisteme expert
Strategiile de căutare pe nivel si în adâncime pot fi uşor adaptate la căutarea soluţiei problemei în reprezentarea prin grafuri SI/SAU.
Diferenţa constă în criteriul de determinare a condiţiei de oprire. De această dată trebuie să se testeze dacă o mulţime de noduri formează un arbore SI/SAU soluţie. Impactul fiecărui nod nou generat trebuie propagat în arborele parţial construit pentru a determina dacă nodul problemă iniţială a devenit rezolvat.Algoritmele de căutare în grafuri SI/SAU trebuie să gestioneze, pe lângă
listele LF si LT, şi o structură de date care reprezintă arborele SI/SAU construit prin explicitatea spaţiului de căutare definit în mod implicit de reprezentare. O altă diferenţă constă în faptul că nodurile SI nu se introduc în listele LF şi LT deoarece ele nu corespund efectiv unor subprobleme, ci indică numai o mulţime de subprobleme care trebuie rezolvate. Aceste noduri sunt însă construite şi fac parte din porţiunea explicitată a spaţiului de căutare. Pe baza stării de rezolvat sau nerezolvabil a acestor noduri se poate decide când s-a obţinut arborele soluţie.
10.04.2011 99
Cap. 1. Sisteme expert
Strategii de căutare euristică
Rezolvarea problemelor utilizând strategii de căutare neinformată prezintă dezavantajul că numărul de stări investigate pentru a găsi o soluţie poate ajunge prohibitiv de mare, chiar si pentru probleme relativ simple.
Necesitatea aplicării tehnicilor euristice de căutare.Acestea ţin seama de cât de aproape este fiecare nod al grafului de nodul corespunzător stării finale.
10.04.2011 100
Cap. 1. Sisteme expert
Observaţie: cuvântul euristic(ă) provine din greaca veche şi are înţelesul “a descoperi”. Conform DEX “un procedeu euristic serveşte la descoperirea unor cunoştinţe noi”, respectiv defineşte o parte a ştiinţei care are ca obiect descoperirea de fapte noi.
În contextul problemelor de căutare, o tehnică euristică este o strategie folosită pentru a creşte eficienţa căutării, fără a garanta obţinerea soluţiei. Dezvoltarea unei tehnici euristice se face pe baza unor
aproximări raţionale;ipoteze simplificatoare;cunoştinţe specifice domeniului problemei.
10.04.2011 101
Cap. 1. Sisteme expert
În acest context, cunoştinţele euristice pot fi utilizate pentru:
selectarea nodului următor de expandat în cursul căutării –selectarea nodului cel mai promiţător pentru obţinerea soluţiei;a decide care dintre succesorii nodului ce este expandat vor fi generaţi şi care nu – expandarea parţială a unui nod prin aplicarea numai a unui sbset de operatori dintre cei posibil de aplicat;eliminarea din spaţiul de căutare a anumitor noduri generate – retezarea arborelui de căutare
10.04.2011 102
Cap. 1. Sisteme expert
Deşi o mare parte dintre tehnicile euristice cunoscute sunt tehnici cu aplicabilitate generală totuşi, pentru aplicarea lor cu succes la o problemă particulară, ele trebuie suprapuse peste euristica specifică problemei analizate.În acest sens, se defineşte o funcţie euristică care exprimă – cel mai adesea în formă numerică – cât de promiţătoare este o stare din spaţiul de căutare în procesul de identificare a soluţiei, adică cât de apropiată este starea respectivă de stare finală.
10.04.2011 103
Cap. 1. Sisteme expert
Definirea unei funcţii euristice f implică utilizarea:
unei funcţii g evaluează costul deplasării din starea iniţială Si în starea curentă Sc;unei funcţii h estimează costul deplasării din starea curentă Sc în starea finală Sf;
Sf
Si
Sc
g( )Sc
h( )Sc
f( )Sc
10.04.2011 104
Cap. 1. Sisteme expert
Observaţii :Dintre cele trei funcţii doar g poate fi evaluată precis, celelalte două fiind doar estimate şi de aceea se notează f* şih* , iar legătura dintre ele este dată de relaţia
O particularitate proprie tehnicilor euristice de căutare o reprezintă caracterul local al procesului decizional care determină o comportare nemonotonă a funcţiei h în spaţiul stărilor.
* *( ) ( ) ( )i f i c c ff S S g S S h S S→ = → + →
10.04.2011 105
Cap. 1. Sisteme expert
Metoda căii spre obiectivPrincipiul metodei constă în alegerea acelor operatori care par să conducă la un obiectiv: soluţia problemei. La fiecare pas al procesului de căutare se evaluează diferenţele dintre starea curentă Sc şi starea finală Sf pe baza cărora se identifică un operator O1 ce ar permite trecerea directă din starea curentă în cea finală. Din păcate un astfel de operator fie nu există, fie nu poate fi aplicat. Se aplică principiul descompunerii problemei în subprobleme astfel:
se determină o stare intermediară S’c căreia i se poate aplica
operatorul identificat anterior şi în care se poate ajunge din starea curentă Sc prin aplicarea unui operator secundar .
10.04.2011 106
Cap. 1. Sisteme expert
Metoda pasului optim (best – first)Strategia selectează pentru expandare cel mai bun nod din spaţiul de căutare generat folosind cunoştinţele euristice, adică o estimare a stării cu ajutorul unei funcţii euristice. Algoritmul de bază al metodei implică parcurgerea următoarelor etape:1. Calculul funcţiei euristice pentru toate nodurile din
nivelul curent (nodurile din frontieră)2. Selectarea nodului cu valoarea minimă/maximă a
funcţiei euristice3. Expandarea nodului selectat (generarea succesorilor
săi). Dacă unul dintre succesori este soluţia, atunci procesul de căutare se opreşte.
10.04.2011 107
Cap. 1. Sisteme expert
Algoritmele A* şi AO*Folosesc pentru a evalua fiecare nod al frontierei o funcţie cost globală de tipul :
Caută o soluţie optimă a problemei. Algoritmul A* este specific reprezentării prin spaţiul stărilor, Algoritmul AO* este specific reprezentării prin grafuri SI/SAU.
* *( ) ( ) ( )i f i c c ff S S g S S h S S→ = → + →
10.04.2011 108
Cap. 1. Sisteme expert
R1: DACĂ B ŞI D ŞI E → FR2: DACĂ D ŞI G → AR3: DACĂ C ŞI F → AR4: DACĂ B → XR5: DACĂ D → ER6: DACĂ A ŞI X → HR7: DACĂ C → DR8: DACĂ X ŞI C → AR9: DACĂ X ŞI B → D
B C
X
, , B C
X D
, ,
,
B C
X D
E
, ,
, ,
B C
X D
E F
, ,
, ,
,
B C
X D
E F
A
, ,
, ,
, ,
R7R8
R9
R5R8
R9
R1
R8R9
R3
R8R9
R6
R8R9
HR4R7
B C,
B C
X
, , B C
X A
, ,
, R7
R8
R9
R6R7
R9
R4R7B C,
H
H R6
R4
A
X B
G
DR2
C
F
R3 B
D
E
R7
R9
C
R5 DC
R8
verificatverificat
verificat
verificat
verificat
neverificat
inutil deoarece nu a fost verificat G
a
b
c
R7
R9
R1ŞI
ŞI
ŞI
ªI
SAU
SAU
ŞIambele subscopuritrebuie verificate
SAUuna sau alta dintrereguli poate fi aplicată