Examen solucionado 2012-2013 (2º parcial) (2017)

Examen Catalán
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Gestión Aeronáutica - 2º curso
Asignatura IA - Inteligencia Artificial
Año del apunte 2017
Páginas 7
Fecha de subida 15/06/2017
Descargas 0
Subido por

Vista previa del texto

INTEL·LIGÈNCIA ARTIFICIAL – GESTIÓ AERONÀUTICA CURS 2012-2013 – 2on PARCIAL Cognoms i nom: _________ SOLUCIONS _______________________________ NIU: ______________ 1.- Responeu les següents qüestions: a) Explica de forma resumida en què consisteix la millora de l’algorisme Backtracking anomenada “forward checking” i quin efecte té sobre l’algorisme bàsic de Backtracking.
Consisteix en fer comprovacions de les restriccions per avançat (Forward Checking) i eliminar del domini de cada variable els valors que no poden complir les restriccions. Quan el domini d’una variable es queda buit, tornem enrere en l’arbre de cerca (fem backtracking) L’efecte sobre l’algorisme Backtracking és que ens estalviem cercar en branques que no poden portar a una solució i, per tant, l’algorisme és més ràpid.
b) Quins són els problemes principals del mètode dels “Factors de certesa” que s’utilitza en els sistemes basats en regles? Problemes del model de Factors de Certesa: • És un model que es va fer adhoc pel sistema MYCIN (tot i que es pot aplicar a qualsevol sistema) • No té un fonament teòric fort problemes de coherència en el raonament (Ex.conclusions contradictòries) c) En el següent sistema basat en regles, quines regles actuen com una “meta-regla”? Base de Regles: R1: f1 ^ s1 o1 R2: f1 ^ ¬s2 ^ o1 o2 R3: f1 ^ o2 esborrar (f1) ^ f2 R4: f2 ^ ¬o3 o4 R5: f2 ^ o4 esborrar (f2) ^ f3 R6: f3 ^ o2 esborrar (o4) ← META-REGLA ← META-REGLA d) En un problema de reconeixement de patrons, tenim la mostra de la figura. Els quadrats són mostres de la classe 1, els cercles són de la classe 2 i els triangles de la classe 3. Digueu si les següents afirmacions són certes o falses: d.1) Les mostres estan representades a partir de dues característiques. ( CERT / FALS ) d.2) En aquest problema és adequat aplicar l’algorisme k-means amb k=3. ( CERT / FALS ) d.3) Les mostres es poden separar bé amb dos classificadors lineals. ( CERT / FALS ) d.4) Les mostres es poden separar bé amb la funció de decisió del veí més proper considerant tres representants. ( CERT / FALS ) d.5) Reduint la dimensió de l’espai a una dimensió, les mostres es poden separar tan bé com en l’espai de dimensió 2. ( CERT / FALS ) 2.- Apliqueu un encadenament endavant amb la base de regles i la memòria de treball següents, fent servir les estratègies de resolució de conflictes amb l’ordre en què es donen: Memòria de treball: [ s1, s2, s3, s4 ] Estratègies de resolució de conflictes: 1.- Refractorietat 2.- Recència 3.- Especificitat 4.- Ordre de les regles Base de Regles: R1: s1 ^ s2 ^ s3 o1 R2: s1 ^ s2 ^ s3 ^ s4 o2 R3: s1 ^ o2 o3 R4: s3 ^ o3 o4 R5: o3 ^ o4 L1 R6: o3 ^ o2 L2 Completeu el quadre següent aplicant l’encadenament endavant fins que no hi hagi cap regla aplicable o fins que totes les regles hagin estat aplicades un cop.
1 Memòria de Treball s1, s2, s3, s4 R1,R2 2 s1, s2, s3, s4, o2 3 s1, s2, s3, s4, o2, o3 s1, s2, s3, s4, o2, o3, L2 s1, s2, s3, s4, o2, o3, L2, o4 s1, s2, s3, s4, o2, o3, L2, o4, L s1, s2, s3, s4, o2, o3, L2, o4, L , o1 Pas 4 5 6 7 R2,R1 Regla aplicada R2 o2 R1,R2,R3 R3,R1,R2 R3 o3 R1,R2,R3,R4,R6 R6,R4,R1,R3,R2 R6 L2 R1,R2,R3,R4,R6 R4,R1,R6,R3,R2 R4 o4 Regles aplicables Ordre Accions R1,R2,R3,R4,R5,R6 R5,R1,R6,R4,R3,R2 R5 L R1,R2,R3,R4,R5,R6 R1,R5,R6,R4,R3,R2 R1 o1 R1,R2,R3,R4,R5,R6 ---- --- --- 3.- Una companyia aèria vol que dissenyeu un sistema per fer l’assignació de les aeronaus a les rutes comercials que explota des de Barcelona. La companyia opera 10 rutes i disposa de 12 aeronaus.
Tal com es pot veure a la taula que teniu a continuació, per cada ruta es coneix la distància que ha de recórrer l’avió i s’ha fet una estimació del número de passatgers que hi haurà en cada vol. Per altra banda, cada avió té una certa autonomia (kilòmetres que pot volar sense proveir-se de combustible) i una determinada capacitat (número màxim de passatgers).
Núm avió 1 2 : 10 11 12 Aeronaus Autonomia (kms) 500 3000 : 14000 5000 11000 Capacitat 50 225 : 332 420 288 Num. ruta 1 2 : 10 Rutes Distància (kms) 11500 5170 : 350 Núm. Pax 150 310 : 46 El sistema que heu de dissenyar ha d’assignar una aeronau a cada ruta de forma que: la capacitat de l’aeronau sigui més gran que el nombre estimat de passatgers en els vols de la ruta l’autonomia de l’aeronau sigui més gran que la distància a recórrer en la ruta A més, a les rutes 2 i 3 (que corresponen als vols a Dubai i Qatar) es vol que l’aeronau assignada sigui una de les següents: 10, 11 ó 12. Aquests avions són els més nous i la companyia vol donar el millor servei en aquestes rutes perquè hi viatgen els passatgers amb més poder adquisitiu.
Una altra limitació és que no es pot assignar la mateixa aeronau a dues rutes diferents.
Per solucionar el problema, plantegeu-lo com una cerca per a satisfacció de restriccions responent les següents qüestions: (HI HA ALTRES SOLUCIONS VÀLIDES APART DE LA DONADA) a) Què representen i quines són les variables en aquest problema? Les variables representen... les rutes.
Variables = { R1, R2, ... ,R10 } b) Què representa i quin és el domini dels valors en aquest problema? Els valors del domini representen... les aeronaus.
Domini = { 1, 2, ... , 12 } c) Formuleu les restriccions del problema. (Si necessiteu utilitzar algun operador o funció, definiu-los i indiqueu què retornen) Definim les següents funcions: Autonomia(X) – Funció que retorna l’autonomia de l’aeronau X Capacitat(X) – Funció que retorna la capacitat de l’aeronau X Distància(X) – Funció que retorna la distància de la ruta X Passatgers(X) – Funció que retorna el número de passatgers de la ruta X Les restriccions són: i Capacitat(Ri) > Passatgers(i) i Autonomia(Ri) > Distància(i) R2 ≥ 10 R3 ≥ 10 i,j Ri≠Rj si i≠j d) Completeu els passos de l’algorisme que utilitzaríem per resoldre el problema una vegada plantejat.
Algorisme per a satisfacció de restriccions (Backtracking) 1. Inicialment LVA = [ ] i LVNA = Variables del problema 2. Si LVNA és buida sinó Tenim la solució a LVA Retornar LVA Agafar la 1ª variable de LVNA 3. Per cada valor del domini que podem assignar a la variable, fer: a) Si (es satisfan / no es satisfan) les restriccions: i.
Posar la variable i el valor a LVA ii.
Continuar assignant les variables de LVNA en el següent nivell de l’arbre (Tornar al pas 2 ) b) Si (es satisfan / no es satisfan) les restriccions: i.
Abandonar la branca actual (tornar enrere) 4. Si cap branca ha satisfet totes les restriccions No hi ha solució Obs.- En els passos 3a) i 3b) heu de triar entre les dues possibilitats donades: (es satisfan / no es satisfan) LVA = Llista de variables assignades LVNA = Llista de variables no assignades 4.- Suposeu que volem fer un sistema que classifiqui de forma automàtica les maletes facturades que s’han de carregar a les bodegues dels avions. Així, quan els operaris hagin de posar les maletes a la bodega les tindran classificades i les podran col·locar de forma òptima.
L’objectiu del sistema és que les maletes es classifiquin en 4 classes, però no es té clar quines han de ser aquestes classes. Per fer el sistema, s’han recollit dades de les maletes facturades al darrer mes, de forma que es té el pes, el volum i la relació entre Amplada i Alçada (Amplada/Alçada) de cada maleta facturada: Pes (kg) 30 25 20 18 12 8 7 20 : Volum (cm3) 50000 46000 25000 38000 30000 25000 12000 25000 : Amp. / Alç.
2 1.75 1.5 1 1 1.5 10 5 : Responeu les següents qüestions: a) De quin tipus de problema es tracta? És un problema de reconeixement de patrons.
b) Descriviu la representació del coneixement més adequada per aquest problema. Digueu quina és i descriviu totes les seves components.
La millor representació del coneixement per aquest problema és un espai de característiques de 3 dimensions amb 3 eixos, un per cadascuna de les característiques.
Les característiques del problema són: x1 = pes x2 = volum x3 = relació amplada/alçada En aquest espai, un punt (x1,x2,x3) representa les característiques d’una maleta.
Classes: Tenim 4 classes que corresponen als diferents tipus de maletes. Per tant, l’espai s’ha de dividir en 4 parts.
c) Quin tipus d’aprenentatge seria el més adequat per aquest problema? Justifiqueu la vostra resposta.
L’aprenentatge no supervisat perquè no coneixem a quina classe pertany cadascuna de les mostres d’aprenentatge que ens proporcionen.
d) Quin algorisme s’hauria d’aplicar per resoldre el problema plantejat? Què ens retornaria aquest algorisme? Hauríem d’aplicar l’algorisme k-means amb el paràmetre k=4. El resultat de l’algorisme serien els 4 centres de les classes en què es dividirien les mostres d’aprenentatge.
e) Si s’aplica l’Anàlisi de Components Principals (Transformada de Karhunen-Loeve) a les dades del problema...
e.1) L’objectiu seria reduir la dimensió de l’espai perquè amb menys dimensions tenim més informació. ( CERT / FALS ) e.2) Reduir la dimensió de l’espai perquè amb menys dimensions els càlculs són més fàcils.
( CERT / FALS ) e.3) Si obtenim els vectors propis v1 amb valor propi 1=0.7, v2 amb valor propi 2=0.2 i v3 amb valor propi 3=0.1, i volem reduir la dimensió de l’espai a 2, el millor seria passar a un espai on els eixos serien v1 i v2. ( CERT / FALS ) e.4) Si obtenim els vectors propis v1 amb valor propi 1=0.7, v2 amb valor propi 2=0.2 i v3 amb valor propi 3=0.1, i volem reduir la dimensió de l’espai a 2, el millor seria passar a un espai on els eixos serien v2 i v3. ( CERT / FALS ) 5.- El departament d’economia de la companyia anterior necessita que també els implementeu un sistema basat en conjunts difusos que els permeti avaluar millor els riscos dels projectes que proposen els diferents departaments de la companyia.
L’anàlisi de riscos es realitzarà a partir de dues variables d’entrada: IMPORT: Percentatge de l’import total del projecte que cal finançar a través de crèdits.
Aquesta variable pot prendre els valors lingüístics: Petit (P), Mitjà (M) i Gran (G), amb conjunts difusos definits per les següents funcions de pertinença: PETIT ( x ) 1 50 x 20 0 si x 30 si 30 si x 50 50 si 0 x 30 20 70 x 20 0 MITJA ( x ) x x si 30 x si 50 si 30 GRAN ( x ) 70 x 70 0 x 50 20 1 50 si x 50 si 50 si x 70 x 70 x EMPLEATS: Percentatge d’empleats externs a la companyia necessaris pel projecte.
Aquesta variable pot prendre els valors lingüístics: Reduït (R) i Elevat (E), amb conjunts difusos definits per les següents funcions de pertinença: REDUIT 1 50 y 40 0 ( y) y 10 si si 10 si y 50 50 ELEVAT ( y) y 0 y 10 40 1 y 10 si si 10 y 50 si 50 y La variable de sortida del sistema serà l’indicador del risc del projecte: RISC: Valor entre 0 i 100 que indica el risc que té el projecte.
Aquesta variable pot prendre els valors lingüístics: Baix (B), Normal (N) i Alt (A), amb conjunts difusos definits per les següents funcions de pertinença: 0 BAIX ( z) 1 30 z 20 0 z 10 si si 10 si z 30 30 z NORMAL z 10 si z 10 20 si 10 z 30 1 si 30 z 50 70 z 20 si 50 z 70 ( z) 0 si 70 0 ALT ( z) z 50 20 1 si si 50 si 50 z 70 z 70 z z Els analistes de risc del departament, a partir de la seva experiència en el tema, ens indiquen el comportament aproximat que ha de tenir el sistema. Aquests comportament queda resumit en la taula: IMPORT EMPLEATS REDUIT (R) ELEVAT (E) PETIT (P) B N MITJÀ (M) N A GRAN (G) A A a) Escriviu les regles del sistema que corresponen a la taula dissenyada pels experts.
b) Representeu gràficament els conjunts difusos de totes les variables del sistema.
Suposeu que es vol analitzar el risc d’un projecte que necessita finançar el 50% del seu import i necessita contractar un 20% de personal extern.
c) Calculeu el grau de compliment de l’antecedent de cada regla amb els valors d’entrada donats.
d) Representeu gràficament el conjunt difús de la conclusió de les regles amb grau de compliment de l’antecedent diferent de zero.
e) Representeu gràficament el conjunt difús global de les conclusions de totes les regles.
f) Segons el sistema, quin és el valor del risc del projecte en l’escala de 0 a 100? Indiqueu el mètode utilitzat per calcular aquest valor.
...

Comprar Previsualizar