HEURISTICAS PARA EL PROBLEMA DEL AGENTE VIAJERO

Se denomina heurística a la capacidad de un sistema para realizar de forma inmediata innovaciones positivas para sus fines. La capacidad heurística es un rasgo característico de los humanos, desde cuyo punto de vista puede describirse como el arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad y el pensamiento lateral o pensamiento divergente. 

Las restricciones que fastidian por su cantidad y estructura son las ultimas (las de destrucción de sub-recorridos). Lo que queda sin ellas es un simple Problema de Asignación (flujo en redes). Que se resuelve fácilmente. Entonces es natural que los algoritmos de B + B o de planos cortantes para el PAV utilicen algún esquema de relajación - restricción que siga estas líneas.

 Los algoritmos modificados relajan estas restricciones y resuelven la relajación (asignación). Si la solución obtenida es un recorrido, tenemos COR, listo. Caso contrario, añadir restricción que destruya algún sub-recorrido (si se hace directo es planos cortantes, si se hace a través de cotas y en subgrafos es B+B) y proceder con la nueva relajación. Estos algoritmos son computacionalmente aplicables s´olo a problemas con unos pocos cientos de ciudades. Para problemas m´as grandes se necesitan métodos heurísticos.

ALGUNAS HEURISTICAS PARA EL PAV:

Las heurísticas a ser discutidas se pueden clasificar en dos tipos: Las que construyen recorridos y las que los mejoran. Comenzamos con las primeras.

La idea se puede resumir así:

1. Encontrar un sub-recorrido inicial (basta que tenga dos ciudades pero puede ser de más).

2. Seleccionar una ciudad a ser añadida al sub-recorrido, usando alguna regla de selección.

3. Insertar el nodo correspondiente en el sub-recorrido, basándose en un criterio de inserción.

4. Si se tiene un recorrido, parar. Caso contrario ir a 2.

Las distintas reglas de selección y criterios de inserción dan lugar a diferentes heurísticas. Veamos una de ellas: La heurística de inserción más barata.

Se comienza con un sub-recorrido T con dos ciudades i1 e i2, tales que

di1i2 + di2i1 = mın/i=j (dij + dji)

Es decir, el sub-recorrido más cortó entre dos ciudades. Luego se busca el costo mínimo de inserción en el sub-recorrido:

ck∗ = mın/(i, j)∈T (dik + dkj − dij)

Y se selecciona un nodo k∗ con ese costo. Luego se inserta el nodo entre las ciudades involucradas en el cálculo de ck∗. Finalmente se repite este proceso (con los sub-recorridos que se van generando) hasta construir un recorrido.

EJEMPLO DE LA HEURÍSTICA DE INSERCIÓN MÁS BARATA

Consideremos el PAV dado por la siguiente matriz de distancias:

En primer lugar tenemos que encontrar el sub-recorrido más barato con dos ciudades. Esto se hace calculando mıni6=j (dij + dji) que corresponde a sumar elementos simétricos de la matriz D y ver cuál nos da menor. En este caso el más pequeño es d78 + d87 = 3 + 1 = 4.

Calculemos ahora el mínimo costo de inserción: ck∗ = mın(i, j)∈T (dik + dkj − dij) :

De donde el mínimo valor es 12 y se obtiene de tres formas. Seleccionamos la inserción del nodo 1 entre los nodos 8 y 7. Las restantes iteraciones se muestran en la siguiente tabla:

Dando como recorrido final: 1 → 2 → 3 → 7 → 8 → 6 → 4 → 5 → 1. Este recorrido, casualmente, es óptimo. No siempre se corre con la misma suerte. Note que en la tercera columna se calcula, en cada fila y para cada k, el mínimo costo de inserción de ese k particular (en algunos casos hay empate y el k se repite), y luego se toma el mínimo de todos ellos.

OPINION SOBRE EL TEMA

La heurística se puede describir como el arte y la ciencia del descubrimiento y de invención de resolver problemas mediante la creatividad y el pensamiento. En si las heurística y el problema del agente viajero se clasifican en dos tipos las que construyen recorridos y las que la mejoran. El problema del agente viajero consiste en encontrar el recorrido más corto.

BIBLIOGRAFIA

http://prof.usb.ve/bfeijoo/dat/CO5423/200509_CO5423_Clase_17.pdf

SISTEMAS DE PRODUCCIÓN

DEFINICIÓN:

– Sistemas inteligentes basados en reglas que operan frente a una base de hechos con mecanismos de emparejamiento formando parte explícita de su arquitectura.

SE CLASIFICAN EN DOS CATEGORÍAS SEGÚN SU ESTRUCTURA DE CONTROL:

Ø  Sistemas dirigidos por los datos

Ø  Sistemas dirigidos por los objetivos

Clasificación de Sistemas de Producción

·         SISTEMAS DIRIGIDOS POR LOS DATOS

– Las inferencias se obtienen cuando los antecedentes de alguna (o más de una) de sus reglas de producción se emparejan con, al menos, una parte de los hechos que describen el estado actual.

– Cuando esto ocurre, se dice que la regla en cuestión se ha activado, y está en condiciones de ser ejecutada. Su ejecución o no dependerá de la estrategia de exploración elegida.

– Son menos específicos, porque ejecutarán todas las reglas disponibles en función de la información introducida.

·         SISTEMAS DIRIGIDOS POR LOS OBJETIVOS

– Tanto los antecedentes como los consecuentes de las reglas deben ser considerados como aserciones sobre los datos. En este caso, la activación de las reglas tiene lugar por medio de un encadenamiento regresivo, y el emparejamiento se efectúa a través de las conclusiones de las reglas.

– Para alcanzar una determinada meta hay que configurar un proceso evocativo en el que, de forma recursiva, se van estableciendo los antecedentes de las metas como submetas de orden inferior.

– Son más específicos, porque la ejecución lleva implícito un proceso de búsqueda.

ARQUITECTURA DE SISTEMAS DE PRODUCCIÓN

OPINIÓN  SOBRE EL TEMA

Mi opinión el sistema de producción, como ya se mencionó este se encarga de facilitar la ejecución de distintos problemas para las modernas organizaciones y para la práctica administrativa.

Ya que la tecnología y la ciencia son aspectos que se han convertido en una fuerza muy grande para la sociedad ya que estas influyen en todas las actividades que se realizan a nivel social

BIBLIOGRAFIA

http://quegrande.org/apuntes/EI/4/IA/teoria/0910/tema_6__sistemas_de_produccion.pdf

PROBLEMAS Y ESPACIO DE ESTADOS

Es un proceso usado en el campo de la Informática, incluyendo la Inteligencia Artificial (IA), en el cual se consideran sucesivos estados de una instancia, con la meta de encontrar un "estado final" con las características deseadas.

Los problemas se modelan a menudo como un espacio de estados, un conjunto de estados que un contienen el problema. El conjunto de estados forma un grafo donde dos estados están conectados si hay una operación que pueda se pueda llevar a cabo para transformar el primer estado en el segundo.

La búsqueda en el espacio de estados difiere de los métodos de búsqueda tradicionales porque el espacio de estados está implícito: El grafo del espacio de estados típico es mucho es demasiado grande para generarlo y guardarlo en memoria. En su lugar, los nodos se generan en el momento en que se exploran y generalmente son descartados después. Una solución puede consistir solamente en un estado objetivo, o en un camino desde un estado inicial hasta el estado final.

FORMULACIÓN DE UN PROBLEMA

„ 

Ø „ Proceso que consiste en decidir que  acciones y estados habrán de considerarse

    Ø  „ ¿Qué condiciones son necesarias?

·         ‰ ¿Qué sucede si no hay forma de discernir qué camino nos lleva a la meta?

·         ‰ ¿Qué decisión tomar en tal situación?

BÚSQUEDAS

 En términos generales, cuando un agente tiene ante si diversas opciones cuyo valor tiene ante si diversas opciones cuyo valor ignora, éstas se tienen que evaluar de alguna forma evaluar las diversas secuencias de acciones que le conducen a estados cuyo valor se conoce.

Ø     Algoritmo de búsqueda

· ‰ Entrada: un problema

· ‰ Salida: solución que adopta la forma de una secuencia de acciones

§  Una vez encontrada una solución, se procede a ejecutar las acciones

AGENTES QUE RESUELVEN PROBLEMAS

􀂄 Formular: decidir qué acciones y estados deberán considerarse

􀂄 Buscar: proceso para hallar las secuencias de acciones que conduzcan a una meta

􀂄 Ejecutar: fase donde se llevan a cabo las acciones que conducen a la meta

BIBLIOGRAFIA

http://www.cs.buap.mx/~iolmos/ia/Sesion5_Busquedas1.pdf

¿QUE ES INTELIGENCIA?

La inteligencia (del latín intellegentĭa) es la capacidad de pensar, entender, asimilar, elaborar información y utilizarla para resolver problemas. El Diccionario de la lengua española de la Real Academia Española define la inteligencia, entre otras acepciones como la «capacidad para entender o comprender» y como la «capacidad para resolver problemas». La inteligencia parece estar ligada a otras funciones mentales como la percepción, o capacidad de recibir información, y la memoria, o capacidad de almacenarla.

¿QUE ES ARTIFICIAL?

Artificial es algo que no es natural. Su sentido original, en relación con un artefacto o artificio, se refiere a un producto de la actividad humana; como sinónimo de «hecho por el hombre». También se utiliza en el sentido de «falso», en el sentido de que pretende ser o mostrar lo que no es, como un sustituto de lo natural; como en césped artificial o edulcorante artificial.

Artificial es cualquier cosa hecha con intención y propósito, teniendo la capacidad de modificar su entorno para ello. Este propósito es para obtener un beneficio. Esto significa que no solo el hombre, sino otros seres vivos, producen lo que se pueda llamar artificial. Como algunos ejemplos, colmenas de las abejas, galerías de las hormigas, nidos de los pájaros (a veces para guardar los huevos, a veces para impresionar a la hembra...), estructuras de las termitas, cuevas de los conejos, etc.

¿QUE ES INTELIGENCIA ARTIFICIAL?

La inteligencia artificial (IA) es un área multidisciplinaria que, a través de ciencias, tales como la informática, la lógica y la filosofía, estudia la creación y diseño de entidades capaces de razonar por si mismas utilizando como paradigma la inteligencia humana.

Tan general y amplio como eso, es que reúne varios campos (robótica, sistemas expertos, por ejemplo), todos los cuales tienen en común la creación de máquinas que pueden pensar. En ciencias de la computación se denomina inteligencia artificial a la capacidad de razonar de un agente no vivo. John McCarthy, acuñó el término en 1956, la definió: "Es la ciencia e ingenio de hacer máquinas inteligentes, especialmente programas de cómputo inteligentes."

INFORMÁTICA: Es una ciencia que estudia métodos, procesos, técnicas, con el fin de almacenar, procesar y transmitir información y datos en formato digital. La informática se ha desarrollado rápidamente a partir de la segunda mitad del siglo XX, con la aparición de tecnologías tales como el circuito integrado, Internet y el teléfono móvil.

LÓGICA: Es una ciencia formal que estudia los principios de la demostración e inferencia válida. La palabra deriva del griego antiguo λογική (logike), que significa «dotado de razón, intelectual, dialéctico, argumentativo», que a su vez viene de λόγος (logos), «palabra, pensamiento, idea, argumento, razón o principio».

FILOSOFÍA: (del latín philosophĭa, y este del griego antiguo φιλοσοφία, «amor por la sabiduría»)¹ es el estudio de una variedad de problemas fundamentales acerca de cuestiones como la existencia, el conocimiento, la verdad, la moral, la belleza, la mente y el lenguaje.  Al abordar estos problemas, la filosofía se distingue del misticismo, la mitología y la religión por su énfasis en los argumentos racionales por sobre los argumentos de autoridad, y de la ciencia porque generalmente lleva adelante sus investigaciones de una manera no empírica, sea mediante el análisis conceptual, los experimentos mentales, la especulación u otros métodos a priori, aunque sin desconocer la importancia de los datos empíricos.

CARACTERÍSTICAS DE LA INTELIGENCIA ARTIFICIAL

Stuart Russell y Peter Norvig diferencian estos tipos de la inteligencia artificial:

Sistemas que piensan como humanos.- Estos sistemas tratan de emular el pensamiento humano; por ejemplo las redes neuronales artificiales. La automatización de actividades que vinculamos con procesos de pensamiento humano, actividades como la Toma de decisiones, resolución de problemas, aprendizaje.

       Sistemas que actúan como humanos.- Estos sistemas tratan de actuar como humanos; es         decir, imitan el comportamiento humano; por ejemplo la robótica. El estudio de cómo lograr que                   los computadores realicen tareas que, por el momento, los humanos hacen mejor.

          Sistemas que piensan racionalmente.- Es decir, con lógica (idealmente), tratan de                     imitar o   emular el pensamiento lógico racional del ser humano; por ejemplo                                   los sistemas expertos. El estudio de los cálculos que hacen posible percibir, razonar y                   actuar.

              Sistemas que actúan racionalmente (idealmente). – Tratan de emular de                     forma racional el comportamiento humano; por ejemplo los agentes inteligentes.                 Está relacionado con conductas inteligentes en artefactos. 

CLASIFICACIÓN

INTELIGENCIA ARTIFICIAL CONVENCIONAL

 

Está basada en el análisis formal y estadístico del comportamiento humano ante diferentes problemas:

Razonamiento basado en casos: Ayuda a tomar decisiones mientras se resuelven ciertos problemas concretos.

Sistemas expertos: Infieren una solución a través del conocimiento previo del contexto en que se aplica y ocupa de ciertas reglas o relaciones.

Redes bayesianas: Propone soluciones mediante inferencia estadística.

Inteligencia artificial basada en comportamientos: que tienen autonomía y pueden auto-regularse y controlarse para mejorar.

 INTELIGENCIA ARTIFICIAL COMPUTACIONAL

La Inteligencia Computacional implica desarrollo o aprendizaje interactivo (por ejemplo, modificaciones interactivas de los parámetros en sistemas conexionistas). El aprendizaje se realiza basándose en datos empíricos.