22/ago/2009uvm - chapultepec1 licenciaturas ejecutivas - lsca introducciÓn a la inteligencia...

22/AGO/2009 UVM - CHAPULTEPEC 1

LICENCIATURAS EJECUTIVAS - LSCA

INTRODUCCIÓN A LA INTELIGENCIA ARTIFICIAL

Profesor: Joel Pérez González

PLANTEL CHAPULTEPEC


4. Solución de problemas por medio de la inteligencia artificial:

• 4.1 Procedimiento de representación de problemas 4.1.1 Algoritmos • 4.1.2 Heurística

• 4.2 Teoría de juegos• 4.3 Teoría del caos • 4.4 Método de generación y prueba• 4.5 Método de análisis de medios y metas• 4.6 Método de reducción del problema

Solución de problemas por medio de la inteligencia artificial


Representación:

Principio de la representación: Una vez que un problema se describe mediante una buena representación, el problema está casi resuelto (80%).



Representación:

Una representación tiene 4 partes:

Parte Léxica: Determina los símbolos que están permitidos en el vocabulario de la representación.

Parte Estructural: describe las restricciones sobre la forma en que los símbolos pueden ordenarse en una representación

Parte Operativa: Especifica los procedimientos de de acceso que permiten crear descripciones, así como la forma de modificarlas y utilizarlas para responder preguntas.

Parte Semántica: establece la forma de asociar el significado con las descripciones.



Resolución de problemas:

La resolución de problemas es uno de los procesos básicos de razonamiento que la inteligencia artificial trata de abordar El objetivo consiste en lograr que la máquina ayude a un

experto humano a encontrar la solución a un determinado problema (de forma más rápida, más exacta, más fiable...)

Pero... ¿cómo expresar el problema de forma computacional? ¿cómo puede resolverlo la máquina de forma eficiente?.




Deseamos definir cualquier tipo de problema de manera que se pueda resolver automáticamente

Necesitamos: Una representación común para todos los problemas Algoritmos que usen alguna estrategia para resolver

problemas definidos en esa representación común.




Definición de un Problema: Si abstraemos los elementos de un problema podemos

identificar: Un punto de partida. Un objetivo a alcanzar. Acciones a nuestra disposición para resolver el problema. Restricciones sobre el objetivo. Elementos que son relevantes en el problema definidos por el

tipo de dominio.




Representación del Problema: Existen diferentes formas de representar problemas para

resolverlos de manera automática Representaciones generales:

Espacio de estados: un problema se divide en un conjunto de pasos de resolución desde el inicio hasta el objetivo

Reducción a subproblemas: un problema se puede descomponer en una jerarquía de subproblemas.

Representaciones para problemas específicos Resolución de juegos. Satisfacción de restricciones.



Espacio de versiones:

Espacios de Estados: Representación del conocimiento a través de las acciones del agente.

Búsqueda en el espacio de estados (operadores): Resolución del problema mediante proyección de las distintas acciones.




Estado: Descripción de una posible situación en el problema ( Abstracción de propiedades). Distinguiremos dos estado especiales

Estado Inicial (punto de partida). Estado Final (objetivo del problema).

Operadores: Representan un conjunto finito de acciones básicas que transforman unos estados en otros.

Aplicabilidad: precondición y poscondición. Estado resultante de su aplicación (aplicable) a un estado. Depende de la representación de los estados.

Solución de un problema: Secuencia de acciones a realizar para conseguir el objetivo u Secuencia de operadores cuya aplicación desde el estado inicial obtiene un estado final




Descripción de un problema en Espacio de Estados Definir el conjunto de estados del problema (explícita o

implícitamente). Especificar el estado inicial. Especificar el estado final o las condiciones que cumple. Especificar los operadores de cambio de estado

(condiciones de aplicabilidad y función de transformación).

Especificar el tipo de solución: La secuencia de operadores o el estado final Una solución cualquiera, la mejor (definición de coste).




8-Puzzle




El mundo de los bloques




El mundo de los bloques

Inicialmente los 4 operadores disponibles son:

APILAR(A, B) DESAPILAR(A, B) AGARRAR(A) BAJAR(A)



Espacio de versiones:El mundo de los bloques




Torres de Hanoi



Espacio de versiones:Torres de Hanoi



Algorítmo:

Es un método para resolver un problema mediante una serie de pasos definidos, precisos y finitos.

Un algoritmo es un conjunto de pasos claramente definidos, que a partir de una cierta entrada produce una determinada salida.



Algorítmo:

Todo algoritmo debe ser:

Preciso, es decir, cada instrucción debe indicar de forma inequívoca que se tiene que hacer.

Finito, es decir, debe tener un número limitado de pasos.

Definido, es decir, debe producir los mismos resultados para las mismas condiciones de entrada.



Algorítmo:

Algoritmo determinístico:

Un algoritmo es determinístico si la respuesta que produce se puede conocer a partir de los datos de entrada.



Heurística:

Se dice de aquel truco o regla empírica que ayuda a encontrar la solución de un problema (pero que no garantiza que se encuentre).

Se apoya en el resultado obtenido en un análisis de alternativas de experiencias anteriores similares. De las mismas, a se deducen una serie de reglas empíricas o heurísticas que de ser seguidas, conducen a la selección de la mejor alternativa en todas o la mayoría de las veces.

Búsquedas heurísticas: (descubrir) Disponen de información especifica sobre el problema con el que se

puede mejorar la eficiencia del proceso de búsqueda



Heurística :

En programación se dice que un algoritmo es heurístico cuando la solución no se determina en forma directa, sino mediante ensayos, pruebas y reensayos.

El método consiste en generar candidatos de soluciones posibles de acuerdo a un patrón dado; luego los candidatos son sometidos a pruebas de acuerdo a un criterio que caracteriza a la solución.

Si un candidato no es aceptado, se genera otro; y los pasos dados con el candidato anterior no se consideran. Es decir, existe inherentemente una vuelta atrás, para comenzar a generar un nuevo candidato; por esta razón, este tipo de algoritmo también se denomina "con vuelta atrás" (backtracking en nglés).



Heurística :

A los algoritmos heurísticos reciben el nombre de estrategias de búsqueda informada, mientras que los ciegos son búsquedas no informadas.

Desafortunadamente las heurísticas no lo miden todo, simplemente pretende encontrar una solución lo mejor posible al problema.

Un método heurístico más avanzado lo comprenden los algoritmos genéticos.



Heurística :

Son características de los métodos heurísticos:

No garantizan que se encuentre una solución, aunque existan soluciones.

Si encuentran una solución, no se asegura que ésta tenga las mejores propiedades (que sea de longitud mínima o de coste óptimo).

En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable..



Heurística :

En general, los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.



Heurística : Problema del cajero automático:

Los cajeros automáticos (ATM) son dispositivos embebidos cuya función consiste en despachar a clientes proporcionando dinero en efectivo.

Cuentan con recursos finitos en este caso billetes de distintas nominaciones $1000, 500, 200, 10 y 50 en distintas cantidades.

Al solicitar una cantidad el cajero debe “ingeniarselas” para dar la mejor combinación de dinero.

Se debe brindar de una buena combinación ya que sino se pueden acabar los billetes de cierta denominación pudiendo dejar sin operaciones a muchos clientes.




Una heurística balanceada muy simple pero poco eficiente consiste en repartir dinero de una denominación hasta tratar de completar la suma (por ejemplo dar billetes muy altos (puede ser bajos pero no es tan eficiente) y después completarlos con los de siguiente denominación).

Esta solución da como resultado que primero se acaben todos los billetes de una denominación.

Una solución simple y más eficiente es repartir dinero en forma balanceada, empezando por billetes de altas denominaciones hasta bajas. Este esquema es más justo ya que va quitando billetes por igual, desgraciadamente esta es su deficiencia ya que un billete de 50 tendría un peso igual a uno de 500.




Una mejor solución consiste en ponerle ponderación a cada recurso (billete) de acuerdo a su valor monetario y a la cantidad de recurso disponible, por lo que se ocuparía una función de similaridad que quizás tenga que ser dinámica y quizás no muy sencilla de calcular.

En general existen diversas alternativas de solución para el mismo problema. En el caso de los cajeros se prefiere una heurística de acabar primero los billetes más grandes ya que de los chicos hay mayor cantidad.

Otra solución de entre las mejores consiste en crear diversas soluciones para después comparar aquellas que sean más benéficas, pero esto requiere de tiempo y de espacio.



Comentarios…..

Representación del Conocimiento

22/ago/2009uvm - chapultepec1 licenciaturas ejecutivas - lsca introducciÓn a la inteligencia...

Documents