Home >Documents >INTELIGEN¢‚ ARTIFICIAL‚

INTELIGEN¢‚ ARTIFICIAL‚

Date post:19-Jan-2016
Category:
View:38 times
Download:0 times
Share this document with a friend
Description:
INTELIGENŢĂ ARTIFICIALĂ. Laura Dioşan. Curs 2 Rezolvarea problemelor de căutare Strategii de căutare informată globală şi locală. Sumar. Scurtă introducere în Inteligenţa Artificială (IA) Rezolvarea problemelor prin căutare Definirea problemelor de căutare Strategii de căutare - PowerPoint PPT Presentation
Transcript:
  • INTELIGEN ARTIFICIAL

    Laura DioanCurs 2Rezolvarea problemelor de cutareStrategii de cutare informat global i local

  • Sumar Scurt introducere n Inteligena Artificial (IA)

    Rezolvarea problemelor prin cutareDefinirea problemelor de cutareStrategii de cutareStrategii de cutare neinformateStrategii de cutare informateStrategii de cutare locale (Hill Climbing, Simulated Annealing, Tabu Search, Algoritmi evolutivi, PSO, ACO)Strategii de cutare adversial

    Sisteme inteligenteSisteme bazate pe reguli n medii certeSisteme bazate pe reguli n medii incerte (Bayes, factori de certitudine, Fuzzy)Sisteme care nva singure Arbori de decizieReele neuronale artificialeMaini cu suport vectorialAlgoritmi evolutiviSisteme hibride

  • SumarRezolvarea problemelor prin cutare

    Strategii de cutare informate (euristice) - SCIStrategii globaleBest first searchStrategii localeHill ClimbingSimulated AnnealingTabu search

  • Materiale de citit i legturi utilecapitolul II.4 din S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 1995

    capitolul 3 i 4 din C. Groan, A. Abraham, Intelligent Systems: A Modern Approach, Springer, 2011

    capitolul 2.5 din http://www-g.eng.cam.ac.uk/mmg/teaching/artificialintelligence/

  • Rezolvarea problemelor prin cutareStrategii de cutare (SC)Topologien funcie de informaia disponibilSC ne-informate (oarbe)SC informate (euristice)

  • Strategii de cutare informate (SCI)Caracteristicise bazeaz pe informaii specifice problemei ncercnd s restrng cutarea prin alegerea inteligent a nodurilor care vor fi explorateordonarea nodurilor se face cu ajutorul unei funcii (euristici) de evaluaresunt particulare

    Topologie Strategii globaleBest-first searchGreedy best-first searchA*IDA*Strategii localeCutare tabuHill climbingSimulated annealing

  • SC n structuri arborescenteNoiuni necesaref(n) funcie de evaluare pentru estimarea costului soluiei prin nodul (starea) nh(n) funcie euristic pentru estimarea costului drumului de la nodul n la nodul obiectivg(n) funcie de cost pentru estimarea costului drumului de la nodul de start pn la nodul nf(n) = g(n) + h(n)

    actual estimatstart nobiectiv g(n)h(n)f(n)

  • SCI Best first searchAspecte teoreticeBest first search = nti cel mai bunSe determin costul fiecrei stri cu ajutorul funciei de evaluare fNodurile de expandant sunt reinute n structuri (cozi) ordonate Pentru expandare se alege starea cu cea mai bun evaluare Stabilirea nodului care urmeaz s fie expandatExemple de SC care depind de funcia de evaluareCutare de cost uniform (SCnI)f = costul drumuluin SCI se folosesc funcii euristiceDou categorii de SCI de tip best first searchSCI care ncearc s expandeze nodul cel mai apropiat de starea obiectivSCI care ncearc s expandeze nodul din soluia cu costul cel mai mic

    ExempluDetalii n slide-urile urmtoare

  • SCI Best first searchAlgoritm

    bool BestFS(elem, list){found = false;visited = ;toVisit = {start}; //FIFO sorted list (priority queuewhile((toVisit != ) && (!found)){if (toVisit == ) return falsenode = pop(toVisit);visited = visited U {node};if (node == elem)found = true;elseaux = ;for all unvisited children of node do{aux = aux U {child};}toVisit = toVisit U aux; //adding a node onto the FIFO list based on its evaluation //(best one in the front of list)

    } //whilereturn found;}

  • SCI best first searchAnaliza cutriiComplexitate temporal:b factor de ramnificare (nr de noduri fii ale unui nod)d - lungimea (adncimea) maxim a soluieiT(n) = 1 + b + b2 + + bd => O(bd)Complexitate spaialS(n) = T(n)CompletitudineNu- drumuri infinite dac euristica evalueaz fiecare stare din drum ca fiind cea mai bun alegereOptimalitate Posibil depinde de euristic

    AvantajeInformaiile despre domeniul problemei ajut cutarea (SCI)Vitez mai mare de a ajunge la starea obiectiv

    DezavantajeNecesit evaluarea strilor efort computaional, dar nu numaiAnumite path-uri pot arta ca fiind bune conform funciei euristice

    Aplicaii Web crawlerJocuri

  • SCI Funcii euristiceEtimologie: heuriskein (gr)a gsi, a descoperiStudiul metodelor i regulilor de descoperire i invenie

    UtilitateEvaluarea potenialului unei stri din spaiul de cutareEstimarea costului drumului (n arborele de cutare) din starea curent pn n starea final (ct de aproape de int a ajuns cutarea)

    CaracteristiciDepind de problema care trebuie rezolvatPentru probleme diferite trebuie proiectate sau nvate diferite euristiciSe evalueaz o anumit stare (nu operatorii care transform o stare n alt stare)Funcii pozitive pentru orice stare n h(n) 0 pentru orice stare nh(n) = 0 pentru starea finalh(n) = pentru o stare din care ncepe un drum mort (o stare din care nu se poate ajunge n starea final)

  • SCI Funcii euristiceExemple

    Problema misionarilor i canibalilorh(n) nr. persoanelor aflate pe malul iniial

    8-puzzleh(n) nr pieselor care nu se afl la locul lorh(n) suma distanelor Manhattan (la care se afl fiecare pies de poziia ei final)

    Problema comisului voiajorh(n) cel mai apropiat vecin !!!

    Plata unei sume folosind un numr minim de monezih(n) alegerea celei mai valoroase monezi mai mic dect suma (rmas) de plat

  • SCI - GreedyAspecte teoreticeFuncia de evalaure f(n) = h(n)estimarea costului drumului de la starea curent la starea final h(n)minimizarea costului drumului care mai trebuie parcurs

    Exemplu

    A,D,E,H

    Algoritm

    bool BestFS(elem, list){found = false;visited = ;toVisit = {start}; //FIFO sorted list (priority queuewhile((toVisit != ) && (!found)){if (toVisit == ) return falsenode = pop(toVisit);visited = visited U {node};if (node == elem)found = true;elseaux = ;for all unvisited children of node do{aux = aux U {child};}toVisit = toVisit U aux; //adding a node onto the FIFO list based on its evaluation h(n) //(best one in the front of list)

    } //whilereturn found;}ABCDHIEFG44202133

    Vizitate dejaDe vizitatAAD, B, CA, DE, F, G, B, CA, D, EH, I, F, G, B, CA, D, E, H

  • SCI - GreedyAnaliza cutrii:Complexitate temporal DFSb factor de ramnificare (nr de noduri fii ale unui nod)dmax - lungimea (adncimea) maxim a unui arbore exploratT(n) = 1 + b + b2 + + bdmax => O(bdmax)Complexitate spaial BFSd - lungimea (adncimea) soluieiS(n) = 1 + b + b2 + + bd => O(bd)CompletitudineNu (exist posibilitatea intrrii n cicluri infinite)Optimalitate posibil

    Avantaje Gsirea rapid a unei soluii (dar nu neaprat soluia optim), mai ales pentru probleme miciDezavantaje Suma alegerilor optime de la fiecare pas nu reprezint alegerea global optim Ex. Problema comisului voiajor

    AplicaiiProbleme de planificareProbleme de sume parialePlata unei sume folosind diferite tipuri de moneziProblema rucsaculuiPuzzle-uriDrumul optim ntr-un graf

  • SCI A*Aspecte teoreticeCombinarea aspectelor pozitive alecutrii de cost uniform optimalitate i completitudineutilizarea unei cozi ordonatecutrii Greedy viteza mare ordonare pe baza unei funcii de evaluareFuncia de evalaure f(n)estimarea costului celui mai bun drum care trece prin nodul nf(n) = g(n) + h(n)g(n) funcie folosit pentru stabilirea costului drumului de la starea iniial pn la starea curent nh(n) funcie euristic folosit pentru estimarea costului drumului de la starea curent n la starea finalMinimizarea costului total al unui drum

    ExempluProblema rucsacului de capacitate W n care pot fi puse n obiecte (o1, o2, ..., on) fiecare avnd o greutate wi i aducnd un profit pi, i=1,2,...,nSoluia: pentru un rucsac cu W = 5 alegerea obiectelor o1 i o3g(n) = pi, pentru acele obiecte oi care au fost selectateh(n) = pj, pentru acele obiecte care nu au fost selectate i wj

  • SCI A*Algoritm

    bool BestFS(elem, list){found = false;visited = ;toVisit = {start}; //FIFO sorted list (priority queuewhile((toVisit != ) && (!found)){if (toVisit == ) return falsenode = pop(toVisit);visited = visited U {node};if (node == elem)found = true;elseaux = ;for all unvisited children of node do{aux = aux U {child};}toVisit = toVisit U aux; //adding a node onto the FIFO list based on its evaluation // f(n)= g(n)+ h(n) (best one in the front of list)

    } //whilereturn found;}

  • SCI A*Analiza cutrii:Complexitate temporal:b factor de ramnificare (nr de noduri fii ale unui nod)dmax - lungimea (adncimea) maxim a unui arbore exploratT(n) = 1 + b + b2 + + bdmax => O(bdmax)Complexitate spaiald - lungimea (adncimea) soluieiT(n) = 1 + b + b2 + + bd => O(bd)CompletitudineDa Optimalitate Da

    Avantaje Algoritmul care expandeaz cele mai puine noduri din arborele de cutareDezavantaje Utilizarea unei cantiti mari de memorie

    AplicaiiProbleme de planificareProbleme de sume parialePlata unei sume folosind diferite tipuri de moneziProblema rucsaculuiPuzzle-uriDrumul optim ntr-un graf

  • SCI A*Varianteiterative deepening A* (IDA*)memory-bounded A* (MA*)simplified memory bounded A* (SMA*)recursive best-first search (RBFS)dynamic A* (DA*)real time A*hierarchical A*

    Bibliografie suplimentar02/A_IDA.pdf02/A_IDA_2.pdf02/SMA_RTA.pdf02/Recursive Best-First Search.ppt02/IDS.pdf02/IDA_MA.pdfhttp://en.wikipedia.org/wiki/IDA*http://en.wikipedia.org/wiki/SMA*

  • Rezolvarea problemelor prin cutareTipologia strategiilor de cutaren funcie de modul de generare a soluieiCutare constructivConstruirea progresiv a soluieiEx. TSPCutare perturbativO soluie candidat este modificat n vederea obinerii unei noi soluii candidatEx. SAT - Propositional Satisability Problemn funcie de modul de traversare a spaiului de cutareCutare sistematic Traversarea complet a spaiuluiIdeintificarea soluiei dac ea exist algoritmi compleiCutare localTraversarea spaiului de cutare dintr-un punct n alt punct vecin alg

Embed Size (px)
Recommended