inteligenta artificiala

12/29/2011

INTELIGENA ARTIFICIAL

George G. Savii Departamentul de Mecatronic Universitatea Politehnica din Timioara 2011-2012

IntroducereInteligena artificial este un domeniu al informaticii care urmrete dezvoltarea de sisteme tehnice capabile s rezolve prin metode asemenea celor folosite de om, probleme intelectuale dificile, precum i nelegerea, modelarea i chiar previziunea comportrii sistemelor vii. Inteligena artificial nseamn: Proiectarea i analiza programelor de calculator cu comportare inteligent Studiul modului n care calculatoarele pot face lucrurile pe care acum oamenii le fac mai bine Studiul facultilor mentale cu modele informatice Studiul comportrii inteligente Dezvoltarea de programe inteligente, ce pot rezolva situaii neprevzute

Inteligena Artificial

2

2011 George Savii

1

12/29/2011

IstoricA.M. Turing a a introdus pentru prima oar conceptul de memorare a programelor, prin aceasta calculatorul putnd s-i schimbe funcia, adic poate fi fcut s nvee sau s gndeasc. n 1960 John McCarthy a introdus LISP-ul, ca primul limbaj de cercetare al inteligenei artificiale. Un an mai trziu, Marvin Minskey a publicat prima carte n domeniul inteligenei artificiale intitulat "Steps towards Artificial Intelligence". Au urmat primul joc de ah pe calculator, prima demonstraie matematic i programul ELIZA, care a ncercat s nlocuiasc un psihiatru n discuia cu pacientul. La sfritul anilor '70 s-au obinut mai multe succese n: prelucrarea limbajelor naturale, reprezentarea cunoaterii i rezolvarea problemelor. Au fost puse bazele introducerii primului tip de produse comerciale de inteligen artificial, sistemele expert, ce conin informaii despre un anumit domeniu i atunci cnd sunt interogate, rspund asemntor unui expert uman. Unul din primele sisteme expert a fost MYCIN (Universitatea Stanford), pentru a ajuta medicii n diagnosticarea infeciilor. Un important eveniment a fost apariia n 1972 a limbajului Prolog, care a fost proiectat pentru a ajuta rezolvarea problemelor legate de inteligena artificial. Spre deosebire de LISP, are mai multe caracteristici specifice, precum faciliti de baze de date ncorporate, rutine de urmrire napoi i o sintaxa destul de simpl. n prezent cel mai important lucru n domeniul inteligenei artificiale este deplasarea de la cercetare la implementare.


3

2011 George Savii

Maina inteligentO definiie posibil: Un program inteligent este un program care manifest o comportare similar cu cea a unui om care se confrunt cu o problem similar. Nu este necesar ca programul s rezolve sau s ncerce s rezolve problema n acelai mod ca i omul. Testul Turing (variant): Un individ A converseaz de la un terminal cu alte dou terminale. La unul (nu se tie care) rspunde un alt individ, B, la altul un program de calculator, C. Dac dup o conversaie de durat mare, pe teme diverse, individul A nu poate spune la care terminal se afl individul B i la care programul, atunci programul respectiv este inteligent.


4

2011 George Savii

2

12/29/2011

Temele majore ale inteligenei artificialereprezentarea cunoaterii cutarea planificarea nvarea recunoaterea formelor, reele neuronale vederea artificial sisteme expert procesarea limbajului natural incertitudine n cunotine i n raionament, logica fuzzy raionarea automat Inteligena Artificial 5 2011 George Savii

Sisteme cu inteligen artificialtraducere automat sisteme decizionale sisteme de supervizare controlul traficului aerian asisteni personali automai cutare n baze de date roboi vehicule automate Inteligena Artificial 6 2011 George Savii

3

12/29/2011

Reprezentarea cunoateriiProblema central a inteligenei artificiale moderne este reprezentarea cunotinelor, adic codarea elementelor din lumea real, a cunotinelor obinuite, ntr-un format ce poate fi citit i neles de calculator. Orice cantitate de cunotine s poat fi codat n anumite configuraii particulare de bii ntr-o memorie a calculatorului suficient de mare. Relaiile dintre obiecte i concepte s poat fi, de asemenea, nregistrate. Reprezentrile s fie astfel nct s poat fi manipulate pentru a executa ceea ce n termeni obinuii se numete judecat. Reprezentrile s fie complete i concise. Fiecare pies de cunoatere reprezint descrierea n limbajul de reprezentare a sistemului a unei entiti din universul [de discurs] (domeniul de competen) al sistemului. Piesele de cunoatere plus procedurile de acces la cunoatere constituie sistemul cognitiv. Cunotinele nu sunt simple date, ci sunt organizate corespunztor modului n care vor fi utilizate


7

2011 George Savii

Tipuri de reprezentare a cunoateriidescriptiv comparativ (genul proxim + diferena specific) constructiv (generativ)

Metode de reprezentare a cunoateriilogice (propoziii) relaionale (obiecte, clase) procedurale (generative)Inteligena Artificial 8 2011 George Savii

4

12/29/2011

Reprezentarea cunoaterii prin logica predicatelorpentru cunotine declarative prin propoziii ce descriu obiectele cunoaterii i relaiile ntre ele regulile de inferen ale logicii predicatelor pot fi aplicate direct Toate mamiferele au snge cald. DAC animalul este mamifer ATUNCI are snge cald.


9

2011 George Savii

Reprezentarea procedural a cunoateriiUtilizeaz: obiecte proceduri specializate de inducie Pistonul este o parte a motorului. Motorul este o parte a automobilului. Pistonul este o parte a automobilului.Inteligena Artificial 10 2011 George Savii

5

12/29/2011

Reele semanticesunt grafuri ce descriu relaii ntre concepte, fapte, evenimente etc. relaiile pot fi: structurale, cauzale, semantice conceptul este un obiect intensional instana este un obiect extensional relaiile taxonomice asigur motenirea proprietilor conceptului de ctre toate instanele sale Exemple relaie taxonomic: Cinele este un mamifer. ESTE (cine, mamifer) relaie structural: PARTE-A (piston, motor) PARTE-A (motor, automobil)automobilparte-a

mamiferinstan-a

motorparte-a parte-ainstan-a

cineinstan-a

piston

cilindru

Grivei

Rex


11

2011 George Savii

Reprezentarea cunoaterii prin cadrecadrul este o structur, un ablon, n care datele noi sunt interpretate n termenii sau conceptele experienei (i.e. dobndite anterior) conine mai multe sertare/faete, corespunztoare diferitelor aspecte, ce vor fi completate cu elemente ce descriu cunoaterea asociat cadrului sertarele pot conine informaii descriptive sau procedurale permit cunoateri absente sau incomplet specificate un sistem cadru poate fi adesea considerat ca o baz de date relaional ierarhic special motenirea este un proces de inferen care permite deducerea de informaie implicit, care nu este reprezentat explicit n cadru/reea


12

2011 George Savii

6

12/29/2011

Reprezentarea cunoaterii prin cadre Exempluanimal de frumos DA companie proprietarun_fel_de un_fel_de

pasre

zboar are pene culoare

DA DA

un_fel_de

kiwi

culoare zboar este

galben NU

un_fel_de

canar

culoare galben proprietar

mierl este este Cip

culoare

neagr

Penny

este Ciripproprietar

Nicveterinar proprietar proprietar veterinar

proprietar

Gic este persoan

Sandu esteveterinar un_fel_de

Sic este


13

2011 George Savii

Reprezentarea cunoaterii prin scenariiscenariul este o structur ce descrie o secven stereotip de evenimente ntr-un context particular conine mai multe sertare (sau faete), ce pot conine informaii descriptive sau procedurale fiecare sertar are asociat informaia privind natura valorilor ce le poate conine, inclusiv valorile n lips (pentru cazul n care nici o alt informaie nu este disponibil) partea procedural specific:aciunea normal aciunea n caz de eroare aciunea cnd lipsete o anumit valoare

scenariile sunt utile pentru reprezentarea relaiilor cauzale ntre evenimente


14

2011 George Savii

7

12/29/2011

Reprezentarea cunoaterii prin ontologiiO ontologie este o descriere de comun acord a unor concepte i relaii ntr-un domeniu Ontologiile specific relaii ntre termenii unei scheme (=descriptor de document) i utilizeaz reguli de inferen cu care se pot realiza deducii despre termeni O ontologie poate fi:generic de domeniu de aplicaie meta-ontologie de procesare de interfaare pentru servicii

Ontologiile de aplicaii pot fi:


15

2011 George Savii

Interogarea ontologiilorInterogare de selecie sau extragere : se cere o informaie reprezentat n ontologie, de obicei bazat pe coninut, structur sau poziie. Interogare de reducere: se specific ce nu trebuie returnat ca rezultat. Interogare de restructurare: se modific nu numai valorile, ci i structura datelor. Interogare de agregare: o form simpl de obinere de cunotine noi, legat de inferen este agregarea datelor. Interogare de combinare i de inferen: combinarea informaiei existente dar nu explicit conectat, de ex., din diferite surse sau reprezentat n diverse structuri.


16

2011 George Savii

8

12/29/2011

Ontologii: limbajede programare (Prolog, Lisp,) bazate pe logic (KIF, Loom,) bazate pe cadre (Ontolingua, OIL,) bazate pe grafic (reele semantice,) bazate pe XML (DTD, XML-Schema,) bazate pe WWW (OWL,)Inteligena Artificial 17 2011 George Savii

Ontologii n mecatronicSunt trei grupe de descriptori pentru cunotine de baz pentru a captura semnificaia componentelor mecatronice: funcia, adic ce face un obiect (component, grup de componente, sau subansamblu) n ansamblu; comportarea, aciunile observabile prin care i ndeplinete funcia; structura, atributele obiectului fizic (de ex. materiale) ce sunt legate de realizarea comportrii.


18

2011 George Savii

9

12/29/2011

OntoSensor


19

2011 George Savii

Ontologia SiarSensorSwitch


20

2011 George Savii

10

12/29/2011

Interogarea ontologiei


21

2011 George Savii

Interogarea ontologiei


22

2011 George Savii

11

12/29/2011

LogicaO logic este o reprezentare definit a cunotinelor (un mod de exprimare). O teorem a unei logici date este o pies de cunoatere care a fost derivat din axiomele logicii (adic din fapte sau reguli date ca fundamente ale logicii). Calculul propoziional este un cadru logic n care propoziiile sunt uniti atomice semantice. Simbolurile logicii propoziionale sunt propoziiile atomice (P, Q,), conectorii i , parantezele ( ). Exemplu: O formul poate fi: valid (tautologie): adevrat n toate interpretrile realizabil: adevrat n cel puin o interpretare nerealizabil (contradicie): fals n orice interpretare (interpretare = o evaluare pentru propoziiile atomice ale unei formule) Regul de deducie (modus ponens, MP): din formulele P i P Q putem deduce Q. Calculul predicatelor este o extensie a calculului propoziional, ce permite utilizarea de variabile. Predicatul este o parte a unei propoziii afirmnd ceva despre obiectul propoziiei. Exemplu: x >7. Variabilele pot fi afectate de cuantificatori: universal () sau existenial (). Exemple:Inteligena Artificial 23 2011 George Savii

Exemplu de raionamentRegul: Aseriune:

Consecin: Socrate este muritor. [Concluzie] Regula are forma unei implicaii logice, n care partea stng, condiional (dup DAC) este antecedentul, iar partea dreapt (dup ATUNCI) este consecventul. Antecedentul poate conine mai multe propoziii logice combinate cu conective logice (conjuncia, disjuncia, negaia).

DAC este fiin uman ATUNCI este muritor. [Implicaie] Socrate este fiin uman. [Premis]

Exemplu de regul complex:A1 B1

DAC A1 SAU A2 I A3 ATUNCI B1 I B2A2 A3 B2

Diagrama regulilorInteligena Artificial 24 2011 George Savii

12

12/29/2011

Rezolvarea problemelor. CutareRezolvarea problemelor este fundamental n cele mai multe aplicaii de inteligen artificial; posibilitatea de a rezolva probleme este o msur a inteligenei att pentru om ct i pentru main. Principial exist dou tipuri de probleme: problemele care pot fi rezolvate utiliznd cteva tipuri de proceduri deterministe, care conduc garantat la succes; o astfel de procedur se numete calcul; metodele folosite la rezolvarea acestor probleme se pot traduce n algoritmi pe care calculatorul i poate executa; puine probleme din realitate au soluii obinute prin calcule problemele care se rezolv prin cutarea soluiilor (metode nedeterministe); aceste probleme ncearc s le rezolve inteligena artificial


25

2011 George Savii

Reprezentare i terminologieSpecificarea problemei: spaiul strilor problemei (mulimea configuraiilor posibile) strile iniiale strile int (finale) mulimea regulilor descriind aciunile permise strategia de conducere Rezolvarea problemei const n micarea n spaiul problemei conform strategiei de conducere, utiliznd regulile, pn la gsirea unui drum de la o stare iniial la o stare final (cutarea unei ci). Metode generale de rezolvare: deducia, inferena, planificarea, raionamentul de bun sim, demonstrarea teoremelor.


26

2011 George Savii

13

12/29/2011

Reprezentare i terminologie - exempluWC baie1buctrie

cmar sufragerie

hol

debara

sufragerie

dormitor1 baie1 dormitor2 buctrie dormitor1 dormitor2

hol X

debara

baie2

WC

cmar

baie2

Nod - un punct distinct i posibila int. Nod terminal - un nod care termin o cale. Spaiul de cutare - mulimea tuturor nodurilor. inta - nodul care este obiectul cutrii. Euristica - informaia despre probabilitatea ca un anumit nod s fie o alegere mai bun pentru ncercarea urmtoare, dect un alt nod. Calea soluiei - graful orientat al nodurilor parcurse care conduc la soluie.Inteligena Artificial 27 2011 George Savii

Explozia combinatorialFiecare nod adugat spaiului de cutare adaug mai mult de o cale. Exemplu: problema comis-voiajorului; pentru N localiti rezult N! stri. Deoarece numrul posibilitilor crete att de repede, doar problemele cele mai simple pot fi rezolvate prin cutri exhaustive, cutri care examineaz toate nodurile. Tehnica exhaustiv poate fi teoretic aplicat ntotdeauna, dar practic nu este posibil aplicarea, deoarece consum prea mult timp, prea multe resurse de calcul sau amndou. Din acest motiv s-au dezvoltat alte tehnici de cutare.

EuristicaEuristica utilizeaz reguli simple care mresc probabilitatea ca o cutare s evolueze n direcia corect (euristic=care servete la descoperire). Informaia euristic, dei imprecis i negarantat, crete ansele ca o metoda de cutare s ating inta mai repede. Cel mai adesea, metodele de cutare euristic se bazeaz pe maximizarea sau minimizarea unor aspecte ale problemei. (Ex.: cel mai apropiat ora)Inteligena Artificial 28 2011 George Savii

14

12/29/2011

Complexitatea unei problemeComplexitatea unei probleme este complexitatea celui mai bun algoritm (pn n acel moment) pentru rezolvarea problemei Complexitatea unui algoritm, cnd se d un vector de date de lungime n, este numrul de pai necesari, n cel mai ru caz, pentru a ajunge la terminarea algoritmului. Este indicat prin O(f(n)), n care f(n) este o funcie cu parametrul n. Complexitatea poate fi: polinomial, cnd rezolvarea necesit un timp exprimat ca funcie polinomial de dimensiunea datelor de intrare, n; exemple: O(n) pentru gsirea unui element n list nesortat, O(log(n)) pentru gsirea unui element n list sortat, O(n*log(n)) pentru sortarea unei liste; exponenial, cu timp de rezolvare exprimat exponenial funcie de dimensiunea datelor de intrare, n; exemplu: O(2n) pentru probleme de testare a satisfacerii unor condiii, cum ar fi testarea corectitudinii unei relaii logice pentru cel puin un set de valori ale variabilelor.


29

2011 George Savii

Clase de complexitateP probleme rezolvabile n timp polinomial NP probleme pentru care cel mai bun algoritm este nedeterministic exponenial, dar verificarea soluiei se poate face n timp polinomial NP-hard probleme al cror algoritm poate fi adaptat n unul pentru rezolvarea oricrei alte probleme NP (deci NP-hard sunt problemele de dificultate maxim) NP-complete probleme care sunt i NP i NPhard (exemplu: problema comis-voiajorului)


30

2011 George Savii

15

12/29/2011

Tehnici de cutareCutare oarb Cutare ghidatCutarea n adncime Cutarea pe nivel Cutarea cu efort maxim Cutarea cu cost redus

Evaluarea unei tehnici: rapiditatea gsirii soluiei valoarea soluiei A gsi soluia optim presupune, adesea, o cutare exhaustivInteligena Artificial 31 2011 George Savii

Tehnica de cutare n adncimeIpoteza curent este extins pn la limit nainte de a lua n considerare o alt ipotez (alt nod) La atingerea unei limite (nod terminal etc.) se revine la cea mai recent ipotez viabil (backtracking) Cutarea n adncime duce cu siguran la int, deoarece n cazul cel mai ru degenereaz n cutare exhaustiv

Exemplu. Origine: New York, int: Los AngelesPlecare Sosire Distanta --------------------------------New York Toronto 800 New York Chicago 1000 Chicago Denver 1000 New York Denver 1900 Toronto Calgary 1500 Toronto Los Angeles 1800 Toronto Chicago 500 Denver Houston 1500 Houston Los Angeles 1500 Denver Los Angeles 1000Inteligena Artificial

Calgary

2 3Toronto

D=2600 4Chicago

1

New York

Denver Los Angeles Houston32 2011 George Savii

16

12/29/2011

Tehnica de cutare n adncime: algoritmstabilete spaiul cutrilor (lista arcelor), nodul_rdcin i inta; marcheaz nodul_rdcin; nodul_curent:=nodul_rdcin; nceput_cutare:=1 (primul arc din list) pas de cutare: caut de la arcul nceput_cutare un arc i care pleac de la nodul_curent i ajunge la un nod nemarcat exist arc pas nainte: stocheaz i n arbore i n lista arcelor active; nodul_curent:=nod sfrit arc i; nodul curent e inta da nu afiare cale; marcheaz STOP nodul_curent; afiare coad/list nu exist arc lista arcelor active e nevid e vid revenire: nodul_curent:= afiare nodul nceput arc curent arbore; nceput_cutare:=arcul curent+1 STOP scoate arcul curent din list active


33

2011 George Savii

Tehnica de cutare pe nivelsunt luate n considerare toate ipotezele (nodurile) de la un anumit nivel nainte de a trece la nivelul urmtor calea la inta gsit este cea mai scurt (nr. minim de noduri) buclele nu fac probleme


Calgary

4Toronto

D=2600 5Chicago

1 2New York

3Denver Los Angeles Houston34 2011 George Savii

17

12/29/2011

Tehnica de cutare pe nivel: algoritmstabilete spaiul cutrilor (lista arcelor), nodul_rdcin i inta; marcheaz nodul_rdcin; nodul_curent:=nodul_rdcin; nceput_cutare:=1 pas de cutare: caut de la arcul nceput_cutare un arc i care pleac de la nodul_curent i ajunge la un nod nemarcat exist arc pas nainte: stocheaz i n arbore i n lista arcelor active; nodul sfrit e inta da nu afiare cale; marcheaz nod STOP sfrit arc i; nceput_cutare :=i; afiare coad/list nu exist arc lista arcelor active e nevid schimbare nod curent: nodul_curent:= nodul sfrit al primului arc din list nceput_cutare:=1 scoate primul arc din list active e vid afiare arbore; STOP


35

2011 George Savii

Tehnica de cutare cu efort maximEuristica utilizat: probabilitatea de a fi ct mai aproape de destinaie este cu att mai mare cu ct se acoper o distan mai mare. Formal, acest algoritm alege ca pas urmtor nodul care pare s-l plaseze cel mai aproape de int. Conduce la o soluie optimal mai repede dect orice metod ne-euristic


Calgary Toronto

D=2900Chicago

1 2Los Angeles Houston36

New York

Denver

2011 George Savii

18

12/29/2011

Tehnica de cutare cu cost minimEuristica utilizat: alegerea cilor cu efort minim duce probabil la efort total minim. Formal, acest algoritm alege ca pas urmtor nodul cel mai apropiat


Calgary Toronto

D=2600 2Chicago

1

New York

Denver Los Angeles Houston37 2011 George Savii

Alegerea unei tehnici de cutareTehnicile de cutare euristic au tendina de a funciona mai bine dect cutrile oarbe. Dac nu se poate aplica euristica se folosete metoda cutrii n adncime pentru c n general este cea mai bun. Excepie face situaia n care se tie c este mai bun cutarea pe nivel. Alegerea ntre cutarea cu efort maxim i cutarea cu cost redus depinde de condiia pe care vrem s-o maximizm sau minimizm. n general cutarea cu efort maxim produce o soluie cu cel mai mic numr de noduri parcurse, iar cutarea cu cost redus gsete calea care cere efortul cel mai mic. Dac este cutat o soluie apropiat de cea optimal dar nu putem folosi cutarea exhaustiv, atunci se poate ncerca fiecare metod i se alege soluia cea mai bun. Tehnica aceasta d rezultate deoarece fiecare metod lucreaz altfel i de aceea, oricare poate produce rezultate mai bune dect celelalte.


38

2011 George Savii

19

12/29/2011

Cutarea soluiilor multipleSoluiile multiple pot prezenta diferite opiuni pentru a ajuta n gsirea soluiei optime ntr-o anumit situaie. Exist mai multe metode de generare a soluiilor multiple, cele mai uzuale fiind: eliminarea cii: elimin din baza de date toate arcele care formeaz o soluie curent i apoi ncearc s gseasc o alt soluie eliminarea nodului: elimin din baza de date ultimul nod (dinaintea intei) care formeaz o soluie curent i apoi ncearc s gseasc o alt soluie


39

2011 George Savii

Calgary Toronto 1Chicago

Metoda eliminrii cii(tehnica n adncime)

D1=2600 D2=5000 D3=2900Denver

2 New York 3

Los AngelesHouston

Calgary TorontoD1=2600 D2=5000 D3=3000

1

Chicago

New YorkDenver

3 Los Angeles 2

Metoda eliminrii nodului

Houston


40

2011 George Savii

20

12/29/2011

Sisteme expertSisteme expert sunt programe de IA, bazate pe cunoatere, care imit comportarea unui expert uman n rezolvarea problemelor. Sistemele expert: pot pune ntrebri i pot da explicaii privind modul cum raioneaz sau motivul ntrebrii raioneaz euristic pot interaciona folosind limbajul natural pot manipula date imprecise, eronate sau lips pot trata simultan mai multe ipoteze parte de stocare a cunotinelor e separat de partea de prelucrare ncearc s dea sfaturi utilizatorului n domeniul de expertiz sunt disponibile oricnd, n orice zi, la orice or pot fi create ntr-un numr nelimitat de exemplare informaia pe care o conin nu se pierde lucreaz ntotdeauna la acelai nivel de performan sunt lipsite de personalitateInteligena Artificial 41 2011 George Savii

Sisteme expert exemplu de consultaie MYCIN----- PACIENT 1 ----(1) Numele pacientului: FRED SMITH (2) Sex: BRBTESC (3) Vrsta : 55 (4) Ai reuit s obinei o cultur pozitiv dintr-un loc unde Fred Smith are o infecie ? DA ----- INFECTIA 1 ----(5) Ce fel de infecie este ? BACTERIEMIE PRIMAR (6) Va rog, introducei data cnd au aprut primele simptome ale bacteriemiei primare (INFECTIA 1) (l/z/a) : MAI 5, 1975 Cea mai recent cultur asociat bacteriemiei primare se refer la: ----- CULTURA 1 ----(7) De unde s-a luat mostra pentru CULTURA 1 ? SNGE (8) Va rog, introducei data si ora cnd CULTURA 1 a fost obinut: 9 MAI 75 Cel mai recent microorganism din aceast cultur de snge este: ----- ORGANISM 1 ----(9) Introducei identitatea organismului 1 : NECUNOSCUT (10) ORGANISM 1 este bacil sau coc? BACIL (11) Care este coloraia-Gram a organismului 1? GRAMNEG (12) Au fost gsite i alte culturi POZITIVE n afar de infecia bnuit? NU (13) A crescut ORGANISM 1 n mediu aerob ? DA (14) A crescut ORGANISM 1 n mediu anaerob ? DA (15) Care este poarta de intrare suspectat ? GASTRO-INTESTINAL Indicaiile terapeutice se vor baza pe urmtoarele infecii probabile i poteniale microorganisme cauzatoare ale bolii: INFECTIA 1 este BACTERIEMIE PRIMARA ORGANISM 1 este E.COLI ORGANISM 1 este PSEUDOMONAS - AERUGINOSAInteligena Artificial 42 2011 George Savii

21

12/29/2011

Structura sistemelor expertbaza de cunotine

motorul de inferen

interfee speciale

periferice

subsistemul de achiziie a cunotinelor

subsistemul de explicare

interfaa cu utilizatorul

expert/inginer de cunotine

utilizator


43

2011 George Savii

Baza de cunotineconine informaii relevante pentru domeniul de expertiz reprezentarea cunotinelor este n forme diverse, de obicei prin fapte, reguli, cadre, reele semantice


44

2011 George Savii

22

12/29/2011

Baz de cunotine - exempluObiectul: poseda proprietatea Mrul: crete n pom, are forma rotund, are culoare roie sau galben Pepenele: crete pe pmnt, are dimensiuni mari, are culoare verde, are forma alungit Portocala: crete n pom, are forma rotund, are culoare portocalie DAC crete n pom I are forma rotund I (are culoarea roie SAU are culoarea galben) ATUNCI fructul este mr DAC crete pe pmnt I are dimensiuni mari I are culoarea verde I are forma alungit ATUNCI fructul este pepene DAC crete n pom I are forma rotund I are culoarea portocalie ATUNCI fructul este portocal


45

2011 George Savii

Motorul de inferenMotorul de inferen este acea parte a unui sistem expert care ncearc s utilizeze cunotinele existente n sistem pentru a gsi noi cunotine. Exist dou categorii mari de maini de inferen: deterministe i probabilistice. Pentru cunotine sub form de reguli, strategiile de control pot fi nlnuirea (raionamentul) nainte sau nlnuirea napoi. Pentru cunotine n logica predicatelor sunt utilizate mecanismele deductive ale logicii clasice.


46

2011 George Savii

23

12/29/2011

Strategia cu nlnuire nainteMetoda cu nlnuire nainte se mai numete i orientat pe date, deoarece motorul de inferen folosete informaia pe care utilizatorul o furnizeaz, pentru a se deplasa ntr-o reea de reguli pn atinge punctul terminal, care este soluia. Dac maina de inferen nu poate gsi o soluie utiliznd informaia existent, atunci cere mai mult informaie. Singura cale de a ajunge la soluie o reprezint satisfacerea tuturor regulilor implicate. Cutarea pleac de la o stare iniial pentru a determina strile finale ce pot fi atinse pe baza cunotinelor date. Strategia este tipic problemelor de conducere (decizionale).


47

2011 George Savii

Strategia cu nlnuire nainte exemplun pom forma rotund culoarea galben MR roie portocaliePORTOCAL

crete

pe pmnt dimensiuni mari culoarea verde forma alungit PEPENE

DATE:


48

2011 George Savii

24

12/29/2011

Strategia cu nlnuire napoi

Metoda cu nlnuire napoi se mai numete i orientat pe obiect, deoarece motorul de inferen ncepe cu o ipotez (un obiect) i cere informaie pentru a o confirma sau nega. Dac maina de inferen nu poate gsi o soluie utiliznd informaia existent, atunci cere mai mult informaie. Singura cale de a ajunge la soluie o reprezint satisfacerea tuturor regulilor implicate. Cutarea pleac de la o stare final pentru a determina validitatea condiiilor n care aceasta poate fi atins. Strategia este tipic problemelor de diagnosticare.


49

2011 George Savii

Ghidare prin valoarea reguliiUn motor de inferen cu ghidare prin valoarea regulii este teoretic superior celorlalte deoarece cere informaii care au cea mai mare importan n raport cu starea curent a sistemului. Se aplic, de obicei, motorului de inferen cu nlnuire napoi. Sistemul cere ca urmtoare unitate de informaie pe aceea care va elimina cele mai multe incertitudini din sistem (cea mai valoroas). Sisteme expert cu ghidare prin valoarea regulii pot ncepe fie ca sisteme cu nlnuire nainte fie cu nlnuire napoi, avnd un modul statistic pentru nregistrarea diferitelor aspecte din sistem. Mai trziu, dup ce sistemul expert a fost folosit pe mai multe cazuri, statistica poate fi folosit pentru a implementa ghidarea prin valoarea regulii. Implementarea obinuit este realizat prin asocierea la fiecare regul a unei valori proporionale cu numrul de cazuri n care regula a fost declanat (validat).


50

2011 George Savii

25

12/29/2011

Interfaa cu proiectantulCrearea bazei de cunotinecu editor de texte ASCII cu editor controlat de sintax (gen formulare)

ExplicaiiDe ce? (Why?) Cum? (How?) Dar dac? (What if?)

Trasarea inferenei Editor on-line Bibliotec de cazuri


51

2011 George Savii

Interfaa cu utilizatorulMeniuri Orientare iniial Acceptare de rspunsuri multiple sau nesigure Explicaii Grafica Instruire Documentaie Consultan

Interfaa cu sistemulLegturi cu baze de date Utilizare de module externe create cu alte limbaje Compilarea bazei de cunotine Sisteme de operare acceptateInteligena Artificial 52 2011 George Savii

26

12/29/2011

Ingineria cunoateriiIngineria cunoaterii este tiina care se ocupa cu modul de organizare a bazelor de cunotine, construirea i verificare lor. Organizarea bazelor de cunotine O metod bun de organizare a cunotinelor este plasarea la nceputul bazei de cunotine a obiectelor mai probabile i la sfritul ei a celor mai puin probabile. Problema este a afla care obiecte sunt mai probabile i care mai puin probabile. Se poate crea o baza de cunotine n mod aleator i s fie folosit o anumit perioada de timp, nregistrnd de cte ori este selectat fiecare obiect. Folosind aceast frecven se pot reordona bazele de cunotine. Un alt mod de organizare este de a plasa la nceputul bazei de cunotine acele atribute care cauzeaz tierea celei mai mari pri a ramurilor din arborele spaiului de cutare.Inteligena Artificial 53 2011 George Savii

Ingineria cunoateriiGsirea expertuluiEste dificil de decis cine este un expert i cine nu. Doi experi diferii pot avea opinii diferite referitoare la acelai subiect. Cnd opiniile experilor difer, exist trei alternative obinuite. Poate fi selectat un expert i ignorat cellalt. Aceasta este cea mai simpl alternativ, dar nseamn c baza de cunotine poate s conin informaii eronate. Se poate face o mediere a informaiilor, adic se poate folosi doar informaia comun experilor. Dezavantajul este c baza de cunotine nu reflect totalitatea cunotinelor experilor. Se poate introduce informaia tuturor experilor n baza de cunotine i se las utilizatorul s decid ce soluie adopt; se poate aduga un factor de probabilitate pentru fiecare soluie. Dei aceast metod este acceptabil n unele situaii, pentru multe aplicaii se dorete ca sistemul expert s fie autoritatea, nu utilizatorul. O alt problem este c experii umani de multe ori nu tiu ce tiu. De aceea poate fi dificil s extrag toat informaia necesar. Pe de alt parte, unii experi nu vor fi dispui s piard timpul pentru a comunica ceea ce tiu.Inteligena Artificial 54 2011 George Savii

27

12/29/2011

Ingineria cunoateriiVerificarea bazei de cunotineDac este gsit un expert care este cooperant i furnizeaz informaii complete, mai rmne de rezolvat problema verificrii dac informaiile introduse n sistemul expert sunt corecte. n esen, trebuie testat baza de cunotine. Verificarea prin cutare exhaustiv nu este posibil dect pe mulimi foarte mici de date, din cauza exploziei combinatoriale. De aceea, pentru cele mai multe sisteme ale lumii reale nu exist posibilitatea unei verificri complete a corectitudinii bazei de cunotine. Cea mai bun soluie este s se efectueze suficiente testri pentru a fi relativ sigur de corectitudinea bazei de cunotine. Prin folosirea tehnicilor de eantionare statistic se pot efectua o serie de teste care s genereze orice nivel de ncredere dorit. n alt abordare, se poate ca sistemul s efectueze un autotest de necontradicie, pentru a vedea dac informaia din baza de cunotine este coerent. Acest lucru nu va permite detecia tuturor erorilor, dar va permite detecia unora. La unele baze de cunotine se va putea atinge limita combinatorial, fcnd imposibil utilizarea acestei metode.


55

2011 George Savii

Vederea artificial i recunoaterea formelorPentru ca un calculator s poat fi interfaat complet cu realitatea, este necesar s aib cteva faciliti de vedere (exemplu: robotul autonom). Procesul de digitizare a semnalului unei camere de luat vederi nu face parte din domeniul inteligenei artificiale, dar procesul de interpretare a acestor semnale este o problem IA. Termenul de prelucrare a imaginii descrie, adesea, domeniul vederii artificiale i al recunoaterii formelor. Domeniul este larg deoarece cuprinde procesarea bidimensional i tridimensional.Inteligena Artificial 56 2011 George Savii

28

12/29/2011

Preprocesarea imaginiin general exist dou metode prin care sistemele de vedere sunt implementate: reducerea imaginii la liniile care formeaz conturul fiecrui obiect redarea imaginii mai aproape de cea vzut de om Prima metod folosete diferite filtre pentru a elimina informaie din imagine i pentru a mri contrastul, n scopul obinerii de pri ale imaginii negre sau albe. Se obine astfel ceea ce se numete imagine binar, deoarece nu conine zone gri. Avantajul imaginii binare: furnizeaz doar contururile pe care calculatorul le poate recunoate uor, folosind algoritmi simpli (este clar unde ncepe i unde se termina fiecare obiect). Imaginea de contrast ridicat este folosit de obicei n mediile controlate, unde se tie dinainte c pot s existe numai cteva obiecte cunoscute. A doua metod d calculatorului informaie legat de strlucirea prilor imaginii. Cu aceast informaie, calculatorul poate obine date importante legate de suprafeele i umbrele obiectelor, date ce nu pot fi obinute prin prima metod. Calculatorul poate folosi aceste date pentru a furniza informaii tridimensionale legate de imagine i pentru a rezolva conflictele n cazurile n care un corp acoper parial pe altul.Inteligena Artificial 57 2011 George Savii

Recunoaterea formelorForma = entitate ce poate fi numit Recunoaterea formelor rezolv probleme legate de: clasificarea obiectelor (supervizat sau nu) gsirea unor tipare n date, n vederea realizrii unor descoperiri sau predicii gsirea unor tipare n datele din reacie (feedback) n vederea nvrii i evoluiei crearea de memorii cu forme n vederea recuperrii la prezentarea unor forme asemntoare Aplicaii tipice: vederea artificial, recunoatere scris/amprent/avion, recunoaterea vorbirii analiza semnalelor medicale (EKG) data mining predicii financiareInteligena Artificial 58 2011 George Savii

29

12/29/2011

Structura unui sistem de recunoatere a formelorcaptor imagine (cu matrice de senzori) preprocesor imagine (zgomote, contrast etc.) izolator de forme (segmentare) mecanism de extragere a caracteristicilor (stocare n memorie ca vector) clasificator sau descriptor (cu arbore de decizie, reea neuronal etc.) postprocesor (decidere aciune recomandat) set de exemple/antrenament deja clasificate/descriseInteligena Artificial 59 2011 George Savii

Caracteristici pentru recunoaterea formelorcaracteristica este un atribut distinctiv (nlimea, culoarea, vrsta, h/b, p2/A,) vectorul caracteristicilor conine o combinaie de n caracteristici spaiul n-dimensional definit de vectorul caracteristicilor este spaiul caracteristicilor formele (obiectele) sunt reprezentate ca puncte n spaiul caracteristicilor forma (pattern) este un complex de caracteristici particulariznd un obiect caracteristicile pot avea ataate grade de importan (ponderi)Inteligena Artificial 60 2011 George Savii

30

12/29/2011

Clasificatorulare funcia de a partiiona spaiul caracteristicilor n regiuni etichetate graniele ntre regiuni sunt frontiere de decizie clasificarea unui vector de caracteristici const n determinarea regiunii creia i aparine i asignarea lui clasei respective clasificatorul poate fi reprezentat ca o mulime de funcii discriminant clasele reale pot avea suprapuneriInteligena Artificial 61

clasa asignat selectare maxim

f1(x)

f2(x)

f3(x)

x1

x2

x3X

x4X X X X X X

X

X

2011 George Savii

Clasificatorul - Exemplu

Start DA DA NU NU DA Q P DA O>1 NU NU O

V>0

C>0

C>1

E

L


62

2011 George Savii

31

12/29/2011

Recunoaterea formelor - Abordristatistic sintactic/structuralbazat pe un model statistic al caracteristicilor, definit de o familie de funcii de densitate de probabilitate Pr(x|ci) bazat pe msura similaritii (structurale) reprezentare prin structuri formale (gramatici, automate etc.) utilizat i pentru descrieri (tipic: ierarhice, pentru forme complexe, din sub-forme)

neuronalbazat pe rspunsul unei reele de uniti de procesare (neuroni) la un stimul de intrare (form) rspunsul depinde de topologia reelei, de ponderile sinaptice i de funciile de activare individuale este strategie nealgoritmic, cu nvare necesit minimum de cunotine a priori poate realiza orice forme pentru regiunile de decizieInteligena Artificial 63 2011 George Savii

Reele neuronale artificialeReelele neuronale artificiale au ca punct principal de inspiraie sistemul nervos. Unitatea de organizare a sistemului nervos este neuronul, o celul care prezint un numr de dendrite i un axon, prin intermediul crora se interconecteaz cu ali neuroni. Totalitatea impulsurilor prezentate la intrarea neuronului l pot excita ca acesta s genereze un impuls mai departe spre neuronul cu care este conectat. Legturile ntre neuroni sunt ponderate i fiecare neuron aplic o transformare asupra impulsului de la intrri nainte de a-l transmite mai departe. O reea neuronal artificial este alctuit dintr-o mulime de noduri n care se afl neuronii artificiali, elemente de procesare neliniare, care opereaz n paralel. Prin analogie cu neuronul biologic, un neuron artificial are un anumit numr de intrri i o singur ieire, care se poate conecta la intrrile mai multor neuroni.Inteligena Artificial 64 2011 George Savii

32

12/29/2011

Reele neuronale artificiale - AvantajeReelele neuronale artificiale prezint un numr destul de mare de caracteristici ale creierului: pot nva din experien pot generaliza din anumite exemple altele noi pot sintetiza caracteristicile eseniale din intrri ce conin i date irelevante. Un mare avantaj al reelelor neuronale artificiale este c pot descrie o problem i o pot rezolva n acelai timp, prin autoorganizarea lor i nu prin program. Acest proces de autoorganizare are loc pe parcursul unui proces de nvare realizat prin cooperarea unei topologii iniiale, a unor reguli de nvare i a unui numr mare de antrenamente. Avantaje fa de calculatoarele tradiionale: adaptarea la mediu nou prin nvare. procesarea informaiilor vagi, imprecise manipularea datelor cu zgomote sau eronate realizarea rapid a clasificrilorInteligena Artificial 65 2011 George Savii

RNA: Dezavantaje

conin prea muli parametri (ponderile, rata nvrii, rata impulsului etc.) arhitectura este greu de ales antrenamentul este lent se blocheaz uor n minime locale n consecin, se caut alte metode din aceeai clas (de exemplu bazate pe maini cu vectori suport, care sunt asemntoare perceptroanelor)


66

2011 George Savii

33

12/29/2011

RNA: CaracteristiciCapacitatea de a nva Reelele neuronale artificiale nu necesit programare, ci sunt rezultatul unor antrenamente Fiind dat un set de intrri (eventual i cu ieirile dorite), n urma procesului de antrenament reelele neuronale se autoorganizeaz astfel c pot rezolva problemele pentru care au fost antrenate Capacitatea de generalizare Dac au fost antrenate corespunztor, reelele sunt capabile s dea rspunsuri corecte i pentru intrri diferite fa de cele cu care au fost antrenate, att timp ct aceste intrri nu sunt foarte diferite de cele de la antrenament. Reelele neuronale artificiale generalizeaz automat ca urmare a structurii lor, nu cu ajutorul inteligentei omului nglobat intr-un anumit program special creat n acest scop Capacitatea de sintez Reelele neuronale artificiale pot lua decizii sau trage concluzii cnd sunt confruntate cu informaii complexe, irelevante (zgomote) sau pariale. De exemplu, o reea poate fi antrenat cu o secven de versiuni distorsionate ale literei A. Dup un proces de antrenare adecvat, aplicarea unei versiuni distorsionate a literei A va avea ca rezultat la ieirea reelei litera corect.


67

2011 George Savii

RNA: ParadigmeAutoasociatorul Asociatorul de forme Clasificatorul Detectorul de regulariti

RNA: nvareaSupervizat Nesupervizat Cu recompense/pedepseInteligena Artificial 68 2011 George Savii

34

12/29/2011

Neuronul artificialx1 w2 w1

x2

a

f

y

xn

wn


69

2011 George Savii

Funcii de activaretreapt:

f(x)=1/(1+e-x) 1

f(x)=2/(1+e-x)-1 1

0,5

0 -1 0 x

x

dinamic:Inteligena Artificial

cu integrarea stimulului70 2011 George Savii

35

12/29/2011

PerceptronulPerceptronul este o reea feed-forward stratificat (un strat de intrare, N-1 straturi ascunse i un strat de ieire). Activarea este binar (treapt). A fost introdus de McCulloch i Pits[1943].

x1

hw 11

h1 h2 h3

ow 11

o1

x2

o2ow 42

x3

hw 34

h4

Pentru un strat (clasificare n dou regiuni A1|y>0; A2|y H: WT.X = 0 Schimbare de variabil: => WT.Z > 0 dac clasificarea este corectInteligena Artificial 71 2011 George Savii

Funcia criteriu


72

2011 George Savii

36

12/29/2011

Algoritm de antrenament pentru perceptron cu un strataleg w1n; se alege ; se alege kmax; k:=1 ia o form nou (Zi,Di) i este prezentat la intrare (ciclic, 1ip) 3.se calculeaz ieirea real: signum((Wk)T.Zi ) 4. i eroarea 5.se modific ponderile: Wk+1 := Wk [+ .hk] 6.se verific criteriul de oprire (nu s-a modificat nici un vector pondere n p epoci); se termin dac este ndeplinit 7.k:=k+1; dac k=0); E:=D-Y; S:=E.ET; k:=1 NUdW:=E.XT; W:=W+ .dW; A:=W.X; Y:=(A>=0); E:=D-Y; S:=E.ET; k:=k+1

S=0STOP

DAAfieaz rezultate

NU Afieaz rezultate intermediare

k>kmax

DA Afieaz mesaj STOP


74

2011 George Savii

37

12/29/2011

Propagarea napoi a erorii la reea neuronal cu dou straturix1k . . . xnk q w1q . . . wnq jk i

hk = q

n

xi =1

w iq

iq k wqj

yk = j

iq

k q

w qj

ojk

ik = S h (h k ) q q q

o k = S o (y k ) j j j


75

2011 George Savii

Reguli de coreciepentru stratul de ieire general: wqjo(k+1)=wqjo(k)+k.(djk-ojk).Sqh(hqk).Sjo(yjk); kj=(djk-ojk).Sjo(yjk) wqjo(k+1)=wqjo(k)+k.kj.iqk wqjo(k+1)=wqjo(k)+k.(djk-yjk).iqk pentru strat de ieire linear, Sjo(yjk)=yjk

kj=(djk-yjk):

pentru strat de ieire sigmoidal, Sjo(yjk)=1/(1+exp(-yjk)): o(y k)= S o(y k).[1- S o(y k)] =(d k-o k).o k.(1- o k) Sj j j j j j kj j j j j wqjo(k+1)=wqjo(k)+k.(djk- ojk).ojk.(1- ojk) .iqk wiqh(k+1)=wiqh(k)+k.iqk.(1- iqk) pentru strat ascuns sigmoidal: .xik.j(wqjo(k).kj)


76

2011 George Savii

38

12/29/2011

Algoritm de antrenament pentru reea neuronal multistratiniializeaz toate ponderile w cu valori mici aleatoare; se alege ; se alege kmax; k=1 ia o form nou (Xp, Dp) i este prezentat reelei (ciclic, 1pP) 3.se propag intrrile ctre ieiri: yim=f(aim)=f(j(wji.xj)), pentru fiecare neuron i din fiecare strat m 4.se calculeaz semnalele de eroare pentru stratul de ieire M: iM=f(aiM).(diP-yiM) 5.se calculeaz semnalele de eroare pentru straturile anterioare prin propagarea erorii napoi: im-1=f(aim-1). j(wjim.jm), m=M,M-1,...,2 pentru toi i 6.se modific ponderile cu wijm=.im.xjm 7.se verific criteriul de oprire; se termin dac este ndeplinit 8.k:=k+1; dac k a ub uc c.

1

1

a

b

c

u

S 1 0,5 0

a

b

c

d

u

a

b

c

u2011 George Savii

Operaii cu mulimi nuanateA = B A(u) = B(u) , u U A B A(u) B(u) , u U A B (u) = max(A(u), B(u)) , u U B (u) = min(A(u), B(u)) , u U A(u) = 1 A(u) , u U1

A

B

0

u1

A

B

0

u1

A A u

0


106

2011 George Savii

53

12/29/2011

Operaii pentru modificarea formei funciilor de apartenenRidicarea la putere Ap = {(u, A(u))}p = {u, (A(u))p} , u U Concentrarea CON(A)(u) = (A(u))2 , u U Dilatarea DIL(A)(u) = (A(u))0,5 , u U1

CON(A) A0

u1

A0

DIL(A)

u


107

2011 George Savii

Operaii avansate cu mulimi nuanateProdusul algebric (PROD), denumit i conjuncie sau intersecie probabilistic: AB(u) = A(u) B(u) , u U Suma algebric (ASUM), denumit i disjuncie sau reuniune probabilistic: A+B(u) = A(u) + B(u) A(u) B(u) , u U Produsul mrginit (diferena mrginit BDIF): AB(u) = max(0, A(u) + B(u) 1) , u U Suma mrginit (BSUM): AB(u) = min(1, A(u) + B(u)) , u U t-norme i t-conorme asociate:


108

2011 George Savii

54

12/29/2011

Relaii nuanateFie n universuri U1,...,Un. O relaie nuanat n-ar R n U = U1...Un este o mulime nuanat pe U1...Un , submulime a produsului cartezian U1...Un: RU = {((u1,...,un), R(u1,...,un)) | (u1,...,un) U1...Un}. Produsul cartezian este utilizat, n general, pentru a defini relaia dintre dou sau mai multe mulimi. Dac A i B sunt mulimi clasice, produsul lor cartezian este: AB = {(a, b) | a A, b B} n care (a, b) este o pereche ordonat, iar aA, bB nseamn c se ia fiecare element din A i din B. Dac A are m elemente (m = |A|), iar B are n elemente, produsul cartezian AB va avea m.n elemente. O relaie binar clasic R de la A la B este orice submulime a produsului cartezian AB. O relaie binar nuanat R de la U la V este o submulime nuanat a produsului cartezian U V : R = {(u, v), R(u, v) | u U, v V } , n care R(u, v) este funcia de apartenen a mulimii R. Cnd universurile U i V sunt finite, relaia binar poate fi reprezentat i ca un tablou bidimensional, numit matricea relaiei, cu elementul generic: [R]i,j = ri,j = R(ui , vj) , i = 1, m , j = 1, n, n care m = |U| i n = |V|.Inteligena Artificial 109 2011 George Savii

Relaii nuanate - exempluA = {creion, pix, stilou}; B = {lemn, plastic, metal}; C = {ieftin, mediu, scump}

P Q (a, c) = sup min (P (a, b), Q (b, c)), a A, c Cb B

ri,j = max { min (Pi,1, Q1,j), min(Pi,2, Q2,j), min(Pi,3, Q3,j)} i = 1,2,3 , j = 1,2,3,


110

2011 George Savii

55

12/29/2011

Raionament nuanatRegula dat: DAC A ATUNCI B ~ R=AB R(x, y) = (A B) (x, y) = min(A(x), B(y)) Cu aseriunea P rezult consecina: C (y) = sup [min(P (x), A (x), B (y))], y YNotare: D(x,y) = min(P (x), A (x), B (y))x X

Regula generic: Rk : DAC x1 este Ak,1 I... I xi este Ak,i I... I xn este Ak,n ATUNCI y este Bk CU Gk Rezultatele trebuie agregate pentru rezolvarea contradiciilor dintre concluziile regulilor.Inteligena Artificial 111 2011 George Savii

Raionament nuanat exemplu simpluFie regulile: R1 : DAC este lemn ATUNCI este mediu CU 0,2 R2 : DAC este lemn ATUNCI este scump CU 0,8 R3 : DAC este plastic ATUNCI este ieftin CU 0,5 R4 : DAC este plastic ATUNCI este mediu CU 0,5 R5 : DAC este metal ATUNCI este mediu CU 1. Fie aseriunea: creion = lemn/0,9 + plastic/0,1 Utiliznd operatorul MAX-MIN, n urma inferenei rezult: R1 = mediu/(0,9 0,2) = mediu/(min(0,9; 0,2)) = mediu/0,2 R2 = scump/(0,9 0,8) = scump/(min(0,9; 0,8)) = scump/0,8 R3 = ieftin/(0,1 0,5) = ieftin/(min(0,1; 0,5)) = ieftin/0,1 R4 = mediu/(0,1 0,5) = mediu/(min(0,1; 0,5)) = mediu/0,1 R5 = mediu/(0 1) = mediu/(min(0; 1)) = mediu/0 Prin agregare se obine: creion = ieftin/0,1 + mediu/(max(0,2; 0,1; 0) + scump/0,8 adic: creion = ieftin/0,1 + mediu/0,2 + scump/0,8Inteligena Artificial 112 2011 George Savii

56

12/29/2011

Raionament nuanat exemplu simplu


113

2011 George Savii

Variabile lingvisticeVariabilele lingvistice se caracterizeaz prin aceea c primesc valori lingvistice (nu numerice, precum variabilele obinuite). O mulime nuanat poate fi considerat corespunztoare unei valori lingvistice precum "scump" sau "ieftin", iar variabila lingvistic "cost" poate fi considerat ca lund astfel de valori lingvistice Un important avantaj al variabilelor lingvistice este abilitatea de a accepta modificatori lingvistici:


114

2011 George Savii

57

12/29/2011

Variabile lingvisticeO variabil lingvistic poate fi definit ca un cvintuplu (x, T (x), G, U, M), n care: x este numele variabilei; T (x) - mulimea valorilor lingvistice ale variabilei x, fiecare valoare fiind o variabil nuanat n U ; T este o mulime numrabil; G - regula de generare a elementelor din T; de obicei G este o gramatic independent de context, caz n care T este limbajul generat de G ; U - universul de discurs; M - regula semantic de ataare a semnificaiei ctre fiecare valoare lingvistic a x, sub forma unei mulimi nuanate pe universul U. De exemplu, dac x = cost definit pe U = [0, 2], se pot alege: T (cost) = {ieftin, moderat, scump} , M (scump) = mulimea nuanat pentru "cost peste 1,5 RON/kg", cu funcia de apartenen scump, ce poate fi definit analitic: =0, u 1,5.Inteligena Artificial 115 2011 George Savii

Variabile lingvisticeProcesul de definire a unei variabile nuanate are dou etape: 1.Se stabilete nivelul de cuantizare, adic numrul de valori lingvistice pe care s le poat lua variabila respectiv, deci numrul de submulimi nuanate aferente.Dependent de problema concret de rezolvat, se stabilesc universurile variabilelor de intrare (din antecedente) i de ieire (din consecvente). Aceste universuri vor fi segmentate corespunztor cuantizrii stabilite. Pentru etichetarea submulimilor nuanate se utilizeaz, n mod obinuit, valori lingvistice, ceea ce face ca regulile s poat fi scrise n form natural. Exemple tipice de cuantizare sunt: temperatura: foarte fierbinte, fierbinte, cald, normal, rcoros, rece, foarte rece; viteza: foarte repede, repede, mediu, ncet, foarte ncet; nivelul: foarte nalt, nalt, mijlociu, cobort, foarte cobort. Exist un set standard de etichete, ce se potrivete mrimilor de tip eroare: foarte negativ, negativ mediu, negativ mic, zero, pozitiv mic, pozitiv mediu, foarte pozitiv.2.Fiecrei etichete i se ataeaz o submulime nuanat, definit prin funcia ei de apartenen.


116

2011 George Savii

58

12/29/2011

Difuzarea ("fuzzificarea")

Difuzarea realizeaz trecerea de la valorile fizice din realitate, la valori nuanate, n termenii etichetelor lingvistice utilizate n premisele regulilor, n vederea procesrii prin raionament nuanat. De exemplu, pentru sistemele de comand nseamn transformarea valorilor obinute de la traductoare, n valori lingvistice cu diverse grade de apartenen.


117

2011 George Savii

Concentrarea ("defuzzificarea")Concentrarea, numit i decompoziie sau dezambiguizare, este faza final n cadrul raionamentului nuanat. Este procesul de obinere a unui scalar din mulimea nuanat reprezentnd rezultatul unui raionament nuanat. Rezultatul este, n sistemele de conducere, valoarea unei variabile de comand. Procesul de concentrare izoleaz o valoare din universul de discurs, fcnd trecerea de la reprezentarea nuanat la reprezentarea numeric, adecvat sistemelor fizice. Metodele de maxim analizeaz muchiile spaiului nuanat i selecteaz valoarea din univers pentru care valoarea de adevr este maxim: = {u* | A(u*) A(u), u U } Metodele de moment produc valoarea concentrat a unei variabile din consecine prin calculul centrului unui moment static de ordinul zero sau unu al regiunii mulimii nuanate rezultat: u* = (U u A(u)du)/( U A(u)du) .Inteligena Artificial 118

Putere 1

0 0

10

u* 20 Putere [W]

Decompoziie prin maxim (MoM)Putere 1

0 0

10 u*

20 Putere [W]

Decompoziie prin centrul de mas (COG)

2011 George Savii

59

12/29/2011

Exemplu de raionament nuanatR1 : DAC x1 este A11 I x2 este A21 ATUNCI y este B1 R2 : DAC x1 este A12 I x2 este A22 ATUNCI y este B21 A11 1 A21 agregare min min 0 0 A12 1 0 1 min 0 x1i difuzare 0 1 activare: min B1

x1

0

0 A22

x2

0

0 B2

y

1

x1

0 x2i

x2

0

0

acumulare max

y

decompoziie COG 0 y*119

y2011 George Savii


Bazele sistemelor de reglare automat nuanatprogram eroare Regulator comanda Proces automat ieire stare Traductor

Regulatoarele nuanate (fuzzy) au fost introduse de Mamdani (1974), n special pentru cazurile n care nu exist un model precis al procesului, iar cea mai mare parte a informaiei a priori este disponibil n form calitativ. S-a pornit de la observaia c un operator uman este cteodat mai eficient dect un sistem automat pentru comanda unor astfel de procese. Strategiile intuitive de conducere utilizate de operatorii experimentai pot fi considerate drept algoritmi nuanai.Inteligena Artificial 120 2011 George Savii

60

12/29/2011

Bazele sistemelor de reglare automat nuanatMecanismul de inferen implementat de obicei n regulatoarele nuanate este bazat pe o schem modus ponens generalizat. Strategia Mamdani este bazat pe operatorul MAX-MIN pentru inferen (acumulare cu maxim - implicaie cu minim). Strategia Larsen este bazat pe operatorul MAX-PROD pentru inferen (acumulare cu maxim - implicaie cu produs). Strategia Tsukamoto este bazat pe o simplificare a metodei Mamdani, pentru cazul n care toate funciile de apartenen (antecedente i concluzii) sunt monotone. Strategia Sugeno este bazat pe o descriere diferit a modelului: variabilele de comand sunt definite ca funcii de variabilele de stare.


121

2011 George Savii

Structura unui regulator nuanatbaza de cunotine decompoziie

program

eroarea i modific.

inferena nuanat

comenzi

Proces

ieire

Etapele procesrii informaiei: difuzarea (dup eventual normalizare) agregarea antecedentelor: compunerea valorilor pentru fiecare intrare; inferena: prelucrarea regulilor pentru a stabili gradul de declanare a fiecreia; activarea (compoziia): gradul de declanare a fiecrei reguli este aplicat asupra mulimii nuanate de ieire, conform implicaiei; acumularea (agregarea concluziilor); decompoziia (eventual cu denormalizare).Inteligena Artificial 122 2011 George Savii

difuzare

regulator nuanat Traductoare

61

12/29/2011

Generarea regulilor nuanateutilizarea experienei unui expert i a cunotinelor de ingineria reglrii automate:este cea mai puin structurat, dar cea mai utilizat metod;

urmrirea aciunilor de comand ale operatorului:ncearc modelarea aciunilor unui operator cu experien; are avantajul c, de regul, aciunile operatorului sunt mai uor de modelat dect procesul (operatorul poate fi ntrebat ce informaii din proces folosete pentru a decide comenzile); are dezavantajul c se poate aplica doar la procese relativ lente;

utilizarea modelului nuanat al procesului:descrierea lingvistic a caracteristicii dinamice a unui proces poate fi considerat ca un model nuanat al procesului; identificarea se bazeaz pe analiza nregistrrilor rspunsurilor sistemului la secvene de semnale de intrare prototip; regulile generate sunt de tipul: dac la momentul t variabila de comand este Bt i starea sistemului este At, atunci la momentul t+1 starea sistemului va fi At+1; pe baza modelului nuanat se pot genera reguli de reglare nuanate; metoda este mai complex, dar produce rezultate mai bune i are o fiabilitate mai mare; de asemenea, permite o analiz teoretic a sistemului i este aplicabil proceselor rapide;

prin nvare:pentru a putea emula comportamentul operatorilor umani n luarea deciziilor, regulatoarele pot fi prevzute cu capacitatea de nvare, adic de generare automat de reguli sau de modificare a celor deja existente n baz; capacitatea de nvare este bazat, de obicei, pe reele neuronale i algoritmi genetici.


123

2011 George Savii

Exemplu de sistem cu reglare nuanat Reglarea nivelului apei n rezervorQinmax cpompa Qin Qiefix Qie Qievar1 sh

1 s

cPompa Osc erh du/dt derh dpompa

1 1/A hprog

Volum

dPompa

Nivelul apei din rezervor se poate determina din: h = h0 + t (Qin(t) Qie(t))/Adt , n care: h0 este nivelul la momentul iniial; Qin(t) debitul apei care intr n rezervor (pompat); Qie(t) debitul apei care ias din rezervor (la consum); A aria bazei rezervorului (cilindric); t intervalul de timp considerat.Inteligena Artificial 124 2011 George Savii

62

12/29/2011

Etapele proiectrii regulatorului1.Stabilirea

numrului de variabile de intrare: dou (erh i derh), i de ieire: una (dpompa). 2.Stabilirea universurilor, numrului i etichetei valorilor nuanate pentru fiecare variabil:erh: trei valori: NE, ZE i PO, corespunznd erorilor negative, n jur de zero i, respectiv, pozitive, pe universul [-2,2]; derh: trei valori: NE, ZE i PO, corespunznd derivatelor negative, n jur de zero i, respectiv, pozitive, pe universul [-2, 2]; dpompa: cinci valori, pentru o reglare mai fin: SR, SN, OK, CN i CR, corespunznd scderii rapide, scderii cu rat normal, pauzei (meninerii), creterii cu rat normal, respectiv creterii rapide a debitului, pe universul [-10, 10].3.Definirea 4.Stabilirea

euristic. 5.Toate regulile sunt considerate cu grad maxim de ncredere (pondere 1). 6.Funciile pentru agregarea antecedentelor se aleg: minimum pentru conjuncie i maximum pentru disjuncie. 7.Pentru implicaie (activare) este utilizat funcia minimum. 8.Pentru acumulare se alege funcia maximum. Rezult operatorul compoziional MAX-MIN (sistem Mamdani). 9.Pentru decompoziie se alege metoda centrului de greutate.

funciilor de apartenen pentru valorile nuanate: se aleg de tip triunghiular. setului de reguli: setul complet are 33=9 reguli simple, ce sunt stabilite


125

2011 George Savii

Parametrii regulatorului 1 NE ZE PO 1 SR SN OK CN CR

0 -2

-1

0

1

2 erh,derh

0 -10

-5

0

5

10 dpompa

Funciile de apartenen pentru variabilele erh i derh

Funciile de apartenen pentru variabila dpompa


126

2011 George Savii

63

12/29/2011

Logica nuanat n procese decizionaleO problem clasic de decidere cu alternative multiple poate fi exprimat matriceal. O matrice de decizie pentru m alternative i n criterii are dimensiunile m n i elementele xij indicnd calificativul performanei alternativei i (Ai) din punct de vedere al criteriului j (Cj). n formulare nuanat, criteriile cuprind att funciile obiectiv, ct i condiiile. Matricea deciziei descrie relaia nuanat ntre alternative i criterii. Relaia nuanat S de la A la C este o submulime nuanat a produsului cartezian: S = {(a, c), S(a, c) | a A, c C} , n care S(a, c) este funcia de apartenen a mulimii nuanate a relaiei S, obinut pe baza calificativelor X. Matricea S poart i numele de matricea satisfaciilor, indicnd gradele relative n care fiecare alternativ satisface fiecare criteriu.Inteligena Artificial 127 2011 George Savii

Bazele procesului decizional nuanatPentru a selecta alternativa ctigtoare A*, pot fi luate n considerare importane diferite ale criteriilor i/sau grade diferite de optimism. Iniial sunt definii vectorul criteriilor (obiective i condiii) C = {cj} i vectorul alternativelor A = {ai}, i = 1, 2,.., m, j = 1, 2,..., n. Pentru a converti valorile fizice (obinute prin numrare, msurare, notare etc.) n grade de apartenen, poate fi definit cte o mulime nuanat j pentru fiecare criteriu. Pentru a putea lua o decizie, alternativele n discuie trebuie ordonate pe baza unor scoruri calculate conform unui algoritm ce ine cont de gradele de ndeplinire a unor criterii date. Pentru combinarea gradelor de ndeplinire a criteriilor de ctre o alternativ, se aplic operatori de agregare. n scopul introducerii unui mecanism de realizare a compromisurilor, a compensrilor ntre gradele de ndeplinire a criteriilor, sunt utilizate diverse tipuri de medieri (aritmetic, geometric, armonic).


128

2011 George Savii

64

12/29/2011

Ordonarea nuanat cu criterii de importan egalAbordarea pesimistn abordarea pesimist se cere ndeplinirea tuturor criteriilor, ceea ce revine la aplicarea conjunciei ntre criterii pentru a calcula scorul fiecrei alternative: Ai = xi 1 xi 2 ... xij ... xin , i = 1, 2,..., m, n care xij este valoarea nuanat asociat satisfacerii criteriului j de ctre alternativa i. Funcia (mulimea) nuanat a deciziei, definit pe mulimea alternativelor z A, devine: D(z) = C1(z) C2(z) ... Cj(z) ... Cn(z) , n care Cj(z) este valoarea criteriului j evaluat pentru alternativa z. Modelnd conjuncia cu funcia minimum, rezult: Ai = min(xi 1, xi 2,..., xin) , i = 1, 2,..., m, adic: D(z) = min(C1(z), C2(z),..., Cn(z)) . Ctigtoare este alternativa cu scor maxim: A* = {Ak | min xkj = max min xij}j=1,n i=1,m j=1,n

Abordarea pesimist minimizeaz pierderea maxim. Este o abordare conservatoare.Inteligena Artificial 129 2011 George Savii

Abordare pesimist: exemplul 1Se consider problema deciziei privind tipul de autoturism ce s fie cumprat. Se dau alternativele: A = {AlfaSN, BetaGT, GamaGL, DeltaXL} i criteriile: C = {putere, calitate, pre}. Pentru luarea deciziei, nu este necesar transformarea notelor n grade de satisfacie pe intervalul [0, 1]. Se pot aplica direct relaiile pentru rezolvare: D(z) = min(C1(z), C2(z), C3(z), C4(z)) = {1, 3, 7, 6} z* = arg(max D(z)) = 3.zA

Ctigtoare n abordarea pesimist este alternativa 3, autoturismul GamaGL, care are cel mai mare minim (7).Inteligena Artificial 130 2011 George Savii

65

12/29/2011

Abordare pesimist: exemplul 2Un investitor caut o soluie pentru a-i valorifica disponibilul. Are trei variante, n domenii diferite, pentru care profitul este diferit funcie de evoluia ratei dobnzii. Pentru a maximiza profitul minim pe care-l poate obine, evideniaz profiturile minime:

D(z) = min(C1(z), C2(z), C3(z)) = {1000, 3000, 5000} z* = arg(max D(z)) = 3. Decizia este de a nvesti n a treia societate, pentru a avea un profit mare n orice condiii.Inteligena Artificial 131 2011 George Savii

zA

Ordonarea nuanat cu criterii de importan egalAbordarea optimistn abordarea optimist se cere ndeplinirea cel puin a unui criteriu, ceea ce revine la aplicarea disjunciei ntre criterii: Ai = xi 1 xi 2 ... xij ... xin , i = 1, 2,..., m, deci mulimea nuanat a deciziei poate scrie: D(z) = C1(z) C2(z) ... Cj(z) ... Cn(z) . Modelnd disjuncia cu funcia max, rezult: Ai = max(xi 1, xi 2,..., xin) , i = 1, 2,..., m, adic: D(z) = max(C1(z), C2(z),..., Cn(z)) . Ctigtoare este alternativa cu scor maxim: A* = {Ak | max xkj = max max xij}j=1,n i=1,m j=1,n

Abordarea optimist maximizeaz profitul maxim obtenabil. Este o abordare riscant.Inteligena Artificial 132 2011 George Savii

66

12/29/2011

Abordare optimist: exemplu

Se consider problema de decizie de la exemplul 1 pesimist. Se aplic relaiile pentru rezolvare: D(z) = max(C1(z), C2(z), C3(z), C4(z)) = {9, 8, 8, 8} z* = arg(max D(z)) = 1.zA

Ctigtoare n abordarea optimist este alternativa 1, autoturismul AlfaSN, care are cel mai mare maxim (9). Decizia optimist este discutabil, pentru c nu ine cont de dezavantajele alternativei.Inteligena Artificial 133 2011 George Savii

Ordonarea nuanat cu criterii de importan egalAbordarea concesiv:sunt admise compromisuri pentru a permite compensri ntre gradele de satisfacere a criteriilor, ntre pierderi i ctiguri pentru modelarea compromisurilor sunt utilizai operatori de mediere.

Abordarea pentru regret minim:

regretul este definit ca diferena de la valoarea curent a unui criteriu la valoarea maxim a criteriilor pentru o alternativ dat matricea regretelor R se calculeaz din matricea calificativelor, X, avnd elementul general: rij = min xij xijj=1,n


134

2011 George Savii

67

12/29/2011

Ordonarea nuanat cu criterii de importan diferitFie X un set de entiti de ordonat. Este natural s fie comparate n perechi. Pentru a desemna importana relativ sunt utilizate, de obicei, valori pe scara de la 1 la 9 cu semnificaia: 1 pentru importane egale; 3 mic superioritate; 5 superioritate puternic; 7 superioritate demonstrat; 9 superioritate absolut, 2, 4, 6 i 8 valori intermediare. Pentru o pereche de entiti x i y, gradele relative de importan se stabilesc astfel nct (x, y) . (y, x) = 1. Gradele relative pot fi calculate din gradele de importan W (x ), x X atribuite entitilor de comparat: (x,y ) = W (x ) / W (y ) . Din matricea gradelor relative de importan trebuie obinut un vector al factorilor de importan. Acest vector, V, este determinat ca vectorul propriu al matricei M a gradelor relative (M = [(x,y)]), ce corespunde valorii proprii maxime max . n continuare trebuie calculate scorurile alternativelor, de exemplu exponenial: Ai =F ((gij)pj), n care F=max/min pentru abordare optimist/pesimist, gij este calificativul alternativei i pentru criteriul j, iar p este vectorul factorilor de importan scalat.Inteligena Artificial 135 2011 George Savii

Ordonarea nuanat cu criterii de importan diferit: exempluSe consider exemplul 1 de la abordarea pesimist cu criterii de egal importan. Fie importanele criteriilor C = {6, 9, 9}. Se aplic o deriv astfel nct elementul minim s fie unitar: W = C min(C ) + 1 = {1, 4, 4}. Matricea gradelor relative, M, are valoarea: Valoarea proprie cea mai mare este 3, iar vectorul propriu corespunztor scalat la sum egal cu dim(V ) = 3 este: P = {1/3 4/3 4/3}. Matricea de decizie este transformat n matricea calificativelor G prin scalare pe domeniul [0, 1]: A1 = min {0,51/3, 0,14/3, 0,94/3} = 0,046 A2 = min {0,61/3, 0,34/3, 0,84/3} = 0,201 A3 = min {0,71/3, 0,84/3, 0,74/3} = 0,622 A4 = min {0,81/3, 0,84/3, 0,64/3} = 0,506 Ctigtoare este alternativa de scor maxim, A3 = GamaGL.


136

2011 George Savii

68

12/29/2011

Metode cu metrici adimensionalePentru exprimarea funciilor obiectiv n problemele complexe de optimizare, acestea pot fi formulate ca probleme Min-Max. Formularea Min-Max este bazat pe minimizarea distanei relative de la o soluie-candidat la soluia utopic. Distana ntre o soluie-candidat i soluia utopic (dorit) este exprimat tipic ca o norm:

G = [gij] este matricea de decizie; gid - valoarea dorit pentru gi ; - parametru; =1 pentru formularea simplex (compensare perfect), =2 pentru distana euclidian; pi - ponderile criteriilor, pi > 0, pi = 1.Inteligena Artificial 137 2011 George Savii

Metode cu metrici adimensionale: exemplu

Cu ponderile pi i exponentul unitare: A = {-0.936 -1.664 5.111 5.717 1.983 4.461 3.300 -0.306 0.644 2.581} deci ctigtor este proiectul P8.Inteligena Artificial 138 2011 George Savii

69

12/29/2011

ALGORITMI GENETICIPentru a rezolva problemele specifice tehnicilor de gradient, precum blocarea n minime locale sau nedifereniabilitatea, sau tehnicilor de cutare n spaiul strilor, au fost explorate tehnici globale de cutare, ce nu se bazeaz pe derivate, cum sunt: recoacerea simulat, algoritmii genetici, cutarea aleatorie, programarea liniar. Cea mai cunoscut paradigm pentru astfel de cutri este calculul evolutiv, domeniu al inteligenei artificiale. Aceast paradigm acoper mai multe variante, precum: strategiile evolutive, pentru optimizarea continu a funciilor; programele evolutive, care genereaz automate cu stri finite ce descriu strategii sau comportamente; algoritmii genetici, ce permit optimizri de funcii continue sau discrete, sinteze de sisteme, ajustare, testare etc.; programarea genetic, programe de calculator evolutive pentru rezolvarea aproximativ a problemelor, cum ar fi generarea de expresii executabile pentru aproximarea seriilor de timp.


139

2011 George Savii

Calculul evolutiv - principiiPrincipalele trei clase de metode algoritmii genetici, strategiile evolutive i programarea evolutiv au multe similariti. Fiecare este bazat pe o populaie de soluii de testat, impune modificri aleatorii soluiilor respective i utilizeaz selecia pentru a determina care dintre soluii s fie meninute n generaiile urmtoare. Algoritmii genetici pun accentul pe operatori genetici observai n natur, precum ncruciarea, inversiunea, mutaia, pe care i aplic unor cromozomi abstraci. Strategiile i programele evolutive pun accentul pe transformri prin mutaii care menin legtura comportamental ntre fiecare printe i descendenii si. Algoritmii genetici sunt inspirai din teoria evoluiei speciilor. Au fost introdui de J. H. Holland (1975). Analiza matematic a acestora a dovedit c algoritmii genetici naturali au o eficien deosebit n cutri i optimizri. Un caz special al algoritmilor genetici este metoda cunoscut sub numele de recoacere simulat. Este o versiune mai restrictiv a algoritmilor genetici, n care nu au loc ncruciri, mutaiile sunt controlate de bariere energetice, iar populaia tipic este de un individ.Inteligena Artificial 140 2011 George Savii

70

12/29/2011

Fundamente biologicen fiecare celul, informaia privind evoluia este stocat n cromozomi, care sunt lanuri de acizi nucleici (ADN i ARN). Un segment din molecula de ADN, care determin sinteza unei catene polipeptidice poart numele de gen. Gena are o funcie biochimic unitar i un efect specific asupra caracterelor organismului (de exemplu culoarea ochilor). Setul complet de material genetic poart numele de genom. Totalitatea fondului de gene ale unei populaii determin genotipul. Manifestarea vizibil, n realitatea fizic, a informaiilor din gene constituie fenotipul. Gena este un segment genotipic, cromozomul fiind un lan de gene. Variantele de gene ce pot ocupa un anumit loc n cromozom poart numele de alele.


141

2011 George Savii

Reproducerean procesul reproducerii organismelor vii au loc: ncruciarea mutaii, de obicei cauzate de:erori de copiere a genelor de la prini factori externi (radiaii etc.)

Unele modificri ale genelor vor fi nefavorabile, indivizii respectivi avnd anse mai mici de a transmite informaia genetic unor descendeni. Modificrile favorabile vor face ca indivizii respectivi s aib anse mai mari de a transmite informaia genetic.


142

2011 George Savii

71

12/29/2011

Principiile algoritmilor genetici1. Start: generarea aleatorie a n cromozomi (genotipuri fezabile); 2. Testarea adecvrii: evaluarea gradului de adecvare (fitness) al fiecrui cromozom relativ la problema dat, pe baza fenotipului corespunztor; 3. Crearea unei noi populaii:3.1. Selecia: alegerea aleatorie a unei perechi de cromozomi ca prini, dependent de gradul de adecvare al lor; 3.2. ncruciarea: combinarea probabilistic a unor pri din cromozomii-prini pentru a crea noi cromozomi, descendenii; unii descendeni pot fi obinui prin duplicare (ncruciare 0%/100%); 3.3. Mutaia: modificarea aleatorie a noilor cromozomi; 3.4. Validarea: verificarea fezabilitii noilor cromozomi i corectarea lor la nevoie; 3.5. Acceptarea: plasarea noilor cromozomi n noua populaie;

4. nlocuirea: plasarea populaiei nou-create n locul vechii populaii; 5. Testarea terminrii: verificarea condiiei de oprire a algoritmului i terminarea dac este cazul; 6. Reluarea ciclului: de la pasul 2.


143

2011 George Savii

CodareaCodarea este necesar pentru a face trecerea de la fenotip (valorile din realitate) la genotip (cromozom). Pentru a vedea proprietile indicate de gene este necesar o decodare, adic trecerea de la genotip la fenotip. Modul n care valorile variabilelor de decizie sunt codate n cromozomi depinde de tipul problemei. Principalele tipuri: binar cu valori numerice simbolic cu arboriInteligena Artificial 144 2011 George Savii

72

12/29/2011

Codarea binarFiecare gen conine un ir de cifre binare ce pot:reprezenta binar valori numerice (zecimale); semnifica existena sau inexistena unei proprieti.

Exemplul 1: pentru problema cutrii minimului unei funcii de dou variabile, cromozomul va avea dou gene, fiecare fiind reprezentarea binar a valorii uneia din variabile; dac variabilele sunt definite pe intervalul [0, 100] i cromozomul are 20 de bii, atunci configuraia: 01100011001101101101 corespunde valorilor: x = 0110001100B100D/1111111111B 38,7 y = 1101101101B100D/1111111111B 85,7 cu o precizie de 100/(2101) 0,1. Exemplul 2: n probleme de mpachetare, valorile biilor indic dac un obiect este sau nu n pachet (container).


145

2011 George Savii

Codarea cu valori numericeGenele conin direct valori, deci cromozomul va fi un ir de valori numerice reale, de exemplu:

Exemplu: pentru problema antrenamentului reelelor neuronale, cnd trebuie aflat combinaia de valori pentru ponderi care realizeaz eroarea minim ntre ieirile calculate i cele impuse, cromozomii vor fi iruri de valori numerice ale ponderilor.


146

2011 George Savii

73

12/29/2011

Codarea simbolicFiecare gen conine un simbol. Pentru problemele de permutare, simbolul poate fi numrul de ordine dintr-o secven (caz n care fiecare simbol poate aprea o singur dat n cromozom). Problema tipic este cea a comis-voiajorului, n care trebuie gsit ordinea n care s fie parcurse oraele dintr-o list dat pentru ca lungimea total a traseului s fie minim. O pereche tipic de cromozomi poate avea forma: DGBHACFE EHDACFBG n care genele conin simbolurile localitilor de ordonat.


147

2011 George Savii

Codarea cu arboriCromozomul este reprezentat ca un arbore de obiecte. Este utilizat n programarea genetic i n programele evolutive. Cromozomul conine operatori, operanzi, funcii. Un exemplu tipic de utilizare este n problemele de gsire a unei funcii ce produce o relaie dat.

+ * x 7 y / 2


148

2011 George Savii

74

12/29/2011

Gradul de adecvareCalitatea unui cromozom este apreciat prin gradul de adecvare, gradul n care cromozomul respectiv este eficient, adic gradul n care fenotipul corespunztor satisface problema. Poate fi calculat, de exemplu, dependent de valoarea funciei obiectiv ce trebuie maximizat sau minimizat. Pentru problemele de proiectare n care se cere realizarea unui sistem pentru producerea unui ansamblu de valori prestabilite ale unor atribute, adecvarea poate fi apreciat prin abaterea medie ptratic a rezultatelor produse de sistemul descris de cromozomul respectiv, fa de rezultatele dorite.


149

2011 George Savii

SeleciaPentru selecie se aplic o metod probabilistic, eantionarea universal stocastic, numit i metoda ruletei. Fiecrui cromozom i se ataeaz o probabilitate de a fi ales ce depinde de gradul su de adecvare. Dac gama gradelor de adecvare este mic, probabilitile de selecie pot fi proporionale cu gradele de adecvare. Dac gama gradelor de adecvare este mare, cromozomii mai puin adecvai vor avea anse aproape nule de a fi selectai cu metoda proporional, toi descendenii tinznd s semene cu prinii cu adecvare mare, devenind uniformi. De aceea, probabilitatea ca un cromozom s fie selectat trebuie optimizat prin:aplicarea rdcinii ptrate pe valoarea adecvrii majorat cu o unitate; aplicarea unei transformri liniare asupra valorilor adecvrii; normalizare liniar: probabilitatea de selecie se ia proporional cu rangul cromozomului ntr-o clasificare funcie de adecvare, i nu proporional cu adecvarea.


150

2011 George Savii

75

12/29/2011

Selecia cu normalizare liniar

"Ruleta" pentru valori ale adecvrii prea diferite

"Ruleta" cu normalizare liniar


151

2011 George Savii

ncruciareaPrin ncruciare (crossover) sunt combinate probabilistic pri din cromozomii-prini pentru a crea noi cromozomi, descendenii. O modalitate simpl de realizare a ncrucirii este prin alegerea aleatorie a unui punct de ncruciare (ntre dou gene) i preluarea unei pri de la un printe i a celeilalte pri de la cellalt printe.


152

2011 George Savii

76

12/29/2011

ncruciareaCnd codarea este prin permutare, pentru a obine cromozomi utilizabili (fezabili), dup ce a fost copiat prima parte de la un cromozom, restul se completeaz de la cellalt cromozom pornind de la nceputul lui, cu gene care nu exist nc.

Pentru ca cea mai bun soluie curent s nu fie pierdut, se aplic tehnica elitismului, adic cromozomii (de obicei doi) cu cea mai bun adecvare sunt copiai (duplicai, "clonai") n noua generaie. Duplicarea este un caz particular al ncrucirii, cnd tierea se face chiar la captul cromozomului.Inteligena Artificial 153 2011 George Savii

MutaiaOperaia de tip mutaie are rolul de a ajuta la evitarea capcanelor reprezentate de minimele/maximele locale. Noul cromozom, obinut dup ncruciare, este modificat aleatoriu. n cazul codrii binare, sunt inversate valorile biilor selectai aleatoriu pentru mutaie (0 1, 1 0). Cnd codarea este tip permutare, se vor schimba ntre ele locurile a dou gene alese aleatoriu. n cazul codrii cu valoare, se adaug o valoare mic pozitiv sau negativ la valorile genelor selectate. Mrimea valorii adugate poate fi controlat prin parametrul nivelul radiaiei. Pentru codarea cu arbore, se modific valoarea din nod (operatorul sau operandul). Este recomandat o probabilitate de aplicare a mutaiei de 0,54%.


154

2011 George Savii

77

12/29/2011

Exemplu: gsirea minimului unei funcii de dou variabilez(x,y) = x sin(x) + y sin(y) x[0,100], y[0,100] function z = fitness(x,y) z=x.*sin(x)+y.*sin(y); Considernd o populaie P de m cromozomi de cte n bii (n par), se adopt codare binar, cu dou gene: primii n/2 bii corespund valorii x, iar ultimii n/2 valorii y. Decodare: x=bin2dec(P(:,1:n/2),n/2) * kx + xmin; y=bin2dec(P(:,n/2+1:n),n/2) * ky + ymin; ky = (ymaxymin) / (2n/21) ; kx = (xmaxxmin) / (2n/21) ;


155

2011 George Savii

Exemplu (cont.)Iteratia: 6, valoarea:-115.1256, cromozomul: 00101100101111110110 Iteratia:10, valoarea:-121.4047, cromozomul: 00111100101111110110 Iteratia:17, valoarea:-146.5285, cromozomul: 01111100101111110110 Iteratia:19, valoarea:-193.9613, cromozomul: 11111100101111110110 Iteratia:25, valoarea:-195.7063, cromozomul: 11111101101111110110 Iteratia:28, valoarea:-196.7158, cromozomul: 11111101001111110110 Iteratia:37, valoarea:-197.7252, cromozomul: 11111101001111110100 Optimul la: x=98.9247 y=98.9247 Valoare obiectiv: -197.7252 Cromozomul: 11111101001111110100 [x,fval]=fminsearch(inline... ('x(1)*sin(x(1))+x(2)*sin(x(2))'),[-98.9247, -98.9247]) fval = 197,9304 la x1 = x2 = 98,9702Inteligena Artificial 156 2011 George Savii

78

12/29/2011

Exemplu: problema comis-voiajoruluicodare binar a celor p localiti, cu bpp = ceil(log(p)/log(2)) bii pe gen; numrul de bii pe cromozom rezult n = bpp.p adecvarea: suma distanelor ntre localiti Iteratia: 2, Perimetrul:4055, Calea: 4 5 6 8 9 7 1 2 10 3 Iteratia: 3, Perimetrul:3655, Calea: 4 5 6 8 9 7 1 10 2 3 Iteratia:13, Perimetrul:3272, Calea: 1 4 5 6 7 8 9 10 3 2 Iteratia:14, Perimetrul:2918, Calea: 4 5 6 8 7 9 10 1 2 3 Iteratia:16, Perimetrul:2472, Calea: 4 5 6 7 8 9 10 1 2 3


157

2011 George Savii

Avantaje i dezavantajeparalelismul: sunt prelucrate simultan mai multe soluii, deci este mai robust la minimele locale; uurina implementrii: de la o problem la alta trebuie modificat doar funcia pentru calculul gradului de adecvare; posibilitatea de codare a diverse proprieti, deci rezolvarea de probleme de mare diversitate, fr a avea cunotine prealabile despre funcia de optimizat; nu necesit calcularea unor valori auxiliare, precum gradientul, deseori imposibil de realizat; permit depirea limitelor abordrilor intuitive n proiectare. Dezavantajul principal este durata mare pentru soluionare.


158

2011 George Savii

79

12/29/2011

Aplicaii: categorii

planificarea proiectarea identificarea i simularea conducerea clasificarea


159

2011 George Savii

Aplicaii: domeniiplanificarea strategic; planificarea traiectoriilor n robotic; planificarea n probleme de transport (comis-voiajor); probleme de mpachetare; logistic; managementul sistemelor tehnice; planificarea n sistemele de producie; proiectarea reelelor neuronale; proiectarea circuitelor integrate; proiectarea formelor tehnice complexe (profiluri hidro- i aerodinamice pentru turbine, aeronave etc.); optimizarea structurilor mecanice; optimizarea liniilor de fabricaie; optimizarea sistemelor de reglare automat; optimizri n econometrie; alegerea strategiilor de mentenan; determinarea structurii spaiale a proteinelor complexe; data mining (cutarea de relaii ntre date); analiza datelor i prognoza pentru sisteme dinamice neliniare; determinarea fiabilitii sistemelor; identificarea sistemelor n protecia mediului; decizii la bursele de valori; identificarea riscurilor la asigurri; analiza imaginilor (teledetecie, imagistic medical, vedere artificial, criminalistic); clasificarea dovezilor criminalistice


160

2011 George Savii

80

12/29/2011

Raionament probabilisticProbabiliti condiionateP(A) = fraciunea de lumi n care A este adevrat P(A, B) = P(A B) = probabilitatea ca A i B s fie simultan adevrate P(A|B) = probabilitatea lui A, dat fiind B Regul fundamental: P(A B) = P(A|B) * P(B) P(A, B) = P(A|B) * P(B)Inteligena Artificial 161 2011 George Savii

Probabiliti condiionate


162

2011 George Savii

81

12/29/2011

Teorema lui Bayes

P(A B) = P(A|B) * P(B) P(A B) = P(B|A) * P(A) P(B|A) = P(A|B) * P(B) / P(A)


163

2011 George Savii

Teorema lui Bayes Exemplu la diagnozProbabiliti cunoscute:Meningit: P(M) = 0.002% Gt nepenit: P(G) = 5% Meningita cauzeaz gt nepenit: 50%

Dac un pacient are gtul nepenit, care este probabilitatea s aib meningit?P(M|G) = P(G|M) * P(M) / P(G) = 0,02%Inteligena Artificial 164 2011 George Savii

82

12/29/2011

Teorema lui Bayes Exemplu la doveziO localitate are dou companii de taxiuri, Taxi Albastru cu 15 autovehicule i Taxi Negru cu 85 autovehicule. ntr-o noapte are loc un accident cu fuga taximetrului implicat. Toate cele 100 taximetre erau de serviciu la ora respectiv. Un martor vede accidentul i spune c a fost implicat un taximetru albastru. Supus unui test de vedere n condiiile accidentului, martorul greete culoarea n 20% din cazuri. Care companie este cel mai probabil s fie implicat n accident?Inteligena Artificial 165 2011 George Savii

Teorema lui Bayes Exemplu la doveziCunoscnd probabilitile anterioare i probele:P(B) = 0,15; P(B) = 0,85 P(E|B) = 0,8; P(E|B) = 0,2

se determin probabilitile posterioare:P(B|E) = P(E|B) * P(B) / P(E) P(E) = P(E|B) * P(B) + P(E|B) * P(B)

P(B|E) = 0,41


166

2011 George Savii

83

12/29/2011

Teorema lui Bayes Exemplu la dovezi


167

2011 George Savii

Teorema lui Bayes Alt exemplu la diagnozDate:Incidena cancerului X: P(C) = 1% Rezultate fals pozitive la test: P(E|C) = 21%

Dac un pacient obine rezultat pozitiv la test, care este probabilitatea s aib cancerul X?P(C|E) = P(E|C) * P(C) / (P(E|C) * P(C) + P(E|C) * P(C)) = 4,6%


168

2011 George Savii

84

12/29/2011

Reea bayesianS-a instalat un nou sistem de alarm, sun dac e spargere sau e cutremur Vecinii John i Mary sun pe proprietar la serviciu dac aud alarmaInteligena Artificial 169 2011 George Savii

Interogri simpleCare este probabilitatea ca alarma s se declaneze fr s fi fost spargere sau cutremur iar John i Mary s fi sunat? P(J M A B E) = P(J|A)*P(M|A)*P(A|BE)*P(B)*P(E) = 0,9*0,7*0,001*0,999*0,998 = 0,00062


170

2011 George Savii

85

12/29/2011

Reele cauzaleO reea cauzal este un graf direcionat aciclic Nodurile sunt variabile cu o mulime finit de stri ce sunt mutual exclusive i exhaustive Legturile reprezint relaii cauz-efect Exemplu:

Defectul

Manifestarea


171

2011 George Savii

Cuantificarea reelelor cauzaleSalmonella d, n Grip d, n

Grea d, nSalmonella d (0,9; 0,1) (0,8; 0,2) n (0,6; 0,4) (0,1; 0,9)2011 George Savii

P(d | d, d) P(n | d, d) P(d | n, d) P(n | n, d)

P(d | d, n) P(n | d, n) P(d | n, n) P(n | n,n)

P(Grea | Salmonella, Grip) (d; n) d Grip n172


86

12/29/2011

Reelele cauzale probabilistice n diagnosticare Automobilul


173

2011 George Savii

Reelele cauzale probabilistice n diagnosticare Automobilul


174

2011 George Savii

87

12/29/2011

Reelele cauzale probabilistice n diagnosticare - Automobilul


175

2011 George Savii

Reelele cauzale probabilistice n diagnosticare - Accidentul


176

2011 George Savii

88

12/29/2011

Reelele cauzale probabilistice n diagnosticare - Accidentul


177

2011 George Savii

Reelele cauzale probabilistice n fiabilitate


178

2011 George Savii

89

12/29/2011

Reelele cauzale probabilistice n fiabilitate


179

2011 George Savii

Diagrame de influenExtind reelele bayesiene pentru rezolvarea problemelor de decizie, cu dou tipuri de noduri:de decizie: definete aciunile opionale de utilitate: are ca valoare utilitatea rezultatului

Nodul de decizie (dreptunghic/oval) este conectat la nodurile de anse a cror distribuie de probabilitate este direct afectat de decizie Nodul de utilitate (rombic) are o tabel de valori de utilitate pentru toate combinaiile de valori ale nodurilor-printeInteligena Artificial 180 2011 George Savii

90

12/29/2011

Diagrame de influenAciunea Utilitatea: msur a valorii de ntrebuinare Necunoscutele: cu funcii de distribuie de probabilitate Exemplu: Ce este de preferat: A ctiga 100 lei cu probabilitatea 0,0002 A ctiga 10 lei cu probabilitatea 0,001Inteligena Artificial 181 2011 George Savii

ExpectanaEste definit ca i cantitatea medie care poate fi ctigat pentru fiecare unitate riscat, sau mai simplu, profitul tipic pentru o tranzacie. Exist dou variabile n exemplu, fie ele B1 i B2: P(B1 = 0) = 0,9998; P(B1 = 100) = 0,0002 P(B2 = 0) = 0,9990; P(B2 = 10) = 0,0010 Expectanele sunt: E(B1) = 0,9998 x 0 + 0,0002 x 100 = 0,02 E(B2) = 0,9990 x 0 + 0,0010 x 10 = 0,01Inteligena Artificial 182 2011 George Savii

91

12/29/2011

Utilitatea ateptatUtilitatea unei aciuni este utilitatea rezultatului la care conduce Ea depinde, de obicei, de necunoscute Este cutat aciunea ce maximizeaz utilitatea ateptat Exemplu: Ce este de preferat: S accepi 3000 lei siguri S accepi 4000 lei cu pro

inteligenta artificiala

Documents